Generic criticality of community structure in random graphs
arXiv:1312.6494 · doi:10.1103/PhysRevE.90.032815
Abstract
We examine a community structure in random graphs of size and link probability determined with the Newman greedy optimization of modularity. Calculations show that for communities are nearly identical with clusters. For the average sizes of a community and of the giant community show a power-law increase and . From numerical results we estimate , , and using the probability distribution of sizes of communities we suggest that should hold. For the community structure remains critical: (i) and have a power law increase with ; (ii) the probability distribution of sizes of communities is very broad and nearly flat for all sizes up to . For large the modularity decays as , which is intermediate between some previous estimations. To check the validity of the results, we also determined the community structure using another method, namely a non-greedy optimization of modularity. Tests with some benchmark networks show that the method outperforms the greedy version. For random graphs, however, the characteristics of the community structure determined using both greedy an non-greedy optimizations are, within small statistical fluctuations, the same.
arXiv comment4 pages, non-greedy optimization added, Phys. Rev. E (accepted)
References in corpus (14)
- Statistical mechanics of complex networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Fast algorithm for detecting community structure in networks
- Cooperative Game Theory Approaches for Network Partitioning
- Random graphs with arbitrary degree distributions and their applications
- Community detection algorithms: a comparative analysis
- Statistical Mechanics of Community Detection
- Community detection in complex networks using Extremal Optimization
- Modularity from Fluctuations in Random Graphs and Complex Networks
- Roulette-wheel selection via stochastic acceptance
- Clique percolation in random networks
- Modularity-Maximizing Network Communities via Mathematical Programming