李慧 許英

摘 要：復(fù)雜網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)是數(shù)據(jù)挖掘領(lǐng)域的研究熱點，也是進一步發(fā)現(xiàn)社區(qū)關(guān)系知識的前提。根據(jù)網(wǎng)絡(luò)的系統(tǒng)局部信息和全局信息，計算通過網(wǎng)絡(luò)系統(tǒng)節(jié)點之間的貼近度矩陣，并將網(wǎng)絡(luò)節(jié)點可以按照貼近度和模塊度指標劃分為兩個不同的簇。在四個實際網(wǎng)絡(luò)數(shù)據(jù)集以及計算機生成網(wǎng)絡(luò)的實驗結(jié)果表明，該算法相比Newman、GN等[1]算法具有更高的準確率。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò);節(jié)點貼近度;簇劃分;簇結(jié)構(gòu)

中圖分類號：N94;TP393 ?文獻標識碼：A ?文章編號：1673-260X（2021）06-0023-05

引言

在不同的域中，許多類型的數(shù)據(jù)可以用網(wǎng)絡(luò)來表示，其中節(jié)點代表個體，節(jié)點之間的邊代表個體之間的關(guān)系。在社會網(wǎng)絡(luò)中，信息的傳遞、人與人之間的交流以及蛋白質(zhì)結(jié)構(gòu)的作用可以幫助我們通過將這些問題構(gòu)建復(fù)雜的網(wǎng)絡(luò)來分析。因此，復(fù)雜網(wǎng)絡(luò)起著重要的作用，而社區(qū)劃分是研究復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)和功能特征的最基礎(chǔ)的工作。多年來對于復(fù)雜網(wǎng)路的簇劃分進行了廣泛的研究，如GN（Girvan-Newman）算法[1]、譜劃分算法[2]、層次聚類算法[3]、標簽傳播算法（Label Propagation Algorithm，LPA）[4，5]、密度分值聚類算法[6]等。GN算法的基本理論思想是從網(wǎng)絡(luò)中刪除信息中介度最高的邊，直到?jīng)]有邊，每個時間節(jié)點是一個國家獨立的簇。譜方法是基于圖的Pierre-Simon Laplace矩陣，標簽傳播算法是一種適用于大規(guī)模復(fù)雜網(wǎng)絡(luò)的線性社區(qū)劃分方法，使用不同的標簽來識別不同的社區(qū);文獻中的密度峰值算法結(jié)合了Jaccard指數(shù)和最短路徑信息，形成復(fù)合貼近度[6]。然后，通過改進的密度峰值模型計算每個節(jié)點的密度和最小距離，并在關(guān)鍵節(jié)點列表中選擇密度最高、距離最短的節(jié)點。此外閾值條件使密度峰模型分析能夠更加準確地選擇一個具有一定代表性的關(guān)鍵節(jié)點。社區(qū)聚類的內(nèi)容包括非關(guān)鍵節(jié)點的分配、社區(qū)的合并和不穩(wěn)定節(jié)點的屬性修改。

社區(qū)進行劃分的基本理論思想是將具有非常貼近屬性的節(jié)點劃分為同一個領(lǐng)域。因此，本文主要研究基于局部貼近度的算法，構(gòu)造節(jié)點貼近度矩陣（Modified Similarity Matrix，MSN）MSN={Sij}，Sij表示節(jié)點i和j的貼近性程度。根據(jù)貼近度矩陣對社區(qū)進行初步劃分。

1 節(jié)點貼近度

計算節(jié)點貼近度方法主要分為基于全局和基于局部信息這兩類，比如Jaccard[7]，AA，PA[8]，RA[9]，HPI[10]，CRA，CPA等貼近度指標，RA指數(shù)是構(gòu)造節(jié)點貼近度的最有效方法[10]。

RA方法通過模擬網(wǎng)絡(luò)中的資源分配過程來測量兩個節(jié)點的貼近性。對于任何一個網(wǎng)絡(luò)，都不能看作是一些重要節(jié)點和一些邊組成的圖。定義圖G=（V，E），其中V是頂點集，E是邊集。頂點數(shù)n=|V|，邊數(shù)k=|E|。假設(shè)圖G（V，E）中節(jié)點對（i，j）通過它們共同的鄰居進行通信，兩個節(jié)點的親密程度取決于它們共同鄰居的程度。將節(jié)點i和節(jié)點j之間的貼近度定義為貼近度，公式如下：

