分層遞階的網絡結構洞占據者挖掘及分析

崔平平，趙姝，陳潔，錢付蘭，張以文，張燕平

(1. 安徽大學 圖書館，安徽 合肥 230601； 2. 安徽大學 協同創新中心，安徽 合肥 230601； 3. 安徽大學 計算機科學與技術學院，安徽 合肥 230601)

0 引言

近年來，對于社交網絡用戶影響力[1-2]的研究，研究者從宏觀的基于復雜網絡理論的分析，對網絡的度與度分布、聚集系數、路徑長度以及小世界和冪律分布等統計特性進行分析，到中觀的網絡拓撲結構分析，對網絡進行合理的社團劃分。在對網絡的拓撲結構研究基礎上，研究焦點逐漸轉移到微觀網絡中關鍵節點的發現。關鍵節點對于控制網絡信息傳播具有重要作用，結構洞即是網絡中的一類關鍵節點。1992年，羅納德·伯特(Ronald Burt)以Granovertter的強關系和弱關系的假設、庫克的社交網絡交換論和伯特本人關于結構自主性和廠商邊際效益為理論背景，在《結構洞》一書中首次提出并定義了結構洞[3]。

目前，對于結構洞的研究，主要是通過分析結構洞的特點，結合實際為挖掘結構洞建模。Buskens V和Van de Rijt A[4]以網絡游戲的形成為結構洞建模，他們認為節點A只有處在節點B和C中間時才能獲益。Goyal和Vega-Redondo[5]從博弈論的角度分析結構洞并建模，他們認為節點A在節點B和C之間任意位置都有可能獲益。Kleinberg等[6]通過對社會網絡隨時間變化規律建模以擴展伯特結構洞理論的工作。

研究結構洞算法具有重要的現實意義和商業價值。Yu和Liu等人[7]提出一種識別網絡重要節點的算法，其優越性高于中介中心度、節點度和接近中心度。Zhang等[8]提出二分查找算法尋找廣義結構洞。基于網絡結構特征的方法，李泓波和張健沛等[9]提出影響因子優化算法和基于拓撲勢理論的重疊社區識別方法，識別社區間結構洞。基于信息傳播的方法，Lou和Tang[10]根據兩級信息傳播理論，提出基于意見領袖的HIS和基于最小割的MaxD兩種挖掘模型來挖掘top-k結構洞。

以上對結構洞的研究主要集中在單一粒度上，即只在網絡中的某一層挖掘關鍵節點。然而我們發現，真實網絡是一種具有分層嵌套現象的分層網絡，網絡中大的社團可以細分為多個小的社團。例如，一所大學可細分為很多院系，院系又細分為多個專業，專業細分出不同年級。將大學看作大社團，那么院系即為大社團里的小社團，專業是社團中更小的社團。從學院角度，網絡是一種劃分；從年級角度，網絡是一種更細的劃分。這種大社團里包含小社團的現象，就是網絡的一種分層遞階特性。

在具有分層遞階特性的網絡中，不同層級的關鍵節點不一定相同。上例中，學院層的結構洞節點，不一定還是專業層的結構洞節點。只對網絡的某一層進行分析時，可能忽略了某些在其他層占據重要位置的節點，從而使結果并不能反映整個網絡的真實狀況。因此，在挖掘網絡的結構洞時，需要考慮網絡不同分層對結構洞結果的影響。網絡的分層遞階特性符合粒計算的商空間模型，采用粒計算的商空間理論為社交網絡的這種分層遞階特性的數據分析提供了理論基礎。

綜上所述，本文提出一種基于分層遞階的結構洞挖掘方法HI-SH。首先，基于分層遞階的商空間理論，對網絡進行多粒度社團劃分，得到每一粒度下網絡的社團；然后，根據兩級信息傳播理論，用結構洞挖掘算法，挖掘每一粒度下top-k結構洞；最后，對不同粒度下結構洞的演化進行分析。在公用數據Topic16和真實數據ICML_10中進行實驗。

本文第二節是相關工作，介紹結構洞的概念、粒計算的商空間模型、結構洞挖掘算法和社團劃分算法，第三節是多粒度結構洞挖掘方法模型，第四節是實驗及結果分析，第五節是全文總結與展望。

1 結構洞理論及相關算法

