重叠社团的划分算法及其节点影响力的研究

发布时间：2020-06-11 19:20

【摘要】：社团是复杂网络广泛存在的拓扑特性之一,发现网络中的社团结构是复杂网络研究的基础性问题,也是热点问题。社团划分算法按划分结果可以分为重叠和非重叠社团划分算法两类。在社交网络中,与非重叠社团相比,重叠社团更接近于现实的网络结构,因此,本文选择研究重叠社团划分算法。同时,考虑到社团结构的变化可能会对依赖社团的应用产生负面影响,故本文也研究节点对社团结构稳定性的影响,用于辅助分析这类应用的易损性,而这也是近来研究者关注的一个热点问题。针对这两个问题,本文提出如下两种算法:(1)提出一种重叠社团划分算法ESCA(Edge Strength Conductance Algorithm),该算法是针对Conductance算法存在的不足改进后的算法。Conductance算法是一个划分结果相对可靠的有权重叠社团划分算法,但在选择初始社团时没有考虑节点与邻居节点的关系,导致初始社团选择不合理,因而不能更准确地发现网络真实的社团结构,另外算法还存在节点遗漏的问题。针对这一不足,ESCA算法分别从边强度和隶属度的角度解决了这两个问题。实验结果表明:在LFR基准合成的有权和无权网络中,ESCA算法不存在节点遗漏,与Conductance和COPRA(Community Overlap PRopagation Algorithm)算法相比,该算法能够更准确地发现网络存在的社团数,且划分出的社团结构更接近于网络真实的社团结构。(2)提出一种评估节点对网络社团结构影响力的算法BCA(Break Community Algorithm)。BCA首先从网络中识别对社团结构影响最大的子结构,然后评估所有子结构的全局影响力,最后从子结构挑选出对社团结构影响最大的前K个节点。实验结果表明:在LFR基准合成的有权和无权网络中,与传统的节点影响力评估指标相比,BCA能够更准确地发现对社团结构影响最大的节点集。
【学位授予单位】：内蒙古大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP301.6;O157.5

【参考文献】