复杂网络中的重叠社区发现算法研究

发布时间：2020-06-08 01:28

【摘要】：摘要：随着复杂系统科学的不断发展,同时受到移动通信网络、社交网络等现实网络的推动作用,人们针对复杂网络的研究逐渐深入。由于复杂网络能够很好地描述许多复杂系统,人们期望通过对复杂网络的研究和分析,揭示并掌握其统计特征、功能特性、演化规律等等,从而能够更深刻地理解复杂系统,指导解决实际问题。在研究中人们发现复杂网络存在社区结构,并且社区结构对于理解复杂网络的结构和功能非常重要,许多研究者因此投入到对社区发现的研究,社区发现问题也因此成为近年复杂网络领域中的热门问题。但是该问题迄今并未被完美解决。 本文通过研究近年该领域具有代表性的文献,总结目前典型的一些社区发现算法,并分析它们的优点和不足之处,在此基础上提出一种可以并行化的重叠社区发现算法,以解决当前重叠社区发现算法普遍效率偏低,无法处理超大规模网络的问题。 首先,借鉴将clique作为初始社区核心的思想,本文提出了将clique作为标签传播过程中拥有标签的基本单位这一新思路,并以此为基础提出了一种用于发现网络中重叠社区结构的CLPA算法。在人工网络以及真实网络上的实验结果都证明了基于此思想的重叠社区发现算法的有效性,并且在很多网络上该算法比其他一些算法具有更佳的社区发现结果,同时其时间效率也令人满意。 其次,本文创新性的将MapReduce分布计算模型与重叠社区发现结合。由于本文提出的算法具备并行化的条件,借助于MapReduce分布计算模型,使得对现实中普遍存在的超大规模网络进行重叠社区发现成为可能,因而具有一定的实际意义。
【图文】：

括包括社会网络汇’]、生物学网络[2]、论文协作网络等。复杂网络可以用图的形式表示为G(V，E)，其中，V是节点集合，E是边集。图2.1给出了一种样例。根据网络中边的性质，网络可以分为多种。按照边是有向还是无向这一特征，可以将网络分为有向网络和无向网络。常见的有向网络有电信通话网络、互联网链接关系网络、论文引用网络、邮件关系网络等。常见的无向网络有社交网络、公路网络、集成电路网络、生物学网络等。根据边是带权还是无权这一特征，可以将网络分为带权网络和无权网络。当然无权网络也可以看做是带权网络的特殊形式，，即所有边的权值都是相等的。网络中权值代表的意义与具体网络相关，并

图2.2Enron[54]网络的度分布Figure2.2oe盯eedistributionofEnron[54]network2.1.2主要应用由于复杂网络在表示真实复杂系统方面的天然优势，因此对复杂网络的研究为许多其他学科的研究进展提供了新的思路和方法，复杂网络在生物学、计算机科学、社会学等学科中得到了广泛应用。生物体系中存在大量类似生态环境系统、新陈代谢系统等这样的复杂系统。这些系统存在一个共同点，即都是由大量个体(例如新陈代谢系统中的酶以及生态系统中的各种生物和非生物因子)以及这些个体之间的各种关系组成。这些关系包括新陈代谢系统中各种生物化学反应和生态系统中的捕食、共生等关系。过去的科学研究对于生物体系中的个体性质已经有了非常深刻和细致的了解，科学家们期望研究透彻系统的微观性质，之后通过还原理论的方法获得系统的所有性质，这也成为20世纪在生物学研究中分子生物学占据了核心地位的卞要
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2011
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 郑敏;复杂网络的正弦稳态分析与计算方法[J];青海师范大学学报(自然科学版);1999年01期

2 赵小梅;高自友;黄海军;;复杂网络的时空建模法(英文)[J];交通运输系统工程与信息;2006年03期

3 常慧;何阅;张义勇;苏蓓蓓;何大韧;;中国旅游线路的合作网络描述[J];科技导报;2006年09期

4 张季谦;陈含爽;刘建青;;网络拓扑结构对混沌同步能力的影响[J];安徽师范大学学报(自然科学版);2007年03期

5 刘作仪;;复杂网络理论及相关管理复杂性研究的资助进展[J];中国科学基金;2008年01期

6 侯世中;龚白桦;黄亮;杨孔庆;;嵌入晶格的地理网络的逾渗[J];复杂系统与复杂性科学;2008年03期

7 房艳君;王新春;;基于复杂网络的绩效考核分析[J];复杂系统与复杂性科学;2009年02期

8 ;《系统工程学报》混沌和复杂网络理论与应用专辑征文通知[J];系统工程学报;2009年06期

9 杨月全;余星火;张天平;;时变内耦合复杂网络的平衡态同步smart变结构控制(英文)[J];控制理论与应用;2010年02期

10 杨小刚;马建;陈灿峰;王文东;;移动相册的复杂网络分析[J];计算机应用研究;2010年07期

