基于随机游走的动态社团划分算法

发布时间：2017-10-23 08:26

  本文关键词：基于随机游走的动态社团划分算法

  更多相关文章： 社团划分 马尔科夫过程 随机游走 线性方程组求解 正规拉普拉斯矩阵

【摘要】：网络科学是近十多年来兴起的一门交叉科学。对复杂网络性质的研究有重要的意义。社团性质是复杂系统中网络结构的一个重要结构特征。直观上讲,社团结构表示在同一个社团中图的顶点之间的连边比较密集,相对地,社团之间的连边稀疏。社团划分是一个NP-hard问题。本篇文章的第一部分介绍了一些典型的网络和重要的社团划分算法,例如空手道俱乐部网络,蛋白质网络等以及二部划分,层次划分和动态划分等。第二部分阐述了本人的社团划分算法。在一个网络中,随机游走是从某一个顶点出发随机地移动到与其相邻的顶点,并继续这样的游走的过程。定性的认为从顶点i出发的游走将会大概率地滞留在顶点i的社团中(找不到错综复杂的迷宫的出口),这就意味着顶点i移动到其他社团的期望步长很大(不断地做尝试)。基于这个思路,与马尔科夫随机过程理论结合,求出任意两个顶点间的首次到达的期望步长,通过根据这个度量将顶点进行聚类的方式将顶点集合划分成不同的社团。第三部分对此算法的复杂度和优劣性进行了讨论,在分析复杂度的过程中尝试了很多种求解线性方程组的方法,利用标准化拉普拉斯矩阵的谱理论和柯西交错定理证明了在顶点个数很大的情况下一般的迭代算法是不可取的,最终选择的方法为共轭梯度法,本算法的复杂度为O(3)。最后利用了几个典型的关系网络和随机图来验证算法的可靠性,通过测试的对比结果来看此算法在可靠性上具有一定优越性。
【关键词】：社团划分 马尔科夫过程 随机游走 线性方程组求解 正规拉普拉斯矩阵
【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 中文摘要6-7
• 英文摘要7-9
• 第一章 引言9-12
• 第二章 重要网络和社团结构划分算法介绍12-22
• 2.1 网络介绍12-14
• 2.2 算法介绍14-22
• 2.2.1 社团量化标准14-16
• 2.2.2 社团发现和划分算法16-22
• 第三章 复杂网络的动态划分算法22-28
• 3.1 经典算法的局限性22-23
• 3.2 基于随机游走的算法23-28
• 3.2.1 基本思想和理论基础23-25
• 3.2.2 对距离矩阵的分析25-27
• 3.2.3 算法流程27-28
• 第四章 算法复杂度分析和改进28-33
• 4.1 复杂度分析28-31
• 4.2 算法的改进31-33
• 第五章 模型测试33-37
• 5.1 随机图33-35
• 5.2 空手道社团35
• 5.3 海豚图35-37
• 第六章 总结与展望37-38
• 参考文献38-41
• 附录一 程序代码41-46

【相似文献】

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

1 吴迪;周利娟;林鸿飞;;基于随机游走的就业推荐系统研究与实现[J];广西师范大学学报(自然科学版);2011年01期

2 苏浩航;张义门;张玉明;解敏;满进财;;基于改进的压缩式随机游走算法对静态电源/地网的模拟[J];计算物理;2007年06期

3 宋锐;汤建勋;周健;;工作电流对二频机抖激光陀螺角随机游走影响的研究[J];激光杂志;2010年02期

4 周持中;一类具有吸收点的平面随机游走[J];岳阳大学学报;1996年02期

5 雷钰丽;李阳;王崇骏;刘红星;谢俊元;;基于权重的马尔可夫随机游走相似度度量的实体识别方法[J];河北师范大学学报(自然科学版);2010年01期

6 俞琰;邱广华;;基于局部随机游走的在线社交网络朋友推荐算法[J];系统工程;2013年02期

7 何建军;李仁发;;改进的随机游走模型节点排序方法[J];计算机工程与应用;2011年12期

8 邓贵仕,赖宝全;反馈式随机游走模型及其在股票投资中应用[J];大连理工大学学报;2004年06期

9 戴颖;;深圳股票市场的随机游走检验[J];商业经济;2005年11期

10 周军军;王明文;何世柱;石松;;基于随机游走和聚类平滑的协同过滤推荐算法[J];广西师范大学学报(自然科学版);2011年01期

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

1 郑伟;王朝坤;刘璋;王建民;;一种基于随机游走模型的多标签分类算法[A];NDBC2010第27届中国数据库学术会议论文集A辑一[C];2010年

2 朱松豪;罗青青;梁志伟;;一种改进图像标注的新方法[A];第24届中国控制与决策会议论文集[C];2012年

3 燕飞;张铭;谭裕韦;唐建;邓志鸿;;综合社会行动者兴趣和网络拓扑的社区发现方法[A];NDBC2010第27届中国数据库学术会议论文集(B辑)[C];2010年

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

1 长盛基金管理有限公司研究部副总监 李骥;投资自己熟悉的股票[N];证券时报;2006年

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

1 邓凯英;复杂网络搜索策略及相关模型的数值方法[D];东北师范大学;2015年

2 徐晓华;图上的随机游走学习[D];南京航空航天大学;2008年

3 孙甲申;基于主题模型和随机游走的标签技术研究[D];北京邮电大学;2013年

4 吕强;面向高性能和强表达力的自动规划[D];中国科学技术大学;2013年

5 赵学华;统计网络模型若干关键问题研究[D];吉林大学;2014年

6 廖振;基于查询点击核心图的查询推荐问题研究[D];南开大学;2013年

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

1 何岱洧;Z~d上使Schramm的上界达到的旋转配置[D];复旦大学;2014年

2 田新春;回火老化效应及其扩散方程[D];兰州大学;2015年

3 鞠薇;基于随机游走和图割算法的PET-CT肺肿瘤分割[D];苏州大学;2015年

4 祝霖;基于随机游走的动态社团划分算法[D];上海交通大学;2015年

5 陆林;图上的智能随机游走分类算法研究及应用[D];扬州大学;2014年

6 王丽莎;基于随机游走模型的个性化信息推荐[D];大连理工大学;2011年

7 胡洁;基于图论的医学图像分割随机游走算法研究[D];南方医科大学;2013年

8 郑伟;基于增强语义和随机游走的分类算法研究[D];清华大学;2011年

9 沈敬欣;结合最大度与随机游走策略的复杂网络搜索技术研究[D];大连海事大学;2012年

10 康宗战;协同标注系统中基于随机游走的个性化推荐研究[D];云南大学;2015年

，

本文编号：1082387