復雜社會網絡節點重要性可拓聚類動態分析方法

嚴家萌 龐超逸 許立波*

1(浙江大學工程師學院 浙江 杭州 310015)2(浙江大學寧波理工學院計算機與數據工程學院 浙江 寧波 315100)

0 引 言

隨著信息化網絡化走向縱深領域，對復雜網絡[1]的研究越來越顯現其巨大的實用價值。在人類活動的參與下，網絡表現為社會化，相比于其他類型網絡，社會網絡體現出更接近現實的復雜度，且往往要求對關鍵和核心節點的認定。比如，交通擁堵路口識別，疾病傳播關鍵節點發現，國際環境中的大國影響力等，都離不開對影響力節點的刻畫。發現復雜網絡中的關鍵節點，有針對性的有效利用有著重要意義。在對復雜社會網絡節點重要性度量時，應該考慮時間和空間兩個維度，即此時此刻和某時某刻。而當前，對復雜網絡的研究大都是建立在靜態基礎之上的，缺乏動態分析和考量。在復雜網絡節點重要性背景下，無論是綜合考慮節點連接度和經過該節點最短路徑數的節點收縮法[2]，還是借鑒排名算法的有向加權評估方法[3]，亦或是評價網絡中每個節點與“核心節點”的關聯度的定量評估法[4]，以及通過計算多重屬性到理想的接近程度的綜合評價指標[5]等，基本上都是靜態分析方法。

在國外，復雜網絡節點重要性中心性指標用來對節點的傳播影響力進行刻畫，主要有度中心性(Degree Centrality)[6]、介數中心性(Betweenness Centrality)[7]、緊密度指標(Closeness Centrality)[8]、K-Shell(KS指標)[9]等。文獻[10]利用度中心性來度量節點的影響力，節點度描述了節點間的直接通信能力，直觀反映節點的重要性，度表示為與節點直接相連的個數，在復雜社會網絡中度數較大的節點的傳播影響力相對較大。文獻[11]利用介數中心性來衡量社會網絡節點重要性，刻畫了復雜網絡中節點對于信息流動的影響力，以其經過某個節點的最短路徑的數目來描述節點的重要性，網絡節點介數定義為經過節點的路徑數目占最短路徑總數的比例。介數中心性認為，在復雜網絡中如果一個節點是其他節點對之間聯通的必經之路，則其在網絡中具有重要地位，相應的影響力也就越大。文獻[12-13]利用緊密度指標刻畫某個節點到其他節點的難易程度，用其到網絡中其他所有節點距離之和的倒數來刻畫，節點的緊密度值越大，表明該節點越居于網絡中心位置，相應地也就越重要。文獻[14-15]提出通過K-shell(KS)分解來確定最具有影響力的單源節點，操作上相當于剝去了最外面一層殼。首先去除網絡中度數小于k的所有節點及其連邊，如果在剩下的節點中仍有度值小于k的節點，那么就繼續去除這些節點，直至網絡中剩下的節點的度值不小k，依此類推，直到復雜社會網絡中所有的節點都被賦予KS值。

總體來看，目前大多數研究對復雜網絡節點重要性度量時的方法均是靜態的，能很好地闡釋復雜網絡節點內部相互連接的邏輯，區分重要性程度。然而，對變化了的節點重要度如何度量缺乏研究，更沒有給出變化的量。本文意在嘗試提出一種新的基于可拓聚類的節點重要性動態分析方法。

1 可拓聚類方法說明

1.1 變量說明

對文中所涉及主要變量作如下定義和說明。

Dc為度中心性Cc為緊密度中心性pij為標準化后的屬性值λj為屬性權重Ti為時點K(i)為綜合關聯度Bc為介數中心性qij節點原始屬性值dr為第r個等級ui為節點屬性k(pij)為關聯度為r等級的取值區間

1.2 引入可拓學

可拓學[16]是通過定性和定量相結合的手段去處理矛盾問題的新興學科，其中可拓集理論是研究事物動態性和可變性的有力工具。楊國為等[17]利用可拓模式識別建立起神經網絡模型，推出模式可拓識別分類器。Xu等[18]提出可拓關聯結合后悔理論，應用于決策分析領域。周玉等[19]對可拓神經網絡的基本思想、算法思路、應用研究進行了系統分析，并提出了有待進一步研究的方向和問題。而將可拓聚類分析方法應用于復雜網絡節點重要性方面尚未見到。本文試圖將可拓集理論引入復雜網絡節點影響力研究領域，提出一種基于可拓聚類的復雜網絡節點重要性動態分析方法。將復雜網絡節點重要性加上時間維度，引入可拓關聯函數分析關聯度變化，從而判斷變化方向，給出變化的量。

1.3 節點重要性多屬性值

在社會網絡中，可用圖模式量化，用圖中節點表示個體，用邊表示各個體之間的連接關系?？稍O復雜社會網絡G=(V,E)是一個無向無權圖，其中V={v1,v2,…，vn}是網絡中所有節點的集合，|V|=n;E={e1,e2,…,em}是節點間邊的集合，|E|=m,aij=1，其中aij=1表示節點i和節點j相連，否則aij=0，如圖1所示。

