基于改進的節點貼近度簇劃分算法的研究

李慧 許英

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

關鍵詞：復雜網絡;節點貼近度;簇劃分;簇結構

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

引言

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

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

1 節點貼近度

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

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

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

然而，這種僅僅需要考慮網絡進行局部信息來度量貼近度的指標會導致網絡的過于局部最優，忽略了網絡的整體構架，從而導致與實際研究結果有很大的偏差。基于此，甘立強[11]提出將兩個節點間公共鄰居的網絡局部信息和兩個節點間最短路徑的網絡全局信息進行整合，并定義了節點貼近度Sim（i，j）：

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

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

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

2 基于節點貼近度的社區劃分算法

2.1 衡量網絡劃分質量的指標

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

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

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

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

2.2 理論模型

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

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

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

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

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

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

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

3 實驗結果和分析

本文通過將其應用于劃分四個真實網絡和計算機生成的基準網絡的社區結構，來評估所提出的貼近性度量的性能。四個實際網絡的方法的實驗數據，如表1所示。

3.1 Zachary空手道俱樂部網絡

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

3.2 海豚網絡

該網絡數據集是一個海豚社會關系網絡，來自新西蘭海峽六十二只海豚種群的交流。網絡中含有62個節點以及159條邊。節點代表單獨的海豚，每條邊代表兩只海豚之間的頻繁接觸。

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

3.3 美國足球隊網絡

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

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

3.4 美國政治書籍網絡

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

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

3.5 計算機生成網絡

除了實際網絡，還將此算法應用到著名的人工合成LFR（Lancichinetti-Fortunato-Radicchi）基準網絡[15]中。在這個網絡中，用一個混合因子？滋∈[0，1]測量群落結構的模糊化程度，值越低，表明群落結構的模糊化程度越低，清晰度越低，即簇組織結構越清楚[16]。基于不同大小的人工數據集計算NMI值。在實驗過程中，創建了五個不同節點數的計算機生成網絡，具體參數設定如表3所示，？滋值從0.1到0.9不等，NMI值結果如圖5所示。

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

4 結論

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

參考文獻：

〔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貼近度的簇發現方法[J].電子技術與軟件工程，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〕甘立強，王旭陽，燕楠，等.基于節點貼近度的簇劃分方法研究[J].計算機與數字工程，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〕梁宗文，楊帆，李建平.基于節點貼近性度量的簇結構劃分方法[J].計算機應用，2015，35（05）：1213-1217+1223.

〔15〕LANCICHINETTI A，FORTUNATO 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.