FACH: Fast algorithm for detecting cohesive hierarchies of communities in large networks
Date
2018-02-02
Authors
Rezvani, Motjaba
Wang, Qing
Liang, Weifa
Journal Title
Journal ISSN
Volume Title
Publisher
ACM
Abstract
Vertices in a real-world social network can be grouped into densely connected communities that are sparsely connected to other groups. Moreover, these communities can be partitioned into successively more cohesive communities. Despite an ever-growing pile of research on hierarchical community detection, existing methods suffer from either inefficiency or inappropriate modeling. Yet, some cut-based approaches have shown to be effective in finding communities without hierarchies. In this paper, we study the hierarchical community detection problem in large networks and show that it is NP-hard. We then propose an efficient algorithm based on edge-cuts to identify the hierarchy of communities. Since communities at lower levels of the hierarchy are denser than the higher levels, we leverage a fast network sparsification technique to enhance the running time of the algorithm. We further propose a randomized approximation algorithm for information centrality of networks. We finally evaluate the performance of the proposed algorithms by conducting extensive experiments using real datasets. Our experimental results show that the proposed algorithms are promising and outperform the state-of-the-art algorithms by several orders of magnitude.
Description
Keywords
Hierarchical community detection, large-scale networks
Citation
Collections
Source
WSDM '18: Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining
Type
Conference paper
Book Title
Entity type
Access Statement
Open Access
License Rights
Restricted until
Downloads
File
Description