姚　靜　趙彤洲

(1.武漢工程大學(xué)智能機(jī)器人湖北省重點(diǎn)實(shí)驗(yàn)室　武漢　430073)(2.武漢工程大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院　武漢　430073)

?

復(fù)雜社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)重要性研究

姚靜1,2趙彤洲1,2

(1.武漢工程大學(xué)智能機(jī)器人湖北省重點(diǎn)實(shí)驗(yàn)室武漢430073)(2.武漢工程大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院武漢430073)

摘要復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)對(duì)整個(gè)網(wǎng)絡(luò)有重要影響。論文分別對(duì)無(wú)向圖、有向圖中的網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行研究,采用接近中心度、介數(shù)中心度和節(jié)點(diǎn)重要度等參數(shù)作為評(píng)估無(wú)向圖的度量指標(biāo),而對(duì)有向圖采用PageRank作為評(píng)估指標(biāo)。實(shí)驗(yàn)數(shù)據(jù)采用某微博上獲取的數(shù)據(jù)構(gòu)造了一個(gè)網(wǎng)絡(luò)結(jié)構(gòu),通過(guò)對(duì)結(jié)構(gòu)相似的有向圖和無(wú)向圖計(jì)算結(jié)果對(duì)比,發(fā)現(xiàn)上述度量指標(biāo)都能很好地對(duì)關(guān)鍵節(jié)點(diǎn)進(jìn)行評(píng)估,進(jìn)一步證實(shí)了算法的有效性和可靠性。

關(guān)鍵詞復(fù)雜網(wǎng)絡(luò); 關(guān)鍵節(jié)點(diǎn); 接近中心度; 介數(shù)中心度; PageRank

Node Importance in Complex Social Networks

YAO Jing1,2ZHAO Tongzhou1,2

(1. Hubei Provincial Key Laboratory of Intelligent Robot, Wuhan Institute of Technology, Wuhan430073)

(2. School of Computer Science & Engineer, Wuhan Institute of Technology, Wuhan430073)

AbstractThe key modes play a major role in the complex social networks. The undirected graph and directed graph are focused on respectively in this paper, which use closeness centrality, betweenness centrality and key degree to describe the important node of the undirected graphas well as thePageRank index describes the directed graph. The data from the micro-blog website is collected to construct a network. The results show the validity and reliability of these evaluating indicators.

Key Wordscomplex networks, key nodes, closeness centrality, betweenness centrality, PageRank

Class NumberTP301

1引言

復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)對(duì)整個(gè)網(wǎng)絡(luò)有重要影響。例如,若想最小代價(jià)完成特定任務(wù)并且取得最大滿意度,可對(duì)關(guān)鍵節(jié)點(diǎn)施加影響。在互聯(lián)網(wǎng)世界中,若網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)遭受攻擊則會(huì)以較小代價(jià)對(duì)整個(gè)網(wǎng)絡(luò)產(chǎn)生較大程度的破壞,反之,我們也可以通過(guò)保護(hù)這些關(guān)鍵節(jié)點(diǎn)提高網(wǎng)絡(luò)的安全性。隨著社交網(wǎng)絡(luò)的快速發(fā)展,在此基礎(chǔ)上形成的服務(wù)、應(yīng)用等呈現(xiàn)出高度復(fù)雜化趨勢(shì),因而對(duì)其中節(jié)點(diǎn)的重要性進(jìn)行評(píng)價(jià)進(jìn)而發(fā)現(xiàn)其中的關(guān)鍵節(jié)點(diǎn)具有重要意義。

