基于交互度的重叠社区发现算法.pdf

《基于交互度的重叠社区发现算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号密级公开编号碎士研究被香像合式题目基干交互的■疊社区发现算法学院（所、中心）信息学院专业名称计算机科学与技术研究生姓名李磊学号导师姓名职称年月扉页论文独创性声明及使用授权本论文是作者在导师指导下取得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不存在剽窃或抄袭行为。与作者一同工作的同志对本研宄所做的任何贡献均已在论文中作了明确的说明并表示了谢意。现就论文的使用对云南大学授权如下：学校有权保留本论文（含电子版），也可以釆用影印、缩印或其他复制手段保存论文；学校有权公布论文的全部

2、或部分内容，可以将论文用于查阅或借阅服务；学校有权向有关机构送交学位论文用于学术规范审查、社会监督或评奖；学校有权将学位论文的全部或部分内容录入有关数据库用于检索服务。内部或保密的论文在解密后应遵循此规定）研究生签名导师签名：丄戈日期：摘要近年来，研究者通过对复杂网络的深入研究，提出了社区的概念，并且发现现实世界中的复杂网络几乎都具有社区结构。学者们为了发掘复杂网络中的社区结构，提出了很多社区发现算法。社区发现算法在不同学科和领域中都有重要的应用，例如，生物学，互联网，社会学和计算机科学等。在社发现领域中，重叠社区发现的目的是找

3、到社区之间的重叠部分，重叠部分本身的特点使其在复杂网络中具有特殊的意义和价值，例如，可以从重叠部分进而推断社区之间是否有相似的关联；对于动态变化的社区，可以从重叠部分预测社区未来的变化，或把己出现的社区还原为上一形态；若把重叠部分删除，则社区之间就是完全独立的；等等。本文提出了一种基于交互度的重叠社区发现算法。本文的主要研究内容和创新之处总结如下：基于交互度的思想，对社区的重叠部分进行了新的定义，使得对重叠部分的解释更加接近现实也更为合理。本算法以网络中度最大的节点为初始节点，采用凝聚的方式并以交互度为衡量标准对社区进行划分，得

4、出最终的划分结果，且划分出的重叠部分较为合理。很多重叠社区发现算法只适用于无权网络，而本算法不仅可用于无权网络，而且还可用于带权网络。无权网络或有带权网络使用本算法都能得到较为理想的结果。本算法使用海豚网络、空手道俱乐部网络和恒河猴网络作为实验数据，对这三个网络进行实验，把得出的结果与其他重叠社区发现算法得出的结果进行对比，可以认为本算法的结果较为合理，说明了本算法是有效的和可用的。关键词：复杂网络；社区发现；重叠社区；交互度AbstractInthepastfewyears，，ordirectedweightednetwork

5、susingthisalgorithmcangetmoredesirableresults.(3)丁；；；目录艘目胃一雜仓研究背景社区发现和重叠社区发现的意义国内外研究综述；研宄内容本文组织结构第二章相关理论社区的相关概念重叠社区的相关概念交互度的相关概念交互行为的概述交互图的概念社区交互度的概念相关算法介绍第三章基于交互度的重叠社区发现算法在重叠社区发现算法中引入交互度的合理性基于交互度的重叠社区的定义本算法的主要思想用于带权网络用于无权网络本算法的主要步骤第四章实验分析及对比海豚网络实验网络实验恒河猴网实验结果分析及扩展的取

6、值问题。扩大重叠部分第五章总结与建议本文结论应用与建议不足与展望隱考挪攻读硕士学位期间完成的科研成果^第一章绪论研究背景在年，数学家欧拉）提出了非常著名的“七桥问题”，从任意地点出发，是否可以走遍座桥，且每座桥只能走过一次，最后回到始发地点。这就是著名的“七桥问题”。欧拉把此问题抽象为一个一笔画问题，并证明此问题是不可能完成的。“七桥问题”是使用图论解决问题的第一次尝试，之后图论逐渐成为一种新的学科。复杂网络被发现之后，图论成为研宄复杂网络的基础。在世纪年代，数学家与提出了随机图（理论。在随机图中，边的出现体现了“随机”的特点，

7、任意两点之间的边都是随机产生的。随机图的概念为以后的学者提供了基本的理论依据，通过对复杂网络的进一步研宄，研宄者认为复杂网络并不是随机构成的，而是具有某些特点的。年，以及提出了“小世界”的概念⑴。随机网络中具有较小的平均路径长度，这种现象称为“小世界现象”。这种现象普遍存在与复杂网络中。年，和提出了复杂网络中的无标度特征的概念主要表现为：大多数节点只有很少的邻接点，而另一些节点有很多的邻接点，节点的度数整体上满足幂率分布。随机网络和规则网络都不具有无标度特征。这两个概念的提出，使研究者突破了用传统图论和随机图理论来研究复杂网络的

8、界限，逐步进入了研宄非随机复杂网络的新时代。研宄复杂网络的意义和目的是挖掘复杂网络中成员之间的内在联系以及网络结构之间的内在关系。现实世界中的复杂系统都可以被抽象成为复杂网络，使用复杂网络的概念为其他领域的研宄提供了新的思路和方法，并得到了令人意向不到的效果。随