基于用户节点相似度的局部社团挖掘算法的研究

《基于用户节点相似度的局部社团挖掘算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、DissertationSubmittedtoShanghaiJiaoTongUniversityfortheDegreeofMasterLOCALCOMMUNITYDETECTIONBASEDONUSER’SSIMILARITYCandidate：FanChaoxiangStudentID:1110369045Supervisor：AssociateProf.FanLeiAcademicDegreeAppliedfor：MasterofEngineeringElectronicandCommunicationSpeciality：EngineeringSchoolofInformation

2、SecurityAffiliation：EngineeringDateofDefence：Jan,2014Degree-Conferring-Institution：ShanghaiJiaoTongUniversity万方数据上海交通大学硕士学位论文基于用户节点相似度的局部社团挖掘算法的研究摘要社团结构是复杂网络非常重要的特征之一。表示人与人之间关系的社交网络、因特网、科学家之间合作的引文网络、物种捕食关系的食物链网络等等都是复杂网络的典型代表。近些年，社交网络社团结构的挖掘受到越来越多的人的关注。传统的社团挖掘方法往往关注于整个网络的社团结构，这样带来的问题往往是复杂度较高。随着网络的规模

3、不断的扩大，运用传统的从全局角度出发挖掘社团结构的算法所带来的计算复杂度高的问题越来越突出，成为社团挖掘面临的瓶颈，与此同时对于类似于万维网这样规模巨大并且动态变化的网络，上述方法的可行性和意义有待讨论。基于以上问题，局部社团结构挖掘算法的研究就显得尤为重要。所谓局部社团结构挖掘是从某个点或者与该点关联性比较大的点出发，挖掘出局部社团的结构。在现实世界中，由于存在巨大的社交网络，人们往往更关注局部具有代表性的节点所属的社区。例如通常情况下，大多数人只是关注社交网络中某个他们感兴趣的人所在的社团结构，或者在万维网中某些特别的网站所在的局部社团结构。本文提出一种局部社团挖掘算法，该算法是一种基于

4、用户节点相似度的局部社团挖掘算法，通过对算法进行复杂度分析以及实验对比，可以得到本文算法在保证较高准确度的情况下，同时保证较低的复杂度的结论。本文主要工作和创新点包括以下几方面内容：第一，通过寻找待挖掘节点的局部中心节点，进而从局部中心节点出发进行局部社团挖掘，同时把用户节点相似度作为往社团中添加2节点的依据，降低了算法的时间复杂度，时间复杂度降为O(kd)。第二，算法在降低时间复杂度的同时，依然保持了较高的算法准I万方数据上海交通大学硕士学位论文确性。第三，将算法运用于经典的空手道网络、海豚网络、美式足球俱乐部网络、美国政治书籍网络以及计算机生成的满足复杂网络结构的计算机模拟生成的标准数据

5、集中，并与经典的局部社团挖掘算法进行了对比试验，本算法社团挖掘准确度提高。通过实验证实了该算法在降低复杂度的同时，可以保证较高的准确度。关键词：社团挖掘；复杂网络；局部中心点；节点相似度II万方数据上海交通大学硕士学位论文LOCALCOMMUNITYDETECTIONBASEDONUSER’SSIMILARITYABSTRACTCommunitystructureisoneofthemostimportantfeatureofcomplexnetworks.Itrepresentstherelationshipbetweenpeopleinsocialnetworks,thewebsites

6、linkrelationshipintheInternet,thecooperationrelationshipincitationnetworksandthefoodchainrelationshipinanimalnetworks.Allofthesenetworksarerepresentativesofcomplexnetworks.Inrecentyears,communitystructuresdetectiongetmuchmoreattentioninacademicworld.Traditionalcommunitydetectionalgorithmsfocusonthe

7、communitystructureoftheentirenetwork,whichhavehightimecomplexity,andthesesalgorithmsrequireinformationofthewholenetwork,whichistoolargeandhardtoknowcompletely.Withthesizeofthenetworksbecomelargerandlarger,t