在復(fù)雜社會(huì)網(wǎng)絡(luò)的研究對(duì)象是人與人或人與組織之間的關(guān)系。一個(gè)社會(huì)網(wǎng)絡(luò)圖由節(jié)點(diǎn)和邊構(gòu)成,其中,節(jié)點(diǎn)是現(xiàn)實(shí)中參與社會(huì)活動(dòng)的個(gè)人或組織等單元,邊是指活動(dòng)參與者之間的關(guān)系[1~2]。常見(jiàn)的社會(huì)網(wǎng)絡(luò)包括合作者網(wǎng)絡(luò)、電子郵件網(wǎng)絡(luò)和互聯(lián)網(wǎng)社區(qū)等,在(移動(dòng))互聯(lián)網(wǎng)世界中,國(guó)內(nèi)的微博、微信、國(guó)外的Facebook中的用戶及其相互關(guān)系構(gòu)成了規(guī)模較大的復(fù)雜社會(huì)網(wǎng)絡(luò)。

復(fù)雜網(wǎng)絡(luò)的理論研究是以圖論和拓?fù)鋵W(xué)為研究基礎(chǔ)的。常用的節(jié)點(diǎn)重要性評(píng)價(jià)方法是對(duì)節(jié)點(diǎn)的中心度作為度量指標(biāo)。中心度的主體對(duì)象可以是網(wǎng)絡(luò)中的節(jié)點(diǎn)、邊、局域社團(tuán)甚至是整個(gè)網(wǎng)絡(luò)。目前常用的中心度度量指標(biāo)包含節(jié)點(diǎn)中心度、接近中心度、介數(shù)中心度、特征向量中心度等[3~4]。著名的PageRank算法是類(lèi)似于特征向量中心度的算法,這兩者都包含了反饋機(jī)制。

2節(jié)點(diǎn)重要性評(píng)價(jià)指標(biāo)

本文重點(diǎn)關(guān)注隨機(jī)網(wǎng)絡(luò),即以ER隨機(jī)圖理論為主要理論依據(jù)的網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)可以表示為G=〈V,E〉,其中V={v1,v2,…,vn}為頂點(diǎn)集合,E={ei=(vi,vj)|vi,vj∈V}為邊的集合。

2.1接近中心度

接近中心度是用來(lái)度量該節(jié)點(diǎn)通過(guò)整個(gè)網(wǎng)絡(luò)對(duì)其他節(jié)點(diǎn)產(chǎn)生影響的能力,若該節(jié)點(diǎn)的中心度越大,則該節(jié)點(diǎn)在網(wǎng)絡(luò)中所發(fā)揮的作用越大,定義為

(1)

其中,dij表示節(jié)點(diǎn)vi,vj之間的最短距離。

2.2介數(shù)中心度

介數(shù)中心度被定義為經(jīng)過(guò)節(jié)點(diǎn)的所有最短路徑的比例[4]:

(2)

其中,pse表示從頂點(diǎn)vs到頂點(diǎn)ve之間的所有最短路徑的數(shù)目,psie表示在pse中經(jīng)過(guò)節(jié)點(diǎn)的數(shù)目。由該表達(dá)式可知,介數(shù)中心度Cb(i)實(shí)際上是評(píng)估經(jīng)過(guò)該節(jié)點(diǎn)流向另外節(jié)點(diǎn)的概率。

2.3節(jié)點(diǎn)重要度

在接近中心度和介數(shù)中心度基礎(chǔ)上,綜合上述兩種因素,定義節(jié)點(diǎn)重要度為

(3)

2.4PageRank

PageRank算法是基于反饋的特征向量中心度算法[5]。該算法通過(guò)計(jì)算網(wǎng)頁(yè)之間的鏈接關(guān)系,從而判斷網(wǎng)頁(yè)的重要程度。其主要思想是若網(wǎng)頁(yè)有鏈接指向網(wǎng)頁(yè)時(shí),我們稱之為網(wǎng)頁(yè)的出鏈,則網(wǎng)頁(yè)將得到分?jǐn)?shù),該分?jǐn)?shù)取決于網(wǎng)頁(yè)的重要程度。當(dāng)剛剛開(kāi)始時(shí),PageRank賦予每個(gè)網(wǎng)頁(yè)相同的得分,經(jīng)過(guò)一段時(shí)間迭代后網(wǎng)頁(yè)重要性程度將通過(guò)結(jié)算結(jié)果看出。該指標(biāo)被描述為[6~7]

