基于網(wǎng)絡(luò)嵌入的稀疏子圖發(fā)現(xiàn)算法

孫鶴立，何 亮，何 方，孫苗苗，賈曉琳*

（1.西安交通大學(xué)計算機科學(xué)與技術(shù)學(xué)院，西安 710049；2.西安交通大學(xué)新聞與新媒體學(xué)院，西安 710049）

（*通信作者電子郵箱xlinjia@mail.xjtu.edu.cn）

0 引言

隨著在線社交網(wǎng)絡(luò)（如新浪微博、微信）的廣泛流行，社團發(fā)現(xiàn)問題由于其廣泛的應(yīng)用得到了長足的發(fā)展。然而現(xiàn)有的多數(shù)工作大多關(guān)注于網(wǎng)絡(luò)中的稠密子圖發(fā)現(xiàn)問題，很少有關(guān)于稀疏子圖（tenuous subgraph）的研究。所謂稀疏子圖，是指由具有較少的連接或者弱連接的節(jié)點組成的子圖結(jié)構(gòu)。

稀疏子圖在實際生活中有許多的應(yīng)用場景。例如，在科研論文的審稿時，組織者需要為論文分派審稿人。除了需要審稿人的研究領(lǐng)域與論文內(nèi)容相關(guān)之外，也需要避免審稿人與論文作者、審稿人之間互相認識，從而避免審稿時可能出現(xiàn)的學(xué)術(shù)不端現(xiàn)象，保證審稿過程的公平公正。當前多數(shù)審稿系統(tǒng)都使用了論文作者合作關(guān)系、工作單位、國籍等信息來避免研究領(lǐng)域的偏差，但是很少考慮到論文作者與審稿人之間的社交關(guān)系的稀疏性。弱社交網(wǎng)絡(luò)中的好友推薦問題、患者治療小組組建問題［1］同樣與稀疏子圖有關(guān)?？梢?，稀疏子圖在現(xiàn)實生活中具有較為廣泛的應(yīng)用前景。

患者治療小組組建：在精神康復(fù)治療領(lǐng)域，針對某些疾病，如酗酒、藥物依賴等，在對患者進行治療時，通常是將有針對性的治療和小組內(nèi)患者之間的互助相結(jié)合的。這個治療小組成員的選擇不是隨意的，而是需要滿足一定的條件：盡可能保證治療小組中的成員互不認識且沒有共同的朋友，這樣可以將治療小組中共享的私人信息被傳播的可能性降到最低，從而避免他們因為害怕熟識的朋友知道自己的秘密而不吐露自己內(nèi)心的真實想法；且治療小組的規(guī)模不宜過小，這樣可以確保小組里的每個成員都能得到他人的充分的幫助。

評審專家選擇：在審閱學(xué)術(shù)論文或項目立項評審時，均需指派專家。除了保證這些專家的研究方向與所評閱論文或項目的研究內(nèi)容一致，還要盡可能避免審稿人和論文作者/項目申請人認識及審稿人之間互相認識，以確保評審過程的公平公正。

最近，稀疏子圖開始引起了一些研究者的興趣，研究者提出了一些用于稀疏子圖發(fā)現(xiàn)的方法［2-4］，這些方法均基于圖結(jié)構(gòu)給出了稀疏子圖的定義，并進行了相關(guān)研究。與之前的方法不同，本文提出一種基于網(wǎng)絡(luò)嵌入的稀疏子圖發(fā)現(xiàn)（Tenuous subGraph Finding，TGF）方法，將圖結(jié)構(gòu)轉(zhuǎn)化為向量表示，進而在歐氏空間中進行稀疏子圖的發(fā)現(xiàn)。通過這種方法能夠更高效地進行稀疏子圖的發(fā)現(xiàn)，并且可以很好地結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)和屬性信息。

1 相關(guān)研究

1.1 稀疏子圖發(fā)現(xiàn)

