Neighborhood Structure Configuration Models

ACM Web Conference (WWW), pp. 210–220

Abstract

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. Our key innovation is to employ a colored Configuration Model with colors derived from iterations of the so-called Color Refinement algorithm. 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. Our work enables to efficiently generate samples with a precisely controlled similarity to the original network, especially for large networks.

Authors 4

1. Felix I. Stamm Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Germany

2. Michael Scholkemper Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Germany

3. Markus Strohmaier

   University of Mannheim · GESIS - Leibniz Institute for the Social Sciences

   Affiliation as printed

   University of Mannheim & GESIS, Germany

4. Michael T. Schaub Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Germany