基于優(yōu)化結(jié)構(gòu)洞的無(wú)向加權(quán)網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)方法

王麗娟　蔡曉東　楊超　甘凱今　李隆澤

摘 要： 針對(duì)目前大多數(shù)關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)算法沒有兼顧橋節(jié)點(diǎn)與其他類型關(guān)鍵節(jié)點(diǎn)，造成評(píng)價(jià)結(jié)果存在片面性的問題，使用加權(quán)網(wǎng)絡(luò)模型結(jié)合結(jié)構(gòu)洞理論，提出一種優(yōu)化結(jié)構(gòu)洞的無(wú)向加權(quán)網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)方法。綜合考慮了節(jié)點(diǎn)的鄰居數(shù)量及其與鄰居間的拓?fù)浣Y(jié)構(gòu)，首先通過(guò)定義節(jié)點(diǎn)的鄰接度和二次鄰接度來(lái)衡量鄰居節(jié)點(diǎn)對(duì)其的重要程度，在此基礎(chǔ)上測(cè)量網(wǎng)絡(luò)中的結(jié)構(gòu)洞約束系數(shù)并通過(guò)排序發(fā)現(xiàn)網(wǎng)絡(luò)中處于重要位置的關(guān)鍵節(jié)點(diǎn)。該方法既反映出節(jié)點(diǎn)局部連接的特性，又可在全局拓?fù)湮粗那闆r下發(fā)現(xiàn)其中的關(guān)鍵節(jié)點(diǎn)，解決了全局方法計(jì)算復(fù)雜度高的問題。實(shí)驗(yàn)結(jié)果表明，該方法比基于介數(shù)、節(jié)點(diǎn)強(qiáng)度、接近度方法更準(zhǔn)確、有效地發(fā)現(xiàn)無(wú)向加權(quán)網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。

關(guān)鍵詞： 橋節(jié)點(diǎn)； 結(jié)構(gòu)洞； 約束系數(shù)； 鄰接度

中圖分類號(hào)： TN711?34； TP391.41 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2017）06?0035?05

Abstract： In order to solve the problems that most of the exiting algorithms to find key nodes do not take into account the bridge nodes and other key nodes， which may lead to an one?sided evaluation result， an optimized structural holes based method to find the key nodes in the undirected weighted networks is proposed by means of the weighted network model and the structure hole theory. The number of neighbors around the nodes and the topology structure among the nodes and neighbors are considered in this method. The importance of the neighbor nodes to the nodes is measured by defining adjacency degree and secondary adjacency degree of the nodes， and then the constraint coefficient of the structural hole in the network is calculated to find the important position of the key nodes in the network. The method can reflect the local connection feature of the node find the key nodes in network in the case that the global topology is unknown. It can solve the problem of high computational complexity of the global methods. The experiment results show that the method is better than the methods based on betweenness， node strength and proximity.

Keywords： bridge node； structure hole； constraint coefficient； adjacency degree

0 引 言

伴隨著信息技術(shù)的迅猛發(fā)展，人類的社會(huì)活動(dòng)日趨網(wǎng)絡(luò)化。人們的生活被各種復(fù)雜網(wǎng)絡(luò)[1]包圍著，例如社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、郵件網(wǎng)絡(luò)等，其中對(duì)復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)關(guān)鍵性評(píng)估[2]一直受到研究人員的廣泛關(guān)注，尋找網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)成為網(wǎng)絡(luò)科學(xué)的重要研究?jī)?nèi)容之一。挖掘出在各類復(fù)雜網(wǎng)絡(luò)中扮演重要角色的關(guān)鍵節(jié)點(diǎn)，有針對(duì)性地分析其性質(zhì)，從而進(jìn)行有效的利用，具有重要的現(xiàn)實(shí)意義和實(shí)用價(jià)值。復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)不僅與網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)有關(guān)還應(yīng)該綜合考慮其功能特征等方面的因素，結(jié)構(gòu)洞理論[3]認(rèn)為，在現(xiàn)代信息社會(huì)中，處于結(jié)構(gòu)洞位置的節(jié)點(diǎn)或者企業(yè)可以獲取更關(guān)鍵的信息和為企業(yè)帶來(lái)更多的競(jìng)爭(zhēng)優(yōu)勢(shì)，從而影響甚至于控制社會(huì)關(guān)系與信息的傳播，并為企業(yè)獲得累加收益，包括信息收益與控制收益等，因此對(duì)于關(guān)鍵節(jié)點(diǎn)的發(fā)現(xiàn)和評(píng)估不可忽略處于捷徑的節(jié)點(diǎn)。本文的目的是發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的處于重要位置的關(guān)鍵節(jié)點(diǎn)，所謂的關(guān)鍵節(jié)點(diǎn)，在網(wǎng)絡(luò)中具有活躍度較高、控制著他人交流通信、起到連接作用等特征。

