孔 芝, 孫 琦, 寇曉宇, 王立夫

(東北大學秦皇島分校 控制工程學院, 河北 秦皇島 066004)

隨著互聯(lián)網(wǎng)的高速發(fā)展,人們的日常生活中充斥著各種各樣的網(wǎng)絡,如通信網(wǎng)絡、生物網(wǎng)絡、交通網(wǎng)絡、電力網(wǎng)絡、社交網(wǎng)絡等.網(wǎng)絡中節(jié)點之間存在著錯綜復雜的關(guān)系,當某些節(jié)點遭到破壞時,其影響會迅速波及整個網(wǎng)絡,甚至導致網(wǎng)絡癱瘓.因此,對網(wǎng)絡重要節(jié)點的評估與挖掘意義重大,這對網(wǎng)絡可靠性和魯棒性的研究具有重要意義[1].

現(xiàn)有的重要節(jié)點挖掘方法,主要考慮網(wǎng)絡的拓撲結(jié)構(gòu)來進行分析.常用的節(jié)點中心性指標主要有節(jié)點的度中心性[2]、接近中心性[3]、介數(shù)中心性[4]、特征向量中心性、H指數(shù)[5]與k-shell中心性[6]等.另外通過移除網(wǎng)絡中的一些節(jié)點,移除后對網(wǎng)絡的破壞性即為節(jié)點的重要性,研究人員提出了節(jié)點刪除法[7]、節(jié)點收縮法[8]、節(jié)點凝聚法[9]和最大連通子圖法等[10].單一結(jié)構(gòu)性指標不能很好地評價節(jié)點的重要程度,因此研究人員綜合多種指標研究該問題.于會等[11]綜合局部和全局的中心性指標進行多屬性決策,更為全面準確地得到了評價結(jié)果.Liu等[12]將k-shell指標進行改進,并將其作為新的指標,提出了一種基于與理想對象相似度排序的多屬性排序方法.Lu等[13]針對傳統(tǒng)TOPSIS方法的不足,利用相對熵來解決不能有效區(qū)分正、負理想解中的垂直線節(jié)點的問題,使得排序結(jié)果更為準確.從網(wǎng)絡拓撲結(jié)構(gòu)進行分析應考慮節(jié)點的局部信息以及全局信息,因此研究人員從不同的角度展開了研究.胡鋼等[14]通過分析關(guān)聯(lián)節(jié)點的影響以及節(jié)點之間的傳輸能力,構(gòu)建了重要度傳輸矩陣,同時考慮了節(jié)點的局部、全局信息,綜合評估節(jié)點的重要度.黃麗亞等[15]分別將網(wǎng)絡中所有節(jié)點設置為傳染源,進行傳染病傳播,定義K-階傳播數(shù)為網(wǎng)絡中已感染的節(jié)點數(shù)量,最終通過比較不同K值下的K-階傳播數(shù)的大小來對節(jié)點重要度進行評估.

以上關(guān)于節(jié)點重要度排序問題的研究,主要考慮節(jié)點在網(wǎng)絡中的結(jié)構(gòu)特性,忽視了網(wǎng)絡節(jié)點自身的關(guān)鍵屬性.而節(jié)點的自身屬性密切影響著節(jié)點的重要程度.網(wǎng)絡的拓撲結(jié)構(gòu)只能體現(xiàn)網(wǎng)絡中節(jié)點與節(jié)點之間的連接情況,無法體現(xiàn)出每個節(jié)點的屬性特征.因此只利用網(wǎng)絡中的結(jié)構(gòu)特性來挖掘重要節(jié)點,具有一定的單一性和局限性.

而在實際網(wǎng)絡中,節(jié)點屬性信息通過測量工具采集、傳輸、存儲等方式獲得,由于傳感器故障或數(shù)據(jù)保存失敗等因素,導致部分數(shù)據(jù)無法獲得,而數(shù)據(jù)缺失現(xiàn)象是無法避免的客觀存在的問題.當節(jié)點屬性信息不完備時,如何對節(jié)點重要度進行排序,是廣泛存在的實際問題.