根據伯特給出的結構洞定義[3]，結構洞是社會關系網絡中互相之間沒有直接或間接的聯系，擁有互補資源或信息的個體之間存在的空位。從網絡的整體上看，這種空位就像網絡結構中的洞穴，本質上結構洞表示的是三方之間的非冗余聯系。如圖1所示，左圖中，節點1與節點2、3、4相連，信息通過節點1在節點2、3、4之間傳播。如果此時刪除節點1，由于節點2、3、4之間沒有邊相連，不能產生聯系，信息將無法傳播。此時節點1可能是這個網絡的結構洞占據者。但右圖中，刪除節點1，節點2、3、4之間還有邊相連，信息可以繼續傳播，此時節點1就可能不是這個網絡的結構洞占據者。因此，找到網絡中的結構洞，對于控制信息傳播具有重要意義，研究結果表明，在Twitter網絡上，1%的結構洞占據者將控制25%的信息傳播[10]。

圖1 結構洞圖示

伯特提出結構洞指數[3]作為結構洞度量指標，結構洞指數包括有效規模、效率、網絡約束度和等級度四個方面，其中最主要的是約束度。約束度以節點對其他節點的依賴值為衡量指標，定義為節點在個體網絡中擁有的利用結構洞的能力。約束度值越小，結構洞程度越大，節點可能占據越多結構洞位置；約束度值越大，節點可能占據較少結構洞位置。

伯特指出“你自己的機會受到的約束取決于兩個因素： 一是你曾經投入了大量時間和精力的另一個接觸者q；另一個是在多大程度上向接觸者j的關系投入大量的精力。”[3]因此，節點i對其鄰居節點j的約束度計算如式(1)所示。

(1)

其中q≠i,j，pij為節點i花費在與其直接合作的節點j上的時間和精力占節點i花費的總時間和精力的關系比例，在網絡中，用節點的度來衡量。piqpqj為節點i和j之間的冗余度，定義網絡的冗余度為該節點所在的網絡中其他節點的平均度。piqpqj的總和為節點i花費在節點j的關系上的時間和精力相對于節點i花費在其他節點關系上的時間和精力的比例。因此節點i的總約束度如式(2)所示。

(2)

根據兩級信息傳播理論，信息總是先流向意見領袖，再由意見領袖流向大眾，Lou和Tang提出挖掘網絡結構洞的HIS算法[10]，他們認為從意見領袖傳播的信息更容易傳播到更廣泛的群體，如果一個個體與不同社團的意見領袖之間有直接聯系，則這個個體很有可能成為結構洞。該算法中首先通過PageRank算法[11]，初始化網絡中節點在每個社團的重要性，計算網絡結構洞的可能性大小；通過迭代公式，重新計算節點重要性，重新計算網絡結構洞可能性大小，直到節點的重要性不再更新為止，最后按節點重要性的值從大到小得到網絡的結構洞排名靠前的結構洞。本文將以HIS算法作為單一粒度下挖掘結構洞占據者的基本算法，在分層遞階的網絡中挖掘多粒度結構洞。

2 分層遞階的商空間模型

人類智能的特點是人們能從極不相同的粒度上觀察和分析同一問題。人們不僅能在不同粒度的世界上進行問題求解，還能很快從一個粒度世界跳到另一個粒度世界。這種處理不同粒度世界的能力，正是人類問題求解強有力的表現[12]。商空間理論提供了一個描述不同粒度世界的模型。

定義1商空間模型[12]，對問題(X,f,T)，其中X表示問題的論域，f表示論域的屬性，T表示論域的結構，從不同的粒度(角度、層次)考察問題(X,f,T)，是指給定X的一個等價關系R，并由R產生一商集[X]，然后研究相應問題([X],[f],[T])，其中[f]，[T]分別表示商集[X]上對應的商屬性函數和商結構，稱([X],[f],[T])為(X,f,T)的商空間。

定義2商空間鏈[13]，定義一個粗細關系，[X]i<[X]j?[X]iis coarser than[X]j。如果[X]i是[X]j的商集, 則表示[X]i<[X]j。序關系[X]1<[X]2<……<[X]m=X就叫分層商空間鏈。

定義3商坐標[13]，X的一個分層商空間鏈[X]1<[X]2<……<[X]m=X，對于?x∈X，x=(xC1,xC2,……,xCm)，其中，xCi是[X]i中包含x的粒子。在一個分層商空間鏈[X]1<[X]2<……<[X]m=X中，x的分層商空間坐標即是(xC1,xC2,……,xCm)，簡稱分層坐標。

粒計算[14-15]以粒子為運算對象進行問題的求解。一個粒化準則對應一個粒層，不同的粒化準則對應多個粒層，這些粒層之間的相互聯系構成了一個關系結構，即粒結構。在商空間模型中，建立的粒結構是一種分層遞階的鏈式結構，在不同的粒層上，同一個問題可以以不同的粒度表示，粒計算的主要特點是在同一個問題的求解上，可以在不同粒層間轉化。本文將分層遞階的鏈式結構應用于網絡分層中，用不同的粒度來表示不同層級的社團，實現網絡的不同粒層間的轉化。