近年來(lái)，復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)方法已經(jīng)成為研究熱點(diǎn)。從復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)角度考慮具體的關(guān)鍵節(jié)點(diǎn)重要性評(píng)價(jià)指標(biāo)主要包括度中心性、介數(shù)、凝聚度、特征向量、子圖、網(wǎng)絡(luò)流、隨機(jī)行走[4?6]等。這些評(píng)估方法對(duì)復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)重要性的度量都是側(cè)重于全局和局部?jī)蓚€(gè)不同的角度來(lái)考慮的，但這些算法存在共同的問題：都是基于無(wú)權(quán)無(wú)向圖，未能全面客觀反映真實(shí)復(fù)雜網(wǎng)絡(luò)情況的問題，且大都是側(cè)重于全局角度，對(duì)關(guān)鍵節(jié)點(diǎn)重要性的度量需要遍歷整個(gè)復(fù)雜網(wǎng)絡(luò)，但對(duì)于真實(shí)場(chǎng)景下的復(fù)雜網(wǎng)絡(luò)，規(guī)模比較龐大且結(jié)構(gòu)復(fù)雜，所以從全局角度衡量節(jié)點(diǎn)重要性的困難可想而知。文獻(xiàn)[7]中通過(guò)構(gòu)造有向賦權(quán)圖結(jié)構(gòu)，通過(guò)對(duì)郵件網(wǎng)絡(luò)圖局部特征的分析，即認(rèn)為度越大的節(jié)點(diǎn)在其網(wǎng)絡(luò)中的重要性越高，從而發(fā)現(xiàn)處于關(guān)鍵位置的重要用戶，但是具有度相同的節(jié)點(diǎn)，在網(wǎng)絡(luò)中的重要程度未必相同，另外還有一些“橋節(jié)點(diǎn)”無(wú)法發(fā)現(xiàn)。王建偉等在文獻(xiàn)[8]中提出了一種基于局部特征的網(wǎng)絡(luò)節(jié)點(diǎn)重要性度量方法，通過(guò)考察復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的度和其鄰居度的大小來(lái)衡量此節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度，該方法計(jì)算簡(jiǎn)單，但這種方法僅考慮了節(jié)點(diǎn)本身和鄰居節(jié)點(diǎn)之間的關(guān)系，因此無(wú)法發(fā)現(xiàn)網(wǎng)絡(luò)中的一些處于捷徑的節(jié)點(diǎn)。針對(duì)此類問題的主要研究和改進(jìn)方案有：文獻(xiàn)[9]提出另外一種基于局部特征的重要性評(píng)價(jià)方法，即發(fā)現(xiàn)網(wǎng)絡(luò)中“結(jié)構(gòu)洞”，提出了計(jì)算結(jié)構(gòu)洞的網(wǎng)絡(luò)約束系數(shù)對(duì)網(wǎng)絡(luò)閉合性和結(jié)構(gòu)洞進(jìn)行測(cè)度，這個(gè)系數(shù)描述的是網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)直接或間接聯(lián)系的緊密程度，但是這一概念只考察了最近鄰和次近鄰的影響，沒有考慮到鄰居間的聯(lián)系對(duì)控制力的影響，最終導(dǎo)致無(wú)法發(fā)現(xiàn)一些重要的“橋節(jié)點(diǎn)”。

