寇曉宇，呂天舒，張 巖

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

1 引言

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

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

網(wǎng)絡(luò)中鄰居形成的不同結(jié)構(gòu)有著不同的影響效果：例如在使用微博轉(zhuǎn)發(fā)的數(shù)據(jù)集進(jìn)行用戶行為預(yù)測時，要判斷圖1的紅色節(jié)點(diǎn)即目標(biāo)用戶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；若當(dāng)t接連被F和E轉(zhuǎn)發(fā)，且E和F有共同好友V，則V也轉(zhuǎn)發(fā)t的可能性更大。

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

本文的主要貢獻(xiàn)包括：

（1）提出了結(jié)合深度學(xué)習(xí)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é)點(diǎn)的不同類別下三種鄰居結(jié)構(gòu)矩陣數(shù)據(jù)轉(zhuǎn)換成圖片的像素值，輸入到CNN中進(jìn)行批量處理。

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

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

2 相關(guān)工作

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

2.1 傳統(tǒng)的基于拓?fù)浣Y(jié)構(gòu)進(jìn)行的網(wǎng)絡(luò)研究

（1）對用戶屬性預(yù)測

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

（2）中心度度量

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

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

（3）用戶行為預(yù)測

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

2.2 融合深度學(xué)習(xí)與拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)研究

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

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

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

3.1 相關(guān)定義

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

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

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

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

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

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

3.2 模型描述

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

P表示當(dāng)三種鄰居結(jié)構(gòu)權(quán)重為w1、w2、w3時，vn類別預(yù)測為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é)點(diǎn)被預(yù)測為自身真實(shí)類別的概率最大。

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

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

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

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

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

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

算法4類別中心度度量

例如圖1中所示的一個有向圖G，紅色的為目標(biāo)節(jié)點(diǎn)vn。已知有6個鄰居節(jié)點(diǎn)A、B、C、D、E、F，組成了兩個一度結(jié)構(gòu)，1個二度結(jié)構(gòu)，1個加強(qiáng)二度結(jié)構(gòu)，若G中|C|=3，分別為0類、1類、2類，且vn的真實(shí)類別是2類。0類在圖中是橘色，1類為藍(lán)色，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ìn)行類別的預(yù)測，則根據(jù)算法3可得，P[vn]=[2，2，3]，則c′=2 ，即目標(biāo)節(jié)點(diǎn)被預(yù)測為2類。若是進(jìn)行類別中心度度量，則根據(jù)算法4可得，T[vn]=[2，2，3]，即目標(biāo)節(jié)點(diǎn)在第0類的中心度為2，在第1類的中心度為2，在第2類的中心度為3。

3.3 復(fù)雜度分析

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

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

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

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

4 實(shí)驗(yàn)結(jié)果

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

4.1 實(shí)驗(yàn)設(shè)置

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

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

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

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

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

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

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

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

本次實(shí)驗(yàn)包括三部分，分別使用不同的評價指標(biāo)。

（1）節(jié)點(diǎn)屬性預(yù)測

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

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

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

（2）類別中心度度量

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

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

（3）用戶行為預(yù)測

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

本實(shí)驗(yàn)中使用的數(shù)據(jù)都為真實(shí)世界數(shù)據(jù)集，包括公開數(shù)據(jù)集與爬取的微博數(shù)據(jù)兩部分，具體情況見表2。表中“實(shí)驗(yàn)”一列的“1”表示進(jìn)行節(jié)點(diǎn)屬性預(yù)測，“2”表示類別中心度度量，“3”表示用戶行為預(yù)測。其中，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)計(jì)信息

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

4.3.1 節(jié)點(diǎn)屬性預(yù)測

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

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

Tabel 3 Node attribute prediction results表3 節(jié)點(diǎn)屬性預(yù)測結(jié)果

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

4.3.2 類別中心度度量

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

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

4.3.3 用戶行為預(yù)測

用戶行為預(yù)測實(shí)驗(yàn)采用爬取的weibo數(shù)據(jù)。由于微博具有時效性，為了分析三種算法預(yù)測的準(zhǔn)確性，通過前k天的用戶關(guān)注網(wǎng)絡(luò)和轉(zhuǎn)發(fā)情況，來預(yù)測第k+1～第10天的用戶轉(zhuǎn)發(fā)情況（其中，2≤k＜10）。首先對weibo數(shù)據(jù)進(jìn)行預(yù)處理，將轉(zhuǎn)發(fā)信息中包含“同桌的你”“房價”“霧霾”“華為”這4個主題的類別設(shè)置為“1～4”，其他未轉(zhuǎn)發(fā)這4類主題微博的用戶行為類別設(shè)置為“0”，然后預(yù)測用戶是否會轉(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)的影響概率，從而計(jì)算出第k+1～第10天的用戶轉(zhuǎn)發(fā)不同類別的微博的可能性，取最大的為預(yù)測值。

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

Tabel 5 User behavior prediction results in weibo dataset表5 微博數(shù)據(jù)集中用戶行為預(yù)測結(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ù)集的加強(qiáng)二度鄰居結(jié)構(gòu)影響力比較低之外，其他數(shù)據(jù)集都是加強(qiáng)二度鄰居結(jié)構(gòu)影響力最高，說明關(guān)系密切且進(jìn)行交互行為比較頻繁的鄰居組成會對目標(biāo)節(jié)點(diǎn)影響更大。

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

本節(jié)度量了Batch_size、Learning_rate和Kernelinitialization三個參數(shù)對模型的影響。實(shí)驗(yàn)過程中，除當(dāng)前被測試的參數(shù)，其他參數(shù)均保持默認(rèn)值，即表1中的第二行。測試任務(wù)使用Bcspwer10、Facebook_4039、weibo三個數(shù)據(jù)集，分別進(jìn)行交叉驗(yàn)證求平均正確率和平均迭代次數(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次之間達(dá)到最高。原因是：當(dāng)批處理數(shù)據(jù)太少時，梯度更新頻繁，不容易收斂；當(dāng)批處理數(shù)據(jù)過多，梯度的更新難以達(dá)到最好的效果。而Facebook_4039數(shù)據(jù)集在Batch_size為100時達(dá)到最優(yōu)效果，且Batch_size>400后無變化，分析數(shù)據(jù)發(fā)現(xiàn)由于Facebook_4039數(shù)據(jù)集的類別太多，導(dǎo)致每種類別下的節(jié)點(diǎn)數(shù)目相對較少，因此當(dāng)Batch_size>400時，相當(dāng)于是全部數(shù)據(jù)一起輸入了。

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

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

Fig.4 Influence of learning_rate on DNSI convergence rate圖4 學(xué)習(xí)率對DNSI收斂速度的影響

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

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é)與展望

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

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

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

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

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