嚴家萌 龐超逸 許立波*

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

0 引 言

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

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

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

1 可拓聚類方法說明

1.1 變量說明

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

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

1.2 引入可拓學

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

1.3 節(jié)點重要性多屬性值

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

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

度中心性用Dc表示為：

Dc=d(v)

(1)

式中：d為節(jié)點v的度，即直接相連的邊數(shù)。

節(jié)點的介數(shù)Bc為：

(2)

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

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

(3)

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

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

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

(4)

式中：qij為第i個節(jié)點第j個屬性值；pij為規(guī)范化后第i節(jié)點第j個屬性值。

2 可拓聚類模型

2.1 模型經典域及節(jié)域設置

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

(5)

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

(6)

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

2.2 關聯(lián)函數(shù)

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

(7)

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

(8)

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

2.3 熵權及綜合關聯(lián)度

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

(9)

計算各節(jié)點的熵權λj：

(10)

所有權值向量λ滿足：

(11)

最后根據(jù)各屬性關聯(lián)度及熵權系數(shù)計算每個節(jié)點的綜合關聯(lián)度：

(12)

式中：i為節(jié)點序號；j為屬性序號；n為節(jié)點數(shù)；m為屬性數(shù)量。

2.4 知識發(fā)現(xiàn)

可拓集理論可用來描述復雜網絡節(jié)點重要性動態(tài)變化趨勢和方向。定義當T=(TK,TU)=(e,e)時，根據(jù)關聯(lián)函數(shù)值把論域分為標準正域、負域和零界，即有表達式：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 算法流程

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

3.2 節(jié)點重要性多屬性值

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

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

表1 第一時點多屬性節(jié)點重要性指標

表2 第二時點多屬性節(jié)點重要性指標

3.3 等級劃分及經典域節(jié)域

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

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

3.4 關聯(lián)度及熵權

結果如表5、表6所示。

表5 第一時點各屬性節(jié)點重要性關聯(lián)度

表6 第二時點各屬性節(jié)點重要性關聯(lián)度

續(xù)表6

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

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

3.5 綜合關聯(lián)度及關聯(lián)差

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

表8 節(jié)點重要性綜合關聯(lián)度及關聯(lián)差

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

將各節(jié)點重要性可視化表示如圖2所示，利用坐標系能直觀反映各節(jié)點重要性變化方向，變動量則為其差值?？梢姡阒狄陨喜糠謱?5%高影響力等級節(jié)點，在第二時點有部分節(jié)點由高影響力節(jié)點轉變?yōu)榉歉哂绊懥?jié)點，也有部分節(jié)點由非高影響力節(jié)點轉變?yōu)楦哂绊懥?jié)點，還有部分節(jié)點只有同一等級內的量變。

圖2 各節(jié)點在不同時點的綜合關聯(lián)度變化

4 算法比較

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

5 結 語

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