An Empirical Comparison of Algorithms to Find Communities in Directed Graphs and Their Application in Web Data Analytics

Santa Agreste, Pasquale De Meo, Giacomo Fiumara, Giuseppe Piccione, Sebastiano Piccolo, Domenico Rosaci, Giuseppe M. L. Sarne, Athanasios V. Vasilakos

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    Detecting communities in graphs is a fundamental tool to understand the structure of Web-based systems and predict their evolution. Many community detection algorithms are designed to process undirected graphs (i.e., graphs with bidirectional edges) but many graphs on the Web-e.g., microblogging Web sites, trust networks or the Web graph itself-are often directed. Few community detection algorithms deal with directed graphs but we lack their experimental comparison. In this paper we evaluated some community detection algorithms across accuracy and scalability. A first group of algorithms (Label Propagation and Infomap) are explicitly designed to manage directed graphs while a second group (e.g., WalkTrap) simply ignores edge directionality; finally, a third group of algorithms (e.g., Eigenvector) maps input graphs onto undirected ones and extracts communities from the symmetrized version of the input graph. We ran our tests on both artificial and real graphs and, on artificial graphs, WalkTrap achieved the highest accuracy, closely followed by other algorithms; Label Propagation has outstanding performance in scalability on both artificial and real graphs. The Infomap algorithm showcased the best trade-off between accuracy and computational performance and, therefore, it has to be considered as a promising tool for Web Data Analytics purposes.
    Original languageEnglish
    JournalIEEE Transactions on Big Data
    Volume3
    Issue number3
    Pages (from-to)289-306
    ISSN2332-7790
    DOIs
    Publication statusPublished - 2017

    Keywords

    • Web data analytics
    • Graph analytics
    • Community detection and clustering
    • Directed graphs

    Cite this

    Agreste, S., De Meo, P., Fiumara, G., Piccione, G., Piccolo, S., Rosaci, D., Sarne, G. M. L., & Vasilakos, A. V. (2017). An Empirical Comparison of Algorithms to Find Communities in Directed Graphs and Their Application in Web Data Analytics. IEEE Transactions on Big Data, 3(3), 289-306. https://doi.org/10.1109/TBDATA.2016.2631512