论文部分内容阅读
现实世界中众多的复杂系统都可抽象地表示为网络,对网络的研究已经渗透到各个学科领域。网络通常具有社团结构特性,发现网络中的社团结构有助于更好地理解网络系统的结构和功能,挖掘系统的潜在信息和隐藏规律,对一些未知的功能和行为进行预测。在现实世界中存在一些特殊的网络,每个节点具有一个或多个描述其特征的属性,通常称这种网络为属性网络。挖掘属性网络的社团结构不仅仅依赖于网络的拓扑结构,节点的属性信息也是一种重要的信息源,它具有与拓扑结构互补的重要意义。近年来,基于不同的策略,多个领域的研究者们已经提出了许多属性网络社团检测算法,如何综合利用网络的拓扑结构和节点的属性信息,将网络划分为集合内联系密切且具有较多公共属性的节点集是一个具有挑战性的问题。基于此问题,本文提出了一种基于节点属性信息优化网络结构的多目标进化社团检测算法,之后根据其在属性信息嘈杂的网络上出现的性能下降问题,做了进一步研究,提出了基于双种群协同进化平衡拓扑结构和属性信息的多目标进化社团检测算法。本文的主要研究工作如下:(1)本文提出了一种基于节点属性信息优化网络结构的多目标进化社团检测算法(MOEA-AT)。MOEA-AT算法利用进化算法框架从构建的属性相关网络中选择一些边添加到原始网络,增强了社团内节点之间的联系,使网络的社团结构更加明显。之后设计了一种根据拓扑网络变化局部调整社团归属的社团调整策略,从而快速获得子代网络对应的社团划分。MOEA-AT算法在挖掘社团结构的过程中不需要人为设定社团数目,同时避免了线性叠加网络拓扑结构和节点属性信息挖掘社团结构的算法需要指定平衡参数的问题。在不同生成参数的LFR属性网络和真实属性网络上与当前几种优秀的社团检测算法进行比较,实验结果表明,MOEA-AT算法相比于其他算法在优化网络结构,确定社团数目和检测社团精度方面均具有一定的优势。(2)MOEA-AT算法利用节点属性信息优化网络结构的方式在一定程度上综合利用了网络的拓扑结构和节点的属性信息,在拓扑结构不明显的网络上表现出较高的性能,并具有较高的稳定性。然而当属性信息越来越嘈杂时,MOEA-AT的算法出现了性能急剧下降的问题。基于此问题,本文提出了一种基于双种群协同进化平衡拓扑结构和属性信息的多目标进化社团检测算法(MOEA-DP)。在MOEA-DP算法中建立了两个种群,一个种群根据网络拓扑结构挖掘社团,另一个种群根据节点的属性信息挖掘社团。两个种群通过不同的基因重组方法独立进化,每隔一定的代数选择各自种群的非支配个体进行交互,以获得另一个种群挖掘的优异的社团结构信息。在随机属性网络上和真实属性网络上与当前几种优秀的社团检测算法进行比较,实验结果表明,MOEA-DP算法相比于其他算法在网络结构不明显和属性信息嘈杂的网络上均具有一定的优势。