稀疏子圖相關(guān)的研究從2017 年才開始逐漸出現(xiàn)。Shen等［2］提出的MkTG（Minimumk-Triangle disconnected Group）問題是首個關(guān)于稀疏子圖發(fā)現(xiàn)問題的研究。MkTG 問題使用子圖中k-triangle 的個數(shù)來衡量子圖的稀疏性。k-triangle 定義為子圖中的一個三元組，其中任意兩個節(jié)點之間的最短路徑均小于k。MkTG 問題即為找到圖中最大的一個節(jié)點集合，使得其中的k-triangle 的數(shù)量盡可能地少，并且節(jié)點數(shù)量盡可能地多。盡管該方法可以找到稀疏子圖，但是k-triangle 在某些情況下不是一個很好的評估稀疏性的指標。另一方面，由于需要計算每個節(jié)點參與的k-triangle 的數(shù)量，導(dǎo)致該方法的時間復(fù)雜度較高，較難應(yīng)用于大規(guī)模網(wǎng)絡(luò)上的稀疏子圖發(fā)現(xiàn)。在MkTG 問題的基礎(chǔ)上，Li 等［4］提出KLM（K-Line-Minimized）用于稀疏子圖發(fā)現(xiàn)。KLM 使用k-line衡量子圖的稀疏性。k-line定義為圖中最短路徑小于k的一個節(jié)點對。KLM 問題嘗試找到一個節(jié)點集合，使得其中k-line 的數(shù)量盡可能地少，同時節(jié)點的數(shù)量盡可能地多。

與前面兩個工作不同，Hsu 等［3］提出了 UTNA（Unfamiliarity-aware-Therapy group selection with Noah’s Ark principle）問題，利用稀疏子圖發(fā)現(xiàn)解決群體治療問題。群體治療是針對心理疾病進行治療的主要臨床手段之一，然而治療小組的組建是相當有挑戰(zhàn)性的。UTNA 旨在自動化地找出合理的治療群體成員。UTNA 問題即找到一個最大的子圖，使得其中連邊的數(shù)目盡可能地少，且節(jié)點滿足諾亞方舟準則（Noah’s Ark Principle）。

以上幾種方法均是基于圖結(jié)構(gòu)尋找稀疏子圖，并且均提出各自不同的關(guān)于稀疏子圖的定義，然后基于這些定義設(shè)計了解決算法。然而，由于圖結(jié)構(gòu)的復(fù)雜性，這些關(guān)于稀疏子圖的求解問題都是NP 難的，只能通過貪婪算法找到近似解，并且時間復(fù)雜度通常較高。隨著網(wǎng)絡(luò)嵌入方法在網(wǎng)絡(luò)分析領(lǐng)域的流行，本文考慮使用基于網(wǎng)絡(luò)嵌入的方法來尋找稀疏子圖。

1.2 網(wǎng)絡(luò)嵌入

網(wǎng)絡(luò)嵌入（network embedding）［5-7］又稱為網(wǎng)絡(luò)表示學(xué)習(xí)（network representation learning），旨在將網(wǎng)絡(luò)中的每個節(jié)點表示為低維向量，使原網(wǎng)絡(luò)的拓撲結(jié)構(gòu)信息被高效地保存于學(xué)習(xí)到的向量中。傳統(tǒng)的網(wǎng)絡(luò)一般用稀疏的鄰接矩陣或拉普拉斯矩陣保存網(wǎng)絡(luò)結(jié)構(gòu)特征信息，在網(wǎng)絡(luò)規(guī)模很大的情況下，這種表示會帶來維災(zāi)難。網(wǎng)絡(luò)嵌入將鄰接矩陣映射成低維向量，很好地解決了維災(zāi)難問題。

近年來，隨著深度學(xué)習(xí)的發(fā)展，越來越多的研究者開始采用深度學(xué)習(xí)中的技術(shù)解決網(wǎng)絡(luò)嵌入問題。DeepWalk算法［8］對網(wǎng)絡(luò)進行固定長度的隨機游走，得到節(jié)點序列，然后使用Skip-Gram 模型對這些節(jié)點序列進行學(xué)習(xí)，從而得到節(jié)點向量表示。Node2Vec方法［9］基于DeepWalk 方法，對隨機游走過程進行了改進，設(shè)計了一種有偏的隨機游走方法，在深度優(yōu)先搜索和廣度優(yōu)先搜索之間進行權(quán)衡。LINE（Large-scale Network Embedding）算法［10］則嘗試在網(wǎng)絡(luò)嵌入時保留網(wǎng)絡(luò)中的一階親密性和二階親密性，通過最小化鄰接矩陣和表示向量的KL（Kullback-Leibler）散度，可以在線性時間內(nèi)高效地學(xué)習(xí)到節(jié)點向量表示。TADW（Text-Associated DeepWalk）算法［11］是一種針對文本屬性網(wǎng)絡(luò)的網(wǎng)絡(luò)嵌入方法，在DeeWalk 的基礎(chǔ)之上，加入了文本特征的學(xué)習(xí)，使用非負矩陣分解方法來進行優(yōu)化。一些基于自編碼器［12-14］的網(wǎng)絡(luò)嵌入方法同樣也能很好地學(xué)習(xí)到網(wǎng)絡(luò)結(jié)構(gòu)信息，如SDNE（Structural Deep Network Embedding）算法［12］、DNGR（Deep Neural Networks for Graph Representations）算法［13］等。

