Growing networks of overlapping communities with internal structure
arXiv:1603.05566 · doi:10.1103/PhysRevE.94.022317
Abstract
We introduce an intuitive model that describes both the emergence of community structure and the evolution of the internal structure of communities in growing social networks. The model comprises two complementary mechanisms: One mechanism accounts for the evolution of the internal link structure of a single community, and the second mechanism coordinates the growth of multiple overlapping communities. The first mechanism is based on the assumption that each node establishes links with its neighbors and introduces new nodes to the community at different rates. We demonstrate that this simple mechanism gives rise to an effective maximal degree within communities. This observation is related to the anthropological theory known as Dunbar's number, i.e., the empirical observation of a maximal number of ties which an average individual can sustain within its social groups. The second mechanism is based on a recently proposed generalization of preferential attachment to community structure, appropriately called structural preferential attachment (SPA). The combination of these two mechanisms into a single model (SPA+) allows us to reproduce a number of the global statistics of real networks: The distribution of community sizes, of node memberships and of degrees. The SPA+ model also predicts (a) three qualitative regimes for the degree distribution within overlapping communities and (b) strong correlations between the number of communities to which a node belongs and its number of connections within each community. We present empirical evidence that support our findings in real complex networks.
arXiv comment14 pages, 8 figures, 2 tables
References in corpus (30)
- Emergence of scaling in random networks
- Community structure in social and biological networks
- Community detection in graphs
- Power-law distributions in empirical data
- Error and attack tolerance of complex networks
- Uncovering the overlapping community structure of complex networks in nature and society
- Hierarchical structure and the prediction of missing links in networks
- Stochastic blockmodels and community structure in networks
- Link communities reveal multiscale complexity in networks
- Finding statistically significant communities in networks
- Overlapping Community Detection in Networks: the State of the Art and Comparative Study
- Missing and spurious interactions and the reconstruction of complex networks
- Validation of Dunbar's number in Twitter conversations
- Line Graphs, Link Partitions and Overlapping Communities
- Discrete Hierarchical Organization of Social Group Sizes
- Fuzzy communities and the concept of bridgeness in complex networks
- Detecting highly overlapping community structure by greedy clique expansion
- Community structure and scale-free collections of Erdös-Rényi graphs
- Revisiting Date and Party Hubs: Novel Approaches to Role Assignment in Protein Interaction Networks
- Entropy of stochastic blockmodel ensembles
- Global efficiency of local immunization on complex networks
- Model selection and hypothesis testing for large-scale network models with overlapping groups
- Immunization of networks with community structure
- Fundamental statistical features and self-similar properties of tagged networks
- Detecting Important Nodes to Community Structure Using the Spectrum of the Graph
- Statistics of Lead Changes in Popularity-Driven Systems
- Structural preferential attachment: Network organization beyond the link
- Structural preferential attachment: Stochastic process for the growth of scale-free, modular and self-similar systems
- Complex networks as an emerging property of hierarchical preferential attachment
- A shadowing problem in the detection of overlapping communities: lifting the resolution limit through a cascading procedure