基于改進(jìn)的節(jié)點(diǎn)貼近度簇劃分算法的研究

李慧 許英

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

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

中圖分類(lèi)號(hào)：N94;TP393 ?文獻(xiàn)標(biāo)識(shí)碼：A ?文章編號(hào)：1673-260X（2021）06-0023-05

引言

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

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

1 節(jié)點(diǎn)貼近度

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 理論模型

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

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

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

（1）每個(gè)節(jié)點(diǎn)在初始時(shí)刻被視為一個(gè)社區(qū)，任何一個(gè)節(jié)點(diǎn)都被隨機(jī)選為初始節(jié)點(diǎn)。

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

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

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

3 實(shí)驗(yàn)結(jié)果和分析

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

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

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

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

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

如圖2所示，劃分成兩個(gè)簇，NMI=1，沒(méi)有節(jié)點(diǎn)被錯(cuò)誤分類(lèi)，所以說(shuō)本文算法MSN能夠劃分簇且效果非常好。

3.3 美國(guó)足球隊(duì)網(wǎng)絡(luò)

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

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

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

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

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

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

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

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

4 結(jié)論

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

參考文獻(xià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〕甘立強(qiáng)，王旭陽(yáng)，燕楠，等.基于節(jié)點(diǎn)貼近度的簇劃分方法研究[J].計(jì)算機(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é)點(diǎn)貼近性度量的簇結(jié)構(gòu)劃分方法[J].計(jì)算機(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.