基于BFS的局部社区发现算法研究

发布时间：2017-10-04 01:18

  本文关键词：基于BFS的局部社区发现算法研究

  更多相关文章： 局部社区发现 最大结合性节点 共同好友数目 广度优先搜索

【摘要】：近年来随着互联网技术的飞速发展,越来越多的数据以网状的结构呈现于人们面前,而社团结构正是研究网络拓扑结构的一个重要方面。发现网络中存在的社区结构也成了一个很热门的话题,许多学者对此进行了研究。传统的社区发现算法关注于整个全局网络结构,这样会具有较高的时间复杂度。而有的时候我们也不需要获得网络的全局社区结构。比如对于网络中的一个核心节点,我们想知道的是这个核心节点的覆盖范围,也即找到它所在的社区就可以了。因此本文提出了一种新的局部社区发现算法。本文提出的局部社区发现算法以起始节点相对应的最大结合性节点为出发点,以节点相似性(两个节点的共同邻居节点数目)为度量并基于图的广度优先搜索来进行社区发现。从起始节点相对应的最大结合性节点出发进行社区发现可以避免边界节点找不到社区的情况,提高算法的鲁棒性和普适性。基于图的广度优先搜索可以得到与图的边数呈线性规模的时间复杂度。将本文提出的算法运行在四个经典数据集上,在不降低社区发现精度的情况下依然显著降低了社区发现的时间复杂度,提高了算法鲁棒性。
【关键词】：局部社区发现 最大结合性节点 共同好友数目 广度优先搜索
【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要3-4
• ABSTRACT4-10
• 第一章 绪论10-13
• 1.1 课题研究背景和意义10
• 1.2 国内外研究现状10-12
• 1.3 论文主要工作12
• 1.4 论文组织结构12-13
• 第二章 社区发现综述13-34
• 2.1 社区发现定义13-24
• 2.1.1 基本概念13-15
• 2.1.2 局部定义15-17
• 2.1.3 全局定义17
• 2.1.4 基于节点相似度的定义17-19
• 2.1.5 基于分割的定义19-21
• 2.1.6 基于模块度的定义21-24
• 2.2 全局社区发现算法24-27
• 2.2.1 图分割24
• 2.2.2 等级聚类24-25
• 2.2.3 分割聚类25-26
• 2.2.4 谱聚类26
• 2.2.5 Girvan-Newman算法26-27
• 2.3 局部社区发现方法27-33
• 2.3.1 Clauset算法28-30
• 2.3.2 Luo算法30
• 2.3.3 Lee算法30-31
• 2.3.4 LMD算法31-32
• 2.3.5 Zhu算法32-33
• 2.4 本章小结33-34
• 第三章 基于BFS的局部社区发现算法设计34-47
• 3.1 相似度定义34-35
• 3.2 节点最大结合性35-36
• 3.2.1 节点结合性35-36
• 3.2.2 最大结合性节点36
• 3.3 算法过程描述36-44
• 3.3.1 算法发现步骤37-39
• 3.3.2 算法伪代码描述39-44
• 3.4 算法复杂度分析44-46
• 3.5 本章小结46-47
• 第四章 基于BFS的局部社区发现算法实现与分析47-74
• 4.1 实验数据集介绍47-53
• 4.1.1 数据集格式介绍47
• 4.1.2 空手道俱乐部网络47-49
• 4.1.3 海豚网络49-50
• 4.1.4 美国足球俱乐部网络50-51
• 4.1.5 美国政治书籍网络51-53
• 4.2 实验框架设计53
• 4.3 实验评价标准53-55
• 4.4 实验结果验证与分析55-73
• 4.4.1 空手道俱乐部网络数据验证56-59
• 4.4.2 海豚网络数据验证59-61
• 4.4.3 美国足球俱乐部网络数据验证61-66
• 4.4.4 美国政治书籍网络数据验证66-69
• 4.4.5 实验总结69-73
• 4.5 本章小结73-74
• 第五章 全文总结与展望74-76
• 5.1 论文工作总结74-75
• 5.2 创新点75
• 5.3 后续研究工作75-76
• 参考文献76-80
• 致谢80-81
• 攻读硕士学位期间已发表或录用的论文81-83

【相似文献】

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

1 龙腾芳,高金文;“分而治之”方法在算法设计中的应用[J];渤海大学学报(自然科学版);2004年01期

2 田翠华;王伟杰;许卫平;;《算法设计与分析》的理论研究与教学实践[J];赤峰学院学报(自然科学版);2012年15期

3 仇棣;;算法设计与分析——计算机理论领域中的一本好书[J];应用数学;1991年02期