針對上述問題,本文基于優(yōu)勢粗糙集理論和TOPSIS方法,提出融合網(wǎng)絡節(jié)點自身屬性和網(wǎng)絡結(jié)構(gòu)特性的節(jié)點重要度排序方法,能有效克服單一從拓撲結(jié)構(gòu)分析的局限,使評價結(jié)果更具合理性.最后,將本文所提出的方法應用于微博社交網(wǎng)絡中的用戶重要度的評價問題.利用蓄意攻擊及傳染病模型對該方法進行測試,并將該方法與單一中心性指標、TOPSIS方法和PageRank(PR)方法進行比較,結(jié)果表明本文所提出的方法排序結(jié)果更具合理性.

1 基礎(chǔ)知識

粗糙集理論是處理不完備和不確定性問題的一種有效工具,它是通過等價關(guān)系來對論域進行劃分的,廣泛應用于機器學習、數(shù)據(jù)挖掘、知識發(fā)現(xiàn)等領(lǐng)域.而在實際問題中,數(shù)據(jù)缺失現(xiàn)象經(jīng)常發(fā)生,針對不完備的信息系統(tǒng),利用優(yōu)勢關(guān)系代替等價關(guān)系來處理缺失數(shù)據(jù),具有一定的優(yōu)勢.下面將介紹本文所涉及到的與優(yōu)勢粗糙集相關(guān)的幾個概念.

定義1[16](對象xi在屬性c上優(yōu)于對象xj的概率) 對于一個不完備序信息系統(tǒng)S≥*=(U,A,V,f),A為屬性集,?a∈A,?xi∈U,xj∈U,則對象xi關(guān)于屬性a優(yōu)于對象xj的概率表示為

其中:屬性a的值域Va={v1,v2,…,vo}為一個有限集合,v1

定義2[16](優(yōu)勢類) 給定一個不完備序信息系統(tǒng)S≥*=(U,A,V,f),對于?xi∈U,?xj∈U,關(guān)于屬性集A的α優(yōu)勢關(guān)系定義為

2 屬性信息不完備的節(jié)點重要度排序方法

在實際網(wǎng)絡中,因節(jié)點屬性信息暫時無法獲取或信息被遺漏等因素,節(jié)點信息中常含有未知的數(shù)據(jù),而數(shù)據(jù)缺失現(xiàn)象是無法避免的客觀存在的問題.如何解決節(jié)點屬性信息含有缺失數(shù)據(jù)的重要度排序問題,是實際復雜網(wǎng)絡問題中亟待解決的關(guān)鍵問題.本文采用優(yōu)勢粗糙集方法,分析節(jié)點自身的屬性特征.

2.1 節(jié)點屬性不完備信息描述

利用不完備粗糙集描述該復雜網(wǎng)絡G*=(U*,E,C),C為每個節(jié)點的屬性集,假設節(jié)點ui對應屬性cj的屬性值vj(ui)=vij=*,不完備復雜網(wǎng)絡信息表如表1所示.

表1 屬性值不完備關(guān)系

2.2 節(jié)點屬性不完備信息與結(jié)構(gòu)信息融合的排序方法

分析復雜網(wǎng)絡節(jié)點重要度,由于其屬性值部分信息缺失,屬性信息不完備,因此采用優(yōu)勢粗糙集方法分析該問題.下面詳細闡述該方法.

第1步 設定閾值αl(l=1,…,q),計算不同閾值αl下節(jié)點關(guān)于屬性集C的優(yōu)勢類:

(1)

第2步 求解不同閾值αl下每對節(jié)點之間關(guān)于屬性集C的優(yōu)勢度(l=1,…,q):

(2)

第3步 獲取不同閾值αl下節(jié)點關(guān)于屬性集C的整體優(yōu)勢度(l=1,…,q):

(3)

(4)

其中,Pl=nl/N,nl表示取閾值αl時,排序結(jié)果并列的節(jié)點數(shù),N表示總并列節(jié)點數(shù),q為閾值α選取的個數(shù).

第5步 計算節(jié)點關(guān)于屬性集C的平均綜合優(yōu)勢度DC(xi)(i=1,…,n),即為節(jié)點xi的屬性重要度:

(5)

(6)

算法偽代碼如下:

輸入:不完備序信息系統(tǒng)S≥*=(U,A,V,f),α1,α2,…,αq.

輸出:節(jié)點屬性不完備時全序化排序結(jié)果.

