融合拓撲勢的有向社交網絡關鍵節點識別模型

李 慧

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

1 引 言

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

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

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

2 基本概念

2.1 節點拓撲勢

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

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

(1)

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

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

(2)

2.2 有向拓撲勢

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

(3)

(4)

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

(5)

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

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

2.3 用戶角色

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

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

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

(6)

dik是節點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分別為網絡中所有節點入度拓撲勢和出度拓撲勢的最小值和最大值.

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

定義5.拓撲勢距離.在二維拓撲勢圖中，離頂點A距離越近的節點，在網絡中發揮的作用越大，因此定義節點vi的拓撲勢距離Ti為：

(7)

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

3 算 法

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

3.1 基于有向拓撲勢的關鍵節點識別

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

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

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

1.初始化，l=0；

2.計算網絡中所有節點對之間的最短距離，得到矩陣Q；

3.H=minH=log(N)；

4.whileH≤minHdo

5. minH=H；

6.l=l+Δl；

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

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

10.endwhile

13.forvi∈Vdo

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

15.endfor

16.forvi∈Vdo

17. 計算節點vi的拓撲勢距離Ti；

18.endfor

19.根據拓撲勢距離，對所有節點進行排序；

20.ReturnT、節點排名

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

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

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

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

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

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

2.forvi∈Vdo

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

4.endfor

5.forvi∈Vdo

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

7.endfor

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

9.ReturnP、用戶角色及程度

4 實驗與分析

4.1 實驗數據

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

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

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

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

4.2 用戶角色識別結果分析

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

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

4.2.1 Strike網絡的用戶角色識別結果

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

表1 Strike網絡中節點重要度排序結果Table 1 Ranking results of user influence in Strike network

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

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

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

4.2.2 Polblogs網絡的用戶角色識別結果

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

表2 Polblogs網絡中節點重要度排序結果Table 2 Ranking results of user influence in Polblogs network

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

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

4.2.3 豆瓣話題回復網絡的用戶角色識別結果

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

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

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

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

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

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

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

在統計學中，Kendall等級相關系數τ[23]常用于度量兩種排序結果相關性的強弱.τ的取值范圍為[-1，1]，τ=1表明兩種排序的等級相關性一致，τ=-1表明兩種排序的等級相關性完全相反；τ=0表明兩種排序相互獨立.Kendall等級相關系數τ有三種計算方式：τA、τB和τC.由于不同社交網絡用戶可能擁有相同的拓撲勢距離值或中心性指標值(即等級相同)，本文采用τ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=Xj或Yi=Yj時，認為二者既非一致也非不一致.定義τB如下：

(8)

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

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

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

4.4 節點重要度評估結果分析

4.4.1 評價標準

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

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

G=R/N

(9)

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

網絡效率E[25]定義為：

(10)

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

網絡效率下降比例μ為：

μ=1-E/E0

(11)

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

4.4.2 動態攻擊結果

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

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

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

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

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

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

5 結 論

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