潘 侃，尹春林，王 磊，陳端兵,3*

（1. 云南電網(wǎng)有限責(zé)任公司電力科學(xué)研究院 昆明 650217；2. 成都數(shù)之聯(lián)科技有限公司 成都 610041；3. 電子科技大學(xué)大數(shù)據(jù)研究中心 成都 611731）

現(xiàn)實(shí)生活中的復(fù)雜系統(tǒng)（如交通運(yùn)輸系統(tǒng)、生物系統(tǒng)）可以很自然地用圖表示，其中節(jié)點(diǎn)表示系統(tǒng)中的各個要素，邊表示要素之間的關(guān)系[1]。復(fù)雜網(wǎng)絡(luò)的研究逐漸從宏觀層面深入微觀層面[2]。節(jié)點(diǎn)作為系統(tǒng)中最小的元素，不同節(jié)點(diǎn)在系統(tǒng)中的地位是不同的。重要節(jié)點(diǎn)是指相比于網(wǎng)絡(luò)中其他節(jié)點(diǎn)，能更大程度地影響網(wǎng)絡(luò)功能的一些特殊節(jié)點(diǎn)。這種節(jié)點(diǎn)數(shù)量不多，但是其影響力卻可以快速波及網(wǎng)絡(luò)中大部分節(jié)點(diǎn)，如社交網(wǎng)絡(luò)中權(quán)威賬號的輿論引導(dǎo)，交通網(wǎng)路中重要路口堵塞導(dǎo)致交通系統(tǒng)癱瘓等。節(jié)點(diǎn)重要性排序[1]和相對重要節(jié)點(diǎn)的挖掘[3-4]對現(xiàn)實(shí)生活有著重要的指導(dǎo)意義。在網(wǎng)絡(luò)分析中，節(jié)點(diǎn)的重要性通常用中心性[5]來度量，其主要目的是為基礎(chǔ)網(wǎng)絡(luò)的每個節(jié)點(diǎn)分配一個實(shí)值，用于度量該節(jié)點(diǎn)對其他節(jié)點(diǎn)的影響力。目前已有不少成熟的節(jié)點(diǎn)中心性計(jì)算方法，主要分為兩類[3]：1） 基于網(wǎng)絡(luò)結(jié)構(gòu)特征的指標(biāo)和方法；2） 基于隨機(jī)游走的指標(biāo)和方法。

基于結(jié)構(gòu)特征的指標(biāo)和方法主要根據(jù)其他節(jié)點(diǎn)與已知節(jié)點(diǎn)之間的網(wǎng)絡(luò)結(jié)構(gòu)特征設(shè)計(jì)相對重要指標(biāo)。這些方法通過捕捉節(jié)點(diǎn)之間的局部連邊信息或路徑信息，衡量節(jié)點(diǎn)的重要性。度中心性（degree）是最簡單的中心性度量方法，主要利用網(wǎng)絡(luò)節(jié)點(diǎn)的連邊信息刻畫節(jié)點(diǎn)的重要性。度中心性認(rèn)為一個節(jié)點(diǎn)鄰居數(shù)目越多，該節(jié)點(diǎn)影響力就越大。但若節(jié)點(diǎn)在網(wǎng)絡(luò)中屬于核心位置，即使它本身度很小，也有較高的影響力?；诖耍墨I(xiàn)[6]提出了基于K-殼分解（K-shell decomposition）的K-shell 中心性，該中心性將外圍的節(jié)點(diǎn)層層剝?nèi)?，使處于?nèi)層的節(jié)點(diǎn)擁有較高的影響力。還有一些基于路徑的中心性計(jì)算方法，如節(jié)點(diǎn)的接近中心性（closeness）[7]考慮將節(jié)點(diǎn)與其他節(jié)點(diǎn)的測地距離之和的倒數(shù)作為節(jié)點(diǎn)重要性。而介數(shù)中心性（betweenness）[8]認(rèn)為經(jīng)過一個節(jié)點(diǎn)的最短路徑越多，這個節(jié)點(diǎn)就越重要。受到介數(shù)中心性啟發(fā)，流介數(shù)中心性（flow betweenness）[9]、連通介數(shù)中心性（communicability betweenness）[10]、隨機(jī)游走介數(shù)中心性（random walk betweenness）[11]和路由介數(shù)中心性（routing betweenness）[12]相繼被提出。除此以外，H-index[13]作為評價學(xué)者學(xué)術(shù)成就的權(quán)威方法，也能很自然地延伸到復(fù)雜網(wǎng)絡(luò)的重要節(jié)點(diǎn)挖掘任務(wù)中。