(4)

其中,PR(i)為節(jié)點(diǎn)i的PageRank值,L(j)為節(jié)點(diǎn)j鏈出網(wǎng)頁(yè)的數(shù)量,q為孤立網(wǎng)頁(yè)的修正值。

3算法實(shí)現(xiàn)

3.1接近中心度算法

由接近中心度算法模型可知,該算法只需要構(gòu)造節(jié)點(diǎn)之間的距離矩陣,距離矩陣中的元素dij即為式(1)中的分母。

3.2介數(shù)中心度算法

1) 首先用Dijstra算法計(jì)算節(jié)點(diǎn)vi到網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)之間的最短路徑,并記載每個(gè)出現(xiàn)在路徑上的節(jié)點(diǎn),凡是在最短路徑上的節(jié)點(diǎn),其出現(xiàn)次數(shù)即為PSIE(i),有

2) 計(jì)算節(jié)點(diǎn)vi到網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)之間的路徑(非最短路徑),并記載每個(gè)出現(xiàn)在路徑上的節(jié)點(diǎn),凡是在此路徑上的節(jié)點(diǎn),其出現(xiàn)次數(shù)即為PSE(i),有

3.3PageRank算法

1) 構(gòu)建鄰接表,其中第一列為鏈接源頁(yè)面,另一列為鏈接目標(biāo)頁(yè)面;

2) 用步驟1)中的鄰接表構(gòu)造鄰接矩陣,其中的行為源頁(yè)面,列為目標(biāo)頁(yè)面;

3) 將步驟2)中的矩陣轉(zhuǎn)換為概率矩陣(轉(zhuǎn)移矩陣);

4) 通過(guò)遞歸計(jì)算或者直接計(jì)算矩陣的特征值計(jì)算函數(shù)。

4實(shí)驗(yàn)結(jié)果

本文以新浪微博的數(shù)據(jù)為例進(jìn)行節(jié)點(diǎn)重要性評(píng)估[8~9]。所有新浪微博注冊(cè)的賬戶及其相互關(guān)系構(gòu)成了一個(gè)復(fù)雜的社會(huì)網(wǎng)絡(luò),可以認(rèn)為某一個(gè)微博賬戶就是網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn),其“關(guān)注”值是該節(jié)點(diǎn)的出度,其“粉絲”值是該節(jié)點(diǎn)的入度。在評(píng)價(jià)某一賬戶的重要程度時(shí),我們基于如下假設(shè):若節(jié)點(diǎn)被其他節(jié)點(diǎn)“關(guān)注”程度值越高,則該用戶越重要;若關(guān)注該節(jié)點(diǎn)的“粉絲”越重要(即PR值越高)則該節(jié)點(diǎn)越重要[10~11]。

本文以圖1為例進(jìn)行節(jié)點(diǎn)重要性評(píng)價(jià)。在圖1中共有8個(gè)節(jié)點(diǎn),9條邊;圖2有8個(gè)節(jié)點(diǎn),5條單向邊,4條雙向邊。

圖1　簡(jiǎn)單社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖(無(wú)向圖)

圖2　簡(jiǎn)單社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖(有向圖)

根據(jù)前文描述的節(jié)點(diǎn)重要性評(píng)價(jià)指標(biāo),構(gòu)造圖1的該鄰接矩陣和圖2的鄰接矩陣,其中A中的元素表示路徑(vi,vj)經(jīng)過(guò)該點(diǎn)的次數(shù)。

計(jì)算A的psie及pse為

表1　矩陣A的psie及pse值

又,考慮到用PageRank算法,其中B的狀態(tài)轉(zhuǎn)移矩陣為PB:

由此可得計(jì)算結(jié)果如表2所示。

