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

• Type: Article in International Scientific Journal
• Date: 2011

Authors

Jin, D (Author) Other; Yang, B (Author) Other; Baquero, C (Author) Other; Liu, DY (Author) Other; He, DX (Author) Other; Liu, J (Author) Other

Journal

Title: Journal of Statistical Mechanics: Theory and Experiment

Vol. 2011

ISSN: 1742-5468

Publisher: Institute of Physics Publishing

Indexing

ISI Web of Knowledge - 57 Citations

Scopus - 77 Citations

Other information

Authenticus ID: P-002-S4J

DOI: 10.1088/1742-5468/2011/05/p05031

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 22