融合拓撲勢的有向社交網(wǎng)絡關鍵節(jié)點識別模型

李 慧

(首都師范大學 教育學院，北京100048)

1 引 言

復雜網(wǎng)絡系統(tǒng)的非同質拓撲結構，決定了網(wǎng)絡中節(jié)點的重要度不同.與普通節(jié)點相比，復雜網(wǎng)絡的重要節(jié)點對網(wǎng)絡的結構與功能具有更明顯的影響[1]，采用定量方法評估網(wǎng)絡節(jié)點重要度、識別網(wǎng)絡中的關鍵節(jié)點意義重大，已成為復雜網(wǎng)絡理論研究的熱點之一.作為典型的復雜網(wǎng)絡，社交網(wǎng)絡通常指以各種連接或相互作用的模式而存在的一組人或群體[2-5]，如朋友關系網(wǎng)絡、科研合作網(wǎng)絡、在線社交關系網(wǎng)絡等，可以抽象為一個由節(jié)點(代表社會成員)和連邊(代表節(jié)點間關系)構成的網(wǎng)絡圖.在社交網(wǎng)絡中，每位社會成員扮演著不同的社會角色，反映了該用戶與其鄰居甚至與整個網(wǎng)絡中所有用戶之間的行為關系.識別用戶角色尤其是關鍵節(jié)點對于用戶行為預測、組織網(wǎng)絡分析、輿情監(jiān)測、網(wǎng)絡營銷等具有重要的理論意義和實用價值.

目前已提出許多復雜網(wǎng)絡關鍵節(jié)點識別算法，基于網(wǎng)絡拓撲結構的經典方法包括度中心性[6]、介數(shù)中心性[7]、接近中心性[8]、特征向量中心性[9]等.最直觀最基本的方法是度中心性，其計算簡單有效，但僅反映復雜網(wǎng)絡的局部信息，沒有考慮節(jié)點的自身特性和節(jié)點之間的相互影響[10].Chen等考慮節(jié)點及其鄰居節(jié)點的度提出半局部中心性[11].介數(shù)中心性描述了節(jié)點對網(wǎng)絡所傳播信息流的控制能力，接近中心性描述了節(jié)點到達網(wǎng)絡其他節(jié)點的快慢程度，二者考慮了網(wǎng)絡的全局信息，但算法時間復雜度過高.特征向量中心性則以相鄰節(jié)點的重要度作為衡量某節(jié)點重要度的指標.基于隨機游走思想的關鍵節(jié)點識別算法主要包括PageRank算法[12]、LeaderRank算法[13]、HITS[14]等.PageRank算法假設節(jié)點具有相同的跳轉概率，將PageRank值平均分配給相鄰節(jié)點，存在排序結果不唯一的缺陷.LeaderRank算法很好地解決了上述問題，收斂性更好，魯棒性更強，但標準的LeaderRank算法不能直接應用于加權網(wǎng)絡[15].HITS算法采用節(jié)點的權威值和樞紐值綜合評價節(jié)點的重要性.此外，還有基于節(jié)點移除的算法和基于D-S證據(jù)理論[16]的算法等，但算法時間復雜度高，在非連通網(wǎng)絡中的識別效果不理想.

上述算法大多從網(wǎng)絡拓撲結構的角度衡量節(jié)點重要度，忽略了每個節(jié)點的自身特性[17，18]和節(jié)點之間的相互影響.但Fowler和Christakis提出的三度影響力原則認為節(jié)點既對其直接相連的鄰居節(jié)點產生直接影響，還對三度以內的鄰居節(jié)點產生間接影響[19].因此，本文采用節(jié)點的有向拓撲勢，綜合考慮節(jié)點的屬性以及節(jié)點與其近鄰節(jié)點之間的相互影響力，提出一個新的節(jié)點重要度指標—拓撲勢距離(Topological Potential Distance，TPD)，并將其應用于關鍵節(jié)點識別；進而提出了基于二維有向拓撲勢的用戶角色識別算法.在真實網(wǎng)絡中的對比實驗結果表明：與度中心性、介數(shù)中心性、接近中心性、PageRank、HITS等相比，拓撲勢距離能有效識別有向加權網(wǎng)絡中的關鍵節(jié)點，合理區(qū)分重要度相當?shù)墓?jié)點，并識別網(wǎng)絡中的用戶角色.

2 基本概念

2.1 節(jié)點拓撲勢