其中，k（z）表示節(jié)點i和j的公共鄰居z的度，？祝（i）表示節(jié)點i的所以鄰居節(jié)點的集合。

然而，這種僅僅需要考慮網(wǎng)絡(luò)進行局部信息來度量貼近度的指標會導(dǎo)致網(wǎng)絡(luò)的過于局部最優(yōu)，忽略了網(wǎng)絡(luò)的整體構(gòu)架，從而導(dǎo)致與實際研究結(jié)果有很大的偏差?；诖?，甘立強[11]提出將兩個節(jié)點間公共鄰居的網(wǎng)絡(luò)局部信息和兩個節(jié)點間最短路徑的網(wǎng)絡(luò)全局信息進行整合，并定義了節(jié)點貼近度Sim（i，j）：

其中d（i，j）表示節(jié)點i和節(jié)點j之間最短路徑的長度，n表示網(wǎng)絡(luò)的節(jié)點總數(shù)。節(jié)點i，j可達是指節(jié)點i，j之間有邊直接相連。當d（i，j）越大時，則貼近度矩陣Sim（i，j）中元素值就越小，也就意味著兩個節(jié)點越不貼近。同時，兩個節(jié)點之間如果沒有直接聯(lián)系，則意味著兩個節(jié)點之間的信息交換主要依賴于相鄰節(jié)點，因此忽略它，將貼近度設(shè)置為0。同時，乘以節(jié)點總數(shù)n從而可以適當進行放大結(jié)果，避免結(jié)果過小，超出計算機的計算能力范圍。

然而，該算法忽略了節(jié)點可達但沒有公共鄰居的情況，這也可能造成與實際網(wǎng)絡(luò)的較大偏差。該算法定義，如果兩個節(jié)點之間有邊，但沒有公共鄰居，則兩個節(jié)點之間的貼近性為零。事實上，如果兩個重要節(jié)點之間有一條邊，但是由于沒有一個共同的鄰居，那么兩個不同節(jié)點的度越大，它們發(fā)展之間的貼近度就越小，成反比關(guān)系，但并不意味著它們之間的貼近度就可以忽略不計。基于共同鄰居的局部信息和節(jié)點間最短路徑的全局信息，重新定義了節(jié)點貼近度，Sim（i，j）公式如下：

其中，i～j表示節(jié)點i和j互相連通。

2 基于節(jié)點貼近度的社區(qū)劃分算法

2.1 衡量網(wǎng)絡(luò)劃分質(zhì)量的指標

標準化互信息（NMI），為了量化被檢測群落與被分割群落之間的貼近性，可以利用標準化交互信息（NMI）來評價群落劃分的質(zhì)量，NMI值的范圍在[0，1]之間，越接近1，算法的效果越好，可以挖掘出更多的真實群落結(jié)構(gòu)[12]。計算NMI值公式如下：

其中，N是節(jié)點數(shù)，A和B代表真實的社區(qū)，以及由算法劃分的社區(qū)的結(jié)果。C表示模糊矩陣，矩陣中元素Cij表示屬于A劃分中的社區(qū)i的節(jié)點也屬于B劃分中的社區(qū)j的節(jié)點。

衡量簇結(jié)果性能另外一個最普遍的標準是模塊度（Modularity），這是由Mark Newman等人[3]提出，最常用的衡量網(wǎng)絡(luò)中社區(qū)分割質(zhì)量標準的基本思想是將劃分為社區(qū)的網(wǎng)絡(luò)與相應(yīng)的零模型進行比較，以衡量網(wǎng)絡(luò)中社區(qū)的結(jié)構(gòu)強度。一般模塊度定義如下：

其中，ki是點i的度，函數(shù)？啄（ci，cj）的取值定義為：如果點i和j在一個社區(qū)，即ci=cj，則函數(shù)？啄（ci，cj）值為1，否則為0。m為網(wǎng)絡(luò)中邊的總數(shù)。Aij為網(wǎng)絡(luò)的鄰接矩陣的一個元素。

2.2 理論模型

