Detecting mesoscale structures by surprise

Abstract

The importance of identifying the presence of mesoscale structures in complex networks can be hardly overestimated. So far, much attention has been devoted to the detection of communities, bipartite and core-periphery structures on binary networks: such an effort has led to the definition of a unified framework based upon the score function called surprise, i.e. a p-value that can be assigned to any given partition of nodes, on both undirected and directed networks. Here, we aim at making a step further, by extending the entire framework to the weighted case: after reviewing the application of the surprise-based formalism to the detection of binary mesoscale structures, we present a suitable generalization of it for detecting weighted mesoscale structures, a topic that has received much less attention. To this aim, we analyze four variants of the surprise; from a technical point of view, this amounts at employing four variants of the hypergeometric distribution: the binomial one for the detection of binary communities, the multinomial one for the detection of binary "bimodular" structures and their negative counterparts for the detection of communities and "bimodular" structures on weighted networks. On top of that, we define two "enhanced" variants of surprise, able to encode both binary and weighted constraints and whose definition rests upon two suitable generalizations of the hypergeometric distribution itself. As a result, we present a general, statistically-grounded approach to detect mesoscale structures on networks via a unified, suprise-based framework. To illustrate the performance of our methods, we, first, test them on a variety of well-established, synthetic benchmarks and, then, apply them to several real-world networks, i.e. social, economic, financial and ecological ones. Moreover, we attach to the paper a Python code implementing all the considered variants of surprise.

32 pages, 4 tables, 12 figures. Python code available at: https://github.com/EmilianoMarchese/SurpriseMeMore

References in corpus (12)

• Maps of random walks on complex networks reveal community structure
• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• A fitness model for the Italian Interbank Money Market
• Identification of core-periphery structure in networks
• Generalized Bose-Fermi statistics and structural correlations in weighted networks
• On network bipartivity
• Surprise maximization reveals the community structure of complex networks
• Network Community Detection: A Review and Visual Survey
• Reconstructing networks
• Meta-validation of bipartite network projections
• An algorithm for network community structure determination by surprise

Cited by in corpus (5)

• Testing structural balance theories in heterogeneous signed networks
• The Weighted Bitcoin Lightning Network
• Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• Assessing imbalance in signed brain networks