Cargando…
A seed-expanding method based on random walks for community detection in networks with ambiguous community structures
Community detection has received a great deal of attention, since it could help to reveal the useful information hidden in complex networks. Although most previous modularity-based and local modularity-based community detection algorithms could detect strong communities, they may fail to exactly det...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Nature Publishing Group
2017
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5291113/ https://www.ncbi.nlm.nih.gov/pubmed/28157183 http://dx.doi.org/10.1038/srep41830 |
_version_ | 1782504731465220096 |
---|---|
author | Su, Yansen Wang, Bangju Zhang, Xingyi |
author_facet | Su, Yansen Wang, Bangju Zhang, Xingyi |
author_sort | Su, Yansen |
collection | PubMed |
description | Community detection has received a great deal of attention, since it could help to reveal the useful information hidden in complex networks. Although most previous modularity-based and local modularity-based community detection algorithms could detect strong communities, they may fail to exactly detect several weak communities. In this work, we define a network with clear or ambiguous community structures based on the types of its communities. A seed-expanding method based on random walks is proposed to detect communities for networks, especially for the networks with ambiguous community structures. We identify local maximum degree nodes, and detect seed communities in a network. Then, the probability of a node belonging to each community is calculated based on the total probability model and random walks, and each community is expanded by repeatedly adding the node which is most likely to belong to it. Finally, we use the community optimization method to ensure that each node is in a community. Experimental results on both computer-generated and real-world networks demonstrate that the quality of the communities detected by the proposed algorithm is superior to the- state-of-the-art algorithms in the networks with ambiguous community structures. |
format | Online Article Text |
id | pubmed-5291113 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2017 |
publisher | Nature Publishing Group |
record_format | MEDLINE/PubMed |
spelling | pubmed-52911132017-02-07 A seed-expanding method based on random walks for community detection in networks with ambiguous community structures Su, Yansen Wang, Bangju Zhang, Xingyi Sci Rep Article Community detection has received a great deal of attention, since it could help to reveal the useful information hidden in complex networks. Although most previous modularity-based and local modularity-based community detection algorithms could detect strong communities, they may fail to exactly detect several weak communities. In this work, we define a network with clear or ambiguous community structures based on the types of its communities. A seed-expanding method based on random walks is proposed to detect communities for networks, especially for the networks with ambiguous community structures. We identify local maximum degree nodes, and detect seed communities in a network. Then, the probability of a node belonging to each community is calculated based on the total probability model and random walks, and each community is expanded by repeatedly adding the node which is most likely to belong to it. Finally, we use the community optimization method to ensure that each node is in a community. Experimental results on both computer-generated and real-world networks demonstrate that the quality of the communities detected by the proposed algorithm is superior to the- state-of-the-art algorithms in the networks with ambiguous community structures. Nature Publishing Group 2017-02-03 /pmc/articles/PMC5291113/ /pubmed/28157183 http://dx.doi.org/10.1038/srep41830 Text en Copyright © 2017, The Author(s) http://creativecommons.org/licenses/by/4.0/ This work is licensed under a Creative Commons Attribution 4.0 International License. The images or other third party material in this article are included in the article’s Creative Commons license, unless indicated otherwise in the credit line; if the material is not included under the Creative Commons license, users will need to obtain permission from the license holder to reproduce the material. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/ |
spellingShingle | Article Su, Yansen Wang, Bangju Zhang, Xingyi A seed-expanding method based on random walks for community detection in networks with ambiguous community structures |
title | A seed-expanding method based on random walks for community detection in networks with ambiguous community structures |
title_full | A seed-expanding method based on random walks for community detection in networks with ambiguous community structures |
title_fullStr | A seed-expanding method based on random walks for community detection in networks with ambiguous community structures |
title_full_unstemmed | A seed-expanding method based on random walks for community detection in networks with ambiguous community structures |
title_short | A seed-expanding method based on random walks for community detection in networks with ambiguous community structures |
title_sort | seed-expanding method based on random walks for community detection in networks with ambiguous community structures |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5291113/ https://www.ncbi.nlm.nih.gov/pubmed/28157183 http://dx.doi.org/10.1038/srep41830 |
work_keys_str_mv | AT suyansen aseedexpandingmethodbasedonrandomwalksforcommunitydetectioninnetworkswithambiguouscommunitystructures AT wangbangju aseedexpandingmethodbasedonrandomwalksforcommunitydetectioninnetworkswithambiguouscommunitystructures AT zhangxingyi aseedexpandingmethodbasedonrandomwalksforcommunitydetectioninnetworkswithambiguouscommunitystructures AT suyansen seedexpandingmethodbasedonrandomwalksforcommunitydetectioninnetworkswithambiguouscommunitystructures AT wangbangju seedexpandingmethodbasedonrandomwalksforcommunitydetectioninnetworkswithambiguouscommunitystructures AT zhangxingyi seedexpandingmethodbasedonrandomwalksforcommunitydetectioninnetworkswithambiguouscommunitystructures |