基于锥面积演化算法的社会网络多目标社区检测

发布时间：2020-06-30 12:48

【摘要】：社会网络(SNs)的研究是近年来的热点。现实世界中,通常情况下实体和它们之间存在的关系可以由各种社会网络代替。比如朋友关系网,新陈代谢网络等。实体抽象为社会网络的节点,它们之间的关系则是社会网络的连边。随着对社会网络研究的不断深入,研究者发现大多数社会网络具有社区结构的特征,即社会网络可以分为一定数量并且规模大小不定的社区。通常,对于社会网络的一对节点,它们之间更大的连接强度意味着这对节点在同一社区的可能性越大。特别的,如果一个社会网络中既存在正连边又存在负连边,那么该网络称为符号社会网络;如果社区结构中存在共享节点的社区,那么社会网络带有重叠社区。尽管目前出现了很多社区检测算法,但大多数都是针对无符号和不存在重叠社区结构的社会网络。显然,符号社会网络和带有重叠社区的社会网络能更有效地表示现实世界的各种网络,更符合现实意义。在符号社会网络中,社区结构的划分不仅要考虑连接强度,还要依据连接的属性。在带有重叠社区的社会网络中,如何有效表示重叠节点是个难题。为了更好的检测符号社会网络,和具有重叠社区结构的社会网络,同时考虑现实世界社会网络存在噪音的问题,本文完成以下研究内容从而设计针对以上两种类型社会网络的社区检测算法。(1)提出混合符号相似度和网络节点间固有连接权重来定义节点的连接强度用于符号社会网络社区检测。首先,本文的节点连接强度克服了仅使用符号相似度不适用于稀疏网络的缺陷和单使用节点连接权重容易被噪音干扰的弊端。同时基于本文定义的节点连接强度设计的社区紧致度在初始化时生成更有社区结构意义的种群,并在进化过程中发挥指导基因是否发生变异的作用。然后,结合更为高效的多目标优化算法CAEA,实现符号网络社区检测算法。(2)结合CAEA与最大团表示机制对社会网络重叠社区检测。借助于分解的思想,MOEA/D将一个多目标优化问题分解成多个单目标优化子问题,并通过种群进化同时优化这些子问题。与MOEA/D不同,CAEA不仅将多目标优化问题分解为多个规模的子问题,而且还给每个子问题分配一个独有的决策子区域。此外,每个子问题都使用锥形区域指示器作为其标量目标,在其关联的决策子集中找到一个局部非支配解。实践表明,CAEA算法拥有更好的效果和更高的效率。将团和最大团应用在社区检测上有效地利用了团之间共享节点恰符合重叠社区结构的属性。在预处理阶段找出所有的最大团,将最大团设为新的节点,然后使用简单个体直接表示机制便可以进行重叠社区检测。同时,针对目标函数尺度不同导致的进化偏向大尺度目标,进而损失种群多样性的问题,本文设计了目标函数的离差标准化。(3)分别在真实世界网络,人工合成网络(即带噪音的网络)两类网络对两个算法的性能进行全面评估。其中人工合成网络实验使用多种参数组合进行了较为系统的实验,这些实验包含较大规模,较高噪音时对两个算法的检验。并与性能表现良好的MEAs-SN,louvain和实验MCMOEA进行系统对比,以验证本文算法在社区检测问题上的有效性和高效性。在人工合成网络和现实世界网络的实验结果表明,本文设计的两个基于锥面积演化算法的社会网络多目标社区检测算法在相应类型的社会网络社区检测问题上,不仅能够获得优异的检测结果,同时还拥有较高计算效率和鲁棒性。
【学位授予单位】：华南理工大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP393.09;TP301.6

【参考文献】