Robustness of community structure to node removal
arXiv:1308.6295 · doi:10.1088/1742-5468/2015/03/P03003
Abstract
The identification of modular structures is essential for characterizing real networks formed by a mesoscopic level of organization where clusters contain nodes with a high internal degree of connectivity. Many methods have been developed to unveil community structures, but only a few studies have probed their suitability in incomplete networks. Here we assess the accuracy of community detection techniques in incomplete networks generated in sampling processes. We show that the walktrap and fast greedy algorithms are highly accurate for detecting the modular structure of incomplete complex networks even if many of their nodes are removed. Furthermore, we implemented an approach that improved the time performance of the walktrap and fast greedy algorithms, while retaining the accuracy rate in identifying the community membership of nodes. Taken together our results show that this new approach can be applied to speed up virtually any community detection method in dense complex networks, as it is the case of similarity networks.
References in corpus (21)
- Community structure in social and biological networks
- Community detection in graphs
- Fast algorithm for detecting community structure in networks
- Finding community structure in networks using the eigenvectors of matrices
- Cooperative Game Theory Approaches for Network Partitioning
- The diameter of the world wide web
- Benchmark graphs for testing community detection algorithms
- Comparing community structure identification
- Analysis of weighted networks
- Detecting the overlapping and hierarchical community structure of complex networks
- The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
- Self-similar community structure in organisations
- How Popular is Your Paper? An Empirical Study of the Citation Distribution
- Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
- Community Structure in Jazz
- The Network Analysis of Urban Streets: A Primal Approach
- Subnetwork hierarchies of biochemical pathways
- Robustness of community structure in networks
- Finding instabilities in the community structure of complex networks
- Finding missing edges in networks based on their community structure
- On time-varying collaboration networks