A novel metric for community detection
arXiv:1909.12467 · doi:10.1209/0295-5075/129/68002
Abstract
Research into detection of dense communities has recently attracted increasing attention within network science, various metrics for detection of such communities have been proposed. The most popular metric -- Modularity -- is based on the so-called rule that the links within communities are denser than external links among communities, has become the default. However, this default metric suffers from ambiguity, and worse, all augmentations of modularity and based on a narrow intuition of what it means to form a "community". We argue that in specific, but quite common systems, links within a community are not necessarily more common than links between communities. Instead we propose that the defining characteristic of a community is that links are more predictable within a community rather than between communities. In this paper, based on the effect of communities on link prediction, we propose a novel metric for the community detection based directly on this feature. We find that our metric is more robustness than traditional modularity. Consequently, we can achieve an evaluation of algorithm stability for the same detection algorithm in different networks. Our metric also can directly uncover the false community detection, and infer more statistical characteristics for detection algorithms.
arXiv comment7 pages, 4 figures
References in corpus (18)
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Finding community structure in very large networks
- Uncovering the overlapping community structure of complex networks in nature and society
- Finding community structure in networks using the eigenvectors of matrices
- Cooperative Game Theory Approaches for Network Partitioning
- Maps of random walks on complex networks reveal community structure
- Hierarchical organization of modularity in metabolic networks
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Link Prediction in Complex Networks: A Survey
- Defining and identifying communities in networks
- Clustering and preferential attachment in growing networks
- Community detection in networks: A user guide
- Vertex similarity in networks
- Finding missing edges in networks based on their community structure
- GenPerm: A Unified Method for Detecting Non-overlapping and Overlapping Communities