基于层次提取—局部聚类社区挖掘算法的研究

《基于层次提取—局部聚类社区挖掘算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于层次提取．局部聚类的社区挖掘算法摘要社会网络是指社会个体成员之间因为互动而形成的相对稳定的关系体系，其中联系较为紧密的团体称为社区，处在同一社区中的个体更易于受到社区内其他人的影响，而社区挖掘技术就是挖掘网络中存在的社区。然而大多数社区挖掘算法都是面向中小型网络，当处理结点数千万级甚至上亿级的网络时，耗费巨大时间和资源，因而无法应用。针对大型社会网络社区结点和边数量巨大、社区结构复杂，普通社区挖掘算法挖掘效率低的问题，本文提出层次提取．局部聚类的社区挖掘算法。首先提出局部聚类算法，即提取社区中某一结点度较高的结点为核心结点及某一邻接结点，分

2、别对两结点提取所有的邻接结点，通过对这些结点中公共结点数量来判断这两个结点是否属于同一社区，通过该方法依次以社区内其他未被访问结点为核心结点再进行判定，直至社区内不存在未被访问结点，重复该过程直至社区划分完全；然后在该算法的基础上进行改进，提出多层扩展及无环结点移除的改进思想，并通过实验分析验证可行性；最后将该算法应用在大型社会网络的社区挖掘中，对大型的社会网络核心结点提取，采用层次提取的方法，减少了算法结点扫描次数，并通过实验对算法的可行性进行了验证。实验结果表明该算法能有效的实现社区划分，并且有着较低的时间复杂度和较高的划分精度，并且可以通

3、过对阈值的调整，自由控制挖掘社区的大小及质量。关键词：社会网络；社区挖掘；层次提取；局部聚类；无环节点；哈尔滨工程大学硕士学位论文AbstractAsocialnetworkisasocialstructuremadeupofindiViduals，andc01mectedwi[heachotherbyoneormorespeciflctypesofinterdependency，suchasfriendship，Commoni【lterest，w01．kingrelationorkinship．Inanetwork，thosecloselyl

4、inkedgroupcalledtheCom：nunity，andcommunit)7miningalgorithmsareusedtominingthepotentialcommunities．H(1weVer，mostc()mmunityminingalgorithmsaredesignedformediumnetworks，a11dcannotd(：a1withthoselarge-sca】esocialnetworks．Thispapel-proposedanSNAalgorithmthatextractionnodesbyaVerag

5、enodedegreeandclustertheneighbornodestoanalyzealarge—scalesocialnetworks．Firstly，wepropos‘：dlocalcorenodeexpa【nsionalgorimm，Ⅵ，hichextractsanodewithhighnodedegreeandoneofitsneighbors，gettheentirefirstnoorneighbornodes，thendiVideorcombinethepairsbythepercentageofsharednodes，by

6、thismethod，analyseallunVisitednodesinthecorrmunityuntilethec01nmunityisdivided．Secondly，basedonthisalgoritm，wep】oposedmulti．extensionidentifyandacyclicnodesremoVedide0109ical，thenmaderelatiVeexperiments．nnally，weapplythealgorithminlarge—scaleSNAcommunityminjngandverifiedthef

7、easibilityofthealgorithmthrou曲experiments．Basedonalotexperiment，aUtheresultshowsthisalgorithmisworked，andhaVealowertimecomplexityandahigherclassificationaccuracycomparedwithoth(。rSNAcommunit)，miningalgorithm，moreoVer，thisSNSalgorithmcanfreecontrolthesizeofminedcommurlitiesby

8、changethet11reshold．Keywords：Large．scaleSocialNetworks；SNAalgorithm；cluster