一種有向復(fù)雜網(wǎng)絡(luò)生成模型的建立方法

劉大偉，楊文峰，王海洋，3，劉 瑋，3

1(中國(guó)科學(xué)院 計(jì)算技術(shù)研究所煙臺(tái)分所 煙臺(tái)中科網(wǎng)絡(luò)技術(shù)研究所，山東 煙臺(tái) 264005)

2(中移(蘇州)軟件技術(shù)有限公司，江蘇 蘇州 215000)

3(中國(guó)科學(xué)院 計(jì)算技術(shù)研究所 網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100090)

1 引 言

網(wǎng)絡(luò)作為一種刻畫復(fù)雜系統(tǒng)的方式，已經(jīng)廣泛應(yīng)用于各種網(wǎng)絡(luò)數(shù)據(jù)應(yīng)用中.在一個(gè)網(wǎng)絡(luò)中，節(jié)點(diǎn)通常表示個(gè)體，鏈路通常表示節(jié)點(diǎn)之間的關(guān)聯(lián)關(guān)系.鏈路挖掘(Link Mining)[1]成為熱門研究領(lǐng)域，特別是結(jié)合上下文的交互分析和探索交互結(jié)構(gòu)特征的分析等.通過(guò)拓?fù)涮卣鱽?lái)揭示網(wǎng)絡(luò)功能，理解網(wǎng)絡(luò)演化的本質(zhì)規(guī)律成為鏈路挖掘的重要基礎(chǔ).大量研究提出了一系列鏈路挖掘的結(jié)構(gòu)和關(guān)系模型.周[2]總結(jié)了現(xiàn)有的網(wǎng)絡(luò)生成機(jī)制并總結(jié)為三個(gè)類別：宏觀機(jī)制，例如富者更富，穩(wěn)定性約束等；微觀機(jī)制，例如相近性，集聚性和平衡理論等；中觀機(jī)制，例如群體和社區(qū)的生成和變換.近期，隨著在線社交網(wǎng)絡(luò)的發(fā)展，鏈接數(shù)據(jù)以更為復(fù)雜的方式進(jìn)行表示，尤其是越來(lái)越多的應(yīng)用對(duì)應(yīng)的底層網(wǎng)絡(luò)模型開始使用有向網(wǎng)絡(luò)進(jìn)行刻畫[3].現(xiàn)有的機(jī)制更多的是針對(duì)無(wú)向網(wǎng)絡(luò)的觀察和總結(jié)，缺少對(duì)于鏈接數(shù)據(jù)方向性的考慮.因此，本文關(guān)注有向網(wǎng)絡(luò)的微觀生成機(jī)制，提出一種新的鏈路生成方法.

在現(xiàn)實(shí)世界中有向網(wǎng)絡(luò)普遍存在，例如WWW，食物鏈網(wǎng)絡(luò)，學(xué)術(shù)合作網(wǎng)絡(luò)和微博等社交網(wǎng)絡(luò).將網(wǎng)絡(luò)數(shù)據(jù)挖掘問(wèn)題用有向鏈路的生成模式來(lái)抽象和表達(dá)能夠獲得更多的洞察與分析結(jié)果.本文中，我們結(jié)合現(xiàn)有的機(jī)制，研究了有向表示下的網(wǎng)絡(luò)生成模型，提出了一種鏈路生成理論，稱為局部相關(guān)位置方法(Local Relative Position，LRP)，用來(lái)對(duì)網(wǎng)絡(luò)演化機(jī)制進(jìn)行刻畫，可應(yīng)用于不同的鏈路挖掘問(wèn)題.我們選擇采用鏈路預(yù)測(cè)應(yīng)用并構(gòu)建了基于真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)來(lái)檢驗(yàn)提出的理論方法的有效性.

2 相關(guān)工作

在復(fù)雜網(wǎng)絡(luò)領(lǐng)域，尤其是社交網(wǎng)絡(luò)的研究方向中，有很多鏈路生成的理論方法，包括無(wú)向和有向的配置.同時(shí)，許多針對(duì)網(wǎng)絡(luò)生成理論演化出來(lái)的相似性指標(biāo)已經(jīng)用于鏈路預(yù)測(cè)的任務(wù)中.

