結(jié)合深度學習的網(wǎng)絡(luò)鄰居結(jié)構(gòu)研究及應(yīng)用*

寇曉宇，呂天舒，張 巖

北京大學 信息科學技術(shù)學院，北京 100871

1 引言

隨著信息網(wǎng)絡(luò)規(guī)模的急劇增大，網(wǎng)絡(luò)數(shù)據(jù)變得復雜多樣，通過分析和研究網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，可以探索到網(wǎng)絡(luò)中豐富的知識，進而可以提煉出多種高效的營銷模式。如在微博、Facebook為代表的社交網(wǎng)絡(luò)中，一種方式是通過已知的好友關(guān)系以及部分屬性已知的用戶推測出未知用戶的屬性，進一步得到用戶在不同屬性類別下的影響力高低，從而利用網(wǎng)絡(luò)中具有高影響力的用戶進行高效營銷；另一種方式是通過預測某用戶未來的行為，有針對性地進行個性化營銷等。

網(wǎng)絡(luò)中節(jié)點的鄰居結(jié)構(gòu)可以描述節(jié)點間的復雜交互關(guān)系，不同的鄰居結(jié)構(gòu)往往有不同的意義表達。如微博中用戶的關(guān)注關(guān)系，若某明星A自身有大量粉絲，并且A關(guān)注了B，一般情況下，B也是明星或者有高影響力的用戶；若A的大量粉絲沒有任何粉絲，一般情況下說明A有大量“僵尸粉”但實際影響力不高。目前對于網(wǎng)絡(luò)拓撲關(guān)系的研究中大多數(shù)關(guān)注直接鄰居組成的結(jié)構(gòu)情況[1-2]或者不同跳數(shù)鄰居的數(shù)目情況[3]，很少關(guān)注不同跳數(shù)鄰居組成的結(jié)構(gòu)的影響。為了解決這一問題，本文以三種最為基本的鄰居結(jié)構(gòu)進行分析。圖1給出一個實例，紅色節(jié)點為目標節(jié)點，鄰居A、B為指向目標節(jié)點的直接鄰居，構(gòu)成兩個第一種鄰居結(jié)構(gòu)；鄰居C、D構(gòu)成一個第二種鄰居結(jié)構(gòu)，其中鄰居D為目標節(jié)點的二度鄰居；鄰居E、F構(gòu)成一個第三種鄰居結(jié)構(gòu)，其中鄰居F既是目標節(jié)點的一度鄰居，也是二度鄰居。因為這三種鄰居結(jié)構(gòu)最為普遍，而且比較有代表性，既包含簡單交互關(guān)系，也有復雜交互關(guān)系，因此選取這樣三種鄰居結(jié)構(gòu)進行實驗。

網(wǎng)絡(luò)中鄰居形成的不同結(jié)構(gòu)有著不同的影響效果：例如在使用微博轉(zhuǎn)發(fā)的數(shù)據(jù)集進行用戶行為預測時，要判斷圖1的紅色節(jié)點即目標用戶V是否會去轉(zhuǎn)發(fā)微博t，V的好友們構(gòu)成了這三種鄰居結(jié)構(gòu)。若僅僅好友A或好友B轉(zhuǎn)發(fā)了t，對V觸動可能并不大；若t接連被D和C轉(zhuǎn)發(fā)，V會有更大的可能性繼續(xù)轉(zhuǎn)發(fā)t；若當t接連被F和E轉(zhuǎn)發(fā)，且E和F有共同好友V，則V也轉(zhuǎn)發(fā)t的可能性更大。

自然語言處理技術(shù)與深度學習算法在網(wǎng)絡(luò)中的應(yīng)用越來越廣泛，如網(wǎng)絡(luò)表示學習的DeepWalk模型[4]通過隨機游走得到節(jié)點序列，最終得到節(jié)點向量表示。同時深度學習算法促進了特征自動提取的實現(xiàn)，本文通過結(jié)合深度學習卷積神經(jīng)網(wǎng)絡(luò)（convolutional neural networks，CNN）[5]對網(wǎng)絡(luò)進行研究。由于直接將鄰居結(jié)構(gòu)輸入到CNN中處理會大大降低運行效率，且CNN更適應(yīng)于處理圖像數(shù)據(jù)，因此可以將鄰居結(jié)構(gòu)數(shù)據(jù)轉(zhuǎn)換為圖片的格式，提高CNN對數(shù)據(jù)處理的速度。

本文的主要貢獻包括：

（1）提出了結(jié)合深度學習CNN的網(wǎng)絡(luò)鄰居結(jié)構(gòu)影響力模型DNSI（neighbor structure influence based on deep learning），并通過自動特征提取的方式得到三種鄰居結(jié)構(gòu)在網(wǎng)絡(luò)中的影響力大小。

