基于隶属函数的社团发现算法的研究与实现

发布时间：2017-07-02 08:00

  本文关键词：基于隶属函数的社团发现算法的研究与实现，由笔耕文化传播整理发布。

【摘要】：复杂网络是一门与社会学、信息学和计算机科学等许多研究领域存在交集的研究科学。近年来,随着复杂网络研究的深入发展,复杂网络中越来越多的特征被大家发现和熟知,特别是复杂网络的社团特性,这一特性不仅可以帮助大家清晰地认识和分析网络功能,还是研究复杂网络其他特性的基础。本文首先从复杂网络的研究背景和意义出发,依次介绍了复杂网络的理论基础,描述了目前复杂网络社团发现算法的国内外研究现状,概述了社团结构的定义并重点介绍了几种较典型的社团发现算法。针对目前大多数社团划分算法考虑影响社团划分因素不全面以及社团定义具有模糊性的情况,本文首先定义了一种计算节点到社团隶属情况的隶属函数,该函数是根据模糊数学中隶属函数的定义以及社团的基本性质而确定的。在此基础上,提出了一种基于隶属函数的启发式社团发现算法(MCDA)。该算法以隶属函数作为社团划分的衡量标准,通过计算节点到社团的隶属度,可以找到节点所属的社团。通过结合模糊聚类的基本思想和隶属度函数,MCDA算法可以得到节点到各社团的具体隶属度大小,并且隶属度函数综合考虑了多种因素,使得MCDA算法具有较高的精确性,而且还具有较低的时间复杂度。此外,在MCDA算法的基础上,针对现实世界的复杂网络总是不断变化的情况,设计并实现了一种动态算法(DMCDA)。该算法弥补了 MCDA算法在解决动态问题时的不足,利用动态隶属度函数与增量式动态社团发现算法的思想,实现在初始社团结果的基础上对后续动态网络的社团划分。理论与实验均证明了该算法具有较好的划分效果和较快的运行效率。
【关键词】：复杂网络 社团发现 隶属函数 动态网络
【学位授予单位】：东北大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5;TP301.6
【目录】：

• 摘要5-6
• Abstract6-11
• 第1章 绪论11-17
• 1.1 研究背景与意义11-12
• 1.1.1 研究背景11
• 1.1.2 研究意义11-12
• 1.2 国内外研究现状与挑战12-14
• 1.2.1 国内外研究现状12-14
• 1.2.2 社团发现面临的挑战14
• 1.3 本文的主要内容14-15
• 1.4 本文的组织结构15-17
• 第2章 复杂网络的理论基础17-33
• 2.1 复杂网络的概念与特性17
• 2.2 复杂网络的相关度量17-21
• 2.2.1 复杂网络的形式化表达17-19
• 2.2.2 度与度分布19-20
• 2.2.3 聚类系数20-21
• 2.2.4 模块度21
• 2.3 典型的复杂网络模型21-23
• 2.3.1 ER随机模型21-22
• 2.3.2 WS小世界模型22-23
• 2.3.3 BA无标度模型23
• 2.4 社团定义与社团发现算法23-31
• 2.4.1 社团结构的定义24-25
• 2.4.2 经典的社团发现算法25-31
• 2.4.2.1 基于图形分割的算法25-27
• 2.4.2.2 基于层次聚类的划分算法27-30
• 2.4.2.3 启发式算法30-31
• 2.5 本章小结31-33
• 第3章 MCDA算法的设计与实现33-53
• 3.1 算法的提出33-34
• 3.2 算法的思想基础34-38
• 3.2.1 影响社团划分的因素34-37
• 3.2.2 模糊聚类算法的相关思想37-38
• 3.3 算法的实现38-50
• 3.3.1 相关变量38-42
• 3.3.2 算法的实现过程42-46
• 3.3.3 算法的思想验证46-50
• 3.4 复杂度分析50-51
• 3.4.1 时间复杂度分析50-51
• 3.4.2 空间复杂度分析51
• 3.5 本章小结51-53
• 第4章 DMCDA算法的设计与实现53-61
• 4.1 DMCDA算法的提出53-54
• 4.2 算法的实现54-58
• 4.2.1 相关概念55-56
• 4.2.2 算法的具体实现56-58
• 4.3 简单动态网络的理论验证58-60
• 4.4 本章小结60-61
• 第5章 实验分析61-77
• 5.1 实验环境61
• 5.2 实验数据61-66
• 5.2.1 经典网络数据集61-63
• 5.2.2 生成网络的数据集63-66
• 5.3 实验结果与分析66-74
• 5.3.1 静态算法的实验结果与分析66-72
• 5.3.2 动态算法的实验结果与分析72-74
• 5.4 算法评估74-75
• 5.4.1 精确性指标75
• 5.4.2 运行效率指标75
• 5.5 本章小结75-77
• 第6章 结论与展望77-79
• 6.1 研究工作总结77-78
• 6.2 工作展望78-79
• 参考文献79-83
• 致谢83

【相似文献】

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