上述方法能夠很好地捕捉節(jié)點(diǎn)周圍的局部結(jié)構(gòu)信息。除此之外，很多學(xué)者采用基于路徑和隨機(jī)游走的方法，利用整個圖的拓?fù)湫畔⑼诰驁D中的重要節(jié)點(diǎn)。在不考慮時間開銷的前提下，從初始節(jié)點(diǎn)出發(fā)將信息傳播出去，當(dāng)隨機(jī)游走趨于穩(wěn)定時，信息保留越多的節(jié)點(diǎn)越重要。特征向量中心性（eigenvector）傳播時不僅考慮節(jié)點(diǎn)的鄰居數(shù)目，也同時考慮每個鄰居節(jié)點(diǎn)的重要性。另外，學(xué)者們還提出了HITs[14]、LeaderRank[15]、PageRank[16]、Vote Rank[17]等 其 他全局游走的方法?？傮w而言，這些基于全局游走的方法計(jì)算成本較高，不能有效地應(yīng)用于超大規(guī)模網(wǎng)絡(luò)。文獻(xiàn)[18]考慮四階鄰居，提出了局部中心性方法LocalRank，在時間復(fù)雜度和準(zhǔn)確率之間找到了一個較好的平衡點(diǎn)。

雖然復(fù)雜網(wǎng)絡(luò)中檢測節(jié)點(diǎn)重要性的方法很多，但它們都試圖找到能反映節(jié)點(diǎn)重要性的某種因素。但節(jié)點(diǎn)重要性之所以不同，是因?yàn)椴煌?jié)點(diǎn)周圍的結(jié)構(gòu)是異質(zhì)的[19]。因此，本文利用機(jī)器學(xué)習(xí)方法挖掘節(jié)點(diǎn)結(jié)構(gòu)特征與節(jié)點(diǎn)重要性之間的關(guān)系。首先基于二步可達(dá)子圖的節(jié)點(diǎn)信息，采用特征工程中的特征提取、特征重構(gòu)方法，提出能描述節(jié)點(diǎn)周圍信息的特征集合。再利用簡單的線性回歸模型（linear regression model）[20]，學(xué)習(xí)節(jié)點(diǎn)局部結(jié)構(gòu)與節(jié)點(diǎn)重要性之間的關(guān)系。在13 個真實(shí)網(wǎng)絡(luò)中，將訓(xùn)練所得模型與度中心性、介數(shù)中心性[8]、K-shell[6]、H-index[13]和DynamicRank[21]中心性進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明，本方法能更準(zhǔn)確、更有效地識別出復(fù)雜網(wǎng)絡(luò)中對信息傳播影響較大的重要節(jié)點(diǎn)。

1 基于特征工程的重要節(jié)點(diǎn)挖掘方法

重要節(jié)點(diǎn)挖掘是網(wǎng)絡(luò)攻擊和信息傳播及控制等領(lǐng)域中的核心問題之一。網(wǎng)絡(luò)中的少數(shù)節(jié)點(diǎn)具有非常高的影響力。而造成網(wǎng)絡(luò)中節(jié)點(diǎn)重要性差異的根本原因是節(jié)點(diǎn)周圍的結(jié)構(gòu)差異[19]。閉塞的局部結(jié)構(gòu)會阻礙節(jié)點(diǎn)影響力的傳播，而好的局部結(jié)構(gòu)會促進(jìn)信息在網(wǎng)絡(luò)中傳播。

本文研究主要針對無向無權(quán)圖G(V,E)，其中V={v1,v2,···,vn}是 節(jié)點(diǎn)集合，E={e1,e2,···,em}是邊集合，n和m分別是節(jié)點(diǎn)數(shù)量和邊數(shù)量。為了提取和重構(gòu)節(jié)點(diǎn)鄰居信息得到節(jié)點(diǎn)的局部結(jié)構(gòu)特征，首先拓展兩個鄰居的定義。

定義1 二階鄰居

若網(wǎng)絡(luò)中節(jié)點(diǎn)u的一階鄰居定義為 Γ1(u)，那么節(jié)點(diǎn)u的二階鄰居可定義為：

定義2 二階外聯(lián)鄰居