根據(jù)有源物理場的思想，網(wǎng)絡G=(V，E)可以看作一個包含n個節(jié)點及其相互作用的物理系統(tǒng)，每個節(jié)點周圍存在一個拓撲場，對場中的所有節(jié)點產生一定的拓撲勢，其拓撲勢值隨網(wǎng)絡距離的增長而快速衰減[20].基于數(shù)據(jù)場理論提出的節(jié)點拓撲勢，反映了節(jié)點受自身及其近鄰節(jié)點共同影響的程度.

定義1.無向拓撲勢.假設無向網(wǎng)絡拓撲為G=(V，E)，V={v1，v2，…，vn}為節(jié)點的非空有限集，E?V×V為邊的非空有限集，節(jié)點vi的拓撲勢為：

(1)

其中，N為網(wǎng)絡中的節(jié)點數(shù)|V|；mj≥0代表節(jié)點vj的質量，可映射為實際網(wǎng)絡中的固有屬性；dji表示節(jié)點vj到節(jié)點vi的最短路徑長度；σ為影響因子，用于控制節(jié)點的影響范圍，可根據(jù)節(jié)點拓撲勢熵進行優(yōu)選.

定義2.無向拓撲勢熵.給定無向網(wǎng)絡G=(V，E)及拓撲勢場，其拓撲勢熵為：

(2)

2.2 有向拓撲勢

定義3.有向拓撲勢.設有向加權網(wǎng)絡G=(V，E，W)，V為節(jié)點集，E為有向邊集，W為有向邊的權重集合，節(jié)點vi的入度拓撲勢φin(vi)和出度拓撲勢φout(vi)分別定義為：

(3)

(4)

其中，dwji為在有向邊的權重影響下節(jié)點間的最短距離，mj為節(jié)點vj的固有屬性.在實際網(wǎng)絡中，邊權重越大表明節(jié)點間的聯(lián)系越密切、距離越小.設節(jié)點vj到節(jié)點vi的最短路徑為e1→e2→…→em，dr為第r段的距離長度，wr為對應邊er的權重，則：

(5)

根據(jù)影響因子σ確定的影響范圍l不再針對節(jié)點間的跳數(shù)而是針對dwji，即dwji≤l的節(jié)點都在影響范圍之內.

在有向網(wǎng)絡中，節(jié)點vi的入度拓撲勢φin(vi)代表該節(jié)點受其他節(jié)點影響的程度，出度拓撲勢φout(vi)則反映了節(jié)點vi對其他近鄰節(jié)點的影響能力.

2.3 用戶角色

用戶角色是社交網(wǎng)絡中用戶行為和關系的劃分，即對用戶位置、用戶行為或虛擬身份的刻畫.如：在線社交網(wǎng)絡中的不同用戶擁有不同ID，每位用戶的參與方式、互動行為和語言風格等迥然不同，決定了該用戶的角色.本文把入度拓撲勢和出度拓撲勢作為用戶角色識別的關鍵特征，建立二維拓撲勢圖(橫坐標軸為入度拓撲勢，縱坐標軸為出度拓撲勢，如圖1所示)，定義4類用戶角色.①橋接用戶：具有較大的入度拓撲勢和出度拓撲勢，在網(wǎng)絡中具有承上啟下的關鍵作用，位于圖1的I區(qū)；②貢獻用戶：具有較大的出度拓撲勢，主動與其他用戶交互，對其近鄰用戶產生較大影響，位于圖1的II區(qū)；③接收用戶：具有較大的入度拓撲勢，通常是網(wǎng)絡中用戶交互行為的被動接收者，易受其他用戶的影響，位于圖1的III區(qū)；④普通用戶：出度拓撲勢和入度拓外勢均不顯著，位于圖1的IV區(qū).

圖1 二維拓撲勢圖Fig.1 2D topological potential distribution map

定義4.用戶角色分布向量.給定有向加權網(wǎng)絡G=(V，E，W)，節(jié)點vi從屬于4類角色的概率定義為角色分布向量Pi=，其中分量pik為角色從屬概率：

(6)

dik是節(jié)點vi到二維拓撲勢圖(如圖1所示)中4個頂點A(maxφin，maxφout)、B(minφin，maxφout)、C(maxφin，minφout)和D(minφin，minφout)的歐式距離，minφin，minφout，maxφin，maxφout分別為網(wǎng)絡中所有節(jié)點入度拓撲勢和出度拓撲勢的最小值和最大值.

