面向复杂网络的社区发现算法研究

发布时间：2017-09-17 04:13

  本文关键词：面向复杂网络的社区发现算法研究

  更多相关文章： 复杂网络 社区相似 层次聚类 k-means算法 社区发现 重要结点评估

【摘要】：网络是一种呈现复杂系统的有效方法。复杂网络（complex network）描述了一系列的自然和社会系统，例如信息系统、生物系统、社会系统、交通系统、航空网络、电力系统以及一些合作性质的网络系统等。自然界中大量真的网络都具有其独特的结构特点，系统内部个元组之间的联系以及相互作用，可以抽象为具有一定组织关系的小型网络，这种小型网络承担着系统的功能，并且能够具体的体现网络中的组织关系特点。这些小型网络就定义为复杂网络的社区结构（community）。 复杂网络中社区发现的研究可以揭示复杂网络结构特点和一些网络现象的成因。将复杂网络中的个体划分为不同的社区结构进行研究，可以有针对性的对复杂网络的某些特征进行研究，也可以减少对复杂网络某些特征研究的工作量。因此，复杂网络的社区发现方法的研究具有巨大的社会、经济和科研价值。 本文针对复杂网络，，首先，基于Louvain社区发现算法的启发，提出了基于社区相似的层次聚类社区发现算法（CSHC）。算法初始阶段将每一个结点作为一个社区，然后提出社区之间的相似性和模块度最大增益之间的一个合并系数，决定社区是否合并，迭代算法的停止条件为达到需要划分的社区个数k为止。CSHC算法分别在Karate ClubNetwork数据集和American College Football数据集上得到了很好的社区划分，其纯度与模块度对以往的社区发现算法都有一定的提高。并且CSHC算法可以在很少次的合并达到社区划分结果，与以往社区发现算法相比其效率大大增加。其次，本文提出了基于重要结点的社区发现算法（INC），首先依据模块度最大化理论，计算出网络的模块度矩阵B的最大k特征向量矩阵S。然后，提出聚类中心方法用于求出k个社团的重要结点作为k聚类中心。利用欧几里得距离计算每一个结点到k个聚类中心的距离，将结点分配到距离聚类中心最近的社区中。最后，对网络应用k-means方法进行迭代计算，最终得到k个社区的划分。INC算法分别在Karate Club Network数据集和American CollegeFootball数据集上得到了很好的社区划分，并且可以有效的发现潜在社区，其纯度与模块度对以往的社区发现算法都有一定的提高。并且INC算法可以在很少次的迭代达到社区划分结果，与以往社区发现算法相比其效率有很大提高。 复杂网络内部的各个社区结构是复杂网络结构特征的具体承担者和复杂网络属性特征的具体体现者。另外，在系统内部，并不是所有的元组个体对复杂网络的特征和结构都起到一样的作用，一些元组会扮演更为重要角色，这种元组被称为网络中的关键结点。因此，本文提出了基于社区的重要结点评定方法，既充分的考虑到一个结点与其他所有结点之间的紧密程度，又充分考虑到结点在社区中的贡献，提出ICC算法对网络中结点进行重要性的评定。ICC算法分别在Karate Club Network数据集和AmericanCollege Football数据集进行实验验证，并与经典的中心性计算方法进行对比。实验结果表明，ICC算法很好的将社区中重要结点对网络的实际意义凸现出来，对网络中重要结点的评价有了新的视角，并且对网络的实际意义做出很好的评判。 现代科学的网络为复杂网络的理解带来了重大的发展。复杂网络中社区发现与社区发现算法的研究对关键问题的讨论、集群的意义以及对真实网络的描述具有重要的意义。由于复杂网络中每个结点的重要程度不同，对复杂网络中的属性贡献就不同。因此，挖掘复杂网络中的关键结点，具有巨大的实用价值。
【关键词】：复杂网络 社区相似 层次聚类 k-means算法 社区发现 重要结点评估
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要4-6
• Abstract6-11
• 第1章 绪论11-17
• 1.1 研究背景与研究意义11-13
• 1.2 国内外研究现状13-15
• 1.3 本文主要工作15-16
• 1.4 本文组织架构16-17
• 第2章 复杂网络与社区发现17-29
• 2.1 复杂网络17-20
• 2.1.1 网络与表示17-18
• 2.1.2 复杂网络的属性18-20
• 2.2 社区发现的研究方法20-23
• 2.2.1 基于结点为中心的社区发现21
• 2.2.2 基于群组为中心的社区发现21-22
• 2.2.3 基于网络为中心的社区发现22
• 2.2.4 基于层次为中心的社区发现22-23
• 2.3 社区发现经典算法23-28
• 2.3.1 谱聚类23-26
• 2.3.2 潜在空间模型26-28
• 2.4 本章小结28-29
• 第3章 基于社区相似的层次聚类社区发现算法29-42
• 3.1 Louvain 社区发现算法简介29
• 3.2 基于社区相似的层次聚类社区发现算法（CSHC）29-34
• 3.2.1 相关问题探究29-33
• 3.2.2 CSHC 社区发现算法33-34
• 3.3 实验评估标准34-35
• 3.3.1 纯度34
• 3.3.2 模块度34-35
• 3.4 实验结果及分析35-41
• 3.4.1 Karate Club Network 数据集35-37
• 3.4.2 American College Football 数据集37-41
• 3.5 实验总结41
• 3.6 本章小结41-42
• 第4章 基于重要结点的社区发现算法42-54
• 4.1 相关问题探究42-45
• 4.1.1 模块度最大化42-43
• 4.1.2 K-means 方法介绍43-44
• 4.1.3 欧几里得度量44
• 4.1.4 聚类中心44-45
• 4.2 基于重要结点的社区发现算法（INC）45-46
• 4.3 实验结果及分析46-52
• 4.3.1 Karate Club Network 数据集47-48
• 4.3.2 American College Football 数据集48-52
• 4.4 实验总结52
• 4.5 本章小结52-54
• 第5章 基于社区的重要结点评定方法54-58
• 5.1 中心性简介54-55
• 5.1.1 度中心54
• 5.1.2 紧密度中心54-55
• 5.2 基于社区的重要结点评估算法（ICC）55-56
• 5.3 实验结果及分析56-57
• 5.3.1 Karate Club Network 数据集56-57
• 5.3.2 American College Football 数据集57
• 5.4 本章小结57-58
• 第6章 总结与展望58-60
• 6.1 总结58
• 6.2 展望58-60
• 参考文献60-63
• 作者简介及在学期间所取得的科研成果63-64
• 致谢64