二階外聯(lián)鄰居屬于二階鄰居的子集，區(qū)別在于二階外聯(lián)鄰居是二階鄰居與一階鄰居的差集，定義如下：

從局部角度考慮，節(jié)點(diǎn)的度以及節(jié)點(diǎn)鄰居的度最能反映節(jié)點(diǎn)的局部結(jié)構(gòu)特征。除此以外，現(xiàn)有的中心性算法中，H-index 和K-shell 也是能較好反映節(jié)點(diǎn)重要程度的中心性指標(biāo)。然而這些中心性指標(biāo)對節(jié)點(diǎn)周圍復(fù)雜多樣的局部結(jié)構(gòu)還是很難刻畫。

度中心性可以廣泛地概括簡單圖中重要節(jié)點(diǎn)的規(guī)律，一般來說，節(jié)點(diǎn)的鄰居越多，影響力越大?，F(xiàn)實(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)的局部結(jié)構(gòu)非常復(fù)雜，單獨(dú)用某一種復(fù)雜網(wǎng)絡(luò)指標(biāo)無法準(zhǔn)確地刻畫節(jié)點(diǎn)周圍的結(jié)構(gòu)信息。如圖1a～1d 中，節(jié)點(diǎn)A、B、C、D具有不同的局部結(jié)構(gòu)，相應(yīng)的中心節(jié)點(diǎn)的影響力也有差異，使用傳統(tǒng)的中心性方法無法準(zhǔn)確區(qū)分這4 個節(jié)點(diǎn)的真實(shí)重要性。如采用度中心計(jì)算時，A、B、C、D屬于同一類型節(jié)點(diǎn)（dA=dB=dC=dD=2）。而Hindex 無法判斷節(jié)點(diǎn)A、C、D（hA=hC=hD=2）。另外K-shell 中心性也無法判斷A、B和C、D（kA=kB=1,kC=kD=2）。可以看出，傳統(tǒng)方法在節(jié)點(diǎn)重要性分析中還屬于粗粒度方法，對于不同的微觀局部結(jié)構(gòu)有時很難區(qū)分。

圖1 復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的局部結(jié)構(gòu)示例

1.1 特征提取

由于傳統(tǒng)的基于中心性的方法不能很好地刻畫節(jié)點(diǎn)的局部結(jié)構(gòu)，特別是對于二階鄰居結(jié)構(gòu)信息的刻畫過于粗糙。因此本文主要以節(jié)點(diǎn)的鄰居信息為基礎(chǔ)，提取和重組能刻畫節(jié)點(diǎn)局部結(jié)構(gòu)的特征。

課堂中的所有元素都應(yīng)該相互協(xié)同合作的，教師和學(xué)生作為課堂中的兩個參與者，師生之間的互動交流是不可缺少的?？v觀當(dāng)前的高中英語課堂，教學(xué)氛圍比較壓抑，師生之間的交流不多，一般總是教師單方面的滔滔不絕的講述，學(xué)生沒有參與其中，只是被動的接受知識灌輸，實(shí)際上只有在師生之間友好交流的過程中，才能帶動學(xué)生參與學(xué)習(xí)，達(dá)到高效教學(xué)的效果，同時也增進(jìn)了師生感情。因此，教師應(yīng)該注重搭建師生互動平臺，在教學(xué)中要設(shè)計(jì)更多師生之間交流反饋的機(jī)會，比如可以開展小組合作學(xué)習(xí)，讓學(xué)生自主討論出一篇課文中比較難以理解的詞匯釋義或者句型語法，然后教師再引導(dǎo)他們進(jìn)行解決，這有助于鍛煉學(xué)生的感知力和表達(dá)能力，真正實(shí)現(xiàn)師生協(xié)調(diào)發(fā)展。

1.1.1 一階鄰居特征

從一階鄰居開始，一般而言，度越大，信息越有可能傳播出去，因此，節(jié)點(diǎn)的度是刻畫信息傳播能力的一個重要特征。除此以外，一階鄰居度的分布一定程度上反映了節(jié)點(diǎn)二階鄰居的結(jié)構(gòu)信息。如圖1 中，雖然節(jié)點(diǎn)A、B、C、D的度都為2，但是它們的一階鄰居度分布相差卻很大。特別地，A的一階鄰居度分布為[4,4]，而B的分布是[2,6]。顯然，A的一階鄰居度的分布更加均衡，而B的鄰居度分配不均衡。由于這兩個一階鄰居度的分布對應(yīng)的局部結(jié)構(gòu)不同，導(dǎo)致節(jié)點(diǎn)的影響力也不同。在低感染率下，鄰居度分布越均勻，信息往外傳播能力越強(qiáng)。若度分布極度不均衡，在圖1b 中，若度為6的節(jié)點(diǎn)沒有被感染，B節(jié)點(diǎn)的傳播能力會大打折扣。