在獲得節(jié)點vi的角色分布向量Pi=后，比較角色從屬概率pik的大小，選擇概率最大的角色作為節(jié)點vi的角色.

定義5.拓撲勢距離.在二維拓撲勢圖中，離頂點A距離越近的節(jié)點，在網(wǎng)絡中發(fā)揮的作用越大，因此定義節(jié)點vi的拓撲勢距離Ti為：

(7)

節(jié)點vi的拓撲勢距離越小，離頂點A越近，其重要度越高；反之，節(jié)點的重要度越低.

3 算 法

本文針對有向社交網(wǎng)絡，以入度拓撲勢和出度拓撲勢作為分析節(jié)點重要度及識別用戶角色的主要特征，提出節(jié)點重要度的度量指標——拓撲勢距離，根據(jù)節(jié)點的有向拓撲勢及局部影響力將節(jié)點劃分為4類角色.

3.1 基于有向拓撲勢的關鍵節(jié)點識別

算法1.基于有向拓撲勢的關鍵節(jié)點識別算法

輸入：網(wǎng)絡G=(V，E，W)，影響范圍的增量Δl

輸出：所有節(jié)點的拓撲勢距離T及排名

1.初始化，l=0；

2.計算網(wǎng)絡中所有節(jié)點對之間的最短距離，得到矩陣Q；

3.H=minH=log(N)；

4.whileH≤minHdo

5. minH=H；

6.l=l+Δl；

8. 根據(jù)l、σ分別計算所有節(jié)點的入度拓撲勢和出度拓撲勢；

9. 計算H，并保存l、σ和H；

10.endwhile

13.forvi∈Vdo

14. 計算節(jié)點vi的入度拓撲勢φin(vi)和出度拓撲勢φout(vi)；

15.endfor

16.forvi∈Vdo

17. 計算節(jié)點vi的拓撲勢距離Ti；

18.endfor

19.根據(jù)拓撲勢距離，對所有節(jié)點進行排序；

20.ReturnT、節(jié)點排名

3.2 基于二維拓撲勢的用戶角色識別

有向加權網(wǎng)絡中，用戶角色識別的基本思想為：計算節(jié)點vi的角色分布向量Pi=，其最大分量對應的角色就是節(jié)點vi的角色；根據(jù)各分量值的大小，判斷節(jié)點vi隸屬于該角色的程度.具體過程如算法2所示.

算法2.基于二維拓撲勢的用戶角色識別算法

輸入：網(wǎng)絡G=(V，E，W)中所有節(jié)點的入度拓撲勢φin和出度拓撲勢φout

輸出：所有節(jié)點的角色分布向量P及對應的角色

1.根據(jù)φin和φout的最大值和最小值，得到二維拓撲勢圖的4個頂點；

2.forvi∈Vdo

3. 計算節(jié)點vi到4個頂點的歐式距離dik；

4.endfor

5.forvi∈Vdo

6. 計算vi的角色分布向量Pi=；

7.endfor

8.獲得所有節(jié)點的所屬角色及其程度；

9.ReturnP、用戶角色及程度

4 實驗與分析

4.1 實驗數(shù)據(jù)

為了驗證拓撲勢距離在有向社交網(wǎng)絡的用戶角色識別和節(jié)點重要度評估的效果，本文針對3個不同規(guī)模、不同類型的真實網(wǎng)絡數(shù)據(jù)集Strike、Polblogs和豆瓣話題回復網(wǎng)絡設計對比實驗.

Strike是由24個節(jié)點和38條邊組成的有向網(wǎng)絡[21]，節(jié)點代表一家木材加工廠的工人，有向邊表示工人之間的聯(lián)系，邊權值均為1.Strike網(wǎng)絡描述了一場罷工運動中工人之間的溝通情況，說西班牙語的工人和說英語的工人之間的溝通較少；在說西班牙語的工人中，Alejandro最精通英語；Bob會講西班牙語，與Norm關系密切；Ozzie是Karl的父親.

Polblogs[22]是2004年美國大選期間美國政治博客之間的超鏈接形成的有向網(wǎng)絡(1490個節(jié)點和19090條有向邊)，以不同的政治博客為節(jié)點，每個節(jié)點具有1個表示其政治傾向的屬性(即民主黨或共和黨)；各博客之間的超鏈接為有向邊，邊權值均為1.主要拓撲參數(shù)為：平均度12.768、網(wǎng)絡直徑9、聚類系數(shù)0.172、平均路徑長度3.39.

