非重叠社区发现中近邻传播算法的研究与应用.pdf

硕士学位论文
非重叠社区发现中近邻传播算法的研究与
应用
Research and Application of Affinity
Propagation Algorithm on Non-overlapping
Community Detection
作 者：王淑靖
导 师：孟凡荣 教授
中国矿业大学
二○一六年五月
中图分类号 TP311 学校代码 10290
UDC 004 密 级 公开
中国矿业大学
硕士学位论文
非重叠社区发现中近邻传播算法的研究与应用
Research and Application of Affinity Propagation
Algorithm on Non-overlapping Community
Detection
作 者 王淑靖 导 师 孟凡荣
申请学位 工学硕士 培养单位 计算机科学与技术学院
学科专业 计算机应用技术 研究方向 数据挖掘
答辩委员会主席 张永平 评 阅 人
二○一六年五月
论文审阅认定书
研究生 王淑靖 在规定的学习年限内，按照研究生培养方案的要
求，完成了研究生课程的学习，成绩合格；在我的指导下完成本学位
论文,经审阅，论文中的观点、数据、表述和结构为我所认同，论文
撰写格式符合学校的相关规定，同意将本论文作为学位申请论文送专
家评审。
导师签字：
年 月 日
致谢
时光荏苒，三年的硕士研究生生活转瞬即逝，忆及这三年的硕士生活充实而有意义，
令人难以忘记。在此论文完成之际，我要向给予我指导、支持、帮助及关心过我的老师、学
长、同学和亲人表示衷心的感谢！
首先，非常诚挚地感谢我的导师孟凡荣教授和夏士雄院长。孟老师对我研究生三年的
培养起到了非常关键的作用。研究上，教会我踏实、严谨和创新；生活上，教会我乐观、勇
敢和真诚；他们还给我们提供了良好的科研实践环境，让我们可以认真学习不辜负三年光阴，
这些经历将使我终身受用。
感谢周勇老师，从本科毕业论文，到硕士论文的最终完成，都离不开周勇老师的悉心指
导。他对我平时的研究和学习给予了莫大的帮助和关怀，也对我的工作提供了充分的鼓励和
支持，同时生活上也给予了无微不至的关怀，是我很敬重的一位老师。
感谢矿山数字化研究所的姚睿老师、王志晓老师、牛强老师等，他们在科研学习方面给
予我无私的帮助，在此向他们表示诚挚的感谢。
感谢实验室的邢艳师姐和已经毕业的朱牧师兄，在科研过程中给予我极大的帮助和启
发，没有他们，我不可能这么顺利地完成学业。感谢同届的汤镇宇、宋路杰，以及张凤、王
伟东、于冰洁、崔哲、刘峰、孙贵宾、孙金亮等师弟师妹，感谢他们共同创造了一个和谐、
温馨的学习环境，也使我少走了很多弯路，在此向他们表示诚挚的敬意和衷心的感谢，祝他
们今后事业有成、一帆风顺。
感谢我最爱的爸爸、妈妈和姐姐，感谢他们这些年来在生活和精神上给予我的支持与鼓
励，今后无论身在何方，他们都将是我坚强的后盾和前进的动力。
本论文虽然几经修改，但由于才疏学浅，疏漏之处在所难免，还望各位老师批评指正，
感谢各位专家百忙之中审阅本文并提出宝贵意见！
摘 要
复杂社会网络可以抽象为由大量节点和节点之间的联系组成的拓扑结构，其
在众多领域中广泛存在。聚类分析作为研究复杂社会网络的重要手段之一，目的
在于发现其内部的社区结构，体现其内在属性，更好地对现实生活进行指导。本
文主要针对近邻传播算法的执行速率较慢、无监督的缺点，给出其改进算法，并
将近邻传播算法运用在增量社区发现中。
首先，给出基于近邻传播的快速半监督社区发现算法（FSAP 算法）。算法
在研究近邻传播算法(AP 算法)的基础上，根据因子图模型中信息在节点间的传
递规则，