為了描述鄰居度的分布均衡性，本文引入國際通用的，用以衡量一個國家或地區(qū)居民收入差距的常用指標(biāo)：基尼系數(shù)（Gini coefficient），基尼系數(shù)最大為1，最小等于0。系數(shù)越大說明該分布越不均勻，系數(shù)越接近0 表明收入分配越是趨向平等。對給定的序列x=[x1,x2,···,xn]，該序列數(shù)據(jù)平均值為 μ，可采用下式直接計(jì)算序列的基尼系數(shù)：

如圖1 所示，B的一階鄰居度的差距很大，而A的一階鄰居相對平衡。給定節(jié)點(diǎn)u，其一階鄰居為 Γ1(u)， 一階鄰居度的集合為D1(u)={dv|v∈Γ1(u)}。為了刻畫節(jié)點(diǎn)u的一階鄰居度分布的平衡度，定義節(jié)點(diǎn)u的一階鄰居度的基尼系數(shù)：

然而，只有基尼系數(shù)還不能完全反映節(jié)點(diǎn)一階鄰居局部結(jié)構(gòu)。如圖1 中A和C，一階鄰居的基尼系數(shù)都為0 且中心節(jié)點(diǎn)的度都為2，僅靠這兩個特征還不能很好區(qū)分相同度節(jié)點(diǎn)重要性的差異，有時小度節(jié)點(diǎn)甚至比大度節(jié)點(diǎn)具有更高的傳播影響力。為了體現(xiàn)這種差異性，引入特征2 區(qū)分這種情況，特征2 為一階鄰居度之和，定義如下：

1.1.2 二階鄰居特征

有時僅用一階鄰居的特征還不能很好地刻畫節(jié)點(diǎn)周圍的局部特征，如圖1 中的節(jié)點(diǎn)A和D，Gini(D1(A))=Gini(D1(D))=0 且 SUM(D1(A))= SUM(D1(D))=0，僅從這兩個角度還是無法區(qū)別A、D兩種局部結(jié)構(gòu)。針對上述情況，本文將二階鄰居數(shù)目作為特征，記為 Len(Γ2(u))， 其中 Len(Γ2(A))=6，Len(Γ2(D))=3。

在對一階鄰居的規(guī)模和分布進(jìn)行分析后，將基尼系數(shù)和規(guī)模作為二階鄰居的特征。但與一階鄰居不同的是，一階鄰居與二階鄰居會出現(xiàn)重疊鄰居的情況。如圖1f 中的F節(jié)點(diǎn)，其周圍很多一階鄰居之間存在連接。在獲取二階鄰居時，很多一階鄰居還會被判定為二階鄰居。重疊的鄰居越多，節(jié)點(diǎn)聚集系數(shù)越大，節(jié)點(diǎn)的影響力在局部區(qū)域內(nèi)能充分地傳播，但這種結(jié)構(gòu)會導(dǎo)致信息很難再往外傳播[22]。如圖1 所示，在鄰居節(jié)點(diǎn)數(shù)目一致的情況下，E節(jié)點(diǎn)往外傳播的能力大于F節(jié)點(diǎn)。因此中心節(jié)點(diǎn)的二階外聯(lián)鄰居Γ ?2(u)度的分布和規(guī)模反映了信息從中心節(jié)點(diǎn)向外傳播的能力。基于此，本文提取二階外聯(lián)鄰居度的基尼系數(shù)和SUM 值作為節(jié)點(diǎn)的局部結(jié)構(gòu)特征。

表1 節(jié)點(diǎn)局部結(jié)構(gòu)特征度量

至此，本文從局部結(jié)構(gòu)的規(guī)模和平衡性兩個角度，針對一階、二階鄰居，提取了共8 個特征，具體計(jì)算方法和描述總結(jié)在表1 中。除上述特征外，還有其他類型的特征對排序結(jié)果也有影響，如鄰居度的最大值、平均值、方差等。這些特征都會對節(jié)點(diǎn)重要性判斷帶來影響，本文僅作為一種算法思路，通過重構(gòu)二階鄰居內(nèi)的度信息，得到刻畫節(jié)點(diǎn)鄰居結(jié)構(gòu)最主要的8 個特征用于節(jié)點(diǎn)重要性排序。

