大連理工大學(xué)碩士學(xué)位論文摘要隨著WS小世界網(wǎng)絡(luò)模型和BA無標(biāo)度網(wǎng)絡(luò)模型的提出，國內(nèi)外掀起了研究復(fù)雜網(wǎng)絡(luò)的熱潮。復(fù)雜網(wǎng)絡(luò)的研究以系統(tǒng)的觀點來看待真實系統(tǒng)，如INTERNET網(wǎng)絡(luò)、電力網(wǎng)、新陳代謝網(wǎng)絡(luò)等。復(fù)雜網(wǎng)絡(luò)通常會呈現(xiàn)出社區(qū)結(jié)構(gòu)特性，如何在實際網(wǎng)絡(luò)中高效地發(fā)現(xiàn)社區(qū)結(jié)構(gòu)是近年來復(fù)雜網(wǎng)絡(luò)的研究熱點之一。本文基于譜算法的思想提出了一種基于共鄰矩陣和增益函數(shù)的有效算法來劃分復(fù)雜網(wǎng)絡(luò)中的社區(qū)，并把此算法推廣到了加權(quán)的復(fù)雜網(wǎng)絡(luò)中。主要工作如下1定義了共鄰矩陣和增益函數(shù)這兩個概念，在此基礎(chǔ)上提出一種有效算法來劃分復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。其中共鄰矩陣中的元素定義為結(jié)點對之間擁有相同鄰居的數(shù)目。以增益函數(shù)作為網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分的目標(biāo)函數(shù)，進一步推導(dǎo)出基于增益矩陣和增量矩陣的特征值和特征向量的社區(qū)結(jié)構(gòu)劃分方法。最后把這種算法應(yīng)用于三個常用的實際網(wǎng)絡(luò)數(shù)據(jù)中，并和NEWMAN基于模塊度矩陣的譜算法結(jié)果做了比較，以驗證算法的可行性和有效性。2重新定義了在加權(quán)網(wǎng)絡(luò)中結(jié)點對之間擁有共同鄰居的數(shù)目，把基于共鄰矩陣和增益函數(shù)的復(fù)雜網(wǎng)絡(luò)社區(qū)劃分算法推廣到加權(quán)的復(fù)雜網(wǎng)絡(luò)中。在以往許多復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法中，網(wǎng)絡(luò)中的邊常被看作是無權(quán)重的，但是現(xiàn)實世界中存在許多加權(quán)網(wǎng)絡(luò)。如果忽略邊的權(quán)重，僅僅把劃分無權(quán)網(wǎng)絡(luò)社區(qū)的算法應(yīng)用到這些加權(quán)網(wǎng)絡(luò)中，將會忽略許多包含在邊權(quán)重中的重要信息，從而得出不盡合理的結(jié)果。借鑒NEWMAN把加權(quán)網(wǎng)絡(luò)映射到無權(quán)多重圖的思想，重新定義了在加權(quán)網(wǎng)絡(luò)中結(jié)點對之間擁有共同鄰居的數(shù)目，然后將基于共鄰矩陣和增益函數(shù)的算法推廣到加權(quán)的網(wǎng)絡(luò)中，并把算法應(yīng)用到計算機仿真網(wǎng)絡(luò)和實際的加權(quán)網(wǎng)絡(luò)數(shù)據(jù)中，驗證了推廣算法的可行性和有效性。關(guān)鍵詞復(fù)雜網(wǎng)絡(luò)；社區(qū)結(jié)構(gòu)；共鄰矩陣；增益函數(shù)；加權(quán)網(wǎng)絡(luò)HTTP/INFO3DOUCOM/論壇推廣復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法研究PARTITIONINGMETHODSFORCOMMUNITYSTRUCTUREINCOMPLEXNETWORKSABSTRACTINRECENTYEARS，ASTHEWSSMALLWORLDNETWORKMODELANDBASCALEFREENETWORKMODELWASPROPOSED，THESTUDYONCOMPLEXNETWORKSISACHIEVINGACLIMAXATHOMEANDABROADNOWTHESTUDYONCOMPLEXNETWORKSTREATSTHEREALSYSTEMSSUCHASTHEINTERNET，ELECTRICITYNETWORKSANDMETABOLICNETWORKS、L，ITLLTHEVIEWPOINTOFSYSTEMSCIENCECOMMUNITYSTRUCTUREEXISTSINMANYREALNETWORKSHOWTOFINDSUCHCOMMUNITIESEFFECTIVELYISONEOFFOCUSESOFMANYRECENTRESEARCHESINTHEBRANCHOFCOMPLEXNETWORKSINTHISARTICLE，THEAUTHORPROPOSESAPARTITIONALMETHODBASEDONCOMMONNEIGHBOURSMATRIXANDGAINFUNCTIONANDGENERALIZESTHEMETHODTOWEIGHTEDNETWORKSTHEMAINWORKOFTHISPAPERCANBESUMMARIZEDASFOLLOWS1DEFININGTHECOMMONNEIGHBOURSMATRIXANDGAINFUNCTION,ANDPROPOSINGANEFFECTIVEMETHODOFANALYZINGTHECOMMUNITYSTRUCHLREINCOMPLEXNETWORKSBASEDONTHESETWOCONCEPTSTHEELEMENTSINCOMMONNEIGHBOURSMATRIXMEANSTHENUMBEROFCOMMONNEIGHBOURSBETWEENNODESWITHTHEGAINFUNCTIONASTHEOBJECTIVEFUNCTIONOFANALYZINGTHECOMMUNITYSTRUCTURE，WEDERIVEAPARTITIONMETHODBASEDONTHEEIGENVALUESANDEIGENVECTORSOFGAINMATRIXANDINCREMENTMATRIXFURTHERMORE，WEAPPLYTHISMETHODTOTHREECOMMONREALNETWORKDATAANDCOMPARETHECOMPUTATIONALRESULTSWITHMODULARITYBASEDANALYSISMETHODSPROPOSEDBYNEWMANCOMPUTATIONALRESULTSDEMONSTRATETHATTHEPROPOSEDMETHODISFEASIBLEANDEFFECTIVE2REDEFMINGTHECOMMONNEIGHBOURSBETWEENAPAIROFNODESINWEIGHEDNETWORKANDGENERALIZINGTHEALGORITHMBASEDONCOMMONNEIGHBOURSMATRIXANDGAINFUNCTIONTOWEIGHTEDNETWORKSALTHOUGHTHEREAREMANYWEIGHTEDNETWORKINTHEWORLD，NETWORKSAREUSUALLYCONSIDEREDTOBEUNWEIGHTEDINLOTSOFALGORITHMSFORCOMMUNITYSTRUCTUREINCOMPLEXNETWORKCERTAINLYTHEABOVEALGORITHMSCANBEAPPLIEDTOSUCHNETWORKSBYSIMPLYIGNORINGEDGEWEIGHTS，BUTTODOSOISTOTHROWAWAYUSEFULINFORMATIONCONTAINEDINTHEWEIGHTS，INFORMATIONTHATCOULDHELPUSTOMAKEAMOREACCURATEDETERMINATIONOFTHECOMMUNITIESINTHISPAPERWEUSETHETECHNIQUETHATWEIGHEDNETWORKSAREMAPPEDONTOMULTIGRAPHSPROPOSEDBYNEWMANANDREDEFINETHECOMMONNEIGHBOURSBETWEENAPAIROFNODESINWEIGHTEDNETWORKTHEN，THEALGORITHMBASEDONCOMMONNEIGHBOURSMATRIXANDGAINFUNCTIONISGENERALIZEDTOWEIGHTEDNETWORKSFURTHERMORE，WEAPPLYTHISMETHODTOACOMPUTERGENERATEDNETWORKANDAREALSOCIALNETWORKCOMPUTATIONALRESULTSDEMONSTRATETHATTHEPROPOSEDMETHODISFEASIBLEANDEFFECTIVE一IIHTTP/INFO3DOUCOM/論壇推廣大連理工大學(xué)碩士學(xué)位論文KEYWORDSCOMPLEXNETWORK；COMMUNITYSTRUCTURE；COMMONNEIGHBOURSMATRIX；GAINFUNCTION；WEIGHTEDNETWORK111HTTP/INFO3DOUCOM/論壇推廣大連理工大學(xué)學(xué)位論文獨創(chuàng)性聲明作者鄭重聲明所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下進行研究工作所取得的成果。盡我所知，除文中已經(jīng)注明引用內(nèi)容和致謝的地方外，本論文不包含其他個人或集體已經(jīng)發(fā)表的研究成果，也不包含其他已申請學(xué)位或其他用途使用過的成果。與我一同工作的同志對本研究所做的貢獻均已在論文中做了明確的說明并表示了謝意。若有不實之處，本人愿意承擔(dān)相關(guān)法律責(zé)任。學(xué)位論文題目堡壘塑蘭墨疊堡至查塑蘭笪望墨塑庭作者簽名繼塑芒日期4年L月J魚日HTTP/INFO3DOUCOM/論壇推廣大連理工大學(xué)碩士學(xué)位論文大連理工大學(xué)學(xué)位論文版權(quán)使用授權(quán)書本人完全了解學(xué)校有關(guān)學(xué)位論文知識產(chǎn)權(quán)的規(guī)定，在校攻讀學(xué)位期間論文工作的知識產(chǎn)權(quán)屬于大連理工大學(xué)，允許論文被查閱和借閱。學(xué)校有權(quán)保留論文并向國家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和電子版，可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索，可以采用影印、縮印、或掃描等復(fù)制手段保存和匯編本學(xué)位論文。學(xué)位論文題目作者簽名導(dǎo)師簽名日期竺12年生月魚日日期4年上月止日HTTP/INFO3DOUCOM/論壇推廣大連理工大學(xué)碩士學(xué)位論文1緒論11復(fù)雜網(wǎng)絡(luò)研究的背景與意義20世紀(jì)90年代以來，以INTERNET為代表的信息技術(shù)的迅猛發(fā)展使人類社會大步邁入了網(wǎng)絡(luò)時代。從INTERNET到WWW，從大型電力網(wǎng)絡(luò)到全球交通網(wǎng)絡(luò)，從生物體中的大腦到各種新陳代謝網(wǎng)絡(luò)，從科研合作網(wǎng)絡(luò)到各種經(jīng)濟、政治和社會關(guān)系網(wǎng)絡(luò)等，可以說；人們已經(jīng)生活在一個充滿著各種各樣的復(fù)雜網(wǎng)絡(luò)的世界中。人類社會的網(wǎng)絡(luò)化是一把“雙刃劍”它既給人類社會生產(chǎn)與生活帶來了極大便利，提高了人類生產(chǎn)效率和生活質(zhì)量，但也給人類社會生活帶來了一定的負面沖擊，如傳染病和計算機病毒的快速傳播以及大規(guī)模的停電事故等。因此，人類社會的日益網(wǎng)絡(luò)化需要人類對各種人工和自然的復(fù)雜網(wǎng)絡(luò)的行為有更好的認識。長期以來，通信網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、社會網(wǎng)絡(luò)等分別是通信科學(xué)、電力科學(xué)、生命科學(xué)、社會學(xué)等不同學(xué)科的研究對象，而復(fù)雜網(wǎng)絡(luò)理論所要研究的則是各種看上去互不相同的復(fù)雜網(wǎng)絡(luò)之間的共性和處理它們的普適方法。從20世紀(jì)末開始，復(fù)雜網(wǎng)絡(luò)研究正滲透到數(shù)理學(xué)科、生命學(xué)科和工程學(xué)科等眾多不同的領(lǐng)域，對復(fù)雜網(wǎng)絡(luò)的定量與定性特征的科學(xué)理解，已成為網(wǎng)絡(luò)時代科學(xué)研究的一個極其重要的挑戰(zhàn)性課題心31，甚至被稱為“網(wǎng)絡(luò)的新科學(xué)NEWSCIENCEOFNETWORKS”。傳統(tǒng)的對網(wǎng)絡(luò)的研究最早起源于著名的歐拉七橋問題。之后的近兩百年中，數(shù)學(xué)家們一直致力于對簡單的規(guī)則網(wǎng)絡(luò)和隨機網(wǎng)絡(luò)進行抽象的數(shù)學(xué)研究。隨著近年來計算機存儲能力和處理數(shù)據(jù)能力的增強，以及一些大規(guī)模系統(tǒng)的數(shù)據(jù)庫的建立，人們重新獲得了真實網(wǎng)絡(luò)的特征數(shù)據(jù)，發(fā)現(xiàn)大多數(shù)真實網(wǎng)絡(luò)既不是規(guī)則的，也不是隨機的，而是呈現(xiàn)一定規(guī)律的復(fù)雜網(wǎng)絡(luò)H。復(fù)雜網(wǎng)絡(luò)之所以復(fù)雜，不僅在于網(wǎng)絡(luò)規(guī)模的巨大，網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜而且網(wǎng)絡(luò)在時間、空間上都具有動態(tài)的復(fù)雜性，網(wǎng)絡(luò)行為也具有復(fù)雜性。許多真實系統(tǒng)都可以用網(wǎng)絡(luò)的形式加以描述，一個典型的網(wǎng)絡(luò)是由許多結(jié)點與連接結(jié)點之間的邊組成的。結(jié)點代表系統(tǒng)中的個體，邊則表示結(jié)點之間的作用關(guān)系。如WWW網(wǎng)絡(luò)可以看成是網(wǎng)頁之間通過超鏈接構(gòu)成的網(wǎng)絡(luò)璐3；INTERNET網(wǎng)絡(luò)可以看作不同的計算機通過光纜連接構(gòu)成的網(wǎng)絡(luò)嵋1科學(xué)家合作網(wǎng)絡(luò)可以看作不同的科學(xué)家合作關(guān)系構(gòu)成的網(wǎng)絡(luò)盯81基因調(diào)控網(wǎng)絡(luò)可以看作是不同的基因通過調(diào)控與被調(diào)控關(guān)系構(gòu)成的網(wǎng)絡(luò)舊1。這些真實網(wǎng)絡(luò)的普遍存在，促使來自不同學(xué)科領(lǐng)域的科學(xué)家共同致力于復(fù)雜網(wǎng)絡(luò)的研究。這些學(xué)科領(lǐng)域包括復(fù)雜性科學(xué)、數(shù)學(xué)、物理、生物和計算機等。復(fù)雜網(wǎng)絡(luò)的研究HTTP/INFO3DOUCOM/論壇推廣復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法研究可以使人們更好地了解現(xiàn)實世界的復(fù)雜系統(tǒng)，為設(shè)計具有良好性能的網(wǎng)絡(luò)提供依據(jù)。同時復(fù)雜網(wǎng)絡(luò)的理論成果將會廣泛地應(yīng)用到生物、計算機等各個學(xué)科領(lǐng)域。復(fù)雜網(wǎng)絡(luò)的研究大致可以描述為三個密切相關(guān)但又依次深入的方面大量的真實網(wǎng)絡(luò)的實證研究，分析真實網(wǎng)絡(luò)的統(tǒng)計特性構(gòu)建符合真實網(wǎng)絡(luò)統(tǒng)計性質(zhì)的網(wǎng)絡(luò)演化模型，研究網(wǎng)絡(luò)的形成機制和內(nèi)在機理研究網(wǎng)絡(luò)上的動力學(xué)行為，如網(wǎng)絡(luò)的魯棒性和同步能力，網(wǎng)絡(luò)的擁塞及網(wǎng)絡(luò)上的傳播行為等。當(dāng)把一個系統(tǒng)描述為網(wǎng)絡(luò)的形式后，就可以通過分析網(wǎng)絡(luò)的統(tǒng)計性質(zhì)，如網(wǎng)絡(luò)的度分布，網(wǎng)絡(luò)的簇系數(shù)，網(wǎng)絡(luò)的平均最短距離等來描述真實網(wǎng)絡(luò)N叫引。大量的實證研究表明許多真實世界的網(wǎng)絡(luò)具有兩個基本性質(zhì)小世界特性SMALLWORLDCHARACTERN司和無標(biāo)度特性SCALEFREECHARACTERN剛。小世界特性是指與相同規(guī)模的隨機網(wǎng)絡(luò)相比，該網(wǎng)絡(luò)具有較小的平均最短距離和較大的簇系數(shù)。1967年，美國哈佛大學(xué)社會心里學(xué)家MILGRAM做了一個實驗，在美國將一封信通過熟人找熟人的方式傳遞到目標(biāo)者，發(fā)現(xiàn)平均最短經(jīng)過6人就可到達，這就是著名的“六度分離SIXDEGREEOFSEPARATION”現(xiàn)象，它揭示了社會網(wǎng)絡(luò)的小世界特性。而在萬維網(wǎng)嗍中，平均只需點擊19次超級鏈接，就可以從任意一個網(wǎng)頁到達其它網(wǎng)頁鄙。大量的小世界網(wǎng)絡(luò)的普遍存在，促使人們探討形成這種網(wǎng)絡(luò)的內(nèi)在機理。1998年，學(xué)者WATTS和STROGATZ在規(guī)則網(wǎng)絡(luò)中引入隨機性，建立了著名的小世界網(wǎng)絡(luò)模型WS小世界網(wǎng)絡(luò)模型N翻，很好地描述了真實網(wǎng)絡(luò)的小世界特性。1999年，學(xué)者BARABASI和ALBERT通過對萬維網(wǎng)的數(shù)據(jù)進行統(tǒng)計分析發(fā)現(xiàn)萬維網(wǎng)的度分布服從冪律分布，在雙對數(shù)坐標(biāo)系下是一條下降的直線，由于冪律分布具有標(biāo)度不變性，缺乏一個特征度值，因此稱這種度分布服從冪律分布的網(wǎng)絡(luò)為無標(biāo)度網(wǎng)絡(luò)SCALEFREENETWORKN明。之后的研究表明，許多社會網(wǎng)絡(luò)如科學(xué)家合作網(wǎng)絡(luò)口81、生物網(wǎng)絡(luò)中的新陳代謝網(wǎng)絡(luò)N刀和技術(shù)網(wǎng)絡(luò)中的INTERNET網(wǎng)絡(luò)3等都是無標(biāo)度網(wǎng)絡(luò)。這些來自不同領(lǐng)域的大規(guī)模系統(tǒng)呈現(xiàn)了共同的普適規(guī)律，促使人們?nèi)ヌ剿麟[藏在這些表象后的內(nèi)在演化機制，從此掀起了研究復(fù)雜網(wǎng)絡(luò)的熱潮。近年來，隨著大型數(shù)據(jù)庫的建立和計算機存儲與運算能力的迅速提高，復(fù)雜網(wǎng)絡(luò)的研究進程大大加快。人們對社會系統(tǒng)、大型基礎(chǔ)性設(shè)施和生物系統(tǒng)中大量的真實網(wǎng)絡(luò)數(shù)據(jù)庫進行了系統(tǒng)的分析，尋找呈現(xiàn)表象的內(nèi)在機制和模式，試圖發(fā)現(xiàn)支配和影響這些復(fù)雜系統(tǒng)的動力學(xué)和演化規(guī)律的內(nèi)在本質(zhì)。復(fù)雜網(wǎng)絡(luò)的理論及實證研究的發(fā)展將會對網(wǎng)絡(luò)安全、網(wǎng)絡(luò)控制、疾病傳播的控制與防御、社會中人的行為動力學(xué)的研究和生物網(wǎng)絡(luò)的演化機制研究等產(chǎn)生重要影響。HTTP/INFO3DOUCOM/論壇推廣大連理工大學(xué)碩士學(xué)位論文12復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)研究現(xiàn)狀隨著對網(wǎng)絡(luò)性質(zhì)的物理意義和數(shù)學(xué)特性的深入研究，人們發(fā)現(xiàn)許多實際網(wǎng)絡(luò)都具有一個共同性質(zhì)，即社區(qū)結(jié)構(gòu)。也就是說，整個網(wǎng)絡(luò)是由若干個“社區(qū)“或“組構(gòu)成的。每個社區(qū)內(nèi)部的結(jié)點間的連接相對非常緊密，但是各個社區(qū)之間的連接相對來說卻比較稀疏N81訓(xùn)。揭示網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，對于深入了解網(wǎng)絡(luò)結(jié)構(gòu)與分析網(wǎng)絡(luò)特性是很重要的。如社會網(wǎng)絡(luò)中的社區(qū)代表根據(jù)興趣和背景而形成的真實的社會團體；引文網(wǎng)絡(luò)中的社區(qū)代表針對同一主題的相關(guān)論文；萬維網(wǎng)中的社區(qū)就是討論相關(guān)主題的若干網(wǎng)站U7一；而生物化學(xué)網(wǎng)絡(luò)或者電子電路中的網(wǎng)絡(luò)社區(qū)可以是某一類功能單元幢“捌。發(fā)現(xiàn)這些網(wǎng)絡(luò)中的社區(qū)有助于我們更加有效地理解和開發(fā)這些網(wǎng)絡(luò)。在復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分的研究中，社區(qū)結(jié)構(gòu)劃分算法所要劃分的網(wǎng)絡(luò)大致可分為兩類，一類是比較常見的網(wǎng)絡(luò)，即僅包含正聯(lián)系的網(wǎng)絡(luò)網(wǎng)絡(luò)中邊的權(quán)值為正實數(shù)；另一類是符號社會網(wǎng)絡(luò)，即網(wǎng)絡(luò)中既包含正向聯(lián)系的邊，也包含負向聯(lián)系的邊。因此劃分網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的算法相應(yīng)分為兩大類，而對于第一類網(wǎng)絡(luò)又提出了許多不同的社區(qū)結(jié)構(gòu)劃分算法，劃分第一類網(wǎng)絡(luò)社區(qū)的傳統(tǒng)算法可分為兩大類，第一類是基于圖論的算法，比如KL算法晗羽、譜平分法盼釓刪、隨機游走算法啪3和派系過濾算法口7勰3等；第二類是層次聚類算法，比如基于相似度度量的凝聚算法N劬和基于邊介數(shù)度量的分裂算法N墨觀制等。最近幾年從其他不同的角度又提出了許多劃分第一類網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的算法，大致可劃分如下基于電阻網(wǎng)絡(luò)性質(zhì)的算法騶、基于信息論的算法B船、基于PCA的算法羽和最大化模塊度們的算法州等。對于符號網(wǎng)絡(luò)，DOREIAN和MRVAR提出了一種利用局部搜索劃分符號網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的算法H，而YANG等提出一種基于代理的啟發(fā)式劃分符號網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的算法FECH羽。下面簡要介紹一下幾種具有代表性的算法。1970年，KERNIGHAN和LIN提出一種試探優(yōu)化法劃分網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，簡稱KL算法。它是一種基于貪婪算法原理將網(wǎng)絡(luò)劃分為兩個大小已知的社區(qū)的二分法。其基本思想是為網(wǎng)絡(luò)的劃分引進一個增益函數(shù)Q，增益函數(shù)定義為兩個社區(qū)內(nèi)部的邊數(shù)減去連接兩個社區(qū)之間的邊數(shù)，然后尋找使Q值最大的劃分方法。1990年，POTHEN等基于圖的LAPLACE矩陣的譜特征提出一種將網(wǎng)絡(luò)劃分為兩個社區(qū)的二分法瞻目。該算法的理論基礎(chǔ)是不為零的特征值所對應(yīng)的特征向量的各元素中，同一個社區(qū)內(nèi)的結(jié)點對應(yīng)的元素是近似相等的。因此可以根據(jù)網(wǎng)絡(luò)的LAPLACE矩陣的第二小特征值將其分為兩個社區(qū)。2001年，GIRVAN和NEWMAN提出了一種基于邊介數(shù)的分裂算法，簡稱GN算法N81。該算法的基本思想是不斷地從網(wǎng)絡(luò)中移除介數(shù)最大的邊。邊介數(shù)定義為網(wǎng)絡(luò)中經(jīng)過每條邊的最短路徑數(shù)目。該算法的復(fù)雜度非常高，2003年TYLER等在GN算法的基礎(chǔ)上提出HTTP/INFO3DOUCOM/論壇推廣復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法研究了一種新的算法圓1，它可以顯著提高計算速度，但也降低了計算的準(zhǔn)確性。GN算法是以網(wǎng)絡(luò)中的每一個結(jié)點I為源結(jié)點，來計算它到其他結(jié)點的最短路徑，并以這些最短路徑經(jīng)過每條邊的次數(shù)作為該邊的介數(shù)。而TYLER等人提出，以網(wǎng)絡(luò)中某個結(jié)點集內(nèi)的結(jié)點為源結(jié)點來計算邊的介數(shù)也可以達到較好的效果。2004年，NEWMAN把GN算法推廣到了加權(quán)網(wǎng)絡(luò)中H副。2003年，WU和HUBERMAN基于電阻網(wǎng)絡(luò)的性質(zhì)提出了W_H算法3，其主要思路為將網(wǎng)絡(luò)中每條邊想象成電阻為單位值的導(dǎo)線，且在網(wǎng)絡(luò)中任意選擇的兩個結(jié)點上加上單位值的電位差。WU和HUBERMAN認為，如果網(wǎng)絡(luò)可以分解成兩個社區(qū)，那么電位譜在連接兩個社區(qū)的邊的兩端會產(chǎn)生一個較大的間隙。因此，首先確定電位譜的最大間隙處的某個電位值，然后根據(jù)每個結(jié)點處的電位是否大于該值而確定結(jié)點屬于哪個社區(qū)。該算法的一個重要特點是可以用來確定包含指定結(jié)點的社區(qū)，而無須計算出所有的社區(qū)。2004年，NEWMAN提出一種基于貪婪法思想的凝聚算法N9I，并稱這種算法為快速算法。該算法是在使得模塊度不斷增加的基礎(chǔ)上進行，即每次合并沿著使模塊度增多最大和減小最少的方向進行。算法總的復(fù)雜度為D研刀咖，對于稀疏網(wǎng)絡(luò)則為ON2，其中N為網(wǎng)絡(luò)中結(jié)點的個數(shù)，M為網(wǎng)絡(luò)中邊的條數(shù)。在NEWMAN快速算法的基礎(chǔ)上，CLAUSET、NEWMAN和MOORE等人采用堆的數(shù)據(jù)結(jié)構(gòu)來計算和更新網(wǎng)絡(luò)的模塊度，提出了一種新的貪婪算法，稱為CNM算法啪1。該算法的復(fù)雜度只有ONL092刀，已接近線性復(fù)雜性，可用來分析大型復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)。同樣為了最大化網(wǎng)絡(luò)的模塊度，2006年NEWMAN基于模塊度矩陣提出一種劃分網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的譜算法M1，并于2008年把該算法推廣到有向網(wǎng)絡(luò)中443O2005年，PONS和LATAPY提出一種利用隨機游走劃分網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的算法嘶3，算法的初始條件為每個結(jié)點為一個單獨的社區(qū)，然后逐步合并可使結(jié)點和它所在社區(qū)之間的平方距離均值達到最小的兩個社區(qū)。每一步都要更新社區(qū)之間的距離，其中兩個結(jié)點之間的距離對應(yīng)于它們的相似度，即在一個離散的隨機游走過程中，它們之間的方向轉(zhuǎn)移概率。大多數(shù)社會網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法僅適用于包含正聯(lián)系的網(wǎng)絡(luò)，而不適合符號網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)劃分。在符號社會網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)中，不僅社區(qū)內(nèi)部的正聯(lián)系比較多，而且社區(qū)之間的負聯(lián)系也比較多。1996，DOREIAN和RRVART提出了一種利用局部搜索劃分符號社會網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的算法1。這種算法本質(zhì)上是一種基于貪婪策略的算法，通過最小化一個預(yù)定義的誤差函數(shù)把網(wǎng)絡(luò)劃分為幾個社區(qū)。誤差函數(shù)的定義為社區(qū)內(nèi)部負向聯(lián)系和社區(qū)之間正向聯(lián)系權(quán)重絕對值的和。算法的初始條件為隨機的把結(jié)點劃分到已HTTP/INFO3DOUCOM/論壇推廣大連理工大學(xué)碩士學(xué)位論文知數(shù)量的社區(qū)中，然后計算對于初始劃分的誤差函數(shù)值。為了減小誤差函數(shù)的值，把結(jié)點從一個社區(qū)移動到另外一個社區(qū)，結(jié)點的移動直到誤差函數(shù)不再減少為止。算法復(fù)雜度為D迭代次數(shù)奉刀2，其中迭代次數(shù)為結(jié)點移動的次數(shù)，N為網(wǎng)絡(luò)中結(jié)點的個數(shù)。該算法的缺陷為必須事先知道要劃分的社區(qū)的數(shù)目且依賴于初始劃分，并且該算法僅考慮到邊的符號而沒有考慮邊的密度。2007年YANG等人提出了一種基于代理的啟發(fā)式方法劃分符號社會網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，并稱這種算法為FEC算法H羽。該算法分為兩個階段，第一個階段為FC階段，即計算其他所有結(jié)點經(jīng)過一定數(shù)量的步長到達匯結(jié)點SINKNODE的概率；第二個階段為定義一個截斷標(biāo)準(zhǔn)，找出匯結(jié)點所在的社區(qū)。該算法效率比較高，為O，Z，其中N為網(wǎng)絡(luò)中結(jié)點的個數(shù)，并且能給出接近最優(yōu)解的解。以上所述算法最終目的均是把網(wǎng)絡(luò)劃分為若干個相互分離的社區(qū)，但是現(xiàn)實中很多網(wǎng)絡(luò)并不存在絕對的彼此獨立的社區(qū)結(jié)構(gòu)，相反它們是由許多彼此重疊且相互關(guān)聯(lián)的社區(qū)構(gòu)成。比如，每個人根據(jù)不同的分類方法都會屬于多個不同的社區(qū)如學(xué)校、家庭、不同的興趣小組等。在這種情況下，很難單獨的將這些社區(qū)劃分出來。因此，PALLA等人提出了一種派系過濾算法CLIQUEPERCOLATIONMETHOD來分析這種互相重疊的社區(qū)結(jié)構(gòu)3。盡管復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問題得到了大量的研究，但還存在一些尚未解決的基本問題，如社區(qū)概念雖然大量使用，但卻缺少嚴(yán)格的數(shù)學(xué)定義；大多數(shù)社區(qū)發(fā)現(xiàn)算法雖然性能優(yōu)越，但所需計算量卻很大。這說明復(fù)雜網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)的研究還需要付出大量的努力蜘。13本文的研究內(nèi)容與文章結(jié)構(gòu)本課題主要研究復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)劃分。首先，針對無權(quán)的復(fù)雜網(wǎng)絡(luò)，提出了共鄰矩陣和增益函數(shù)的概念，在此基礎(chǔ)上提出一種有效的劃分社區(qū)結(jié)構(gòu)的算法。實驗結(jié)果表明該算法是可行且有效的。最后把這種算法推廣到加權(quán)的復(fù)雜網(wǎng)絡(luò)中，并把算法應(yīng)用到計算機仿真網(wǎng)絡(luò)和實際的加權(quán)網(wǎng)絡(luò)數(shù)據(jù)中，驗證了推廣算法的可行性和有效性。綜上所述，本文主要研究內(nèi)容共分為兩個部分第一部分提出了一種基于共鄰矩陣和增益函數(shù)的復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法；第二部分把此算法推廣到加權(quán)的復(fù)雜網(wǎng)絡(luò)中。具體內(nèi)容如下第二章首先介紹了復(fù)雜網(wǎng)絡(luò)的圖表示、度分布、平均最短路徑和社區(qū)結(jié)構(gòu)等基本概念和基本性質(zhì)。然后詳細介紹了幾種劃分復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)算法的基本思想和特點，包括無權(quán)網(wǎng)絡(luò)和加權(quán)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)劃分算法。HTTP/INFO3DOUCOM/論壇推廣復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法研究第三章從社區(qū)內(nèi)部結(jié)點對之間應(yīng)該擁有更多的共同鄰居出發(fā)，提出了基于共鄰矩陣和增益函數(shù)的復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法。把這種網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分方法應(yīng)用于空手道俱樂部網(wǎng)絡(luò)、海豚網(wǎng)絡(luò)和政治書籍網(wǎng)絡(luò)三個常用的實際網(wǎng)絡(luò)數(shù)據(jù)中，并和NEWMAN基于模塊度矩陣的譜算法結(jié)果做了比較，數(shù)值實驗結(jié)果表明本文提出的方法是可行且有效的。第四章重新定義了在加權(quán)網(wǎng)絡(luò)中結(jié)點對之間擁有共同鄰居的數(shù)目，把基于共鄰矩陣和增益函數(shù)的復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法推廣到加權(quán)的復(fù)雜網(wǎng)絡(luò)中。在以往許多復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法中，網(wǎng)絡(luò)中的邊常被看作是無權(quán)重的，但是現(xiàn)實世界中卻存在許多加權(quán)網(wǎng)絡(luò)。如果忽略邊的權(quán)重，僅僅把劃分無權(quán)網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的算法應(yīng)用到加權(quán)網(wǎng)絡(luò)中，將會忽略許多包含在邊權(quán)重中的重要信息，得出不合理的結(jié)果。借鑒NEWMAN把加權(quán)網(wǎng)絡(luò)映射到無權(quán)多重圖的思想，重新定義了在加權(quán)網(wǎng)絡(luò)中結(jié)點對之間擁有共同鄰居的數(shù)目，然后將基于共鄰矩陣和增益函數(shù)的算法推廣到加權(quán)的網(wǎng)絡(luò)中，并把算法應(yīng)用到計算機仿真網(wǎng)絡(luò)和實際的加權(quán)網(wǎng)絡(luò)數(shù)據(jù)中，驗證了推廣算法的可行性和有效性。最后對全文的工作進行了總結(jié)，并對今后的工作和發(fā)展方向提出了展望。HTTP/INFO3DOUCOM/論壇推廣大連理工大學(xué)碩士學(xué)位論文2復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法概述21復(fù)雜網(wǎng)絡(luò)基本性質(zhì)211真實網(wǎng)絡(luò)的圖表示首先，簡單介紹有關(guān)圖的定義和基本概念。圖G可以表示為集合，9，G1，2，表示圖G的頂點集合，N表示網(wǎng)絡(luò)的頂點總數(shù)，9G，五，之，五，名，止代表邊集合，E表示總邊數(shù)，如果F，JJF，F(xiàn)，則圖是無向圖，否則為有向圖。當(dāng)網(wǎng)絡(luò)是無向無權(quán)網(wǎng)絡(luò)時，鄰接矩陣A概，是一個01對稱矩陣，表示圖中頂點之間的連接關(guān)系。如果頂點F，歹之間有連接，則1否則AO0。當(dāng)網(wǎng)絡(luò)是有向圖時，鄰接矩陣A是非對稱的01矩陣當(dāng)網(wǎng)絡(luò)是加權(quán)網(wǎng)絡(luò)時，A中的非零元素代表邊的權(quán)重。212度分布度分布是描述網(wǎng)絡(luò)性質(zhì)的一個重要統(tǒng)計量。結(jié)點I的度定義為與結(jié)點F連接的邊的數(shù)目。度分布PJJ定義為隨機地選擇一個結(jié)點，度為K的概率，或者等價地描述為網(wǎng)絡(luò)中度為后的結(jié)點數(shù)占網(wǎng)絡(luò)結(jié)點總數(shù)的比例。當(dāng)然，對于有向網(wǎng)絡(luò)，其度分布還可細致地分為網(wǎng)絡(luò)的入度分布INDEGREEDISTRIBUTION和出度分布OUTDEGREEDISTRIBUTION。近年來大量的實證研究表明，許多真實網(wǎng)絡(luò)的度分布都遵循冪律分布，數(shù)學(xué)形式為P后K，其中Y一般介于2到3之間。冪函數(shù)在雙對數(shù)坐標(biāo)系下是一條下降的直線，如WWWH71的度分布，如圖21B所示。與指數(shù)函數(shù)相比，冪函數(shù)下降速度較慢，使得網(wǎng)絡(luò)中存在度較大的結(jié)點，通常稱這些結(jié)點為集散結(jié)點HUBNODE。研究發(fā)現(xiàn)除了冪律分布，真實網(wǎng)絡(luò)中還存在其它形式的度分布，如電力網(wǎng)絡(luò)N司的度分布服從指數(shù)分布，在單對數(shù)坐標(biāo)系下是一條下降的直線；也存在冪律加指數(shù)截斷的度分布的網(wǎng)絡(luò)，如電影演員合作網(wǎng)絡(luò)口61，如圖21A所示，以及蛋白質(zhì)相互作用網(wǎng)絡(luò)。213網(wǎng)絡(luò)的平均最短路徑和頂點的介數(shù)網(wǎng)絡(luò)的平均最短距離AVERAGEPATHLENGTH定義為網(wǎng)絡(luò)中任意一對結(jié)點之間的最短距離的平均值，數(shù)學(xué)表達式為1一D二辦21NN1F篇8。HTTP/INFO3DOUCOM/論壇推廣復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法研究其中辦為結(jié)點F，J之間的最短路徑的長度。所有結(jié)點間的最短路徑長度的最大值稱為網(wǎng)絡(luò)半徑NETWORKDIAMETER。大多數(shù)真實網(wǎng)絡(luò)具有較小的平均最短距離，如具有153127個結(jié)點的萬維網(wǎng)WWW的平均最短距離為31H釘，大腸桿菌的代謝網(wǎng)絡(luò)的平均最短距離為24648】。訂塒O礦衛(wèi)，軋礦1LFI礦圖21不同類型的大規(guī)模網(wǎng)絡(luò)的度分布。A電影演員合作網(wǎng)絡(luò)，網(wǎng)絡(luò)規(guī)模為N212，250，七2878；B唧網(wǎng)絡(luò)，網(wǎng)絡(luò)規(guī)模為N325，729，七546。度分布的冪指數(shù)，一23，21，引自文16。FIG21THEDISTRIBUTIONFUNCTIONSOFEONNECTIVITIESFORVARIOUSLARGENETWORKSAACTORCOLLABORATIONGRAPHWITHN212250NODESANDAVERAGECONNECTIVITY2878BWWW，N325，729，54611他DASHEDLINESHAVESLOPESAY礎(chǔ)，23，BY刪21REF16網(wǎng)絡(luò)中不相鄰的結(jié)點歹和K之間的路徑主要依賴于連接結(jié)點歹和K的路徑上所經(jīng)過的結(jié)點，如果某個結(jié)點被其它許多路徑經(jīng)過，則表示該結(jié)點在網(wǎng)絡(luò)中很重要。定量地描某個結(jié)點在網(wǎng)絡(luò)中的影響力或重要性可以用頂點的介數(shù)NODEBETWEENESS來衡量，這一定義最早由FREEMAN在1977年提出呻。頂點F的介數(shù)置定義為22業(yè)歸忍HTTP/INFO3DOUCOM/論壇推廣大連理工大學(xué)碩士學(xué)位論文其中擰硪表示結(jié)點J、后之間的最短路徑的個數(shù)，NJ,I表示結(jié)點J、七之間的最短路徑中經(jīng)過結(jié)點I的個數(shù)。214網(wǎng)絡(luò)的簇系數(shù)網(wǎng)絡(luò)的簇系數(shù)CLUSTERINGCOEFFICIENT是衡量網(wǎng)絡(luò)集團化程度的重要參數(shù)，是一個局部特征量。結(jié)點F的簇系數(shù)G定義為結(jié)點F的鄰接點之間實際存在的邊數(shù)與所有可能的邊數(shù)的比值，數(shù)學(xué)表達為C生一23。匆毛I其中，毛表示結(jié)點F的度，E，表示結(jié)點F的鄰接點之間實際存在的邊數(shù)。網(wǎng)絡(luò)的簇系數(shù)定義為對所有結(jié)點的簇系數(shù)做和求平均NC專C，24J，一VT許多真實網(wǎng)絡(luò)具有較大的簇系數(shù)和較小的平均最短距離。這里“較大的簇系數(shù)指真實網(wǎng)絡(luò)的簇系數(shù)遠遠大于相同規(guī)模的隨機網(wǎng)絡(luò)的簇系數(shù)。“較小的平均最短距離指平均最短距離隨網(wǎng)絡(luò)規(guī)模的增加呈對數(shù)或者更小增長。22復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)定義近幾年來，復(fù)雜網(wǎng)絡(luò)的研究正處于蓬勃發(fā)展的階段，其思想已經(jīng)充斥到科學(xué)和社會的每一個角落。隨著對網(wǎng)絡(luò)性質(zhì)的物理意義和數(shù)學(xué)特性的深入研究，人們發(fā)現(xiàn)許多實際網(wǎng)絡(luò)都具有一個共同性質(zhì)社區(qū)結(jié)構(gòu)。也就是說，網(wǎng)絡(luò)是由若干個“群GROUP“或“團CLUSTER構(gòu)成的。每個群內(nèi)的結(jié)點之間的連接非常緊密，而群之間的連接卻相對比較稀疏N1，如圖22所示。圖中的網(wǎng)絡(luò)包含三個社區(qū)，分別對應(yīng)圖中三個虛線圓圈包圍的部分。在這些社區(qū)內(nèi)部，結(jié)點之間的聯(lián)系非常緊密，而社區(qū)之間的聯(lián)系就稀疏得多。一般而言，社區(qū)可以包含模塊、類、群和組等各種含義。例如，萬維網(wǎng)可以看成是由大量網(wǎng)站社區(qū)組成，其中同一個社區(qū)內(nèi)部的各個網(wǎng)站所討論的都是一些有共同興趣的話題N7閽3。類似地，在生物網(wǎng)絡(luò)或者電路網(wǎng)絡(luò)中，同樣可以將各個結(jié)點根據(jù)其不同的性質(zhì)劃分為不同的社區(qū)瞳H翻。揭示網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，對于了解網(wǎng)絡(luò)結(jié)構(gòu)與分析網(wǎng)絡(luò)特性具有極為重要的意義。社區(qū)結(jié)構(gòu)分析在生物學(xué)、物理學(xué)、計算機圖形學(xué)和社會學(xué)中都有廣泛的應(yīng)用N8剛。HTTP/INFO3DOUCOM/論壇推廣復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法研究圖22一個小型的具有社區(qū)結(jié)構(gòu)性質(zhì)的網(wǎng)絡(luò)示意圖。引自文1。FIG22ASMALLNETWORKWITHCOMMUNITYSTRUCTUREREF123復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的研究已經(jīng)有很長的歷史。為了能夠準(zhǔn)確有效地分析復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，人們提出了多種不同的社區(qū)結(jié)構(gòu)劃分算法，這些算法的目的是利甩盡量少的信息得到盡量準(zhǔn)確地網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)，從而更好地分析網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的基本特點和共同特性。早期分析社區(qū)結(jié)構(gòu)的算法，包括計算機科學(xué)中的圖形分割GRAPHPARTITION和社會學(xué)中的層次聚類HIERARCHICALCLUSTERING兩種晦1嘲，前者主要包括KERNIGHANLIN算法嘲和基于圖的LAPLACE矩陣特征向量的譜平分法SPECTRALBISECTIONMETHOD幽踟；而后者則以著名的GNGIRVANNEWMAN算法為代表N馴。231迭代二分法計算機科學(xué)中的一個典型問題，是將一個網(wǎng)絡(luò)分解成若干結(jié)點數(shù)基本相等的子網(wǎng)，使得不同子網(wǎng)中的結(jié)點之間的連接數(shù)最少，稱為圖分割GRAPHPARTITIONING。圖分割問題GPP可應(yīng)用于并行計算機的處理器合理分配進程。實際應(yīng)用中，大多數(shù)圖分割方法均基于迭代二分法首先將圖按要求分割成2個子圖，然后再分別對這2個子圖進行分割，如此迭代下去直至獲得所要求的子圖個數(shù)。我們介紹兩個最具代表性的迭代二分法一是KERNIGHANLIN算法昭引，該算法使用貪婪策略對社區(qū)內(nèi)以及社區(qū)間的邊數(shù)進行優(yōu)化，從而達到改進網(wǎng)絡(luò)的初始分解的目的；另一個是基于圖的LAPLACE矩陣的特征向量的譜二分法SPECTRALBISECTIONMETHOD24,25】。HTTP/INFO3DOUCOM/論壇推廣大連理工大學(xué)碩士學(xué)位論文2311KERNIGHANLIN算法KERNIGHANLIN算法是一種試探優(yōu)化法1。它基于貪婪算法原理將網(wǎng)絡(luò)劃分為兩個規(guī)模已知的社區(qū)。其基本思想是為網(wǎng)絡(luò)的劃分引進一個增益函數(shù)Q，Q定義為兩個社區(qū)內(nèi)部的邊數(shù)減去連接兩個社區(qū)之間的邊數(shù)，然后尋找使Q值最大的劃分方法。整個算法可描述如下首先，將網(wǎng)絡(luò)中的結(jié)點隨機地劃分為已知規(guī)模的兩個社區(qū)。在此基礎(chǔ)上，考慮所有可能的結(jié)點對，其中每個結(jié)點對的結(jié)點分別來自兩個社區(qū)。對每個結(jié)點對，計算如果交換這兩個結(jié)點的話可能得到的Q的增益QQ交換后一綏換前，然后交換最大的Q對應(yīng)的結(jié)點對，同時記錄交換以后的Q值。規(guī)定每個結(jié)點只能交換一次。重復(fù)這個交換過程，直到某個社區(qū)內(nèi)所有的結(jié)點都被交換一次為止。需要注意的是，在結(jié)點對交換的過程中，Q值并不一定總是單調(diào)增加的。不過，即使某一步的交換會使Q值有所下降，但是仍然可能在其后的步驟中出現(xiàn)一個更大的Q值。當(dāng)交換完畢后，便找到上述交換過程中所記錄的最大的Q值。這時對應(yīng)的社區(qū)結(jié)構(gòu)就認為是該網(wǎng)絡(luò)實際的社區(qū)結(jié)構(gòu)。KERNIGHANLIN算法最大的缺陷是要求事先知道兩個社區(qū)的規(guī)模，否則，就很可能不會得到正確的結(jié)果。這個缺陷使得它在實際網(wǎng)絡(luò)分析中難以應(yīng)用。而且，即使這個問題可以得到解決，它與所有的二分算法一樣，仍然面臨著如何事先知道網(wǎng)絡(luò)中的社區(qū)數(shù)目，以及確定二分法要重復(fù)到哪一步停止的問題。2312譜平分法一個有N個結(jié)點的無向圖G的LAPLACE矩陣是一個刀X刀維的對稱矩陣L。其中，L的對角線上的元素厶，是結(jié)點I的度結(jié)點的度定義為與該結(jié)點連接的其它結(jié)點的數(shù)目，而其他非對角線上的元素厶，則表示結(jié)點I和結(jié)點J的連接關(guān)系。如果這兩個結(jié)點之間有邊連接，則厶，值為1，否則為0。L矩陣所有的行與列的和都為0，因此，該矩陣總有一個特征值為O，其對應(yīng)的特征向量為L1，1，1。可以從理論上證明，不為零的特征值所對應(yīng)的特征向量的各元素中，同一個社區(qū)內(nèi)的結(jié)點對應(yīng)的元素是近似相等的。這就是譜平分法的理論基礎(chǔ)?？紤]網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的一種特殊情況當(dāng)一個網(wǎng)絡(luò)中僅存在兩個社區(qū)，此時該網(wǎng)絡(luò)的LAPLACE矩陣L就對應(yīng)了兩個近似的對角矩陣塊。對一個實對稱矩陣而言，它的非退化的特征值對應(yīng)的特征向量總是正交的。因此，除了最小特征值0以外，矩陣L其他特征值對應(yīng)的特征向量總是包含正、負兩種元素。這樣，當(dāng)網(wǎng)絡(luò)由兩個社區(qū)構(gòu)成時，就可以根據(jù)非零特征值相應(yīng)的特征向量中的元素對應(yīng)網(wǎng)絡(luò)的結(jié)點進行分類。其中，所有正元素對應(yīng)的那些結(jié)點都屬于同一個社區(qū)，而所有負元素對應(yīng)的結(jié)點則屬于另一個社區(qū)。HTTP/INFO3DOUCOM/論壇推廣復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法研究因此，我們可以根據(jù)網(wǎng)絡(luò)的LAPLACE矩陣的第二小的特征值九將其分為兩個社區(qū)。這就是譜平分法的基本思想。當(dāng)網(wǎng)絡(luò)的確是分成兩個社區(qū)時，用譜平分法可以得到非常好的效果。但是，當(dāng)網(wǎng)絡(luò)不滿足這個條件時，譜平分法的優(yōu)點就不能得到充分體現(xiàn)。事實上，第二小特征值厶可以作為衡量譜平分法效果的標(biāo)準(zhǔn)它的值越小，平分的效果就越好。九也稱為圖的代數(shù)連接度ALGEBRAICCONNECTIVITY。一般情況下，計算一個聆”矩陣的全部特征向量的時間復(fù)雜度為ON3。但是在大多數(shù)情況下，實際網(wǎng)絡(luò)的LAPLACE矩陣是一個稀疏矩陣，因此，可以用LANCZOS方法快速計算主要的特征向量。該方法的時間復(fù)雜度大致為M厶一九，其中，M表示網(wǎng)絡(luò)中邊的條數(shù)。這樣，計算的速度可以得到很大程度的提高。但是，如果不能很快將九從其它特征值中分離出來，該算法就可能在一定程度上有所減慢。換句話說，當(dāng)網(wǎng)絡(luò)很明顯地分成兩個社區(qū)時，該算法的速度非?？?，否則該算法就未必很有效。232層次聚類法層次聚類是尋找社會網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的一類傳統(tǒng)算法。它基于各個結(jié)點之間連接的相似性或者強度，把網(wǎng)絡(luò)自然地劃分為各個子群。根據(jù)加邊或去邊，該類算法又可以分為兩小類凝聚方法AGGLOMERATIVEMETHOD和分裂方法DIVISIVEMETHOD嘞1。按照網(wǎng)絡(luò)中添加或者刪除邊的步驟，層次聚類方法通常采用譜系圖或樹狀圖來記錄算法的結(jié)果，從而描述整個網(wǎng)絡(luò)從單個獨立的子群逐步凝聚為整個網(wǎng)絡(luò)或者從整個網(wǎng)絡(luò)逐步分解為若干個越來越小的子群的連續(xù)過程，如圖23所示，其中底部的各個圓代表了網(wǎng)絡(luò)中的各個結(jié)點。當(dāng)水平虛線從樹的底端逐步上移，各結(jié)點也逐步聚合成為更大的社區(qū)。當(dāng)虛線移至頂部，即表示整個網(wǎng)絡(luò)就成為一個社區(qū)。在該樹狀圖的任何一個位置用虛線斷開，就對應(yīng)著一種社區(qū)結(jié)構(gòu)。HTTP/INFO3DOUCOM/論壇推廣大連理工大學(xué)碩士學(xué)位論文圖23分級聚類方法中記錄算法結(jié)果的樹狀圖譜系圖18O底部的各個圓代表了網(wǎng)絡(luò)中的各個結(jié)點。FIG2_3ANEX鋤PLEOFASMALLHIERARCHICALCLUSTERINGTREE【捌THECIRCLESATTHEBOTTOMREPRESENTTHENODESINTHENETWORK2321分裂方法分裂方法中最典型的算法是GN方法口剛。它的基本思想是通過不斷地從網(wǎng)絡(luò)中移除介數(shù)BETWEENNESS最大的邊將整個網(wǎng)絡(luò)分解為各個社區(qū)。其中，邊介數(shù)定義為網(wǎng)絡(luò)中經(jīng)過該邊的最短路徑的數(shù)目。它為區(qū)分一個社區(qū)的內(nèi)部邊和連接社區(qū)之間的邊提供了一種有效的度量標(biāo)準(zhǔn)。GN算法的基本流程如下步驟1計算網(wǎng)絡(luò)中所有邊的介數(shù)；步驟2找到介數(shù)最高的邊并將它從網(wǎng)絡(luò)中移除；重復(fù)步驟1和2，直到每個結(jié)點就是一個退化的社區(qū)為止。GN算法彌補了一些傳統(tǒng)算法的不足，但是，在不知道社區(qū)數(shù)目的情況下，GN算法也不知道這種分解要進行到哪一步終止。為解決這個問題，NEWMAN等人引進了一個衡量網(wǎng)絡(luò)劃分質(zhì)量的標(biāo)準(zhǔn)模塊度M1。它是基于同型混合ASSOCIATIVDMIXING來定義的?？紤]某種劃分形式，它將網(wǎng)絡(luò)劃分為K個社區(qū)。定義一個七XK維的對稱矩陣EP。，其中元素E，表示網(wǎng)絡(luò)中連接兩個不同社區(qū)的結(jié)點的邊在所有邊中占的比例；這兩個結(jié)點分別位于第F個社區(qū)和第，個社區(qū)。注意，在這里所說的所有的邊是在原始網(wǎng)絡(luò)中的，而不必考慮是否被社區(qū)結(jié)構(gòu)算法移除。因此，該模塊度的衡量標(biāo)準(zhǔn)是利用完整的網(wǎng)絡(luò)來計算的。HTTP/INFO3DOUCOM/論壇推廣復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法研究設(shè)矩陣中對角線上各元素之和為MYP一它給出了網(wǎng)絡(luò)中連接某一個社區(qū)內(nèi)部各結(jié)點的邊在所有邊的數(shù)目中所占比例。定義每行或者列中各元素之和為AIY，_YJ它表示與第I個社區(qū)中的結(jié)點相連的邊在所有邊中所占的比例。在此基礎(chǔ)上，用下式來定義模塊度的衡量標(biāo)準(zhǔn)QQ，一砰25上式的物理意義是網(wǎng)絡(luò)中連接兩個同種類型的結(jié)點的邊即社區(qū)內(nèi)部邊的比例減去在同樣的社區(qū)結(jié)構(gòu)下任意連接這兩個結(jié)點的邊的比例的期望值。如果社區(qū)內(nèi)部邊的比例不大于任意連接時的期望值，則有Q0。一般認為，Q的最大值對應(yīng)的社區(qū)結(jié)構(gòu)就是網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。Q的上限為QI，Q越接近這個值，就說明網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)越明顯。實際網(wǎng)絡(luò)中，該值通常位于O3到07之間阱1。經(jīng)過NEWMAN等人的改進以后，GN算法不必依賴多余的信息來判斷得到的社區(qū)結(jié)構(gòu)是否具有實際意義，而是可以直接從網(wǎng)絡(luò)的拓撲結(jié)構(gòu)來進行分析。但是該算法的耗時比較大，為ON3，因此它僅僅適用于中等規(guī)模的大型網(wǎng)絡(luò)N10000以下。為了解決這個問題，人們在GN算法的基礎(chǔ)上提出了多種改進的算法，主要包括采用結(jié)點集的GN算法、自包含GN算法等。2321凝聚方法GN算法雖然準(zhǔn)確度比較高，分析社區(qū)結(jié)構(gòu)的效果比原有的一些算法好，但是它的算法復(fù)雜度比較大，因此僅僅局限于研究中等規(guī)模的復(fù)雜網(wǎng)絡(luò)?，F(xiàn)在，對于INTERNET、唧和電子郵件網(wǎng)絡(luò)等網(wǎng)絡(luò)的研究越來越多，面這些網(wǎng)絡(luò)通常都包含幾百萬個以上的結(jié)點。在這種情況下，傳統(tǒng)的GN算法就不能滿足要求?；谶@個原因，NEWMAN在GN算法的基礎(chǔ)上提出了一種快速算法N鐘NEWMANFASTALGORITHM，以下簡稱NF算法，它實際上是基于貪婪算法思想的一種凝聚算法，可以用于分析結(jié)點數(shù)達100萬的復(fù)雜網(wǎng)絡(luò)。NF算法如下步驟1初始化網(wǎng)絡(luò)為N個社區(qū)，即每個結(jié)點就是一個獨立社區(qū)。則在GN算法中討論過的矩陣E中，初始的Q，和口J滿足HTTP/INFO3DOUCOM/論壇推廣大連理工大學(xué)碩士學(xué)位論文J肌如果結(jié)點L之間有邊相連9IO其他26Q其中KI為結(jié)點I的度，M為網(wǎng)絡(luò)中總的邊數(shù)。步驟2依次合并有邊相連的社區(qū)對，并計算合并后的模塊度增量AQP，2A，AJ2E，A,AJ。根據(jù)貪婪算法的原理，每次合并應(yīng)該沿著Q增大最多或者減小最少的方向進行，其算法復(fù)雜度為0M。每次合并以后，對相應(yīng)的元素更新，并將與F、，社區(qū)相關(guān)的行和列相加，其時間復(fù)雜度為0N。因此，步驟2總的時間復(fù)雜度為OMN。步驟3重復(fù)執(zhí)行步驟2，不斷合并社區(qū)，直到整個網(wǎng)絡(luò)都合并成為一個社區(qū)。最多要執(zhí)行N1次合并。該算法總的算法復(fù)雜度為0MNN，對于稀疏網(wǎng)絡(luò)則為ON2。整個算法完成后可以得到一個社區(qū)結(jié)構(gòu)分解的樹狀圖。再通過選擇在不同位置斷開可以得到不同的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。在這些社區(qū)結(jié)構(gòu)中，選擇一個對應(yīng)著局部最大Q值的，就得到最好的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。為了進一步提高算法的速度，CLAUSET等人在NF算法的基礎(chǔ)上，采用堆的數(shù)據(jù)結(jié)構(gòu)來計算和更新網(wǎng)絡(luò)的模塊度，提出了一種新的凝聚算法嘲。該算法的復(fù)雜度只有ONL092刀1，已接近線性復(fù)雜性。233基于模塊度矩陣的社區(qū)結(jié)構(gòu)劃分算法2006年，NEWMAN在模塊度矩陣的基礎(chǔ)上，結(jié)合譜分析的思想，提出了一種新的算法。此處僅列出兩社區(qū)的劃分算法，多社區(qū)劃分算法可參考文獻40。該算法的目的是為了讓社區(qū)內(nèi)部擁有盡可能多的邊數(shù)。此目的可通過最大化實際網(wǎng)絡(luò)中社區(qū)內(nèi)部的邊數(shù)和網(wǎng)絡(luò)在隨機相連的情況下社區(qū)內(nèi)部的邊數(shù)的差值來實現(xiàn)。但是，尋找該差值的最大值將會耗費很大的計算量，不適合大型復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)的社區(qū)劃分，因此可尋找一種使差值盡可能大的方法?；谀K度矩陣的社區(qū)劃分方法就是利用模塊度矩陣的譜特征，使差值盡可能大的一種方法。式27中去掉等式右邊的常系數(shù)項后表示在網(wǎng)絡(luò)劃分為兩個社區(qū)的情形下的上述差值Q去莓名一等礦1去莓一等H。27HTTP/INFO3DOUCOM/論壇推廣復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法研究其中肌為網(wǎng)絡(luò)中的總邊數(shù)，彳。為網(wǎng)絡(luò)鄰接矩陣中的元素，為網(wǎng)絡(luò)在隨機相連的情。2M形下，結(jié)點F與結(jié)點歹之間擁有的邊數(shù)。S島，SN7是一個標(biāo)記向量，若結(jié)點F屬于第一個社區(qū)，則S，1，否則S，一1。上式Q的值正好為NEWMAN提出的對網(wǎng)絡(luò)進行二社區(qū)劃分后的模塊度的值嘲1。等式27可轉(zhuǎn)換為如下的等價形式Q去SRBS28其中矩陣B被稱為模塊度矩陣，B，彳，一罟?；谀K度矩陣劃分網(wǎng)絡(luò)二社區(qū)的算法描述如下首先求得模塊度矩陣B的最大特征值所對應(yīng)的特征向量，然后根據(jù)此特征向量中元素的正負，把網(wǎng)絡(luò)劃分為兩個社區(qū)。正的元素為一個社區(qū)，負的元素屬于另一個社區(qū)。該算法的時間復(fù)雜度為ON2LOGN，其中N為網(wǎng)絡(luò)中結(jié)點的個數(shù)。234加權(quán)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)劃分算法以上算法所適用的網(wǎng)絡(luò)大多數(shù)是無權(quán)網(wǎng)絡(luò)，然而現(xiàn)實世界中卻存在許多加權(quán)網(wǎng)絡(luò)。網(wǎng)絡(luò)中邊的權(quán)重大小具有實際意義，比如在社會網(wǎng)絡(luò)中邊的權(quán)重可能表示人與人之間關(guān)系親密程度的大小，因此如果忽略權(quán)重去分析加權(quán)網(wǎng)絡(luò)將會丟失大量包含在權(quán)重中的有用信息。直接處理加權(quán)網(wǎng)絡(luò)難以實現(xiàn)社區(qū)結(jié)構(gòu)的劃分，NEWMAN通過把加權(quán)網(wǎng)絡(luò)轉(zhuǎn)換為多重圖的形式H3I，即通過把網(wǎng)絡(luò)中結(jié)點對之間邊的權(quán)重N，看作是此結(jié)點對之間有N條邊相連，實現(xiàn)了把GN算法推廣到加權(quán)網(wǎng)絡(luò)中143。GN算法的本質(zhì)是不斷的移除網(wǎng)絡(luò)中具有最大邊介數(shù)的邊。邊的介數(shù)定義為通過該邊的所有最短路徑的條數(shù)。把GN算法推廣到加權(quán)網(wǎng)絡(luò)中，一個很簡單的想法是在把加權(quán)網(wǎng)絡(luò)轉(zhuǎn)換的多重圖中計算邊的介數(shù)，然后移除擁有最大邊介數(shù)的邊。邊的權(quán)重越大，通過該邊的最短路徑數(shù)目越多，被移除的概率也越大，然而邊的權(quán)重代表該邊所連接的結(jié)點對的親密程度，權(quán)重越大，結(jié)點對之間的親密程度越高，從社區(qū)結(jié)構(gòu)劃分的角度上來說，該邊被移除的概率應(yīng)該越小，所以上述算法的推廣是不可行的。正確的求解加權(quán)網(wǎng)絡(luò)中邊的介數(shù)的方法應(yīng)該是在忽略邊的權(quán)重的情形下，計算網(wǎng)絡(luò)中各邊的介數(shù)，然后定義加權(quán)網(wǎng)絡(luò)中邊的介數(shù)為以上無權(quán)情形下求得的邊的介數(shù)除以該邊的權(quán)重，這樣權(quán)重越大的邊得到的邊的介數(shù)越小，因而被移除的概率越小，符合社區(qū)結(jié)構(gòu)劃分的定義。HTTP/INFO3DOUCOM/論