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

• Tipo: Artigo em Revista Científica Internacional
• Data: 2011

Autores

Jin, D (Autor) Outra; Yang, B (Autor) Outra; Baquero, C (Autor) Outra; Liu, DY (Autor) Outra; He, DX (Autor) Outra; Liu, J (Autor) Outra

Revista

Título: Journal of Statistical Mechanics: Theory and Experiment

Vol. 2011

ISSN: 1742-5468

Editora: Institute of Physics Publishing

Indexação

ISI Web of Knowledge - 57 Citações

Scopus - 77 Citações

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 22