半监督的社区发现方法研究

《半监督的社区发现方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、宣拿未)

2、p夕l硕士学位论文瘪篱半监督的社区发现方法研究Researchonsemi—supervisedcommunitydetectionalgorithm作者：康旭彬导师：贾彩燕北京交通大学2012年12月学位论文版权使用授权书f㈣本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。(保密的学位论文在解密后适用本

3、授权说明)学位论文作者签名：馕幅襁导师签名：覆移彩签字目期：2。?2年12-,目1]日签字日期：zo／z年臃月／)n中图分类号：TPl82UDC：004．8学校代码：10004密级：公开北京交通大学硕士学位论文半监督的社区发现方法研究Researchonsemi—supervisedcommunitydetectionalgorithm作者姓名：康旭彬导师姓名：贾彩燕学位类别：工学学科专业：计算机科学与技术学号：10120474职称：副教授学位级别：硕士研究方向：数据挖掘北京交通大学北尿父通大字2012年12月致谢本论文的

4、工作是在我的导师贾彩燕副教授的悉心指导下完成的，贾彩燕副教授严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三年来贾老师对我的关心和指导。于剑教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都给予了我很大的关心和帮助，在此向于剑老师表示衷心的谢意。周学忠副教授、景丽萍副教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷心的感谢。在实验室工作及撰写论文期间，姜在兴、刘凯、王超、朱莹莹等同学对我论文中的复杂网络研究工作给予了热情帮助，在此向他们表达我的感激之情。另外也感谢我的家人，他们的理解

5、和支持使我能够在学校专心完成我的学业。中文摘要自然界中存在的很多系统可以用网络的形式表示，如人际关系网、蛋白质作用网络、交通网络等。这些网络具有很高的复杂性，因此被称为“复杂网络”。社区结构是复杂网络研究的几个重要分支之一，越来越受到人们的重视。现有的社区发现方法常存在算法复杂度高、需要事先指定社区的数目、需要预先制定评价指标等缺陷，有的甚至需要给出大致的社区大小，限制了算法的实际应用效率。LPA(LabelPropagationAlgorithm)是一种重要的社区发现算法，它具有思想简单、复杂度低、不需要指定社区数目等优

6、点，但算法精确度比较低。针对LPA算法，本文设计了一种改进的基于节点局部相似性的半监督算法，本文的主要创新点有：一，LPA算法在节点的label传播过程中，由于平等的对待了节点的每一个邻居节点，当邻居节点中出现多个label数目相同时，LPA会随机的选择一个label作为候选label，此方法容易造成不同社区之间的label相互传播，从而造成社区划分的准确率比较低。本文通过计算相邻节点问的相似度，为网络的每条边加入权值，使得不同社区之间的label传播被阻断，提高了算法的精确率。二，现有的社区发现算法都属于无监督学习的范畴

7、，无法处理事先给定的半监督知识。本文中，将LPA算法加入了对半监督知识的处理过程，通过增加must．1ink节点对之间的边，删除cannot．1ink节点对最短路径中权值较小的边，使得网络的社区结构趋于明显，从而提高了算法的精确度。三，将以上两种方法相结合，通过在不同规模的人工网络和多种真实网络中进行试验并与多种方法相比较，验证了该算法的有效性。关键词：复杂网络；社区发现；半监督分类号：TPl82ABSTRACTABSTRACT：Manysystemsexistedinnaturecanberepresentedbythe

8、network，suchasInterpersonalnetwork，Proteininteractionnetwork，Tra伍cnetwork．Thesenetworkshaveveryhi曲complexity,SOtheyarecalled“complexnetwork”．Asoneofthemostimportantbranchesofcomplexnetworks，communitystructurehasattractedmoreandmoreattentionformpeople．Theexistedcom

9、munitydetectionalgorithmshavehi曲computationalcomplexity,requirepriornumberofcommunity,needtoadvancethedevelopmentofevaluationindexandotherdefects，someev