1. Fori,j=1:ndo

2. Forl=1:qdo

6. End for

7. End for

8. Forl=1:qdo

10.End for

11.Fori=1:ndo

12. 利用式(5)計算節(jié)點xi的不完備屬性重要度DC(xi),

13.End for

14.Fori=1:ndo

15. 通過TOPSIS算法[11]計算節(jié)點xi的結(jié)構(gòu)重要度Zi,

16. 利用式(6)計算節(jié)點xi的屬-結(jié)重要度,返回運算結(jié)果,

17.End for

2.3 舉例分析

為驗證新方法的合理性和可行性,以具有17個節(jié)點的防空化網(wǎng)絡為例,分析節(jié)點重要度排序問題,其中節(jié)點重要度是指該節(jié)點對我方作戰(zhàn)意圖的貢獻程度和對敵方的威脅程度.在防空化網(wǎng)絡中,每個節(jié)點代表一個作戰(zhàn)單元,不同的符號代表不同的作戰(zhàn)單元,主要包括指揮控制、傳感器、火力打擊單元等.節(jié)點與節(jié)點之間的連邊表示各節(jié)點之間的物理、邏輯聯(lián)系,箭頭方向為信息、能量流動的方向.網(wǎng)絡示意圖如圖1所示.

圖1 網(wǎng)絡化防空系統(tǒng)

分析防空化網(wǎng)絡節(jié)點自身的屬性特征,設定節(jié)點的屬性集C={c1對敵方威脅程度,c2對我方作戰(zhàn)影響,c3與作戰(zhàn)意圖一致度,c4抗毀能力,c5修復難度},各節(jié)點的屬性描述如表2所示,其中*為未知數(shù)據(jù).

表2 防空化網(wǎng)絡節(jié)點的屬性值

由于屬性值的缺失不會對網(wǎng)絡的結(jié)構(gòu)造成影響,因此只需考慮節(jié)點屬性重要度對節(jié)點重要度的影響,利用優(yōu)勢粗糙集方法分析節(jié)點屬性重要度,選取α1=0.1,α2=0.5,α3=0.9,k=0.8,不完備防空化網(wǎng)絡節(jié)點屬-結(jié)重要度排序結(jié)果對比如表3所示.

表3 不完備防空化網(wǎng)絡節(jié)點重要性top10排序結(jié)果

從表3可以看出,在排序結(jié)果的top10中,重要度最高的節(jié)點均為節(jié)點9.不完備屬-結(jié)重要度與結(jié)構(gòu)重要度的排序結(jié)果大致相同.在不完備屬-結(jié)重要度與結(jié)構(gòu)重要度的排序中,節(jié)點10與節(jié)點17的差異最大,觀察表2不完備防空化網(wǎng)絡節(jié)點各屬性值,可以發(fā)現(xiàn)節(jié)點10的與作戰(zhàn)意圖一致度遠遠大于節(jié)點17,且經(jīng)計算可知節(jié)點10的優(yōu)勢度高于節(jié)點17.此外,從網(wǎng)絡的拓撲結(jié)構(gòu)中也可以發(fā)現(xiàn),相較于節(jié)點17,節(jié)點10與其他節(jié)點的聯(lián)系更加緊密,因此節(jié)點10的不完備屬-結(jié)排序結(jié)果優(yōu)于節(jié)點17是合理的.

根據(jù)以上的示例說明,選擇k∈(0,1),步長為0.05,討論k的變化對排名結(jié)果的影響,結(jié)果如表4所示.由表4可知,k的變化會導致排名的變化,但不同k的最優(yōu)選擇變化不變,即節(jié)點9.因此,驗證了本文所提方法的穩(wěn)定性.

表4 不同k值的排序結(jié)果

3 微博社交網(wǎng)絡節(jié)點重要度分析

3.1 數(shù)據(jù)獲取

本文以新浪微博作為數(shù)據(jù)源,讀取了2020年10—11月份某大學的官方微博數(shù)據(jù),獲得7 509名微博用戶的信息,選取其中200個節(jié)點構(gòu)建有向社交網(wǎng)絡.獲取用戶的基本信息如下:用戶名、用戶ID、關(guān)注數(shù)、粉絲數(shù)、會員等級、是否認證、認證方式、微博數(shù),每條博文的點贊數(shù)、轉(zhuǎn)發(fā)數(shù)、評論數(shù)等.

