基于遗传算法的社区发现
毕业论文关键词 遗传算法 社区发现 社区结构 模块度
Title Community detection in social networks based on the genetic algorithms
Abstract
Recently, the problem of detecting the structure of complex networks has been
extensively studied as a hot topic in the areas of scientific research and so on.
In this paper, we propose an algorithm to find methods of piding network
architecture of social communities based on the genetic theory. The algorithm we
propose in this paper, using roulette selection and elite selection mechanism
implemented method to combine genetic algorithm selection operation, crossover
and mutation operation.The crossover operation is based on the coded chromosome
with one-way crossover operation in the value of the significant node of the
community.The mutation opeartion changes the value of the node to its adjact
node.It is possible to identify the group densely connected set of nodes with a
probable fitness function，which is simple and effective. Experimental tested data
uses three real-world social networks, three data sets represented by the adjacency
matrix, the standard results of community structure piding are compared with
the results of the experiment performed in real-world networks,which can
successfully detect the optimal community network structure and differentiate
their complex communities well.
Keywords Genetic algorithm Community detecting Community structure Modularity
目 次
1 引言· 1
2 遗传算法简介· 3
2.1 算法基本介绍 3
2.2 遗传算法的主要优点· 3
2.3 遗传算法流程介绍 4
2.3.1 编码与解码4
2.3.2 选择操作·5
2.3.3 交叉操作·5
2.3.4 变异操作·5
3 基于遗传算法的社区发现算法设计与实现·7
3.1 控制参数设定8
3.2 编码操作9
3.3 解码操作 11
3.4 选择操作 12
3.5 交叉操作 13
3.6 变异操作 14
4 实验结果与分析·15
4.1 Karate Club 数据集 15
4.2 Dolphins 数据集·17
4.3 Football 数据集·19
4.4 结果分析·23
结 论· 24
致 谢· 25
参考文献26
1 引言
近十几年来，复杂网络这一研究课题逐渐进入越来越多的各个领域的科研人员的研究范
围，如来自计算机学、社会学、物理学、生物学等等各种领域，而复杂网络的社团结构划分
是在此研究过程中被开拓出来的新的研究方向。为了科研者实验研究的方便与深入，很多现
实世界中的复杂系统都表示成各个结构类型的网络, 比如万文网、交通网[1]
、合作网络、因
特网、食物链网[2]
、基因调控网还有人际交往网络[3]
等等。这些复杂网络都由两部分构成，结
点集和边集， 其中结点代表现实世界系统中的实体, 边则代表这些实体两两之间的某些联系，