基于基尼系數的網絡結構洞測量

鄧世果, 吳干華,2, 楊會杰

(1.上海理工大學管理學院,上海 200093；2.華南師范大學南海學院,佛山 528225)

基于基尼系數的網絡結構洞測量

鄧世果1, 吳干華1,2, 楊會杰1

(1.上海理工大學管理學院,上海 200093；2.華南師范大學南海學院,佛山 528225)

用結構洞分析網絡結構是評價網絡結構引起的競爭優勢的一種重要方法.本文提出了一種新的結構洞定量描述方法,即基于主成分分析(PCA)的結構洞的測量.給出了類似于基尼系數的網絡貢獻度的概念,在滿足度分布不變的條件下利用貢獻度分析對比無標度網絡與對應的隨機網絡,證實用貢獻度評價網絡有效性的優越性.得出結論:貢獻度S越大,說明網絡中每個節點的重要性越平均,結構洞程度越大;反之,貢獻度S越小,則說明網絡結構信息主要集中在部分節點上,結構洞程度越小.

結構洞;主成分分析;網絡貢獻度;復雜網絡

1 結構洞的概念及計算方法

隨著社會關系網絡研究的進展,網絡結構對社會關系的影響日益受到關注.普遍存在的信息壁壘導致不完全競爭,選擇往往集中在具有支配地位的玩家手里,其他的每個玩家一定程度上附屬于具有支配地位的玩家.競爭場中處于某種特殊關系結構中的個體,可以透過信息過濾(information filtering)獲得更多競爭優勢與創新能力.關系結構對信息利益和控制利益的影響是社會競爭網絡研究的核心問題[1].

結構洞[2]是關系結構分析方法中引起廣泛關注的概念,該理論試圖對個體在群體之中的關鍵位置進行深入的解釋.結構洞指在社會關系網絡中兩個個體或兩個群體之間不存在直接連接,且它們之間不存在間接冗余關系(redundancy),那么,兩者之間的阻礙就是結構洞.如圖1所示,3個菱形和三角形B均與三角形A直接相連,但3個菱形與三角形B之間沒有邊,要通過三角形A產生聯系,這樣它們之間就產生了間隙,形成結構洞,三角形A具有較好的競爭優勢,更容易獲得信息又沒有造成冗余.三角形B的地位同于三角形A,但與三角形B直接相連的3個菱形彼此之間也有直接聯系,這就造成了網絡冗余,B在網絡結構中的優勢和控制力會明顯低于A.擁有較多結構洞的個體,越趨向于財富的快速積累、地位的快速提升.競爭的社會結構不僅要有個體的資源優勢比較,還應包括對擁有結構洞數量的關系優勢(relations advance)比較.個體的最佳方案是盡量占據多的結構洞,然后跨越結構洞,連接原來沒有關系的群體,使個體成為信息流的媒介[3-4].

圖1 結構洞示意圖Fig.1 Illustration of structural holes

網絡約束系數(network constraint index)是Burt在1992年提出的計算結構洞系數的方法[1].設節點i花費在j上的時間或者精力占其總時間或精力的比例為Pij.節點i的網絡約束系數

該約束系數描述的是網絡中某一節點與其它節點直接或間接聯系的緊密程度.網絡約束系數越高,網絡的閉合性越高,結構洞程度越小；反之,結構洞程度越大.此方法成功地應用于中等類型公司中信息擴散路徑和行動者的心理研究[5-6].但是,這一概念只是考察了節點最近鄰和次近鄰的影響,沒有考慮到更加宏觀的結構信息,并且沒有考慮到鄰居間的聯系對控制力的影響.

介數中心性(betweenness centrality)廣泛地用于定量描述結構洞.關系網絡中某節點的介數中心度是所有節點對之間的最短路徑中途經該節點的最短路徑數目.其中包含兩個假設:每條路徑的權系數相等,且信息從起始節點到目標節點傳達的過程中總是走最短路徑.因此,可測量單個節點對網絡資源控制的程度.這一方法的缺點是假設節點之間通過

最短路徑傳遞信息,這并不是普遍的行為策略[7-8],且在網絡中只有聚類系數(cluster)小的節點,介數(betweenness)大時才處于結構洞位置.

網絡有效結構尺度(network effective size)[9]定量地考慮了結構洞的部分內容,簡單地認為,如果間接看來節點之間不存在冗余關系,那么兩者之間的空隙就是結構洞,即節點度的規模減去冗余連接的數目[10].節點i的有效結構尺度

式中,j為所有與i相連的節點；q為不同于i和j的第三點；PiqPjq為節點i與節點j的冗余邊數.

總之,這些結構洞的定量描述提供了關系網絡上節點在結構上的特異性,為評價這些節點的結構上競爭性提供了重要的參考指標,但是,仍然存在一些問題需要改進,特別是沒有提供一個有效的量對關系網絡整體進行有效的評價[11].實際上,結構洞的核心思想是節點之間傳遞信息通路的非冗余性.冗余性的存在會削弱節點的競爭力,增加維護網絡結構的耗費.因此,本文將從這一思想出發,采用主成分分析方法,將基尼系數應用于結構洞特性的描述,給出網絡結構的一個整體性的評價.

