Tehnički vjesnik, Vol. 22 No. 2, 2015.
Izvorni znanstveni članak
https://doi.org/10.17559/TV-20150317103835
An efficient multi-objective community detection algorithm in complex networks
Kun Deng
; College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China
Jian-Pei Zhang
; College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China
Jing Yang
; College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China
Sažetak
Community detection in complex networks is often regarded as the problem of single-objective optimization and it is hard for single-objective optimization to identify potential community structure of meaningfulness. Thus, algorithm of multi-objective optimization is applied to the field of community detection. However, multi-objective community detection algorithm is prone to local optimization and weak diversity of the set of Paretooptimal solutions. In view of this, based on the framework of NSGAII, a multi-objective community detection algorithm, named I-NSGAII, is proposed in this paper. This algorithm is able to optimize simultaneously the two conflicting objective functions evaluating the density of intra-community connections and the sparsity of inter-community connections, and obtain the set of Pareto optimal solutions having diverse hierarchal community structures; it also proposes diversity evolutionary strategy enabling the algorithm to expand searching space and thus avoids local optimization of the set of Pareto-optimal solutions. In addition, to improve algorithm’s searching ability, I-NSGAII algorithm adopts the strategies of locus-based adjacency representation, unified label, one-way crossover and local mutation. Tests on synthetic and real-world networks and comparisons with many state-of-theart algorithms verify the validity and feasibility of I-NSGAII.
Ključne riječi
complex networks; diversity evolutionary strategy; multi-objective community detection; NSGAII
Hrčak ID:
138083
URI
Datum izdavanja:
22.4.2015.
Posjeta: 2.672 *