為了解決大多數(shù)關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)算法沒有兼顧橋節(jié)點(diǎn)與其他類型關(guān)鍵節(jié)點(diǎn)，造成評(píng)價(jià)結(jié)果只能發(fā)現(xiàn)某一類的片面性問題，本文提出一種優(yōu)化結(jié)構(gòu)洞的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)方法，借鑒結(jié)構(gòu)洞理論并將其運(yùn)用于無(wú)向加權(quán)網(wǎng)絡(luò)，綜合考慮了節(jié)點(diǎn)的鄰居數(shù)量及其與鄰居間的拓?fù)浣Y(jié)構(gòu)，并通過(guò)定義節(jié)點(diǎn)的鄰接度和二次鄰接度來(lái)衡量其鄰居節(jié)點(diǎn)對(duì)其的重要程度，通過(guò)計(jì)算對(duì)鄰居節(jié)點(diǎn)投入時(shí)間（精力）占其總時(shí)間（精力）的比值，并測(cè)量網(wǎng)絡(luò)中的“結(jié)構(gòu)洞”約束系數(shù)，以此來(lái)發(fā)現(xiàn)網(wǎng)絡(luò)中處于重要位置的關(guān)鍵節(jié)點(diǎn)。

1 無(wú)向加權(quán)網(wǎng)絡(luò)拓?fù)鋱D模型

在加權(quán)復(fù)雜網(wǎng)絡(luò)中，邊權(quán)的定義方式一般遵循兩種原則：相異權(quán)和相似權(quán)。相異權(quán)與相似權(quán)表示方法恰恰相反，相異權(quán)的定義與傳統(tǒng)意義上的距離表示相似，即邊權(quán)重越小則表示兩節(jié)點(diǎn)之間的距離越小，關(guān)系越緊密；而相似權(quán)的定義則恰恰相反，即邊權(quán)重值越大則表示兩節(jié)點(diǎn)的關(guān)系越緊密。本文提出的基于優(yōu)化結(jié)構(gòu)洞的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)方法是在相似權(quán)的原則下進(jìn)行的。

圖1給出無(wú)向加權(quán)網(wǎng)絡(luò)的模型及符號(hào)表示：設(shè)網(wǎng)絡(luò)模型[G=（V，E）]是一個(gè)無(wú)自環(huán)的無(wú)向加權(quán)網(wǎng)絡(luò)，其中[V]是網(wǎng)絡(luò)中節(jié)點(diǎn)的集合， [V={v1，v2，…}，vi∈V]；[E]是邊的集合，[E={e1，e2，…}]，其中[N=V]，[W=E]。網(wǎng)絡(luò)的鄰接矩陣為[A=（aij）N×N]，對(duì)于本文中的無(wú)向加權(quán)網(wǎng)絡(luò)來(lái)說(shuō)，其鄰接矩陣是一個(gè)對(duì)稱矩陣，若節(jié)點(diǎn)[i]與節(jié)點(diǎn)[j]直接相連，則[aij=w（i，j）]，否則[aij=0]，其中[w（i，j）]表示節(jié)點(diǎn)[vi]與[vj]相連的邊的權(quán)值。對(duì)于無(wú)向加權(quán)網(wǎng)絡(luò)而言，定義節(jié)點(diǎn)的強(qiáng)度為節(jié)點(diǎn)連邊的權(quán)值之和即[wi=j=1Naij]。

2 優(yōu)化的結(jié)構(gòu)洞關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)算法

