基于密度峰值的重叠社区发现算法研究

发布时间：2017-12-02 07:01

  本文关键词：基于密度峰值的重叠社区发现算法研究

  更多相关文章： 复杂网络 社区发现 重叠社区 小世界特性 模块度函数

【摘要】：在现实世界中，许多复杂系统是由大量组成单元或子系统构成的，因而可以将该它们抽象成复杂网络，网络中的节点是复杂系统的构成单元，而网络中的边则是单元之间的相互关系。复杂网络的应用领域非常广泛，如社会领域中的演员合作网、友谊网、科研合作网、Email网；生态领域中的食物链网、新陈代谢网、蛋白质网、基因调控网络；技术领域中的电力网、Internet网络以及电话线路网络，等等。尤其是近几十年间，互联网技术的迅猛发展使世界变得更小了，人与人之间的联系更加紧密，人类已经生活在充满形形色色的复杂网络的世界中。因此，复杂网络的相关研究也越来越成为一个研究的热点。 目前，学者们在对复杂网络的研究过程中，发现现实网络不仅具有小世界和无标度等特征，而且还具有社区结构特征。社区与社区之间的连接虽然较为稀疏，但是社区内部的节点之间的连接却非常稠密。因此，社区结构的研究在当前复杂网络发展过程中占据着相当重要的地位。 传统的社区发现算法主要分为图形分割和层次聚类两大类方法,其中，层次聚类又包括凝聚算法和分裂算法两类。随着对社区发现的深入研究，Newman等人提出了模块度函数，随后又出现了某些基于模块度极值优化的方法。然而，在现实生活中的网络，其节点并不是完全只属于某一个社区，而是可能属于多个社区，也就是说网络中存在着重叠部分。因此，学者们为了能更加真实地刻画网络的结构特征，又提出了许多重叠社区划分方法。一些研究者将统计推理应用到重叠社区划分算法中，取得了较好的效果，如GN算法、SPAEM算法等。 本文主要针对复杂网络重叠社区发现算法进行研究，通过借鉴最近Science上提出的基于快速搜索和发现密度峰值的聚类方法思想，提出了“基于密度峰值的重叠社区发现算法”。本文首先对社区发现算法的相关文献进行了综述，介绍了复杂网络中社区发现算法的类别以及相应优缺点等，，对一些经典算法的核心思想、适用范围、时间复杂度等方面进行了分析。之后，论文还详细介绍了Science上提出的基于快速搜索和发现密度峰值的聚类方法，分析了该算法的核心思想。 在深入理解基于快速搜索和发现密度峰值的聚类方法的基础上，本文提出了基于密度峰值的重叠社区发现算法。算法首先通过给出新的距离矩阵算法避免了现有邻接矩阵都为整数，且有大量重复的问题。之后在搜索中心的过程中与原有算法一样，认为那些具有高局部密度并且到更高局部密度的点的最短距离相对较高的节点才是类簇中心。得到类簇中心后，不再限制每个节点属于某一单个社区，而是以一定概率属于各个社区，计算社区内节点的概率分布矩阵，得到相应的划分结果，从而使得重叠社区的划分成为可能。为验证所提出算法的有效性，将其应用于实际网络中，如空手道网络、海豚关系网等。对karate数据和dolphins数据的划分结果与原数据的社区划分结果基本相类似，对于稍大规模的网络得到的重叠社区划分结果要比其它算法好。 论文主要是通过将基于快速搜索和发现密度峰值的聚类方法引入到重叠社区划分问题中，通过定义新的距离矩阵算法克服邻接矩阵为整数的缺陷，并以概率形式刻画每个节点属于不同类别的可能性，实现了重叠社区的划分。所提出的基于密度峰值的重叠社区发现算法简单易懂，既能够用于非重叠社区的划分，也可以进行重叠社区的划分，而且还可以扩展到加权网络。此外，该算法不用事先预设社区的个数，可以通过决策图来判断社区个数以及类簇中心节点。并且，基于真实网络的实验证明了本文提出算法的有效性。
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【共引文献】

中国期刊全文数据库 前10条

1 淦文燕;赫南;李德毅;王建民;;一种基于拓扑势的网络社区发现方法[J];软件学报;2009年08期

2 李琳;李生红;陆松年;陈秀珍;;基于PCA的社团结构谱聚类改进算法[J];计算机工程与设计;2013年10期

3 刘伍颖;易绵竹;张兴;;一种时空高效的多类别文本分类算法[J];山东大学学报(理学版);2013年11期

4 王庚;宋传超;盛玉晓;王童童;李盛恩;;基于标签传播的稳定重叠社区挖掘算法研究[J];山东科学;2013年05期

5 You-Ping Li;Wei-Qun Gan;Li Feng;Si-Ming Liu;A.Struminsky;;The breakdown of the power-law frequency distributions for the hard X-ray peak count rates of solar flares[J];Research in Astronomy and Astrophysics;2013年12期

6 阳广元;曹霞;甯佐斌;潘煦;;国内社区发现研究进展[J];情报资料工作;2014年02期

7 刘倩;刘群;;基于引力度扩展的重叠社区发现算法[J];计算机工程与设计;2014年03期

8 周秋菊;杨立英;岳婷;丁洁兰;;基于期刊同被引和互引网络的学科结构和知识流动研究[J];情报杂志;2014年08期

9 董哲;伊鹏;贺成龙;;基于链路标签传播的重叠社团发现算法[J];计算机工程与设计;2014年10期

10 侯思权;张振宇;文少杰;;基于边权重局部扩展的机会网络社区检测方法[J];计算机工程与设计;2014年11期

中国重要会议论文全文数据库 前5条

1 ;Fuzzy Analysis for Overlapping Community Structure of Complex Network[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

2 伍勇;钟志农;景宁;李星;;适于社区挖掘分析与可视化的布局算法[A];第29届中国数据库学术会议论文集（B辑）（NDBC2012）[C];2012年

3 Hongbo Li;Wenjing Geng;Yu Wu;Xian Wang;;An Improved Force-Directed Algorithm Based on Emergence for Visualizing Complex Network[A];2013年中国智能自动化学术会议论文集（第二分册）[C];2013年

4 Yun Li;Gang Liu;Song-yang Lao;;Overlapping Community Detection in Complex Networks based on the Boundary Information of Disjoint Community[A];第25届中国控制与决策会议论文集[C];2013年

5 李杰;张皎娟;;C2C电子商务顾客重复购买幂分布规律及其影响因素[A];2013中国信息经济学会学术年会暨博士生论坛论文集[C];2013年

中国博士学位论文全文数据库 前10条

1 沈项军;基于语义学习的图像检索研究[D];中国科学技术大学;2006年

2 万里;时间序列中的知识发现[D];北京邮电大学;2009年

3 马瑞新;基于粒子群的网络社区动态角色挖掘研究[D];大连理工大学;2012年

4 朱岩;面向文本数据的半监督学习研究[D];北京交通大学;2012年

5 黄亮;社会网络中的社区发现与链接预测算法研究[D];华中科技大学;2012年

6 何边;复杂网络上的分块问题[D];上海交通大学;2012年

7 高雅纯;基于复杂系统理论的金融市场动力学研究[D];中国科学技术大学;2013年

8 吴联仁;基于人类动力学的社交网络信息传播实证分析与建模研究[D];北京邮电大学;2013年

9 陈t

本文编号：1244013