复杂网络重叠社区结构发现的算法研究与实现

发布时间：2017-10-11 16:35

  本文关键词：复杂网络重叠社区结构发现的算法研究与实现

  更多相关文章： 复杂网络 社区划分 重叠节点 基因片段 模块度 演化算法

【摘要】：复杂网络可以用来描述交通网、互联网、社交关系网络、神经网络以及科研合作网络等现实网络。随着对复杂网络研究的深入,研究者们发现社区结构存在于很多的现实网络中,并且现实生活中很多社区之间存在相互关联和彼此重叠。基于此我们主要对复杂网络中社区的发现及划分进行研究。复杂网络是由节点和边构成,网络中的节点代表不同实体,可以同时属于多个社区;边表示实体之间的某种关系。在划分社区时可根据节点邻居属性划分其所属社区,本文基于节点邻居的多样性及节点选取的随机性主要做了以下工作:1)提出复杂网络重叠社区结构划分的个体从众演化算法ICEA(Individual Conformity Evolutionary Algorithm)。算法根据社区节点的从众和变异属性,使得在划分社区时根据节点的邻居不同从而产生不同的社区划分结果,通过比较模块度找到比较好的社区划分,在社区结构确定的基础上我们使用陈俊宇等人的邻居投票机制LM-NV(Louvain Method with Neighbor Voting)对社区的边界节点进行判断,判断其是否为重叠节点,从而完成复杂网络重叠社区的划分工作。2)提出一种基因片段覆盖算法GFCA(Gene Fragment Covering Algorithm),基本思想是将由节点邻居组成的个体,随机选取其它个体的一个基因片段覆盖到当前个体的相应位置上,若覆盖后,模块度有改善,则选择覆盖后的个体作为当前个体;否则保留原来的个体。在真实网络上进行实验,结果表明此算法具有一定的优势及实际可用性。为了验证所提算法ICEA和GFCA社区划分的有效性,我们选取常用于测试复杂网络划分算法的三个真实数据集Zachary Karate club、Dolphin Social network以及American College football对两个算法进行了测试,并将我们的算法与Newman的GN算法和快速算法FN、基于改进的K-means模糊聚类的网络社区结构划分算法NKFCM以及基于粒子群算法的模糊社区结构划分算法PFCM在划分社区的模块度、划分社区个数以及迭代次数几个方面进行对比分析。实验结果表明本文所提算法ICEA和GFCA在运行时间和划分结果等方面都优于典型算法。
【关键词】：复杂网络 社区划分 重叠节点 基因片段 模块度 演化算法
【学位授予单位】：闽南师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 摘要5-6
• ABSTRACT6-10
• 第1章 绪论10-16
• 1.1 研究背景与意义10-11
• 1.2 复杂网络社区发现国内外研究现状11-13
• 1.3 本文研究内容13-14
• 1.4 本文结构及安排14-16
• 第2章 复杂网络社区发现相关研究16-32
• 2.1 复杂网络与图的表示16-18
• 2.2 网络社区的定义18-19
• 2.3 重叠社区的定义及特点19-20
• 2.4 模块度函数20-24
• 2.5 复杂网络社区结构发现算法24-30
• 2.5.1 图论方法24
• 2.5.2 社会学方法24-26
• 2.5.3 CPM算法26-27
• 2.5.4 EAGLE算法27-29
• 2.5.5 LFK算法29-30
• 2.6 本章小结30-32
• 第3章 复杂网络重叠社区发现演化算法ICEA32-38
• 3.1 基本概念介绍32
• 3.2 个体编码32-34
• 3.3 ICEA算法34-35
• 3.4 邻居投票机制的重叠社区发现算法35-37
• 3.5 本章小结37-38
• 第4章 基因片段覆盖算法GFCA38-42
• 4.1 基因片段38
• 4.2 GFCA算法描述38-41
• 4.3 本章小结41-42
• 第5章 实验结果及分析42-50
• 5.1 真实数据集42-45
• 5.2 实验数据与结果45-49
• 5.3 本章小结49-50
• 第6章 总结和展望50-52
• 6.1 总结50-51
• 6.2 展望51-52
• 参考文献52-56
• 致谢56-58
• 攻读学位期间取得的科研成果清单58