無(wú)向加權(quán)網(wǎng)絡(luò)從結(jié)構(gòu)角度考慮屬于非同質(zhì)拓?fù)浣Y(jié)構(gòu)，這就決定了網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的重要程度是不同的。對(duì)于無(wú)權(quán)網(wǎng)絡(luò)只反映了網(wǎng)絡(luò)的拓?fù)潢P(guān)系和節(jié)點(diǎn)的連接方式，并不能準(zhǔn)確描述節(jié)點(diǎn)間相互作用的強(qiáng)弱程度，在現(xiàn)實(shí)生活中一些網(wǎng)絡(luò)的節(jié)點(diǎn)之間存在著強(qiáng)弱關(guān)系，因此，本文基于無(wú)向加權(quán)網(wǎng)絡(luò)模型，提出了一種優(yōu)化的結(jié)構(gòu)洞關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)方法。

2.1 相關(guān)定義

網(wǎng)絡(luò)節(jié)點(diǎn)[i]的網(wǎng)絡(luò)約束系數(shù)定義為：

[Ci=j∈Γ（i）pij+qpiqpqj2] （1）

式中：[q]為連接節(jié)點(diǎn)[i]和節(jié)點(diǎn)[j]的間接節(jié)點(diǎn)；[pij]為節(jié)點(diǎn)[i]花費(fèi)在節(jié)點(diǎn)[j]上的時(shí)間占其總時(shí)間的比例。[pij=zijj∈Γ（i）zij-1]，[zij]指節(jié)點(diǎn)[i]和節(jié)點(diǎn)[j]之間的連接強(qiáng)度，但是該方法沒有考慮鄰居間的聯(lián)系對(duì)控制力的影響，導(dǎo)致無(wú)法發(fā)現(xiàn)一些處于重要位置的橋節(jié)點(diǎn)。

本文基于結(jié)構(gòu)洞理論，提出一種針對(duì)無(wú)向加權(quán)網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)的優(yōu)化方法，相關(guān)的定義如下：

定義1 設(shè)無(wú)向加權(quán)網(wǎng)絡(luò)的通信特征為[（f1，f2，…，fn）]，其中邊權(quán)定義：

[aij=w（i，j）=（α1，α2，…，αn）（s1，s2，…，sn）] （2）

式中：[sn]為兩節(jié)點(diǎn)通信特征為[fn]的通信頻率；[αn]表示通信特征為[sn]的權(quán)重。

在傳統(tǒng)的結(jié)構(gòu)洞理論中，并沒有對(duì)邊權(quán)進(jìn)行定義，本文考慮到在復(fù)雜網(wǎng)絡(luò)中，節(jié)點(diǎn)之間的每次通信或者聯(lián)系所產(chǎn)生的價(jià)值可能不同，因此對(duì)兩個(gè)連接節(jié)點(diǎn)之間的邊權(quán)進(jìn)行定義。例如在微博網(wǎng)絡(luò)中，節(jié)點(diǎn)之間可以通過(guò)轉(zhuǎn)發(fā)、私信、評(píng)論等進(jìn)行通信，但是不同的通信特征在兩節(jié)點(diǎn)間發(fā)生聯(lián)系時(shí)所表征出來(lái)的緊密度或者親密度是不同的；同樣在郵件網(wǎng)絡(luò)中，郵件收發(fā)雙發(fā)通過(guò)回復(fù)、發(fā)送、抄送、密送所體現(xiàn)出來(lái)的緊密度關(guān)系也是不相同的。

定義2 網(wǎng)絡(luò)節(jié)點(diǎn)[j]的鄰接度為：

[Qj=m∈Γ（j）km] （3）

式中：[Γ（j）]是節(jié)點(diǎn)[j]的鄰居節(jié)點(diǎn)的集合，[k（m）]是節(jié)點(diǎn)[m]的加權(quán)值。為了表征節(jié)點(diǎn)與鄰接節(jié)點(diǎn)之間連接的緊密性，本文與傳統(tǒng)方法一樣定義了網(wǎng)絡(luò)節(jié)點(diǎn)的鄰接度。節(jié)點(diǎn)[j]的鄰接度為與節(jié)點(diǎn)[j]直接相連的所有鄰居節(jié)點(diǎn)的強(qiáng)度值之和。

定義3 網(wǎng)絡(luò)節(jié)點(diǎn)[i] 的二次鄰接度為：

