復(fù)雜社會網(wǎng)絡(luò)節(jié)點重要性可拓聚類動態(tài)分析方法

嚴家萌 龐超逸 許立波*

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

0 引 言

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

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

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

1 可拓聚類方法說明

1.1 變量說明

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

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

1.2 引入可拓學

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

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

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

圖1 根據(jù)社會網(wǎng)絡(luò)人員熟識如否模擬復(fù)雜網(wǎng)絡(luò)圖(節(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之間經(jīng)過節(jié)點i的最短路徑數(shù)。

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

(3)

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

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

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

(4)

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

2 可拓聚類模型

2.1 模型經(jīng)典域及節(jié)域設(shè)置

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

(5)

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

(6)

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

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

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

(7)

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

(8)

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

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

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

(9)

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

(10)

所有權(quán)值向量λ滿足：

(11)

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

(12)

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

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

可拓集理論可用來描述復(fù)雜網(wǎng)絡(luò)節(jié)點重要性動態(tài)變化趨勢和方向。定義當T=(TK,TU)=(e,e)時，根據(jù)關(guān)聯(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劃分為關(guān)于變換T的正質(zhì)變、負質(zhì)變、正量變、負量變域和拓界，可分別形式化表示為：

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 算法流程

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

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

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

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

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

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

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

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

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

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

結(jié)果如表5、表6所示。

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

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

續(xù)表6

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

表7 各屬性不同時點熵權(quán)值

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

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

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

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

將各節(jié)點重要性可視化表示如圖2所示，利用坐標系能直觀反映各節(jié)點重要性變化方向，變動量則為其差值?？梢?，零值以上部分對應(yīng)著前25%高影響力等級節(jié)點，在第二時點有部分節(jié)點由高影響力節(jié)點轉(zhuǎn)變?yōu)榉歉哂绊懥?jié)點，也有部分節(jié)點由非高影響力節(jié)點轉(zhuǎn)變?yōu)楦哂绊懥?jié)點，還有部分節(jié)點只有同一等級內(nèi)的量變。

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

4 算法比較

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

5 結(jié) 語

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