早期的一些研究工作的研究對(duì)象多為社交網(wǎng)絡(luò)、生物化學(xué)網(wǎng)絡(luò)、生態(tài)學(xué)網(wǎng)絡(luò)、工程網(wǎng)絡(luò)等，旨在提出網(wǎng)絡(luò)底層結(jié)構(gòu)的生成機(jī)制和設(shè)計(jì)原則.Milo等[4]提出一種網(wǎng)絡(luò)圖式(Network Motifs)模型，通過(guò)局部的網(wǎng)絡(luò)圖式來(lái)刻畫網(wǎng)絡(luò)的內(nèi)部鏈路間典型的模式.例如，在19個(gè)真實(shí)有向網(wǎng)絡(luò)中抽象出13種由3個(gè)節(jié)點(diǎn)構(gòu)成的鏈路子圖模式，即13中網(wǎng)絡(luò)圖式.值得注意的是，相比于無(wú)向網(wǎng)絡(luò)，有向網(wǎng)絡(luò)具有更多更復(fù)雜的局部結(jié)構(gòu)類型.以兩個(gè)節(jié)點(diǎn)A和B構(gòu)成的模式為例，局部結(jié)構(gòu)類型從無(wú)向配置的1種(A-B)增加到有向配置的3種(A→B，A←B和A<->B).在社交網(wǎng)絡(luò)的應(yīng)用中，有向網(wǎng)絡(luò)的鏈路生成模式比無(wú)向網(wǎng)絡(luò)得到更多的關(guān)注和研究，尤其是微博網(wǎng)絡(luò)，網(wǎng)絡(luò)中的關(guān)注關(guān)系是不對(duì)稱的.Golder等[5]研究了Twitter數(shù)據(jù)，構(gòu)建了基于Web的實(shí)驗(yàn)分析，發(fā)現(xiàn)在新鏈路生成的過(guò)程中，傳遞性(transitivity)和相互性(mutuality)起到了重要作用，可以用來(lái)作為鏈路的預(yù)測(cè)算子.Yin等[6]研究了社交網(wǎng)絡(luò)和信息網(wǎng)絡(luò)，總結(jié)了新鏈路的關(guān)系類型分布，發(fā)現(xiàn)90%以上的新鏈路是在兩條之內(nèi)的局部結(jié)構(gòu)中產(chǎn)生的.Garlaschelli等[7]關(guān)注鏈路的互惠性(reciprocity)，提出了一種新的互惠性度量方法，利用相互連接計(jì)算相關(guān)度并對(duì)網(wǎng)絡(luò)鏈路進(jìn)行重排.近期，Zhu等[8]通過(guò)研究發(fā)現(xiàn)在線社交網(wǎng)絡(luò)里互惠鏈路比非互惠鏈路在信息擴(kuò)散過(guò)程中起到了更重要的作用，并從網(wǎng)絡(luò)連通性和效率的角度給出了分析.LI等[13]研究了微信用戶網(wǎng)絡(luò)，提出了一種基于平均場(chǎng)方法的演化模型，來(lái)刻畫網(wǎng)絡(luò)鏈路生成和動(dòng)態(tài)傳播機(jī)理.

