FACH: Fast algorithm for detecting cohesive hierarchies of communities in large networks

Mojtaba Rezvani, Qing Wang, Weifa Liang

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    1 Citation (Scopus)

    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 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.

    Original languageEnglish
    Title of host publicationWSDM 2018 - Proceedings of the 11th ACM International Conference on Web Search and Data Mining
    PublisherAssociation for Computing Machinery, Inc
    Pages486-494
    Number of pages9
    ISBN (Electronic)9781450355810
    DOIs
    Publication statusPublished - 2 Feb 2018
    Event11th ACM International Conference on Web Search and Data Mining, WSDM 2018 - Marina Del Rey, United States
    Duration: 5 Feb 20189 Feb 2018

    Publication series

    NameWSDM 2018 - Proceedings of the 11th ACM International Conference on Web Search and Data Mining
    Volume2018-Febuary

    Conference

    Conference11th ACM International Conference on Web Search and Data Mining, WSDM 2018
    Country/TerritoryUnited States
    CityMarina Del Rey
    Period5/02/189/02/18

    Fingerprint

    Dive into the research topics of 'FACH: Fast algorithm for detecting cohesive hierarchies of communities in large networks'. Together they form a unique fingerprint.

    Cite this