基因算法在社区发现中的应用,一篇很好的论文,值得学习
J. Cent. South Univ. (2013) 20: 1269 1276 DOI: 10.1007/s11771-013-1611-y

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
局部搜索 10.3724/SP.J.1004.2011.00873 Genetic Algorithm with Local Search for Community Detection in Large-scale Complex Networks JIN Di1, 2 LIU Jie...
遗传 算法 ;单 向交叉 中 图分 类号 :TP301.6 文 献标 志码:A Community detection in complex networks based on immune genetic algorithm CAO Yongchun...
C.A multi—objective genetic algorithm for community detection in networks,in...煤 炭技术 ,2013,02:213—214. (2) 资源共享 区: 提供 了老师和学生上传...
A new overlapping communities detection algorithm based on links is proposed...community structure in complex networks〔J〕 . New Journal of Physics, 2009...
Community detection in complex networks using genetic algorithms [Online], ...GA-net: a genetic algorithm for community detection in social networks. In...
2013. 02. 036 ON COMMUNITY DETECTION OF COMPLEX NETWORKS BASED ON ALGEBRAIC...complex network segmentation algorithm,we present a spectrum optimisation model ...
A new overlapping communities detection algorithm based on links is proposed...community structure in complex networks〔J〕 . New Journal of Physics, 2009...
Genetic algorithm with local search for community detection in large-scale complex networks. Acta Automatica Sinica, 2011, 37(7): 873?882 (金弟, 刘杰,...
Real-Coded Genetic Algorithm for Rule-Based ...a complex system and in the absence of domain ...community have come to champion the large alphabet...
BIOINFORMATICS GARD A Genetic Algorithm for Recombination Detection Motivation:...Arbitrarily complex models of point substitution (e.g. those allowing site-...
热门文档