本文采用鏈路預(yù)測(cè)來(lái)檢驗(yàn)鏈路生成理論的有效性.近年來(lái)，鏈路預(yù)測(cè)已經(jīng)作為復(fù)雜網(wǎng)絡(luò)應(yīng)用的一個(gè)典型問(wèn)題，應(yīng)用于各個(gè)領(lǐng)域的多個(gè)實(shí)際場(chǎng)景中.Liben-Nowellet等[9]首先定義了鏈路預(yù)測(cè)問(wèn)題并提出了一系列基于節(jié)點(diǎn)相似度的方法，他們認(rèn)為未來(lái)鏈接的信息可以只通過(guò)現(xiàn)有的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)來(lái)獲取，節(jié)點(diǎn)相似性指標(biāo)具有較好的效果.Zhou等[10]總結(jié)了復(fù)雜網(wǎng)絡(luò)中的鏈路預(yù)測(cè)算法體系，一些代表性的工作包括基于節(jié)點(diǎn)鄰居的方法，如共同鄰居、Jaccard相似度，Adamic-Adar指標(biāo)等.本文中，為了驗(yàn)證網(wǎng)絡(luò)生成理論，我們假定網(wǎng)絡(luò)中的鏈路生成傾向于以高概率存在的子圖模式進(jìn)行，這樣刻畫鏈路優(yōu)先級(jí)的鏈路生成理論就可以用鏈路預(yù)測(cè)的結(jié)果來(lái)進(jìn)行檢驗(yàn).基于同樣的理論與實(shí)驗(yàn)設(shè)計(jì)，Romero等[11]研究了有向閉合結(jié)構(gòu)，給出了2步路徑類型的形式化定義和網(wǎng)絡(luò)生成方法，并在Twitter數(shù)據(jù)集中進(jìn)行了證實(shí).Schall[12]研究了節(jié)點(diǎn)間的三角模式并在有向網(wǎng)絡(luò)中應(yīng)用于鏈路預(yù)測(cè)，提出了三角相似度指標(biāo)的新算法.Liu等[18]研究了局部結(jié)構(gòu)，提出了局部差異融合算法，優(yōu)化了基于共同鄰居的相似性指標(biāo).Zhang等[2]提出了一種有向網(wǎng)絡(luò)中鏈路生成的模式：位勢(shì)理論，并應(yīng)用于鏈路預(yù)測(cè)獲得了較好的預(yù)測(cè)效果.

3 有向網(wǎng)絡(luò)生成模型

3.1 問(wèn)題與定義

有向網(wǎng)絡(luò)的鏈路數(shù)據(jù)表示為一個(gè)有向圖G=(N，E)，其中N={x1，x2，…，xn}表示節(jié)點(diǎn)集合，E={eij}表示連邊集合.相應(yīng)的，每個(gè)元素eij=1代表一條從節(jié)點(diǎn)xi到節(jié)點(diǎn)xj的有向鏈路.基于有向圖表示的網(wǎng)絡(luò)，有如下概念定義：

定義1.一個(gè)圖G=(N，E)被稱為連通的當(dāng)且僅當(dāng)其不能被表示為兩個(gè)圖的組合，即不存在兩個(gè)圖G1=(N1，E1)和G2=(N2，E2)使得節(jié)點(diǎn)集合N1和N2不相交，其中N=N1∪N2，E=E1∪E2.

圖的連通性表明節(jié)點(diǎn)集合N中的每?jī)蓚€(gè)不同的節(jié)點(diǎn)都通過(guò)至少一個(gè)節(jié)點(diǎn)序列連接在一起.本文研究的網(wǎng)絡(luò)鏈路生成模式基于連通的圖，不考慮非連通有向圖的情況.

定義2.在圖G中一個(gè)節(jié)點(diǎn)xi被稱為支配另一個(gè)節(jié)點(diǎn)xy，則有eij=1且eji=0.

定義3.在圖G中兩個(gè)不同的節(jié)點(diǎn)xi和xy被稱為等價(jià)，則有eij=1且eji=1.

定義4.在圖G中節(jié)點(diǎn)xi支配的所有節(jié)點(diǎn)集合稱為節(jié)點(diǎn)xi的后繼.所有支配節(jié)點(diǎn)xi的節(jié)點(diǎn)集合稱為節(jié)點(diǎn)xi的前趨.

根據(jù)支配狀態(tài)和等價(jià)狀態(tài)，我們能夠區(qū)分有向圖中兩個(gè)節(jié)點(diǎn)的區(qū)別，進(jìn)而可以對(duì)有向圖中一個(gè)路徑序列進(jìn)行描述，為不同的節(jié)點(diǎn)生成刻畫角色的分?jǐn)?shù).相應(yīng)的，在我們的體系中節(jié)點(diǎn)有三種角色，分別定義如下：