1.2 節(jié)點(diǎn)重要性學(xué)習(xí)建模

節(jié)點(diǎn)的重要性與節(jié)點(diǎn)周圍的局部結(jié)構(gòu)有著緊密的關(guān)系。本文根據(jù)表1 列出的特征，采用線性回歸（linear regression）模型對節(jié)點(diǎn)局部特征與節(jié)點(diǎn)重要性關(guān)系進(jìn)行建模。定義一個線性回歸函數(shù)f:x→s，將節(jié)點(diǎn)的結(jié)構(gòu)特征映射為節(jié)點(diǎn)的相對重要性，具體可表示為：

式中，w為特征向量的權(quán)重向量；x是特征向量；b是誤差項(xiàng)。

圖2 節(jié)點(diǎn)局部特征生成示例

至此，在獲得了節(jié)點(diǎn)v的歸一化結(jié)構(gòu)特征xv和真實(shí)重要性sv后，采用線性回歸模型，選取均方誤差（mean squared error, MSE）建立目標(biāo)函數(shù)以學(xué)習(xí)節(jié)點(diǎn)局部結(jié)構(gòu)特征與真實(shí)重要性之間的關(guān)系：

為了獲得模型最優(yōu)的回歸系數(shù)，本文采用Adam 優(yōu)化器[27]優(yōu)化目標(biāo)函數(shù)。

1.3 模型訓(xùn)練

本文用LastFM[28]作為訓(xùn)練網(wǎng)絡(luò)對節(jié)點(diǎn)重要性挖掘模型進(jìn)行訓(xùn)練學(xué)習(xí)。LastFM 是一個2020 年3 月從公共API 收集的社交網(wǎng)絡(luò)，節(jié)點(diǎn)代表亞洲的用戶賬號，邊代表它們之間相互關(guān)注的關(guān)系，其節(jié)點(diǎn)規(guī)模為7 624，邊數(shù)量為27 806，最大度為216。首先從LastFM網(wǎng)絡(luò)中提取節(jié)點(diǎn)的特征向量；同時，以LastFM 網(wǎng)絡(luò)中每個節(jié)點(diǎn)為初始感染節(jié)點(diǎn)，進(jìn)行1 000 次獨(dú)立的SIR 傳播仿真，將1 000次的平均sv作為每個節(jié)點(diǎn)的標(biāo)簽；最后，將標(biāo)簽和特征向量作為訓(xùn)練集輸入線性回歸模型，訓(xùn)練得到節(jié)點(diǎn)重要性度量模型，用于預(yù)測其他網(wǎng)絡(luò)中每個節(jié)點(diǎn)的重要性。

2 實(shí)驗(yàn)與討論

本文用13 個不同類型的真實(shí)網(wǎng)絡(luò)對本文提出的方法進(jìn)行測試，并和度中心性、介數(shù)中心性、Kshell 中心性、H-index 中心性和DynamicRank 中心性進(jìn)行對比。

2.1 評估指標(biāo)

2.2 數(shù)據(jù)集

表2 13 個真實(shí)網(wǎng)絡(luò)的基本特征數(shù)據(jù)