2 基于網(wǎng)絡(luò)嵌入的稀疏子圖發(fā)現(xiàn)算法

TGF 算法主要分為兩個步驟：節(jié)點網(wǎng)絡(luò)嵌入學(xué)習(xí)和稀疏子集發(fā)現(xiàn)。其中：節(jié)點網(wǎng)絡(luò)嵌入負責對網(wǎng)絡(luò)進行特征學(xué)習(xí)，在盡可能保持網(wǎng)絡(luò)信息的情況下，將每個節(jié)點映射成低維空間中的表示向量；稀疏子集發(fā)現(xiàn)通過對學(xué)習(xí)到的節(jié)點表示向量進行學(xué)習(xí)，找到其中的稀疏子結(jié)構(gòu)。

2.1 節(jié)點網(wǎng)絡(luò)嵌入學(xué)習(xí)

本文主要基于Node2Vec 方法的思想進行網(wǎng)絡(luò)嵌入。Node2vec是對DeepWalk 算法的改進，借鑒了自然語言處理中的詞嵌入方法［15］。通過在網(wǎng)絡(luò)中進行隨機游走，得到節(jié)點序列，然后再使用skip-gram 方法即可學(xué)習(xí)到每個節(jié)點的表示向量。它的隨機游走方法是深度優(yōu)先遍歷和廣度優(yōu)先遍歷的一種權(quán)衡，通過設(shè)置參數(shù)控制游走在鄰域停留或者往遠處擴散。Node2vec 方法首先對網(wǎng)絡(luò)中的鄰域信息進行學(xué)習(xí)，然后對鄰域信息保持目標函數(shù)進行優(yōu)化完成節(jié)點表示向量的學(xué)習(xí)過程。這個目標函數(shù)是靈活的，而且有偏的隨機游走方法使得該算法可以采樣到不同類型的鄰居結(jié)構(gòu)。

Node2vec方法的優(yōu)勢在于它可以靈活控制隨機游走的方式，很好地使原圖中的結(jié)構(gòu)信息得以保留。在原圖中距離較遠的兩個節(jié)點，在低維向量表示空間中，它們的相對位置也會較遠。Node2vec 綜合考慮節(jié)點的DFS（Depth First Search）鄰域和BFS（Bread First Search）鄰域通過對深度優(yōu)先遍歷和廣度優(yōu)先遍歷進行權(quán)衡，既能學(xué)習(xí)到局部的鄰域結(jié)構(gòu)信息，又能避免游走過遠導(dǎo)致較遠的兩個節(jié)點形成相似的表示向量，充分考慮節(jié)點的“同質(zhì)性”和“同構(gòu)性”?！巴|(zhì)性”表示距離相近節(jié)點的嵌入向量應(yīng)該盡量接近，“同構(gòu)性”表示結(jié)構(gòu)上相似的節(jié)點的嵌入向量應(yīng)該盡量接近。

如圖1所示，節(jié)點u和s1、s2、s3、s4之間聯(lián)系非常緊密，它們組成了一個社區(qū)，應(yīng)該具有相似的向量表示。同樣地，節(jié)點v和s5、s6、s7、s8也應(yīng)該具有相似的向量表示，它們也組成了一個社區(qū)?？梢钥闯鰑和v分別是這兩個社區(qū)的中心節(jié)點，它們在社區(qū)中扮演同樣的角色，因此也應(yīng)該具有相似的向量表示。Node2vec算法可以充分捕捉節(jié)點間的“同構(gòu)性”。