定義5.一個(gè)節(jié)點(diǎn)xi∈N被稱為頭節(jié)點(diǎn)，當(dāng)且僅當(dāng)xi支配了至少一個(gè)節(jié)點(diǎn)xj∈N，即eij=1且不被任何一個(gè)節(jié)點(diǎn)支配，即不存在xj∈N，eji=1.

定義6.一個(gè)節(jié)點(diǎn)xi∈N被稱為尾節(jié)點(diǎn)當(dāng)且僅當(dāng)xi被至少一個(gè)節(jié)點(diǎn)xj∈N支配，即eji=1且不支配任何一個(gè)節(jié)點(diǎn)，即不存在xj∈N，eij=1.

定義7.一個(gè)節(jié)點(diǎn)xi∈N被稱為中間節(jié)點(diǎn)，當(dāng)且僅當(dāng)存在xj，xk∈N使得eij=1且eki=1，即節(jié)點(diǎn)xi支配其他節(jié)點(diǎn)且被其他節(jié)點(diǎn)支配.

圖1 三節(jié)點(diǎn)模式的不同角色示意圖Fig.1 Different roles of 3-node patterns

以三個(gè)節(jié)點(diǎn)構(gòu)成的有向網(wǎng)絡(luò)為例說(shuō)明三種角色的定義，如圖1所示，在A，B，C三個(gè)有向網(wǎng)絡(luò)例子中，節(jié)點(diǎn)1始終是頭節(jié)點(diǎn)，節(jié)點(diǎn)3始終是尾節(jié)點(diǎn)，節(jié)點(diǎn)2的角色有變化，在A網(wǎng)絡(luò)中節(jié)點(diǎn)2是中間節(jié)點(diǎn)，在B網(wǎng)絡(luò)中節(jié)點(diǎn)2是頭節(jié)點(diǎn)，在C網(wǎng)絡(luò)中，節(jié)點(diǎn)2是尾節(jié)點(diǎn).

3.2 局部相關(guān)位置方法

根據(jù)以上定義，我們提出一種復(fù)雜網(wǎng)絡(luò)鏈路生成模型的建立方法：局部相關(guān)位置方法.該模型基于如下思路：在有向網(wǎng)絡(luò)中，存在某些特定的典型的模式；相比于其他模式，這些模式有較高概率在網(wǎng)絡(luò)中重現(xiàn).通過(guò)分析不同尺度的局部結(jié)構(gòu)，我們能夠得到一系列局部相關(guān)位置集合，可以用來(lái)度量節(jié)點(diǎn)之間的相似度.我們首先描述成成局部相關(guān)位置集合的通用過(guò)程，然后將模型應(yīng)用于3節(jié)點(diǎn)模式和4節(jié)點(diǎn)模式并通過(guò)鏈路預(yù)測(cè)來(lái)驗(yàn)證方法的有效性.

在有向網(wǎng)絡(luò)中，具有不同功能、能量或者作用的節(jié)點(diǎn)具有不對(duì)等的位置信息，從而導(dǎo)致邊的有向性和不對(duì)稱性，這也是有向網(wǎng)絡(luò)與無(wú)向網(wǎng)絡(luò)的主要區(qū)別之一.我們定義一種特殊的度量(局部相關(guān)位置)來(lái)提取這種因?yàn)榉较蛟斐傻牟粚?duì)等信息，進(jìn)而通過(guò)子圖中所有節(jié)點(diǎn)的位置和所有有向鏈路來(lái)刻畫每個(gè)節(jié)點(diǎn)的特征.令S?N為節(jié)點(diǎn)集N的一個(gè)子集，GS=(S，ES)是有向圖G的一個(gè)子圖，那么對(duì)應(yīng)于子圖GS中一個(gè)節(jié)點(diǎn)xi的局部相關(guān)位置度量為一個(gè)向量lrpi，定義為：

(1)

其中c∈R是一個(gè)由子圖確定的常量.D(xi)是節(jié)點(diǎn)xi的后繼節(jié)點(diǎn)集合，P(xi)是節(jié)點(diǎn)xi的前趨節(jié)點(diǎn)集合.對(duì)于整個(gè)圖來(lái)說(shuō)，以矩陣形式描述為：