（2）將鄰居結(jié)構(gòu)數(shù)據(jù)轉(zhuǎn)換為便于CNN對網(wǎng)絡(luò)數(shù)據(jù)處理的樣式，即將網(wǎng)絡(luò)中節(jié)點的不同類別下三種鄰居結(jié)構(gòu)矩陣數(shù)據(jù)轉(zhuǎn)換成圖片的像素值，輸入到CNN中進行批量處理。

（3）由模型DNSI得到三種鄰居結(jié)構(gòu)的影響力，在真實世界的網(wǎng)絡(luò)數(shù)據(jù)集上進行節(jié)點屬性預測、類別中心度度量以及用戶行為預測，證明該模型在絕大多數(shù)情況下都可以提高預測的正確率。

本文第2章介紹使用拓撲結(jié)構(gòu)對網(wǎng)絡(luò)進行分析的相關(guān)研究。第3章詳細介紹了本文提出的基于深度學習的網(wǎng)絡(luò)鄰居結(jié)構(gòu)影響力模型DNSI的原理。第4章為模型在多個真實世界數(shù)據(jù)集上的實驗結(jié)果。最后，是對本文工作的總結(jié)和下一步工作的展望。

2 相關(guān)工作

本章介紹基于拓撲結(jié)構(gòu)對網(wǎng)絡(luò)分析的相關(guān)研究，包括傳統(tǒng)的基于拓撲結(jié)構(gòu)進行的網(wǎng)絡(luò)研究以及融合深度學習與拓撲結(jié)構(gòu)的網(wǎng)絡(luò)研究兩部分。

2.1 傳統(tǒng)的基于拓撲結(jié)構(gòu)進行的網(wǎng)絡(luò)研究

（1）對用戶屬性預測

針對社交網(wǎng)絡(luò)中用戶會選擇性提供個人信息的情況，He等人[6]提出將好友關(guān)系映射出貝葉斯網(wǎng)絡(luò)的方法，通過已知的先驗概率對用戶屬性進行推測，可以得到預測為每種屬性的條件概率。而Zhou等人[7]在這基礎(chǔ)上融合了用戶的社交關(guān)系，指出不同的社交關(guān)系可以推測不同的屬性。Zheleva等人[8]拓展了社交關(guān)系，通過可見的群信息來推測用戶屬性。除此之外，Mislove等人[9]提出了基于社區(qū)發(fā)現(xiàn)的推測用戶屬性算法，該算法可以應(yīng)用于在線社交網(wǎng)絡(luò)，算法思想是相同屬性的用戶更有可能形成聚合度比較高的社區(qū)群體。

（2）中心度度量

最常見也最容易理解的中心度度量指標為度中心性（degree centrality）[10]，定義為目標節(jié)點的直接鄰居數(shù)目，該指標反映出該節(jié)點的直接影響力情況。Chen等人[11]將中心度擴展到目標節(jié)點的鄰居數(shù)目與其鄰居的鄰居數(shù)目，即局部中心性（local centrality）指標。在這種思想的引領(lǐng)下，擴展度（ExDegree）指標指出，不同的節(jié)點傳播概率，會有不同的度擴展層數(shù)，比如：n節(jié)點傳播概率很小，則只需計算直接相鄰的鄰居數(shù)目，而m節(jié)點概率較大，則可能要計算三度以內(nèi)鄰居數(shù)目，且一度鄰居數(shù)目計算三次，二度鄰居數(shù)目計算兩次，三度鄰居節(jié)點只計算一次。在此基礎(chǔ)上，F(xiàn)owler等人[3]定義節(jié)點的三度以內(nèi)的鄰居都屬于強連接關(guān)系，三度以上的鄰居不會被影響，即三度影響力原則。

另兩個常見的反映節(jié)點拓撲特性的指標是介數(shù)中心性（betweenness centrality）[2]與緊密中心性（closeness centrality）[12]，介數(shù)中心性是指目標節(jié)點在網(wǎng)絡(luò)中任意兩個節(jié)點的最短路徑上的數(shù)目，緊密中心性是指某節(jié)點到達網(wǎng)絡(luò)中所有其他節(jié)點的總距離除以步數(shù)。由于這兩個方法復雜度都比較大，不適合于大型的網(wǎng)絡(luò)，因此人們提出很多改進方法，如Kitsak等人[13]提出的K-核分解算法，通過把網(wǎng)絡(luò)中所有節(jié)點從核心到邊緣分層，來定義影響力的大小。而Lv等人[14]通過研究提出H指數(shù)（對期刊或者作者進行影響力評價的指標）與K-核在衡量節(jié)點影響力方面有類似的效果。

（3）用戶行為預測

