基于节点间邻居关系的社团检测算法研究

发布时间：2024-05-09 03:00

　　现实世界中存在许多不同类型的复杂网络,它们都蕴含着各自内在的社团结构。社团检测算法可帮助我们发现复杂网络的内在结构与拓扑特征。目前已有多种社团检测算法被提出,因其巨大的实用价值而被广泛应用于现实生活的各个领域。大多数社团检测算法都是基于相似度度量或模块度最大化而提出的。而基于相似度的社团检测算法面临输入参数难以确定以及对特定复杂网络无法准确划分的问题;基于模块度最大化的社团检测算法寻找最优划分的时间复杂度非常高,并且在很多情况下,最大的模块度不一定对应网络的真实划分。为了解决此问题,本文致力于提出快速的、精确的社团检测算法。本文首先从邻居节点间关系入手,提出了一种新的相似性度量方式。不同于传统相似度,此相似度除考虑节点间的公共邻居外,还考虑了节点间的互斥程度。从而,它能更加客观、全面地从节点结构出发反映节点间的相似程度。然后,为了快速、准确地找到不同社团中的核心节点,本文基于节点对其邻居的影响,定义了一种新的局部密度计算方式,并将社团中局部密度最大的节点定义为此社团的核心节点。该密度计算方式认为,一个节点的密度是其对所有邻居节点的影响力之和。节点影响力越大,其密度就越大,对其他节点吸引...

【文章页数】：71 页

【学位级别】：硕士

【部分图文】：

图1.1蛋白质-蛋白质相互作用网络可以说，社团检测在商业、安全以及学术领域都有很大的作用

基于节点间邻居关系的社团检测算法研究-2-但如果将这些数据收集汇总并经过处理分析，就可以将看似没有任何关联的成员进行分类，找到具有相同属性的社团成员。由于处在同一社团中的个体联系较为紧密，所以这些个体必定有相似之处。针对这一特点，系统可以对已划分好的社团成员提供千人千面的个性化服....

图3.1节点间相似度计算举例所用网络

兰州交通大学工程硕士学位论文居数，其中，min(,)uvdd为节点u和节点v中较小度者。两个相邻节点u,vV间的互斥度Exclusion(u,v)计算方法如公式(3.2)所示。(,)=min(,)1(,)uvExclusionuvddCNuv(3.2)在网络G(V,E)中，根据节....

图3.3CDRN算法划分过程示例图

基于节点间邻居关系的社团检测算法研究3的小社团，算法将小社团二次合并，将所有节点数小于3的小社团合并到与之连接最多的社团中。至此完成网络划分，获得最终社团结构。算法3.3为本算法第三小节和第四小节的伪代码。图3.3以RiakMap网络为例，具体展示了CDRN算法的划分网络过程。图....

图4.1LPA算法思想示意图

兰州交通大学工程硕士学位论文图4.1LPA算法思想示意图(6)PPC算法PPC(PersonalizedPageRankClustering)[72]算法将随机游走和模块度两种方法相结合，可以对网络进行精确有效地划分。随机游走适用于社团检测的原因为，有限的随机游走倾向在一个社团内....

本文编号：3968217