Paper Info
Title
A Markov random walk under constraint for discovering overlapping communities in complex networks
Abstract
The detection of overlapping communities in complex networks has motivated recent research in relevant fields. Aiming to address this problem, we propose a Markov-dynamics-based algorithm, called UEOC, which means 'unfold and extract overlapping communities'. In UEOC, when identifying each natural community that overlaps, a Markov random walk method combined with a constraint strategy, which is based on the corresponding annealed network (degree conserving random network), is performed to unfold the community. Then, a cutoff criterion with the aid of a local community function, called conductance, which can be thought of as the ratio between the number of edges inside the community and those leaving it, is presented to extract this emerged community from the entire network. The UEOC algorithm depends on only one parameter whose value can be easily set, and it requires no prior knowledge of the hidden community structures. The proposed UEOC has been evaluated both on synthetic benchmarks and on some real-world networks, and has been compared with a set of competing algorithms. The experimental result has shown that UEOC is highly effective and efficient for discovering overlapping communities.
Year
DOI
Venue
2013
10.1088/1742-5468/2011/05/P05031
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT
Keywords
Field
DocType
analysis of algorithms,network dynamics,random graphs,networks,clustering techniques
Local community,Data mining,Community structure,Random graph,Network dynamics,Random walk,Markov chain,Analysis of algorithms,Complex network,Mathematics
Journal
Volume
Issue
ISSN
2011
5
1742-5468
Citations 
PageRank 
References 
28
1.21
12
Authors
6
Name
Order
Citations
PageRank
Di Jin131749.25
Bo Yang282264.08
Carlos Baquero3674.65
Dayou Liu481468.17
Dongxiao He520128.10
Jie Liu619922.56