本文采用的13 個真實(shí)網(wǎng)絡(luò)中，包括了規(guī)模較小的網(wǎng)絡(luò)（如Jazz），也有規(guī)模較大的網(wǎng)絡(luò)（如Cond-Mat, CM），其平均度的范圍為2～35。其中，1） Jazz 是爵士樂手之間的協(xié)作網(wǎng)絡(luò)，每條邊表示兩個樂手在一個樂隊(duì)中一起演奏；2） NetScience（NS）是發(fā)表關(guān)于復(fù)雜網(wǎng)絡(luò)主題論文的科學(xué)家之間的合作者網(wǎng)絡(luò)；3） Email 是Rovirai Virgili 大學(xué)成員之間的電子郵件交換網(wǎng)絡(luò)；4） Sex 是研究男女性伙伴的網(wǎng)絡(luò)；5） Polblog 是2004 年美國大選中博客之間的超鏈接形成的網(wǎng)絡(luò)；6） USAir 是2010 年美國機(jī)場之間的航空網(wǎng)絡(luò)；7） Router 是由Rocketfuel 項(xiàng)目收集的互聯(lián)網(wǎng)路由器拓?fù)渚W(wǎng)絡(luò)；8） Cond-Mat（CM）是1995 年-1999 年arXiv 出版物的科學(xué)家合作網(wǎng)絡(luò)；9） Grid 是美國西部的某電力網(wǎng)絡(luò)；10） Figeys、Stelzl 和Vidal是3 個蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)；11） Hamster是一個包含網(wǎng)站用戶之間的友誼和家庭關(guān)系的網(wǎng)絡(luò)。以上數(shù)據(jù)集可從網(wǎng)站（http://konect.cc/networks/）獲得，這13 個真實(shí)網(wǎng)絡(luò)的詳細(xì)特征如表2 所示，其中，n是節(jié)點(diǎn)數(shù)目，m是邊數(shù)目，表示所有節(jié)點(diǎn)的平均度，kmax代表節(jié)點(diǎn)的最大度，所有節(jié)點(diǎn)的平均聚集系數(shù)為。

2.3 實(shí)驗(yàn)及分析

為了檢測模型預(yù)測的準(zhǔn)確性，本文首先對測試網(wǎng)絡(luò)中每個節(jié)點(diǎn)作1 000 次SIR 傳播仿真，將1 000次的平均sv作為測試網(wǎng)絡(luò)節(jié)點(diǎn)的真實(shí)影響力。再根據(jù)節(jié)點(diǎn)影響力的預(yù)測值和真實(shí)值的Kendall Tau 系數(shù)評價模型的預(yù)測效果。本文方法和其他基準(zhǔn)方法的對比結(jié)果如表3 所示。

從表3 可以看出，本文提出的方法在大部分網(wǎng)絡(luò)中表現(xiàn)非常好，13 個網(wǎng)絡(luò)中有10 個網(wǎng)絡(luò)都好于對比方法，尤其在NS 網(wǎng)絡(luò)中，相比于表現(xiàn)第二好的DynamicRank 中心性方法，相關(guān)系數(shù)提升了0.2456。在平均度比較高（平均度大于20）的網(wǎng)絡(luò)中，由于訓(xùn)練集中缺少類似的大度點(diǎn)的局部結(jié)構(gòu)，無法學(xué)習(xí)到大度節(jié)點(diǎn)的重要性，極大影響了模型的判斷，如在Polblog 網(wǎng)絡(luò)中，最大度為467，遠(yuǎn)高于訓(xùn)練網(wǎng)絡(luò)的最大度216。另一方面，平均度反映網(wǎng)絡(luò)中常見的局部結(jié)構(gòu)。如訓(xùn)練網(wǎng)絡(luò)LastFM 的平均度為7.294，雖然也存在度為20 的局部結(jié)構(gòu)，但這種結(jié)構(gòu)在訓(xùn)練網(wǎng)絡(luò)中并不常見，轉(zhuǎn)換得到的訓(xùn)練集會極不平衡。模型對度為20 的局部結(jié)構(gòu)無法充分學(xué)習(xí)，因此模型在度大于20 的網(wǎng)絡(luò)表現(xiàn)也就較差。

表3 不同方法與SIR 模型仿真結(jié)果的Kendall Tau 相關(guān)性系數(shù)

為了驗(yàn)證本文學(xué)習(xí)模型的魯棒性，本文在不同感染概率下對模型效果進(jìn)行了分析。設(shè)置 β=cβc，選取不同c值用于分析選取不同傳染概率對重要節(jié)點(diǎn)挖掘的影響。

如圖3 所示，在不同感染概率β=βc、1.5βc、2βc、2.5βc下，本文利用特征工程的方法提出的特征能夠很好地描述節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性。在不同的感染概率下，本文方法依舊能在低平均度的網(wǎng)絡(luò)中取得最好的效果。圖3 的結(jié)果表明，雖然基于特征工程的方法在訓(xùn)練時依賴于感染概率，但訓(xùn)練得到的重要性評估模型對感染概率并不敏感，適用于對不同感染概率下，節(jié)點(diǎn)重要性的挖掘。

圖3 本文方法與其他基準(zhǔn)方法在各網(wǎng)絡(luò)中不同感染概率下的Kendall Tau 相關(guān)性系數(shù)對比

進(jìn)一步，為了驗(yàn)證這8 個特征的有效性，本文在不同網(wǎng)絡(luò)上選取不同特征組合進(jìn)行實(shí)驗(yàn)分析。