[Ni=j∈Γ（i）Qj] （4）

為了反應(yīng)節(jié)點(diǎn)在網(wǎng)絡(luò)中的拓?fù)潢P(guān)系，本文定義了節(jié)點(diǎn)的二次鄰接度，其中節(jié)點(diǎn)[i]的二次鄰接度為和節(jié)點(diǎn)[i]直接相連的所有鄰居節(jié)點(diǎn)的鄰接度之和。

定義4 節(jié)點(diǎn)[j]相對(duì)于節(jié)點(diǎn)[i]的相對(duì)重要程度：[pji=QjNi， j∈Γi， jpji=1] （5）

為了反映節(jié)點(diǎn)間鄰居關(guān)系對(duì)控制力的影響，定義了相對(duì)重要度。其中與節(jié)點(diǎn)[i]直接相連的節(jié)點(diǎn)[j]相對(duì)于節(jié)點(diǎn)[i]的相對(duì)重要度，反映了節(jié)點(diǎn)[i]對(duì)節(jié)點(diǎn)[j]所投入的時(shí)間或者精力占節(jié)點(diǎn)[i]對(duì)其所有鄰居節(jié)點(diǎn)投入的總時(shí)間或者精力的比例。若節(jié)點(diǎn)[i]的一個(gè)鄰居節(jié)點(diǎn)[j]與一個(gè)度值很大的節(jié)點(diǎn)[m]直接相連，這就意味著節(jié)點(diǎn)[m]的初始重要性較高，則節(jié)點(diǎn)[i]期望投入節(jié)點(diǎn)[j]的時(shí)間或者精力就較大，即人們總期望對(duì)有重要關(guān)系的人投入更多的精力和時(shí)間。

定義5 每個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性：[D（i）=jp（j|i）+qpqipjq2， i≠q≠j] （6）

本文采用定義4 中所定義的[pji]來(lái)取代“結(jié)構(gòu)洞”約束系數(shù)中的[pij]，即節(jié)點(diǎn)[i]對(duì)鄰居節(jié)點(diǎn)[j]投入的時(shí)間（精力）占其總時(shí)間（精力）的比例用其鄰接度和二次鄰接度的比率來(lái)替代，一個(gè)直觀的思想是如果節(jié)點(diǎn)[i]的鄰居節(jié)點(diǎn)[j]有更好的社會(huì)關(guān)系[m]，[m]為節(jié)點(diǎn)[i]的次鄰節(jié)點(diǎn)，那么對(duì)于節(jié)點(diǎn)[i]和節(jié)點(diǎn)[m]之間的共有節(jié)點(diǎn)[j]；由于[j]有更好的社會(huì)關(guān)系[m]，則節(jié)點(diǎn)[i]更傾向于對(duì)節(jié)點(diǎn)[j]投入更多的時(shí)間（精力），以期獲取更多的回報(bào)，這和現(xiàn)實(shí)生活中的人們之間的交往也相符合。

2.2 算法描述

利用上述理論分析，基于優(yōu)化的結(jié)構(gòu)洞關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)方法描述如下：

算法描述：

1.For 1：N

2.計(jì)算[aij=w（i，j）=（α1，α2，…，αn）（s1，s2，…，sn）]

3.Input 無(wú)向加權(quán)網(wǎng)絡(luò)的鄰接矩陣[A=（aij）N*N]

4.計(jì)算[wi=j=1Naij]

5.Delect[m]when [k（m）]=0

6.計(jì)算 Q（[i]）

7.計(jì)算 N（[i]）

8.計(jì)算[pji=QjNi]

9.計(jì)算[D（i）=jpji+qpqipjq2]，[i≠q≠j]

10.Select top?4 or top?10 from D（i）

11.end

3 實(shí)驗(yàn)分析