圖1 網(wǎng)絡(luò)結(jié)構(gòu)示意圖Fig.1 Schematic diagram of network structure

2.2 稀疏子集發(fā)現(xiàn)

稀疏子集是由稀疏子圖中的節(jié)點組成的集合，為了便于后續(xù)形式化描述，這里將稀疏子圖問題轉(zhuǎn)化為稀疏子集發(fā)現(xiàn)。在得到網(wǎng)絡(luò)的節(jié)點表示向量之后，將稀疏子圖發(fā)現(xiàn)問題從圖結(jié)構(gòu)中轉(zhuǎn)移到了低維向量空間中。由于向量空間與圖結(jié)構(gòu)完全不同，原先在圖結(jié)構(gòu)上定義的k-line、k-triangle 等均無法使用，因此為了在向量空間中完成稀疏子集發(fā)現(xiàn)，需要重新定義向量空間中的稀疏子集發(fā)現(xiàn)問題。以下討論中本文假設(shè)網(wǎng)絡(luò)嵌入方法學(xué)習(xí)到的節(jié)點表示向量的維度為h。

首先需要考慮的是低維向量空間中稀疏性的度量方法。給定一個向量集合時，如何去評價它是否稀疏。本文可以通過計算樣本之間的距離來判斷兩個點相距較近還是較遠。對于一個向量集合，可以計算所有向量之間的距離，如果它們之間的距離都比較遠，那么可以認為這個向量集合比較稀疏。為了衡量向量集合的稀疏性，本文引入ε對的定義：

定義1ε對，ε-pair。給定兩個樣本點的向量表示x1、x2，如果它們滿足dis(x1，x2)＜ε，將其稱為一個ε對。有了ε對的定義之后，就可以衡量給定的向量集合的稀疏性。假設(shè)集合T中的ε對的數(shù)量為r，r越小，說明集合T越稀疏。

這里的樣本距離度量方式可以有多種，比如余弦距離、歐氏距離等。本文選用的距離度量為歐氏距離，即

下面給出向量空間中稀疏子集發(fā)現(xiàn)問題的定義：

定義2稀疏子集發(fā)現(xiàn)（tenuous subset finding）問題。給定歐氏空間Rh的散點集合，給定距離參數(shù)ε，從集合D中找到一個子集，使得T滿足以下條件：

a）?xi∈T，xj∈T，dis(xi，xj)＞ε；

b）??xm∈{xi|xi∈D，xi?T}。

其中：|T|表示集合中節(jié)點的個數(shù)；dis(xi，xj)為點xi與xj之間的距離。約束條件a）表明稀疏子集T中的任意兩個節(jié)點間的距離需大于ε，即對的數(shù)量為0，這表明T中的所有節(jié)點間的距離都比較遠，從而可以表明T比較稀疏；約束條件b）則表明稀疏子集中的樣本數(shù)目應(yīng)盡可能多。

為了解決定義2 中的稀疏子集發(fā)現(xiàn)問題，本文提出了一種基于局部密度擴張的貪婪算法TGF。TGF 算法的思路為：計算所有節(jié)點的鄰居節(jié)點及鄰居數(shù)目，首先選取鄰居數(shù)目最少的節(jié)點u加到稀疏子集中，對于剩下的候選節(jié)點，在滿足dis(u，xi)＞ε的條件下優(yōu)先將鄰居數(shù)目最少的節(jié)點加入到稀疏子集中。該算法在向稀疏子集中添加節(jié)點時總是選取當前狀態(tài)下的最優(yōu)節(jié)點，整體來講是一種貪婪算法。

首先提出ε鄰居的概念，定義如下：

定義3ε鄰居（epsilon neighborhood）。對于點xi∈D，給定距離參數(shù)ε，則點xi的ε鄰居Nε(xi)定義為：

Nε(xi)={xi∈D|dis(xi，xj)≤ε}

這個集合的樣本個數(shù)記為|Nε(xi)|。可見，ε鄰居定義為與給定樣本點的距離小于ε的所有節(jié)點集合。對于給定樣本點xi，其ε鄰居中的樣本數(shù)量|Nε(xi)|越少，說明該樣本周圍的密度較小，則該節(jié)點越有可能被加入到稀疏子集中；反之，樣本點xi的ε鄰居中的樣本數(shù)量|Nε(xi)|越大，說明該樣本周圍的密度較大，則該節(jié)點應(yīng)盡可能避免被加入到稀疏子集中。