圖1 根據社會網絡人員熟識如否模擬復雜網絡圖(節點1為例)

度中心性用Dc表示為：

Dc=d(v)

(1)

式中：d為節點v的度，即直接相連的邊數。

節點的介數Bc為：

(2)

式中：Sjk表示源節點j到目標節點k的最短路徑數；Sjk(i)表示節點j和k之間經過節點i的最短路徑數。

緊密度中性具體Cc表示為:

(3)

式中：dij表示以節點i為起點,以j為終點的最短路徑中所含邊的數量；N為節點總數。

在評估復雜網絡各節點重要性時，為了克服單一屬性的片面性，本文采用多屬性(即度中心性、介數中心性、緊密度中心性和KS指標)綜合考量，在計算完每個節點在對應屬性上的關聯度后，取綜合關聯度為該節點重要性的最終量值。

多屬性分析方法要求對屬性值進行標準化，每個節點在對應的屬性上的取值規范化為：

(4)

式中：qij為第i個節點第j個屬性值；pij為規范化后第i節點第j個屬性值。

2 可拓聚類模型

2.1 模型經典域及節域設置

以網絡節點O為對象，ci為節點各屬性特征，O關于ci的量值vi構成的有序三元組M=(O,ci,vi)作為描述節點重要性的基元；而網絡節點O的n個特征屬性c1,c2,…,cn及O關于ci(i=1,2,…,n)對應的量值vi(i=1,2,…,n)所構成的矩陣M1稱為n維物元[20]。

(5)

根據論域U中一個對象對于某特征的量值符合要求的程度，可分為滿意區間X0=和可接受區間X=，即經典域和節域，顯然X0?X。

(6)

式中：O表示網絡節點，dr(r=1,2,…,n)表示對應的第r個等級；(r=1,2,…,n)表示節點O對應等級特征的量值范圍。相應地，有表示節點O對應等級特征的節域。

2.2 關聯函數

定義可拓距[21]為某節點與經典域節域區間的距離。給定區間X0=，當最優點x0在右側(最優點在x0=b處)，則x與區間X0關于x0的右側距為：

(7)

反映各節點重要性與各經典域的隸屬程度的函數為關聯函數[22]。設區間X0=，X=且X0?X，則x關于x0及區間X0和X的關聯函數為(文中x即為屬性值pij)：

(8)

式中：ρ(x,x0,X)為可拓距；D(x,x0,X0,X)稱為位值，用來描述點x關于x0與X0和X組成的區間套的位置關系。

2.3 熵權及綜合關聯度

在度量節點重要性綜合關聯度時，將根據每個屬性的不同重要程度取合理的權系數計算得到。在復雜社會網絡中，節點綜合關聯度有整體變化的趨勢，因此利用等權值并不合適。根據網絡節點不同屬性的變化程度來設置不同的權值將更具可靠性。而熵權是根據特征參數值變化程度所反映的信息量大小來確定權值的客觀賦權法。計算各節點的熵值ej：

(9)

計算各節點的熵權λj：

(10)

所有權值向量λ滿足：

(11)

最后根據各屬性關聯度及熵權系數計算每個節點的綜合關聯度：

(12)

式中：i為節點序號；j為屬性序號；n為節點數；m為屬性數量。

2.4 知識發現

可拓集理論可用來描述復雜網絡節點重要性動態變化趨勢和方向。定義當T=(TK,TU)=(e,e)時，根據關聯函數值把論域分為標準正域、負域和零界，即有表達式：V+={u|u∈U,k(u)>0}，V-={u|u∈U,k(u)<0}，V0={u|u∈U,k(u)=0}。當T=TK,TU≠(e,e)時，把論域U劃分為關于變換T的正質變、負質變、正量變、負量變域和拓界，可分別形式化表示為：

V.+(T)={u|u∈U,y=k(u)≤0;Tu(u)∈U,y′=Tkk(Tuu)>0}

(13)

V.-(T)={u|u∈U,y=k(u)≥0;Tu(u)∈U,y′=Tkk(Tuu)<0}

(14)

V+(T)={u|u∈U,y=k(u)>0;Tu(u)∈U,y′=Tkk(Tuu)>0}

(15)

V-(T)={u|u∈U,y=k(u)<0;Tu(u)∈U,y′=Tkk(Tuu)<0}

(16)

V0(T)={u|u∈U;Tu(u)∈U,y′=Tkk(Tuu)=0}

(17)

3 實驗與分析

3.1 算法流程

對于給定的復雜社會網絡，可拓聚類算法首先分析節點的多重屬性并計算其重要性。然后按照實際需求劃分為不同的等級，統計每個等級的取值范圍及其在全體數據中的取值范圍分別構成經典域和節域。通過關聯函數計算每個節點關于對應等級的關聯度。利用熵權值取綜合關聯度。最后比較不同時間點每個節點綜合關聯度變化，計算關聯差，給出等級變動。利用這種形式化模型刻畫復雜社會網絡，根據關聯函數定量分析各個節點隸屬于某區間的范圍，并在不同時間點上給出動態變動。