1） 在Figeys 網(wǎng)絡(luò)中去除特征1 后，算法排序結(jié)果和實(shí)際仿真排序結(jié)果的Kendall Tau 相關(guān)性系數(shù)從0.83 下降到0.77。

2） 在NS 網(wǎng)絡(luò)中去除特征1 后，Kendall Tau 相關(guān)性系數(shù)從0.879 下降至0.872，若去除特征2，Kendall Tau 相關(guān)性系數(shù)下降更為明顯，降至0.861。

3） 若在Grid 網(wǎng)絡(luò)中去除特征2，Kendall Tau相關(guān)性系數(shù)從0.775 下降至0.728。若再進(jìn)一步去除特征7，Kendall Tau 相關(guān)性系數(shù)大幅降低至0.688。

4） 在Stelzl 網(wǎng)絡(luò)中，若同時去除特征3 和7 時，Kendall Tau 相關(guān)性系數(shù)從0.89 大幅下降至0.79。

從上面的分析可以看出，8 個特征在不同網(wǎng)絡(luò)的重要節(jié)點(diǎn)排序上相互補(bǔ)充和促進(jìn)，去掉某個或某組特征，對節(jié)點(diǎn)重要性研判將帶來直接影響。而完整的8 個特征，模型更穩(wěn)定，也能更準(zhǔn)確地判斷網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性。

同時，根據(jù)信息傳播理論，節(jié)點(diǎn)對三階鄰居以外的影響已經(jīng)很小，更高階的鄰居信息趨于同質(zhì)化[30]。為了驗(yàn)證更高階鄰居對模型的影響，根據(jù)特征4-8，拓展三階鄰居的特征9-13（三階鄰居的度之和、三階鄰居數(shù)目、三階鄰居度的基尼系數(shù)、三階外聯(lián)鄰居度之和、三階外聯(lián)鄰居度的基尼系數(shù)）。選取email 作為測試網(wǎng)絡(luò)，發(fā)現(xiàn)8 個特征訓(xùn)練所得模型的排序結(jié)果與仿真結(jié)果的Kendall Tau 相關(guān)性系數(shù)為0.925，而13 個特征的相關(guān)系數(shù)為0.927，提升并不明顯。實(shí)驗(yàn)表明，選取二階鄰居以內(nèi)的信息已足夠。

3 結(jié) 束 語

本文利用特征工程方法對節(jié)點(diǎn)的鄰居信息進(jìn)行提取和重構(gòu)，提取更能反映節(jié)點(diǎn)局部結(jié)構(gòu)的特征向量。根據(jù)節(jié)點(diǎn)的局部結(jié)構(gòu)特征信息，建立了用于挖掘網(wǎng)絡(luò)中重要節(jié)點(diǎn)的機(jī)器學(xué)習(xí)模型。用13 個實(shí)際網(wǎng)絡(luò)對本文所提方法的有效性進(jìn)行了測試，并和典型的基準(zhǔn)方法進(jìn)行了對比。實(shí)驗(yàn)結(jié)果表明，本文提出的機(jī)器學(xué)習(xí)模型能有效地挖掘網(wǎng)絡(luò)中的重要節(jié)點(diǎn)，13 個網(wǎng)絡(luò)中有10 個網(wǎng)絡(luò)的效果顯著地優(yōu)于已有方法。由于本文方法一定程度上依賴于訓(xùn)練網(wǎng)絡(luò)的局部結(jié)構(gòu)，對于訓(xùn)練數(shù)據(jù)中出現(xiàn)較少的局部結(jié)構(gòu)，由于訓(xùn)練不充分，在測試時表現(xiàn)出的效果整體欠佳。在未來的研究中，一方面是構(gòu)建更加豐富多樣的訓(xùn)練集，另一方面，需提取更為豐富的局部特征，提升模型的預(yù)測能力。近年來，隨著深度學(xué)習(xí)的發(fā)展，尤其是圖神經(jīng)網(wǎng)絡(luò)的研究深入，如何利用圖神經(jīng)網(wǎng)絡(luò)訓(xùn)練泛化性能更好的復(fù)雜網(wǎng)絡(luò)局部結(jié)構(gòu)特征的表達(dá)模型[31]，從而提高重要節(jié)點(diǎn)識別的準(zhǔn)確率也是一個重要的研究方向。