基于模糊聚类的社团划分算法研究

发布时间：2017-10-10 14:28

  本文关键词：基于模糊聚类的社团划分算法研究

  更多相关文章： 复杂网络 社团划分 隶属函数 模糊等价关系 等价类

【摘要】：社团结构作为复杂网络的重要特性之一,对复杂网络进行社团划分,则可以通过对几个小社团的研究,以“分而治之”的方式对整个系统的模块、功能及演化进行研究,大大降低了直接对庞大的复杂系统进行研究的复杂性,还进一步加深了对复杂系统的组织原则、拓扑结构与动力学特性的理解。目前已有的复杂网络的社团划分算法中,大部分的算法主要是非重叠社团划分算法,划分结果显示为网络被划分为若干个互相独立的社团,社团与社团之间没有重叠节点。但是在某些实际网络中,网络中存在具有多个社团属性的节点即重叠节点,社团之间是存在一定关联的,我们可以根据重叠节点进而推断社团之间的关联程度,对于动态的网络,根据重叠节点还能对社区的下一步变化进行预测,因此,重叠节点的发现有特殊的意义和研究价值。本文在对已有的经典社团划分算法的研究基础上,提出了一种基于模糊聚类的社团划分算法,可以同时应用于非重叠社团和重叠社团结构的网络的社团划分。基于模糊聚类的社团划分算法是一种启发式算法,它的启发式规则:将节点作为模糊聚类算法中用于聚类的样本,应用模糊聚类算法后,属于同一等价类的样本对应的节点应属于相同的社团。在传统的模糊聚类算法中,隶属函数的值反映的是样本之间的模糊关系~R的程度即样本间的相似程度。将传统的模糊聚类算法应用到社团划分中,将节点作为聚类样本,本文算法的具体工作如下:1、对传统的共享邻居数的定义进行了改进,通过改进后的共享邻居数定义表示节点间的相似程度并提出了一种基于节点间共享邻居数的隶属函数。2、对于网络中存在重叠节点的情况,模糊聚类算法所得的划分结果中,针对少数不属于任何等价类的节点即重叠节点候选解,提出了重叠节点的判别准则,检测出候选解中的重叠节点。本文提出的算法的时间复杂度为22(log)nO n。在GN经典人造网和几个实际网络上进行测试,对社团大小规模已知且不存在重叠社团的GN经典人造网的划分结果符合真实情况,算法在实际网络的验证上,通过与其它算法的划分结果进行比较,得到的模块度Q值较高,并且能够更好的检测出实际网络中的重叠节点。
【关键词】：复杂网络 社团划分 隶属函数 模糊等价关系 等价类
【学位授予单位】：太原理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5;O159
【目录】：

• 摘要4-6
• ABSTRACT6-11
• 第一章 绪论11-21
• 1.1 研究背景和研究意义11-14
• 1.2 国内外的研究现状14-19
• 1.3 本文的主要工作19
• 1.4 论文组织结构19-21
• 第二章 相关工作基础21-31
• 2.1 相关定义及概念21-27
• 2.1.1 复杂网络的表示方法21-24
• 2.1.2 聚类系数24-25
• 2.1.3 社团的定义25-27
• 2.2 社团划分结果评价指标27-30
• 2.2.1 模块度27-29
• 2.2.2 标准化互信息29-30
• 2.3 本章小结30-31
• 第三章 经典的社团划分算法31-45
• 3.1 非重叠社团划分算法31-41
• 3.1.1 Kernighan-Lin算法31-33
• 3.1.2 谱平分算法33-36
• 3.1.3 GN算法及其改进算法36-40
• 3.1.4 Newman快速算法40-41
• 3.2 重叠社团的划分算法41-43
• 3.3 本章小结43-45
• 第四章 基于模糊聚类的社团划分算法45-59
• 4.1 模糊聚类算法的相关基础45-47
• 4.1.1 模糊聚类算法的相关理论基础45-46
• 4.1.2 模糊聚类算法介绍46-47
• 4.2 基于节点间共享邻居数的隶属函数47-49
• 4.2.1 相关定义及其物理意义47-49
• 4.2.2 相关数学证明49
• 4.3 重叠节点的判别准则49-52
• 4.4 算法的主要工作52-53
• 4.5 算法的具体实现步骤53-56
• 4.6 算法的时间复杂度分析56-57
• 4.7 本章小结57-59
• 第五章 实验与分析59-69
• 5.1 实验数据集59-61
• 5.1.1 人工网络数据集59-60
• 5.1.2 实际网络数据集60-61
• 5.2 实验分析61-67
• 5.2.1 评价指标的采用依据61-62
• 5.2.2 算法的实验结果比较分析62-67
• 5.3 本章小结67-69
• 第六章 总结与展望69-71
• 6.1 总结69-70
• 6.2 展望70-71
• 参考文献71-75
• 致谢75-77
• 攻读硕士学位期间发表的学术论文77

