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

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

0 引言

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

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

研究結(jié)構(gòu)洞算法具有重要的現(xiàn)實意義和商業(yè)價值。Yu和Liu等人[7]提出一種識別網(wǎng)絡(luò)重要節(jié)點的算法，其優(yōu)越性高于中介中心度、節(jié)點度和接近中心度。Zhang等[8]提出二分查找算法尋找廣義結(jié)構(gòu)洞?；诰W(wǎng)絡(luò)結(jié)構(gòu)特征的方法，李泓波和張健沛等[9]提出影響因子優(yōu)化算法和基于拓?fù)鋭堇碚摰闹丿B社區(qū)識別方法，識別社區(qū)間結(jié)構(gòu)洞?；谛畔鞑サ姆椒ǎ琇ou和Tang[10]根據(jù)兩級信息傳播理論，提出基于意見領(lǐng)袖的HIS和基于最小割的MaxD兩種挖掘模型來挖掘top-k結(jié)構(gòu)洞。

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

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

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

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

1 結(jié)構(gòu)洞理論及相關(guān)算法

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

圖1 結(jié)構(gòu)洞圖示

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

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

(1)

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

(2)

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

2 分層遞階的商空間模型

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

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

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

定義3商坐標(biāo)[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的分層商空間坐標(biāo)即是(xC1,xC2,……,xCm)，簡稱分層坐標(biāo)。

粒計算[14-15]以粒子為運算對象進行問題的求解。一個?；瘻?zhǔn)則對應(yīng)一個粒層，不同的?；瘻?zhǔn)則對應(yīng)多個粒層，這些粒層之間的相互聯(lián)系構(gòu)成了一個關(guān)系結(jié)構(gòu)，即粒結(jié)構(gòu)。在商空間模型中，建立的粒結(jié)構(gòu)是一種分層遞階的鏈?zhǔn)浇Y(jié)構(gòu)，在不同的粒層上，同一個問題可以以不同的粒度表示，粒計算的主要特點是在同一個問題的求解上，可以在不同粒層間轉(zhuǎn)化。本文將分層遞階的鏈?zhǔn)浇Y(jié)構(gòu)應(yīng)用于網(wǎng)絡(luò)分層中，用不同的粒度來表示不同層級的社團，實現(xiàn)網(wǎng)絡(luò)的不同粒層間的轉(zhuǎn)化。

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

(3)

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

本文在EAGLE方法層次社區(qū)結(jié)構(gòu)基礎(chǔ)上，最終獲取分層遞階社團結(jié)構(gòu)，將每一粒度下的社團作為HIS算法輸入，取該粒度下的結(jié)構(gòu)洞占據(jù)者，最終通過結(jié)構(gòu)洞的商坐標(biāo)建立結(jié)構(gòu)洞在不同粒度下的聯(lián)系，并對其進行分析。

3 多粒度結(jié)構(gòu)洞挖掘方法3.1 主要框架

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

3.2 多粒度結(jié)構(gòu)洞挖掘方法HI-SH

分層遞階網(wǎng)絡(luò)的多粒度結(jié)構(gòu)洞挖掘方法的邏輯符號表示如下：

其中，αi和βS均是可調(diào)的參數(shù)，且αi+βS<1。

(6)

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

(7)

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

HI-SH多粒度結(jié)構(gòu)洞挖掘過程如下：

