基于多目标优化的社团发现及系统实现

发布时间：2021-01-24 01:21

　　近年来,随着复杂网络研究的兴起,复杂网络中的社团发现备受关注。社团结构是复杂网络最重要的拓扑结构属性之一,它揭示了复杂网络的隐藏规律和行为特征。复杂网络中的社团发现对揭示网络的结构和功能之间的联系有着重要的意义。社团发现中常见的方法是优化单个目标函数,例如模块度Q。目前的大多数算法都采用了将模块度作为优化目标,进而将社团发现问题转化为优化模块度的问题。然而,这些算法大部分都有很高的复杂度,并不适合解决大规模网络问题。而另一方面,由于采用单个优化目标,这些算法都不可避免地会存在解限制的问题。为解决上述第一个问题,本文首先提出了将遗传算法引入社团发现,产生了一种新的算法,有效解决了目前的社团发现算法效率低的问题,并通过四个实验证明了该算法的有效性。另一方面,为解决单目标优存在的解限制问题,本文又提出了将进化多目标算法应用于社团发现。该算法同时优化两个互补的目标函数,并返回一组在这两个目标函数之间进行折中优化的非占优解。在返回的非占优解集中需要选择一个作为最优解,本文进一步提出了四个模型选择标准。相关实验分为两个部分：第一部分的实验结果表明进化多目标优化算法运行一次能够找到多个从不同角度反映... 

【文章来源】：北京邮电大学北京市 211工程院校 教育部直属院校

【文章页数】：75 页

【学位级别】：硕士

【部分图文】：

一个简单的遗传算法流程图

而图中的社团则由结点集合来表示。在为社团划分进行编码方面，我们使用了邻接点表示法[36]，如图3一1所示。每个基因型包含了91，92，…，g。n个基因(n为网络中结点个数)，每个基因gi表示了结点i的一个邻居结点编号。因此，第i个基因的值j表示了结点i和j之间有边相连，从社团划分结果来看，则表示结点i与j被划分到了同一个社团中。解码过程需要对图中每一个连通分量进行识别。隶属于同一个连通分量的所有结点被划分到同一个社团。因为解码过程采用的是一种回溯的策略，解码过程的时间复杂度呈线性。解码过程的伪代码在附录1中说明。通过以上对编码解码过程的说明，不难看出采用邻接点编码策略解决社团发现问题十分有益。其中最大的一个优点就是决策者不用事先定义划分社团个数

图3-2一个交叉操作的实例图。源染色体A中的基因g:与目标染色体B中的基因98位置交换。3.2实验本节将进行四个实验，分别从四个方面来验证GACD的性能。实验环3GH主频、IG内存、运行Linux.我们首先对已知其社团结构的人工网络进行实验来验证算法的准确性。对象是一个有128个结点，平均分成了四个各自包括犯个结点的网络[371。中的平均结点度为16，kou，表示不同社团之间结点连接的平均度，气表示同团的结点之间相连的平均度(*、+k0.，=16)。实验首先产生了一组这样的网络，的蠕值从0逐渐增加到10。随着kou，值的增加，网络的社团结构也越来越

【参考文献】：
期刊论文
[1]进化多目标优化算法研究[J]. 公茂果,焦李成,杨咚咚,马文萍.  软件学报. 2009(02)
[2]复杂网络聚类方法[J]. 杨博,刘大有,金弟,马海宾.  软件学报. 2009(01)
[3]基于信息瓶颈的社区发现[J]. 沈华伟,程学旗,陈海强,刘悦.  计算机学报. 2008(04)
[4]一种从马尔可夫聚类簇发现潜在WEB社区特征的方法[J]. 杨楠,林松祥,高强,孟小峰.  计算机学报. 2007(07)
[5]一种快速的基于占优树的多目标进化算法[J]. 石川,李清勇,史忠植.  软件学报. 2007(03)



本文编号：2996290