豆瓣話題回復網(wǎng)絡來源于采用網(wǎng)絡爬蟲自主下載的豆瓣網(wǎng)人文經典閱讀小組2014年2月-2016年5月的話題回復數(shù)據(jù)，以用戶為節(jié)點、用戶之間的話題回復關系為有向邊、回復次數(shù)為邊權，構建而成的有向加權網(wǎng)絡(有6260個節(jié)點和16833條有向邊).主要拓撲參數(shù)為：平均度3.862、網(wǎng)絡直徑11、聚類系數(shù)0.113、平均路徑長度3.709.

4.2 用戶角色識別結果分析

選取7種經典的節(jié)點重要度指標：①中心性指標，包括加權度、介數(shù)中心性、接近中心性、特征向量中心性；②鏈接分析法，包括PageRank、HITS-Authority、HITS-Hub，實現(xiàn)拓撲勢距離與7項指標的對比分析.表1-表3分別列出了在3個真實網(wǎng)絡上不同方法得到的前10/15個重要節(jié)點，表中括號前數(shù)值為節(jié)點編號，括號內為對應方法計算所得的數(shù)值(即節(jié)點排序的依據(jù)).

表3 豆瓣話題回復網(wǎng)絡中節(jié)點重要度排序結果Table 3 Ranking results of user influence in DouBan reply network

4.2.1 Strike網(wǎng)絡的用戶角色識別結果

表1列出了Strike網(wǎng)絡在8項指標上的節(jié)點重要度排序結果，可以看出：拓撲勢距離排名前5的節(jié)點，被其他重要度指標認可；例如，拓撲勢距離排名第1的節(jié)點7(Bob)，被其余5項指標選為第1名；拓撲勢距離排名第2的節(jié)點12(Norm)，被其余4項指標選為第2名.與加權度、接近中心性、PageRank、HITS-Authority、HITS-Hub相比，拓撲勢距離的精度更高，如節(jié)點2、節(jié)點11、節(jié)點18和節(jié)點19的加權度值相同，并列第4，而拓撲勢距離無并列排名、區(qū)分度高.

表1 Strike網(wǎng)絡中節(jié)點重要度排序結果Table 1 Ranking results of user influence in Strike network

圖2是Strike網(wǎng)絡的二維拓撲勢圖，可以看出：節(jié)點7(Bob)和節(jié)點12(Norm)屬于“橋接用戶”，具有較大的入度拓撲勢和出度拓撲勢.其中，節(jié)點7(Bob)的有向拓撲勢最高，是罷工運動中的領導、核心；節(jié)點12(Norm)的入度拓撲勢和出度拓撲勢均不突出，但在圖2中能清晰表明該節(jié)點的重要程度.入度拓撲勢大、出度拓撲勢小的“接收用戶”，在網(wǎng)絡中人數(shù)最多，通常是聽從指揮的人員，例如節(jié)點15(Domingo)從不聯(lián)系別人、只有別人聯(lián)系他.僅出度拓撲勢相對較大的“貢獻用戶”，對其近鄰節(jié)點具有較大的影響力.入度拓撲勢和出度拓撲勢均較小的“普通用戶”，如節(jié)點21(Quint)，在罷工運動中的作用相對較小.入度拓撲勢或出度拓撲勢最小的節(jié)點，處于罷工網(wǎng)絡的邊緣，如節(jié)點1(Frank)、節(jié)點24(Wendle)等.

圖2 Strike網(wǎng)絡的二維拓撲勢圖Fig.2 2D topological potential distribution map of Strike network

根據(jù)Strike 網(wǎng)絡的用戶角色識別結果，得出結論：從二維拓撲勢圖中能有效識別4類用戶角色，進而判斷不同用戶在網(wǎng)絡中的作用；本文提出的拓撲勢距離能反映用戶的影響力(即節(jié)點重要性).

4.2.2 Polblogs網(wǎng)絡的用戶角色識別結果

表2列出了Polblogs網(wǎng)絡在8項指標上的節(jié)點重要度排序結果，可以看出：拓撲勢距離排名前5的節(jié)點，被其他重要度指標認可；例如，拓撲勢距離排名第1的節(jié)點855，被其余2項指標選為第1名；拓撲勢距離排名第3的節(jié)點55，被其余7項指標選為前10名.與介數(shù)中心性相比，拓撲勢距離的精度更高，如節(jié)點1000和節(jié)點1153的介數(shù)中心性相同，并列第12，而拓撲勢距離無并列排名、區(qū)分度高.