為了確保找到的稀疏子集中不存在ε對，在選取樣本點加入到稀疏子集時，應(yīng)該從候選集合中去掉該樣本ε鄰居中的所有樣本點。為了避免過多的樣本被刪除，應(yīng)盡量選擇密度較小的樣本點加入到稀疏子集中。在刪除樣本點時，其鄰域內(nèi)所有樣本點的ε鄰居都需要進行更新。

TGF算法的偽代碼如算法1所示。

其中：第1）～2）行定義了相關(guān)變量；第3）～5）行是預(yù)處理階段，負責計算出所有樣本的ε鄰居Nε(xi)以及ε鄰居數(shù)量|Nε(xi)|；第6）～18）行是算法的主體部分，負責尋找稀疏子集并且刪除不在稀疏子集中的樣本點，其中第8）行將樣本xt加入到稀疏子集中；第9）～14）行刪除xt的ε鄰居中的所有樣本點，15）～18）行從候選集中刪除樣本點xt。

圖2 為算法在二維空間上的稀疏子集發(fā)現(xiàn)過程。其中圖2（a）表示初始化階段，計算出每個樣本的ε鄰居和ε鄰居數(shù)量，每個樣本點旁邊標示的數(shù)字即為樣本的ε鄰居的數(shù)量。圖2（b）為TGF 算法最終找到的稀疏子集，所有的樣本點的ε鄰域數(shù)量都為0，可見所有的樣本點的ε鄰域內(nèi)均沒有其他樣本點。

圖2 稀疏子集發(fā)現(xiàn)過程Fig.2 Process of tenuous subset finding

2.3 時間復(fù)雜度分析

對于網(wǎng)絡(luò)嵌入階段，本文采用的是基于Node2vec 的網(wǎng)絡(luò)嵌入方法，Node2vec 方法主要分為隨機游走和skip-gram 的訓(xùn)練兩個步驟。隨機游走的時間復(fù)雜度為O(N)，skip-gram 的時間復(fù)雜度為O(logN)。對于ε鄰居的計算過程，采用kd-tree數(shù)據(jù)索引結(jié)構(gòu)，時間復(fù)雜度為O(NlogN)。對于稀疏子集發(fā)現(xiàn)的計算過程，每次添加樣本點到稀疏子集中時，需要在未訪問的樣本中查找鄰居數(shù)目最少的樣本，采用線性查找的方法，時間復(fù)雜度為O(N)。刪除給定樣本的ε鄰居中的樣本這一步驟的時間復(fù)雜度為O(ρ2)，其中ρ表示平均每個樣本的ε鄰居個數(shù)。綜上，稀疏子集發(fā)現(xiàn)過程總的時間復(fù)雜度為O(l(N+ρ2))，其中l(wèi)表示集合D中的稀疏子集的個數(shù)，通常l≤N，可以近似認為尋找稀疏子集算法的時間復(fù)雜度接近線性時間復(fù)雜度，即O(N)。

綜合以上分析，TGF 的算法時間復(fù)雜度為O(N+logN+NlogN+l(N+ρ2))，整理后即為O(NlogN+l(N+ρ2))。

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

為了評估TGF 算法的準確率和有效性，在多個人工合成網(wǎng)絡(luò)和真實網(wǎng)絡(luò)數(shù)據(jù)集上進行實驗，并和已有的算法進行對比。本次實驗的電腦環(huán)境為Interl Core i5-4590 CPU @3.2 GHz 型號CPU 和8 GB 內(nèi)存，操作系統(tǒng)為Ubuntu 16.04，TGF算法采用Python語言實現(xiàn)。

3.1 實驗數(shù)據(jù)集

本實驗中采用的數(shù)據(jù)集分為人工合成網(wǎng)絡(luò)數(shù)據(jù)集和真實網(wǎng)絡(luò)數(shù)據(jù)集。數(shù)據(jù)集的所有相關(guān)信息總結(jié)在表1中。

表1 數(shù)據(jù)集信息Tab.1 Dataset information