MS·lrp=cIS

(2)

其中l(wèi)rp是對(duì)應(yīng)于節(jié)點(diǎn)集合xi∈S的向量，IS是單元向量，MS是參數(shù)矩陣，其構(gòu)成元素確定如下：

Mii=1 對(duì)角線置1

圖2 3節(jié)點(diǎn)模式的有向網(wǎng)絡(luò)鏈路模式Fig.2 Link pattern of 3 nodes directed network

作為一種鏈路生成機(jī)制，我們相信局部相關(guān)位置理論能夠揭示一些底層網(wǎng)絡(luò)演化過(guò)程中隱含的規(guī)律.參考文獻(xiàn)[2]的思路，我們考察了3節(jié)點(diǎn)和4節(jié)點(diǎn)構(gòu)成的所有模式，并設(shè)計(jì)對(duì)應(yīng)的鏈路預(yù)測(cè)方法.如圖2所示，3節(jié)點(diǎn)有向網(wǎng)絡(luò)能夠構(gòu)成的鏈路模式一共有9種，其中下標(biāo)代表連接的方向性，包括接入i，接出o，和雙向m.相比于文獻(xiàn)[2]，我們考慮了雙向鏈路，因此在我們的定義下，鏈路具有更為復(fù)雜的類型.對(duì)每一個(gè)模式，移除其中一個(gè)鏈路，如圖2中虛線所示，可以得到新的子圖，通過(guò)計(jì)算移除前后子圖結(jié)構(gòu)的局部相對(duì)位置度量的變化，可以得到每種模式生成所對(duì)應(yīng)的權(quán)重.具體的，在3節(jié)點(diǎn)模式下，分別計(jì)算該鏈路存在和不存在對(duì)應(yīng)的局部相關(guān)位置方法計(jì)算的節(jié)點(diǎn)位置向量，節(jié)點(diǎn)位置向量的差值即為對(duì)應(yīng)的權(quán)重變化.

如表1所示，為3節(jié)點(diǎn)網(wǎng)絡(luò)中所有9種模式對(duì)應(yīng)的權(quán)重分?jǐn)?shù).

一個(gè)新產(chǎn)生的鏈路對(duì)于網(wǎng)絡(luò)整體的貢獻(xiàn)作用可以通過(guò)局部相關(guān)位置方法來(lái)確定.可以利用某一種類型的模式，如3節(jié)點(diǎn)模式，也可以利用多種類型模式的組合，如3節(jié)點(diǎn)和4節(jié)點(diǎn)模式，來(lái)生成一個(gè)該鏈路用于預(yù)測(cè)的分?jǐn)?shù).當(dāng)前未連接的鏈路預(yù)測(cè)分?jǐn)?shù)定義為這個(gè)鏈路產(chǎn)生后帶來(lái)的分?jǐn)?shù)之和.在3節(jié)點(diǎn)模式定義下的鏈路預(yù)測(cè)分?jǐn)?shù)為：

表1 3節(jié)點(diǎn)模式權(quán)重分?jǐn)?shù)表Table 1 Weights of 3-Node patterns

(3)

其中Slink表示鏈路的預(yù)測(cè)分?jǐn)?shù)，Si表示特定類型模式中不同的權(quán)重分?jǐn)?shù)，如Soo，Tnew是所有新產(chǎn)生的相關(guān)模式的總和.具體的，統(tǒng)計(jì)得到每個(gè)節(jié)點(diǎn)在該鏈路不存在時(shí)對(duì)應(yīng)的9種鏈路模式個(gè)數(shù)，再統(tǒng)計(jì)得到每個(gè)節(jié)點(diǎn)在該鏈路存在時(shí)對(duì)應(yīng)的9中鏈路模式個(gè)數(shù)，差值即為每種模式所對(duì)應(yīng)的權(quán)重總和，用來(lái)刻畫該鏈路存在與否對(duì)全網(wǎng)的影響.

同理，4節(jié)點(diǎn)模式的權(quán)重分?jǐn)?shù)表(如表2所示).