3.2 節點重要性多屬性值

實驗數據來自Freeman觀測的由美國國家科學基金會贊助的計算機會議的參加者構成的社會網絡，該網絡呈現出復雜網絡的基本特征。會議的參加者都是社會網絡研究領域從事新興學科專業研究的研究者，選取其中32個人構成的網絡數據，通過熟識與否來定義網絡的邊取值，并在兩個時間點上進行了測量，兩個時間點距離9個月。

根據該網絡圖測量節點的多重重要性屬性，分別計算基于度中心性u1、介數中心性u2、緊密度u3以及K-shell分解值u4的影響力重要性量值。標準化后得到如表1、表2所示的量值矩陣。

表1 第一時點多屬性節點重要性指標

表2 第二時點多屬性節點重要性指標

3.3 等級劃分及經典域節域

節點重要性度量后，在每個屬性上取前25%組成高影響力等級節點的經典域X0，取全部屬性上的范圍為節域X，如表3、表4所示。隨著節點間的相互熟悉程度的提升，會出現屬性值整體提高的可能，因此，在取經典域節域時在兩個時點上分別取值，各自考察其高影響力等級節點的變化。此處的屬性都是越大越好的效益型屬性，最優點在經典域的最大值處取得，即右側距中x0=b處。

表4 第二時點各個屬性高影響力經典域及節域

3.4 關聯度及熵權

結果如表5、表6所示。

表5 第一時點各屬性節點重要性關聯度

表6 第二時點各屬性節點重要性關聯度

續表6

根據式(9)和式(10)計算各個屬性熵權值(如表7所示)。

表7 各屬性不同時點熵權值

3.5 綜合關聯度及關聯差

綜合關聯度的變化反映了節點重要性的變化，根據式(12)，計算其前后兩個時間節點T1、T2的綜合關聯度K(i)和關聯差Sumi，數據結果如表8所示。

表8 節點重要性綜合關聯度及關聯差

在這里，不僅能看到節點重要性變化方向，而且給出了變動的量。在趨勢一欄里，節點重要性有所下降則其符號為負，相應地，節點重要性有所提高則符號為正。比較第一時點與第二時點綜合關聯度，如果符號相同則為量變，符號不同則為質變。更具體地，如果第一時點符號為負第二時點為正則等級提升，該節點變為高影響力節點。相反，如果第一時點符號為正第二時點為負則等級下降，該節點變為非高影響力節點。例如，節點2的綜合關聯度由負號變為正號，說明其重要性等級一定有所提升，由非高影響力節點轉變為高影響力節點，發生了質變，即“正質變”，且其變化量是0.09。

將各節點重要性可視化表示如圖2所示，利用坐標系能直觀反映各節點重要性變化方向，變動量則為其差值?？梢?，零值以上部分對應著前25%高影響力等級節點，在第二時點有部分節點由高影響力節點轉變為非高影響力節點，也有部分節點由非高影響力節點轉變為高影響力節點，還有部分節點只有同一等級內的量變。

圖2 各節點在不同時點的綜合關聯度變化

4 算法比較

假設共有N個節點，r個類別等級，各節點有m個特征，則K均值算法針對每一個特征首先選取k個樣本節點，然后計算每個節點與各個樣本節點聚類中心的距離，時間復雜度為O(N×k)，共m個特征，則總復雜度為O(N×k×m)。而DBSCAN密度聚類算法，針對每一個特征，首先隨機選取一個節點，然后檢查其領域半徑內是否達到密度要求，若是則新建聚類，把所有點加入候選集，在候選集中對沒處理過的對象繼續檢查其領域，如此往復，時間復雜度為O(N×m)。而可拓聚類算法將每個特征上的節點重要性劃分為r個類別等級，時間復雜度均為O(m×r)。由于N?r，所以可拓聚類時間復雜度較低。當然，可拓聚類中的等級個數主要是由根據實際問題或者經驗知識劃分得到，粒度相對較粗，但可拓聚類的特點在于能夠描述網絡節點影響力在動態變化下的量變和趨勢，其他的聚類算法則不具備。

5 結 語

復雜網絡往往具有多對多的復雜關系，對復雜網絡的把握有利于掌握輿論熱點和對關鍵的認定。而對復雜社會網絡節點重要性動態觀測，從變化的視角審視網絡，本文給出了可拓聚類分析方法。該方法根據多屬性計算節點重要性，首先通過聚類分析劃分節點重要性等級，構造經典域和節域。然后根據關聯函數計算節點與對應等級關聯度，進而計算綜合關聯度，最后分析不同時點的變化量。通過可拓聚類方法實現對節點重要性變化的動態把握，使網絡節點及各指標均能以形式化的模型更直觀地展現。該方法不僅能判別節點重要性的變化方向，而且給出了變化的量。接下來工作包括：(1) 對可拓聚類預測方法在更大數據集中的預測效果作進一步探索；(2) 在節點重要性劃分等級時嘗試利用其他方法，而不是根據需要主觀劃分；(3) 在一個有向帶權網絡圖上利用該方法，驗證是否具有相同結果等。