表2 Polblogs網(wǎng)絡中節(jié)點重要度排序結果Table 2 Ranking results of user influence in Polblogs network

圖3是Polblogs網(wǎng)絡的二維拓撲勢圖，可以看出：節(jié)點855屬于“橋接用戶”，具有較大的入度拓撲勢和最大的出度拓撲勢，是擁有超鏈接數(shù)最多的政治博客，屬于Polblogs網(wǎng)絡中承上啟下的核心節(jié)點.入度拓撲勢大、出度拓撲勢小的“接收用戶”有12個，出度拓撲勢大、入度拓撲勢小的“貢獻用戶”有9個，其中拓撲勢距離排名第2-15位的節(jié)點中有11個屬于典型的“接收用戶”或“貢獻用戶”.入度拓撲勢和出度拓撲勢均較小的“普通用戶”，在網(wǎng)絡中占比最大，其作用相對較小.

圖3 Polblogs網(wǎng)絡的二維拓撲勢圖Fig.3 2D topological potential distribution map of Polblogs network

4.2.3 豆瓣話題回復網(wǎng)絡的用戶角色識別結果

表3列出了豆瓣話題回復網(wǎng)絡在8項指標上的節(jié)點重要度排序結果，可以看出：入度拓撲勢和出度拓撲勢排名前5的節(jié)點，被其他重要度指標認可；例如，出度拓撲勢排名第1的節(jié)點3，被其余7項指標均列為第1名.與加權度、介數(shù)中心性、PageRank、HITS-Hub相比，拓撲勢距離的精度更高，如節(jié)點5776和節(jié)點3787的介數(shù)中心性相同，并列第11，而拓撲勢距離無并列排名、區(qū)分度高.

由豆瓣話題回復網(wǎng)絡的二維拓撲勢圖(如圖4所示)可以看出：網(wǎng)絡中絕大多數(shù)節(jié)點的入度拓撲勢和出度拓撲勢均較小，約98.43%的用戶屬于“普通用戶”.節(jié)點3、節(jié)點523和節(jié)點1784是“橋接用戶”；其中，節(jié)點3是管理員，經常發(fā)表新話題和回復別人的話題，共發(fā)表1116個新話題，回復1775個話題；節(jié)點523和節(jié)點1784各發(fā)表了198個、101個新話題，經常回復其他用戶的話題，在網(wǎng)絡中活躍程度較高，與其他用戶互動頻繁，具有相對較大的入度拓撲勢和出度拓撲勢，雖然有向拓撲勢排名不突出，但在網(wǎng)絡中具有重要的橋接作用.35個“貢獻用戶”的出度拓撲勢較高，在網(wǎng)絡中屬于經常回復話題的用戶；例如節(jié)點1714是管理員，回復的話題數(shù)較多，沒有發(fā)表過新話題.60個“接收用戶”的入度拓撲勢較高；其中，節(jié)點925的入度拓撲勢最高，發(fā)表131個新話題并被其他用戶多次回復，但只回復過2個話題；節(jié)點1939是組長，其入度拓撲勢高于出度拓撲勢，發(fā)表85個新話題，回復30個話題；節(jié)點364、節(jié)點1828是管理員，經常發(fā)表新話題并被其他用戶多次回復，但很少回復其他用戶的話題.

圖4 豆瓣話題回復網(wǎng)絡的二維拓撲勢圖Fig.4 2D topological potential distribution map of DouBan reply network

結合實際數(shù)據(jù)背景，進一步分析：本文提出的用戶角色識別模型找出了豆瓣話題回復網(wǎng)絡中1.57%的重要成員，其中包括1名組長和8名管理員.管理員在豆瓣話題小組中的作用很多，如管理版務、引導話題導向、貢獻原創(chuàng)資源、調節(jié)紛爭等.1.57%的重要成員中有些用戶是豆瓣話題小組中的普通成員，但卻是領袖人物或某領域的專家，其“發(fā)帖數(shù)”、“回復帖數(shù)”、“被回復帖數(shù)”、“參與話題數(shù)”等均高于平均水平，體現(xiàn)了他們在論壇中的活躍程度，表明他們是論壇中的代表性用戶.