對社交網(wǎng)絡(luò)中用戶行為的分析最早出現(xiàn)在復雜性科學、統(tǒng)計物理等領(lǐng)域，如Zhou等人[15]進行人類行為特征的研究綜述。除此之外，Zaman等人[16]利用協(xié)同過濾方法，通過對博客的用戶轉(zhuǎn)發(fā)數(shù)據(jù)集進行分析，從而得到用戶轉(zhuǎn)發(fā)的概率。受到上面這些思想的啟發(fā)，Tang等人[17]深入研究了微博上用戶的轉(zhuǎn)發(fā)數(shù)據(jù)，剖析鄰居節(jié)點形成的拓撲結(jié)構(gòu)，發(fā)現(xiàn)已轉(zhuǎn)發(fā)過某消息的鄰居節(jié)點形成的連通圖個數(shù)會對目標節(jié)點產(chǎn)生影響，從而提出局部節(jié)點影響力（social influence locality）模型，并證明在已轉(zhuǎn)發(fā)某消息的鄰居數(shù)目相同的情況下，形成的連通子圖數(shù)目越少，目標節(jié)點也轉(zhuǎn)發(fā)該消息的可能性就越大。進而又提出在動態(tài)網(wǎng)絡(luò)上不同的鄰居結(jié)構(gòu)對目標節(jié)點的行為有不同的影響力，即StructInf模型[18]，并通過對微博數(shù)據(jù)的邊采樣和節(jié)點采樣，得到了20種鄰居結(jié)構(gòu)的影響力。本文中的模型便是受到StructInf模型的啟發(fā)，對其鄰居結(jié)構(gòu)進行分類簡化，使用深度學習得到鄰居結(jié)構(gòu)影響力，并對其應(yīng)用范圍進行了擴展。

2.2 融合深度學習與拓撲結(jié)構(gòu)的網(wǎng)絡(luò)研究

2.1節(jié)所述的相關(guān)研究由于受到特定因素的影響，會有一定局限性，比如網(wǎng)絡(luò)規(guī)模較大、網(wǎng)絡(luò)結(jié)構(gòu)變化大等因素。如StructInf模型需首先進行邊采樣和節(jié)點采樣，然后通過統(tǒng)計方式計算其鄰居結(jié)構(gòu)影響力，計算量龐大。而隨著深度學習的深入人心，將深度學習算法融入傳統(tǒng)網(wǎng)絡(luò)拓撲結(jié)構(gòu)的研究不斷涌現(xiàn)，相比較傳統(tǒng)的網(wǎng)絡(luò)研究方法，其優(yōu)越性一方面體現(xiàn)在準確率的提升，另一方面體現(xiàn)在算法運行速度的提高。如DeepWalk算法[4]在自然語言處理的啟發(fā)下，通過在網(wǎng)絡(luò)中隨機游走地選擇節(jié)點與邊，把網(wǎng)絡(luò)轉(zhuǎn)換成一系列“句子”，其中單詞代表節(jié)點，從而可以利用自然語言處理中的skip-gram模型[19]，將單詞（節(jié)點）轉(zhuǎn)換為表示向量，進而對網(wǎng)絡(luò)分析。LINE模型[20]在DeepWalk的基礎(chǔ)上，融合了節(jié)點的鄰居結(jié)構(gòu)，提出網(wǎng)絡(luò)中存在的兩種相似性，第一種是first-order，即兩個節(jié)點直接有邊相連則為相似；第二種是second-order，即兩個節(jié)點的共享鄰居數(shù)目越多，相似性越高。通過兩種相似性學習得到的兩種向量表示的拼接，可以得到節(jié)點的特征表示，從而可以進行網(wǎng)絡(luò)研究。

3 基于深度學習的鄰居結(jié)構(gòu)影響力研究

本文提出基于深度學習的網(wǎng)絡(luò)鄰居結(jié)構(gòu)影響力模型DNSI，該模型利用CNN算法進行特征提取，得到三種鄰居結(jié)構(gòu)的影響力，從而進行節(jié)點屬性預測、類別中心度度量以及用戶行為預測三類實驗。本章首先給出模型相關(guān)定義，然后詳細介紹模型的實現(xiàn)，并進行實例講解，最后對模型的復雜度進行討論與分析。

3.1 相關(guān)定義

該模型首先統(tǒng)計出網(wǎng)絡(luò)中所有節(jié)點的三種鄰居結(jié)構(gòu)的數(shù)目，輸入到CNN中構(gòu)建深度網(wǎng)絡(luò)，通過特征提取得到三種鄰居結(jié)構(gòu)的影響力，根據(jù)這三種影響力可以反映節(jié)點在不同圖中的不同特性。