為了驗(yàn)證本文提出的基于優(yōu)化結(jié)構(gòu)洞的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)方法可有效、準(zhǔn)確發(fā)現(xiàn)網(wǎng)絡(luò)中處于重要位置的關(guān)鍵節(jié)點(diǎn)，且適用于大規(guī)模真實(shí)網(wǎng)絡(luò)，采用APRA（Advanced Research Project Agency）網(wǎng)絡(luò)數(shù)據(jù)集和安然公司郵件往來(lái)數(shù)據(jù)集進(jìn)行驗(yàn)證。

3.1 小規(guī)模網(wǎng)絡(luò)數(shù)據(jù)集實(shí)驗(yàn)

為了進(jìn)一步證明該優(yōu)化算法的有效性和準(zhǔn)確性，本文使用如圖2所示的ARPA網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，它由21個(gè)節(jié)點(diǎn)和23條邊組成，對(duì)ARPA網(wǎng)絡(luò)進(jìn)行邊賦權(quán)得到的無(wú)向加權(quán)網(wǎng)絡(luò)，其中默認(rèn)節(jié)點(diǎn)之間通行特征只有一個(gè)。并給出了該網(wǎng)絡(luò)的基于改進(jìn)結(jié)構(gòu)洞的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)排序結(jié)果如表1所示。

從表1中得到top?4的關(guān)鍵節(jié)點(diǎn)分別為14，3，6，12，為了證明該算法的有效性和可行性，表2和圖3給出了與其他三種算法相比較的結(jié)果。

表2給出本文中提出的算法以及采用度中心性、介數(shù)、接近度等方法確定的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)的排序結(jié)果。結(jié)果四種算法得出的處于重要位置的關(guān)鍵節(jié)點(diǎn)排序都略有差異，主要是因?yàn)楦髯缘呐袛鄠?cè)重點(diǎn)不同。在基于度中心性的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)算法中，排名前4位的關(guān)鍵節(jié)點(diǎn)分別為2，3，14，15，由圖2可看到這些節(jié)點(diǎn)皆為網(wǎng)絡(luò)中節(jié)點(diǎn)強(qiáng)度較大且與鄰居節(jié)點(diǎn)連接最為緊密頻繁的一類節(jié)點(diǎn)；在基于鄰近度的方法中，排名前4位的關(guān)鍵節(jié)點(diǎn)為8，9，10，7，結(jié)合圖2和表1可知該類節(jié)點(diǎn)強(qiáng)度較低，網(wǎng)絡(luò)約束系數(shù)較大；在基于burt的方法中，排名前4的關(guān)鍵節(jié)點(diǎn)分別為3，6，12，19，但是其中6，12，19的網(wǎng)絡(luò)約束系數(shù)是相同的，無(wú)法進(jìn)一步判斷這三個(gè)節(jié)點(diǎn)的重要程度；在基于介數(shù)的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)方法中，關(guān)鍵節(jié)點(diǎn)為處于橋接處的一類節(jié)點(diǎn)，忽略了其他類型的節(jié)點(diǎn)；在本文提出的方法中，排名前4位的關(guān)鍵節(jié)點(diǎn)分別為14，3，6，12，其中包括節(jié)點(diǎn)強(qiáng)度較大的14，3節(jié)點(diǎn)和處于橋連接位置的6節(jié)點(diǎn)和其他關(guān)鍵節(jié)點(diǎn)12。

為了進(jìn)一步驗(yàn)證該算法優(yōu)于其他四種算法。圖3給出了采用上述五種方法得到的ARPA網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)重要性排序后刪除前4個(gè)關(guān)鍵節(jié)點(diǎn)后的情況。其中本文中的改進(jìn)算法刪除前4個(gè)關(guān)鍵節(jié)點(diǎn)后，ARPA網(wǎng)絡(luò)被獨(dú)立地劃分為6個(gè)社團(tuán)，說(shuō)明本文的算法很好地計(jì)算出了ARPA網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)；圖3中使用基于度中心性[4]、burt[9]、介數(shù)和接近度[2]算法刪除前4個(gè)關(guān)鍵節(jié)點(diǎn)后將網(wǎng)絡(luò)分為5個(gè)獨(dú)立的社團(tuán)，在接近度算法中刪除前4個(gè)關(guān)鍵節(jié)點(diǎn)之后網(wǎng)絡(luò)被劃分為1個(gè)獨(dú)立的社團(tuán)，對(duì)比實(shí)驗(yàn)結(jié)果說(shuō)明本文提出的算法在對(duì)ARPA網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)中要優(yōu)于其他算法。

