面向帶權(quán)圖統(tǒng)計(jì)顯著社區(qū)評(píng)估和挖掘算法

社區(qū)發(fā)現(xiàn)是網(wǎng)絡(luò)數(shù)據(jù)分析中的一個(gè)基礎(chǔ)步驟也是數(shù)據(jù)挖掘和網(wǎng)絡(luò)科學(xué)中最重要的問題之一。由于目前對(duì)于社區(qū)沒有一個(gè)統(tǒng)一的定義，在過去的幾十年里，很多社區(qū)發(fā)現(xiàn)算法從不同的角度被提出。然而這些算法都沒能衡量帶權(quán)網(wǎng)絡(luò)中單個(gè)社區(qū)的統(tǒng)計(jì)顯著性。通過上面的觀察，本文從假設(shè)檢驗(yàn)的角度提出了兩個(gè)方法：一個(gè)是可以直接評(píng)估在帶權(quán)網(wǎng)絡(luò)中單個(gè)社區(qū)真實(shí)性的一般式；另一個(gè)是一個(gè)能夠直接計(jì)算帶權(quán)網(wǎng)絡(luò)中單個(gè)p值的無參社區(qū)檢測算法。考慮到噪聲在真實(shí)數(shù)據(jù)中存在的客觀性，在所社區(qū)評(píng)估方法中，邊權(quán)重信息被建模成了刪失數(shù)據(jù)。因此，社區(qū)顯著性評(píng)估的問題就可以被轉(zhuǎn)化為對(duì)刪失數(shù)據(jù)的雙樣本檢驗(yàn)問題。更具體的說，本文用ogrank檢驗(yàn)對(duì)兩組增廣邊權(quán)重集合（邊權(quán)重集合和外部邊權(quán)重集合）進(jìn)行顯著性檢驗(yàn)。在帶權(quán)網(wǎng)絡(luò)數(shù)據(jù)和無權(quán)網(wǎng)絡(luò)數(shù)據(jù)上對(duì)所方法進(jìn)行了實(shí)驗(yàn)。結(jié)果表明，在單個(gè)社區(qū)顯著性評(píng)估的實(shí)驗(yàn)上，本文所提出的方法優(yōu)于之前廣泛使用的評(píng)價(jià)指標(biāo)。由于上文所社區(qū)評(píng)估指標(biāo)的復(fù)雜性，不適合將它作為社區(qū)檢測算法的目標(biāo)函數(shù)。因此，為了解決能直接在帶權(quán)網(wǎng)絡(luò)數(shù)據(jù)中通過衡量單個(gè)社區(qū)的統(tǒng)計(jì)顯著性而進(jìn)行社區(qū)發(fā)現(xiàn)的問題，本文又提出了一個(gè)能夠在帶權(quán)網(wǎng)絡(luò)中計(jì)算單個(gè)社區(qū)p所p值能夠接評(píng)估一候選社在機(jī)帶權(quán)網(wǎng)絡(luò)出現(xiàn)的統(tǒng)顯著性。了驗(yàn)p區(qū)效文p值作為局搜過函數(shù)，并推導(dǎo)出一種新的社區(qū)發(fā)現(xiàn)算法。實(shí)驗(yàn)結(jié)果表明，對(duì)于在帶權(quán)網(wǎng)絡(luò)數(shù)據(jù)中檢測統(tǒng)計(jì)顯著性社區(qū)的效果來講，本文所新算法能夠達(dá)到與現(xiàn)有的社區(qū)檢測算法相當(dāng)?shù)男阅?。Significance-BasedCommunityEvaluationandDetectionAlgorithmsinWeightedNetworksCommunitydetectionisafundamentalprocedureintheysisofnetworkdataandoneofthemostimportantissuesindataminingandnetworkscience.Becauseofthelackofconsensusonthedefinitionofacommunity,duringthepastdecades,numerouscommunitydetectionalgorithmshavebeendevelopedfromdifferents.However,mostoftheseobjectionfunctionsdonotaddressthestatisticalsignificanceofasinglecommunityinweightedMotivatedbytheaboveobservations,wepresenttwomethodsbasedonasignificancetesting:oneisageneralformulationthatcanyticallytesttherealnessofacandidatecommunityinweightednetworksandanotheroneisanonparametricmethodthatcandirectlycalculatetheyticalp-valueofanindividualcommunityinweightednetworks.Inthecommunityevaluationmetric,theedge-weightismodeledasacensoredobservationwiththeconsiderationofthenoisycharacteristicsofrealnetworks.Thereafter,thecommunitysignificanceassessmentissueisformulatedasatwo-sampletestproblemoncensoreddata.Moreprecisely,theLogrankengagedinconductingthesignificancetestingontwosetsofaugmentededge-weights:internalweightsetandexternalweightset.Thepresentedapproachisevaluatedonbothweightednetworksandun-weightednetworks.TheexperimentalresultsshowthatourmethodcanoutperformpriorwidelyusedevaluationmetricsonthetaskindividualcommunityConsideringthecomplexityoftheaboveproposedcommunityevaluationmetric,itisnotsuitabletobeutilizedasanobjectivefunctionofacommunitydetectionalgorithm.Thus,toaddresstheissueofdetectingcommunitiesfromweightednetworksbydirectlyassessthestatisticalsignificanceofanindividualcommunity,wepresentanewmethodtocalculatetheyticalp-valueofasinglecommunityinweightednetworks.Theproposedyticalp-valuecandirectlyassessthestatisticalsignificanceofonetargetcommunitythatappearsinarandomweightedgraph.Toverifytheeffectivenessoftheproposedp-valueincommunityevaluation,itisemployedastheobjectivefunctioninalocalsearchproceduretoderiveanewcommunitydetectionalgorithm.Experimentalresultsshowthatthenewalgorithmisabletoachievecomparableperformancetothosestate-of-the-artalgorithmsforidentifyingcommunitiesfromweightednetworks.：CommunityDetection;Two-sampleTest;HypothesisTesting;StatisticalSignificance;WeightedNetworks-III............................................................................................................................ -------Friedman檢驗(yàn)及后續(xù)檢驗(yàn).................................................................-8-------------問題概網(wǎng)絡(luò)數(shù)據(jù)的類型以及規(guī)模在過去二十年有了飛速的增長，網(wǎng)絡(luò)越來越多地被應(yīng)用在社會(huì)科學(xué)、計(jì)算機(jī)科學(xué)、生物學(xué)、醫(yī)學(xué)、化學(xué)等領(lǐng)域][12。社區(qū)發(fā)現(xiàn)的目的是找到滿足社區(qū)定義的誘導(dǎo)子圖的集合，也就是根據(jù)某些社區(qū)的定義標(biāo)準(zhǔn)或者衡量指標(biāo)將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分為不同的群體，這些劃分后的群體也稱為社區(qū)。目前來講，社區(qū)的定義一般基于每個(gè)社區(qū)內(nèi)應(yīng)該有更緊密的連接或者不同社區(qū)之間的連接更加稀疏這樣的標(biāo)準(zhǔn)[3]被所有人都接受的解決方案。也就是說，到目前為止，人們?nèi)匀粵]有在如何定義一個(gè)社區(qū)這個(gè)問題上達(dá)成共識(shí)。因?yàn)閷?duì)社區(qū)的定義缺乏統(tǒng)一的標(biāo)準(zhǔn)，很多不同的用于衡量社區(qū)質(zhì)量的標(biāo)準(zhǔn)被提出[4]oulrity[5]和onduta[6]。雖然很多像odularityondutae出，但大多數(shù)評(píng)估方法都不是從嚴(yán)格的統(tǒng)計(jì)假設(shè)檢驗(yàn)過程中得到的[7]。確定被檢測出來的結(jié)果社區(qū)是否真實(shí)的問題還遠(yuǎn)未得到解決。(a)不考慮邊權(quán)重信息 圖1.1邊權(quán)重對(duì)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的影響 Theinfluenceofedge-weightoncommunitystructureof22條邊的網(wǎng)絡(luò)結(jié)構(gòu)（粗表示對(duì)應(yīng)邊的權(quán)重值越大）：1.1)個(gè)明顯的社區(qū)結(jié)構(gòu)；在考慮邊權(quán)重信息的情況下，如圖1.1.(b)社區(qū)結(jié)構(gòu)。從這個(gè)例子可以看到，不考慮邊的權(quán)重信息和考慮邊的權(quán)重信息所反映的社區(qū)結(jié)果是不同的。所以考慮邊的權(quán)重信息也是非常重要的。由于目前的社區(qū)發(fā)現(xiàn)算法大多都沒有考慮或沒有直接考慮邊權(quán)重信息對(duì)社區(qū)結(jié)構(gòu)的影響，那么尋找一個(gè)能考慮邊權(quán)重信息的統(tǒng)計(jì)顯著性社區(qū)發(fā)現(xiàn)算法或者統(tǒng)計(jì)顯著性結(jié)果社區(qū)衡量指標(biāo)顯得尤為重要。研究現(xiàn)在過去的幾十年里，各種各樣的社區(qū)檢測算法從不同的角度出發(fā)得到了不同程度的發(fā)展[1][4910]。盡管已經(jīng)有了這些發(fā)展，但評(píng)估檢測到的結(jié)果社區(qū)是否真實(shí)的問題還遠(yuǎn)遠(yuǎn)沒有得到解決。這樣的社區(qū)驗(yàn)證問題很自然地符合假設(shè)檢驗(yàn)的框架，在這個(gè)框架中，空假設(shè)是目標(biāo)社區(qū)不是真實(shí)的。事實(shí)上，許多指標(biāo)（ondutaeodulrity）已經(jīng)被提出用于評(píng)估一個(gè)目標(biāo)社區(qū)的真實(shí)性[4]。從理論上講，社區(qū)的真實(shí)性應(yīng)該是一個(gè)與特定的社區(qū)定義相關(guān)的分析性問題。朝著這個(gè)方向，已經(jīng)有了一些研究工作來分析和評(píng)估一個(gè)候選社區(qū)的真實(shí)E[11]、OSO[12]、SS[13]S[14]FS[15[7]。相比之下，基于統(tǒng)計(jì)顯著pp0和1pp很可能是一個(gè)真正的社區(qū)，也就是具有統(tǒng)計(jì)顯著性的社區(qū)。換句話說，很容易指定一個(gè)閾值（對(duì)應(yīng)于顯著性等級(jí)）并用類似統(tǒng)計(jì)顯著性的方式來解釋得到的結(jié)果。因此，在近幾年的時(shí)間里，很多用于評(píng)估社區(qū)統(tǒng)計(jì)顯著性的指標(biāo)被探索出來，例如：文獻(xiàn)[11131620]。基于對(duì)結(jié)果社區(qū)評(píng)估的方式，可以將現(xiàn)有的評(píng)估方法分為兩個(gè)不同的類別：（1）評(píng)估一個(gè)網(wǎng)絡(luò)劃分的統(tǒng)計(jì)顯著性的方法（例如：文獻(xiàn)[16-19]和文獻(xiàn)[2123]）；（2）評(píng)估單個(gè)社區(qū)的統(tǒng)計(jì)顯著性的方法（例如：文獻(xiàn)[11-13]、文獻(xiàn)[20]以及文獻(xiàn)[2427]）。而本文的重點(diǎn)是討論以p衡量單個(gè)社區(qū)統(tǒng)計(jì)顯著性的評(píng)估方法或者以此為目標(biāo)的社區(qū)檢測算法。雖然有很多可以用于評(píng)估單個(gè)社區(qū)的統(tǒng)計(jì)顯著性算法已經(jīng)被提出，但大多數(shù)可用的方法只能評(píng)估未網(wǎng)絡(luò)中單個(gè)社區(qū)的統(tǒng)計(jì)顯著性（例如：文獻(xiàn)13][20][24-27]）。也就是說，大多數(shù)評(píng)估方法都沒有考慮權(quán)重信息在社區(qū)評(píng)估中重要性。如前文所講，在許多真實(shí)的網(wǎng)絡(luò)中，每條邊都會(huì)具有某種特定的屬性，這些屬性值可以轉(zhuǎn)化為圖論中的.1含的信息可能對(duì)社區(qū)劃分產(chǎn)生重要或者決定性的影響。因此，考慮邊權(quán)重信息可能提高社區(qū)評(píng)估的性能，有助于揭示社區(qū)的底層結(jié)構(gòu)。據(jù)了解，OSM和E中的目標(biāo)函數(shù)是目前文獻(xiàn)中僅有的兩種可以對(duì)網(wǎng)絡(luò)中結(jié)果社區(qū)進(jìn)行統(tǒng)計(jì)顯著性評(píng)估的方法。相應(yīng)的社區(qū)發(fā)現(xiàn)算法，OSME是目前文獻(xiàn)中僅有的兩種可以從帶權(quán)網(wǎng)絡(luò)中檢測出具有統(tǒng)計(jì)顯著性社區(qū)的社區(qū)發(fā)現(xiàn)算法。因此，這兩個(gè)方法也是本文方法主要的對(duì)比對(duì)象。下面幾段將詳細(xì)闡述這兩種算法。OSME區(qū)的統(tǒng)計(jì)顯著性本質(zhì)上是基于E（OS）中社區(qū)內(nèi)（外）所有節(jié)點(diǎn)的最低歸屬概率來衡量的。換句話說，這兩種方法不能直接提供一個(gè)解析p統(tǒng)計(jì)顯著性。從理論上講，這種用于衡量單個(gè)社區(qū)統(tǒng)計(jì)顯著性的間接策略是合理的。但是，只有社區(qū)（外部）的“”節(jié)點(diǎn)用于顯著性的衡量而忽略了其他節(jié)點(diǎn)，這可能會(huì)導(dǎo)致信息未被充分利用或者一部分信息的丟失。因此，相應(yīng)的顯著性衡量指標(biāo)可能不能完全表征或者區(qū)分不同的社區(qū)。為了更詳細(xì)的闡述這個(gè)問題，本文在第OSM使用指數(shù)函數(shù)來近似邊權(quán)重之和的標(biāo)準(zhǔn)尾概率。而這個(gè)概率是根據(jù)人為指SM持的。相反，E首先提出了一種被稱為連續(xù)配置模型的空模型，然后證明了在該空模型下，一個(gè)節(jié)點(diǎn)與一個(gè)社區(qū)之間連邊的權(quán)重和漸近服從正態(tài)分布。相應(yīng)的，可以p值。然而，EpOSOM和E都是基于參數(shù)模型來計(jì)算節(jié)點(diǎn)歸屬概率的，但是其中一些假設(shè)可能是不正確的。OSOMCE與社區(qū)之間的歸屬概率來進(jìn)行間接評(píng)估的，所以，據(jù)了解，目前還沒有一種評(píng)估方法可以直接評(píng)估帶權(quán)圖中目標(biāo)社區(qū)的真實(shí)性，也沒有一種社區(qū)發(fā)現(xiàn)算法具有能直接衡量單個(gè)候選社區(qū)統(tǒng)計(jì)顯著性的目標(biāo)函數(shù)。研究與主要貢隨著網(wǎng)絡(luò)數(shù)據(jù)的日漸壯大，社區(qū)發(fā)現(xiàn)問題的重要性日漸顯現(xiàn)，越來越多的社區(qū)發(fā)現(xiàn)算法被提出。其中很大一部分社區(qū)發(fā)現(xiàn)算法只能應(yīng)用于無權(quán)重的網(wǎng)絡(luò)數(shù)據(jù)中，而可以用于帶權(quán)重網(wǎng)絡(luò)數(shù)據(jù)的社區(qū)發(fā)現(xiàn)算法很少。隨著網(wǎng)絡(luò)數(shù)據(jù)的快速權(quán)網(wǎng)絡(luò)數(shù)據(jù)的重要性日益凸顯，并且邊權(quán)重反映出來的信息可以對(duì)社區(qū)的劃分產(chǎn)生重要甚至決定性的影響。除此之外，很多社區(qū)發(fā)現(xiàn)算法的目標(biāo)函數(shù)并不是從嚴(yán)格的統(tǒng)計(jì)顯著導(dǎo)過程中得到的。相應(yīng)的，可以在帶權(quán)網(wǎng)絡(luò)數(shù)據(jù)中檢測具有統(tǒng)計(jì)顯著性社區(qū)的社區(qū)發(fā)現(xiàn)算法就更少了。據(jù)解，OSM和E是前獻(xiàn)中僅有的種可以從網(wǎng)絡(luò)中測出E以及SM自身CEOSMp對(duì)于第一個(gè)方面，也就是對(duì)直接評(píng)估社區(qū)真實(shí)性算法的研究：本文將社區(qū)發(fā)現(xiàn)問題轉(zhuǎn)化為統(tǒng)計(jì)學(xué)中的無參雙樣本檢測的問題，進(jìn)而評(píng)估社區(qū)的真實(shí)性。更詳細(xì)的內(nèi)容在本文第三章進(jìn)行了詳細(xì)的講解。本方法的主要貢獻(xiàn)點(diǎn)如下：通過在帶權(quán)網(wǎng)絡(luò)數(shù)據(jù)以及無權(quán)網(wǎng)絡(luò)數(shù)據(jù)上的實(shí)驗(yàn)，將所算法與CCME、OSLOM、Modularity和Conductance進(jìn)行了比較。在實(shí)驗(yàn)中，用Friedman檢驗(yàn)[28]以及后續(xù)檢驗(yàn)[29]評(píng)估結(jié)果的統(tǒng)計(jì)顯著性。實(shí) 對(duì)于第二個(gè)方面，本文從基于子圖計(jì)數(shù)的社區(qū)統(tǒng)計(jì)顯著性評(píng)估角度出發(fā)，提出了一個(gè)以解析p算法，形成一個(gè)完整的社區(qū)發(fā)現(xiàn)算法（簡稱為SSC），更詳細(xì)的內(nèi)容在本文第四章進(jìn)行描述。對(duì)于所基于子圖計(jì)數(shù)的社區(qū)統(tǒng)計(jì)顯著性評(píng)估算法，有以下貢獻(xiàn)點(diǎn)：據(jù)了解，這是目前文獻(xiàn)中第一個(gè)能夠提供解析p值來直接評(píng)估網(wǎng)絡(luò)中單個(gè)社區(qū)的統(tǒng)計(jì)顯著性的工作。為了減少計(jì)算代價(jià)，本文進(jìn)一步給出了p值的上界。將所p值作為候選社區(qū)評(píng)價(jià)的目標(biāo)函數(shù)，提出了一種從網(wǎng)絡(luò)中檢通過在仿真網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)，將所MSSC算法與CCME、OSLOM以及其他的社區(qū)檢測算法進(jìn)行了比較。實(shí)驗(yàn)結(jié)果證明了本文所提出方法的有效組織結(jié)究現(xiàn)狀進(jìn)行了一個(gè)梳理，闡述了本文的研究以及主要的貢獻(xiàn)點(diǎn)。第三章詳細(xì)描述了基于雙樣本檢驗(yàn)的社區(qū)統(tǒng)計(jì)顯著性評(píng)估算法。首先介紹了雙樣本檢驗(yàn)方法ogrnk詳細(xì)展示本文所第一個(gè)方法在帶權(quán)網(wǎng)絡(luò)數(shù)據(jù)上以及無權(quán)網(wǎng)絡(luò)數(shù)據(jù)上的結(jié)果，并給出了總結(jié)。第四章詳細(xì)描述了本文基于子圖計(jì)數(shù)的社區(qū)統(tǒng)計(jì)顯著性評(píng)估算法。首先詳MSSC算法的詳細(xì)算法流程；最后分別詳細(xì)展示了算法在仿真數(shù)據(jù)以及和文獻(xiàn)[30-34]）。一般來說，這些空模型擴(kuò)展了那些常用的非隨機(jī)圖空模型。例如：隨機(jī)塊模型[35]、配置模型[36]和Erd?s–Rényi（E-R）模型[37]。這些擴(kuò)展的空模型主要通E-RE-R模型為真實(shí)網(wǎng)絡(luò)的性質(zhì)提供了基本的參考[30]，而且它足夠簡單，可以推導(dǎo)出解析的p值。非E-R模型有兩種變體：G(N,p)和G(N,M)。在G(N,p)中，所有的節(jié)點(diǎn)對(duì)以p的概率獨(dú)立連接，生成一個(gè)N個(gè)節(jié)點(diǎn)的隨機(jī)圖。G(N,M)中，隨機(jī)圖是在所有可能的具有N個(gè)節(jié)點(diǎn)和MG(N,M)：G(N,M,W)，它根據(jù)以下程序生成一個(gè)隨機(jī)網(wǎng)絡(luò)從大小為??MM(2經(jīng)過以上兩個(gè)步驟之后，可以生成需要的帶重信息的隨機(jī)圖。假設(shè)檢假設(shè)檢驗(yàn)是利用樣本的分布狀態(tài)對(duì)總體進(jìn)行的某種推斷進(jìn)而判斷整體特征的一種方式。在假設(shè)檢驗(yàn)中，要首先對(duì)總體參數(shù)??的值提出一個(gè)假設(shè)，然后利用已有的樣本信息通過一系列的過程去推斷所設(shè)立的假設(shè)是否成立。在簡單的假設(shè)檢驗(yàn)中，0一般用于表示原假設(shè)，也稱為“零假設(shè)”或者“空假設(shè)”；1用來表示備擇假設(shè)，也稱為“替換假設(shè)”。原假設(shè)和備擇假設(shè)是互斥的：原假設(shè)成立則意味著備擇假設(shè)是不成立的；相應(yīng)的，原假設(shè)不成立則意味著備擇假設(shè)是成立的。第一類錯(cuò)誤（棄真）：原假設(shè)為真，但是被2.1Tab.2.1ErrortypesinmultiplehypothesisFWER（Family-WiseErrorRate）FDR（FalseDiscoveryRate）這兩種度量方式。最基本的方法就是基于假設(shè)的數(shù)量對(duì)原始p值或者統(tǒng)計(jì)顯著性水平進(jìn)行調(diào)整。pp值是在假設(shè)檢驗(yàn)中為了精確反映決策的風(fēng)險(xiǎn)度而選擇的一種決策方式。更確切的說，p值是當(dāng)原假設(shè)為真的時(shí)候所得到的樣本觀察結(jié)果或更結(jié)果出現(xiàn)的概率。如果p值很小，說明原假設(shè)為真發(fā)生的概率很小；而如果出現(xiàn)原假設(shè)為真的情況，根據(jù)2.2p值的大小對(duì)于原假設(shè)的意義。p值越小，原假設(shè)發(fā)生的可能性越小，2.2pTab.2.2Thesignificanceofp-valuetothenullpp>p<p<雙樣本假設(shè)檢驗(yàn)是對(duì)兩個(gè)樣本之間的關(guān)系進(jìn)行判斷的一個(gè)過程。對(duì)于給定的兩組X1,2,3??Y=1,2,3,??,??為是相互獨(dú)立的總體（一般認(rèn)為兩個(gè)樣本都是獨(dú)立同分布的）。而對(duì)于雙樣本假設(shè)檢驗(yàn)，一般是想要證明這兩組樣本具有相同分布，也就是雙樣本假設(shè)檢驗(yàn)的原假設(shè)??0是????(??????(??)FxFyXY的分布函數(shù)。根據(jù)不同的實(shí)際Friedman檢驗(yàn)及后續(xù)檢Friedman檢驗(yàn)[28]ANOVAFriedman檢驗(yàn)無參的特點(diǎn)，它的應(yīng)用范圍更廣，應(yīng)用頻率也相對(duì)較高。Friedman檢驗(yàn)的大致流對(duì)每個(gè)數(shù)據(jù)集上的所有算法根據(jù)表現(xiàn)情況分別進(jìn)行：表現(xiàn)最好的算法排名為1，第二好的算法為2，……。設(shè)????是所有k個(gè)算法中第j個(gè)算法在所有N個(gè)將第j個(gè)算法在所有N個(gè)數(shù)據(jù)集上分別得到 的平均情況??=1∑???? ??R應(yīng)該是相等的。對(duì)應(yīng)的Friedman統(tǒng)計(jì)量??2= [∑??2???(??+1)2]是服從k- ?? 自由度的??2分布。ImanDavenportFriedman的??2 個(gè)更好的統(tǒng)計(jì)量???? ??，它是自由度為k-1和(k-1)(N-1)的驗(yàn)方法來研究各個(gè)算法之間更具體的差異。比較常用的后續(xù)檢驗(yàn)方法有NemenyiBonferroni-Dunn檢驗(yàn)和 tep-down檢驗(yàn)等檢驗(yàn)方法[29]當(dāng)所有對(duì)比方法相互比較時(shí)，Nemenyi檢驗(yàn)類似于ANOVA分析的后續(xù)檢驗(yàn)方法中的Tukey檢驗(yàn)。如果兩個(gè)對(duì)比方法對(duì)應(yīng)的平均的差值至少達(dá)到臨界差值

√??(??+1)，那么可以認(rèn)為這兩個(gè)對(duì)比方法的性能是有顯著差異的。其中，臨界????Studentized范圍統(tǒng)計(jì)量除以√2得到的，比較常用一些????2.3所示。Tab.2.3Criticalvaluesforthetwo-tailedNemenyi23456789Tab.2.4Criticalvaluesforthetwo-tailedBonferroni-Dunntest;thenumberofmethodsincludethecontrolmethod23456789Nemenyi檢驗(yàn)更強(qiáng)大。因?yàn)闉榱吮ＷC??(???1)次比較，Nemenyi2驗(yàn)調(diào)整了進(jìn)行比較的臨界值，而當(dāng)與對(duì)照方較時(shí)，只進(jìn)行k-1次比較。(???????

√??(??+

z用于從正態(tài)分布表中找到相應(yīng)的概率值，然后將其與指定的統(tǒng)計(jì)顯著性水平檢驗(yàn)相同的公式計(jì)算臨界差值CD，但其中的臨界值??是??，比較常用一些?? 與單步Bonferroni-Dunn程序相比，Hotep-down程序按重要性順序檢驗(yàn)假設(shè)。用??1,??2,??,?????1來表示排序后的p值，其中??1≤??2≤??≤?????1。然后把每個(gè)????與??比較，但測試的順序不同。 tep-down從最顯著的p值開始，如果??小??， 相應(yīng)的假設(shè)，然后將??與

評(píng)價(jià)指

在過去的幾十年里，社區(qū)發(fā)現(xiàn)算法的結(jié)果衡量指標(biāo)得到了很大的發(fā)展，衡量指標(biāo)主要有：、Purity、ndndx、Priion、llF1mure等方法。在本Jaccard相似系數(shù)、Precision、Recall、F1measure、RandIndex、PurityONMI。他們的具體信息Jaccard相似系數(shù)用于比較有限樣本集之間的相似性與差異性。Jaccard系數(shù)的值越此，可以認(rèn)為A是結(jié)果社區(qū)集合，B是真實(shí)參考社區(qū)集合），Jaccard系數(shù)定義為：|?????Precision

??(??,??)

|?????

PriionllB，如果兩個(gè)節(jié)點(diǎn)來自同一個(gè)真實(shí)參考社區(qū)，那么就認(rèn)為這兩個(gè)節(jié)點(diǎn)具有相同的。每一個(gè)節(jié)點(diǎn)對(duì)（一個(gè)節(jié)點(diǎn)來自參考社區(qū)，一個(gè)節(jié)點(diǎn)對(duì)應(yīng)于結(jié)果社區(qū)）都有四種可能：（1）真正例TP：兩個(gè)具有相同的節(jié)點(diǎn)被分到了同一個(gè)結(jié)果社區(qū)中；（2）假反例FN：兩個(gè)具有相同的節(jié)點(diǎn)被分到了不同的結(jié)果社區(qū)中；（3）假正例FP：兩個(gè)具有不同的節(jié)點(diǎn)被分到了同一個(gè)結(jié)果社區(qū)中；（4）真反例TN：兩個(gè)具有不同的節(jié)點(diǎn)被分到了不同的結(jié)果社區(qū)中。根據(jù)這個(gè)結(jié)果，Priion被定義為：

??????????????????????????????

????+

F1

????+2×??????????????????×??1= ??????????????????+(1+??2)×??????????????????×

???? (??2×??????????????????)+ 從公式（2.6）可以看到，β值是用于控制Precision在結(jié)果中占據(jù)的。當(dāng)β=1的時(shí)候，就是本文中使用的F1measure；當(dāng)β>1的時(shí)候，Precision在結(jié)果中會(huì)產(chǎn)生更大的影響；當(dāng)β<1的時(shí)候，Precision在結(jié)果中會(huì)產(chǎn)生較小的影響。RandRandIndex是通過衡量正確決策所占據(jù)的比率來進(jìn)行對(duì)結(jié)果進(jìn)行評(píng)估的式。根據(jù)結(jié)果集合點(diǎn)對(duì)可能性的定義（也就是TP、FP、TN和FN的定義），RandIndex可以表示成如下這種方式：

??????????????????

????+????+????+????+

PurityPurityAB社區(qū)，然后通過計(jì)算所有重合節(jié)點(diǎn)的個(gè)數(shù)并除以總的節(jié)點(diǎn)個(gè)數(shù)的方式來衡量該分配的1????????????=??∑????????|?????

令??={??1,??2,??,????}作為檢測到的結(jié)果社區(qū)。令二項(xiàng)關(guān)系變量????（??=1??,??）Ak個(gè)社區(qū)。則????的概率分布

=1)=并且??(????=0)=1???(????=1)，其中N是在網(wǎng)絡(luò)中存在的結(jié)點(diǎn)數(shù)。同樣的，用??={??1,??2,??,????}表示真實(shí)參考社區(qū)集合。用變量????（??=12,??,??）是否屬于B的第j個(gè)社區(qū)。??的概率分布為??(??=1)= ??(??=0)=1???(??

1)。因此，可以以同樣的方式可以得到變量????和????的聯(lián)合概率分布??(????,????)。在給定的條件下，????的條件熵可以這樣定義??(????|????)=??(????,????)? 其中??(?)表示標(biāo)準(zhǔn)熵函數(shù)。因此基于??={??1,??2????}的所有元素，對(duì)于??????(????|??)=????????∈{1,2,?? 對(duì)于??={??1,??2,??,????}Y ??(??|??)=|A|∑??(??

同樣的方法可以定義??(??|??)。最終，對(duì)于A和B的社區(qū)結(jié)構(gòu)，得到ONMI的公式????????(??|??)=1

??(??|??)+ ONMI的值越大表示實(shí)驗(yàn)結(jié)果越好。特別的ONMI1時(shí)，表示檢測出來的社本章小本章主要對(duì)研究過程中所用到E-R模型以及對(duì)其在帶權(quán)網(wǎng)絡(luò)上進(jìn)行的拓展進(jìn)行了介紹；其次對(duì)假設(shè)檢驗(yàn)相關(guān)的理論內(nèi)容進(jìn)行了詳細(xì)介紹：假設(shè)檢驗(yàn)中所用到的p值、雙Friedman檢驗(yàn)方法以及常用的三種后續(xù)檢驗(yàn)方法：Nemenyi檢驗(yàn)方法、Bonferroni-Dunn檢驗(yàn)方法和Hotep-down方法。最后，又詳細(xì)描述了在實(shí)驗(yàn)中用到的6種評(píng)價(jià)指標(biāo)。在進(jìn)行社區(qū)統(tǒng)計(jì)顯著性評(píng)估的研究時(shí)，可以使用統(tǒng)計(jì)中假設(shè)檢驗(yàn)的理論框架。在這個(gè)框架中，原假設(shè)0是目標(biāo)社區(qū)不是真實(shí)的；相應(yīng)的備擇假設(shè)1就是所要衡量的目假設(shè)邊權(quán)重是非負(fù)的連續(xù)數(shù)值。由于在網(wǎng)絡(luò)數(shù)據(jù)的記錄或者整理過程中，網(wǎng)絡(luò)結(jié)構(gòu)和邊權(quán)重可能包含大量的測量誤差[8]，因此，可以將每個(gè)邊的權(quán)重值建模為生存分析中的刪失觀察[8]。如果兩個(gè)節(jié)點(diǎn)之間沒有邊，那么這條邊要么未被觀察記錄到，要么0。因此，可以構(gòu)造兩組增廣邊權(quán)值集合：一組由社區(qū)內(nèi)的邊的邊權(quán)值組成，另一組由社區(qū)內(nèi)節(jié)點(diǎn)與社區(qū)外剩余節(jié)點(diǎn)之間的邊的邊權(quán)值組成。如果目標(biāo)社區(qū)不是一個(gè)真正的社區(qū)，也就是原假設(shè)0成立，那么有理由認(rèn)為這兩個(gè)增廣邊權(quán)值集合之間沒有差異。因此，可以在刪失數(shù)據(jù)分析中利用無參雙樣本檢驗(yàn)的方法來評(píng)估候選社區(qū)的統(tǒng)計(jì)顯著性。本章選擇了比較流行的ogrnk檢驗(yàn)[39]來完成這個(gè)任務(wù)。算法流給定一個(gè)網(wǎng)絡(luò)??=(??,??,??)，其中V是節(jié)點(diǎn)集合，E是邊集合，W是邊對(duì)應(yīng)的權(quán)值集合。對(duì)于給定的節(jié)點(diǎn)子集??(??∈??)，其誘導(dǎo)子圖??[??]可認(rèn)為是一個(gè)候選社區(qū)。所有與集合S點(diǎn)有關(guān)聯(lián)的邊可以分為兩組：??[??]邊集合（集合每條邊連接的兩個(gè)節(jié)點(diǎn)都來自于S）；??[??]外部邊集合（集合每條邊連接的兩個(gè)節(jié)點(diǎn)中，一個(gè)節(jié)點(diǎn)來自于S，一個(gè)節(jié)點(diǎn)來自于除S之外的部分：V\S）。設(shè)??????(?)和????????(?)分別是邊和外部邊權(quán)重的互補(bǔ)累積分布函數(shù)。然后，可以將??0：??????(??)=??1：??????(??)????????(??對(duì)于至少一個(gè)??,其中??≥0是非負(fù)邊權(quán)值。需要注意的是，邊權(quán)值越大表示對(duì)應(yīng)的兩個(gè)節(jié)點(diǎn)之間的連接越強(qiáng)。如果H0被，而H1成立，則說明會(huì)有的邊權(quán)為正的邊，且邊的權(quán)值較大。因此，提出本檢驗(yàn)問題，有很多種有效的方法可以被采用。因?yàn)長ogrank檢驗(yàn)的普遍使用，這里本章采用的是Logrank檢驗(yàn)。Logrank檢驗(yàn)的一般流程是：給定兩個(gè)樣本數(shù)據(jù)集合：??={??1??2????1}和??={??1??2????2}。首先將兩個(gè)樣本合并，然后去掉合并后集合中重復(fù)出現(xiàn)的數(shù)值得到數(shù)據(jù)集??={??1,??2,??,????}。將合并的數(shù)值根據(jù)的大小降序排列記作：??(1)>??(2)>??>??(??)。然后統(tǒng)計(jì)數(shù)值??(??)A中出現(xiàn)的總次數(shù)（記作??0）??

的總次數(shù)（記作??1），AB中出現(xiàn)的總次數(shù)叫做????，也就是說????=??0+??1 A中小于等于數(shù)值??(??)的數(shù)值出現(xiàn)的次數(shù)（記作??0），B等于數(shù)值??(??)的數(shù)值出現(xiàn)的次數(shù)，并記作??1。用????AB中小于等于數(shù)值??(??)的數(shù)值出現(xiàn)的次數(shù)，也就是????=??0+??1ABLogrank 驗(yàn)的統(tǒng)計(jì)量????為

∑??????=??=1 √∑??其中

??=1

=??

=?? OrderedinternalOrderedexternal221122212i123i12345E24602ni-inniout-Ni-10100iabweight=0iabweight=0 weight>0 Externaledge, weight=0 Externaledge,weight>0122232365007 1 dc∑????Z= ∑p-Oneidep-Z=-4-3-2-1012322402Fig.3.1Themainworkflowofour圖3.1.(a)是對(duì)缺失的邊增加邊權(quán)的網(wǎng)絡(luò)：每條實(shí)線代表一條實(shí)邊，每條虛線代表一條未包含在E中的增廣邊。在圖中所示的網(wǎng)絡(luò)中，共有7個(gè)節(jié)點(diǎn)，候選社區(qū)為節(jié)點(diǎn)集{1,2,3,4}的誘導(dǎo)子圖。每條線的粗細(xì)與相應(yīng)的邊權(quán)成正比，缺失的邊的增廣邊權(quán)圖3.1.(b)是有序邊權(quán)集：對(duì)于圖3.1.()廣邊權(quán)集合：一個(gè)集合由的邊權(quán)值組成，另一個(gè)集合由與該候選社區(qū)內(nèi)節(jié)點(diǎn)相連的外部的邊權(quán)值組成?？梢詫?duì)這兩組集合排序來驗(yàn)證它們的互補(bǔ)累積分布函數(shù)是否是相同的。如果候選社區(qū)不是真實(shí)社區(qū)，那么可以預(yù)期這兩組權(quán)值具有相同的互補(bǔ)累積分布函數(shù)。3.1.(c)3.1.(b)中的每個(gè)不同的權(quán)值，都可以構(gòu)造一個(gè)列聯(lián)表。例兩條邊的權(quán)值為3.2。表格的最左邊的第一列是（2,0,2）4條（12條）內(nèi)（和外）3.2，那么表格最左邊的第二列是（4,12,16）3.1.(d)3.1.(c)中的列聯(lián)表，可以計(jì)算檢驗(yàn)統(tǒng)計(jì)量Z和相應(yīng)的p值來量化候選社區(qū)的統(tǒng)計(jì)顯著性。進(jìn)一步應(yīng)用Bonferroni校正來提供一個(gè)調(diào)整后的p值，這個(gè)p值是通過將原始p值與所有具有相同大小的可能社3.1所示，在方法的第一步，把每一條邊的權(quán)重值作為一個(gè)刪失觀測數(shù)據(jù)。如圖后構(gòu)造兩個(gè)增廣的邊權(quán)集：邊權(quán)重集合記作??????={??????,??????,??,??????}；外部 2權(quán)重值集合記為????????={????????,????????,??, }。如圖3.1.(b)所示，對(duì)?????? ????????、????分別表示邊中邊權(quán)重值為????的邊數(shù)量、外部邊中邊權(quán)重值為????的邊的數(shù)量以及????中邊權(quán)重值為????的邊數(shù)量。??????、????????、????分別表示邊中邊權(quán)重值小于等 于????的邊數(shù)量、外部邊中邊權(quán)重值小于等于????的邊的數(shù)量以及????中邊權(quán)重值????的邊數(shù)∑??(???????????=??=1 ??=1其中q????中不同邊權(quán)的個(gè)數(shù)，????=

??????=???? 。當(dāng)??0ZN(0,1)分布。在公式（3.2）?????????????可以被視為“相對(duì)于特定權(quán)值的邊數(shù)，觀測到的值與期望值的差值” Z統(tǒng)計(jì)量相關(guān)聯(lián)。在這個(gè)近似的基礎(chǔ)上，可以得到相應(yīng)的p值來評(píng)估結(jié)果社區(qū)的統(tǒng)計(jì)顯著性。因此，通過計(jì)算每個(gè)候選社區(qū)的調(diào)整后的p值來進(jìn)行多重假設(shè)檢驗(yàn)。最常用的多重檢驗(yàn)Bonferronip值乘以檢驗(yàn)假設(shè)的個(gè)數(shù)，得到修正后的p值。在本文所研究問題的背景下，檢驗(yàn)假設(shè)的數(shù)量可以計(jì)算為與候選社區(qū)具p值計(jì)算為：????????(??[??])=??????{1??(??[??]×(|??|，其中??(??[??])是對(duì)于非網(wǎng)絡(luò)，網(wǎng)絡(luò)中的邊權(quán)值為1或0，則公式（3.2）中q=2。對(duì)于權(quán)重

=1，則有：??????=(|??|，????????=|??|(|??||??|)，因此，??????

??1 ??????????????(?????

|??||

| )

)+

??1，??1????=1

2 1= 。對(duì)于權(quán)重 |

(??1) ||(||||)2 ||(|||)+2

[(2)+???????][(2)+???????

=0，則有：??????=??????????????=????????

=

，因此，??????

=??????，??????=0 (?????????????)+(??????? (????????? √(??????+

??????

)+|??|(|??|? )|??|(|??|?|??|)??1 )+|??|(|??|?|??|)? 2[(|??|)+|??|(|

?

[(|??|)+|??|(|??|?|??|)?1]

(|??|)|??|(|??|?|??|)[(|??|)+|??|(|??|?|??|)?=

??[(|??|)+|??|(|??|?|??|)???

|??|(|??|? ) |??|)+|??|(|??|?|??|)?)= |??|(| |

|??|(|

|

|??|)+|??|(|??|?|??|)???

???

|??|(|??|????

??12

2文獻(xiàn)[40]提出了一種新的社區(qū)評(píng)價(jià)指標(biāo)。根據(jù)本文的符號(hào)，該指標(biāo)可以表1??′=|??|(|??|?|??|)[12

11

|??|)+|??|(|??|?|??|)???≈

2)[(

|??|(|??|?|??|)??1[(|??|)+|??|(|??|?|??|)?2實(shí)驗(yàn)結(jié)為了檢驗(yàn)p值對(duì)社區(qū)評(píng)價(jià)是否有效，本章根據(jù)圖3.2所示的流程圖進(jìn)行了一系列實(shí)驗(yàn)。其中，圖3.2中描述的例子的具體流程如下：給定一個(gè)具有三個(gè)真實(shí)參考社區(qū)的網(wǎng)絡(luò)，其真實(shí)參考社區(qū)分別是{1,3,4,5}、{2,7,8}和{9101112}。使用一個(gè)社區(qū)檢測算法檢測到三個(gè)社區(qū)：A{1,3,4,5}、B6,7,8,9}和C={10,11,12}。每個(gè)結(jié)果社區(qū)都可以使用驗(yàn)證度量指標(biāo)和外部驗(yàn)證度量指標(biāo)進(jìn)行評(píng)估。例如，對(duì)于結(jié)果社區(qū)A，本章所方法的負(fù)對(duì)數(shù)值以及查準(zhǔn)率分,法的結(jié)果向量。例如，本章所提出方法的驗(yàn)證指標(biāo)向量和Jaccard系數(shù)向量分別為（9.39,6.31,7.56）和（1,0.8,0.75）。然后，在兩個(gè)向量（一個(gè)來自驗(yàn)證度量，另一個(gè)來自外部驗(yàn)證度量）Pearson相關(guān)系數(shù)。在相關(guān)系數(shù)的基礎(chǔ)上，進(jìn)一步應(yīng)用四個(gè)統(tǒng)計(jì)檢驗(yàn)方法，以檢驗(yàn)本章所方法在單個(gè)社區(qū)評(píng)估上是否真的優(yōu)于其他絡(luò)上檢測得到一組結(jié)果社區(qū)。然后，本章使用驗(yàn)證度量（例如：本章所方00000000000000000000000002202202202202020000Fig.3.2Themainworkflowofour換句話說，如果一個(gè)驗(yàn)證指標(biāo)與每個(gè)外部驗(yàn)證指標(biāo)對(duì)結(jié)果社區(qū)的評(píng)估相關(guān)度很高，計(jì)算兩個(gè)指標(biāo)向量（一個(gè)由驗(yàn)證度量指標(biāo)生成，另一個(gè)由外部驗(yàn)證度量指標(biāo)生成）之間的Pearson相關(guān)系數(shù)。最后，F(xiàn)riedman檢驗(yàn)和三個(gè)后續(xù)檢驗(yàn)（Nemenyi檢驗(yàn)、Bonferroni-Dunn檢驗(yàn)和Hotep-down檢驗(yàn)）用來檢查本章所方法是否明顯優(yōu)于其他流行的驗(yàn)證指標(biāo)。在本章的實(shí)驗(yàn)中，兩組數(shù)據(jù)集被用來驗(yàn)證方法的有效性。一組是由四個(gè)（蛋白質(zhì)-蛋白質(zhì)相互作用）網(wǎng)絡(luò)組成。分別是：Collins_2007[41]、Gavin_2006[42]、Krogan2006-Core[43]、Krogan2006-Extended[43]。這些PPI網(wǎng)絡(luò)有三組參考真實(shí)社區(qū)，每組分別是從以下蛋白質(zhì)復(fù)合物數(shù)據(jù)庫之一收集的：CYC2008[44]、MIPS[45]和SGD[46]。在這三組中分別有408、203和323個(gè)真實(shí)參考社區(qū)。另一組數(shù)據(jù)由6個(gè)真實(shí)的非網(wǎng)絡(luò)組成：Karate[47]、Football[3]、al （以下簡稱為al）[13]、Politicalblogs（本章簡稱為PolBlogs）[48]、BooksaboutUSpolitics（本章簡稱為PolBooks）[49]以及Railways[50]。這6個(gè)真實(shí)非網(wǎng)絡(luò)的拓?fù)涮卣魅绫?.1所示。（Cmin）為真實(shí)參考社區(qū)的最大（最?。㏕ab.3.1Thedetailedinformationofsixun-weightednetworks.Nisthenumberofvertices,Misthenumberofedges,????istheaveragedegreeandCmax(Cmin)isthe al(minimum)sizeoftheground-truthDataNM531因?yàn)樵趯?shí)驗(yàn)方法之前需要有已經(jīng)檢測出來的結(jié)果社區(qū)集合，因此，在實(shí)驗(yàn)中，本章選擇了三種經(jīng)典的社區(qū)檢測方法：SPA[51]、Infomap[52]ouvin[53]用于檢測結(jié)果社區(qū)，并且在本文中使用這三個(gè)方法的默認(rèn)參數(shù)設(shè)置運(yùn)行它們實(shí)驗(yàn)。其中，SPAw的r根據(jù)文獻(xiàn)[51].45。四個(gè)指標(biāo)被用來與本章所方法進(jìn)行比較：Conductance、Modularity、OSLOMpCCMEp值。OSLOMp值是通過默認(rèn)設(shè)置得到的；CCMEpp值的最大值。由于理論上，Conductance、p值、OSLOMpCCMEpJaccard相似系數(shù)、Precision和Recall呈負(fù)相關(guān)。因此，為了統(tǒng)一結(jié)果的數(shù)值變化與效果之間的關(guān)系，本章取這四個(gè)指標(biāo)與三個(gè)外部指標(biāo)之間的Pearson相關(guān)系數(shù)的負(fù)數(shù)值。那么，對(duì)于社區(qū)檢測算法在每個(gè)數(shù)據(jù)集上檢測出來的結(jié)果社區(qū)集合，基于評(píng)估結(jié)果與每個(gè)外部度量指標(biāo)的Pearson相關(guān)系數(shù)來衡量哪個(gè)衡量指標(biāo)更好。更準(zhǔn)確地說，一個(gè)更好的內(nèi)Pearson相度量指標(biāo)的情況，相關(guān)系數(shù)值越大其對(duì)應(yīng)的越高（數(shù)值越小）圖3.3.(a)和圖3.3.(b)以箱線圖的形式分別給出了五種衡量指標(biāo)在PPI網(wǎng)絡(luò)和未網(wǎng)絡(luò)數(shù)據(jù)上的分布。從圖3.3可以看出，本章的方法在5個(gè)驗(yàn)證指標(biāo)中平均最高。 Conductance Internal

Conductance Internal 圖3.3在(a)PPI網(wǎng)絡(luò)和(b)非網(wǎng)絡(luò)上每個(gè)驗(yàn)證度量的等級(jí)分布。這里使用箱線圖來描Fig.3.3Therankdistributionforeachinternalvalidationmetricon(a)WeightedPPInetworksand(b)Un-weightednetworks.Heretheboxplotisusedtodepictthedistributions:minimum(lowerline),lowerquartile(loweredgeofthebox),median(centerline),upperquartile(upperedgeofthebox)andum(upperline).Meanwhile,mean(star)andoutlier(cross)arealso為了進(jìn)一步檢查本章的方法是否真的比其他四個(gè)驗(yàn)證指標(biāo)更好，首先應(yīng)用Friedman檢驗(yàn)來評(píng)估所有方法具有相同的零假設(shè)??0。PPI網(wǎng)絡(luò)和非網(wǎng)絡(luò)的Friedman檢驗(yàn)的??2200.570445.6889然后，進(jìn)一步使用Nemenyi檢驗(yàn)、Bonferroni-Dunn檢驗(yàn)和Hotep-down檢驗(yàn)，以成對(duì)的方式將本章的方法與其他驗(yàn)證度量進(jìn)行比較。表3.2記錄了本章的方法與各對(duì)比方法在PPI網(wǎng)絡(luò)和非網(wǎng)絡(luò)上的平均的差值。如表3.2所示，在PPI網(wǎng)絡(luò)數(shù)據(jù)上，當(dāng)顯著性水平為0.05時(shí)，本章的方法與Modularity、Conductance和CCME的平均差值均大于Nemenyi檢驗(yàn)和Bonferroni-Dunn檢驗(yàn)的臨界差值(CD)。Conductance、ModularityCCME。在非網(wǎng)絡(luò)上，通過Bonferroni-Dunn檢驗(yàn)和Nemenyi檢驗(yàn)，本章的方法明顯優(yōu)于OSLOM和CCME。度量。在最后兩行，在顯著性水平為??0.05的Nemenyi檢驗(yàn)和Bonferroni-Dunn檢驗(yàn)的臨界差值Tab.3.2TheaveragerankdifferenceRD(a,b)betweentwomethods,whereadenotesourmethodandbrepresentsacompetinginternalvalidationmetric.Inlasttworows,thecriticaldifference(CD)thresholdsatthesignificancelevel??=0.05fortheNemenyitestandtheBonferroni-Dunntestarelisted,respectively.WeightedPPIRD(Ours,RD(Ours,RD(Ours,RD(Ours,CDCD表3.3在Hotep-down檢測下，兩種方法在PPI網(wǎng)絡(luò)（左列）和非網(wǎng)絡(luò)（右列）Tab.3.3Thep-valueP(a,b)fortherankdifferencebetweentwomethodsundertheHotep-downtestonweightedPPInetworks(theleftcolumn)andun-weightednetworks(therightcolumn),whereadenotesourmethodandbrepresentsacompetinginternalvalidationmetric.Inthemiddlecolumn,theadjustedsignificancelevelat??=0.05foreachpositionaftersortingthep-valuesinanon-decreasingorderislisted.αP(Ours,0P(Ours,P(Ours,0P(Ours,P(Ours,P(Ours,P(Ours,P(Ours,在表3.3中，根據(jù)Hotep-down檢驗(yàn)方法列出了本章的方法與每個(gè)對(duì)比方法之間的平均差的p值。此外，表3.3的中間一列列出了對(duì)p值進(jìn)行非降序排序后，每整顯著性水平。那么，通過Hotep-down檢驗(yàn)方法也表明了：在PPI網(wǎng)絡(luò)上，本章的方其他四種度量方法表現(xiàn)更好。類似于表3.2的結(jié)果，根據(jù)表3.3的假設(shè)檢驗(yàn)結(jié)果，可以看到本章的方法在非網(wǎng)絡(luò)上明顯優(yōu)于OSLOM和CCME。本章小本章主要詳細(xì)的描述了所一種評(píng)估社區(qū)統(tǒng)計(jì)顯著性的一般方法，以及該方法與一些對(duì)比方法在真實(shí)和真實(shí)無權(quán)數(shù)據(jù)集上的實(shí)驗(yàn)。本章開頭描述了在算法的分析過程中用到的一些符號(hào)以及概念。然后詳細(xì)介紹了本章所方法中用到的無參雙樣本檢測方法ogrnk檢驗(yàn)。隨后，介紹了基于Logrnk檢驗(yàn)社區(qū)計(jì)顯著評(píng)估方的主要流程在這個(gè)過中，缺失邊的權(quán)重值被設(shè)為零，所有邊權(quán)重值被視為刪失數(shù)據(jù)。基于這一假設(shè)，將社區(qū)驗(yàn)證問題建模為刪失數(shù)據(jù)上的雙樣本檢測問題。公式（3.2）從統(tǒng)計(jì)顯著性測試的角度提供了社區(qū)驗(yàn)證的一般框架?；谒?，本章在帶權(quán)網(wǎng)絡(luò)數(shù)據(jù)上以及無權(quán)網(wǎng)絡(luò)數(shù)據(jù)上均進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果證明了本章所提出方法的有效性。CCMEOSLOM都是通過計(jì)算每個(gè)節(jié)點(diǎn)屬于候選社區(qū)的概率來評(píng)估單個(gè)社區(qū)的統(tǒng)計(jì)顯著性。也就是說，這兩種方法不能提供一個(gè)解析p值來直接評(píng)估一個(gè)社區(qū)的統(tǒng)計(jì)顯檢測的目標(biāo)函數(shù)。因此，為了填補(bǔ)這一空白，本章提出了一種能在網(wǎng)絡(luò)中直接計(jì)算單個(gè)社區(qū)解析p值的新方法。該方法直接計(jì)算一個(gè)目標(biāo)社區(qū)在隨機(jī)圖中出現(xiàn)的概率，而不依賴于每個(gè)節(jié)點(diǎn)屬于候選社區(qū)的概率。為了從網(wǎng)絡(luò)中挖掘具有統(tǒng)計(jì)意義的社區(qū)，將所p值作為目標(biāo)函數(shù)進(jìn)一步提出了一種社區(qū)檢測算法，簡稱為MSSC。MSSC的搜索過程與文獻(xiàn)[27]中使用的搜索過程相似，文獻(xiàn)[27]使用了一個(gè)爬山算法，以迭代的方式尋找社區(qū)。為了提高運(yùn)行效率，本章進(jìn)一步提出了p值的上界和一個(gè)剪枝策給定一個(gè)網(wǎng)絡(luò)??=(??,??,??)，其中V是節(jié)點(diǎn)集合，E是邊集合，??{??1??2????????}M條邊的權(quán)重值集合，其中????i條邊（1≤??≤??）的權(quán)重值。N=|V|是節(jié)點(diǎn)個(gè)數(shù)，M=|E|是邊數(shù)。對(duì)于給定的節(jié)點(diǎn)子集??(??∈??)，其誘導(dǎo)子圖??[??]可被認(rèn)為是一個(gè)潛在的社區(qū)。以??[??]S中的節(jié)點(diǎn)相關(guān)聯(lián)的邊分為兩組：社區(qū)邊集合（每條邊的兩個(gè)節(jié)點(diǎn)都屬于S）；社區(qū)外部邊集合（每條邊兩個(gè)節(jié)點(diǎn)中，一個(gè)屬于S，另一個(gè)屬于V\S）。對(duì)于網(wǎng)絡(luò)??=(??????)????（????∈??），可以分別用??1和??0表示節(jié)點(diǎn)????SV\S內(nèi)的鄰居數(shù)。此外，用??1 示與??相連并且屬于社區(qū)邊集合的邊的權(quán)重之和；同理，??0表示與??相連并且屬于社區(qū)外部邊集合的邊的權(quán)重之和。本章直接評(píng)估單個(gè)候選社區(qū)的統(tǒng)計(jì)顯著性，也就??[??]p認(rèn)為這個(gè)候選社區(qū)是一個(gè)具有統(tǒng)計(jì)顯著性的社區(qū)。在原假設(shè)（0：子圖??[??]的邊與子圖??[??]的外部邊服從相同的分布p值。更準(zhǔn)確地說，pS??[]由于現(xiàn)在對(duì)于社區(qū)的定義沒有統(tǒng)一的規(guī)定，因此，為了計(jì)算p值，必須先確定“更子圖是否比真實(shí)網(wǎng)絡(luò)中的對(duì)應(yīng)子圖“更好”。設(shè)??1?0?1?0?[??] ?[??]∑??∈??[??] ∑??∈??[??]?1（1）?≥??，其中，??= ??和? ?[??]

∑??∈??[??]

∑??∈??[??]?0（2）?≤??，其中，?? ??和? ?[??]

∑??∈??[??]

∑??∈??[??]?0?≥??，其中，?? ??和? 分別表示??[??]和?[??]

∑??∈??[??]

∑??∈??[??]?0?≤??，其中，?? ??和? ?[??] p值計(jì)算

在原假設(shè)（H0：子圖??[??]的邊與子圖??[??]的外部邊服從相同的分布）成立的pS誘導(dǎo)的隨機(jī)子圖?[??]比誘導(dǎo)子圖??[??]在原始網(wǎng)絡(luò)中“更好”的隨機(jī)圖個(gè)數(shù)占總的隨機(jī)圖個(gè)數(shù)的比例。因此，需要計(jì)算所有隨機(jī)圖的數(shù)量（A表示）和能夠找到的“更好”子圖的隨機(jī)圖的數(shù)量（B表示）。下面將分別介紹這兩個(gè)數(shù)值A(chǔ)B的計(jì)算過程。首先，對(duì)于圖??=(??,??,??)，隨機(jī)圖的總數(shù)在不考慮權(quán)重信息的情況下為(2)2也就是從所有可能的(??)組節(jié)點(diǎn)對(duì)中選擇M組節(jié)點(diǎn)對(duì)來構(gòu)建M條邊。其次，可以將邊權(quán)劃分為??(1≤??≤??)q組根據(jù)權(quán)值進(jìn)行升序排序，即??1<??2<??<????4.ll組權(quán)重組別中，有????條邊的權(quán)重值2為????(1≤??≤??)。顯然 ????=??Tab.4.1Medgesaredividedintoqgroupswheretheedgesinthesamegrouphavethesame12…q……??=(

??1!??2!?

下面將介紹基于??=(??,??,??)空模型如何構(gòu)造滿足條件的隨機(jī)圖。相應(yīng)的，可以計(jì)算基于以下步驟，可以構(gòu)造一個(gè)滿足這種條件的隨機(jī)圖：由S中所有可能的節(jié)點(diǎn)對(duì)個(gè)數(shù)為(??)。然后，從節(jié)點(diǎn)集合S所有可能的(??)組節(jié)點(diǎn)對(duì)里選擇 組節(jié)點(diǎn)對(duì)來構(gòu)造??≥??1條邊。在這些所生成的i條邊中，有??1條邊的權(quán)重被賦值????(??∈[1??])。因此，有以下條件需要滿足：??=∑????1并且∑??(??1????)≥??1??=1 產(chǎn)生i條滿足條件的帶權(quán)重的邊的方法的個(gè)數(shù)是：((2)∑[(∑??

(??1??)≥??

???? 。其中第一個(gè)二項(xiàng)式系數(shù)是構(gòu)造 ?? ??=1 ?? ?? 束的情況下，給i條邊賦予權(quán)重值而產(chǎn)生的所有可能的隨機(jī)圖的個(gè)數(shù)。節(jié)點(diǎn)對(duì)來構(gòu)造??≤??0條外部邊。在這些生成的j條邊中，有??0????(??∈[1,??])。因此，有以下條件需要滿足：??= ??0并且 (??0????)≤??0。類??=1 的，相應(yīng)的產(chǎn)生j條滿足條件的帶權(quán)重的邊的方法的個(gè)數(shù)是： 0)] [(∑??=1????)=??, (?? ??=1(??2部分的邊。在這些生成的M-i-j條邊中，有???????1???0條邊的權(quán)重被賦值為????(??∈ [1,??])并且M-i-j= (???????1???0)。那么相應(yīng)的產(chǎn)生M-i-j條帶權(quán)重的邊的方法的2 2

(???

) ) ???????? ??(??? ??=∑∑(2) ) )??≥??1

??????

1 1} ??1)=??, (??1??)≥?? ??=1 ??

????? }

(??????

[(?????1? ??0)=??, (??0??)≤?? ??=1 ??

p值及其上界計(jì)算方法 ( (2) ) ????????????(??[??])==∑

(2

??≥??1

??1!??2!?

1 1} ??1)=??, (??1??)≥??

??=1 ??

????? }

(??????

[(?????1? ??0)=??, (??0??)≤?? ??=1 ??

為了準(zhǔn)確地根據(jù)公式計(jì)算p值，需要解決以下算法問題：“算法的輸入是M個(gè)非負(fù)的權(quán)重值??1??2????以及四個(gè)閾值??1、??0、??1和??0。算法的目的是計(jì)算將M個(gè)權(quán)重值分成三個(gè)不的子集并且滿足以下兩個(gè)條件的所有可能的不同分布的個(gè)數(shù)。對(duì)應(yīng)的兩個(gè)條件是：（1）在第一個(gè)子集中，子集內(nèi)元素的個(gè)數(shù)至少是??1，并且對(duì)應(yīng)的元和至少為??1；（2）在第二個(gè)子集中，子集內(nèi)元素的個(gè)數(shù)至多是??0，并且對(duì)應(yīng)的元和至多為??0?！?。0/1n??1??2????C的背包，0/10/15-7算法的時(shí)間復(fù)雜度仍然很高54]。例如，文獻(xiàn)5]所算法的時(shí)間復(fù)雜度至少是所給出物品個(gè)數(shù)的二次方。如果在社區(qū)檢測算法中使用p值作為目標(biāo)函數(shù)，那么由于這些算法的時(shí)間復(fù)雜度高，使用這些算法將是不可行的。因此，尋求在不需要解決背包計(jì)數(shù)問題的情況下近似計(jì)算pp值的上界和下，然后用兩個(gè)上界和來近真實(shí)的p值。p值的一個(gè)嚴(yán)格上限可以通過忽略兩個(gè)邊權(quán)重和的約束來求得。也就是說，如果條件限制 (??1??)≥??和 (??0??)≤??從p值的公式中移除，那么公式（4.3） ?? ?? 的最后兩行就等 方式的個(gè)數(shù)。因此，p值的上界（可以記作????(??[??])）( (???(2)

) ????(??[??])=∑??≥??1

(2

p值的上界????(??[??])是嚴(yán)格的，因?yàn)楫?dāng)不考慮權(quán)重值對(duì)社區(qū)結(jié)構(gòu)的影響時(shí)，也就是所重相同時(shí)，對(duì)應(yīng)的p值是等于方程（4.4）中的p值。而且，它等價(jià)于文獻(xiàn)[27]中給出的未網(wǎng)絡(luò)的精確p值。換句話說，權(quán)重信息在計(jì)算????(??[??])時(shí)沒有被利用。22??≤??(??)。令??=??????{??|1≤??≤??,∑????(??)≥??1}記作最小的r使得排序后的前r個(gè)權(quán)重之和不小于??1。同樣地，可以用??=??????{??|0≤??≤??,∑?? ??(??)≤??0}記作最大的r使得排序后的后r個(gè)權(quán)重之和不大于??0。在情況??>(|??|)時(shí)，本章令??=(|??|)。很明顯，??≥??1并且??≤??0。同時(shí)，任意??≥??條邊的權(quán)重之和不小于??1，并且任何??≤??條邊的權(quán)重之和不高于??0。基于上面的記號(hào)以及事實(shí)，在p值公式中，當(dāng)??22??,??≤??時(shí)，那么對(duì)于權(quán)重的約束成立。因此，可以得到p值的一個(gè)下界值記( ( ( ) ) ??(??[??])=∑ ??≥??

(2

很明顯的看到，p值的下界????(??[??])也是嚴(yán)格的。此外，可以看到它僅由權(quán)重集和顯然，精確的p值是在區(qū)間[????(??[??])，????(??[??])]之間。一種很自然的想法是求取一個(gè)帶權(quán)重的上下界和來近似p值（近似的p值記作????(??[??])），例如：????(??[??])=??×????(??[??])+(1???)×????(??[??])，其中0≤??≤1是一個(gè)用來調(diào)和上界和下界比例的為了進(jìn)一步提高p值的運(yùn)算效率，可以這樣計(jì)算????(??[??])：( ( ( ) )

(??[??])=∑

(2

其中，???????(1????1??????(1????0?根據(jù)Q和T的定義，公式中的近似p值（????(??[??])）依然在區(qū)間p值的時(shí)間復(fù)雜度為??((??2?))4.1p值的上界，這種方式可以更快的計(jì)算????(??[??])((

(?????定理4.1如果

=

??

<1并且??2=????(?????)???+1 1，那么公式（4.6）中的??(??[??])

1)(????????

( (2) )

2(???2)????(??[??])=∑

(2((2))(??(?????))((???)

)(??

1???)(????? 1?

]

( 1? 1?(2 22其中??1=????????,證明

0。

(???????(??[??])= ??≤??≤??1

) ) (2

()+(???

( (??? )( 2 (2) =

( ?? (2

( 2

((2

(???2

對(duì)于每一個(gè)固定的j滿足??≤??≤ ????????= + +?+ ??≤??≤??1()+(??? ?? ?? ( 2(2)(???) )()

((其中每個(gè)

????????。那么

2

，其中??1 ()+(??? ?,??= ( 2 ??1。接下來，將證明下面這個(gè)不等式

((2))((???) ((2))((???))1? )(??1??? ∑≤ ∑≤()+(???

?????[()+(???[

?? 1???≤??≤??1( 2

( 2

??導(dǎo)致分子的減少和分母的增加。因此，???,??(?=+1,?,??1)的最大值是????+1,??。如果

(2 2

(???)22

[1?(??

]

) ()+(??? ( 2

()+(??? ( (???))1?

)(??1??? )( 2)(2) ????(??[??])≤

????? ()+(???

[] 1???[]?? (2

( 2

2(??(?????))((2))((???))1?2(

(??1???)=

(2

1?????

((

(?????此外，當(dāng)??=??(??≤??≤)時(shí) 達(dá)到最大值。因此22

1)((?????)???+??22(??(?????))((2))((???))1?2(

(??1???)([

????????

??

≤

(2

1?

??(??1???

(???

1?

)(

2)=(2)

1?

]]

(??? (2

(

(???

(???) 對(duì)于不等式（ ）中的和，有∑?? (???)+(??? (???

(???

(

=????(?????)???+????(?????)???+1+? (???)+(???(??? 2(2)+(???)???+2(???

(???( ??=

)((???)+(???)???+

。那么，

=

(2)+(??? (???)+(???2(??(?????)???+1)((???)+??(?????)???+?? ，其中(??(????1)≤??≤(??(??????)??(????? 同樣地，????r的增大而減小，并且????(??=??(?????)+1??(?????)的最大值是

1。如果????(?????)???+11????(?????)???+

1+?????(?????)???2=????(?????)???+????(?????)???1????(?????)???+?+????(?????)???(????(?????)???+1?????(?????)???2)≤????(?????)???[1+

1+?+??

(??1 (???

(???

(?????(

)

(???)???1 (???)+(??? (

(???1?

(??? (???

) 2????(??[??])≤

2)

1?

]]

2 (???2(??1???

(???

(2

(???

1?

) ) 2 1? ≤(2) ] 1?

?? (2

(???(

1?????(?????)???((2))(??(?????))((???

1? )(??1???

1?

2

??

][ ( 1? 1?(2

((2))(??(?????))((???)

)(??

1?

)(????? 1? [ [

1?

] 1? (2 □2如果預(yù)先計(jì)算階乘的對(duì)數(shù)直到(??)!并將這些值預(yù)先在主器中，那么就可以在一定時(shí)間內(nèi)計(jì)算出二項(xiàng)式系數(shù)。因此，公式（4.7）的上界也可以在O(1)時(shí)間內(nèi)得到。如果在社區(qū)搜索過程中使用p值作為目標(biāo)函數(shù)，這是一個(gè)非常吸引人的特性。2當(dāng)??1<1并且??2<1時(shí)，上界將是合理的。由??1和??2的定義不難看出，當(dāng)增大時(shí)，??1將減?。徊⑶耶?dāng)減小時(shí)，??2將會(huì)減小。也就是說，對(duì)于邊數(shù)越多（或者邊權(quán)之和越大）外部邊數(shù)越少（或者外部邊權(quán)之和越?。┑暮蜻x社區(qū)??1<1和??2<的事實(shí)是，在每一階段的證明都類似于在文獻(xiàn)[58]中近似Fisher’s精確p值。然而，由于為了檢驗(yàn)所p值計(jì)算方法對(duì)社區(qū)評(píng)估是否有效，本章提出了一種新的社區(qū)檢測算法MSSC（從網(wǎng)絡(luò)中挖掘具有統(tǒng)計(jì)顯著性意義的社區(qū)），該算法使用公式（4.6）中的p值作為目標(biāo)函數(shù)。如算法4.1所示，MSSC算法的輸入由一個(gè)網(wǎng)??=(????,??)，顯著性水平??∈(0,1)，調(diào)整參數(shù)??∈[0,1]以及一個(gè)重合率參數(shù)??∈MSSC算法的第一步，一個(gè)集S初始化為空；另一left_V初始化V用于剩余部分的節(jié)點(diǎn)（第1行）。S用于檢測到的社區(qū)，并且left_V用于記錄在Algorithm.4.1ThepseudocodeofMSSCInput:AweightednetworkG=(V,E,W);thesignificancelevelα∈(0,1);atrade-offparameterθ∈[0,1];anoverlapscorethresholdγ∈[0;1];Output:AsetofstatisticallysignificantcommunitiesF.1:S←?;left_V←V;2:while|left_V|>03:C ??′ munity_expansion(G,C);if??′>2&&????(??′)≤α S←S∪ left_V←left_V-??′; endif left_V←left_V–{seed_node};10:endwhile11:F←MergeCommunities(S,在初始化步驟之后，MSSC算法使用局部搜索過程迭代地找到一組具有統(tǒng)計(jì)顯著性的社區(qū)（第2-9行）。在社區(qū)搜索過程中，該算法迭代地進(jìn)行社區(qū)的選擇和擴(kuò)展。作為默認(rèn)的選擇度量標(biāo)準(zhǔn)。對(duì)于密集網(wǎng)絡(luò)（如平均度≥10）和大型稀疏網(wǎng)絡(luò)（如5<平均度<10并且網(wǎng)絡(luò)規(guī)模>1000），本章采用度與局部聚類系數(shù)的乘積作為選擇準(zhǔn)則。需要說明的是，left_V是通過刪除被選擇為的節(jié)點(diǎn)或分配給由方法munity_expansion(G,C)返回的社區(qū)內(nèi)包含的節(jié)點(diǎn)來更新的（79行）。給定一個(gè)社區(qū)C，munity_expansion(G,C)是用來進(jìn)行檢測具有統(tǒng)計(jì)顯著性的社區(qū)??′（4行）4.2中進(jìn)行闡述。如果結(jié)果社區(qū)??′內(nèi)2或者??′p值不小于統(tǒng)計(jì)顯著性水平??，那么結(jié)果社區(qū)??′將不是一個(gè)具有統(tǒng)計(jì)顯著性的社區(qū)，那么，??′將不會(huì)加入到S中（第5–8行）。在MSSC算法的最后一步，合并率較高的社區(qū)，以減少冗余（第11行）。算法munity_expansion(G,C)是從網(wǎng)絡(luò)??=(??,??,??)中找到基于所給定的社區(qū)C的具有統(tǒng)計(jì)顯著性的社區(qū)C'。首先，計(jì)算社區(qū)C'的初始p值z(mì)0并且令C'=C（第1行）。然后，重復(fù)一個(gè)爬山搜索過程，找到一個(gè)具有統(tǒng)計(jì)顯著性的局部“最優(yōu)”的社區(qū)（2-14行）p值的新候選社C'（4行）C'（5行）z0pC'（第6-13行）。在算4.2中，最耗時(shí)的操作是4行和5行中找到最p值。如果計(jì)算單個(gè)節(jié)點(diǎn)更新后的所有候選社區(qū)的p值而不進(jìn)行剪枝操作，那么時(shí)間復(fù)雜度將會(huì)非常高。3.13.1中的上界。第二種策略是對(duì)候選社區(qū)的空間進(jìn)行剪枝，因?yàn)橛行┥鐓^(qū)在單節(jié)點(diǎn)更新后無法獲得比其他候選社區(qū)更小的p值。接下來將首先說明如何在第4行中快速找到去除單節(jié)點(diǎn)后的最小p值，然后以同樣的方式可以求解第5行中尋找“最優(yōu)”鄰居節(jié)點(diǎn)的優(yōu)化問題。({(),(,,(|??|,|??|)}表示點(diǎn)集對(duì)于去除每個(gè)節(jié)點(diǎn)后的|??′|個(gè)候選社區(qū)集合，那么，有如{(),(,(點(diǎn)后的|??′|pΡD所代表的候選社區(qū)中獲得，其D中的每一個(gè)點(diǎn)都優(yōu)Ρ中的任意一個(gè)點(diǎn)。如果????，并且??≤??那么點(diǎn)(??,??)就可以認(rèn)為優(yōu)于(??,??)。可知，((,(,此，定理4.2即成立。□Algorithm.4.2Thepseudocodeofseedcommunity Input:AweightednetworkG=(V,E,W);aseedcommunityC;atrade-offOutput:AstatisticallysignificantcommunityC';1:Let??0←????(??)and??′←??;2: ??′′← ????←????????????{????(??′–{??})|??∈??′}and????=????(??′– ????←????????????{????(??′∪{??})|(??,??)∈??,?????′,??∈??′}and????=????(??′∪ if??????{????,????}<??0 ??0=??????{????, if????<???? ??′=??′–{????}; ??′=??′∪{????}; endif end14:until??′′=15:return因此，為了加快社區(qū)擴(kuò)展過程，本章只計(jì)算D中的這些點(diǎn)的p值。實(shí)際上，這是計(jì)算幾何[59]中的一個(gè)點(diǎn)集極大值的問題。在這里，本章提出了一個(gè)基于排序的算法（算法4.3），它非常類似于文獻(xiàn)[60]中的方法。??????_非遞減的順序排序獲得?{(11),(22((|??|(|??|（2行。然后，可以選擇最上面的點(diǎn)(11)作為第一個(gè)優(yōu)先點(diǎn)（3行）并將其添加到集合D中（4行）。然后反復(fù)尋找下一個(gè)優(yōu)先點(diǎn)并將D中，直到第一次遇x軸坐標(biāo)為??????_的點(diǎn)（5-12行）。最后，返回優(yōu)先點(diǎn)集合D（13行）。Algorithm.4.3Thepseudocodeofnon-dominatedpointsetdetectioninpruning4.3Non-dominatedPointSetInput:ApointsetPOutput:Anon-dominatedpointsubsetD;1:??????_←??????{1,2,?,|??′|};2:Firstsort??inanon-increasingorderandthensort??inanon-decreasingorder:?{(((3:k←1;(5:index=2;6: if(??????????)<(??) k= D←D∪((??), end 12:until(??????????)==??????_13:return局部搜索過程可能檢測出相互之間具有冗余的社區(qū)[11,12]。因此，有必要消除那些冗余的社區(qū)，以獲得一個(gè)簡潔的社區(qū)集。為了評(píng)估兩個(gè)社區(qū)C和C'之間的率，本章使用以下率評(píng)估函數(shù)：??(??,??′)

|??∩??????(|??|,

當(dāng)率??(??,??′)大于用戶指定的閾值時(shí)，可以合并結(jié)果社區(qū)C和??′為一個(gè)社區(qū)2由于為了在O(1)中時(shí)間復(fù)雜度內(nèi)得到二項(xiàng)式系數(shù)，需要預(yù)先計(jì)算并到(??)范2內(nèi)的階乘的對(duì)數(shù)值，因此這一預(yù)處理步驟的時(shí)間復(fù)雜度為??(??2)N個(gè)節(jié)點(diǎn)的局部系數(shù)的時(shí)間復(fù)雜度最多為O(N×??2 )，其中????????是所有節(jié)點(diǎn)中最大的度。一般來說，大多數(shù)真實(shí)世界的網(wǎng)絡(luò)數(shù)據(jù)不是很密集，那么可以假設(shè)????????近似于√??。那么，計(jì)算局部系數(shù)的時(shí)間復(fù)雜度為??(??2)。在MSSC的節(jié)點(diǎn)選擇階段，最多考慮N個(gè)節(jié)點(diǎn)。因此，這一步的總體時(shí)間復(fù)雜度為??(??2)。在SSC算法的社擴(kuò)階，最慮N個(gè)社區(qū)。對(duì)于每個(gè)社區(qū)，它將迭代更新，直到收斂。在每次迭代中，需要通過加入或刪除一個(gè)節(jié)點(diǎn)來檢查和評(píng)估最多N個(gè)候選社區(qū)。在此過程中，可以在(M+×ogM)的時(shí)間內(nèi)得到所有候選社區(qū)的檢驗(yàn)統(tǒng)計(jì)量和?；谒惴?.3的剪枝策略最多需要對(duì)N(×og)的時(shí)間。如果假設(shè)上