方法1 HI-SH多粒度結(jié)構(gòu)洞挖掘方法輸入:給定網(wǎng)絡(luò)G(V,E),參數(shù)αi,βS,收斂閾值ε輸出:結(jié)構(gòu)洞占據(jù)者集合VSH和結(jié)構(gòu)洞節(jié)點分層坐標(biāo)XSHStep-1:對每一個節(jié)點v∈VStep-2:使用分層社團發(fā)現(xiàn)算法,求每一層網(wǎng)絡(luò)社團CLji={v1,v2,…}Step-3:對每一層網(wǎng)絡(luò)Step-4:對當(dāng)前層的每一個節(jié)點v∈VStep-5:根據(jù)公式I(v,CLi)=r(v),v∈CLiI(v,CLi)=0,v?CLi對網(wǎng)絡(luò)中的每個節(jié)點進行初始化Step-6:對每個節(jié)點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)|≤ε是否成立?若成立,則結(jié)束,不成立,則繼續(xù)Step-11:計算VSH=max|SL|≥2{βSLH(v,SL)}的值Step-12:對這一層網(wǎng)絡(luò)的VSH取top-k結(jié)構(gòu)洞Step-13:標(biāo)記VSH中每個節(jié)點xSH在不同粒度社團的坐標(biāo)Xv={(CL1i1,CL1k1,…),(CL2i2,CL2k2,…),…,(CLnin,CLnkn,…)}Step-14:重復(fù)Step-3到Step-13,直到求出前三層VSH節(jié)點End

通過上述方法，即得到分層遞階網(wǎng)絡(luò)在不同粒層下排名靠前的結(jié)構(gòu)洞和結(jié)構(gòu)洞節(jié)點在不同分層下所在的社團坐標(biāo)。下面以圖2中節(jié)點為例來說明多粒度結(jié)構(gòu)洞挖掘過程。

圖2 網(wǎng)絡(luò)在不同粒度下的社團劃分

4 實驗

4.1 實驗數(shù)據(jù)

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

表1 實驗數(shù)據(jù)

4.2 實驗結(jié)果及分析

4.2.1 不同粒度下的排序情況

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

真實數(shù)據(jù)ICML_10的社團分層結(jié)果分別為： 粒度最粗的342個社團、粒度變細(xì)的565個社團、粒度更細(xì)的806個社團。取每一粒度下的排名前20的結(jié)構(gòu)洞，結(jié)果如圖4所示。

圖3 HI-SH方法多粒度結(jié)構(gòu)洞占據(jù)者排名變化(Topic16)

圖4 HI-SH方法多粒度結(jié)構(gòu)洞占據(jù)者排名變化(ICML_10)

從圖3、圖4兩種數(shù)據(jù)可以看出，在不同的粒度下，社團中的節(jié)點發(fā)生變化導(dǎo)致結(jié)構(gòu)洞占據(jù)者發(fā)生變化，細(xì)粒度下的結(jié)構(gòu)洞占據(jù)者連接的兩個社團很可能變成粗粒度下的一個社團。此時，該節(jié)點可能會變成社團內(nèi)部一個普通的節(jié)點，而不再承擔(dān)粗粒度下結(jié)構(gòu)洞占據(jù)者的角色。

4.2.2 分層坐標(biāo)情況

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

表2 Topic16在粒度最細(xì)時top-20結(jié)構(gòu)洞的PageRank排名和分層社團坐標(biāo)

通過觀察發(fā)現(xiàn)，節(jié)點所在不同粒層的社團粒度由粗到細(xì)的過程中，占據(jù)重疊位置的節(jié)點變多，結(jié)構(gòu)洞節(jié)點占據(jù)的社團也在變多。結(jié)合圖3，在社團粒度較粗的時候，重疊節(jié)點不在結(jié)構(gòu)洞位置上。再進一步將社團?；梢园l(fā)現(xiàn)更多占據(jù)結(jié)構(gòu)洞位置的重疊節(jié)點。在這些結(jié)構(gòu)洞占據(jù)者中，在粗粒度下，若節(jié)點是重疊節(jié)點，粒度細(xì)化時，占據(jù)結(jié)構(gòu)洞位置的節(jié)點還是重疊節(jié)點，并且占據(jù)更多的社團。表中結(jié)構(gòu)洞節(jié)點在粒度最粗時所在社團大部分都在1號社團，所以有可能某個社團存在很多結(jié)構(gòu)洞。

對于ICML_10數(shù)據(jù)，表3同樣地給出最細(xì)粒度下top20結(jié)構(gòu)洞占據(jù)者和意見領(lǐng)袖PageRank排名。