2 方法與材料

2.1 主成分分析測量結構洞

主成分分析(PCA)是一種從對象中提取主要信息,而忽略相對次要信息的多元統計分析方法[12],可有效消除數據結構中的冗余信息,從而對數據進行有效的壓縮.本文基于PCA的信息壓縮思想,提出了一種新的測量結構洞程度的方法.

一個社會關系網絡可以采用鄰接矩陣描述.鄰接矩陣的矩陣元A(i,j)表示節點與節點之間的連接狀態.當兩者直接相連時該元素為1；否則為0.現

在將該矩陣的節點看作一個復雜系統的N個成分.而將鄰接矩陣的每一列看作對該列對應的成分的一個測量,也就是該成分的屬性.當網絡上兩個節點處于對稱位置時,屬性將幾乎完全相同,相關系數接近1.這種對稱結構在網絡上對應的是大量的冗余結構,結構洞會顯著減少.一個高效率的關系網絡應該是盡可能少地存在冗余結構,也就是可壓縮性盡可能達到最小,從而使每個節點和邊的存在都有其獨特的性質.當然,冗余會帶來結構的魯棒性,也是必不可少的,實際的最優關系網絡是達到兩者的平衡.

各成分的狀態表示為

PCA算法過程如下:

a.計算觀測值的協方差C

b.計算C的N個特征值,并將特征值按大小排序,記為λ1≥λ2≥…≥λN.

c.以前m個λ的和,即以可解釋百分率P為橫坐標,以m/N為縱坐標做曲線.仿照基尼系數的定義,可定義關系網絡的基尼系數,本文中將其稱為關系網絡的節點貢獻度S,如圖2所示,即所得曲線與X軸組成的面積(圖中黑色部分面積)與直線X=Y 與X軸組成的面積(圖中紫色線與X軸組成的面積)的比值.該系數越大,說明要達到同樣的可解釋百分率需要的節點數目越多,即結構冗余程度越低,結構洞越多.

圖2 貢獻度SFig.2 Contribution degree S

2.2 數據

本文選用了兩個真實的社會關系網絡,圣塔菲(Santa Fe)研究所科研合作網絡和足球運動員網絡.在保持節點度不變的條件下,隨機交叉互換邊,得到這兩個網絡對應的隨機交叉網絡.

3 結 果

3.1 擴展的BA增長模型

運用主成分分析方法計算了28個網絡的節點貢獻度S,結果發現,在同一e的條件下,擴展的BA增長模型生成的網絡的節點貢獻度SBA均隨著α的增大而減小,如圖3所示,即α越大,網絡的結構洞程度越小.這是因為新增節點與舊節點連接的偏好程度增大,即新增節點偏向于與度大的節點相連,這樣就會導致網絡中大部分節點都與部分中心節點相連,因此,網絡的信息主要集中在這些中心節點上,使其它節點的重要性降低,網絡的可壓縮性增強,造成網絡冗余.

現分別對擴展的BA增長網絡的節點貢獻度SBA和擴展的BA網絡對應的隨機交叉網絡的節點貢獻度SBAr進行比較,結果如圖3所示.在e=1,2, 3,4時,BA增長網絡的節點貢獻度SBA均大于BA網絡對應的隨機交叉網絡的節點貢獻度SBAr,即BA網絡對應的隨機交叉網絡的結構洞程度較低,因為擴展BA網絡對應的隨機交叉網絡是在度不變的條件下隨機交叉互換邊得到的網絡,這一網絡在原有網絡的基礎上破壞了原有網絡的網絡結構,降低了結構洞程度,造成網絡冗余.因此,擴展的BA網絡的網絡結構優于擴展的BA網絡對應的隨機交叉網絡的網絡結構.這說明,雖然與隨機網絡相比BA網絡的貢獻度SBA較小,即結構洞程度較小,但是,BA網絡也存在一定的網絡結構優勢,這一網絡結構要優于隨機交叉網絡的網絡結構.

圖3 e相同時S與α的關系圖Fig.3 Relation of S versusαwith same e

現比較不同e之間的擴展BA網絡節點貢獻度S,如圖4所示.在圖4(a)中發現,隨著e的增加,S增大,且S增大的速率越來越緩慢,當e從3增大到4時,S的變化已經很小,這說明e越大,BA網絡的網絡結構性越明顯,結構洞程度越高.但是,S又不會無限制地增長,它會慢慢趨向一個穩定值.而BA增長網絡對應的度不變隨機交叉網絡的S的變化趨勢沒有BA增長網絡的明顯.

3.2 真實社會網絡

基于圣塔菲科研合作網絡和足球運動員網絡的成員在俱樂部內部以及外部的社會關系,比較真實網絡與其對應的隨機交叉網絡的貢獻度,如表1所示.在表1中可以看出,真實網絡的節點貢獻度St大于隨機交叉網絡的節點貢獻度Ste,這表明真實的社會網絡結構優于隨機交叉網絡的網絡結構.

