基于局部扩充的重叠社区发现算法研究和改进

发布时间：2017-09-01 05:29

  本文关键词：基于局部扩充的重叠社区发现算法研究和改进

  更多相关文章： 重叠社区发现 节点影响力 局部优化 并行计算

【摘要】：随着网络的飞速发展以及社交媒体的广泛应用,使得人与人之间的联系尤为密切。这种错综复杂的关系组成一个庞大的社交网络,因此吸引了众多学者致力于复杂网络的研究,从复杂网络中发现并抽取其中的模块结构这就是所谓的社区发现。以前学者都致力于非重叠网络的研究,然后这在现实生活中是不实用的,由此引发了大家对重叠网络的研究,近几年来取得了不小的进展。本文即针对重叠社区发现算法进行改进。重叠社区即网络中包含的节点不止属于一个社区,能够有效地识别这些重叠节点是本文算法研究的重点。比较有名的算法有LFM算法和GCE算法,它们都是利用网络的局部信息,对单个种子节点进行成长的理念。本文鉴于局部扩充的核心思想,对种子选择、社区扩充剪枝、相似度判断、并行化模型等提出了自己的改进方案。(1)由于LFM算法选择种子节点过于随机,影响算法准确性;而GCE算法需要找到网络图的所有团结构,影响算法效率;本文采取折中策略,通过删除网络中影响力较小的节点来得到核心结构。主要基于度数较多的点在社团结构中是比较重要的节点,如果一个节点的影响力较大那么它邻居节点也是重要的。(2)LFM算法和GCE算法在对一个种子进行扩充时并未对其候选集进行判断,这严重影响了算法性能。本文对扩充过程进行了细致的推导和严格的数学证明,对社区扩充过程产生的候选集进行了剪枝处理,以进一步的提升算法效率。(3)种子扩充后生成的社区存在一定的相似性,如果不加以判断会对结果准确性产生影响。本文提到的相似度度量公式除了考虑社区节点集合还考虑了社区邻居节点的影响,更具有实际意义。(4)对扩充过程进行并行化处理。并行化是提高算法性能的一个很重要的手段,通过分析本文算法过程,可以方便的解除数据依赖,并且引入生产者消费者模型来解决线程通信问题。由于硬件环境限制实验在多核CPU上进行操作。(5)通过应用到实际网络图中验证了种子选择策略在一定范围之内的可行性,以及综合改进算法ISA对于社区发现的准确性以及时间损耗。准确性用NMI(标准互信息量)进行度量,发现本文算法对于混淆参数以及社区结构敏感,总体性能优于LFM算法,且不逊于GCE算法。
【关键词】：重叠社区发现 节点影响力 局部优化 并行计算
【学位授予单位】：重庆大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5;TP301.6
【目录】：

• 中文摘要3-4
• 英文摘要4-8
• 1 绪论8-13
• 1.1 研究背景8-9
• 1.2 国内外研究现状9-12
• 1.3 本文的主要研究内容和组织结构12
• 1.4 本章小结12-13
• 2 复杂网络社区发现基本理论13-24
• 2.1 复杂网络概述13
• 2.2 社区的概念13-17
• 2.2.1 社区的定义14-15
• 2.2.2 社区的评价标准15-17
• 2.3 非重叠社区发现算法17-20
• 2.3.1 划分算法17-18
• 2.3.2 基于模块度的算法18-19
• 2.3.3 谱聚类算法19
• 2.3.4 动态算法19-20
• 2.4 重叠社区发现算法20-22
• 2.4.1 基于团过滤算法20-21
• 2.4.2 基于连接划分算法21
• 2.4.3 基于局部扩充算法21-22
• 2.4.4 基于模糊检测算法22
• 2.4.5 基于代理的动态检测算法22
• 2.5 本章小结22-24
• 3 基于局部扩充的重叠社区发现算法24-29
• 3.1 基于局部扩充优化的重叠社区发现算法简介24
• 3.2 常见的局部扩充优化的重叠社区发现算法24-28
• 3.2.1 LFM算法24-26
• 3.2.2 GCE算法26-28
• 3.3 本章小结28-29
• 4 基于局部扩充的重叠社区发现算法改进29-43
• 4.1 种子选择的改进29-33
• 4.1.1 寻找核心节点集合29-32
• 4.1.2 形成仿团集32-33
• 4.1.3 种子集形成算法流程33
• 4.2 局部优化质量函数的优化33-36
• 4.3 相似性度量36-37
• 4.4 并行化改进37-40
• 4.4.1 并行化理论概述37-38
• 4.4.2 并行化分析38-40
• 4.5 算法综合描述40-42
• 4.6 本章小结42-43
• 5 实验结果及分析43-53
• 5.1 实验准确性评价标准43
• 5.2 实验数据源43-44
• 5.3 种子选择算法实验对比44-46
• 5.4 综合算法实验对比46-52
• 5.4.1 NMI准确性实验对比46-50
• 5.4.2 速度指标的实验对比50-52
• 5.5 本章小结52-53
• 6 总结与展望53-55
• 6.1 本文总结53-54
• 6.2 研究展望54-55
• 致谢55-56
• 参考文献56-59
• 附录59
• A. 作者在攻读硕士学位期间发表的论文59