表3 ICML_10在粒度最細(xì)時top-20結(jié)構(gòu)洞的PageRank排名和分層社團坐標(biāo)

續(xù)表

對真實數(shù)據(jù)ICML_10，節(jié)點在粒度變細(xì)的過程中，同樣表現(xiàn)出占據(jù)更多的重疊節(jié)點的可能性。

4.2.3 結(jié)構(gòu)洞評價指標(biāo)

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

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

對于Topic16，對比不同粒層下結(jié)構(gòu)洞節(jié)點約束度之和，可以明顯發(fā)現(xiàn)，不論哪個粒層的結(jié)構(gòu)洞，其約束度之和都比意見領(lǐng)袖的約束度之和明顯偏低，即結(jié)構(gòu)洞要比意見領(lǐng)袖更不受網(wǎng)絡(luò)其他節(jié)點的約束，在信息傳播中更不受網(wǎng)絡(luò)中其他節(jié)點的約束。對比不同粒層結(jié)構(gòu)洞約束度之和，在粒度最粗的情況下，節(jié)點約束度之和最優(yōu)。當(dāng)k<7時，不同粒層結(jié)構(gòu)洞的約束度之和差別不大；當(dāng)k>7時，在粒度最粗的情況下，節(jié)點約束度之和最優(yōu)。對于ICML_10，對比不同粒層結(jié)構(gòu)洞約束度之和，當(dāng)k<9時，約束度之和差別不大；當(dāng)k>9時，細(xì)粒度下的結(jié)構(gòu)洞約束度之和增幅變小，此粒層下的結(jié)構(gòu)洞節(jié)點更不受網(wǎng)絡(luò)的約束。相比于結(jié)構(gòu)洞，發(fā)現(xiàn)其意見領(lǐng)袖約束度之和更低，更不受網(wǎng)絡(luò)的約束。

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

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

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

對于Topic16數(shù)據(jù)，當(dāng)k<10時，節(jié)點約束度之和在粒度最粗的時候較??；當(dāng)k>10時，約束度之和相同。對比不同算法的結(jié)果，發(fā)現(xiàn)兩種結(jié)構(gòu)洞算法求得的排名靠前的結(jié)構(gòu)洞節(jié)點的約束度都比較低，而PageRank排名靠前的節(jié)點的約束度之和相對較高。對于數(shù)據(jù)ICML_10，節(jié)點的約束度之和與網(wǎng)絡(luò)的粒度沒有直接關(guān)系。在不同粒度情況下，都有可能出現(xiàn)約束度比較低的結(jié)構(gòu)洞。而PageRank排名靠前的節(jié)點的約束度之和介于兩者之間。

Topic16和ICML_10數(shù)據(jù)實驗結(jié)果表明，對網(wǎng)絡(luò)結(jié)構(gòu)洞的挖掘，不能通過單一的一個粒層找到最優(yōu)的，即網(wǎng)絡(luò)的結(jié)構(gòu)洞是動態(tài)變化的。在挖掘結(jié)構(gòu)洞的過程中，粒度過粗或者過細(xì)的實驗結(jié)果都不是單調(diào)變化的。因此，下一步的研究工作是在實驗中找到合適的粒度，并通過這些粒度的變化分析網(wǎng)絡(luò)的演化過程。

5 總結(jié)與展望

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

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

[2] 許丹青,劉奕群,張敏,等.基于在線社會網(wǎng)絡(luò)的用戶影響力研究[J].中文信息學(xué)報,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] 李泓波,張健沛,楊靜,等. 基于拓?fù)鋭莸闹丿B社區(qū)及社區(qū)間結(jié)構(gòu)洞識別——兼論結(jié)構(gòu)洞理論視角下網(wǎng)絡(luò)的脆弱性[J].電子學(xué)報, 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] 張鈴.問題求解理論及應(yīng)用[M]. 北京:清華大學(xué)出版社, 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]. 軟件學(xué)報, 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