定義1（網(wǎng)絡(luò)圖）記G=(E，V)表示一個有向網(wǎng)絡(luò)圖，其中V代表節(jié)點v的集合，即V={v1，v2，…，vn}，E代表邊ei，j的集合，即所有從節(jié)點vi指向節(jié)點vj的邊集合為E={ei，j}。記f:vi→cj表示一個映射函數(shù)：節(jié)點vi的類別為cj，D={f1，f2，…，fn}表示節(jié)點的類別映射函數(shù)的集合，C={c1，c2，…，cn}表示C為所有類別的集合，其中|C|＜＜|V|。

節(jié)點的類別在現(xiàn)實世界數(shù)據(jù)集中有多重解釋，例如：在生物數(shù)據(jù)集中，類別可以代表不同的種群；在用戶關(guān)注數(shù)據(jù)集中，類別可以代表用戶不同的屬性；在微博轉(zhuǎn)發(fā)數(shù)據(jù)集中，類別可以代表用戶不同的行為等。

定義2（一度鄰居結(jié)構(gòu)）在有向圖G=(E，V)中，記目標節(jié)點為vn，若vn的直接前驅(qū)點vi沒有任何前驅(qū)，則vi構(gòu)成一度鄰居結(jié)構(gòu)。本文中一度鄰居結(jié)構(gòu)對目標節(jié)點的影響力記為w1，類別都為cj的鄰居構(gòu)成的一度鄰居結(jié)構(gòu)的個數(shù)記為mj，1。

定義3（二度鄰居結(jié)構(gòu)）在有向圖G=(E，V)中，記目標節(jié)點為vn，若vn的直接前驅(qū)點vi的前驅(qū)vj不指向vn時，則vi與指向vi的前驅(qū)節(jié)點vj組成了二度鄰居結(jié)構(gòu)。本文中二度鄰居結(jié)構(gòu)對目標節(jié)點的影響力記為w2，類別都為cj的鄰居構(gòu)成的二度鄰居結(jié)構(gòu)的個數(shù)記為mj，2。

定義4（加強二度鄰居結(jié)構(gòu)）在有向圖G=(E，V)中，記目標節(jié)點為vn，若vn的直接前驅(qū)點vi的前驅(qū)vj也指向vn時，則vi與指向vi的前驅(qū)節(jié)點vj組成了加強二度鄰居結(jié)構(gòu)。本文中加強二度鄰居結(jié)構(gòu)對目標節(jié)點的影響力記為w3，類別都為cj的鄰居構(gòu)成的加強二度鄰居結(jié)構(gòu)的個數(shù)記為mj，3。

3.2 模型描述

記需要預測類別的目標節(jié)點為vn，其真實類別為ck，且整個網(wǎng)絡(luò)圖G中的類別總數(shù)|C|，則模型目的是學習出最合適的w1、w2、w3，使得vn被預測為自身類別ck的概率最大，即本模型的總體優(yōu)化目標函數(shù)為：

P表示當三種鄰居結(jié)構(gòu)權(quán)重為w1、w2、w3時，vn類別預測為ck的概率，即最大化屬于第ck類的鄰居構(gòu)成的三種結(jié)構(gòu)數(shù)目與三種影響力的內(nèi)積和與其他類別cq鄰居結(jié)構(gòu)數(shù)目與影響力的內(nèi)積和的差值，具體公式如下所示：

其中，mk，i指屬于第ck類的鄰居組成第i種結(jié)構(gòu)的數(shù)目，同理mq，i指屬于第cq類的鄰居組成第i種結(jié)構(gòu)的數(shù)目。從而使得節(jié)點被預測為自身真實類別的概率最大。

整個模型主要分為兩部分，經(jīng)過前兩種算法可以得到三種影響力，第三種算法是對節(jié)點屬性預測，第四種算法是對節(jié)點進行類別中心度度量。

算法1三種鄰居結(jié)構(gòu)數(shù)目的確定

算法1中第4行的L存儲了目標節(jié)點不同類別的前驅(qū)節(jié)點；第7行設(shè)置flag以及第13行和16行的remove的原因是確保每個鄰居節(jié)點只能參與到一種鄰居結(jié)構(gòu)中。

算法2數(shù)據(jù)處理與CNN網(wǎng)絡(luò)層的構(gòu)建

算法2中第1～5行把節(jié)點鄰居結(jié)構(gòu)數(shù)目矩陣轉(zhuǎn)換成一張張圖片的格式，可以加快算法處理速度。第4行說明每張圖片的長為|C|個像素，寬為3個像素。第6行得到CNN的輸入，X可以看作以圖片的形式表示的數(shù)據(jù)集的特征，Y是每個節(jié)點的類別，即數(shù)據(jù)集的標簽。第7行按照給定的切分比例分出訓練集和驗證集，第8行構(gòu)建CNN網(wǎng)絡(luò)，共1個卷積層，3個全連接層，kernal設(shè)置為1×3，網(wǎng)絡(luò)其他具體參數(shù)在實驗部分討論。第10～14行定義批處理函數(shù)，每次迭代過程中按批次取數(shù)據(jù)，然后進行交叉驗證得到最高的準確率時的卷積層的kernel值，即為三種鄰居結(jié)構(gòu)的影響力。

