复杂网线中基于k-shell的社团发现方法

《复杂网线中基于k-shell的社团发现方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、粤二息心却-·≯【‰-二叫●l秘溅鬻溉鳓燃鬟姆螭鳓魈蚓确醐缵龋瓣躺‘!毒：爱灌囊萋■牯!，晰，：0牲#*朔j盛翟翟置■I孺豫i，蒸”端“烈涮雠纛％谚锦势∥ji耋瓢牌鳓粪鬟口嚣繁嚣誓口山东大学硕士学位论文复杂网络中基于k．shell的社团发现方法于洋(山东大学数学学院，济南，250100)(指导老师：吴建良)中文摘要图论的起源可以追溯N17世纪欧拉对于哥尼斯堡七桥问题的研究。在20世纪60年代，著名的数学家ErdSs和R6nyi所提出的随机图模型构成了现代复杂网络研究的基本理论。在1998年和1999年的《科学》和《自然》上发表的两篇文章，分别揭示出绝

2、大多数现实世界的复杂网络共有的性质：无标度性和小世界性，并建立了相应模型来描述这些特性的产生机理。这两篇文章的发表也开辟了复杂网络研究的新纪元。进入新世纪，学科之间的相互交叉，使得人们能够收集到广泛的不同类型的网络数据，并且随着计算机科学的迅猛发展，人们开始能够处理超大规模的复杂网络的数据。目前科研人员主要关注于研究复杂网络的以下几个方面：对于复杂网络的统计特性以及这些统计特征的度量方法和产生机制的研究、通过分析复杂网络的拓扑结构达到预测和控制整个网络的目的的研究，以及网络的结构稳定性和网络的演化动力学机制的研究等。复杂网络的社团结构是许多实际网络都

3、具有的共同性质，复杂网络的社团结构的研究对于分析复杂网络的拓扑结构、深入了解网络的功能和对复杂网络的预测与控制具有重要的作用。复杂网络中的社团，也称聚类，是网络中相互关系比较紧密的节点构成的集合。迄今为止，已经有了对于社团划分的多种算法：基于模块度概念和贪婪思想的Newman分裂算法和凝聚算法，划分重叠社团的派系过滤算法，利用划分边的社团进而得到点的重叠社团的边社团算法等等。本文正是对复杂网络中的社团发现的研究与扩展。k—shell是新近提出的图论中的概念，研究表明，k值大的k-shell层中的节点比传统研究中所考虑的度数大的节点对于图的拓扑性质以及

4、网络中信息的传播所起的作用要大，最大k值的k-shell中的节点更倾向于成为网络的中心，因此对于图的k-shell及其应用的研究也在逐渐兴起。对于k-shell的定义如下：山东大学硕士学位论文定义1k-core是指图G的一个极大子图，在这个子图中的所有节点的度至少是k。定义2把从(k一1)一core的点集中去掉k-core中的点所剩余的节点生成的子图定义为k-shell。并把图的所有的七一shell中具有最大的k值的那一个记为kmax-shell。‘●鉴于k-shell在网络拓扑结构中的重要作用，我们将其应用在社团发现的算法之中。首先，我们将k-sh

5、ell与Newman凝聚算法相结合从而得到一个新的划分社团的算法。算法的基本思想是以kmax-shell中的节点为中心，然后利用使模块度最大化的贪婪思想，按照后值由大到小的顺序逐层合并图中的剩余节点到k?7，ax-shell的节点所在的社团中去，这样我们就得到了一个以kmax-shell中的节点为中心的社团结构，然后再使用凝聚算法对这个社团结构继续进行计算，最后我们选择网络中对应着局部最大模块度的那个社团划分。然后，我们将k-shell与边社团划分算法结合，得到一个新的划分重叠社团的算法。由于k-shell的重要作用，kin,=-shell中的节点是

6、图中的关键节点，那么与它们相连的边也是图中关键的边，所以我们优先考虑与七。。。一shell中的节点相连的边的社团划分。我们逐步选择k??-。ax-shell的节点周围的边相似度最大的、没有被考虑过的相邻的边对，并将它们合并到一个社团中，直到k。。一shell中的节点周围的所有边的社团所包含的边的数目都大于1。然后逐渐减小k值，再用同样的方法，逐步合并相应的k-shell中节点周围的边对所属的两个社团。这时我们得到了网络的一个边社团结构，再用原始的边社团算法对这一个已经有了一定的边社团划分的网络进行计算，直到所有的边都被划分到一个社团内为止。最后我们选

7、择对应着局部最大划分密度的那个边社团的划分作为最后的划分，再用边的社团标号来标记边的两个端点所属的社团，这样就得到了一个网络中节点的重叠社团结构。经过对上述两个算法的实际测试发现，我们的算法比原来相对应的算法有更好的划分结果，并且算法的复杂性也没有数量级上的增加，但是所得到的社团却有了更加现实的意义。最后我们将k-shell、模块度、边相似度和划分密度的定义推广到赋权图之中，然后将其应用到赋权图的社团发现方法之中，这样我们就得到了赋权图的基于k-shell的社团划分算法。关键字：复杂网络；社团；算法；k-shell；图论一II一口◆山东大学硕士学位论

8、文Communitydetectionmethodsbasedonk．·shellincomplexnetw