论文部分内容阅读
现实世界存在大量的复杂系统,这些复杂系统可以抽象描述为复杂网络。近年来,复杂网络引起了不同领域学者的广泛关注。社团结构是描述复杂网络的重要特性之一,通常,社团内部节点之间的连接较为紧密,而社团之间节点的连接较为稀疏。检测社团结构有助于更好地分析复杂网络结构信息并进一步挖掘复杂网络的潜在功能。因此,复杂网络社团检测是一个重要的研究课题,具有重要的理论意义和现实价值。当前,多目标优化算法是解决复杂网络社团检测问题的重要方法之一。本文提出了一种基于knee point的多目标优化社团检测算法并提出两种决策策略,可以帮助决策者从由多目标优化算法得到的众多社团划分中获得最终的理想划分结果。
本文的主要研究工作如下:
(l)本文提出了一种基于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基准网络数据集和真实世界网络上的实验结果表明,本文提出的两种决策策略能够从多目标社团检测算法得到的众多划分中获得复杂网络的理想划分。
本文的主要研究工作如下:
(l)本文提出了一种基于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基准网络数据集和真实世界网络上的实验结果表明,本文提出的两种决策策略能够从多目标社团检测算法得到的众多划分中获得复杂网络的理想划分。