Link community detection through global optimization and the inverse resolution limit of partition density
arXiv:1601.05100 · doi:10.1038/s41598-017-12432-1
Abstract
We investigate the possibility of global optimization-based overlapping community detection, using link community framework. We first show that partition density, the original quality function used in link community detection method, is not suitable as a quality function for global optimization because it prefers breaking communities into triangles except in highly limited conditions. We analytically derive those conditions and confirm it with computational results on direct optimization of various synthetic and real-world networks. To overcome this limitation, we propose alternative approaches combining the weighted line graph transformation and existing quality functions for node-based communities. We suggest a new line graph weighting scheme, a normalized Jaccard index. Computational results show that community detection using the weighted line graphs generated with the normalized Jaccard index leads to a more accurate community structure.
arXiv comment20 pages, 8 figures
References in corpus (32)
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Uncovering the overlapping community structure of complex networks in nature and society
- Maps of random walks on complex networks reveal community structure
- Functional cartography of complex metabolic networks
- Resolution limit in community detection
- Link communities reveal multiscale complexity in networks
- Detecting the overlapping and hierarchical community structure of complex networks
- Finding statistically significant communities in networks
- Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
- The performance of modularity maximization in practical contexts
- Overlapping Community Detection in Networks: the State of the Art and Comparative Study
- Line Graphs, Link Partitions and Overlapping Communities
- Analysis of the structure of complex networks at different resolution levels
- Parsimonious module inference in large networks
- Multiresolution community detection for megascale networks by information-based replica correlations
- Line Graphs of Weighted Networks for Overlapping Communities
- Unbiased Global Optimization of Lennard-Jones Clusters for N <= 201 by Conformational Space Annealing Method
- Deciphering Network Community Structure by Surprise
- Detecting communities using asymptotical Surprise
- Surprise maximization reveals the community structure of complex networks
- Overlapping Community Detection in Complex Networks using Symmetric Binary Matrix Factorization
- Map equation for link community
- Evaluating accuracy of community detection using the relative normalized mutual information
- Estimating the resolution limit of the map equation in community detection
- Communities and bottlenecks: Trees and treelike networks have high modularity
- Post-Processing Hierarchical Community Structures: Quality Improvements and Multi-scale View
- Extraction of hidden information by efficient community detection in networks
- Global organization of protein complexome in the yeast Saccharomyces cerevisiae
- A shadowing problem in the detection of overlapping communities: lifting the resolution limit through a cascading procedure
- MOCSA: multiobjective optimization by conformational space annealing