4 张银明;元素判别值分配法及其算法设计[J];计算机工程与应用;1995年06期

5 沈灏;;信息与计算科学专业的算法设计能力培养方法[J];学园;2014年10期

6 李秦;;建构主义教学模式与算法设计与分析课程教学[J];甘肃科技;2013年24期

7 夏梦;;《算法设计与分析》的教学方法研究[J];科技资讯;2009年18期

8 许道云;;算法机制设计的数学基础[J];贵州大学学报(自然科学版);2013年03期

9 张银明;货郎担问题的新解法及其算法设计[J];华侨大学学报(自然科学版);1995年04期

10 陈云霞;聂士澄;;试谈学生算法设计能力的培养[J];扬州师院学报(自然科学版);1995年03期

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

1 雷咏梅;;椭圆曲线密码体制的算法设计与实现[A];西部大开发 科教先行与可持续发展——中国科协2000年学术年会文集[C];2000年

2 杨盘洪;朱军祥;赵建安;杨静;;机动目标跟踪的模糊变结构交互多模算法[A];2007'中国仪器仪表与测控技术交流大会论文集（二）[C];2007年

3 徐子珊;;《算法设计与分析》课程中的工程教育[A];2005年全国理论计算机科学学术年会论文集[C];2005年

4 王辉;刘治昌;;用一种新算法设计的安全系统[A];2007年中国智能自动化会议论文集[C];2007年

5 舒辉;柳清峰;杜祝平;周蓓;;实践教学模式在本科专业课程教学中的应用[A];中国电子教育学会高教分会2010年论文集[C];2010年

6 彭小宏;阳东升;刘忠;;基于聚类算法的组织协作网设计[A];2006中国控制与决策学术年会论文集[C];2006年

7 李皓;罗熊;;云存储部署优化的进化算法设计[A];2013年中国智能自动化学术会议论文集（第三分册）[C];2013年

8 罗长政;李熙莹;王镇波;罗东华;;一种大流量交叉路口的背景提取与更新算法[A];第十五届全国图象图形学学术会议论文集[C];2010年

9 杨利;李霖;昌月楼;阳国贵;;对称位向量及启发式并行散列连接算法[A];数据库研究与进展95——第十三届全国数据库学术会议论文集[C];1995年

10 张晋;;嵌入式电脑鼠运行算法的研究[A];全国第20届计算机技术与应用学术会议（CACIS·2009）暨全国第1届安全关键技术与应用学术会议论文集（上册）[C];2009年

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

1 ;算法设计的策略[N];电脑报;2003年

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

1 谷伟哲;齐次光滑算法及其应用[D];天津大学;2010年

2 龙海侠;进化算法及其在生物信息中的应用[D];江南大学;2010年

3 谭跃;具有混沌局部搜索策略的粒子群优化算法研究[D];中南大学;2013年

4 尤海峰;求解隐式目标优化问题的交互式进化算法研究[D];中国科学技术大学;2011年

5 张常淳;基于MapReduce的大数据连接算法的设计与优化[D];中国科学技术大学;2014年

6 郭崇慧;地区中长期发展规划若干定量模型、算法及应用研究[D];大连理工大学;2002年

7 蒋蔚;粒子滤波改进算法研究与应用[D];哈尔滨工业大学;2010年

8 孙贺;算法设计中的若干前沿问题[D];复旦大学;2009年

9 陈宁涛;基于二分技术的高效算法设计及其应用[D];华中科技大学;2006年

10 娄晓文;无符号基因组切割再粘贴重组问题的算法研究[D];山东大学;2010年

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

1 王豫中;基于BFS的局部社区发现算法研究[D];上海交通大学;2015年

2 陈艳琼;若干算法设计模式的研究与应用[D];江西师范大学;2008年

3 贺国华;交互变邻域微分进化群搜索优化算法[D];太原科技大学;2011年

4 蔡平梅;结构化稀疏信号的恢复算法研究[D];上海大学;2015年

5 李枝勇;蝙蝠算法及其在函数优化中的应用研究[D];上海理工大学;2013年

6 房娟艳;混合群搜索优化算法及其应用研究[D];太原科技大学;2010年

7 刘文锦;双收缩人工植物算法[D];太原科技大学;2012年

8 张园;递推技术在算法设计中的应用研究[D];江西师范大学;2012年

9 李旭明;基于小世界模型的社会情感优化算法及应用研究[D];太原科技大学;2012年

10 贾瑞民;人工蜂群算法的改进及应用研究[D];广西民族大学;2013年

，

本文编号：967813