Polbooks 政治書籍網(wǎng)絡(luò)：政治書籍網(wǎng)絡(luò)是由亞馬遜銷售的政治書籍構(gòu)成的網(wǎng)絡(luò)，其中節(jié)點表示由亞馬遜賣出的書籍，邊則表示兩本書經(jīng)常被同時購買。每本書上都存在一個標簽，表明該書籍的政治傾向性，分別為“自由”（liberal）、“中立”（neutral）和“保守”（conservative）。

Football 橄欖球聯(lián)賽網(wǎng)絡(luò)：Football 美國大學(xué)橄欖球聯(lián)賽網(wǎng)絡(luò)是由美國大學(xué)的橄欖球比賽情況構(gòu)成的一個網(wǎng)絡(luò)，其中的節(jié)點表示球隊，邊表示兩個球隊之間曾經(jīng)打過比賽。該網(wǎng)絡(luò)中一共有115 個節(jié)點和613 條邊。網(wǎng)絡(luò)中的所有球隊被劃分成了11個聯(lián)盟和5支獨立隊伍。

Email_eu 研究機構(gòu)郵件網(wǎng)絡(luò)：Email_eu 是由歐洲某研究結(jié)構(gòu)的郵件往來信息組成的網(wǎng)絡(luò)。其中節(jié)點表示一個研究人員，邊表示兩個研究人員之間有過郵件往來。這些研究人員分屬42個不同的科研機構(gòu)。

表1 中的以Synthetic 開頭的數(shù)據(jù)集表明它是一個人工合成數(shù)據(jù)集。人工合成數(shù)據(jù)集由Lancichinetti 等［16］開發(fā)的LFR benchmark 工具生成，在生成網(wǎng)絡(luò)時可以指定網(wǎng)絡(luò)的節(jié)點數(shù)目、平均度、混亂程度等。

3.2 對比算法和評估指標

為了評估TGF 算法的性能，本節(jié)選取兩個已有的稀疏子圖發(fā)現(xiàn)算法WK（Weight ofK-hop）和TERA（Triangle and Edge Reduction Algorithm）來進行對比。

在對實驗結(jié)果進行衡量時，本文采了k-line、k-triangle 以及k-density 作為評價指標。關(guān)于k-triangle 和k-line 的定義詳見1.1節(jié)。k-density的定義如下：

3.3 整體結(jié)果分析

本節(jié)主要分析各個算法在數(shù)據(jù)集上的整體表現(xiàn)。為了公平起見，設(shè)定在所有數(shù)據(jù)集上找到的稀疏子圖規(guī)模是一致的，并且設(shè)定找到的稀疏子圖的規(guī)模為原圖規(guī)模的1/10。針對ε優(yōu)化，使得TGF算法能找到指定大小的稀疏子圖，且該稀疏子圖中的1-line、1-triangle 以及1-density 值都較小。由于TGF 的時間復(fù)雜度非常低，所有要找到合適的ε并不困難。對于WK算法和TERA，為了找到指定規(guī)模大小的稀疏子圖，需要多次嘗試選擇不同的k值。

表2 是WK、TERA、TGF 三個算法在人工合成數(shù)據(jù)集上的結(jié)果。其中：1-line 表示子圖中邊的數(shù)量；1-triangle 表示子圖中直接相連的三個節(jié)點組成的三角形的數(shù)量；1-density 表示對應(yīng)的子圖密度；2-line 表示子圖中最短路徑長度不大于2 的節(jié)點對的數(shù)量；2-triangle 表示子圖中三個節(jié)點組成的兩兩之間距離不大于2的三元組的數(shù)量；2-density表示對應(yīng)的子圖密度。從表2 中可以看到本文提出的TGF 算法在所有數(shù)據(jù)集上的1-line、1-triangle 和1-density 值都是最小的，找到的所有的稀疏子圖中都不存在直接連邊和三角形結(jié)構(gòu)；然而TGF 算法在其他幾個數(shù)據(jù)集上的2-line、2-triangle 和2-density 值較大，產(chǎn)生這種結(jié)果的原因可能是WK 和TERA 的直接目標就是最小化稀疏子圖中的k-line數(shù)量和k-triangle的數(shù)量，而本文提出的TGF 算法并沒有直接針對2-line 或2-triangle 進行優(yōu)化。不過TGF 與這些方法得到的結(jié)果差距都非常小，也能在一定程度上表明TGF算法具有良好的性能。

