文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 互联网 > 2013A genetic algorithm for community detection in complex networks
侵权投诉

2013A genetic algorithm for community detection in complex networks

基因算法在社区发现中的应用,一篇很好的论文,值得学习

J. Cent. South Univ. (2013) 20: 1269 1276 DOI: 10.1007/s11771-013-1611-y

2013A genetic algorithm for community detection in complex networks

A genetic algorithm for community detection in complex networks

LI Yun(李赟), LIU Gang(刘钢), LAO Song-yang(老松杨)

College of Information System and Management, National University of Defense Technology, Changsha 410073, China

© Central South University Press and Springer-Verlag Berlin Heidelberg 2013

Abstract: A new genetic algorithm for community detection in complex networks was proposed. It adopts matrix encoding that enables traditional crossover between individuals. Initial populations are generated using nodes similarity, which enhances the diversity of initial individuals while retaining an acceptable level of accuracy, and improves the efficiency of optimal solution search. Individual crossover is based on the quality of individuals’ genes; all nodes unassigned to any community are grouped into a new community, while ambiguously placed nodes are assigned to the community to which most of their neighbors belong. Individual mutation, which splits a gene into two new genes or randomly fuses it into other genes, is non-uniform. The simplicity and effectiveness of the algorithm are revealed in experimental tests using artificial random networks and real networks. The accuracy of the algorithm is superior to that of some classic algorithms, and is comparable to that of some recent high-precision algorithms.

Key words: complex networks; community detection; genetic algorithm; matrix encoding; nodes similarity

been widely applied by scholars across the world to detect the community structure of complex networks. 1 Introduction

We develop a simple and effective GA based on

matrix encoding and nodes similarity (abbreviated to With recent advances in complex network research,

many real networks have been shown to possess MENSGA), for community detection in complex

networks. In MENSGA, network modularity function is community structure; in other words, the whole network

is composed of several communities. Community set as target and fitness function, matrix encoding is

adopted, and nodes similarity is used to generate an structure emerges as the third important characteristic of

complex networks, the other properties being initial population. The details of the algorithm are

described in the next section. small-world and scale-free. In complex networks, the nodes in a community connect closely with each other,

while communities connect sparsely with other 2 MENSGA communities. Community structure acquires different meanings in different application fields. For example, in 2.1 Network modularity function a social network, the community represents a group of Let G(V, E) represent a complex network, where V people closely connected or possessing similar and E represent the node set and edge set of the network, characteristics, while in world-wide-web terminology, a respectively, and

webpage community comprises a set of webpages linked V {vi|i 1, 2, ,n},E {ei|i 1, 2, ,m} by a common theme. In 2002, NEWMAN and GIRVAN

where n and m are the numbers of nodes and edges, [1] initiated a new development in complex networks

respectively. research, i.e., community detection in complex networks.

Network modularity function, also called Community detection attempts to gain a meaningful

Q-function, is widely used to quantitatively evaluate the community partition of complex networks by using the

community partition of complex networks. It is information hidden in network topology. Assuming that

expressed as follows [1]: all nodes in complex networks can be assigned to groups,

these nodes are divided into several mutually exclusive kikj 1

a communities. Therefore, community detection in Q ij (ci,cj) (1) 2mij 2m

complex networks is a typical NP combinatorial optimization problem. Owing to its high performance in where aij is an element of the network adjacency matrix solving NP-hard problems, genetic algorithm (GA) has A=(aij)n×n. If vi and vj are connected by an edge, then

Received date: 2012 05 10; Accepted date: 2012 10 18

Corresponding author: LI Yun, PhD Candidate; Tel: +86 13787092573; E-mail: lee2003100@163.com

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email