每個節(jié)點在初始時刻都可以被視為一個社區(qū)，并且算法選擇任意節(jié)點作為初始節(jié)點，所以本文算法不需要知道網(wǎng)絡(luò)的先驗信息，另外由于孤立節(jié)點在劃分社區(qū)過程中意義不大，所以假設(shè)網(wǎng)絡(luò)中沒有孤立的節(jié)點。社區(qū)劃分的目的是將具有貼近屬性的節(jié)點劃分到同一個社區(qū)中，因此本文先采用式（3）來計算節(jié)點之間的貼近度，構(gòu)建一個貼近度矩陣MSN={Sij}，其中Sij表示節(jié)點i和j的貼近性程度。然后，再進行后續(xù)操作：將包含該節(jié)點的社區(qū)與包含與該節(jié)點最貼近的節(jié)點的社區(qū)合并，生成一個新的社區(qū)。確定下一個待處理節(jié)點。選擇與當前節(jié)點最貼近的節(jié)點作為下一個節(jié)點。如果此新節(jié)點未包含在當前社區(qū)中，請轉(zhuǎn)到前一步執(zhí)行進一步合并。否則，將隨機選擇一個新的未訪問節(jié)點作為初始節(jié)點，并在第一步執(zhí)行一個新的社區(qū)合并。重復(fù)合并，直到網(wǎng)絡(luò)中的所有節(jié)點都被訪問，形成小的社區(qū)。

初步合并完節(jié)點之后，再進行小簇合并，所遵循的原則是如果簇之間合并完成后能提高所計算的NMI值，則進行合并，反之則不進行合并。重復(fù)此步驟，直到NMI最大時，結(jié)束過程。

根據(jù)節(jié)點貼近性度量的簇分割方法具體操作步驟總結(jié)如下：

（1）每個節(jié)點在初始時刻被視為一個社區(qū)，任何一個節(jié)點都被隨機選為初始節(jié)點。

（2）然后計算節(jié)點貼近度矩陣S={Sij}，其中i=1，2，…，n，j=1，2，3…，n，從剩余的節(jié)點中選擇最貼近的節(jié)點，并將它們合并成一個新的社區(qū)。

（3）最后，以新節(jié)點作為初始節(jié)點，尋找最貼近度的節(jié)點。如果發(fā)現(xiàn)的節(jié)點不在當前進行合并的社區(qū)中，則將該節(jié)點合并到該社區(qū)中，如果是，則隨機進行選擇其余未處理的節(jié)點中的一個可以作為研究初始節(jié)點返回（2）。

（4）重復(fù)迭代步驟（3），直至簇交互化信息NMI達到最大值，算法結(jié)束。最后計算了群落劃分的結(jié)果以及對應(yīng)的交互化信息NMI值和模塊化Q值。

3 實驗結(jié)果和分析

本文通過將其應(yīng)用于劃分四個真實網(wǎng)絡(luò)和計算機生成的基準網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，來評估所提出的貼近性度量的性能。四個實際網(wǎng)絡(luò)的方法的實驗數(shù)據(jù)，如表1所示。

3.1 Zachary空手道俱樂部網(wǎng)絡(luò)

這個網(wǎng)絡(luò)是一個經(jīng)典的耗時兩年收集整理的網(wǎng)絡(luò)數(shù)據(jù)集，20世紀70年代的社會學家扎卡里觀察了美國一所大學空手道俱樂部的34名成員的社會關(guān)系，基于這些成員在俱樂部內(nèi)外的互動，一個社會網(wǎng)絡(luò)被構(gòu)建，由三十多個節(jié)點和七十多條邊組成，兩個節(jié)點之間的邊表示相應(yīng)的兩個節(jié)點是親密的朋友。在圖1中，通過我們算法劃分的兩個簇用不同的數(shù)字表示，而該網(wǎng)絡(luò)的真實組則用不同的顏色標記。如圖1所示，本文算法MSN能夠準確劃分簇，NMI=1，沒有節(jié)點被錯誤分類，因此，本文提出的貼近度量矩陣劃分方法適用于空手道俱樂部網(wǎng)絡(luò)劃分。

3.2 海豚網(wǎng)絡(luò)

該網(wǎng)絡(luò)數(shù)據(jù)集是一個海豚社會關(guān)系網(wǎng)絡(luò)，來自新西蘭海峽六十二只海豚種群的交流。網(wǎng)絡(luò)中含有62個節(jié)點以及159條邊。節(jié)點代表單獨的海豚，每條邊代表兩只海豚之間的頻繁接觸。