在分層遞階網絡的社團劃分上，沈等[16]提出一種基于極大團的凝聚層次聚類算法EAGLE用于層次和重疊社團的結構挖掘，該算法的主要思想： 首先，找到網絡的極大團，作為初始社區；其次將具有最大相似度的社團對不斷合并，生成網絡的樹狀圖；最后在生成樹上根據EQ的值選擇合適位置斷開，得到相應社團劃分。為獲取最合理的社團結構，文章提出一種新的模塊度指標，如式(3)所示。

(3)

其中，m是網絡中邊總數，kv是節點v的度，Ci是網絡中社團，Ov是節點v所在社團數目，A是網絡圖的鄰接矩陣，如果兩節點之間有連接邊，則Avw=1，否則為0，通常選擇在EQ值最大的位置對生成樹進行切割，進而得到理想社團劃分。

本文在EAGLE方法層次社區結構基礎上，最終獲取分層遞階社團結構，將每一粒度下的社團作為HIS算法輸入，取該粒度下的結構洞占據者，最終通過結構洞的商坐標建立結構洞在不同粒度下的聯系，并對其進行分析。

3 多粒度結構洞挖掘方法3.1 主要框架

分層遞階網絡的多粒度結構洞挖掘方法，其主要思想是在社團劃分時將網絡進行分層，網絡中的每一層代表一個粒度，分別挖掘不同粒度下的結構洞。主要步驟： 首先對網絡進行多粒度社團劃分，得到每一粒度下的社團劃分結果，實驗中選取了三個粒度，分別為一個社團模塊度最優、兩個模塊度次優的三種情況下的社團劃分作為三個粒度；對于不同粒度下的節點與節點所在的社團，使用HIS算法求結構洞。接著，記錄結構洞占據者排名靠前節點的分層坐標。對比這些結構洞占據者的位置變化，分析網絡結構洞這類關鍵節點的演化過程。

3.2 多粒度結構洞挖掘方法HI-SH

分層遞階網絡的多粒度結構洞挖掘方法的邏輯符號表示如下：

其中，αi和βS均是可調的參數，且αi+βS<1。

(6)

其中節點v的PageRank值r(v)的計算如式(7)所示。

(7)

式中，c是一個常數，節點v′是節點v的所有鄰居節點，N(v′)表示節點v′的度。

HI-SH多粒度結構洞挖掘過程如下：

方法1 HI-SH多粒度結構洞挖掘方法輸入:給定網絡G(V,E),參數αi,βS,收斂閾值ε輸出:結構洞占據者集合VSH和結構洞節點分層坐標XSHStep-1:對每一個節點v∈VStep-2:使用分層社團發現算法,求每一層網絡社團CLji={v1,v2,…}Step-3:對每一層網絡Step-4:對當前層的每一個節點v∈VStep-5:根據公式I(v,CLi)=r(v),v∈CLiI(v,CLi)=0,v?CLi對網絡中的每個節點進行初始化Step-6:對每個節點v∈VStep-7:對每個社團CLi∈CLStep-8:計算I(v,CLi)=maxeuv∈ESL?CL∧CLi∈SL{I(v,CLi),αiI(u,CLi)+βSLH(u,SL)}Step-9:計算H'(v,SL)=minCLi∈S{I'(v,CLi)}Step-10:判斷maxv∈V,CLi∈C|I'(v,CLi)-I(v,CLi)|≤ε是否成立?若成立,則結束,不成立,則繼續Step-11:計算VSH=max|SL|≥2{βSLH(v,SL)}的值Step-12:對這一層網絡的VSH取top-k結構洞Step-13:標記VSH中每個節點xSH在不同粒度社團的坐標Xv={(CL1i1,CL1k1,…),(CL2i2,CL2k2,…),…,(CLnin,CLnkn,…)}Step-14:重復Step-3到Step-13,直到求出前三層VSH節點End

通過上述方法，即得到分層遞階網絡在不同粒層下排名靠前的結構洞和結構洞節點在不同分層下所在的社團坐標。下面以圖2中節點為例來說明多粒度結構洞挖掘過程。

圖2 網絡在不同粒度下的社團劃分

4 實驗

4.1 實驗數據

本文實驗數據包含公用數據和真實數據。公用數據是清華大學ArnetMiner系統里下載的To-pic16數據。真實數據是搜集CCF推薦國際學術會議A類的ICML從2005年到2014年共10年的會議論文，搜集論文標題和文章作者信息，對數據進行處理，若兩個作者出現在同一篇文章里，則這兩個作者之間有一條邊，數據集記為ICML_10。數據信息如表1所示。