綜上所述，結論如下：拓撲勢距離越小的節(jié)點，與二維拓撲勢圖的頂點A(maxφin，maxφout)距離越近，在網(wǎng)絡中發(fā)揮的作用越大，如Strike網(wǎng)絡中的節(jié)點7是罷工運動中的領導、核心，Polblogs網(wǎng)絡中的節(jié)點855是擁有超鏈接數(shù)最多的政治博客，豆瓣話題回復網(wǎng)絡中的節(jié)點3是管理員.入度拓撲勢或出度拓撲勢最小的節(jié)點，處于網(wǎng)絡的邊緣.拓撲勢距離在節(jié)點重要度評估上的區(qū)分度最好，主要體現(xiàn)在表1-表3中僅有拓撲勢距離指標沒有出現(xiàn)并列排名的情況，其區(qū)分度明顯優(yōu)于其他7項指標.從計算復雜度來看，拓撲勢距離比加權度高，比介數(shù)中心性低，與其他5項指標基本相當.

4.3 拓撲勢距離與其他節(jié)點重要度指標間的關系

拓撲勢距離能實現(xiàn)對有向加權社交網(wǎng)絡的所有用戶進行重要性評價，拓撲勢距離值越小的用戶越重要、排名越靠前.為驗證拓撲勢距離識別有向加權社交網(wǎng)絡中關鍵節(jié)點的合理性，分別對3個真實網(wǎng)絡數(shù)據(jù)集中節(jié)點的加權度、介數(shù)中心性、接近中心性、特征向量中心性、PageRank值、HITS-Authority值、HITS-Hub值和拓撲勢距離進行相關分析，如圖5所示.

在統(tǒng)計學中，Kendall等級相關系數(shù)τ[23]常用于度量兩種排序結果相關性的強弱.τ的取值范圍為[-1，1]，τ=1表明兩種排序的等級相關性一致，τ=-1表明兩種排序的等級相關性完全相反；τ=0表明兩種排序相互獨立.Kendall等級相關系數(shù)τ有三種計算方式：τA、τB和τC.由于不同社交網(wǎng)絡用戶可能擁有相同的拓撲勢距離值或中心性指標值(即等級相同)，本文采用τB度量拓撲勢距離與其他7項指標排序結果的相關性強弱，結果見表4.

表4 拓撲勢距離與7項指標之間的τBTable 4 τB between topological potential distance and 7 indexes

假設兩個n維隨機變量X、Y的第i(1≤i≤n)個元素分別表示為Xi、Yi，X和Y對應元素組成的元素對集合為XY.當XY中任意兩個元素(Xi，Yi)與(Xj，Yj)的排名相同，即滿足Xi>Xj且Yi>Yj或滿足XiXj且YiYj時，認為二者不一致.當出現(xiàn)Xi=Xj或Yi=Yj時，認為二者既非一致也非不一致.定義τB如下：

(8)

圖5是拓撲勢距離與7項指標(加權度、介數(shù)中心性、接近中心性、特征向量中心性、PageRank、HITS-Authority、HITS-Hub)分別在Strike、Polblogs和豆瓣話題回復網(wǎng)絡中用戶重要

圖5 拓撲勢距離與7項指標的關系圖Fig.5 Relation between topological potential distance and 7 indexes

性排序間的關系圖，顯然拓撲勢距離與7項指標均呈現(xiàn)明顯的負相關性.使用τB度量拓撲勢距離與7項指標排序結果的相關性，見表4.在Polblogs網(wǎng)絡和豆瓣話題回復網(wǎng)絡中，拓撲勢距離與7項指標間具有顯著性水平0.01的強負相關性；在Strike網(wǎng)絡中，拓撲勢距離與特征向量中心性、HITS-Authority間具有顯著性水平0.05的強負相關性，與其他5項指標間具有顯著性水平0.01的強負相關性.表明拓撲勢距離在3個有向社交網(wǎng)絡中識別出的關鍵節(jié)點具有合理性.

4.4 節(jié)點重要度評估結果分析

4.4.1 評價標準

基于網(wǎng)絡魯棒性與脆弱性分析，評估節(jié)點重要度排序算法.采用極大連通系數(shù)G與網(wǎng)絡效率下降比例μ作為評估指標，計算移除特定用戶前后網(wǎng)絡結構的變化，進而評價相對應節(jié)點的結構重要性.