圖4 e不同時S與α的關系圖Fig.4 Relation of S versusαwith different e

表1 真實網絡與對應隨機交叉網絡的S比較Tab.1 Comparison of S for real-world networks and the corresponding shuffled networks________

4 結 論

提出了一種新的結構洞測量方法,即基于主成分分析(PCA)的結構洞的測量方法,并用此方法得出如上結果.通過擴展的BA網絡在同一e下分別選取不同的α值,得出網絡節點貢獻度S隨α的增大而減小,即α越大,網絡結構洞程度越低,在擴展的BA模型對應的隨機交叉網絡中也得出相同的結論；通過對擴展的BA增長網絡的節點貢獻度SBA和擴展的BA網絡對應的隨機交叉網絡的節點貢獻度SBAr進行比較,得出SBAr＜SBA,即擴展的BA網絡對應的隨機交叉網絡的結構洞程度低于擴展的BA增長網絡；通過比較不同e之間的擴展BA網絡節點貢獻度S,得出e越大,網絡的結構洞程度越高,但結構洞程度又不會無限制地增高,隨著e的增長會趨向于穩定狀態,且擴展的BA網絡對應的隨機交叉網絡也有相同結論,但擴展的BA網絡對應的隨機交叉網絡結構洞程度變化沒有擴展的BA網絡明顯.

通過比較真實網絡與其對應的隨機交叉網絡,得出真實的網絡的貢獻度高于其對應的隨機交叉網絡,真實的網絡結構優于其對應的隨機交叉網絡.結合各研究領域的應用可以說明,從節點關系和網絡結構的角度可以界定節點所處的位置及擁有的控制知識的力量.結構洞在網絡結構研究中起導向性作用,該理論和方法定會對商業網絡分析、情報分析及計量領域等諸多社會關系網絡研究起到強有力的推動作用.通過對各種結構洞算法的理解和掌握,可以促進對更大范圍的網絡知識的挖掘,并能夠更好地理解相關網絡的關系和結構,有利于對網絡結構展開更深層次的研究.

[1] BURT RS.The Social Structure of Competition[M]. Cambridge:Harvard University Press,1992.

[2] BURT RS.The social capital of opinion leaders[J]. The Analysis of the American Academy of Political and Social Science,1999,556(1):37-54.

[3] BURT RS.The contingent value of social capital[J]. Administrative Science Quarterly,1997,42(2): 339-365.

[4] BURT RS.Structural holes and good ideas[J].American Journal of Sociology,2004,11(2):349-399.

[5] BURT R S.The gender of social capital[J].Rationality and Society,1998,556(1):37-54.

[6] GIUSEPPE S.Network memory.The influence of past and current networks on performance[J].Social Network,2004,47(6):893-906.

[7] FREEMAN L C.A set of measures of centrality based on betweenness[J].Sociometry,1977(1):35-41.

[8] FREEMAN L C.Centrality in valued graphs:A measure of betweenness based on network flow[J].Social Network,1991(13):141-154.

[9] NEWMAN M E J.A measure of betweenness centrality based on random walks[J].Social Networks,2005, 27(2):39-54.

[10] MCEVILY B.ZAHEER A.Bridging ties:A source of firm heterogeneity in competitive abilities[J].Strategic Management Journal,1999,20(12):1133-1156.

[11] 胡蓉,鄧小昭.基于結構洞理論的個人人際網絡分析系統研究[J].情報學報,2005,24(4):485-489.

[12] 郭崇慧.基于PCA的復雜網絡社區結構分析方法[J].運籌與管理,2008,17(6): 144-149.

Gini-coefficient-based measurement of structural holes

DENGShi-guo1, WUGan-hua1,2, YANGHui-jie1
(1.Busimess School,Umiversity of Shamghai for Sciemce amd Techmology,Shamghai 200093,Chima；2.Namhai School,South Chima Normal Umiversity,Fosham 528225,Chima)

Structural hole is an important concept to estimate pattern-induced competitive power for each node in a social network.Principal component analysis(PCA)was proposed to evaluate the structural holes in a global way.Gini-coefficient for social network was defined to measure quantitatively the structural holes.As examples,the Gini coefficients for some real-world networks and the extended Barabási-Albert scale-free networks were calculated.It is concluded that the bigger the contribution of S in the network,the more uniform the importance of modes and the greater the degree of structural holes；Conversely,the smaller the contribution of S,showing the network structure information mainly concentrated in part of nodes,the smaller the degree of structural hole.

structural hole；primcipal compomemt amalysis；metwork comtributiom；complex metwork

N 941文獻標示碼：A

1007-6735(2011)05-0452-05

2011-10-08

國家自然科學基金資助項目(10975099,10635040)；上海市重點學科建設資助項目(S30501)

鄧世果(1985-),女,碩士研究生.研究方向:系統理論.E-mail:guobingpeng123@163.com

楊會杰(聯系人),男,教授.研究方向:經濟和生物復雜系統.E-mail:hjyang@usst.edu.cn