Overlapping Community Detection based on Network Decomposition

Community detection in complex network has become a vital step to understand the structure and dynamics of networks in various fields. However, traditional node clustering and relatively new proposed link clustering methods have inherent drawbacks to discover overlapping communities. Node clustering...

Full description

Bibliographic Details
Main Authors:	Ding, Zhuanlian, Zhang, Xingyi, Sun, Dengdi, Luo, Bin
Format:	Online
Language:	English
Published:	Nature Publishing Group 2016
Online Access:	https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4828636/

id	pubmed-4828636
recordtype	oai_dc
spelling	pubmed-48286362016-04-19 Overlapping Community Detection based on Network Decomposition Ding, Zhuanlian Zhang, Xingyi Sun, Dengdi Luo, Bin Article Community detection in complex network has become a vital step to understand the structure and dynamics of networks in various fields. However, traditional node clustering and relatively new proposed link clustering methods have inherent drawbacks to discover overlapping communities. Node clustering is inadequate to capture the pervasive overlaps, while link clustering is often criticized due to the high computational cost and ambiguous definition of communities. So, overlapping community detection is still a formidable challenge. In this work, we propose a new overlapping community detection algorithm based on network decomposition, called NDOCD. Specifically, NDOCD iteratively splits the network by removing all links in derived link communities, which are identified by utilizing node clustering technique. The network decomposition contributes to reducing the computation time and noise link elimination conduces to improving the quality of obtained communities. Besides, we employ node clustering technique rather than link similarity measure to discover link communities, thus NDOCD avoids an ambiguous definition of community and becomes less time-consuming. We test our approach on both synthetic and real-world networks. Results demonstrate the superior performance of our approach both in computation time and accuracy compared to state-of-the-art algorithms. Nature Publishing Group 2016-04-12 /pmc/articles/PMC4828636/ /pubmed/27066904 http://dx.doi.org/10.1038/srep24115 Text en Copyright © 2016, Macmillan Publishers Limited 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/
repository_type	Open Access Journal
institution_category	Foreign Institution
institution	US National Center for Biotechnology Information
building	NCBI PubMed
collection	Online Access
language	English
format	Online
author	Ding, Zhuanlian Zhang, Xingyi Sun, Dengdi Luo, Bin
spellingShingle	Ding, Zhuanlian Zhang, Xingyi Sun, Dengdi Luo, Bin Overlapping Community Detection based on Network Decomposition
author_facet	Ding, Zhuanlian Zhang, Xingyi Sun, Dengdi Luo, Bin
author_sort	Ding, Zhuanlian
title	Overlapping Community Detection based on Network Decomposition
title_short	Overlapping Community Detection based on Network Decomposition
title_full	Overlapping Community Detection based on Network Decomposition
title_fullStr	Overlapping Community Detection based on Network Decomposition
title_full_unstemmed	Overlapping Community Detection based on Network Decomposition
title_sort	overlapping community detection based on network decomposition
description	Community detection in complex network has become a vital step to understand the structure and dynamics of networks in various fields. However, traditional node clustering and relatively new proposed link clustering methods have inherent drawbacks to discover overlapping communities. Node clustering is inadequate to capture the pervasive overlaps, while link clustering is often criticized due to the high computational cost and ambiguous definition of communities. So, overlapping community detection is still a formidable challenge. In this work, we propose a new overlapping community detection algorithm based on network decomposition, called NDOCD. Specifically, NDOCD iteratively splits the network by removing all links in derived link communities, which are identified by utilizing node clustering technique. The network decomposition contributes to reducing the computation time and noise link elimination conduces to improving the quality of obtained communities. Besides, we employ node clustering technique rather than link similarity measure to discover link communities, thus NDOCD avoids an ambiguous definition of community and becomes less time-consuming. We test our approach on both synthetic and real-world networks. Results demonstrate the superior performance of our approach both in computation time and accuracy compared to state-of-the-art algorithms.
publisher	Nature Publishing Group
publishDate	2016
url	https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4828636/
_version_	1613565067945574400

Overlapping Community Detection based on Network Decomposition

Similar Items