基于聚類系數(shù)的鏈路預測算法改進
2017-03-24 13:11:25李星陶漢
電腦知識與技術(shù) 2017年1期
李星+陶漢
摘要： 鏈路預測是指通過已知的網(wǎng)絡信息來預測網(wǎng)絡中的丟失邊信息或者是錯誤連邊信息，鏈路預測是對于網(wǎng)絡分析和數(shù)據(jù)挖掘的一項支撐學科。經(jīng)過數(shù)十年的學科發(fā)展，鏈路預測得到了長足的發(fā)展，大量新的預測算法得以提出。本文提出了一種基于網(wǎng)絡節(jié)點中聚類系數(shù)的算法優(yōu)化思路，并將該優(yōu)化思路運用到9種經(jīng)典的算法上，在5種真實數(shù)據(jù)集上的實驗表明了該優(yōu)化思路的可行性。鏈路預測的準確性研究多基于丟失邊的預測，對于錯誤連邊的準確性預測少有涉及，本文的實驗部分同時涉及了丟失邊的預測以及錯誤連邊的預測。傳統(tǒng)的鏈路預測比較實驗，對于測試集多選取10%這一固定值，本文為了說明算法的健壯性，針對不同大小的測試集進行了廣泛的實驗。
關(guān)鍵詞：復雜網(wǎng)絡；鏈路預測；聚類系數(shù)；錯邊識別；局部相似性
中圖分類號：TP391 文獻標識碼：A 文章編號：1009-3044（2017）01-0239-05
Abstract： Link prediction is a subject which uses the current network information to predict the missing and spurious links， so it is a supporting discipline for network analysis and data mining. After decades of academic development， link prediction has achieve a lot of progress， a large number of algorithms have been proposed. In this paper， we have proposed an optimization thought which was inspired by clustering coefficient. We have applied this optimization methods to nine kinds of classical algorithms， results on five real data sets prove the feasibility of the optimization method. Former study on link prediction mainly focus on the prediction of missing links， while in this paper we have also concern the spurious links. Compared with the traditional research， we have doing experiments on varies ratio of training set， previous training set were fixed at 10% for the most conditions.
Key words： complex networks； link prediction； clustering coefficient； spurious links； local similarity
1 概述
關(guān)于網(wǎng)絡結(jié)構(gòu)的研究已有數(shù)百年的歷史，網(wǎng)絡學科的理論發(fā)展經(jīng)過了規(guī)則網(wǎng)絡，隨機網(wǎng)絡和復雜網(wǎng)絡三個階段。網(wǎng)絡上的首項研究可以追溯到1736年歐拉關(guān)于哥尼斯堡七橋問題的提出與解決，這屬于規(guī)則網(wǎng)絡時代的研究。之后的很長一段時間，網(wǎng)絡學科都沒有很大的發(fā)展。1959年，匈牙利的著名數(shù)學家Erd?s和Rényi建立了著名的隨機圖（ER）理論，這才將網(wǎng)絡研究帶入到了第二個階段[1]。隨機網(wǎng)絡的提出將網(wǎng)絡的理論研究拓展到了更為廣泛的科研領域，比如社會學家也可以利用隨機理論對于人類關(guān)系網(wǎng)絡進行建模。復雜網(wǎng)絡的開啟主要歸功于Watts和Strogatz在1998提出的小世界模型以及Barabási 在1999提出的無標度網(wǎng)絡[2，3]。小世界網(wǎng)絡指網(wǎng)絡中大多數(shù)的節(jié)點不直接相連，但彼此之間只需通過少量節(jié)點即可以到達，即“六度分離”理論的詮釋。無標度網(wǎng)絡指網(wǎng)絡中節(jié)點度的分布符合冪指數(shù)，即少數(shù)的節(jié)點具有很高的度分布而大多數(shù)節(jié)點的度相對較低。
近年來，隨著復雜網(wǎng)絡學科的快速發(fā)展，作為其分支之一的鏈路預測研究也得到了越來越廣泛的關(guān)注。網(wǎng)絡中的鏈路預測是指根據(jù)網(wǎng)絡現(xiàn)有的節(jié)點屬性以及網(wǎng)絡拓撲等信息來預測網(wǎng)絡中尚未產(chǎn)生連邊的兩個節(jié)點之間產(chǎn)生鏈接的可能性[4]。鏈路預測包含了對于未知邊的發(fā)掘以及網(wǎng)絡演化中即將產(chǎn)生的邊的預測。鏈路預測很好地將網(wǎng)絡與信息科學進行了連接，可以很好地處理信息科學中缺失信息的還原與預測。
鏈路預測具有重要的實踐以及理論價值[5，6，7]。人類已知的蛋白質(zhì)相互作用網(wǎng)絡只占真實網(wǎng)絡的冰山一角，很多蛋白質(zhì)之間是否有相互作用需要大量的實驗來驗證。酵母細菌的相互作用網(wǎng)絡已被觀察到的只有20%，人類網(wǎng)絡更是只有0.3%。由于驗證蛋白質(zhì)相互網(wǎng)絡將消耗巨大的人力以及時間的成本，所以如果能用鏈路預測的方式對可能存在的邊進行預測，進而指導實驗，將對于人類的生命工程產(chǎn)生巨大的推動作用。社交網(wǎng)絡中也存在信息丟失的情況。比如QQ當中，我們好友列表中并不能涵蓋我們?nèi)康暮糜研畔?。鏈路預測此時便可以根據(jù)現(xiàn)有好友列表向我們進行推薦可能認識的好友，進一步完善我們的好友列表 以及增強用戶對于產(chǎn)品的忠誠度。同樣的道理，鏈路預測的算法也可以在商品推薦中得以應用。鏈路預測的理論價值主要在于幫助我們更好的認識網(wǎng)絡的演化機制。針對某種或某類網(wǎng)絡，有許多模型都提供了可能的演化機制，但由于刻畫網(wǎng)絡性質(zhì)的統(tǒng)計變量很多，所以很難比較哪種演化機制更好。有了鏈路預測，我們便得到了一個統(tǒng)一量化的指標，利用該演化機制構(gòu)建鏈路預測的算法，算法預測準確率高者更符合網(wǎng)絡的演化，從而分析哪一個機制能夠更好的刻畫網(wǎng)絡的演化，這大大推進了網(wǎng)絡演化機制的研究工作。
早期的鏈路預測主要基于機器學習和馬爾科夫鏈。該類方法雖然具有較高的預測準確率，但較高的時間復雜度限制了被預測網(wǎng)絡的規(guī)模。同時，由于該類方法的分類往往需要獲取節(jié)點的屬性信息，節(jié)點的屬性信息往往很難獲取即使獲取節(jié)點信息也未必能保證信息的可靠性。比如在社交網(wǎng)絡之中，用戶的年齡、性別、住址未必會如實填寫，這便給該類基于節(jié)點屬性的算法造成了很大的障礙。由于基于馬爾科夫以及機器學習方法的弊端，最近幾年的鏈路預測更多轉(zhuǎn)移到了利用網(wǎng)絡的拓撲信息進行預測。利用網(wǎng)絡結(jié)構(gòu)進行預測的方法主要分為基于相似性的鏈路預測和基于似然分析的鏈路預測?；谙嗨菩缘逆溌奉A測的前提假設是，如果兩個點越相似那么這兩個點存在連邊的可能性越大。相比較基于相似性的鏈路預測，基于思然分析的鏈路預測是一種更為復雜的框架，雖然可以取得較高的準確率，但同基于機器學習的方法類似，當網(wǎng)絡節(jié)點數(shù)目達到數(shù)千個之時，算法處理起來之時便會感到吃力?？紤]到計算的復雜度以及通用性，本文所提出的算法可以歸納到基于相似性的鏈路預測框架之內(nèi)[8，9，10，11]。
在本文中，我們提出了利用網(wǎng)絡節(jié)點的聚類系數(shù)這一特征來提升基于相似性的鏈路預測算法的準確性這一思路。我們將聚類系數(shù)這一特征引入到了9個經(jīng)典的鏈路預測算法之中并得到了9種新的鏈路預測算法，對此我們在5個真實的數(shù)據(jù)集之上進行了實驗，實驗表明算法中聚類系數(shù)的引入可以在一定程度上提升網(wǎng)絡的預測準確性。由于過往鏈路預測的研究d多數(shù)只會進行丟失邊的實驗[12，13]，在此基礎上本文還添加了算法對于錯誤邊糾錯能力的實驗，實驗表明了我們新的算法在網(wǎng)絡噪聲糾錯能力上的提升。除此之外，過往研究將測試集的比例固定在10%這一值之上，我們對此進行了擴展，我們將測試集的比例伸展到了4%到20%范圍之間，進一步提升了實驗的完整性，這一范圍的變化也驗證了我們算法的健壯性。
2 問題描述
定義G（V， E）為一個無向網(wǎng)絡，其中V為節(jié)點集合，E為邊集合。網(wǎng)絡總的節(jié)點數(shù)為N，邊數(shù)為E。若該網(wǎng)絡為一個全連通網(wǎng)絡，那么該網(wǎng)絡共有N（N ?1）/ 2條邊，即全集U。給定某個鏈路預測算法，該算法會對每對沒有連邊的節(jié)點對（x，y）進行評分，賦予一個分數(shù)值Sxy。將所有未連接的邊進行評分，分數(shù)高的邊出現(xiàn)的概率大[14]。
關(guān)于丟失邊和錯誤連邊的預測稍有不同，下面對他們進行分別描述：
2.1 丟失邊的預測
為了預測算法的準確性，一般會將網(wǎng)絡中的邊劃分為兩個部分：訓練集ET和測試集EP。顯然，ETEP=E，且ETEP=?。我們將屬于U但不屬于E的邊稱作不存在的邊。在對算法進行準確度的測試時，我們只會利用到訓練集中的信息，即ET。
2.2 錯誤邊的預測
為了預測算法對錯誤連邊的識別率，我們將在現(xiàn)有網(wǎng)絡的基礎上增加一些連邊來模擬網(wǎng)絡中包含錯誤連邊的情況。現(xiàn)有網(wǎng)絡中的邊我們表示為E， 我們向網(wǎng)絡中添加的不存在的邊為EP，ET=EP+E， 在對算法進行準確度的測試時，我們同樣只會利用到訓練集中的信息，即ET。
3 數(shù)據(jù)集劃分
為了測試特定鏈路預測算法的準確性，我們需要從網(wǎng)絡之中選取一部分作為測試集，剩余部分作為訓練集。不同的測試集的選取方法會對實驗結(jié)果造成一定程度上的影響[15]。常見的測試集的選取方式主要有隨機抽取、逐項遍歷、k-折疊交叉實驗、滾雪球抽樣、熟識者抽樣、隨機游走抽樣、基于路徑抽樣這7種。本文中采取最為常用的隨機抽樣法。對于數(shù)據(jù)集的劃分，丟失邊的預測和錯誤邊的預測稍有區(qū)別。
3.1 丟失邊的預測
給定的網(wǎng)絡G中含有N個節(jié)點E條邊，現(xiàn)給定某一測試集的選取比例p，我們將等概率的從E條邊中選取p*E（若非整數(shù)，向上取整）條邊構(gòu)成測試集，E中的剩余邊作為訓練集。一般的鏈路預測試驗中p的選取比例為10%，為了驗證本文算法的健壯性，我們將p設置為 [0.04，0.08，0.12，0.16，0.20] 這五個不同的值。
3.2 錯邊的識別能力
若網(wǎng)絡G中含有E條邊，先給定某一測試集的選取比例，即錯誤邊的比例。我們將等概率的從不存在的邊中選取p*E（若非整數(shù)，向上取整）條邊構(gòu)成測試集EP，ET= E+EP。為了便于比較，我們p的選值范圍與丟失邊的情況相同。
4 經(jīng)典算法
1） CN指標（Common Neighbors）[16]。對于節(jié)點x，Γ（x）表示x的鄰居節(jié)點，同理Γ（y）表示y的鄰居節(jié)點，下式表示的便是x節(jié)點和y節(jié)點的共同鄰居數(shù)。該算法認為兩個節(jié)點擁有越多的共同鄰居數(shù)，越可能相連接。
2） Salton指標[17]。kx、ky分別表示節(jié)點x和節(jié)點y度的大小，salton指標也被人們稱作余弦相似度指標。
3） Jaccard指標[18]。該指標是Jaccard一百多年前所提出來的
4） Sorensen指標[19]。該指標主要用于生態(tài)網(wǎng)絡系統(tǒng)的預測。
5） 大度節(jié)點有利指標（hub promoted index， HPI）[20]。根據(jù)式子中的分母部分，我們知道該算法認為度較大的節(jié)點更有利于網(wǎng)絡的連接。
6） 大度節(jié)點不利指標（hub depressed index， HDI）[10]。相比較于上式，該算法認為度較大的節(jié)點不利于網(wǎng)絡的連接。
7） LHN指標[21]。與Sorensen指標類似，僅將分母元素的相加改為相乘。
8） AA指標（Adamic-Adar）[22]。這是對于CN指標的一種改進，該算法認為共同鄰居中，度較小的更利于網(wǎng)絡的連接。
9） RA指標（Resource Allocation）[10]。形式上類似于AA，但該算法是受到網(wǎng)絡中資源分配模型的啟發(fā)。
5 基于節(jié)點聚類系數(shù)的算法改進
5.1 聚類系數(shù)的定義
網(wǎng)絡中節(jié)點的聚類系數(shù)由Watts和Strogatz在1998年所提出。針對網(wǎng)絡中的某一個節(jié)點vi，其聚類系數(shù)定義為其鄰居間的連邊數(shù)量占可能連邊的比例，數(shù)學表示為：
其中ki表示節(jié)點vi的度，li表示節(jié)點vi的ki個鄰居之間的連邊數(shù)量[23]。
聚類系數(shù)表示了節(jié)點鄰居之間的連接緊密程度。在生活中，若將人類的生活抽象為社交網(wǎng)絡，若某人的聚類系數(shù)較大，那么該人的朋友之間相互認識的可能性越大，那么我們認為該人的好友之間產(chǎn)生連邊的概率較大?；诖蟮木垲愊禂?shù)促進網(wǎng)絡的連接，所以本文認為可將聚類系數(shù)這一特征融入到現(xiàn)有算法之中，提升算法對于部分網(wǎng)絡的預測準確度。
5.2 算法改進
對于以上提到的9種鏈路預測算法，加入節(jié)點的聚類系數(shù)這一特性之后，得到的改進算法如下所示：
6 實驗分析
本章的實驗部分，我們重點比較了9種經(jīng)典的鏈路預測算法與我們改進后的9種算法，在5類真實的數(shù)據(jù)集之上我們不僅比較了丟失邊預測的準確性同時比較了錯誤邊的恢復效果。本章將對數(shù)據(jù)集，評價指教，實驗結(jié)果三方面進行介紹。
6.1 實驗數(shù)據(jù)
6.1.1 數(shù)據(jù)說明
本文實驗中的數(shù)據(jù)是在pajek和stanford兩個數(shù)據(jù)集當中收集而來。USAir表示的是美國的航線信息，節(jié)點表示機場，若兩個機場之間有直達航線，那么該兩點之間存在一條連接邊。Elegans表示的是線蟲的神經(jīng)網(wǎng)絡，節(jié)點表示線蟲的神經(jīng)元，突觸或間隙表示為連邊。Footbal數(shù)據(jù)中的節(jié)點代表國家隊，這些國家中的球員頻繁參加國外聯(lián)賽，若國家隊中有成員在另外一個國家的聯(lián)賽中踢球，那么這兩個國家隊之間存在連邊信息。Jazz表示jazz演奏家之間的合作網(wǎng)絡。Karate是社會網(wǎng)絡分析領域中的經(jīng)典數(shù)據(jù)集，該網(wǎng)絡構(gòu)造了美國一所大學空手道俱樂部中34名成員的社會關(guān)系，若兩人在現(xiàn)實之中是好友關(guān)系，那么該兩人之間存在一條連邊。
6.1.2 數(shù)據(jù)的特征統(tǒng)計
|V|代表網(wǎng)絡中節(jié)點的數(shù)目。|E|代表網(wǎng)絡中邊的數(shù)目。D表示網(wǎng)絡的密度，計算公式為。C表示節(jié)點的聚類系數(shù)，上文已經(jīng)給出了計算公式。
6.2 評價指標
常見的鏈路預測算法的衡量指標有AUC（area under the receiver operating characteristic curve），Precision和Ranking Score三種。Precision考慮的是排在前K位的預測是否準確，Ranking Score側(cè)重于所預測邊的排序，AUC是三種當中最為常用的一種指標，他可以很好的從整體上衡量算法的準確度。
在丟失邊的預測之中，每次從測試集和不存在的邊當中分別取出一條邊，鏈路預測算法根據(jù)訓練集信息分別對兩條邊進行評分，如果測試集中邊的評分大于不存在的邊，那么加1，如果測試集中邊的評分等于不存在的邊，那么加0.5，如果測試集中邊的評分大于不存在的邊，那么加0。如此往復比較n次，若測試集中的邊分值大于不存在的邊的次數(shù)為n'，測試集中的邊分值等于不存在的邊的次數(shù)為n''。
在錯誤邊的預測中，每次從E和EP當中分別取出一條邊，如果E中邊的評分大于EP中的評分，那么加1，如果相等加0.5，否則加0。如此往復比較n次，若E中的邊分值大于EP邊的次數(shù)為n'，等于的次數(shù)為n''。
根據(jù)先前的劃分，網(wǎng)絡中的未知邊分為不存在的邊和測試集當中的邊。雖然測試集中的邊被劃分在了未知邊中，但好的算法是應該可以區(qū)分出不存在的邊和測試集當中的邊的，即根據(jù)算法測試集中邊出現(xiàn)的概率要高于不存在的邊。現(xiàn)，那么AUC值的計算公式為：
顯然，如果鏈路預測的算法不具備預測能力， AUC=0.5。因此AUC大于0.5的程度衡量了算法在多大程度上比隨機預測的方法精確。
6.3 實驗結(jié)果
為了保證試驗的準確定，當我們確定某一個p值之后，我們會對測試集進行100次劃分，劃分之間彼此不關(guān)聯(lián)，這主要是防止測試集的隨機性對試驗結(jié)果造成的誤差。測試集劃分好之后，我們將內(nèi)層循環(huán)次數(shù)確定為1000次，也就是說總循環(huán)比較的次數(shù)為100000次，該次數(shù)對應于上述AUC指標中的n。
以下便是實驗的結(jié)果：
1） Elegans網(wǎng)絡中缺失邊的發(fā)現(xiàn)與錯誤邊的糾正，左側(cè)為缺失邊的發(fā)現(xiàn)，右側(cè)為錯誤邊的糾正。下圖中共18種算法進行比較，其中原算法9種，加入聚類系數(shù)改進后的算法9種。為了便于比較，我們將某一算法和改進后的算法一一對應，這主要體現(xiàn)在繪圖時線段的顏色，如下圖所示CN和加入聚類系數(shù)后的CCN算法均由黑色線段表示，RA和CRA均由紅色表示。此外，原算法用虛線表示，改進后的算法用實線表示。結(jié)果圖的橫坐標表示所選取的訓練集的比例p，縱坐標表示算法的預測準確度。
從Elegans的實驗結(jié)果圖可以看出改進后的算法相比較原算法在準確率上有所提升，該效果的提升不僅在于發(fā)現(xiàn)丟失邊的情況同時適用于錯誤連邊的糾正。隨著測試集比例的提升，改進后的方法同樣優(yōu)于原算法。
2） Football網(wǎng)絡的實驗結(jié)果如下圖所示。實驗結(jié)果表明改進后的算法在整體上明顯優(yōu)于原先的算法，此外在鏈路預測的過程中我們發(fā)現(xiàn)當p=0.08時，預測的準確率達到最高值。
3） Jazz網(wǎng)絡的實驗結(jié)果如下圖所示。改進后的算法只在少數(shù)幾個點之上不能超越原算法，整體表現(xiàn)仍然十分優(yōu)異。
4） USAir網(wǎng)絡的實驗結(jié)果如下圖所示。該實驗結(jié)果分層現(xiàn)象十分明顯，改進后的算法曲線明顯在改進前算法的曲線之上，這表明加入聚類系數(shù)這一節(jié)點的局部信息之后，該
9種算法在美國航空網(wǎng)絡的預測上效果明顯提升。
5） Karate網(wǎng)絡的實驗結(jié)果如下圖所示。與上述四種網(wǎng)絡結(jié)果共同驗證了算法改進的有效性，此外我們發(fā)現(xiàn)這些鏈路預測算法對錯誤連邊的發(fā)現(xiàn)要略優(yōu)于預測不存在的邊。
7 總結(jié)與展望
聚類系數(shù)表示節(jié)點鄰居之間聯(lián)系的緊密程度，較高的聚類系數(shù)表明鄰居間較高的連接概率。受該指標的影響，我們將其特性添加到現(xiàn)有的9種鏈路預測算法之中得到了我們改進后的9種算法。通過在5種真實網(wǎng)絡上的實驗，我們發(fā)現(xiàn)了改進后的算法在這5種網(wǎng)絡上有著更好的表現(xiàn)。除此之外，針對不同大小的訓練集劃分比例，我們進行了大量的比較實驗，過往研究很少會探討訓練集p的大小對于實驗結(jié)果的影響。我們發(fā)現(xiàn)不同大小的訓練集對于實驗結(jié)果會產(chǎn)生影響，但改進后的算法與原算法的相對大小不變。最后，我們的鏈路預測實驗還包含了算法在錯誤連邊上的發(fā)掘能力，實驗表明，若我們有算法A、B，算法A相比B在丟失邊的發(fā)掘能力上可能會更好，但若換做是錯誤邊的發(fā)現(xiàn)，那么B算法可能會優(yōu)于A算法。
本研究只簡單地考慮了節(jié)點的聚類系數(shù)對于鏈路預測算法的影響，除此之外，在未來的研究當中我們可將更多的網(wǎng)絡特征融入到算法之中來進行算法的提升。本次實驗的網(wǎng)絡只有5種，更多數(shù)據(jù)的實驗有待補充，我們不排除特定網(wǎng)絡之上，改進后算法的準確率不如原算法。本次實驗網(wǎng)絡的節(jié)點只有幾百個，更大規(guī)模網(wǎng)絡的鏈路預測研究有待進一步深入。
參考文獻：
[1] Erd?s P， Rényi A. On Random Graphs[J]. Publicationes Mathematicae， 1959， 6：290-291.
[2] Watts D J， Strogatz S H. Collective dynamics of ‘small-worldnetworks[J]. nature， 1998， 393（6684）： 440-442.
[3] Barabási A L， Albert R. Emergence of scaling in random networks[J]. science， 1999， 286（5439）： 509-512.
[4] Lü L， Zhou T. Link prediction in complex networks： A survey[J]. Physica A： Statistical Mechanics and its Applications， 2011， 390（6）： 1150-1170.
[5] Gao F， Musial K， Cooper C， et al. Link prediction methods and their accuracy for different social networks and network metrics[J]. Scientific Programming， 2015， 2015： 1.
[6] Li D， Zhang Y， Xu Z， et al. Exploiting Information Diffusion Feature for Link Prediction in Sina Weibo[J]. Scientific reports， 2016， 6.
[7] 劉宏鯤， 呂琳媛， 周濤. 利用鏈路預測推斷網(wǎng)絡演化機制[J]. 中國科學： 物理學 力學 天文學， 2011， 41（7）： 81.
[8] Lü L， Pan L， Zhou T， et al. Toward link predictability of complex networks[J]. Proceedings of the National Academy of Sciences， 2015， 112（8）： 2325-2330.
[9] Chen B， Chen L. A link prediction algorithm based on ant colony optimization[J]. Applied Intelligence， 2014， 41（3）： 694-708.
[10] Zhou T， Lü L， Zhang Y C. Predicting missing links via local information[J]. The European Physical Journal B， 2009， 71（4）： 623-630.
[11] Liu Z， Dong W， Fu Y. Local degree blocking model for link prediction in complex networks[J]. Chaos： An Interdisciplinary Journal of Nonlinear Science， 2015， 25（1）： 013115.
[12] Guimerà R， Sales-Pardo M. Missing and spurious interactions and the reconstruction of complex networks[J]. Proceedings of the National Academy of Sciences， 2009， 106（52）： 22073-22078.
[13] Zhang P， Wang X， Wang F， et al. Measuring the robustness of link prediction algorithms under noisy environment[J]. Scientific reports， 2016， 6.
[14] 呂琳媛. 復雜網(wǎng)絡鏈路預測[J]. 電子科技大學學報， 2010， 39（5）： 651-661.
[15] Zhu Y X， Lü L， Zhang Q M， et al. Uncovering missing links with cold ends[J]. Physica A： Statistical Mechanics and its Applications， 2012， 391（22）： 5769-5778.
[16] Lorrain F， White H C. Structural equivalence of individuals in social networks[J]. The Journal of mathematical sociology， 1971， 1（1）： 49-80.
[17] Salton G， McGill M J. Introduction to modern information retrieval[J]. 1986.
[18] Jaccard P. Etude comparative de la distribution florale dans une portion des Alpes et du Jura[M]. Impr. Corbaz， 1901.
[19] Sorensen T. {A method of establishing groups of equal amplitude in plant sociology based on similarity of species and its application to analyses of the vegetation on Danish commons}[J]. Biol. Skr.， 1948（5）： 1-34.
[20] Ravasz E， Somera A L， Mongru D A， et al. Hierarchical organization of modularity in metabolic networks[J]. science， 2002， 297（5586）： 1551-1555.
[21] Leicht E A， Holme P， Newman M E J. Vertex similarity in networks[J]. Physical Review E， 2006， 73（2）： 026120.
[22] Adamic L A， Adar E. Friends and neighbors on the web[J]. Social networks， 2003， 25（3）： 211-230.
[23] 李建， 鄭曉艷. 復雜網(wǎng)絡聚類算法綜述[J]. 電腦知識與技術(shù)， 2015（5）： 019.