表1 實驗數據

4.2 實驗結果及分析

4.2.1 不同粒度下的排序情況

在對社團分層時，選擇一個社團模塊度最優、兩個模塊度次優三種情況下的社團劃分結果，公用數據Topic16的社團分層結果分別為： 粒度最粗的39個社團、粒度變細的163個社團、粒度更細的245個社團。使用HIS算法作為單粒度下的結構洞挖掘算法，對挖掘結果分析時取每一粒度下的排名前20的結構洞，結果如圖3所示，圖中的斷層表示節點不在top20之內。

真實數據ICML_10的社團分層結果分別為： 粒度最粗的342個社團、粒度變細的565個社團、粒度更細的806個社團。取每一粒度下的排名前20的結構洞，結果如圖4所示。

圖3 HI-SH方法多粒度結構洞占據者排名變化(Topic16)

圖4 HI-SH方法多粒度結構洞占據者排名變化(ICML_10)

從圖3、圖4兩種數據可以看出，在不同的粒度下，社團中的節點發生變化導致結構洞占據者發生變化，細粒度下的結構洞占據者連接的兩個社團很可能變成粗粒度下的一個社團。此時，該節點可能會變成社團內部一個普通的節點，而不再承擔粗粒度下結構洞占據者的角色。

4.2.2 分層坐標情況

為進一步分析結構洞占據者在信息傳播中所起的作用，對于Topic16數據，表2給出最細粒度下top20結構洞占據者和意見領袖PageRank排名，表中第三列表示節點在由粗到細的三個粒度中所在社團編號，如1,(2,7),(15,17,32)，用“，”表示不同的分層。“1”表示在最粗粒度下屬于第一個社團，“(2,7)”表示在第二粗粒度下，同時屬于編號為2和7兩個社團，“(15,17,32)”表示在最細粒度下同時屬于編號為15、17和32三個社團。

表2 Topic16在粒度最細時top-20結構洞的PageRank排名和分層社團坐標

通過觀察發現，節點所在不同粒層的社團粒度由粗到細的過程中，占據重疊位置的節點變多，結構洞節點占據的社團也在變多。結合圖3，在社團粒度較粗的時候，重疊節點不在結構洞位置上。再進一步將社團粒化，可以發現更多占據結構洞位置的重疊節點。在這些結構洞占據者中，在粗粒度下，若節點是重疊節點，粒度細化時，占據結構洞位置的節點還是重疊節點，并且占據更多的社團。表中結構洞節點在粒度最粗時所在社團大部分都在1號社團，所以有可能某個社團存在很多結構洞。

對于ICML_10數據，表3同樣地給出最細粒度下top20結構洞占據者和意見領袖PageRank排名。

表3 ICML_10在粒度最細時top-20結構洞的PageRank排名和分層社團坐標

續表

對真實數據ICML_10，節點在粒度變細的過程中，同樣表現出占據更多的重疊節點的可能性。

4.2.3 結構洞評價指標

使用約束度來評價求得結構洞的重要程度，對不同粒度下top-20結構洞節點求約束度之和，結果如圖5所示，其中橫坐標數字表示結構洞排名前多少的節點，縱坐標表示排名前多少節點的約束度之和。

圖5 HI-SH方法(HIS)多粒度結構洞約束度之和變化

對于Topic16，對比不同粒層下結構洞節點約束度之和，可以明顯發現，不論哪個粒層的結構洞，其約束度之和都比意見領袖的約束度之和明顯偏低，即結構洞要比意見領袖更不受網絡其他節點的約束，在信息傳播中更不受網絡中其他節點的約束。對比不同粒層結構洞約束度之和，在粒度最粗的情況下，節點約束度之和最優。當k<7時，不同粒層結構洞的約束度之和差別不大；當k>7時，在粒度最粗的情況下，節點約束度之和最優。對于ICML_10，對比不同粒層結構洞約束度之和，當k<9時，約束度之和差別不大；當k>9時，細粒度下的結構洞約束度之和增幅變小，此粒層下的結構洞節點更不受網絡的約束。相比于結構洞，發現其意見領袖約束度之和更低，更不受網絡的約束。

4.2.4 對比不同算法約束度之和

MaxD算法是文獻[10]中提到的另一種計算結構洞的模型，它基于最小割原理，該算法對社團粒度的變化敏感性不大。使用MaxD算法求單粒度下結構洞，對兩組數據求結構洞約束度之和，結果如圖6所示。