【相似文献】

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

1 冷明平;孙凌宇;郭恺强;边计年;朱平;;赋权超图划分算法的电路划分实验比较研究[J];计算机工程与应用;2012年16期

2 许金凤;董一鸿;王诗懿;何贤芒;陈华辉;;大规模图数据划分算法综述[J];电信科学;2014年07期

3 李莉杰;陈端兵;王冠楠;;有向网络重叠社区的快速划分算法[J];计算机科学;2014年S1期

4 卢风顺;宋君强;张理论;张卫民;任开军;朱小谦;;面向全球数值天气预报模式的加权等积并行数据划分算法[J];计算机研究与发展;2012年04期

5 喻云峰;赖海涛;;一种基于随机搜索的黑洞二划分算法实现[J];科技广场;2006年04期

6 李晨;葛声;;一种重叠可信社团划分算法的设计与实现[J];微计算机信息;2011年09期

7 李孝伟;陈福才;刘力雄;;一种融合节点与链接属性的社交网络社区划分算法[J];计算机应用研究;2013年05期

8 牛建军;刘上乾;韩宝君;任宝文;;同心圆检测中的区域划分算法[J];光子学报;2006年12期

9 吕德奎;;聚合算法在电力GIS中的应用[J];电力信息化;2012年05期

10 王晓芳;贾宗维;;一种新的图划分算法在PPI网络模块化中的研究[J];山西农业大学学报(自然科学版);2012年06期

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

1 王玲娜;李兴明;;基于最小支撑树的通用区域划分算法[A];2008年中国西部青年通信学术会议论文集[C];2008年

2 徐丹丹;章勇;;一种基于节点度更新的簇划分算法[A];2008通信理论与技术新发展——第十三届全国青年通信学术会议论文集（下）[C];2008年

3 刘培强;谢青松;朱大铭;;用于基因表达谱数据聚类分析的贪心图划分算法研究[A];2006年全国理论计算机科学学术年会论文集[C];2006年

4 刘华伟;全庆一;;能量有效的基于连通度的分布式簇划分算法[A];2011年全国通信安全学术会议论文集[C];2011年

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

1 许金凤;大规模动态自适应图划分算法[D];宁波大学;2015年

2 周爽;面向BSP模型的图数据划分算法的设计与实现[D];东北大学;2013年

3 林慧娴;个性化服务中用户建模及社区划分算法研究[D];南京邮电大学;2015年

4 吴磊;复杂网络的社团划分算法研究[D];太原理工大学;2016年

5 宋俐;基于模糊聚类的社团划分算法研究[D];太原理工大学;2016年

6 马静;基于社交网络的社团划分算法研究[D];山东师范大学;2011年

7 韩明伟;超大规模集成电路划分算法研究[D];西安电子科技大学;2008年

8 辛娟娟;社区划分算法的研究与应用[D];北京林业大学;2015年

9 杜鹏飞;基于边的相似性的复杂网络社团划分算法研究[D];山东师范大学;2014年

10 赵琴;并行计算中图划分算法的研究[D];华中师范大学;2013年

，

本文编号：1006884