算法3對網(wǎng)絡(luò)節(jié)點類別的預測

算法4類別中心度度量

例如圖1中所示的一個有向圖G，紅色的為目標節(jié)點vn。已知有6個鄰居節(jié)點A、B、C、D、E、F，組成了兩個一度結(jié)構(gòu)，1個二度結(jié)構(gòu)，1個加強二度結(jié)構(gòu)，若G中|C|=3，分別為0類、1類、2類，且vn的真實類別是2類。0類在圖中是橘色，1類為藍色，2類為綠色。則根據(jù)算法1可得，Q[vn][0]=[2，0，0]，Q[vn][1]=[0，1，0]，Q[vn][1]=[0，0，1]，若已知根據(jù)算法 2 得到的w1、w2、w3為[1,2,3]。若進行類別的預測，則根據(jù)算法3可得，P[vn]=[2，2，3]，則c′=2 ，即目標節(jié)點被預測為2類。若是進行類別中心度度量，則根據(jù)算法4可得，T[vn]=[2，2，3]，即目標節(jié)點在第0類的中心度為2，在第1類的中心度為2，在第2類的中心度為3。

3.3 復雜度分析

算法的復雜度分析分為時間復雜度與空間復雜度。本模型主要是要保存所有節(jié)點的三種鄰居結(jié)構(gòu)的數(shù)目，因此空間復雜度主要受網(wǎng)絡(luò)中節(jié)點數(shù)目影響，即O(|V|)。時間復雜度需要對四種算法分別分析：

算法1的時間復雜度為O(|E|×|V|×|C|)，因為算法需要循環(huán)所有節(jié)點進行計算鄰居情況，計算每個節(jié)點的鄰居情況時只需要循環(huán)一遍網(wǎng)絡(luò)所有的邊并分別保存在不同的類別下即可。又因為類別數(shù)|C|是一個較小的常數(shù)，所以算法1的時間復雜度可以看作是與節(jié)點數(shù)與邊數(shù)乘積成線性相關(guān)的。

算法2的時間復雜度為O(k×|V|×|C|)，其中k指CNN網(wǎng)絡(luò)層的參數(shù)對網(wǎng)絡(luò)的影響，若層數(shù)增加或者增加批量訓練數(shù)據(jù)的大小就會有相應(yīng)影響，但是主要還是受節(jié)點數(shù)目的影響。其次，Batch_size和Epoch的正確選擇也影響內(nèi)存效率與內(nèi)存容量之間的平衡。

算法3和算法4的時間復雜度都為O(|C|)，對于每個節(jié)點來說，時間復雜度是常數(shù)。若是整個網(wǎng)絡(luò)所有節(jié)點計算的話，時間復雜度即與節(jié)點數(shù)目成線性相關(guān)。

4 實驗結(jié)果

本章首先介紹模型的參數(shù)設(shè)置以及對比算法，其次是評價指標和數(shù)據(jù)集介紹，最后在多個真實網(wǎng)絡(luò)數(shù)據(jù)集上進行分析實驗，并進行參數(shù)敏感性分析。

4.1 實驗設(shè)置

通過在真實網(wǎng)絡(luò)數(shù)據(jù)集上實驗發(fā)現(xiàn)，節(jié)點數(shù)目少于1 000個時，學習率大小、批處理大小等都應(yīng)相對減少，權(quán)重初始化的方式也應(yīng)變化。多次實驗后得到表1中最優(yōu)的參數(shù)設(shè)置，即算法2中構(gòu)建CNN的具體參數(shù)。表中第二行是指在網(wǎng)絡(luò)中節(jié)點數(shù)目大于等于1 000個時使用的參數(shù)集合，第三行是指節(jié)點數(shù)目小于1 000個時使用的參數(shù)集合。

Tabel 1 Parameter setting in algorithm 2表1 算法2中的參數(shù)設(shè)置

對于模型將要處理的三類任務(wù)，將分別與不同的算法進行對比，其中主要包括下面幾種算法：

（1）KNN算法：該方法是機器學習算法的一種，根據(jù)最接近目標節(jié)點的k個鄰居情況來判斷目標節(jié)點的類別，預測目標節(jié)點的類別為占比例最大的鄰居類別。

