Emergence of network communities driven by local rules

Abstract

Natural systems are modeled by networks with nodes and links. Often the nodes are segregated into communities with different connectivity patterns. Node heterogeneity such as political affiliation in social networks or biological function in gene networks are highlighted as key factors driving the segregation of nodes into communities. Here, by means of numerical simulations, I show that node heterogeneity is not a necessary requirement. To this end I introduce the Ramsey community number, $r_{\kappa }$, the minimum graph size that warranties the emergence of network communities with almost certainty. Using the stochastic block model and Infomap methods for community detection, I show that networks generated by local rules have finite $r_{\kappa }$ values while their randomized versions do not have emergent communities. I conjecture that network communities are an emergent property of networks evolving with local rules.

9 pages, 11 figures, 1 table. Final version accepted for publication in PRE

References in corpus (17)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Maps of random walks on complex networks reveal community structure
• Resolution limit in community detection
• Defining and identifying communities in networks
• Stochastic blockmodels and community structure in networks
• The statistical mechanics of networks
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Growing Scale-Free Networks with Small World Behavior
• A Bayesian Approach to Network Modularity
• Triadic closure as a basic generating mechanism of communities in complex networks
• Log-Networks
• Inference of hyperedges and overlapping communities in hypergraphs
• Disentangling homophily, community structure and triadic closure in networks
• Mapping flows on sparse networks with missing links
• Micro, Meso, Macro: the effect of triangles on communities in networks
• Network reconstruction via the minimum description length principle