1 胡洪林;;截断思想在算法分析中的应用[J];科技风;2012年12期

2 陈际平;算法分析与优化程序的研究[J];西北大学学报(自然科学版);1994年05期

3 梁彦杰;徐坚;;算法分析中概率变化与图形生成[J];云南大学学报(自然科学版);2009年S2期

4 刘宁;邵晓艳;;算法分析与设计课程中多媒体技术的应用[J];科技风;2009年18期

5 海亚;张永平;;算法对学生解决问题能力的培养[J];黑龙江科技信息;2008年10期

6 李冰颖,夏利民,舒远仲;学分制模式下网上选课系统的算法探析[J];江西科学;2004年05期

7 Anany Levitin;Maria Levitin;;算法谜题[J];中国科技信息;2014年08期

8 杜刚;陆黎明;;一修路问题的算法解决分析[J];太原师范学院学报(自然科学版);2006年02期

9 许之民;;砝码称重问题的多种算法分析与探究[J];合肥学院学报(自然科学版);2011年01期

10 李亚楠;;菌群优化算法分析[J];贵州大学学报(自然科学版);2011年02期

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

1 俞洋;田亚菲;;一种新的变步长LMS算法及其仿真[A];通信理论与信号处理新进展——2005年通信理论与信号处理年会论文集[C];2005年

2 周颢;刘振华;赵保华;;构造型的D~2FA生成算法[A];中国通信学会通信软件技术委员会2009年学术会议论文集[C];2009年

3 赖桃桃;冯少荣;张东站;;一种基于划分和密度的快速聚类算法[A];第二十五届中国数据库学术会议论文集（一）[C];2008年

4 刘远新;邓飞其;罗艳辉;舒添慧;;ERP柔性平台下物流运输配送系统算法分析[A];第二十六届中国控制会议论文集[C];2007年

5 王树西;白硕;姜吉发;;模式合一的“减首去尾”算法[A];第二届全国学生计算语言学研讨会论文集[C];2004年

6 王万青;张晓辉;;改进的A~*算法的高效实现[A];2009全国测绘科技信息交流会暨首届测绘博客征文颁奖论文集[C];2009年

7 孙焕良;邱菲;刘俊岭;朱叶丽;;IncSNN——一种基于密度的增量聚类算法[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年

8 韩建民;岑婷婷;于娟;;实现敏感属性l-多样性的l-MDAV算法[A];第二十七届中国控制会议论文集[C];2008年

9 张悦;尤枫;赵瑞莲;;利用蚁群算法实现基于程序结构的主变元分析[A];第五届中国测试学术会议论文集[C];2008年

10 王旭东;刘渝;邓振淼;;正弦波频率估计的修正Rife算法及其FPGA实现[A];全国第十届信号与信息处理、第四届DSP应用技术联合学术会议论文集[C];2006年

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

1 科文;VIXD算法分析Web异常[N];中国计算机报;2008年

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

1 魏哲学;样本断点距离问题的算法与复杂性研究[D];山东大学;2015年

2 刘春明;基于增强学习和车辆动力学的高速公路自主驾驶研究[D];国防科学技术大学;2014年

3 张敏霞;生物地理学优化算法及其在应急交通规划中的应用研究[D];浙江工业大学;2015年

4 李红;流程挖掘算法研究[D];云南大学;2015年

5 刘新旺;多核学习算法研究[D];国防科学技术大学;2013年

6 于滨;城市公交系统模型与算法研究[D];大连理工大学;2006年

7 曾国强;改进的极值优化算法及其在组合优化问题中的应用研究[D];浙江大学;2011年

8 肖永豪;蜂群算法及在图像处理中的应用研究[D];华南理工大学;2011年

9 陈耿;面向中观审计的规则发现算法研究[D];东南大学;2005年

10 王维博;粒子群优化算法研究及其应用[D];西南交通大学;2012年

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

1 黄厦;基于改进蚁群算法的柔性作业车间调度问题研究[D];昆明理工大学;2015年

2 李平;基于Hadoop的信息爬取与舆情检测算法研究[D];昆明理工大学;2015年

3 赵官宝;基于位表的关联规则挖掘算法研究[D];昆明理工大学;2015年

4 殷文华;移动容迟网络中基于社会感知的多播分发算法研究[D];内蒙古大学;2015年

5 徐翔燕;人工鱼群优化算法及其应用研究[D];西南交通大学;2015年

6 李德福;基于小世界模型的启发式寻路算法研究[D];华中师范大学;2015年

7 郑海彬;一种面向MAPREDUCE的DATASHUFFLE的优化方法[D];苏州大学;2015年

8 赵晓寒;轮换步长PSO算法及SMVSC参数优化[D];沈阳理工大学;2015年

9 安丰洋;基于无线网络的广播算法研究[D];曲阜师范大学;2015年

10 李智明;基于改进FastICA算法的混合语音盲分离[D];上海交通大学;2015年

  本文关键词：基于隶属函数的社团发现算法的研究与实现，，由笔耕文化传播整理发布。

本文编号：509015