（2）ExDegree算法：擴展度算法，不同的傳播概率需計算不同的層數(shù)的鄰居節(jié)點數(shù)目，將對不同類別的鄰居分別進行統(tǒng)計。本次實驗中將采用原始論文中的參數(shù)，傳播概率0.01到0.15之間，最大擴展度為8，30次獨立實驗取平均結(jié)果，節(jié)點將被預測為其中概率最高的類別。

（3）StructInf算法：鄰居結(jié)構(gòu)影響力算法，使用作者公布的源代碼，按照原始論文中的采樣參數(shù)，q=0.9，px=0.6，py=0.1，先得到20種鄰居結(jié)構(gòu)的影響度，然后對未知用戶的行為進行預測。

（4）DeepWalk算法：通過在網(wǎng)絡(luò)圖中進行隨機游走得到節(jié)點序列，輸入到skipgram模型中得到節(jié)點向量表示，并進行多標簽預測任務(wù)。全部使用原始論文中默認的參數(shù)進行實驗。

4.2 評價指標與數(shù)據(jù)描述

本次實驗包括三部分，分別使用不同的評價指標。

（1）節(jié)點屬性預測

該任務(wù)使用正確率（Accuracy）與平均準確率（mean average precision，MAP）作為評價指標，分別定義如下：

其中，f(vj)是指vj被預測為哪一個屬性，D(vj)指vj實際上為哪一個屬性，分子表示屬性被預測正確的節(jié)點。正確率表示為預測正確的節(jié)點數(shù)目與網(wǎng)絡(luò)所有節(jié)點數(shù)目的比值。

其中，Precisioni表示某個屬性被預測正確的節(jié)點數(shù)目與所有被預測為該屬性的節(jié)點數(shù)目的比值，則MAP表示所有屬性準確率的和與網(wǎng)絡(luò)中屬性類別總數(shù)的比值。MAP指標目的是為了彌補網(wǎng)絡(luò)中很多節(jié)點由于缺少前驅(qū)節(jié)點而導致正確率較低的現(xiàn)象。

（2）類別中心度度量

該任務(wù)使用算法總運行時間Time與平均前k召回率M_Recall@k作為評價指標，平均前k召回率定義如下：

其中，index(vj)是指節(jié)點按照預測的中心度從高到低排序的序號，則Recall@k指模型得到的cj類別的前k個節(jié)點中真正屬于高中心度節(jié)點的個數(shù)。num_g指針對某個數(shù)據(jù)集已知的高中心度的節(jié)點數(shù)目。則平均前k召回率指所有類別的Recall@k的和與num_g比值。

（3）用戶行為預測

該任務(wù)使用正確率（Accuracy）、平均準確率MAP、時間Time、最大加速比MRa作為評價指標，其中MRa指其他算法與本實驗中模型運行時間的比值的最大值。

本實驗中使用的數(shù)據(jù)都為真實世界數(shù)據(jù)集，包括公開數(shù)據(jù)集與爬取的微博數(shù)據(jù)兩部分，具體情況見表2。表中“實驗”一列的“1”表示進行節(jié)點屬性預測，“2”表示類別中心度度量，“3”表示用戶行為預測。其中，Biological_tim[21]為美國生物數(shù)據(jù)集；Bcspwer10[21]為美國電網(wǎng)數(shù)據(jù)；Fpga_dcop1220[21]為電路仿真網(wǎng)絡(luò)；Facebook_4039[21]為社交網(wǎng)絡(luò)數(shù)據(jù)集；Cite（http：//www.nber.org/patents/）為美國專利引用網(wǎng)絡(luò)的子圖；weibo為爬取的新浪微博用戶互相關(guān)注網(wǎng)絡(luò)，以及這些用戶在10天內(nèi)發(fā)布微博與轉(zhuǎn)發(fā)微博的情況（所有的微博都屬于“同桌的你”“房價”“霧霾”“華為”四個主題之一，若用戶未發(fā)布或者轉(zhuǎn)發(fā)這四個主題，則類別為“0”，因此共五種類別）。

Tabel 2 Datasets information表2 數(shù)據(jù)集統(tǒng)計信息

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

4.3.1 節(jié)點屬性預測

節(jié)點屬性預測實驗中每個數(shù)據(jù)集都是選擇80%的數(shù)據(jù)作為訓練數(shù)據(jù)，其他作為測試數(shù)據(jù)。正確率和MAP指標結(jié)果見表3，對于Biological_tim小數(shù)據(jù)集，參數(shù)參考表1中的第3行。其他數(shù)據(jù)集的參數(shù)參考表1中第2行。其中KNN算法使用k=2和k=5分別做實驗，較為全面，具有代表性。

