关键词:
复杂网络
社团检测
密度峰值聚类模型
多属性决策
摘要:
对复杂网络的研究是数据挖掘的主要方向之一,而社团检测是复杂网络研究的重要组成部分。社团结构揭示了网络各个组成部分的内部组织信息和不同部分的外部连接关系,不仅可以帮助研究人员更好地理解复杂网络,也进一步促进了复杂网络其它方面的研究。在复杂网络中检测社团的过程可以理解为一个聚类过程,社团可以看作节点在网络上紧密连接的簇,而且社团中存在着“簇中心”这样的特殊节点,使得密度峰值模型适用于社团检测问题。本文在以往相关研究的基础上提出了基于密度峰聚类模型和多属性决策算法TOPSIS(Technique for Order Preference by Similarity to an Ideal Solution)的社团检测算法,其中包括适用于普通复杂网络的DPCT算法(Density Peak Clustering and TOPSIS-based community detection algorithm)和适用于多重网络的MDPCT算法(Density Peak Clustering and TOPSIS-based community detection algorithm in Multiplex networks)。(1)适用于普通网络的DPCT算法。DPCT首先将网络中的节点集根据其连接情况,转化为密度峰值聚类模型中与节点密度和距离有关的二维数据集,并用DBSCAN在该二维数据集中聚类,将无法聚在类中的离群点看作“簇中心”,即关键节点。之后,DPCT在关键节点的基础上形成初始的社团框架,通过逐步添加与社团最相似的节点进行社团扩张,形成初始社团。在这个过程中,DPCT使用多属性决策算法TOPSIS综合四种不同相似度的优势,计算出一种更为准确且适应性更强的新相似度T–similarity,使用T–similarity筛选出与社团最相似的节点。然后,DPCT依据T–similarity分配初始社团未覆盖到的非关键节点。最后,通过两种方式,对之前过程中得到的部分规模较小的社团进行合并,得到最终稳定的社团结构。(2)适用于多重网络的MDPCT算法。本文将DPCT算法的基本思想运用在多重网络的社团检测问题中,并进行适应性改进,提出可以在多重网络中检测出高质量社团结构的MDPCT算法。该方法的具体流程与DPCT类似,首先通过多重网络的特性,将节点以密度和距离作为属性转化在密度峰值聚类模型的二维数据集中,同样通过DBSCAN识别其中的离群点作为关键节点。在转化节点信息的过程中,MDPCT使用熵函数充分考虑多重网络中各层的拓扑信息,得到更合理的关键节点。然后,所得关键节点被用于构建多重社团框架,并通过依次添加与社团框架最相似的节点进行扩张,在这一过程中,TOPSIS综合各层网络中的多种节点相似度,计算出可以在多重网络中衡量节点间相似关系的新相似度MT–similarity。多重网络中,扩张后的社团同样无法覆盖到所有节点,因此,M T–similarity也被用以处理扩张结束后未被划分到社团中的非关键节点。在这个过程中,同样会产生一些规模较小且缺乏内部连接的社团,MDPCT将通过聚合多重网络为一层加权网络,并在该网络中分别使用两种针对加权网络改进后的方法对部分小社团进行合并处理,得到高质量的多重网络社团结构。本文在多个真实网络和多组人工合成网络上分别对DPCT和MDPCT进行了实验,并将实验结果与其它优秀的社团检测算法进行对比。实验结果证明,DPCT和MDPCT相对于其它社团检测算法更为准确且适应性更强。