Ant Colony Optimization with Markov Random Walk for Community Detection in Graphs

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2011

Autores

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

Ata de Conferência Internacional

Título: ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING, PT II: 15TH PACIFIC-ASIA CONFERENCE, PAKDD 2011

Páginas: 123-134

15th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD)

Shenzhen, PEOPLES R CHINA, MAY 24-27, 2011

Indexação

ISI Web of Knowledge - 8 Citações

Scopus - 12 Citações

Outras Informações

ID Authenticus: P-007-YKM

DOI: 10.1007/978-3-642-20847-8-11

Abstract (EN): Network clustering problem (NCP) is the problem associated to the detection of network community structures. Building on Markov random walks we address this problem with a new ant colony optimization strategy, named as ACOMRW, which improves prior results on the NCP problem and does not require knowledge of the number of communities present on a given network. The framework of ant colony optimization is taken as the basic framework in the ACOMRW algorithm. At each iteration, a Markov random walk model is taken as heuristic rule; all of the ants' local solutions are aggregated to a global one through clustering ensemble, which then will be used to update a pheromone matrix. The strategy relies on the progressive strengthening of within-community links and the weakening of between-community links. Gradually this converges to a solution where the underlying community structure of the complex network will become clearly visible. The performance of algorithm ACOMRW was tested on a set of benchmark computer-generated networks, and as well on real-world network data sets. Experimental results confirm the validity and improvements met by this approach.

Idioma: Inglês

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

Nº de páginas: 12