An improved random walk based clustering algorithm for community detection in complex networks

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    10 Citations (Scopus)

    Abstract

    In recent years, there is an increasing interest in the research community in finding community structure in complex networks. The networks are usually represented as graphs, and the task is usually cast as a graph clustering problem. Traditional clustering algorithms and graph partitioning algorithms have been applied to this problem. New graph clustering algorithms have also been proposed. Random walk based clustering, in which the similarities between pairs of nodes in a graph are usually estimated using random walk with restart (RWR) algorithm, is one of the most popular graph clustering methods. Most of these clustering algorithms only find disjoint partitions in networks; however, communities in many real-world networks often overlap to some degree. In this paper, we propose an efficient clustering method based on random walks for discovering communities in graphs. The proposed method makes use of network topology and edge weights, and is able to discover overlapping communities. We analyze the effect of parameters in the proposed method on clustering results. We evaluate the proposed method on real world social networks that are well documented in the literature, using both topological-based and knowledge-based evaluation methods. We compare the proposed method to other clustering methods including recently published Repeated Random Walks, and find that the proposed method achieves better precision and accuracy values in terms of six statistical measurements including both data-driven and knowledge-driven evaluation metrics.

    LanguageEnglish
    Title of host publication2011 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2011 - Conference Digest
    Pages2162-2167
    Number of pages6
    DOIs
    Publication statusPublished - 23 Dec 2011
    Event2011 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2011 - Anchorage, AK, United States
    Duration: 9 Oct 201112 Oct 2011

    Conference

    Conference2011 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2011
    CountryUnited States
    CityAnchorage, AK
    Period9/10/1112/10/11

    Fingerprint

    Complex networks
    Clustering algorithms
    Topology

    Keywords

    • graph clustering
    • random walks
    • social networks

    Cite this

    Cai, B., Wang, H., Zheng, H., & Wang, H. (2011). An improved random walk based clustering algorithm for community detection in complex networks. In 2011 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2011 - Conference Digest (pp. 2162-2167). [6083997] https://doi.org/10.1109/ICSMC.2011.6083997
    Cai, Bingjing ; Wang, Haiying ; Zheng, Huiru ; Wang, Hui. / An improved random walk based clustering algorithm for community detection in complex networks. 2011 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2011 - Conference Digest. 2011. pp. 2162-2167
    @inproceedings{d275d8bd8e444fb79b820ae714fb0c96,
    title = "An improved random walk based clustering algorithm for community detection in complex networks",
    abstract = "In recent years, there is an increasing interest in the research community in finding community structure in complex networks. The networks are usually represented as graphs, and the task is usually cast as a graph clustering problem. Traditional clustering algorithms and graph partitioning algorithms have been applied to this problem. New graph clustering algorithms have also been proposed. Random walk based clustering, in which the similarities between pairs of nodes in a graph are usually estimated using random walk with restart (RWR) algorithm, is one of the most popular graph clustering methods. Most of these clustering algorithms only find disjoint partitions in networks; however, communities in many real-world networks often overlap to some degree. In this paper, we propose an efficient clustering method based on random walks for discovering communities in graphs. The proposed method makes use of network topology and edge weights, and is able to discover overlapping communities. We analyze the effect of parameters in the proposed method on clustering results. We evaluate the proposed method on real world social networks that are well documented in the literature, using both topological-based and knowledge-based evaluation methods. We compare the proposed method to other clustering methods including recently published Repeated Random Walks, and find that the proposed method achieves better precision and accuracy values in terms of six statistical measurements including both data-driven and knowledge-driven evaluation metrics.",
    keywords = "graph clustering, random walks, social networks",
    author = "Bingjing Cai and Haiying Wang and Huiru Zheng and Hui Wang",
    year = "2011",
    month = "12",
    day = "23",
    doi = "10.1109/ICSMC.2011.6083997",
    language = "English",
    isbn = "9781457706523",
    pages = "2162--2167",
    booktitle = "2011 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2011 - Conference Digest",

    }

    Cai, B, Wang, H, Zheng, H & Wang, H 2011, An improved random walk based clustering algorithm for community detection in complex networks. in 2011 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2011 - Conference Digest., 6083997, pp. 2162-2167, 2011 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2011, Anchorage, AK, United States, 9/10/11. https://doi.org/10.1109/ICSMC.2011.6083997

    An improved random walk based clustering algorithm for community detection in complex networks. / Cai, Bingjing; Wang, Haiying; Zheng, Huiru; Wang, Hui.

    2011 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2011 - Conference Digest. 2011. p. 2162-2167 6083997.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    TY - GEN

    T1 - An improved random walk based clustering algorithm for community detection in complex networks

    AU - Cai, Bingjing

    AU - Wang, Haiying

    AU - Zheng, Huiru

    AU - Wang, Hui

    PY - 2011/12/23

    Y1 - 2011/12/23

    N2 - In recent years, there is an increasing interest in the research community in finding community structure in complex networks. The networks are usually represented as graphs, and the task is usually cast as a graph clustering problem. Traditional clustering algorithms and graph partitioning algorithms have been applied to this problem. New graph clustering algorithms have also been proposed. Random walk based clustering, in which the similarities between pairs of nodes in a graph are usually estimated using random walk with restart (RWR) algorithm, is one of the most popular graph clustering methods. Most of these clustering algorithms only find disjoint partitions in networks; however, communities in many real-world networks often overlap to some degree. In this paper, we propose an efficient clustering method based on random walks for discovering communities in graphs. The proposed method makes use of network topology and edge weights, and is able to discover overlapping communities. We analyze the effect of parameters in the proposed method on clustering results. We evaluate the proposed method on real world social networks that are well documented in the literature, using both topological-based and knowledge-based evaluation methods. We compare the proposed method to other clustering methods including recently published Repeated Random Walks, and find that the proposed method achieves better precision and accuracy values in terms of six statistical measurements including both data-driven and knowledge-driven evaluation metrics.

    AB - In recent years, there is an increasing interest in the research community in finding community structure in complex networks. The networks are usually represented as graphs, and the task is usually cast as a graph clustering problem. Traditional clustering algorithms and graph partitioning algorithms have been applied to this problem. New graph clustering algorithms have also been proposed. Random walk based clustering, in which the similarities between pairs of nodes in a graph are usually estimated using random walk with restart (RWR) algorithm, is one of the most popular graph clustering methods. Most of these clustering algorithms only find disjoint partitions in networks; however, communities in many real-world networks often overlap to some degree. In this paper, we propose an efficient clustering method based on random walks for discovering communities in graphs. The proposed method makes use of network topology and edge weights, and is able to discover overlapping communities. We analyze the effect of parameters in the proposed method on clustering results. We evaluate the proposed method on real world social networks that are well documented in the literature, using both topological-based and knowledge-based evaluation methods. We compare the proposed method to other clustering methods including recently published Repeated Random Walks, and find that the proposed method achieves better precision and accuracy values in terms of six statistical measurements including both data-driven and knowledge-driven evaluation metrics.

    KW - graph clustering

    KW - random walks

    KW - social networks

    UR - http://www.scopus.com/inward/record.url?scp=83755221110&partnerID=8YFLogxK

    U2 - 10.1109/ICSMC.2011.6083997

    DO - 10.1109/ICSMC.2011.6083997

    M3 - Conference contribution

    SN - 9781457706523

    SP - 2162

    EP - 2167

    BT - 2011 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2011 - Conference Digest

    ER -

    Cai B, Wang H, Zheng H, Wang H. An improved random walk based clustering algorithm for community detection in complex networks. In 2011 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2011 - Conference Digest. 2011. p. 2162-2167. 6083997 https://doi.org/10.1109/ICSMC.2011.6083997