【相似文献】

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

1 邹汪平;;一种基于网络安全控制的蜂群算法应用研究[J];吉林师范大学学报(自然科学版);2013年04期

2 郭毅可;韩锐;;云计算中的弹性算法:概要和展望[J];上海大学学报(自然科学版);2013年01期

3 刘江华;戴新喜;白似雪;;基于模式矩阵的P_Matrix算法[J];南昌大学学报(理科版);2007年05期

4 胡俊鹏;;基于双向选择的蚁群相遇算法的优化[J];湖北民族学院学报(自然科学版);2013年01期

5 张丽;;关联规则挖掘算法的研究[J];赤峰学院学报(自然科学版);2013年02期

6 吴秋峰;尹海东;孟翔燕;;基于和积和最大积的信念传播算法的收敛性分析[J];数学的实践与认识;2011年09期

7 赵吉东;;蚁群算法的改进策略研究[J];中国科技信息;2012年12期

8 胡森森;周贤善;;一种改进蚁群算法的研究[J];长江大学学报(自科版);2006年10期

9 王恒娜;赵晓静;;基于属性覆盖的关联规则挖掘算法[J];安庆师范学院学报(自然科学版);2007年03期

10 曹建军;刁兴春;李凯齐;邵衍振;;基于进化强度的蚁群算法过程性能评价[J];解放军理工大学学报(自然科学版);2013年01期

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

1 黄纪武;毛泽华;李松涛;张锦雄;;SPMD并行查找算法的MPI实现[A];广西计算机学会——2004年学术年会论文集[C];2004年

2 黄纪武;毛泽华;李松涛;张锦雄;;SPMD并行查找算法的MPI实现[A];广西计算机学会2004年学术年会论文集[C];2004年

3 符丽锦;覃华;邓海;孙欣;;一种改进的Apriori算法的研究[A];广西计算机学会2012年学术年会论文集[C];2012年

4 王东锋;王军民;陈英武;;模糊定性仿真理论研究与算法实现[A];'2000系统仿真技术及其应用学术交流会论文集[C];2000年

5 赵唯;;晶粒度评级的改进算法[A];中国图象图形科学技术新进展——第九届全国图象图形科技大会论文集[C];1998年

6 刘启文;;可扩展的图形学算法演示系统的研究[A];’2004计算机应用技术交流会议论文集[C];2004年

7 佘智;蒋泰;朱延生;;基于Type C协议的防冲突改进算法[A];广西计算机学会25周年纪念会暨2011年学术年会论文集[C];2011年

8 朱绍文;赵培;朱秋云;;基于pSPADE并行挖掘序列算法的研究[A];2003年中国智能自动化会议论文集（下册）[C];2003年

9 杨霞;;新的基于启发式蚁群算法的QoS路由算法[A];广西计算机学会2009年年会论文集[C];2009年

10 陈黎飞;姜青山;董槐林;;基于图形轮廓的快速聚类算法[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年

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

1 钟永腾;基于近场MUSIC算法的复合材料结构健康监测研究[D];南京航空航天大学;2014年

2 刘燕;入侵杂草优化算法在阵列天线综合中的应用[D];西安电子科技大学;2015年

3 苗义烽;突发事件下的列车运行调度模型与算法研究[D];中国铁道科学研究院;2015年

4 杨玉婷;头脑风暴优化算法与基于视频的非接触式运动定量分析方法研究[D];浙江大学;2015年

5 刘杰;全局优化问题的几类新算法[D];西安电子科技大学;2015年

6 柏静;基于多种混合策略的人工蜂群算法改进研究[D];山东师范大学;2016年

7 孔翔宇;几类优化问题的人工蜂群算法[D];西安电子科技大学;2016年

8 匡立;分形网络的理论、算法及应用研究[D];武汉大学;2015年

9 单美静;求解非线性实代数系统的混合算法研究[D];华东师范大学;2008年

10 邱剑锋;人工蜂群算法的改进方法与收敛性理论的研究[D];安徽大学;2014年

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

1 安世勇;命题逻辑中随机3-SAT问题算法研究[D];西南交通大学;2015年

2 毕晓庆;油气探矿权竞争性出让系统设计与实现[D];中国地质大学(北京);2015年

3 王明明;铁路大机与线路固定设施间距检测算法研究[D];西南交通大学;2015年

4 李静;基于视频图像序列的运动目标检测与跟踪算法研究[D];宁夏大学;2015年

5 刘贝玲;基于天地图的租房平台开发及其关键技术研究[D];西南交通大学;2015年

6 曹海锋;IDS中串匹配臭算法并行优化研究[D];西安建筑科技大学;2015年

7 周攀;基于蚁群算法的山区高速铁路隧道火灾应急疏散最优路径研究[D];西南交通大学;2015年

8 张路奇;基于改进蚁群算法的WSN路由协议的研究[D];中国地质大学(北京);2015年

9 王晓晨;入侵杂草优化算法的应用与改进[D];长安大学;2015年

10 信琴琴;手势控制和识别算法研究[D];闽南师范大学;2015年

，

本文编号：770244