從結(jié)果可以看出，DNSI模型除了在Biological_tim數(shù)據(jù)集的MAP和Fpga_dcop1220數(shù)據(jù)集上的正確率略低于其他模型，其余的效果均好于其他模型。尤其是Bcspwer10數(shù)據(jù)集上，正確率超過其他幾種模型的13%左右，這說明DNSI在對節(jié)點屬性預測任務(wù)上有很好的效果。其中在Biological_tim小數(shù)據(jù)集上，幾種算法的正確率都比較低，通過分析原始數(shù)據(jù)發(fā)現(xiàn)，很多節(jié)點缺少前驅(qū)節(jié)點，因此會出現(xiàn)無法預測的情況。Fpga_dcop1220數(shù)據(jù)集的效果普遍都比較高，特別是KNN時得到最高正確率，說明數(shù)據(jù)本身屬性和鄰居節(jié)點屬性相關(guān)性非常大。而算法KNN中k=5時的結(jié)果往往不如k=2時的好，分析認為鄰居擴展太大，不同屬性的鄰居數(shù)目混雜造成的誤差。

Tabel 3 Node attribute prediction results表3 節(jié)點屬性預測結(jié)果

Tabel 4 Category central metric results表4 類別中心度度量結(jié)果

4.3.2 類別中心度度量

類別中心度度量實驗使用的是美國專利引用數(shù)據(jù)集，可以較好地體現(xiàn)DNSI在大數(shù)據(jù)集上的優(yōu)越表現(xiàn)。為了高效地召回中心度較高的節(jié)點，本次實驗只取入度大于100的節(jié)點組成的子圖作為數(shù)據(jù)集。其中，取專利的技術(shù)領(lǐng)域作為類別，取從1963年開始，前800個被引用次數(shù)最高的專利作為真實的高中心度節(jié)點，即式（7）中的num_g=800。

與KNN、ExDegree、Betweenness centrality、Closeness centrality四種算法進行對比實驗的結(jié)果見表4。從結(jié)果可以看出，除了在k=40時，絕大部分情況下DNSI算法都可以得到最高的召回率。特別是在k=10時，DNSI算法可以達到10%召回率，說明同其他四種算法相比，DNSI可以更為準確地召回中心度最高的節(jié)點，且DNSI算法的運行時間最短，相比于其他的算法有穩(wěn)定的優(yōu)越性。

4.3.3 用戶行為預測

用戶行為預測實驗采用爬取的weibo數(shù)據(jù)。由于微博具有時效性，為了分析三種算法預測的準確性，通過前k天的用戶關(guān)注網(wǎng)絡(luò)和轉(zhuǎn)發(fā)情況，來預測第k+1～第10天的用戶轉(zhuǎn)發(fā)情況（其中，2≤k＜10）。首先對weibo數(shù)據(jù)進行預處理，將轉(zhuǎn)發(fā)信息中包含“同桌的你”“房價”“霧霾”“華為”這4個主題的類別設(shè)置為“1～4”，其他未轉(zhuǎn)發(fā)這4類主題微博的用戶行為類別設(shè)置為“0”，然后預測用戶是否會轉(zhuǎn)發(fā)微博以及轉(zhuǎn)發(fā)哪一類微博。

DNSI模型使用表1中第2行的參數(shù)。StructInf、DeepWalk模型使用原始論文中的參數(shù)，并針對算法專門調(diào)整數(shù)據(jù)格式，使用戶關(guān)系數(shù)據(jù)和用戶行為類別數(shù)據(jù)適應(yīng)算法的輸入格式，通過前k天的數(shù)據(jù)得到20種結(jié)構(gòu)的影響概率，從而計算出第k+1～第10天的用戶轉(zhuǎn)發(fā)不同類別的微博的可能性，取最大的為預測值。

從表5中的結(jié)果可以看出，隨著k的增長，三種算法的時間都不斷增長，但是StructInf算法運行時間普遍較長，DNSI與StructInf算法的最高加速比可達6.43。當k小于6時，DNSI算法的正確率和平均準確率一般都比較高，但是當k大于6時，StructInf算法的正確率普遍較高，但是MAP不如DNSI。而DeepWalk模型的正確率和平均準確率都比較低，可能是受到數(shù)據(jù)本身的影響，因為數(shù)據(jù)中有很多節(jié)點沒有前驅(qū)節(jié)點，所以在進行多標簽分類時結(jié)果較差。三種算法的正確率最高就到80%左右，且與MAP的差距比較大，也是由于節(jié)點缺少前驅(qū)節(jié)點的原因。

Tabel 5 User behavior prediction results in weibo dataset表5 微博數(shù)據(jù)集中用戶行為預測結(jié)果