表2 各算法在人工合成數(shù)據(jù)集上的結(jié)果Tab.2 Results of different algorithms on synthetic datasets

表3展示的是三個算法在Polbooks、Football和Emai_eu三個真實數(shù)據(jù)集上的結(jié)果。從這兩個表上可以看出TGF算法在這三個數(shù)據(jù)集上的1-line、1-triangle 和1-density 值都是最小的。TGF 在Polblooks 數(shù)據(jù)集上得到的2-triangle 值也是最小的。

表3 各個算法在真實數(shù)據(jù)集上的結(jié)果Tab.3 Results of different algorithms on real datasets

綜合以上分析，可以看出TGF 算法通過網(wǎng)絡(luò)嵌入方法將網(wǎng)絡(luò)結(jié)構(gòu)映射到低維向量空間中，然后采用基于密度的稀疏子圖發(fā)現(xiàn)方法來間接地完成稀疏子圖發(fā)現(xiàn)的方法是可行的。該算法在所有的數(shù)據(jù)集上都展示出了優(yōu)秀的性能，尤其在1-line、1-triangle 和1-density 三個指標上的值都小于WK 和TERA 兩個對比算法。由于WK 和TERA 兩個算法是直接對2-line、2-trangle和2-density這三個指標做優(yōu)化的，所以這兩個算法在這三個指標上的值相對較小，但是TGF 算法在這些指標上的值與WK 和TERA 的差距非常小，說明TGF 算法具有良好的性能。

3.4 參數(shù)敏感性分析

本文提出的TGF引入?yún)?shù)ε來度量向量之間的距離，ε對結(jié)果有較大的影響。為了分析TGF 算法的參數(shù)ε對性能的影響，本文在兩個人工合成數(shù)據(jù)集上進行了實驗，分析隨著參數(shù)ε從小到大的變化，對應(yīng)找到的稀疏子圖中各項指標的變化情況。圖3 展示了TGF 算法在Synthetic_800 和Synthetic_2000、Synthetic_300000 三個數(shù)據(jù)集上的參數(shù)敏感性分析情況。

圖3 TGF算法在三個數(shù)據(jù)集上的參數(shù)敏感性情況Fig.3 Parameter sensitivity of TGF algorithm on three datasets

圖3 中：縱坐標表示算法得到的1-line、1-triangle 個數(shù)和找到的稀疏子圖節(jié)點數(shù)，即n_tenuous。從圖3中可以看出，隨著參數(shù)距離ε的增大，得到的1-line，1-triangle 個數(shù)均開始逐漸減小，并且呈現(xiàn)出快速下降的趨勢。這說明TGF 對參數(shù)ε較為敏感，如果ε過小，TGF 可能返回整個數(shù)據(jù)集作為稀疏子圖結(jié)果集。而隨著ε的增大，由于TGF會刪除選定點的ε鄰域內(nèi)的所有節(jié)點，所以n_tenuous 的個數(shù)開始快速降低。從Synthetic_800 數(shù)據(jù)集上得到的結(jié)果可以看出：1）當ε＜2.2 時，TGF 會返回整個數(shù)據(jù)集作為稀疏子圖結(jié)果集；2）當ε在2.5～3.0 時，得到的1-line、1-triangle 和n_tenuous 個數(shù)開始快速下降；3）當ε=3.0時，是一個拐點，在ε＞3.0以后，得到的1-line、1-triangle 和n_tenuous 個數(shù)下降速度開始減慢；4）當ε＞4.0時，1-line、1-triangle 和n_tenuous 個數(shù)都變成了0。在Synthetic_2000 和Synthetic_300000 數(shù)據(jù)集上呈現(xiàn)出了類似的結(jié)果，當ε在2.5～3.0 時，算法得到的1-line，1-triangle 和n_tenuous 個數(shù)呈現(xiàn)出快速下降趨勢；在ε＞4.5 之后，1-line、1-triangle和n_tenuous個數(shù)都歸為0。

綜上可知，ε參數(shù)對得到的稀疏子圖的影響較大，選擇合適的ε能得到較好的結(jié)果（稀疏子圖規(guī)模較大且子圖較稀疏），而如果ε選得過小或者過大則有可能導(dǎo)致返回整個數(shù)據(jù)集作為稀疏子圖結(jié)果集或者稀疏子圖結(jié)果集為空。在多個實驗數(shù)據(jù)集上的結(jié)果表明，ε選擇在區(qū)間1.5～4.5 時，TGF 算法能取得較好的效果。

