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

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

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

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

0 引言

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

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

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

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

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

1 相關(guān)研究

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

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

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

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

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

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

近年來(lái)，隨著深度學(xué)習(xí)的發(fā)展，越來(lái)越多的研究者開(kāi)始采用深度學(xué)習(xí)中的技術(shù)解決網(wǎng)絡(luò)嵌入問(wèn)題。DeepWalk算法［8］對(duì)網(wǎng)絡(luò)進(jìn)行固定長(zhǎng)度的隨機(jī)游走，得到節(jié)點(diǎn)序列，然后使用Skip-Gram 模型對(duì)這些節(jié)點(diǎn)序列進(jìn)行學(xué)習(xí)，從而得到節(jié)點(diǎn)向量表示。Node2Vec方法［9］基于DeepWalk 方法，對(duì)隨機(jī)游走過(guò)程進(jìn)行了改進(jìn)，設(shè)計(jì)了一種有偏的隨機(jī)游走方法，在深度優(yōu)先搜索和廣度優(yōu)先搜索之間進(jìn)行權(quán)衡。LINE（Large-scale Network Embedding）算法［10］則嘗試在網(wǎng)絡(luò)嵌入時(shí)保留網(wǎng)絡(luò)中的一階親密性和二階親密性，通過(guò)最小化鄰接矩陣和表示向量的KL（Kullback-Leibler）散度，可以在線性時(shí)間內(nèi)高效地學(xué)習(xí)到節(jié)點(diǎn)向量表示。TADW（Text-Associated DeepWalk）算法［11］是一種針對(duì)文本屬性網(wǎng)絡(luò)的網(wǎng)絡(luò)嵌入方法，在DeeWalk 的基礎(chǔ)之上，加入了文本特征的學(xué)習(xí)，使用非負(fù)矩陣分解方法來(lái)進(jìn)行優(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 算法主要分為兩個(gè)步驟：節(jié)點(diǎn)網(wǎng)絡(luò)嵌入學(xué)習(xí)和稀疏子集發(fā)現(xiàn)。其中：節(jié)點(diǎn)網(wǎng)絡(luò)嵌入負(fù)責(zé)對(duì)網(wǎng)絡(luò)進(jìn)行特征學(xué)習(xí)，在盡可能保持網(wǎng)絡(luò)信息的情況下，將每個(gè)節(jié)點(diǎn)映射成低維空間中的表示向量；稀疏子集發(fā)現(xiàn)通過(guò)對(duì)學(xué)習(xí)到的節(jié)點(diǎn)表示向量進(jìn)行學(xué)習(xí)，找到其中的稀疏子結(jié)構(gòu)。

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

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

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

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

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

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

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

首先需要考慮的是低維向量空間中稀疏性的度量方法。給定一個(gè)向量集合時(shí)，如何去評(píng)價(jià)它是否稀疏。本文可以通過(guò)計(jì)算樣本之間的距離來(lái)判斷兩個(gè)點(diǎn)相距較近還是較遠(yuǎn)。對(duì)于一個(gè)向量集合，可以計(jì)算所有向量之間的距離，如果它們之間的距離都比較遠(yuǎn)，那么可以認(rèn)為這個(gè)向量集合比較稀疏。為了衡量向量集合的稀疏性，本文引入ε對(duì)的定義：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

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

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

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

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

3.2 對(duì)比算法和評(píng)估指標(biāo)

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

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

3.3 整體結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

3.5 實(shí)例分析

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

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

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

3.6 時(shí)間性能分析

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

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

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

4 結(jié)語(yǔ)

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