Bi-Weekly Talk: Michael Scholkemper: Spectral Implications of Graph Structure and a Random Graph Model to Preserve It

Wednesday, April 05, 2023, 10:30am

Location: RWTH Aachen University, Department of Computer Science - Ahornstr. 55, building E3, room 9u10

Speaker: Michael Scholkemper



Networks have become a powerful abstraction to understand a range of complex systems. 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. The core-periphery structure is often associated with the importance or the role of the nodes in the graph.
While e.g. the Stochastic Block Model can be used to model networks with a similar community structure, there are few efficient methods that aim to preserve the roles within a graph. We develop a new method to efficiently sample synthetic networks that preserve the d-hop neighborhood structure of a given network for any given d. The proposed algorithm trades off the diversity in network samples against the depth of the neighborhood structure that is preserved. We prove that with increasing iterations the preserved structural information increases: The generated synthetic networks and the original network become more and more similar, and are eventually indistinguishable in terms of centrality measures such as PageRank, HITS, Katz centrality and eigenvector centrality.