基于核心节点的复杂网络社区划分算法

发布时间：2019-08-11 13:28

【摘要】：针对全局社区发现方法计算复杂度过高,而局部社区发现方法社区发现质量偏低的不足,提出了一种快速有效的社区划分算法。算法预先探测网络中属于不同社区的核心节点,利用基于相似性传递的节点相似性度量方法度量核心节点与网络中其他节点之间的相似性,根据相似性度量结果对网络进行社区结构划分。在采自人人网的数据和公共的网络数据上进行了实验,并与经典算法进行比较,实验结果表明了该算法的可行性和有效性。
【图文】：

空手道,俱乐部,成员,相互关系

量顶点相异度的方法。结构同等是指两个节点的链接关系相同，即两个节点有着相同的邻居节点，，若节点ｉ和ｊ结构同等，则ｄｉｊ＝０。这种方法可以计算出网络中任意节点之间的相异度，但是计算的结果有时并不能正确的反映节点之间的相异程度，如图１所示。采用式（２）计算出Ｖ１２与Ｖ１的相异度为３．８７３，而Ｖ１２与Ｖ３３的相异度为３．６０５６，根据计算结果得到Ｖ１２与Ｖ３３更加近似，但是图中显然可以看出Ｖ１２仅与Ｖ１有边连图１空手道俱乐部成员间的相互关系接，计算结果显然得出了错误的相异性度量。但是当利用式（２）计算Ｖ３３，Ｖ１与Ｖ３４的相异度时，计算结果正确的反映出了节点之间的相异程度。可以发现Ｖ１２处于网络的边界位置，与该节点的邻居节点个数很少，而Ｖ３３，Ｖ１与Ｖ３４都是大度数节点，所以发现采用式（２）往往不能正确得到低度数节点与其他节点的相似度，但可以用于计算大度数节点之间的相似度。局部相似性度量方法共同特点是利用节点的邻域子图，该类方法认为两个节点共有的邻居节点越多，则两个节点之间就更加相似［７］。节点Ｖｉ的邻居节点集记为Ｎ（ｉ），即Ｎ（ｉ）＝｛Ｖｊ｜Ａｉｊ＝１｝。Ｖｉ的星型邻域子图记为Ｓｔ（ｉ），它是由Ｖｉ及其邻居点集构成，即Ｓｔ（ｉ）＝｛Ｖｉ｝∪Ｎ（ｉ）。如图１所示，Ｖ６的星型邻域子图Ｓｔ（６）包括５个节点Ｓｔ（６）＝｛Ｖ１，Ｖ６，Ｖ７，Ｖ１１，Ｖ１７｝，Ｖ６

社区关系,社区

第３４卷第１２期牛冬冬，陈鸿昶，金鑫，等：基于核心节点的复杂网络社区划分算法社区的全部核心节点，对接下来的社区划分具有重要意义。图２是网络Ｇ的简单示意图，设网络Ｇ中存在着３个社区，不同社区之间用虚线连接。图２网络Ｇ社区关系如图２所示，不同的社区内部都会存在着一小部分节点处于社区的中心位置，并且会与网络中的其他节点连接关系紧密，该类节点可认为是网络中的核心节点，本文所要探测的核心节点首先是大度数节点。定义网络中节点的集合为Ｖ＝｛Ｖ１，…，Ｖｎ｝，根据网络中节点之间的链接关系计算网络中所有节点的度数，然后根据度数进行排序，定义排序后的节点集合为，然后取出集合中的前一部分节点即大度数节点构成集合，则网络中不同社区内的核心节点一定处于集合中。在本文社区划分算法中需要获取的是每个社区内部唯一的核心节点，然而同一个社区可能有多个大度数节点存在于集合中，所以需要对集合中的节点进行筛眩结合图２进行分析不难得出由于不同社区的核心节点在网络中相距较远，所以对节点进行相似性度量时，同一社区内部的大度数节点相似度一定远大于不同社区内部大度数节点之间的相似度。利用文中式（２）度量集合中节点两两之间的相似度，将相似度过高的节点从集合中剔除，余下的节点则组成新的集合，该集合即为本文探测出的核心节点集。２．２基于相似性传递的节点相似性度量方法本文进行社区划分时涉及到计算网络中核心节点与网络中其他节点的相似性计算，但是利用式（２）无法得出正确的相似性度量结果，而利用式（３）只能度量与核心节点距离小于３的节点之间的相似性，无法度量网络中所有非核心节点与核心节点的
【作者单位】：国家数字交换系统工程技术研究中心;国家计算机网络与信息安全管理中心;
【基金】：国家973重点基础研究发展计划基金项目(2012CB315901、2012CB315905) 国家自然科学基金项目(61171108)
【分类号】：TP393.09

【参考文献】