基于層次提取—局部聚類社區(qū)挖掘算法的研究

《基于層次提取—局部聚類社區(qū)挖掘算法的研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、基于層次提?。植烤垲惖纳鐓^(qū)挖掘算法摘要社會網(wǎng)絡(luò)是指社會個體成員之間因為互動而形成的相對穩(wěn)定的關(guān)系體系，其中聯(lián)系較為緊密的團體稱為社區(qū)，處在同一社區(qū)中的個體更易于受到社區(qū)內(nèi)其他人的影響，而社區(qū)挖掘技術(shù)就是挖掘網(wǎng)絡(luò)中存在的社區(qū)。然而大多數(shù)社區(qū)挖掘算法都是面向中小型網(wǎng)絡(luò)，當(dāng)處理結(jié)點數(shù)千萬級甚至上億級的網(wǎng)絡(luò)時，耗費巨大時間和資源，因而無法應(yīng)用。針對大型社會網(wǎng)絡(luò)社區(qū)結(jié)點和邊數(shù)量巨大、社區(qū)結(jié)構(gòu)復(fù)雜，普通社區(qū)挖掘算法挖掘效率低的問題，本文提出層次提?。植烤垲惖纳鐓^(qū)挖掘算法。首先提出局部聚類算法，即提取社區(qū)中某一結(jié)點度較高的結(jié)點為核心結(jié)點及某一鄰接結(jié)點，分

2、別對兩結(jié)點提取所有的鄰接結(jié)點，通過對這些結(jié)點中公共結(jié)點數(shù)量來判斷這兩個結(jié)點是否屬于同一社區(qū)，通過該方法依次以社區(qū)內(nèi)其他未被訪問結(jié)點為核心結(jié)點再進行判定，直至社區(qū)內(nèi)不存在未被訪問結(jié)點，重復(fù)該過程直至社區(qū)劃分完全；然后在該算法的基礎(chǔ)上進行改進，提出多層擴展及無環(huán)結(jié)點移除的改進思想，并通過實驗分析驗證可行性；最后將該算法應(yīng)用在大型社會網(wǎng)絡(luò)的社區(qū)挖掘中，對大型的社會網(wǎng)絡(luò)核心結(jié)點提取，采用層次提取的方法，減少了算法結(jié)點掃描次數(shù)，并通過實驗對算法的可行性進行了驗證。實驗結(jié)果表明該算法能有效的實現(xiàn)社區(qū)劃分，并且有著較低的時間復(fù)雜度和較高的劃分精度，并且可以通

3、過對閾值的調(diào)整，自由控制挖掘社區(qū)的大小及質(zhì)量。關(guān)鍵詞：社會網(wǎng)絡(luò)；社區(qū)挖掘；層次提??；局部聚類；無環(huán)節(jié)點；哈爾濱工程大學(xué)碩士學(xué)位論文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