TY - GEN
T1 - FACH
T2 - 11th ACM International Conference on Web Search and Data Mining, WSDM 2018
AU - Rezvani, Mojtaba
AU - Wang, Qing
AU - Liang, Weifa
N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].
PY - 2018/2/2
Y1 - 2018/2/2
N2 - 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 edgecuts 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.
AB - 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 edgecuts 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.
KW - Hierarchical community detection
KW - Large-scale networks
UR - https://www.scopus.com/pages/publications/85046891859
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85046891859&origin=recordpage
U2 - 10.1145/3159652.3159704
DO - 10.1145/3159652.3159704
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9781450355810
VL - 2018-Febuary
T3 - WSDM 2018 - Proceedings of the 11th ACM International Conference on Web Search and Data Mining
SP - 486
EP - 494
BT - WSDM 2018 - Proceedings of the 11th ACM International Conference on Web Search and Data Mining
PB - Association for Computing Machinery
Y2 - 5 February 2018 through 9 February 2018
ER -