Improving the Efficiency and Effectiveness of Community Detection via Prior-Induced Equivalent Super-Network

Abstract Due to the importance of community structure in understanding network and a surge of interest aroused on community detectability, how to improve the community identification performance with pairwise prior information becomes a hot topic. However, most existing semi-supervised community det...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Liang Yang, Di Jin, Dongxiao He, Huazhu Fu, Xiaochun Cao, Francoise Fogelman-Soulie
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2017
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/d0887754dec84f03afb70561bb636d91
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:d0887754dec84f03afb70561bb636d91
record_format	dspace
spelling	oai:doaj.org-article:d0887754dec84f03afb70561bb636d912021-12-02T11:53:10ZImproving the Efficiency and Effectiveness of Community Detection via Prior-Induced Equivalent Super-Network10.1038/s41598-017-00587-w2045-2322https://doaj.org/article/d0887754dec84f03afb70561bb636d912017-03-01T00:00:00Zhttps://doi.org/10.1038/s41598-017-00587-whttps://doaj.org/toc/2045-2322Abstract Due to the importance of community structure in understanding network and a surge of interest aroused on community detectability, how to improve the community identification performance with pairwise prior information becomes a hot topic. However, most existing semi-supervised community detection algorithms only focus on improving the accuracy but ignore the impacts of priors on speeding detection. Besides, they always require to tune additional parameters and cannot guarantee pairwise constraints. To address these drawbacks, we propose a general, high-speed, effective and parameter-free semi-supervised community detection framework. By constructing the indivisible super-nodes according to the connected subgraph of the must-link constraints and by forming the weighted super-edge based on network topology and cannot-link constraints, our new framework transforms the original network into an equivalent but much smaller Super-Network. Super-Network perfectly ensures the must-link constraints and effectively encodes cannot-link constraints. Furthermore, the time complexity of super-network construction process is linear in the original network size, which makes it efficient. Meanwhile, since the constructed super-network is much smaller than the original one, any existing community detection algorithm is much faster when using our framework. Besides, the overall process will not introduce any additional parameters, making it more practical.Liang YangDi JinDongxiao HeHuazhu FuXiaochun CaoFrancoise Fogelman-SoulieNature PortfolioarticleMedicineRScienceQENScientific Reports, Vol 7, Iss 1, Pp 1-15 (2017)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Liang Yang Di Jin Dongxiao He Huazhu Fu Xiaochun Cao Francoise Fogelman-Soulie Improving the Efficiency and Effectiveness of Community Detection via Prior-Induced Equivalent Super-Network
description	Abstract Due to the importance of community structure in understanding network and a surge of interest aroused on community detectability, how to improve the community identification performance with pairwise prior information becomes a hot topic. However, most existing semi-supervised community detection algorithms only focus on improving the accuracy but ignore the impacts of priors on speeding detection. Besides, they always require to tune additional parameters and cannot guarantee pairwise constraints. To address these drawbacks, we propose a general, high-speed, effective and parameter-free semi-supervised community detection framework. By constructing the indivisible super-nodes according to the connected subgraph of the must-link constraints and by forming the weighted super-edge based on network topology and cannot-link constraints, our new framework transforms the original network into an equivalent but much smaller Super-Network. Super-Network perfectly ensures the must-link constraints and effectively encodes cannot-link constraints. Furthermore, the time complexity of super-network construction process is linear in the original network size, which makes it efficient. Meanwhile, since the constructed super-network is much smaller than the original one, any existing community detection algorithm is much faster when using our framework. Besides, the overall process will not introduce any additional parameters, making it more practical.
format	article
author	Liang Yang Di Jin Dongxiao He Huazhu Fu Xiaochun Cao Francoise Fogelman-Soulie
author_facet	Liang Yang Di Jin Dongxiao He Huazhu Fu Xiaochun Cao Francoise Fogelman-Soulie
author_sort	Liang Yang
title	Improving the Efficiency and Effectiveness of Community Detection via Prior-Induced Equivalent Super-Network
title_short	Improving the Efficiency and Effectiveness of Community Detection via Prior-Induced Equivalent Super-Network
title_full	Improving the Efficiency and Effectiveness of Community Detection via Prior-Induced Equivalent Super-Network
title_fullStr	Improving the Efficiency and Effectiveness of Community Detection via Prior-Induced Equivalent Super-Network
title_full_unstemmed	Improving the Efficiency and Effectiveness of Community Detection via Prior-Induced Equivalent Super-Network
title_sort	improving the efficiency and effectiveness of community detection via prior-induced equivalent super-network
publisher	Nature Portfolio
publishDate	2017
url	https://doaj.org/article/d0887754dec84f03afb70561bb636d91
work_keys_str_mv	AT liangyang improvingtheefficiencyandeffectivenessofcommunitydetectionviapriorinducedequivalentsupernetwork AT dijin improvingtheefficiencyandeffectivenessofcommunitydetectionviapriorinducedequivalentsupernetwork AT dongxiaohe improvingtheefficiencyandeffectivenessofcommunitydetectionviapriorinducedequivalentsupernetwork AT huazhufu improvingtheefficiencyandeffectivenessofcommunitydetectionviapriorinducedequivalentsupernetwork AT xiaochuncao improvingtheefficiencyandeffectivenessofcommunitydetectionviapriorinducedequivalentsupernetwork AT francoisefogelmansoulie improvingtheefficiencyandeffectivenessofcommunitydetectionviapriorinducedequivalentsupernetwork
_version_	1718394895768485888

Improving the Efficiency and Effectiveness of Community Detection via Prior-Induced Equivalent Super-Network

Ejemplares similares