3.5 實例分析

為了更好地展現(xiàn)出TGF 算法尋找稀疏子圖的效果，本節(jié)選取Polbooks 數(shù)據(jù)集進行實例分析，展示TGF 算法在該數(shù)據(jù)集上的稀疏子圖發(fā)現(xiàn)結(jié)果。

圖4 是TGF 算法在Polbooks 網(wǎng)絡(luò)上找到的稀疏子圖的示意圖。其中較大的節(jié)點表示通過TGF 算法找到的10 個節(jié)點，它們共同組成了一個稀疏子圖，可以看到這個稀疏子圖中的節(jié)點均勻地分布在整個網(wǎng)絡(luò)中。在該稀疏子圖結(jié)構(gòu)中，任意兩個節(jié)點之間都不存在連邊。由此可見，TGF 算法在真實網(wǎng)絡(luò)上的效果很好，能夠有效地找到網(wǎng)絡(luò)中的稀疏子圖結(jié)構(gòu)，并且有足夠的稀疏性。當然，由于這里的ε參數(shù)取值為0.8，此時只找到了10 個節(jié)點。如果將ε參數(shù)取得更小，那么TGF 能找到規(guī)模更大的稀疏子圖；反之，將ε參數(shù)取得更大，那么找到的稀疏子圖規(guī)模就會更小。參數(shù)ε的選擇可以根據(jù)實際需要找到的稀疏子圖規(guī)模來決定。

圖4 Polbooks網(wǎng)絡(luò)上找到的稀疏子圖Fig.4 Tenuous subgraph found in Polbooks network

3.6 時間性能分析

本節(jié)主要比較TGF算法和其他對比算法的時間效率和可擴展性。表4 為WK、TERA 和TGF 算法在多個人工合成網(wǎng)絡(luò)數(shù)據(jù)集上的運行時間對比。這里分別采用了三個人工合成數(shù)據(jù)集。為了公平的進行比較，本文在對比WK、TERA 和TGF三個算法的運行時間時，設(shè)定在所有數(shù)據(jù)集上找到的稀疏子圖規(guī)模是一致的。

表4 各個算法在不同數(shù)據(jù)集上的運行時間 單位：sTab.4 Running time of different algorithms on different datasets unit：s

從表4 可以看出，相較于其他兩個算法，TGF 算法的時間效率是最高的，且隨著網(wǎng)絡(luò)規(guī)模的增大，TGF的優(yōu)勢變得更為明顯。TGF算法的運行時間較低的原因有兩個方面：一方面，TGF 通過網(wǎng)絡(luò)嵌入方法將圖結(jié)構(gòu)映射到低維向量空間中，在向量空間中的距離計算相對于圖中的最短路徑計算復(fù)雜度大降低；另一方面，TGF 采用了哈希表存儲所有節(jié)點的ε鄰居信息，因此查詢和刪除樣本的速度很快，得到稀疏子圖的時間幾乎是線性的。

4 結(jié)語

本文提出了基于網(wǎng)絡(luò)嵌入的稀疏子圖發(fā)現(xiàn)方法，將網(wǎng)絡(luò)結(jié)構(gòu)映射到低維空間中。在Synthetic_100、Synthetic_1000、Synthetic_300000 三個人工生成數(shù)據(jù)集上的時間性能分析表明，TGF 算法展示出較好的效果，在Synthetic_1000 數(shù)據(jù)集上與TERA 和WK 算法相比，TGF 算法的搜索效率是TERA 的1 353 倍，是WK 算法的4 倍。同時通過在真實數(shù)據(jù)集和人工生成數(shù)據(jù)集上的實驗結(jié)果表明，本文方法在1-line、1-triangle、1-density 指標上的結(jié)果也較優(yōu)。本文沒有考慮屬性圖上的稀疏子圖發(fā)現(xiàn)問題，網(wǎng)絡(luò)中節(jié)點的屬性信息也是非常重要的，比如性別屬性、年齡屬性、背景屬性等信息，后續(xù)會結(jié)合節(jié)點屬性展開相關(guān)研究。