Michael Scholkemper: Structural Network Analysis

 

Networks are a powerful abstraction to understand a range of complex systems such as

• protein interactions relating to drug efficacy,
• structural changes due to disease in respective tissue,
• the emergence of consensus or polarization through social interactions and epidemic spread, or
• the flow of traffic.

To comprehend such networks, we often seek patterns in their connections, e.g., densely interconnected communities or core-periphery structure, which facilitate a simpler or faster analysis of such systems. Communities are in this context typically envisioned as comparably tightly-knit nodes within a graph, though a range of different notions exists often defined in an algorithmic way, or by means of some cost function that is to be optimized. A complementary notion to „community“ is that of a role partition of the node. The concept of node roles – or node equivalences – originates in social network analysis, where a node‘s role – contrary to its community – is often related to symmetries or connectivity, rather than proximity. Both of these complementary approaches aim to simplify the network‘s complexity and provide a reduced view of the networks structure.

The intricacy of node role extraction derives from the lack of a clear definition of the role of a node in mathematical terms. Traditionally, exact equivalences such as automorphic or regular equivalence are considered. These approaches, while extremely expressive, yield a multitude of distinct roles that are incomparable to one another. More recently, node representation through embeddings aiming to capture these structural symmetries have been proposed. While these are clearly comparable by means of some distance measure in the vector space, the plethora of node embedding techniques yields no insight into what the role of a node is.

This research aims to derive a general definition of a node’s role and the resulting reduced view of the network’s structure. This, in turn, can then be applied to signal processing on graphs to provide a reduced view of a complex system of which only a process on the nodes but not the underlying network is observed. Apart from the structural analysis of a graph these node roles can also be used to obtain generative models that assert a certain global structure but are flexible locally. This is useful e.g. as a means of anonymization when sharing sensitive network data.