  Detection of overlapping communities in complex networks has motivated recent
research in the relevant fields. Aiming 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 on the hidden community
structures. The proposed UEOC has been evaluated both on synthetic benchmarks
and on some real-world networks, and was compared with a set of competing
algorithms. Experimental result has shown that UEOC is highly effective and
efficient for discovering overlapping communities.