表2 4節(jié)點(diǎn)模式權(quán)重分?jǐn)?shù)表Table 2 Weights of 4-Node patterns

相應(yīng)的，在4節(jié)點(diǎn)模式定義下的鏈路預(yù)測(cè)分?jǐn)?shù)為：

(4)

4 實(shí)驗(yàn)及驗(yàn)證

4.1 評(píng)估方法和實(shí)驗(yàn)數(shù)據(jù)

我們用鏈路預(yù)測(cè)來(lái)檢驗(yàn)所提出的網(wǎng)絡(luò)鏈路生成方法.采用標(biāo)準(zhǔn)的評(píng)估指標(biāo)AUC(Area Under the receiver operating Characteristic)來(lái)表示鏈路預(yù)測(cè)的準(zhǔn)確性[14].在具體計(jì)算過(guò)程中，我們隨機(jī)選擇一個(gè)存在的鏈路，與另一個(gè)隨機(jī)選取的不存在的鏈路比較鏈路預(yù)測(cè)分?jǐn)?shù).在n次獨(dú)立實(shí)驗(yàn)對(duì)比后，得到nad次該鏈路的預(yù)測(cè)分?jǐn)?shù)大于隨機(jī)選取的不存在鏈路，neq次該鏈路的預(yù)測(cè)分?jǐn)?shù)小于隨機(jī)選取的不存在鏈路，那么AUC指標(biāo)定義如下：

(5)

在隨機(jī)方法下AUC指標(biāo)值為0.5，實(shí)驗(yàn)中AUC指標(biāo)值超過(guò)0.5的程度表示了對(duì)應(yīng)的鏈路預(yù)測(cè)算法的有效程度，AUC指標(biāo)值最高為1.我們選取了4種經(jīng)典方法[15]來(lái)與本文提出的方法進(jìn)行對(duì)比實(shí)驗(yàn).選取的算法包括：

1)CN(Common Neighbors)：Scn=|D(xi)∩P(xj)|

4)PA(Preferential Attachment)：SPA=kout(xi)×kin(xj)

其中Γ(xi)=D(xi)∪P(xi)表示節(jié)點(diǎn)xi的鄰居集合，kin(xj)和kout(xi)分別表示節(jié)點(diǎn)xi的入度和出度.

我們選擇了4類有代表性的真實(shí)世界中不同領(lǐng)域的有向網(wǎng)絡(luò)數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù).其中，Wikivote是從英文百科網(wǎng)對(duì)2794次選舉產(chǎn)生的有向網(wǎng)絡(luò)[16];Political Blogs是由美國(guó)政治博客間的網(wǎng)頁(yè)超鏈接構(gòu)成的有向網(wǎng)絡(luò)[17]；Celegans是由一種線蟲的神經(jīng)網(wǎng)絡(luò)構(gòu)成的有向網(wǎng)絡(luò)[19];Sina Weibo是通過(guò)爬取得到的新浪微博數(shù)據(jù)，我們隨機(jī)選擇了1000個(gè)VIP用戶及其之間的關(guān)注關(guān)系構(gòu)成有向網(wǎng)絡(luò).

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

對(duì)于每種個(gè)數(shù)據(jù)集，我們采用3節(jié)點(diǎn)模式和4節(jié)點(diǎn)模式兩種方法，與四種現(xiàn)有算法進(jìn)行AUC指標(biāo)的對(duì)比.鏈路預(yù)測(cè)的實(shí)驗(yàn)結(jié)果如圖3所示.從三個(gè)方面進(jìn)行分析：

圖3 鏈路預(yù)測(cè)AUC指標(biāo)Fig.3 AUC of link prediction methods

1)基于局部相關(guān)位置度量的方法在Wikivote，Political Blogs和SinaWeibo三個(gè)社交網(wǎng)絡(luò)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果優(yōu)于其他最好的方法，3節(jié)點(diǎn)模式AUC指標(biāo)提升7%以上，4節(jié)點(diǎn)模式指標(biāo)提升12%以上.但在Celegans生物網(wǎng)絡(luò)數(shù)據(jù)集的實(shí)驗(yàn)中，本文提出的方法結(jié)果不如CN和AA方法，這說(shuō)明局部相關(guān)位置理論更適用社交網(wǎng)絡(luò)，對(duì)于刻畫生物網(wǎng)絡(luò)底生成機(jī)制不適合.