圖6 HI-SH方法(MaxD)多粒度結構洞約束度之和變化

對于Topic16數據，當k<10時，節點約束度之和在粒度最粗的時候較小；當k>10時，約束度之和相同。對比不同算法的結果，發現兩種結構洞算法求得的排名靠前的結構洞節點的約束度都比較低，而PageRank排名靠前的節點的約束度之和相對較高。對于數據ICML_10，節點的約束度之和與網絡的粒度沒有直接關系。在不同粒度情況下，都有可能出現約束度比較低的結構洞。而PageRank排名靠前的節點的約束度之和介于兩者之間。

Topic16和ICML_10數據實驗結果表明，對網絡結構洞的挖掘，不能通過單一的一個粒層找到最優的，即網絡的結構洞是動態變化的。在挖掘結構洞的過程中，粒度過粗或者過細的實驗結果都不是單調變化的。因此，下一步的研究工作是在實驗中找到合適的粒度，并通過這些粒度的變化分析網絡的演化過程。

5 總結與展望

本文針對結構洞研究中沒有考慮網絡的分層遞階特性的問題，提出了一種從多粒度角度挖掘結構洞的方法，使用該方法對不同數據進行實驗，可以看到不同粒度下的結構洞占據者信息，這對研究社交網絡影響力、網絡的演化過程和控制信息的傳播具有重要意義。本文在結構洞的研究理論和實踐基礎上，對分層遞階網絡的多粒度結構洞特性進行了分析，由于結構洞算法求得排名的穩定性還有待提高，不同粒度下得到的結構洞影響力指數不同，約束度與粒度粗細并沒有直接聯系。所以在接下來的研究中，將針對如何自適應挖掘最合適的粒度，使得對于整個網絡來說找到最具影響力的結構洞，將該方法進一步完善。

[1] 黃俊銘,沈華偉,程學旗.利用社交網絡的影響力骨架探索信息傳播[J].中文信息學報,2016,30(02):74-82.

[2] 許丹青,劉奕群,張敏,等.基于在線社會網絡的用戶影響力研究[J].中文信息學報,2016,30(02):83-89.

[3] Burt R S. Structural holes: The social structure of competition [M]. Boston: Harvard University Press,1992.

[4] Buskens V, Van de Rijt A. Dynamics of networks if everyone strives for structural holes [J]. American Journal of Sociology, 2008, 114(2): 371-407.

[5] Goyal S, Vega-Redondo F. Structural holes in social networks [J]. Journal of Economic Theory, 2007, 137(1):460-492.

[6] Kleinberg J, Suri S, Tardos é, et al. Strategic network formation with structural holes[J]. Proceedings of Acm Conference on Electronic Commerce, 2008, 7(3):284-293.

[7] Hui Y, Zun L, Yongjun L.Using local improved Structural Holes method to identify key nodes in complex networks[C] //Proceedings of Measuring Technology and Mechatronics Automation (ICMTMA), 2013 Fifth International Conference on. IEEE, 2013: 1292-1295.

[8] Zhang E, Wang G, Gao K, et al. Generalized structural holes finding algorithm by bisection in social communities[C]//Proceedings of Genetic and Evolutionary Computing (ICGEC), 2012 Sixth International Conference on. IEEE, 2012:276-279.

[9] 李泓波,張健沛,楊靜,等. 基于拓撲勢的重疊社區及社區間結構洞識別——兼論結構洞理論視角下網絡的脆弱性[J].電子學報, 2014,42(1):62-69.

[10] Lou T, Tang J. Mining structural hole spanners through information diffusion in social networks[C]//Proceedings of the 22nd International Conference on World Wide Web. International World Wide Web Conferences Steering Committee, 2013:825-836.

[11] Page L, Brin S, Motwani R, et al. The PageRank citation ranking: Bringing order to the web[R].Stanford University： Stanford InfoLab, 1999.

[12] 張鈴.問題求解理論及應用[M]. 北京:清華大學出版社, 2007.

[13] Zhao S, Zhang L, Xu X, et al. Hierarchical description of uncertain information[J]. Information Sciences, 2014, 268(1):133-146.

[14] Zhang B, Zhang L. Theory and applications of problem solving[M]. North-Holland: Elsevier Science Publishers BV, 1992.

[15] 張鈴, 張鈸. 模糊商空間理論(模糊粒度計算方法)[J]. 軟件學報, 2003, 14(4):770-776.

[16] Shen H, Cheng X, Cai K, et al. Detect overlapping and hierarchical community structure in networks[J]. Physica A Statistical Mechanics & Its Applications, 2009, 388(8):1706-1710.

E-mail: chenjie200398@163.com