Cargando…

Overlapping Community Detection Based on Membership Degree Propagation

A community in a complex network refers to a group of nodes that are densely connected internally but with only sparse connections to the outside. Overlapping community structures are ubiquitous in real-world networks, where each node belongs to at least one community. Therefore, overlapping communi...

Descripción completa

Detalles Bibliográficos
Autores principales: Gao, Rui, Li, Shoufeng, Shi, Xiaohu, Liang, Yanchun, Xu, Dong
Formato: Online Artículo Texto
Lenguaje:English
Publicado: MDPI 2020
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7824673/
https://www.ncbi.nlm.nih.gov/pubmed/33374305
http://dx.doi.org/10.3390/e23010015
_version_ 1783640135124910080
author Gao, Rui
Li, Shoufeng
Shi, Xiaohu
Liang, Yanchun
Xu, Dong
author_facet Gao, Rui
Li, Shoufeng
Shi, Xiaohu
Liang, Yanchun
Xu, Dong
author_sort Gao, Rui
collection PubMed
description A community in a complex network refers to a group of nodes that are densely connected internally but with only sparse connections to the outside. Overlapping community structures are ubiquitous in real-world networks, where each node belongs to at least one community. Therefore, overlapping community detection is an important topic in complex network research. This paper proposes an overlapping community detection algorithm based on membership degree propagation that is driven by both global and local information of the node community. In the method, we introduce a concept of membership degree, which not only stores the label information, but also the degrees of the node belonging to the labels. Then the conventional label propagation process could be extended to membership degree propagation, with the results mapped directly to the overlapping community division. Therefore, it obtains the partition result and overlapping node identification simultaneously and greatly reduces the computational time. The proposed algorithm was applied to a synthetic Lancichinetti–Fortunato–Radicchi (LFR) dataset and nine real-world datasets and compared with other up-to-date algorithms. The experimental results show that our proposed algorithm is effective and outperforms the comparison methods on most datasets. Our proposed method significantly improved the accuracy and speed of the overlapping node prediction. It can also substantially alleviate the computational complexity of community structure detection in general.
format Online
Article
Text
id pubmed-7824673
institution National Center for Biotechnology Information
language English
publishDate 2020
publisher MDPI
record_format MEDLINE/PubMed
spelling pubmed-78246732021-02-24 Overlapping Community Detection Based on Membership Degree Propagation Gao, Rui Li, Shoufeng Shi, Xiaohu Liang, Yanchun Xu, Dong Entropy (Basel) Article A community in a complex network refers to a group of nodes that are densely connected internally but with only sparse connections to the outside. Overlapping community structures are ubiquitous in real-world networks, where each node belongs to at least one community. Therefore, overlapping community detection is an important topic in complex network research. This paper proposes an overlapping community detection algorithm based on membership degree propagation that is driven by both global and local information of the node community. In the method, we introduce a concept of membership degree, which not only stores the label information, but also the degrees of the node belonging to the labels. Then the conventional label propagation process could be extended to membership degree propagation, with the results mapped directly to the overlapping community division. Therefore, it obtains the partition result and overlapping node identification simultaneously and greatly reduces the computational time. The proposed algorithm was applied to a synthetic Lancichinetti–Fortunato–Radicchi (LFR) dataset and nine real-world datasets and compared with other up-to-date algorithms. The experimental results show that our proposed algorithm is effective and outperforms the comparison methods on most datasets. Our proposed method significantly improved the accuracy and speed of the overlapping node prediction. It can also substantially alleviate the computational complexity of community structure detection in general. MDPI 2020-12-24 /pmc/articles/PMC7824673/ /pubmed/33374305 http://dx.doi.org/10.3390/e23010015 Text en © 2020 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).
spellingShingle Article
Gao, Rui
Li, Shoufeng
Shi, Xiaohu
Liang, Yanchun
Xu, Dong
Overlapping Community Detection Based on Membership Degree Propagation
title Overlapping Community Detection Based on Membership Degree Propagation
title_full Overlapping Community Detection Based on Membership Degree Propagation
title_fullStr Overlapping Community Detection Based on Membership Degree Propagation
title_full_unstemmed Overlapping Community Detection Based on Membership Degree Propagation
title_short Overlapping Community Detection Based on Membership Degree Propagation
title_sort overlapping community detection based on membership degree propagation
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7824673/
https://www.ncbi.nlm.nih.gov/pubmed/33374305
http://dx.doi.org/10.3390/e23010015
work_keys_str_mv AT gaorui overlappingcommunitydetectionbasedonmembershipdegreepropagation
AT lishoufeng overlappingcommunitydetectionbasedonmembershipdegreepropagation
AT shixiaohu overlappingcommunitydetectionbasedonmembershipdegreepropagation
AT liangyanchun overlappingcommunitydetectionbasedonmembershipdegreepropagation
AT xudong overlappingcommunitydetectionbasedonmembershipdegreepropagation