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

• Type: Article in International Conference Proceedings Book
• Date: 2011

Authors

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

Conference proceedings International

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

Pages: 123-134

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

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

Indexing

ISI Web of Knowledge - 8 Citations

Scopus - 12 Citations

Other information

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

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 12