相关会议论文 前10条

1 汪秉宏;车宏安;;复杂网络与复杂系统[A];第三届全国复杂动态网络学术论坛论文集[C];2006年

2 陈美荣;;回顾与展望(代序)[A];2006全国复杂网络学术会议论文集[C];2006年

3 高亮;樊瑛;吴金闪;狄增如;;复杂网络的最短路径回路性质初探[A];2006全国复杂网络学术会议论文集[C];2006年

4 方锦清;;非线性网络的动力学复杂性研究进展[A];全国复杂系统研究论坛论文集（一）[C];2005年

5 方锦清;;序言[A];第四届全国网络科学学术论坛暨研究生暑期学校论文集[C];2008年

6 杨月全;余星火;张天平;;时变内耦合复杂网络的平衡态同步smart变结构控制(英文)[A];2009年中国智能自动化会议论文集（第八分册）[控制理论与应用（专刊）][C];2009年

7 吴晓锋;陈晔;;舰艇作战系统网络复杂性及其分析[A];第二届全国复杂动态网络学术论坛论文集[C];2005年

8 司守奎;温巧林;孙玺箐;许波林;;复杂网络及其在军事领域的应用研究展望[A];2009年中国智能自动化会议论文集（第三分册）[C];2009年

9 吴俊;谭跃进;;非标度网络理论及其应用综述[A];Well-off Society Strategies and Systems Engineering--Proceedings of the 13th Annual Conference of System Engineering Society of China[C];2004年

10 李平;汪秉宏;;证券指数的权重网络[A];第二届全国复杂动态网络学术论坛论文集[C];2005年

相关重要报纸文章 前10条

1 潘金宽;用复杂网络思维看体系破击的科学内涵[N];战士报;2007年

2 本报记者 胡英;在复杂网络中“缉毒”[N];计算机世界;2003年

3 李;复杂网络 矢量考量[N];中国计算机报;2004年

4 本报记者　房琳琳;数学正向知识和生产领域全面渗透[N];科技日报;2006年

5 北京邮电大学 张民;跳出“技术短板”[N];通信产业报;2006年

6 华中科技大学 范如国;基于复杂网络理论的改革开放制度演化分析[N];光明日报;2008年

7 北京邮电大学光通信中心 张民;RPR商用转型仍需“双连跳”[N];通信产业报;2005年

8 Capgemini公司CTO Andy Mulholland;云计算：从网络与服务起步[N];中国计算机报;2008年

9 陈波;关注信息化战争“无尺度网络”[N];解放军报;2006年

10 记者　 喻春来;国航与国泰商谈"交叉"持股[N];上海证券报;2006年

相关博士学位论文 前10条

1 周海平;复杂网络的演化模型及传播动力学研究[D];贵州大学;2009年

2 郭龙;复杂网络上自组织临界现象及Opinion演化动力学研究[D];华中师范大学;2010年

3 郭淑娟;复杂网络的混沌同步与参数估计[D];上海大学;2010年

4 何红生;非线性波动与复杂网络的研究[D];兰州大学;2006年

5 贾春晓;基于复杂网络的推荐算法和合作行为研究[D];中国科学技术大学;2011年

6 潘新;基于复杂网络的舆情传播模型研究[D];大连理工大学;2010年

7 史冬梅;复杂网络上的合作涌现空间公共品博弈中的异质性研究[D];中国科学技术大学;2011年

8 杜文博;面向航空交通系统的复杂网络与网络动力学研究[D];中国科学技术大学;2010年

9 房艳君;一般复杂网络及经济网络的动态模型与稳定性研究[D];山东师范大学;2010年

10 倪顺江;基于复杂网络理论的传染病动力学建模与研究[D];清华大学;2009年

相关硕士学位论文 前10条

1 刘丽;复杂网络中具有抑制作用的双信息传播建模与仿真[D];青岛大学;2010年

2 王忠;复杂网络在区域集群经济发展中的风险及控制研究[D];江苏大学;2010年

3 李天华;加权复杂网络的病毒传播和免疫策略研究[D];广西师范大学;2010年

4 张喜娟;具有风险预知的复杂网络传染病模型研究[D];中北大学;2010年

5 汪大明;复杂网络社团模型与结构研究[D];国防科学技术大学;2010年

6 刘亚冰;复杂网络中的社团结构特性研究[D];上海交通大学;2010年

7 樊俊;复杂网络中的影响维度：模型及实例[D];兰州大学;2006年

8 张迪;复杂网络及其上的病毒传播和演化博弈的研究[D];西安电子科技大学;2010年

9 尹可可;基于复杂网络理论的三大产业间相互作用研究[D];北京邮电大学;2011年

10 陶建平;基于复杂网络的模糊C均值聚类算法在校园网络安全评估的应用研究[D];合肥工业大学;2010年

本文编号：2702309