表2中的結(jié)果計(jì)算表明,對(duì)于無(wú)向圖1節(jié)點(diǎn)5的重要度最高,其次是節(jié)點(diǎn)3,這種重要性與圖的拓?fù)浣Y(jié)構(gòu)所反映出的保持一致,因?yàn)楣?jié)點(diǎn)5處于整個(gè)網(wǎng)絡(luò)的中樞位置;對(duì)于有向圖2,節(jié)點(diǎn)5的重要程度最高,這也與圖2反映的情況一致。

表2　節(jié)點(diǎn)重要性度量指標(biāo)的比較

5結(jié)語(yǔ)

本文針對(duì)無(wú)向圖及有向圖分別用不同度量指標(biāo)進(jìn)行對(duì)比分析,對(duì)于無(wú)向圖,運(yùn)用接近度中心數(shù)、介數(shù)中心數(shù)及節(jié)點(diǎn)重要度判定指標(biāo),能準(zhǔn)確地發(fā)現(xiàn)重要節(jié)點(diǎn);對(duì)于結(jié)構(gòu)類(lèi)似的有向圖,運(yùn)用PageRank同樣能發(fā)現(xiàn)處于關(guān)鍵位置的節(jié)點(diǎn)。因而,通過(guò)計(jì)算結(jié)果能證明上述度量指標(biāo)的有效性和可信性。

參 考 文 獻(xiàn)

[1] 仇麗青,陳卓艷.基于Pagerank的社會(huì)網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)算法[J].軟件導(dǎo)刊,2014,13(8):25-28.

CHOU Liqing, CHEN Zhuoyan. The key node discovery algorithm in social networks based on Pagerank[J]. Software Tribune,2014,13(8):25-28.

[2] 周濤,柏文潔,嚴(yán)鋼.復(fù)雜網(wǎng)絡(luò)研究概述[J].物理學(xué)報(bào),2005,(1):79-83.

ZHOU Tao, BO Wenjie, YAN Gang. Description of complex networks[J]. Journal of Physics,2005,(1):79-83.

[3] Freeman L. Centrality in social networks conceptual clarification[J]. Social Networks,1979(3):215-239.

[4] Barabasi A L, Albert R. Emergence of Scaling in Random Netwoks[J]. Science,1999:286,509.

[5] 黃慎.復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性算法研究[D].武漢:中國(guó)科學(xué)院武漢物理數(shù)學(xué)研究所,2014.

HUANG Shen. The algorithm research of node importance in the complex networks[D]. Wuhan: Wuhan Institute of Physics and Mathematics, Chinese Academy of Sciences,2014.

[6] Larry Page, Sergey Brin. The Pagerank Citation Ranking: Bringing Order to the Web[C]//Stanford Digital Libraries Working Paper,1998.

[7] Bryan K, Leise T. The ＄25,000,000,000 igenvector: The linear algebra behind Google. SIAM Rev.48,569,2006.

[8] Berkhin P. Asurvey on PageRank computing. Int. Math.2,73,2005.

[9] 譚躍進(jìn),鄧宏鐘.復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要度評(píng)估的節(jié)點(diǎn)收縮方法[J].系統(tǒng)工程理論與實(shí)踐,2006,(11):79-105.

TAN Yuejin, DENG Hongzhong. The node importance evaluation of node contraction method in the complex networks[J]. System Engineering Theory and Practice,2006,(11):79-105.

[10] http://open.weibo.com/.

[11] 蔡建超,蔡明.搜索引擎PageRank算法研究[J].計(jì)算機(jī)應(yīng)用與軟件,2008,25(9):59-60.

CAI Jianchao, CAI Ming. Search engine algorithm based on Pagerank[J]. Computer Applications and Software,2008,25(9):59-60.

中圖分類(lèi)號(hào)TP301

DOI:10.3969/j.issn.1672-9722.2016.01.020

作者簡(jiǎn)介:姚靜,女,碩士研究生,研究方向:數(shù)據(jù)處理。趙彤洲,女,副教授,研究方向:圖像處理。

收稿日期:2015年7月6日,修回日期:2015年8月26日