如圖2所示，劃分成兩個簇，NMI=1，沒有節(jié)點被錯誤分類，所以說本文算法MSN能夠劃分簇且效果非常好。

3.3 美國足球隊網(wǎng)絡(luò)

這個網(wǎng)絡(luò)代表了115支大學橄欖球隊，一個賽季的一百多個節(jié)點和六百多條邊的時間表。網(wǎng)絡(luò)中的每個節(jié)點代表某國橄欖球賽季的大學代表隊，兩個節(jié)點之間的邊表明各自的球隊之間至少進行了一場比賽。根據(jù)本文算法，該網(wǎng)絡(luò)分為十二個簇。用代碼將這些算法劃分得到的社區(qū)用不同的數(shù)字表示，而該網(wǎng)絡(luò)的真實組則以不同的顏色標記。如圖3所示，有九個節(jié)點被錯誤分類，但NMI=0.9252274，NMI值接近1，整體劃分較為明顯。

此外，如表2所示，該算法計算的模塊度高于其他三種算法，說明該算法的質(zhì)量優(yōu)于其他三種算法。

3.4 美國政治書籍網(wǎng)絡(luò)

該網(wǎng)絡(luò)是通過研究2004年總統(tǒng)競選期間購買的一些美國政治書籍而建立起來的，其中有一百多個節(jié)點和四百多條邊。節(jié)點代表美國在線書店出售的與美國政治教育相關(guān)的書籍，而邊則代表一定數(shù)量且同時購買這兩本書的讀者，也就是說這兩本書是同一個目標客戶經(jīng)常購買的。這些網(wǎng)絡(luò)中的政治書籍主要分為三類：自由派、中間派和保守派。這些類別是由Newman根據(jù)書中觀點進行人工分析綜合銷售平臺上的評價而劃分的。

根據(jù)本文算法，該網(wǎng)絡(luò)分為三個簇。同樣，我們用代碼將這些算法劃分得到的社區(qū)用不同的數(shù)字表示，而該網(wǎng)絡(luò)的真實組則以不同的顏色標記。如圖4所示，有十一個節(jié)點被錯誤分類，但錯誤率在合理范圍內(nèi)，NMI值較高，相比較而言，整體劃分較為正確。

3.5 計算機生成網(wǎng)絡(luò)

除了實際網(wǎng)絡(luò)，還將此算法應(yīng)用到著名的人工合成LFR（Lancichinetti-Fortunato-Radicchi）基準網(wǎng)絡(luò)[15]中。在這個網(wǎng)絡(luò)中，用一個混合因子？滋∈[0，1]測量群落結(jié)構(gòu)的模糊化程度，值越低，表明群落結(jié)構(gòu)的模糊化程度越低，清晰度越低，即簇組織結(jié)構(gòu)越清楚[16]?；诓煌笮〉娜斯?shù)據(jù)集計算NMI值。在實驗過程中，創(chuàng)建了五個不同節(jié)點數(shù)的計算機生成網(wǎng)絡(luò)，具體參數(shù)設(shè)定如表3所示，？滋值從0.1到0.9不等，NMI值結(jié)果如圖5所示。

從圖5中可以看出，當0.1≤？滋≤0.3時，所有網(wǎng)絡(luò)都有較高NMI值，且NMI值都基本相等，說明此時劃分算法在人工數(shù)據(jù)集上能夠較為清晰地劃分簇結(jié)構(gòu)，而當？滋≥0.3時，這五個網(wǎng)絡(luò)開始呈現(xiàn)差異，節(jié)點數(shù)越多的網(wǎng)絡(luò)NMI值越高，隨著混合參數(shù)值的增大，NMI值呈下降趨勢，其中在0.4≤？滋≤0.8時，基本所有網(wǎng)絡(luò)NMI值下降較為迅速。在圖5中，網(wǎng)絡(luò)的節(jié)點總數(shù)為1000，節(jié)點的平均度k=15，節(jié)點的最大度Max K=50，節(jié)點的最小度Min K=15，簇的最小尺寸Min C=20，簇的最大尺寸Max C=50，度指標td=2，簇指數(shù)tc=1。與文獻中的標記傳播算法相比，該算法具有更高的歸一化互信息值，即其社區(qū)h的分割結(jié)果更加精確[4]。