【相似文献】

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

1 智源;行飞;;复杂网络社区结构问题综述[J];阴山学刊(自然科学);2011年03期

2 王林;戴冠中;赵焕成;;一种新的评价社区结构的模块度研究[J];计算机工程;2010年14期

3 韩瑞凯;孟嗣仪;刘云;郭英慧;张彦超;;基于兴趣相似度的社区结构发现算法研究[J];铁路计算机应用;2010年10期

4 刘旭;易东云;;基于保守合并策略的复杂网络社区结构发现[J];复杂系统与复杂性科学;2011年04期

5 黄发良;肖南峰;;用于网络重叠社区发现的粗糙谱聚类算法[J];小型微型计算机系统;2012年02期

6 马瑞新;邓贵仕;王晓;;启发式动态社区挖掘算法研究与实现[J];大连理工大学学报;2012年02期

7 梁沙沙;;复杂网络重叠社区结构发现算法研究[J];阴山学刊(自然科学);2013年02期

8 刘大有;金弟;何东晓;黄晶;杨建宁;杨博;;复杂网络社区挖掘综述[J];计算机研究与发展;2013年10期

9 时京晶;;三种经典复杂网络社区结构划分算法研究[J];电脑与信息技术;2011年04期

10 黄发良;肖南峰;;基于线图与PSO的网络重叠社区发现[J];自动化学报;2011年09期

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

1 刁元波;李梦龙;文志宁;印家健;郑波;;人类细胞信号网络社区结构分析[A];第九届全国计算（机）化学学术会议论文摘要集[C];2007年

2 刘欣;李德毅;李兵;王树良;陶志伟;;复杂网络社区发现研究[A];2006全国复杂网络学术会议论文集[C];2006年

3 单波;姜守旭;张硕;高宏;李建中;;IC:动态社会关系网络社区结构的增量识别算法[A];第26届中国数据库学术会议论文集（A辑）[C];2009年

中国重要报纸全文数据库 前1条

1 记者 熊明 实习生 李瑞莹;度假区不断创新社区结构[N];云南日报;2013年

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

1 闵磊;复杂网络社区发现算法研究[D];华中师范大学;2015年

2 蔡清;基于群体智能优化的大数据复杂网络结构分析[D];西安电子科技大学;2015年

3 陈毅;基于统计推理的复杂网络社区结构分析[D];哈尔滨工业大学;2016年

4 杜楠;复杂网络中社区结构发现算法研究及建模[D];北京邮电大学;2009年

5 李一啸;基于复杂网络和演化博弈理论的社会[D];浙江大学;2010年

6 韩院彬;Web服务网络分析和社区发现研究[D];天津大学;2014年

7 谢辉;基于复杂网络的若干动态机制研究[D];西安电子科技大学;2013年

8 任薇;基于微博的社会网络特征研究[D];西南大学;2014年

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

1 贺成龙;复杂网络中的社区发现算法研究[D];解放军信息工程大学;2015年

2 贾娜;基于矩阵分解的重叠社区探测研究[D];吉林大学;2016年

3 李青云;多阶信息模型及推荐技术研究[D];北京理工大学;2015年

4 万云;基于模块度最大化的社区发现算法的研究[D];燕山大学;2016年

5 邹杰;日照滨海民俗村社区结构与旅游发展互动研究[D];曲阜师范大学;2016年

6 王焕杰;社会网络数据发布中有效保护社区结构的匿名方法研究[D];广西师范大学;2016年

7 王洪珏;复杂网络节点相似性研究及其应用[D];华北电力大学;2016年

8 纪开祝;复杂网络重叠社区结构发现的算法研究与实现[D];闽南师范大学;2016年

9 戴飞飞;基于进化算法的复杂网络社区结构发现[D];电子科技大学;2008年

10 王熙;复杂网络中的层次重叠社区发现及可视化[D];北京交通大学;2010年

，

本文编号：1013649