Modularity Maximization for Graphons

SIAM Journal on Applied Mathematics, vol. 82, pp. 1930–1952

Abstract

Abstract. Networks are a widely used tool for investigating the large-scale connectivity structure in complex systems and graphons have been proposed as an infinite-size limit of dense networks. The detection of communities or other meso-scale structures is a prominent topic in network science as it allows the identification of functional building blocks in complex systems. Similarly, we may want to simplify graphons in terms of communities, in order to gain a comprehensible description of their meso-scale structure. This raises the question of how communities in graphons can be identified. In this paper, we define a graphon modularity and demonstrate that it can be maximized to detect communities in graphons. We then investigate specific synthetic graphons and show that they may show a wide range of different community structures. We also reformulate the graphon-modularity maximization as a continuous optimization problem and so prove the optimal community structure or lack thereof for some graphons, something that is usually not possible for networks. Furthermore, we demonstrate that estimating a graphon from network data as an intermediate step can improve the detection of communities, in comparison with exclusively maximizing the modularity of the network. While the choice of graphon estimator may strongly influence the accord between the community structure of a network and its estimated graphon, we find that there is a substantial overlap if an appropriate estimator is used. Our study demonstrates that community detection for graphons is possible and may serve as a privacy-preserving way to cluster network data.

Authors 3

1. Florian Klimm

   University of Cambridge · Imperial College London · Freie Universität Berlin · Max Planck Institute for Molecular Genetics · MRC Mitochondrial Biology Unit

   Affiliation as printed

   Department of Mathematics, Imperial College London, London, SW7 2AZ, UK; MRC Mitochondrial Biology Unit, University of Cambridge, Cambridge, CB2 0XY, UK; Department of Computational Molecular Biology, Max Planck Institute for Molecular Genetics and Department of Computer Science, Freie Universität Berlin, Berlin, 14195, Germany ()

   Department of Mathematics, Imperial College London, London, SW7 2AZ, UK

2. Nick S. Jones

   Imperial College London

   Affiliation as printed

   Department of Mathematics, Imperial College London, London, SW7 2AZ, UK ()

3. Michael T. Schaub Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen University, Aachen, 52074, Germany ()