4 結(jié)論

本文提出了作為一種可以基于節(jié)點貼近性的社區(qū)檢測技術(shù)方法。首先定義節(jié)點間的貼近度，對小社區(qū)中最貼近的節(jié)點進行聚類。然后將這些社區(qū)合并，以找到一個穩(wěn)定的社區(qū)結(jié)構(gòu)。通過測試和與以前的社區(qū)檢測方法的比較來驗證?；诠?jié)點貼近性，提出了一種快速高效的檢測網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的算法，保證了一對貼近度較高的節(jié)點更有可能被分組為一個社區(qū)。它不需要事先知道整個網(wǎng)絡(luò)的結(jié)構(gòu)，并且比其他方法具有更低的計算復(fù)雜度。該算法已應(yīng)用于各種信息網(wǎng)絡(luò)，包括實際收集的網(wǎng)絡(luò)和計算機生成網(wǎng)絡(luò)，表明發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)是相當有效地在實際和計算機生成的網(wǎng)絡(luò)上取得的實驗結(jié)果表明，本文的方法在發(fā)現(xiàn)通過網(wǎng)絡(luò)中的社區(qū)組織結(jié)構(gòu)設(shè)計方面具有非常有效。該方法是在無向無權(quán)網(wǎng)絡(luò)的基礎(chǔ)上發(fā)展起來的，可以推廣到有向網(wǎng)絡(luò)和加權(quán)網(wǎng)絡(luò)，并包含某些參數(shù)，如權(quán)重、計算模塊化的方向等。

參考文獻：

〔1〕GIRVANM， NEWMANMEJ.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences，2002，99（12）：7821-7826.

〔2〕F.Chung， Spectra Graph Theory. American Mathematical Society， Providence， 1997.

〔3〕Clauset Aaron， Newman M E J， Moore Cristopher. Finding community structure in very large networks.. 2004， 70（6 Pt 2）：066111.

〔4〕Asgarali Bouyer，Hamid Roghani. LSMD：A fast and robust local community detection starting from low degree nodes in social networks[J]. Future Generation Computer Systems，2020，113.

〔5〕W. Li， C. Huang， M. Wang， X. Chen， Stepping community detection algorithm based on label propagation and similarity， Physica A： Statistical 365 Mechanics and its Applications 2017，472 ：145–155.

〔6〕Zheng-Hong Deng，Hong-Hai Qiao，Ming-Yu Gao，Qun Song，Li Gao. Complex network community detection method by improved density peaks model[J]. Physica A： Statistical Mechanics and its Applications，2019，526.

〔7〕孫宇.一種基于Jaccard貼近度的簇發(fā)現(xiàn)方法[J].電子技術(shù)與軟件工程，2016（03）：20.

〔8〕Farshad Aghabozorgi， Mohammad Reza Khayyambashi. A new similarity measure for link prediction based on local structures in social networks. 2018， 501：12-23.

〔9〕T. Zhou， L. L， Y.C. Zhang， Predicting missing links via local information， Eur. Phys. J. B， 2009，71（04）：623–630.

〔10〕Peng Zhang， Dan Qiu， An Zeng， et al. A comprehensive comparison of network similarities for link prediction and spurious link elimination. 2018， 500：97-105.

〔11〕Ajay Kumar，Shashank Sheshar Singh，Kuldeep Singh，Bhaskar Biswas. Link prediction techniques， applications， and performance： A survey[J]. Physica A： Statistical Mechanics and its Applications， 2020：553.

〔12〕甘立強，王旭陽，燕楠，等.基于節(jié)點貼近度的簇劃分方法研究[J].計算機與數(shù)字工程，2018，46（02）：213-217+240.

〔13〕NEWMAN M E J.Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences， 2006，103（23）： 8577 - 8582.

〔14〕梁宗文，楊帆，李建平.基于節(jié)點貼近性度量的簇結(jié)構(gòu)劃分方法[J].計算機應(yīng)用，2015，35（05）：1213-1217+1223.

〔15〕LANCICHINETTI A，F(xiàn)ORTUNATO S，RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E，2008，78（04）：046110.

〔16〕DANON L， DIAZ-GUILERA A， DUCH J，et al. Comparing community structure identification[J]. Journal of Statistical Mechanics： Theory and Experiment， 2005（09）： P09008.