根據(jù)節(jié)點重要度排序算法的結果，按順序對所有節(jié)點排序，移除一部分重要節(jié)點，計算網(wǎng)絡的極大連通系數(shù)G，并判斷移除節(jié)點后網(wǎng)絡極大連通子集[24]的變化.

G=R/N

(9)

其中，N為網(wǎng)絡的節(jié)點總數(shù)，R為移除一部分重要節(jié)點后極大連通子集的節(jié)點數(shù).極大連通系數(shù)G∈[0，1]；G取值越大，表明網(wǎng)絡的拓撲連接越強；隨著節(jié)點的刪除，極大連通子集的規(guī)模逐漸變小，極大連通系數(shù)G隨之減小，網(wǎng)絡的拓撲連接減弱；G變小的趨勢越明顯，攻擊網(wǎng)絡的效果越好；當G=0時，網(wǎng)絡中將不存在極大連通子集.

網(wǎng)絡效率E[25]定義為：

(10)

其中，εij=1/dij，dij為節(jié)點vi和節(jié)點vj之間的最短路徑，N為網(wǎng)絡的節(jié)點總數(shù).網(wǎng)絡效率E能有效度量網(wǎng)絡的連通性，E取值越大，表明網(wǎng)絡的連通性越強；當移除特定節(jié)點時，網(wǎng)絡中有些路徑被中斷，某些節(jié)點對之間的最短路徑變大，導致網(wǎng)絡的平均路徑長度增大，網(wǎng)絡的連通性變弱；E下降的趨勢越明顯，表明模擬攻擊的效果越好.

網(wǎng)絡效率下降比例μ為：

μ=1-E/E0

(11)

其中，E為節(jié)點移除后的網(wǎng)絡效率，E0為原始網(wǎng)絡的網(wǎng)絡效率.μ∈[0，1]，μ取值越大，表明移除節(jié)點后的網(wǎng)絡效率越差.本文通過刪除網(wǎng)絡中的特定重要節(jié)點，計算遭受攻擊前后的網(wǎng)絡效率下降比例，并以此衡量各節(jié)點的重要度.

4.4.2 動態(tài)攻擊結果

針對3個真實網(wǎng)絡，根據(jù)拓撲勢距離、加權度、介數(shù)中心性、接近中心性、特征向量中心性、PageRank、HITS-Authority、HITS-Hub的排序結果，分別刪除網(wǎng)絡中一定比例排序靠前的節(jié)點，模擬網(wǎng)絡遭受動態(tài)攻擊時極大連通系數(shù)G與網(wǎng)絡效率下降比例μ的變化(如圖6、圖7所示)，進而評價節(jié)點重要度指標的準確性.當網(wǎng)絡遭受動態(tài)攻擊時，由于移除節(jié)點后網(wǎng)絡拓撲結構發(fā)生變化，因此必須重新計算各個節(jié)點的8項指標值并排序，然后按照節(jié)點的重要度依次刪除節(jié)點.

圖6 利用不同指標動態(tài)刪除一定比例排序靠前的節(jié)點后極大連通系數(shù)G的變化Fig.6 Relation between relative size of giant component G and a certain proportion of key nodes dynamically removed from networks

圖7 利用不同指標動態(tài)刪除一定比例排序靠前的節(jié)點后網(wǎng)絡效率下降比例μ的變化Fig.7 Relation between decline rate of network efficiency μ and a certain proportion of key nodes dynamically removed from networks

如圖6所示，動態(tài)刪除3個網(wǎng)絡中排序靠前的節(jié)點時，拓撲勢距離指標導致網(wǎng)絡極大連通系數(shù)G變小的趨勢最明顯.尤其在豆瓣話題回復網(wǎng)絡(圖6(c))中，拓撲勢距離指標在動態(tài)攻擊的初始階段表現(xiàn)出比其他7項指標更好的攻擊效果，在整個模擬動態(tài)攻擊過程中對網(wǎng)絡結構的破壞性最強；而HITS-Hub指標的動態(tài)攻擊效果最差，曲線中出現(xiàn)網(wǎng)絡極大連通系數(shù)G不隨節(jié)點移除而下降的情況.在Strike網(wǎng)絡(圖6(a))和Polblogs網(wǎng)絡(圖6(b))中，雖然拓撲勢距離指標在動態(tài)攻擊的初始階段表現(xiàn)稍差，但當分別選擇性刪除排名前16%和9%以上的節(jié)點時，拓撲勢距離指標使得網(wǎng)絡極大連通系數(shù)G最小，動態(tài)攻擊最突出.