根據(jù)用戶之間的交互關(guān)系來構(gòu)建社交網(wǎng)絡模型,將微博用戶抽象為節(jié)點,用戶與用戶之間的關(guān)注關(guān)系抽象為邊(如果用戶ui是用戶uj的粉絲,那么就存在一條邊從用戶ui指向用戶uj),用有向圖G*=(U*,E,C)來表示,U*為節(jié)點集合,E是直接相連用戶邊的集合,C為節(jié)點自身屬性集合,節(jié)點的拓撲圖如圖2所示.

圖2 微博社交網(wǎng)絡拓撲圖

本文選取用戶的粉絲數(shù)量、近期微博質(zhì)量(包含被轉(zhuǎn)發(fā)數(shù)、被評論數(shù)、被點贊數(shù))、用戶被信服程度(主要包括用戶所發(fā)微博數(shù),以及近一個月內(nèi)的活躍程度,與其他用戶的交互程度)[17]、用戶等級、認證程度5個方面作為用戶的屬性特征,以15%的概率隨機刪除節(jié)點屬性特征表中的數(shù)據(jù),并對數(shù)據(jù)進行離散化處理,不完備微博網(wǎng)絡屬性值離散等級劃分表如表5所示,其中屬性c1,c4,c5根據(jù)數(shù)據(jù)讀取,c2,c3利用文獻[17]的方法得出,部分節(jié)點屬性特征如表6所示.

3.2 對比分析

利用優(yōu)勢粗糙集方法對該微博網(wǎng)絡節(jié)點的屬性信息進行分析.

3.2.1 對比其他重要度排序方法

本文根據(jù)2.3節(jié)中實驗得出的經(jīng)驗,在本節(jié)實驗中依舊選取k值為0.8,然后將本文所提出的排序結(jié)果與三種單指標方法DC,BC,Ci,TOPSIS方法和PR方法排序結(jié)果進行比較,6種方法挖掘出的top 20節(jié)點如表7所示.

表5 不完備微博網(wǎng)絡屬性值離散等級劃分表

表6 微博部分用戶屬性特征

從表7可以看出,在微博社交網(wǎng)絡中本文提出的方法與TOPSIS方法有17個相同的節(jié)點(其中11個節(jié)點名次完全相同),與DC,BC,Ci分別有15,10,6個相同的結(jié)果,與PR方法有6個相同的結(jié)果.本文提出方法與其他方法的節(jié)點重要度排序結(jié)果基本一致,體現(xiàn)了本文方法的可行性.與TOPSIS方法相比,排序結(jié)果發(fā)生變化的有節(jié)點58↑,159↑,76↓等,節(jié)點58,159的排序名次比較靠前,這是因為這兩名用戶的粉絲數(shù)較高,并且最近一個月內(nèi)的活躍度較高,所發(fā)微博原創(chuàng)度高,獲得其他用戶轉(zhuǎn)發(fā)、點贊、評論數(shù)高,從而獲得了較高的重要度;節(jié)點76的排序下降是因為盡管節(jié)點76有著較高的度數(shù)，即節(jié)點76的鄰居節(jié)點較多,但由于該用戶粉絲數(shù)較少,用戶被信服程度的屬性值較低,沒有認證,從而導致了節(jié)點76的不完備屬-結(jié)重要度下降.

表7 不確定微博網(wǎng)絡節(jié)點重要性top 20排序結(jié)果

3.2.2 蓄意攻擊方法

利用三種單指標方法(DC,BC,Ci)，TOPSIS方法、PR方法和本文所提出的方法分別對節(jié)點重要性進行排序,本文以排序結(jié)果所對應的節(jié)點順序進行蓄意攻擊[18],被攻擊到的節(jié)點不會再對信息傳播起到任何作用,而當社交網(wǎng)絡中的某些節(jié)點失去傳播能力時,網(wǎng)絡的傳播效率必然會受到影響.因此,本文選取網(wǎng)絡穩(wěn)健性為指標進行節(jié)點重要度的驗證,以此來衡量微博社交網(wǎng)絡中重要節(jié)點的傳播效率.

