基于k-truss的图社区发现算法研究

《基于k-truss的图社区发现算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文MASTER’SDISSERTATION论文题目基于k-truss的图社区发现算法研究作者姓名王岩学科专业软件工程指导教师陈子阳（教授）2016年5月中图分类号：TP312学校代码：10216UDC：621.3密级：公开工学硕士学位论文基于k-truss的图社区发现算法研究硕士研究生：王岩导师：陈子阳（教授）申请学位：工学硕士学科专业：软件工程所在单位：信息科学与工程学院答辩日期：2016年5月授予学位单位：燕山大学ADissertationinsoftwareengineeringT

2、HEFIGURECOMMUNITYDISCOVERYALGORITHMBASEDONK-TRUSSByWangyanSupervisor：ChenZiyangYanshanUniversityMay，2016燕山大学硕士学位论文原创性声明本人郑重声明：此处所提交的硕士学位论文《基于k-truss的图社区发现算法研究》，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研究工作所取得的成果。论文中除已注明部分外不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均已在文

3、中以明确方式注明。本声明的法律结果将完全由本人承担。作者签字：日期：年月日燕山大学硕士学位论文使用授权书《基于k-truss的图社区发现算法研究》系本人在燕山大学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山大学，可以采用影印、缩印或其它复制手段保存论文，可以公布论文的全部或部分内容。保密

4、□，在年解密后适用本授权书。本学位论文属于不保密□。（请在以上相应方框内打“√”）作者签名：日期：年月日导师签名：日期：年月日摘要摘要随着现代化信息技术的迅猛发展，图社区发现广泛应用于社交网络、生物学、语义网和模式识别等领域。团问题是近几年提出的图社区发现问题的一个分支，查找极大k-truss是团问题的一种基本解决方法，但是现有的k-truss计算方法不够高效。本文重点研究如何高效求解极大k-truss问题，通过对现有基于内存的极大k-truss算法进行分析，发现现有算法存在过滤效果差、求解过程中

5、存在大量冗余计算以及无法处理大图等问题。具体研究内容如下。首先，针对已有的基于内存的极大k-truss算法在过滤阶段存在过滤效果差的问题，考虑到网络图中顶点度越高越可能形成极大k-truss，提出基于顶点度的过滤策略和以此为基础的算法，在同样的时间复杂度上减少了计算量，缩短了查找时间。其次，针对现存的方法在计算过程中存在大量冗余计算以及不能有效处理大图的问题，提出了基于下界值的极大k-truss算法和基于上界值的极大k-truss算法。前者通过将大图划分成小图以及为图中的每条边确定一个下界值，解决

6、了无法处理大图的问题；后者在此基础上通过对每条边计算一个上界值，避免了无效k-truss的计算，进一步缩短了查找时间。最后，基于5个真实的数据集进行查询测试，对不同方法的计算性能进行了比较。实验结果验证了本文提出的三种方法具有高效性。关键词k-truss；团问题；过滤策略；社区发现I燕山大学工学硕士学位论文AbstractWiththedevelopmentofmoderninformationtechnology,thegraphcommunitydetectionhasbeenwidelyus

7、edinsocialnetwork,biology,semanticwebandpatternrecognition.Thecliqueproblemisabranchofthegraphcommunitydetectionproblemthathasbeenraisedinrecentyears.Abasicsolutionissearchingmaximumk-truss,buttheexistingk-trusscalculationmethodisnotefficientenoughtos

8、olvecliqueproblem.throughtheanalysisoftheexistingk-trussalgorithmwhichisbasedonmemory,wefoundthattheexistingalgorithmhasapoorfilteringeffectandalotofredundantcomputationinthecalculationprocessandcannotprocesslargegraph.Thispaperfocusesonhowtos