六個數(shù)據(jù)集的三種鄰居結(jié)構(gòu)影響力如圖2所示。為了使不同數(shù)據(jù)集的鄰居結(jié)構(gòu)影響力可以互相比較，將w1、w2、w3按比例縮放到0～1之間，且w1+w2+w3=1。可以發(fā)現(xiàn)，除了facebook數(shù)據(jù)集的加強二度鄰居結(jié)構(gòu)影響力比較低之外，其他數(shù)據(jù)集都是加強二度鄰居結(jié)構(gòu)影響力最高，說明關(guān)系密切且進行交互行為比較頻繁的鄰居組成會對目標節(jié)點影響更大。

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

本節(jié)度量了Batch_size、Learning_rate和Kernelinitialization三個參數(shù)對模型的影響。實驗過程中，除當前被測試的參數(shù)，其他參數(shù)均保持默認值，即表1中的第二行。測試任務(wù)使用Bcspwer10、Facebook_4039、weibo三個數(shù)據(jù)集，分別進行交叉驗證求平均正確率和平均迭代次數(shù)來展示效果。

Fig.2 3 neighbor structures'weights of 6 datasets圖2 六個數(shù)據(jù)集的三種鄰居結(jié)構(gòu)影響力

首先評估Batch_size對模型的影響，結(jié)果如圖3所示：Bcspwer10和weibo數(shù)據(jù)集是隨著Batch_size的增加，模型的正確率先升高后降低，在300～500次之間達到最高。原因是：當批處理數(shù)據(jù)太少時，梯度更新頻繁，不容易收斂；當批處理數(shù)據(jù)過多，梯度的更新難以達到最好的效果。而Facebook_4039數(shù)據(jù)集在Batch_size為100時達到最優(yōu)效果，且Batch_size>400后無變化，分析數(shù)據(jù)發(fā)現(xiàn)由于Facebook_4039數(shù)據(jù)集的類別太多，導致每種類別下的節(jié)點數(shù)目相對較少，因此當Batch_size>400時，相當于是全部數(shù)據(jù)一起輸入了。

Fig.3 Influence of batch_size on accuracy圖3 批處理數(shù)據(jù)大小對正確率的影響

Learning_rate對模型收斂速度的影響結(jié)果如圖4所示：當學習率非常小時，模型需要迭代多次才能達到收斂，當學習率在0.01時，模型在三個數(shù)據(jù)集上迭代的次數(shù)都是最少的，而當學習率大于0.01時，模型無法收斂，會出現(xiàn)在極值附近“搖擺不定”的現(xiàn)象。

Fig.4 Influence of learning_rate on DNSI convergence rate圖4 學習率對DNSI收斂速度的影響

以Bcspwer10數(shù)據(jù)集為例分析不同參數(shù)組合下權(quán)重初始化對模型的影響。第一種權(quán)重初始化方式是truncated_normal即正態(tài)分布，并設(shè)置均值為0；第二種是random_uniform即隨機初始化，并設(shè)置最小值為0。表6為4組參數(shù)組合，圖5是對模型收斂速度的影響，圖6是對模型正確率的影響。從結(jié)果可以看出隨機初始化收斂速度相對較快一些，但是正確率總體相對較低。

Tabel 6 Parameter choice表6 參數(shù)選擇

Fig.5 Influence of weight initialization method on convergence speed圖5 權(quán)重初始化方法對收斂速度的影響

Fig.6 Influence of weight initialization method on accuracy圖6 權(quán)重初始化方法對正確率的影響

5 總結(jié)與展望

本文提出了基于深度學習的網(wǎng)絡(luò)鄰居結(jié)構(gòu)影響力模型DNSI，它可以通過自動提取特征得到三種鄰居結(jié)構(gòu)的影響力，并根據(jù)這三種影響力進行節(jié)點屬性預測、類別中心度度量和用戶行為預測。通過在多個真實網(wǎng)絡(luò)數(shù)據(jù)集上進行的實驗，證明了DNSI在不同的應(yīng)用場景下都可以有優(yōu)秀的表現(xiàn)。并且發(fā)現(xiàn)普遍情況下，加強二度鄰居結(jié)構(gòu)的影響力最高，也間接說明網(wǎng)絡(luò)中節(jié)點聯(lián)系越緊密，交互行為越頻繁，對目標節(jié)點的影響就越大。

下一步，將從以下幾方面繼續(xù)嘗試：

（1）除本文三種鄰居結(jié)構(gòu)外，繼續(xù)拓展鄰居節(jié)點的度數(shù)，比如三度、四度鄰居結(jié)構(gòu)等。

（2）除CNN深度學習方法外，嘗試結(jié)合其他深度學習算法，得到更為精確的鄰居結(jié)構(gòu)影響力。

（3）更好地利用不同的鄰居結(jié)構(gòu)影響力。本文已經(jīng)證明通過不同鄰居結(jié)構(gòu)影響力可以進行節(jié)點屬性預測、類別中心度度量和用戶行為預測，在其他的方面可能也會有較大的潛力，可以繼續(xù)進行應(yīng)用研究。