網(wǎng)絡穩(wěn)健性指的是受到攻擊后的網(wǎng)絡效率與初始效率的比值,即ε=E/E′,E為受到攻擊后網(wǎng)絡效率,E′為初始效率.其中,網(wǎng)絡效率定義為網(wǎng)絡中兩兩節(jié)點之間最短距離倒數(shù)之和的平均值,有向網(wǎng)絡中,節(jié)點之間的最短路徑需要同時考慮入邊和出邊,表達式為

(7)

其中:N為社交網(wǎng)絡中的節(jié)點數(shù);rij為節(jié)點i和節(jié)點j之間的最短路徑的距離,如果兩節(jié)點之間沒有任何線路相連接,則rij=∞,1/rij=0,所以當網(wǎng)絡中所有節(jié)點都不連接時,E=0.

按照節(jié)點重要度的順序,由高到低依次對網(wǎng)絡進行攻擊,通過對不同方法以及隨機攻擊下網(wǎng)絡穩(wěn)健性的下降情況進行對比,結(jié)果體現(xiàn)出本文所提方法的可行性及優(yōu)越性.如圖3所示,為網(wǎng)絡穩(wěn)健性隨著移除關(guān)鍵節(jié)點數(shù)量的變化情況.

從圖3中可以看出,網(wǎng)絡穩(wěn)健性與移除節(jié)點的個數(shù)大體上呈現(xiàn)出反比的趨勢,并且網(wǎng)絡穩(wěn)健性的下降速率由快到慢,這是因為起初的節(jié)點重要度較高,失效后對網(wǎng)絡的影響較大,網(wǎng)絡穩(wěn)健性下降速率較快,隨著節(jié)點不斷地失效,節(jié)點重要度開始減小,因此網(wǎng)絡穩(wěn)健性的下降速率也開始逐漸降低.相比之下,利用本文算法檢測出的關(guān)鍵節(jié)點失效后對網(wǎng)絡影響更大,其受到攻擊后網(wǎng)絡穩(wěn)健性的下降速率相比于其他6種攻擊方法較為明顯,網(wǎng)絡結(jié)構(gòu)瓦解得更快.

圖3 網(wǎng)絡穩(wěn)健性對比圖

3.2.3 SI傳染病模型

利用傳染病模型對本文方法進行驗證,在傳染病模型的SI模型中,S代表易感染者,I代表感染者,感染者以一定的概率將病毒傳染給易感染者.社交網(wǎng)絡中的信息傳播類似于該種機制,如二級傳播理論,信息首先到達輿論領(lǐng)袖那里,輿論領(lǐng)袖再把他們得到的內(nèi)容與信息傳達給受他們影響的人.因此,本文將排序結(jié)果的TOP10節(jié)點作為感染者I,剩余其他的全部節(jié)點作為易感染者S,每個節(jié)點都有相同的概率接收到信息.

對比本文方法與TOPSIS方法、三種單指標方法DC,BC,Ci以及PR方法下傳播的情況以及達到全部傳播所需的時間,如表8所示.在微博社交網(wǎng)絡中,本文提出的方法節(jié)點完全感染所需時間最短,并且在每一時刻被感染節(jié)點數(shù)最多,感染范圍最大,說明本文算法找出的關(guān)鍵節(jié)點更為合理,通過控制這些節(jié)點,將信息首先傳播給這些關(guān)鍵節(jié)點,可以提高網(wǎng)絡傳播的效率.由于TOPSIS方法綜合了DC,BC,Ci三種方法,因此每一時刻感染節(jié)點數(shù)以及最終用時與其他方法接近.

表8 不確定微博網(wǎng)絡SI傳染結(jié)果對比

4 結(jié) 論

1) 對比本文所提出的方法與其他方法,利用蓄意攻擊進行驗證,結(jié)果表明本文所提出的方法的關(guān)鍵節(jié)點對網(wǎng)絡影響更大,網(wǎng)絡結(jié)構(gòu)瓦解得更快;利用傳染病模型進行驗證,結(jié)果表明本文所提出方法的傳播時間要小于其他方法.

2) 本文所提出的方法可以有效識別網(wǎng)絡中的重要節(jié)點,對控制信息傳播以及網(wǎng)絡穩(wěn)健性均起到了良好的作用.