基于矩阵分解的重叠社区探测研究

发布时间：2017-05-10 02:05

  本文关键词：基于矩阵分解的重叠社区探测研究，由笔耕文化传播整理发布。

【摘要】：复杂网络是对现实世界系统的抽象。现实世界的个体被抽象为复杂网络的节点,个体之间的联系被抽象为按某种规则连接的边。经过大量实验证明,复杂网络与随机网络不同,具有小世界性、无标度性和结构性。复杂网络的节点成簇状分布,每一个簇成为一个社区。社区是由具有相同背景或者相似属性的节点组成。社区结构普遍存在于现实世界的复杂网络中,例如科学家协作网、交通网络、社交网络、神经网络和蛋白质网络等等。社区结构是复杂网络的重要拓扑属性,研究社区结构有助于揭示复杂网络潜在的信息,因此吸引了各个领域的越来越多的学者专家的研究,成为新的研究热点。目前社区发现研究取得了丰硕的成果,据不完全统计将近一百多种社区发现算法被提出。根据社区是否重叠社区发现算法可以分为重叠社区发现算法和非重叠社区发现算法。非重叠社区发现算法中一个节点属于仅能够属于一个社区。在真实的复杂网络中普遍存在一个节点被多个社区共享现象,即社区之间存在重叠,例如在蛋白质网络中,一种蛋白质能够承担多种功能;在社交网络中,一个人可以属于学校、同事、朋友、家人等多个社区。由于重叠社区更贴近真实的复杂网络结构,因此重叠社区发现成为复杂网络领域新的研究热点。自2005年Palla等人在PANS会议上首次提出了社区重叠现象,重叠社区发现研究成果如雨后春笋般涌现。重叠社区发现算法按照网络划分结果可以分为模糊重叠社区发现算法和非模糊重叠发现算法。非模糊重叠发现算法,例如CPM算法、LC算法等,能够明确划分网络的社区结构,但不能评估节点与社区的隶属强度。模糊重叠社区发现算法,例如FCM(fuzzy c-means)算法、SPAEM算法等,能够提供评估节点与社区的隶属强度,却不能够明确划分社区结构。2013年,Zhongyuan Zhang等人提出了SBMF模型,该模型能够结合两类算法的优点,弥补两类算法的不足。SBMF模型不仅能够明确划分网络的社区结构,还能提供节点与社区的隶属强度。并且,SBMF模型还能判别重叠节点和离群节点。但是,SBMF模型没有考虑重叠节点与多个社区相连,使得重叠节点与各个社区的隶属强度降低,导致潜在的重叠节点被误划分成为离群节点。为弥补SBMF模型这一缺陷,我们提出了基于遗传算法的拓展矩阵分解模型(ESBMF)。改进的ESBMF模型,采用遗传算法计算节点与社区的隶属强度的最优修正值,来明确网络的社区结构。评价社区划分结果的优劣是社区发现的重要步骤。本文采用拓展模块度EQ作为评价指标。EQ主要用来衡量社区结构模块性高低,EQ值越大社区结构模块性越高。为衡量ESBMF模型的性能,本文采用四个经典真实数据集作为实验数据集,包括空手道社交网络数据集、海豚网络数据集、美国政治图书数据集和美国橄榄球联盟数据集,并与经典的LC算法和SBMF模型进行比较,实验结果证明,ESBMF模型划分的网络结构与真实的网络结构更贴近,模块性更高。
【关键词】：重叠社区发现 矩阵分解 评价指标 遗传算法
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5;TP18
【目录】：

• 摘要4-6
• Abstract6-10
• 第1章 绪论10-16
• 1.1 研究背景及研究意义10-12
• 1.2 国内外研究现状12-14
• 1.3 本文工作14-15
• 1.4 内容结构与安排15-16
• 第2章 社区发现算法概述16-26
• 2.1 相关知识介绍16-19
• 2.1.1 介数16
• 2.1.2 平均路径长度16-17
• 2.1.3 聚集系数17
• 2.1.4 Q模块度17-18
• 2.1.5 分割密度18-19
• 2.2 非重叠社区发现算法19-23
• 2.2.1 基于优化的非重叠社区发现算法19-22
• 2.2.2 基于优化的社区发现算法22-23
• 2.3 重叠社区发现算法23-25
• 2.3.1 派系过滤算法23-24
• 2.3.2 连接聚类算法24
• 2.3.3 基于局部信息扩散算法24-25
• 2.4 本章小结25-26
• 第3章 非负矩阵分解模型26-31
• 3.1 SNMF算法26-28
• 3.1.1 非负矩阵分解算法思想26-27
• 3.1.2 SNMF算法27-28
• 3.2 SBMF算法28-29
• 3.3 改进的PD评价指标29-30
• 3.4 本章小结30-31
• 第4章 基于遗传算法的矩阵分解模型31-37
• 4.1 遗传算法31-34
• 4.2 改进的SBMF模型34-35
• 4.3 拓展模块度35-36
• 4.4 本章小结36-37
• 第5章 实验结果分析37-46
• 5.1 实验数据集37-38
• 5.2 实验评估指标38
• 5.3 实验结果38-45
• 5.3.1 空手道数据集39-40
• 5.3.2 海豚社会网络数据集40-42
• 5.3.3 美国政治图书数据集42-43
• 5.3.4 美国橄榄球联盟数据集43-45
• 5.4 本章小结45-46
• 第6章 总结与展望46-47
• 6.1 总结46
• 6.2 展望46-47
• 参考文献47-50
• 作者简介及科研成果50-51
• 致谢51

【相似文献】

中国期刊全文数据库 前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年

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

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

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

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

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

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

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

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

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

1 王童童;社区框架与隐藏社区的挖掘[D];山东建筑大学;2015年

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

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

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

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

6 徐李恒;复杂网络社区发现方法研究[D];太原理工大学;2011年

7 李兆南;基于距离相似度的复杂网络社区挖掘方法[D];吉林大学;2011年

8 商源纯;复杂网络中的重叠社区发现算法研究[D];北京交通大学;2011年

9 吴婷婷;基于极大度数节点的复杂网络社区层次结构发现研究[D];华南理工大学;2011年

10 王亮;基于局部聚类的复杂网络社区发现算法研究[D];大连理工大学;2011年

  本文关键词：基于矩阵分解的重叠社区探测研究，，由笔耕文化传播整理发布。

本文编号：353760