2)計(jì)算復(fù)雜度方面，傳統(tǒng)方法中CN算法復(fù)雜度為O(n2)，其中n為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù).AA算法復(fù)雜度為O(2n2)，RA算法復(fù)雜度為O(2n2)，PA算法復(fù)雜度為O(2n).對(duì)應(yīng)于本文給出的兩種模式，3節(jié)點(diǎn)模式的計(jì)算需要統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)2跳相通的節(jié)點(diǎn)集合，可得計(jì)算復(fù)雜度為O(9n2)，同理4節(jié)點(diǎn)模式的復(fù)雜度為O(27n3).相比于傳統(tǒng)方法，本文提出的方法在計(jì)算性能方面都具有非監(jiān)督相似性指標(biāo)的計(jì)算復(fù)雜度較低的優(yōu)勢(shì).

3)在所有的4種數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果中，4節(jié)點(diǎn)模式AUC指標(biāo)都優(yōu)于3節(jié)點(diǎn)模式AUC指標(biāo).這說(shuō)明考慮子圖模式類型時(shí)，包含更多的節(jié)點(diǎn)，更多的鏈路，更多的模式會(huì)提升網(wǎng)絡(luò)表達(dá)的效果，進(jìn)而提升鏈路預(yù)測(cè)的AUC指標(biāo).但考慮包含更多節(jié)點(diǎn)的模式會(huì)導(dǎo)致模型復(fù)雜度提升，節(jié)點(diǎn)模式類型過(guò)多增加了計(jì)算量，處理效率會(huì)顯著降低，因此，理解網(wǎng)絡(luò)微觀機(jī)制仍然是一個(gè)具有挑戰(zhàn)性的問(wèn)題.

4)局部相關(guān)位置方法在新浪微博數(shù)據(jù)集SinaWeibo中相比其他方法AUC指標(biāo)提升更為顯著.原因是我們?cè)谠O(shè)計(jì)鏈路生成理論時(shí)時(shí)，采用了一些與微博網(wǎng)絡(luò)機(jī)制一致的假設(shè)，如互惠性，傳遞性(Soo)，共同關(guān)注(Soi)，共同粉絲(Sio)等.局部相關(guān)位置方法整合了以上常見的模式，所以能夠在社交網(wǎng)絡(luò)領(lǐng)域取得更高的預(yù)測(cè)準(zhǔn)確率.

5 總 結(jié)

本文中我們提出一種鏈路生成理論，稱為局部相關(guān)位置方法，在微觀組織機(jī)理刻畫有向復(fù)雜網(wǎng)絡(luò)鏈路生成的模式.結(jié)合現(xiàn)有的鏈路預(yù)測(cè)算法，我們?cè)O(shè)計(jì)了兩種鏈路預(yù)測(cè)指標(biāo)，分別基于3節(jié)點(diǎn)模式和4節(jié)點(diǎn)模式.在4種真實(shí)世界的有向網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)證明了局部相關(guān)位置方法在新生成鏈路預(yù)測(cè)方面的有效性.作為一種底層網(wǎng)絡(luò)生成機(jī)制的理論，局部相關(guān)位置方法可以擴(kuò)展應(yīng)用到社交網(wǎng)絡(luò)分析，朋友推薦，社區(qū)發(fā)現(xiàn)等多種應(yīng)用場(chǎng)景.發(fā)現(xiàn)有向網(wǎng)絡(luò)生成的影響因素，總結(jié)鏈路生成模式是一個(gè)具有挑戰(zhàn)性的研究問(wèn)題，在未來(lái)的研究中，我們將擴(kuò)展所分析的子圖的規(guī)模，并結(jié)合應(yīng)用領(lǐng)域的特點(diǎn)，在更復(fù)雜的假設(shè)下提出新的鏈路生成理論.