大型網(wǎng)絡(luò)隨機化的社區(qū)挖掘算法

《大型網(wǎng)絡(luò)隨機化的社區(qū)挖掘算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、計算機研究與發(fā)展ISSN1000—12391CN1卜1777／TPJournalofComputerResearchandDevelopment46(Suppl．)：406—412，2009一種面向大型網(wǎng)絡(luò)的快速隨機化社區(qū)挖掘算法余韜肖仰華何震瀛汪衛(wèi)吳文濤(復(fù)旦大學(xué)計算機科學(xué)技術(shù)學(xué)院上海200433)(yyuuttaaoo@gmail．com)FastRandomizedAlgorithmforCommunityDetectioninLargeNetworksYuTao，XiaoYanghua，HeZhe

2、nying，WangWei，andWuWentao(SchoolofComputerScience，F(xiàn)udanUniversity，Shanghai200433)AbstractDetectingcommunitystructureisfundamentalforuncoveringtheorganizationprincipleofrealnetworks．Existingcommunitydetectionalgorithmsarenottractableforlargegraphs，inpartic

3、ularthegraphswithmillionsofnodes．However，proliferationoflarge-scalerealnetworkdatademandsnewmethodstoidentifycommunitiesefficientlyandeffectively．Forthispurpose，arandomizedalgorithmisproposedtoefficientlyminecommunitystructurewithhighqualityfromlargenetwo

4、rks．EachrandomizedstepofthenewalgorithmistorenumbertheverticesbyaDFSorder．SuchDFSrenumberingishelpfultoidentifytheedgesbetweencommunities．Finally，theeffectivenessandefficiencyofthenewalgorithmareshownbyexperimentalresultsonbothsyntheticandrealnetworks．Key

5、wordsrandomizedalgorithm；communitydetection；largenetworks摘要尋找網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)對于理解真實網(wǎng)絡(luò)的自組織機制、可視化大網(wǎng)絡(luò)有重要的作用．然而，現(xiàn)有的社區(qū)挖掘算法由于性能較低，還難以處理大型網(wǎng)絡(luò)，特別是有著百萬頂點的網(wǎng)絡(luò)．然而，百萬規(guī)模的大網(wǎng)絡(luò)卻在越來越多的真實應(yīng)用中大量涌現(xiàn)，這對于高效的有效社區(qū)識別算法提出新的需求．為此，一種新穎的隨機算法被提出，能夠在接近線性時間內(nèi)，從大型網(wǎng)絡(luò)上高效地挖掘質(zhì)量較高的網(wǎng)絡(luò)社區(qū)：新算法的核心思路是在每一隨機步驟中對網(wǎng)絡(luò)

6、中的頂點進行基于深度優(yōu)先順序的編碼，這樣的編碼有助于有效地識別社區(qū)之間的邊．最后，通過針對模擬網(wǎng)絡(luò)和真實網(wǎng)絡(luò)的一系列實驗驗證了新算法的高效，}生和有效性．關(guān)鍵詞隨機算法；社區(qū)挖掘；大惆絡(luò)中圖法分類號TP391近年來，大量的真實網(wǎng)絡(luò)數(shù)據(jù)大量涌現(xiàn)，常見的包括Www、互聯(lián)網(wǎng)、生物網(wǎng)絡(luò)和社會網(wǎng)絡(luò)．在各種網(wǎng)絡(luò)分析中，社區(qū)挖掘是最為常見的網(wǎng)絡(luò)分析任務(wù)之一，且已被成功地應(yīng)用于各種不同主題的網(wǎng)絡(luò)¨4]的分析中．通常，網(wǎng)絡(luò)上的一個社區(qū)劃分是指將網(wǎng)絡(luò)上的全部頂點劃分成若干分組，使得組內(nèi)頂點之間的鏈接密度顯著高于組間．尋找以及

7、評估網(wǎng)絡(luò)上的社區(qū)結(jié)構(gòu)不僅有助于人們理解網(wǎng)絡(luò)系統(tǒng)的功能和行收稿日期：2009一06—19基金項目：國家自然科學(xué)基金項目(60673133，60703093)，國家“九七三”重點基礎(chǔ)研究發(fā)展計劃基金項目(2005CB321905)；上海市重點學(xué)科建設(shè)基金項目(B114)余韜等：一種面向大型網(wǎng)絡(luò)的快速隨機化社區(qū)挖掘算法407為，也有助于改善大型網(wǎng)絡(luò)結(jié)構(gòu)的可視化．然而，在可接受的時間內(nèi)從網(wǎng)絡(luò)中挖掘較高質(zhì)量的社區(qū)結(jié)構(gòu)絕非易事．在某個給定的社團結(jié)構(gòu)質(zhì)量指標(biāo)的度量下，挖掘該指標(biāo)度量下最優(yōu)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)似乎是一個NP難的問

8、題，因為可能的社區(qū)劃分的數(shù)量與網(wǎng)絡(luò)規(guī)模呈指數(shù)關(guān)系．而近年來，迅速膨脹的網(wǎng)絡(luò)規(guī)模使得面向這些網(wǎng)絡(luò)的社區(qū)挖掘更加復(fù)雜．某些在線社會網(wǎng)絡(luò)，比如MySpace，F(xiàn)acebook上的交友網(wǎng)絡(luò)，其規(guī)模已經(jīng)達(dá)到數(shù)百萬的點和數(shù)億的邊∞]．現(xiàn)有的非線性社區(qū)發(fā)現(xiàn)算法顯然已經(jīng)難以勝任這一規(guī)模網(wǎng)絡(luò)上的社區(qū)分析．因此，我們迫切需要新的高效的方法來挖掘網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)．雖然已經(jīng)有大量的研究工作致力于各類大型網(wǎng)絡(luò)的社區(qū)挖掘，但是設(shè)計一個能夠保證挖掘質(zhì)量的高效