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

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

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

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

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

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

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

1 無向加權(quán)網(wǎng)絡(luò)拓撲圖模型

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

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

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

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

2.1 相關(guān)定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 算法描述

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

算法描述：

1.For 1：N

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

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

4.計算[wi=j=1Naij]

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

6.計算 Q（[i]）

7.計算 N（[i]）

8.計算[pji=QjNi]

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

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

11.end

3 實驗分析

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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

參考文獻

[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].計算機應(yīng)用與軟件，2013，30（3）：51?54.

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

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