3.2 大規(guī)模真實(shí)復(fù)雜網(wǎng)絡(luò)實(shí)驗(yàn)

本文實(shí)驗(yàn)選用的數(shù)據(jù)集是FERC在2003年公開的安然郵件語(yǔ)料庫(kù)，該數(shù)據(jù)集為 1999—2002年間安然公司內(nèi)部成員郵件收發(fā)情況，由151個(gè)節(jié)點(diǎn)，517 435條邊構(gòu)成的復(fù)雜網(wǎng)絡(luò)。為了便于后續(xù)的實(shí)驗(yàn)分析，現(xiàn)需要對(duì)安然郵件數(shù)據(jù)集進(jìn)行預(yù)處理：刪除無(wú)效數(shù)據(jù)，例如noaddress@enron.com、非規(guī)范格式郵箱地址；將郵箱地址進(jìn)行映射轉(zhuǎn)換，給每個(gè)郵箱賬號(hào)賦予一個(gè)連續(xù)但不重復(fù)的整數(shù)；去除重復(fù)郵件、收發(fā)為同一賬號(hào)的郵件；郵件分為密送、回復(fù)和發(fā)送三個(gè)通信特征。

為了證明該算法適用于大規(guī)模復(fù)雜網(wǎng)絡(luò)和實(shí)驗(yàn)結(jié)果的有效性，表3給出了該算法的關(guān)鍵節(jié)點(diǎn)評(píng)價(jià)結(jié)果。

從表3的排名和對(duì)應(yīng)的職位可以看出，本文提出的算法得到的結(jié)果都是職位很高，在公司掌握最新消息或者是與外界聯(lián)系較為頻繁的活躍者，其中，前3名表征了該節(jié)點(diǎn)活躍度相對(duì)不高，但是在公司的職位較高，這符合關(guān)鍵節(jié)點(diǎn)的特征，Mike Grigaby為Manager，作為管理者需要經(jīng)常與員工和上司溝通，且是聯(lián)系公司上下層的橋梁；對(duì)于職位是Employee的Kay Mann而言，因?yàn)槠浠钴S度相對(duì)較高，被視為關(guān)鍵節(jié)點(diǎn)，結(jié)合結(jié)構(gòu)洞原理，可推測(cè)該員工近期可能會(huì)升職。

