基于遗传算法的社区发现
时间:2018-07-21 14:05 来源:毕业论文 作者:毕业论文 点击:次
| 摘要 近年来，复杂网络社区结构检测的问题一直作为热点话题被各领域科研工作者深入研究。在本文中，我们设计了一种基于遗传理论在社交网络结构中发现社区划分的算法。该算法，使用轮盘赌选择与精英选择机制结合的方法实现遗传算法选择操作，交叉操作是对编码后的染色体进行的单点的社团代表性结点值互换，变异操作是对编码后染色体部分位值变换为其随机连接结点所在社团，并使用一个简单有效的，能够识别组间密集连接组结点的适应度函数即模块化 Q函数。实验测试数据使用三个真实世界社区网络，由邻接矩阵表示的三个数据集，实验结果与标准社区结构划分结果对比表明，该算法在真实世界网络中进行的实验能够检测到较好较接近标准划分的社区网络结构划分方法。26009 毕业论文关键词 遗传算法 社区发现 社区结构 模块度 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] 等等。这些复杂网络都由两部分构成，结 点集和边集， 其中结点代表现实世界系统中的实体, 边则代表这些实体两两之间的某些联系， (责任编辑：qin) |