Markov random walk under constraint for discovering overlapping communities in complex networks

摘要: Detection of overlapping communities in complex networks has motivated recent research the relevant fields. Aiming this problem, we propose a Markov dynamics based algorithm, called UEOC, which means, 'unfold and extract communities'. In when identifying each natural community that overlaps, random walk method combined with constraint strategy, is on corresponding annealed network (degree conserving network), performed to unfold community. Then, cutoff criterion aid local function, conductance, can be thought as ratio between number edges inside those leaving it, presented emerged from entire network. The UEOC algorithm depends only one parameter whose value easily set, it requires no prior knowledge hidden structures. proposed been evaluated both synthetic benchmarks some real-world networks, was compared set competing algorithms. Experimental result shown highly effective efficient for discovering communities.