多目标复杂网络社团检测算法和决策策略研究

发布时间：2020-06-30 04:27

【摘要】：现实世界存在大量的复杂系统,这些复杂系统可以抽象描述为复杂网络。近年来,复杂网络引起了不同领域学者的广泛关注。社团结构是描述复杂网络的重要特性之一,通常,社团内部节点之间的连接较为紧密,而社团之间节点的连接较为稀疏。检测社团结构有助于更好地分析复杂网络结构信息并进一步挖掘复杂网络的潜在功能。因此,复杂网络社团检测是一个重要的研究课题,具有重要的理论意义和现实价值。当前,多目标优化算法是解决复杂网络社团检测问题的重要方法之一。本文提出了一种基于knee point的多目标优化社团检测算法并提出两种决策策略,可以帮助决策者从由多目标优化算法得到的众多社团划分中获得最终的理想划分结果。本文的主要研究工作如下：(1)本文提出了一种基于knee point的多目标社团检测算法。当前的多目标优化社团检测算法没有关注搜索过程中出现的关键点,这种关键点可能对应比较好的网络社团划分。为了找到这种潜在的比较好的划分,本文提出了一种基于knee point的多目标优化社团检测算法(KP-Net),该算法可以搜索到Pareto前沿面上的关键点即knee point,这种关键点对应的是潜在的比较好的划分。knee point与其他划分不同,当一个目标函数值减少很小时,会引起另外一个目标函数值大幅度地增加。因此,作为前沿面上的关键点,knee point对应的是潜在的比较好的划分。在扩展的GN基准网络数据集和真实世界网络上进行测试,并与经典的社团检测算法进行比较,实验结果表明,KP-Net算法可以很好地检测到网络社团结构,是一种有效的社团检测算法。(2)本文提出了两种多目标社团检测决策策略。由于多目标优化社团检测算法得到的结果是一组划分而不是单个划分,需要决策者从中选出一个理想的划分结果,这就给决策者的决策工作带来了挑战,如何从这组划分中得到理想划分结果成为一个待解决的问题。当前的多目标优化社团检测算法往往从中选择模块度最大的划分结果作为最终结果,但是模块度最大的划分并不一定对应最好的划分结果。本文提出两种可以获得理想划分的多目标社团检测决策策略。第一种是基于knee point的决策策略,这种决策策略从多目标算法返回的一组划分中选择knee point作为最终划分结果。和其他划分结果相比较,knee point是决策者所感兴趣的解。因此,基于knee point的决策策略选择knee point作为提供给决策者的最终划分结果。第二种是基于多数投票的决策策略,这种决策策略运用多数投票规则,根据多目标优化社团检测算法得到的所有划分产生一个新的网络划分,对于复杂网络中的两个节点来说,如果在得到的这组划分结果中大多数划分将这两个节点划分到同一个社团,那么最终划分结果就将这两个节点划分在同一个社团。在GN基准网络数据集和真实世界网络上的实验结果表明,本文提出的两种决策策略能够从多目标社团检测算法得到的众多划分中获得复杂网络的理想划分。
【学位授予单位】：安徽大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5;TP301.6
【图文】：

美国政治,示例

题Ｐ—７１。复杂网络可１＾用图模型来表示，其中节点对应网络中的个体成员，边对逡逑应网络中节点间的某种相互关系。逡逑图１．１给出美国政治书籍网络的示例。美国政治书籍网络（ｂｏｏｋｓ邋ａｂｏ山ＵＳ逡逑ｐｏｌｉｔｉｃｓ）由Ｖａ］ｄｉｓ邋Ｋｒｅｂｓ根据Ａｍａｚｏｎ在线书店出售的有关美国政治的书籍得到，逡逑该网络包含１０５个节点和４４１条边。网络中的节点代表Ａｍａｚｏｎ中出售的有关美逡逑国政治的书籍，边代表频繁地有买家同时购买这两本书。Ｍａｒｋ邋Ｎｅｗｍａｎ分析了逡逑Ａｍａｚｏｎ网页上公布的关于这竖书籍的描述和评价，将这个网络分成＂中间派＂、逡逑＂自由派＂和＂保守派＂Ｈ类。逡逑图１．１：美国政治书籍网络示例逡逑Ｆｉｇ．邋１．１：邋Ｔｈｅ邋ｎｅｔｗｏｒｋ邋ｏｆ邋ｂｏｏｋｓ邋ａｂｏｕｔ邋ＵＳ邋ｐｏｌｉｔｉｃｓ逡逑１逡逑

社团,社会网络,示例

图１．２：社会网络社团结构示例逡逑Ｆｉｇ．邋１．２：邋Ｅｘａｍｐｌｅ邋ｏｆ邋ｃｏｍｍｕｎｉｔｙ邋ｓｔｒｕｃｔｕｒｅ邋ｏｆ邋ｓｏｃｉａｌ邋ｎｅｔｗｏｒｋｓ．逡逑图１．２给出社会网络社团结构的示例。网络中节点代表狂会中的人，边代表逡逑两个人之间存在某种关系。将同一社团中的节点用同一种颜色表示，从图上可Ｗ逡逑看出，这个网络被划分为Ｈ个社困（分别用红色，黄色和绿色的点表示），在同逡逑一社团中的人具有某种共同的属性，例如，拥有相同的兴趣爱好或者是共同的朋逡逑友圈等。逡逑３逡逑

【相似文献】