【共引文献】

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

1 秦洋;王立宏;武栓虎;宋宜斌;;基于拉普拉斯矩阵的DNA序列集相似性分析[J];北京交通大学学报;2009年06期

2 杨华;聂玉超;张洪斌;樊瑛;;基于复杂网络的快递网络性质分析[J];北京师范大学学报(自然科学版);2009年01期

3 牟向伟;陈燕;杨明;李桃迎;;班轮航运网络拓扑特性[J];大连海事大学学报;2009年02期

4 莫辉辉;王姣娥;金凤君;;交通运输网络的复杂性研究[J];地理科学进展;2008年06期

5 田炜;邓贵仕;武佩剑;车文娇;;世界航运网络复杂性分析[J];大连理工大学学报;2007年04期

6 王建伟;荣莉莉;郭天柱;;一种基于局部特征的网络节点重要性度量方法[J];大连理工大学学报;2010年05期

7 王姣娥;莫辉辉;金凤君;;中国航空网络空间结构的复杂性[J];地理学报;2009年08期

8 武文杰;董正斌;张文忠;金凤君;马修军;谢昆青;;中国城市空间关联网络结构的时空演变[J];地理学报;2011年04期

9 王茂军;田丽英;杨雪春;;山东省城镇网络结构与城镇网络角色识别——基于民国时期土货/洋货流通网络的分析[J];地理研究;2011年09期

10 徐天顺;;谱聚类算法研究[J];电脑知识与技术;2012年16期

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

1 ;Pinning Complex Dynamical Networks with Local Betweeness Centrality Information[A];中国自动化学会控制理论专业委员会C卷[C];2011年

2 王小磊;张瑾;许洪波;;基于交互增强原理的多文档自动文摘算法[A];第四届全国学生计算语言学研讨会会议论文集[C];2008年

3 于连飞;吕国栋;修保新;张维明;范常俊;;基于复杂网络的C2组织描述与建模综述[A];2014第二届中国指挥控制大会论文集（上）[C];2014年

4 林敏;张传海;;基于数学手段的复杂系统仿真方法研究概述[A];系统仿真技术及其应用学术论文集（第15卷）[C];2014年

5 Shengfu Zhou;Kun Yue;Qiyu Fang;Yunlei Zhu;Weiyi Liu;;An Efficient Algorithm for Influence Maximization under Linear Threshold Model[A];第26届中国控制与决策会议论文集[C];2014年

6 毕娟;秦志光;黄嘉;;Dynamic Topic Model for Detecting Community in Social Networks[A];第十一届全国博士生学术年会——信息技术与安全专题论文集[C];2013年

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

1 徐森;文本聚类集成关键技术研究[D];哈尔滨工程大学;2010年

2 宋军;水交换模型的理论方法及应用研究[D];中国海洋大学;2010年

3 胡进;复杂网络上的博弈及其在通信网络资源管理中的应用[D];华中科技大学;2010年

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

5 杨树忠;复杂网络中的社团检测问题研究[D];北京交通大学;2009年

6 陈伟;基于时序文本挖掘的新闻内容理解与推荐技术研究[D];浙江大学;2010年

7 钱鹏江;大规模数据集聚类方法研究及应用[D];江南大学;2011年

8 王伟;铁路网抗毁性分析与研究[D];北京交通大学;2011年

9 吕绍高;统计学习中回归与正则化谱聚类算法的研究[D];中国科学技术大学;2011年

10 朱天;社会网络中节点角色以及群体演化研究[D];北京邮电大学;2011年

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

1 李静伟;基于共享近邻的自适应谱聚类算法[D];大连理工大学;2010年

2 孙玉侠;数据挖掘中的谱聚类算法研究[D];中国海洋大学;2010年

3 温程;并行聚类算法在MapReduce上的实现[D];浙江大学;2011年

4 毛菥;基于文本分析技术的新闻阅读平台的研究与实现[D];浙江大学;2011年

5 王学勇;复杂网络演化与软件平台研究[D];西安电子科技大学;2011年

6 张汉珍;谱划分算法中特征向量选取方法的研究[D];西安电子科技大学;2010年

7 王蓓金;蛋白质网络模块分解的密度聚类算法研究[D];西安电子科技大学;2010年

8 雷玲;离散正则化方法在草场检测上的研究与应用[D];吉林大学;2011年

9 钱新宇;基于实例推理的虚拟装配序列规划研究[D];大连海事大学;2011年

10 黄旭;群智能优化算法及其在PPI网络中的应用研究[D];陕西师范大学;2011年

本文编号：867188