由圖7(a)可知，在Strike網(wǎng)絡中，采用拓撲勢距離指標刪除排序靠前的節(jié)點導致網(wǎng)絡效率下降比例μ最大，網(wǎng)絡碎片化效果最突出，動態(tài)攻擊效果最佳，當動態(tài)刪除到第14個節(jié)點時μ為最大值1；采用特征向量中心性、PageRank、HITS-Authority、HITS-Hub等指標動態(tài)刪除節(jié)點時，出現(xiàn)了網(wǎng)絡效率下降比例μ局部下降的情況，表明這些指標排名靠前的節(jié)點并不是當前網(wǎng)絡的核心節(jié)點，難以有效評價Strike網(wǎng)絡的節(jié)點重要度.由圖7(b)可知，在Polblogs網(wǎng)絡中，選擇性刪除8項指標中前9%的節(jié)點時，介數(shù)中心性指標對網(wǎng)絡的破壞效果略優(yōu)于拓撲勢距離；但選擇性刪除前10%以上節(jié)點時，拓撲勢距離指標使網(wǎng)絡效率E下降的幅度最大，對網(wǎng)絡的瓦解效果最明顯.由圖7(c)可知，采用8項指標動態(tài)攻擊豆瓣話題回復網(wǎng)絡時，拓撲勢距離指標使網(wǎng)絡效率下降比例μ最大，刪除排序靠前的節(jié)點后導致網(wǎng)絡的連通性最差；HITS-Hub指標的動態(tài)攻擊效果最差，曲線中出現(xiàn)了網(wǎng)絡效率下降比例μ不隨節(jié)點移除而上升的情況，表明這些HITS-Hub排名靠前的節(jié)點不是當前網(wǎng)絡的核心節(jié)點，難以有效衡量豆瓣話題回復網(wǎng)絡的節(jié)點重要性.

綜合來看，移除重要節(jié)點后網(wǎng)絡的連通性越差，極大連通系數(shù)G變小的趨勢越突出，網(wǎng)絡效率E的下降趨勢越明顯，網(wǎng)絡效率下降比例μ的上升趨勢越顯著.在3個真實有向社交網(wǎng)絡中，與其他7項指標相比，拓撲勢距離度量節(jié)點重要度的效果最好、最穩(wěn)定，沒有出現(xiàn)隨著節(jié)點刪除比例的增加網(wǎng)絡效率下降比例μ下降的現(xiàn)象.

5 結 論

關鍵節(jié)點識別是社交網(wǎng)絡研究中的重要研究問題之一，對研究社交網(wǎng)絡的結構和功能、分析用戶之間的交互過程、預測用戶行為、監(jiān)測網(wǎng)絡輿情等具有重要意義.通過用戶角色辨識網(wǎng)絡中的關鍵用戶有助于改進網(wǎng)絡防護策略，提升高影響力用戶的安全防護能力，進而提高網(wǎng)絡拓撲結構的穩(wěn)定性.本文針對有向社交網(wǎng)絡中節(jié)點重要度分析和用戶角色發(fā)現(xiàn)，提出一個新的節(jié)點重要度指標——拓撲勢距離，能有效辨識網(wǎng)絡中的關鍵節(jié)點；提出一種基于二維有向拓撲勢的用戶角色識別模型，根據(jù)節(jié)點的有向拓撲勢及局部影響力劃分4類用戶角色.真實社交網(wǎng)絡的對比實驗結果表明：二維有向拓撲勢圖能清晰直觀地刻畫有向加權社交網(wǎng)絡中的4類用戶角色，拓撲勢距離越小的用戶在網(wǎng)絡中發(fā)揮的作用越大；拓撲勢距離與7項節(jié)點重要度指標(加權度、介數(shù)中心性、接近中心性、特征向量中心性、PageRank、HITS-Authority、HITS-Hub)間具有明顯的強負相關性；與7項指標相比，拓撲勢距離在節(jié)點重要度評估上的區(qū)分度最好，當網(wǎng)絡遭受動態(tài)攻擊時，拓撲勢距離使網(wǎng)絡碎片化程度最高、動態(tài)攻擊效果最好.下一步工作將拓展本文模型至動態(tài)網(wǎng)絡中，致力于動態(tài)網(wǎng)絡的關鍵節(jié)點識別和演化研究.