下面是對(duì)算法的時(shí)間復(fù)雜度進(jìn)行分析比較。優(yōu)化結(jié)構(gòu)洞的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)方法與其他方法相比對(duì)網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的發(fā)現(xiàn)非常有效，因?yàn)樗褂昧烁嗟男畔?，而且比介?shù)計(jì)算有更低的復(fù)雜度。由于本文中提出的基于優(yōu)化結(jié)構(gòu)洞的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)方法的時(shí)間復(fù)雜度主要集中在“結(jié)構(gòu)洞”約束系數(shù)的計(jì)算上，若采用標(biāo)準(zhǔn)的矩陣乘法，算法復(fù)雜度為[O（n3）]。但對(duì)于大部分復(fù)雜網(wǎng)絡(luò)來(lái)說(shuō)，其鄰接矩陣往往是稀疏矩陣，如果不考慮其他優(yōu)化算法，僅采用稀疏矩陣存儲(chǔ)復(fù)雜網(wǎng)絡(luò)，則“結(jié)構(gòu)洞”的主要運(yùn)算為[qpiqpqj]，而計(jì)算此式的稀疏矩陣乘法的算法復(fù)雜度為[O（n2+m2n）]，其中[n]為網(wǎng)絡(luò)中頂點(diǎn)的個(gè)數(shù)，[m]為網(wǎng)絡(luò)中邊的數(shù)量。由于[m]可能的最大值為[n2]，因此有[m2n=mmn≤m（n2n）=mn]。對(duì)于加權(quán)圖有[n

4 結(jié) 語(yǔ)

在無(wú)向加權(quán)網(wǎng)絡(luò)中，對(duì)處于重要位置的關(guān)鍵節(jié)點(diǎn)進(jìn)行評(píng)估發(fā)現(xiàn)對(duì)于研究網(wǎng)絡(luò)的抗毀性和后續(xù)社團(tuán)發(fā)現(xiàn)等都具有十分重要的意義。針對(duì)目前關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)算法大多數(shù)沒有兼顧橋節(jié)點(diǎn)與其他類型重要節(jié)點(diǎn)，造成評(píng)價(jià)結(jié)果只能發(fā)現(xiàn)某一類的片面性問題，本文借鑒結(jié)構(gòu)洞理論中網(wǎng)絡(luò)約束系數(shù)評(píng)價(jià)方法，結(jié)合無(wú)向加權(quán)網(wǎng)絡(luò)，利用節(jié)點(diǎn)之間的通信特征定義邊權(quán)。通過(guò)節(jié)點(diǎn)的鄰居數(shù)量及其與鄰居間的拓?fù)浣Y(jié)構(gòu)，定義節(jié)點(diǎn)的鄰接度和二次鄰接度來(lái)衡量其鄰居節(jié)點(diǎn)對(duì)其的重要程度?？紤]到鄰居間的聯(lián)系對(duì)控制力的影響，提出節(jié)點(diǎn)相對(duì)重要性的定義。實(shí)驗(yàn)分析表明該方法能夠準(zhǔn)確、有效地發(fā)現(xiàn)無(wú)向加權(quán)網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)，且算法的時(shí)間復(fù)雜度小于[Onm]，具有很強(qiáng)的實(shí)用性。該算法通過(guò)局部特征進(jìn)行關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)，克服全局法應(yīng)用的局限，無(wú)需對(duì)網(wǎng)絡(luò)全局架構(gòu)進(jìn)行了解，適用于大規(guī)模復(fù)雜網(wǎng)絡(luò)中。

參考文獻(xiàn)

[1] LANDHERR A， FRIEDL B， HEIDEMANN J. A critical review of centrality measure in social networks [J]. Business & information systems engineering， 2010， 2（6）： 37l?385.

[2] HE N， LI D， GAN W， et al.Mining vital nodes in complex networks [J]. Computer science， 2007， 34（12）： 1?5.

[3] 梁魯晉.結(jié)構(gòu)洞理論綜述及應(yīng)用研究探析[J].管理學(xué)家（學(xué)術(shù)版），2011（4）：52?62.

[4] REN Z， SHAO F， LIU J， et al. Node importance measurement based on the degree and clustering coefficient information [J]. Acta physica Sinica， 2013， 62（12）： 1289011?1289015.

[5] ZHU T， ZHANG S， GUO R， et al.Improved evaluation method for node importance based on node contraction in weighted complex networks [J]. Systems engineering and electronics， 2009， 31（8）： 1902?1905.

[6] WANG J， WU X， LIAO W， et al.Improved method of node importance evaluation in weighted complex networks [J]. Computer engineering， 2012， 38（10）： 74?76.

[7] 張立曉，徐汀榮，李海彥，等.一種基于局部特性的重要郵箱用戶發(fā)現(xiàn)方法[J].計(jì)算機(jī)應(yīng)用與軟件，2013，30（3）：51?54.

[8] 王建偉，榮莉莉，郭天柱.一種基于局部特征的網(wǎng)絡(luò)節(jié)點(diǎn)重要性度量方法[J].大連理工大學(xué)學(xué)報(bào)，2010，50（5）：822?826.

[9] BURT R S. Structural holes： the social structure of competition [M]. Cambridge， Mass： Harvard University Press， 1992.