基于社團結(jié)構(gòu)的多粒度結(jié)構(gòu)洞占據(jù)者發(fā)現(xiàn)及分析

趙姝，趙暉，陳潔，陳喜，張燕平

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

?

基于社團結(jié)構(gòu)的多粒度結(jié)構(gòu)洞占據(jù)者發(fā)現(xiàn)及分析

趙姝1,2，趙暉1,2，陳潔1,2，陳喜1,2，張燕平1,2

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

摘要：目前研究者已提出一些基于社團結(jié)構(gòu)的結(jié)構(gòu)洞發(fā)現(xiàn)方法，然而不同粒度下社團劃分結(jié)果使網(wǎng)絡(luò)呈現(xiàn)層次化結(jié)構(gòu)，影響社團結(jié)構(gòu)中節(jié)點跨越結(jié)構(gòu)洞的程度。本文基于網(wǎng)絡(luò)社團劃分思想提出一種分層網(wǎng)絡(luò)的結(jié)構(gòu)洞發(fā)現(xiàn)方法MG_MaxD。首先，使用分層遞階社團劃分算法(本文使用EAGLE算法)，得到不同粒度的社團結(jié)構(gòu)；然后，使用結(jié)構(gòu)洞發(fā)現(xiàn)算法MG_MaxD得到不同粒度下的結(jié)構(gòu)洞占據(jù)者；最后，使用結(jié)構(gòu)洞跨越程度指標分析不同粒度下的社團結(jié)構(gòu)對節(jié)點跨越結(jié)構(gòu)洞程度的影響。在公用和真實數(shù)據(jù)集上的實驗結(jié)果表明節(jié)點跨越結(jié)構(gòu)洞的程度即結(jié)構(gòu)洞節(jié)點的優(yōu)勢將隨著粒度的變細而增大。

關(guān)鍵詞：結(jié)構(gòu)洞；社團結(jié)構(gòu)；多粒度；層次結(jié)構(gòu)；社團劃分；分層網(wǎng)絡(luò)；網(wǎng)絡(luò)結(jié)構(gòu)；社會網(wǎng)絡(luò)分析

在信息化技術(shù)迅猛發(fā)展的今天，社會網(wǎng)絡(luò)在工作生活中發(fā)揮著越來越重要的作用。網(wǎng)絡(luò)中的信息交流、資源交換已成為社會生活中不可缺少的重要途徑。隨著參與社會網(wǎng)絡(luò)的個體增加，社會網(wǎng)絡(luò)對于人們的重要性也隨之增加，使得對社會網(wǎng)絡(luò)的研究具有更深遠的意義。近年來，對于社會網(wǎng)絡(luò)的性質(zhì)分析，逐漸從對網(wǎng)絡(luò)整體結(jié)構(gòu)分析，如發(fā)現(xiàn)網(wǎng)絡(luò)的拓撲性質(zhì)含有無標度、小世界特性和社團結(jié)構(gòu)等，轉(zhuǎn)移到對網(wǎng)絡(luò)中重要節(jié)點的分析，如結(jié)構(gòu)洞[1]、意見領(lǐng)袖[2]等。結(jié)構(gòu)洞是網(wǎng)絡(luò)中普遍存在的現(xiàn)象，在網(wǎng)絡(luò)中占據(jù)何種位置能夠獲益的想法已經(jīng)得到了許多人的關(guān)注。個體或者團體中的中間人可以獲得豐富的信息并控制他們的網(wǎng)絡(luò)關(guān)系，在網(wǎng)絡(luò)中占據(jù)中心位置的主體可以獲得豐厚的利益[1]。結(jié)構(gòu)洞在獲取網(wǎng)絡(luò)有效信息方面起著關(guān)鍵的作用，且發(fā)現(xiàn)網(wǎng)絡(luò)中的結(jié)構(gòu)洞可以對網(wǎng)絡(luò)結(jié)構(gòu)進行優(yōu)化和增強魯棒性。結(jié)構(gòu)洞理論作為網(wǎng)絡(luò)結(jié)構(gòu)分析的重要方法，在不同領(lǐng)域和學(xué)科的研究中都獲得了豐富的成果[3-7]。

在結(jié)構(gòu)洞研究的推進過程中，研究者發(fā)現(xiàn)結(jié)構(gòu)洞占據(jù)者在網(wǎng)絡(luò)中可以獲得競爭優(yōu)勢和網(wǎng)絡(luò)收益，并提出不同的結(jié)構(gòu)洞模型。Kleinberg等[8]從戰(zhàn)略和動態(tài)方面研究了結(jié)構(gòu)洞理論，進一步擴充了伯特等研究者的工作。他們模擬了這樣的過程，即當所有個體都在競爭橋節(jié)點位置的時候，社會網(wǎng)絡(luò)隨著時間是如何改變的。Buskens和Van[9]使用博弈論方法來模擬具有結(jié)構(gòu)洞的網(wǎng)絡(luò)形成過程，認為節(jié)點A只有處在節(jié)點B和C中間時才能獲益。Goyal和Vega[10]提出網(wǎng)絡(luò)形成的模型來研究社會網(wǎng)絡(luò)中結(jié)構(gòu)洞的形成，并認為當節(jié)點A位于任意長的B-C路徑上，且作為節(jié)點B和C的中介時，都將獲得潛在利益。這種模型將導(dǎo)致形成星形網(wǎng)絡(luò)，然而，現(xiàn)實中的大部分網(wǎng)絡(luò)并不一定是星形拓撲結(jié)構(gòu)。Bruggeman等[11]考慮了生態(tài)位重疊導(dǎo)致的分散競爭對網(wǎng)絡(luò)中個體的結(jié)構(gòu)自主性的影響，修正了伯特的模型。

研究者通過對結(jié)構(gòu)洞的性質(zhì)進行分析，提出許多基于網(wǎng)絡(luò)結(jié)構(gòu)和社團結(jié)構(gòu)的結(jié)構(gòu)洞度量指標。基于網(wǎng)絡(luò)結(jié)構(gòu)的度量主要考慮結(jié)構(gòu)洞的優(yōu)勢，伯特提出了4個定量描述結(jié)構(gòu)洞的度量指標[1,12-13]，即網(wǎng)絡(luò)約束系數(shù)、網(wǎng)絡(luò)有效規(guī)模、效率和等級度；Freeman提出介數(shù)中心性指標[14]；Newman等[15]提出局部聚類系數(shù)；鄧世果等[16]提出一種基于基尼系數(shù)的結(jié)構(gòu)洞測量方法，并討論貢獻度和結(jié)構(gòu)洞程度之間的關(guān)系；基于社團結(jié)構(gòu)的度量主要考慮結(jié)構(gòu)洞跨越不同社團的屬性，Rezvani等[17]根據(jù)伯特定義中個體連接的社團數(shù)和個體的鄰居節(jié)點數(shù)提出一種結(jié)構(gòu)洞度量指標。

隨著對結(jié)構(gòu)洞的價值和意義繼續(xù)深入研究，研究者提出多種結(jié)構(gòu)洞發(fā)現(xiàn)算法，在不同結(jié)構(gòu)和類型的復(fù)雜網(wǎng)絡(luò)中準確發(fā)現(xiàn)結(jié)構(gòu)洞占據(jù)者。Zhang等[18]認為網(wǎng)絡(luò)中很難存在單節(jié)點形成的結(jié)構(gòu)洞，他們在結(jié)構(gòu)洞理論的基礎(chǔ)上提出“廣義結(jié)構(gòu)洞”概念，并給出基于譜圖理論的啟發(fā)式“廣義結(jié)構(gòu)洞”發(fā)現(xiàn)算法DGSH。Hu等[19]將結(jié)構(gòu)洞理論擴展到有向模糊社交網(wǎng)絡(luò)并提出單向模糊結(jié)構(gòu)洞和雙向模糊結(jié)構(gòu)洞的算法，分別計算行動者占據(jù)的單向和雙向模糊結(jié)構(gòu)洞個數(shù)。Lou和Tang[20]在假設(shè)網(wǎng)絡(luò)社團結(jié)構(gòu)已知的情況下，基于兩級信息流理論和最小割分別提出兩個結(jié)構(gòu)洞占據(jù)者的挖掘算法HIS和MaxD。

目前對于結(jié)構(gòu)洞[21-22]的研究中，研究者發(fā)現(xiàn)社團結(jié)構(gòu)與結(jié)構(gòu)洞的屬性存在很大關(guān)系，并提出相應(yīng)算法。如Lou和Tang[20]假設(shè)社團結(jié)構(gòu)已知的情況下，提出兩個結(jié)構(gòu)洞挖掘算法HIS和MaxD。研究者主要考慮單一粒度下的結(jié)構(gòu)洞，然而網(wǎng)絡(luò)的社團結(jié)構(gòu)在不同粒度下的劃分具有很大差異，且層次結(jié)構(gòu)[23]具有嵌套關(guān)系。社團劃分粒度由粗到細時，社團結(jié)構(gòu)的規(guī)模和數(shù)量也隨之變化，在粗粒度下的某個社團，粒度變細時可能劃分為多個社團。如中國的行政區(qū)劃，將全國看作一個大網(wǎng)絡(luò)，可從省、市、縣、鄉(xiāng)等不同大小的區(qū)域描述網(wǎng)絡(luò)。省、市、縣、鄉(xiāng)等分別代表不同粒度下劃分的社團，從不同粒度描述，則網(wǎng)絡(luò)社團結(jié)構(gòu)也會不同。網(wǎng)絡(luò)的層次結(jié)構(gòu)特性對節(jié)點屬性如重要性、中心性等具有重要影響。細粒度下的結(jié)構(gòu)洞占據(jù)者在粗粒度下可能不再跨越結(jié)構(gòu)洞，或結(jié)構(gòu)洞程度降低甚至喪失。

綜上所述，本文在單粒度基礎(chǔ)上，研究多粒度對網(wǎng)絡(luò)中結(jié)構(gòu)洞占據(jù)者跨越結(jié)構(gòu)洞程度的影響。本文提出一種基于社團結(jié)構(gòu)的多粒度結(jié)構(gòu)洞發(fā)現(xiàn)方法MG_MaxD，首先使用分層社團劃分算法得到不同粒度下的社團結(jié)構(gòu)；然后用結(jié)構(gòu)洞發(fā)現(xiàn)方法獲得不同粒度下的結(jié)構(gòu)洞占據(jù)者集合；最后，對結(jié)構(gòu)洞占據(jù)者的跨越結(jié)構(gòu)洞程度的變化規(guī)律進行分析，發(fā)現(xiàn)結(jié)構(gòu)洞占據(jù)者的結(jié)構(gòu)洞程度即結(jié)構(gòu)洞節(jié)點在社團間的優(yōu)勢會隨著粒度的變細而增大。本文使用不同數(shù)據(jù)集，并進行多組對比實驗，驗證實驗結(jié)果。

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

1.1結(jié)構(gòu)洞理論

結(jié)構(gòu)洞理論由美國社會學(xué)家羅納德·博特于1992年在其撰寫的《結(jié)構(gòu)洞：競爭的社會結(jié)構(gòu)》[1]一書中首次提出的。所謂結(jié)構(gòu)洞，即“社交網(wǎng)絡(luò)中某個或某些個體和有些個體發(fā)生直接聯(lián)系，但與其他個體不發(fā)生直接聯(lián)系。無直接或關(guān)系間斷的現(xiàn)象，從網(wǎng)絡(luò)整體看好像網(wǎng)絡(luò)結(jié)構(gòu)中出現(xiàn)了洞穴?！焙唵蔚卣f，結(jié)構(gòu)洞是指兩個關(guān)系人之間的非重復(fù)關(guān)系。由于社交網(wǎng)絡(luò)中存在著不直接或間接連接的關(guān)系，從而使擁有互補資源或信息的個體之間出現(xiàn)了空位，也可看做網(wǎng)絡(luò)中的洞穴。結(jié)構(gòu)洞是信息流動的缺口，跨越結(jié)構(gòu)洞的個體可以獲得不同個體之間存在的異質(zhì)性信息。如圖1所示，網(wǎng)絡(luò)由9個節(jié)點構(gòu)成，除了節(jié)點5以外，其他節(jié)點被分為兩個社團，而這兩個社團內(nèi)的節(jié)點只能通過節(jié)點5產(chǎn)生聯(lián)系，若沒有節(jié)點5，則兩側(cè)社團之間就產(chǎn)生了間隙，形成了結(jié)構(gòu)洞。顯然，節(jié)點5占據(jù)了結(jié)構(gòu)洞的位置。因此，可以通過找到類似節(jié)點5的結(jié)構(gòu)洞占據(jù)者，獲得網(wǎng)絡(luò)中的異質(zhì)性信息和資源。

圖1　結(jié)構(gòu)洞示例Fig.1　Illustration of structural holes

1.2基于社團結(jié)構(gòu)的結(jié)構(gòu)洞占據(jù)者發(fā)現(xiàn)算法

無權(quán)網(wǎng)絡(luò)可以表示為G=(V,E)，含有n個節(jié)點，m條邊。其中V表示網(wǎng)絡(luò)中節(jié)點的集合，E表示網(wǎng)絡(luò)中邊的集合。V={v1,v2,…,vn}，E={e1,e2,…,em}，社團結(jié)構(gòu)為C={C1,C2,…,Cl}。

Lou和Tang[20]認為跨越結(jié)構(gòu)洞的個體在不同社團間的信息傳播中發(fā)揮重要作用，結(jié)構(gòu)洞占據(jù)者在社團間起到橋接作用，去除這些結(jié)構(gòu)洞節(jié)點后，社團間的聯(lián)系將會最小化，他們根據(jù)這個思想并使用最小割提出結(jié)構(gòu)洞發(fā)現(xiàn)方法MaxD。結(jié)合最小割定義，他們提出在去除結(jié)構(gòu)洞結(jié)點后，網(wǎng)絡(luò)G中C的最小割將顯著減小，即最小割的減少量在刪除結(jié)點后將會最大，目標函數(shù)如式(1)所示：

(1)

MaxD算法的具體流程如下所示。

算法1MaxD

輸入網(wǎng)絡(luò)G=(V,E)，結(jié)構(gòu)洞個數(shù)k，社團數(shù)l，社團結(jié)構(gòu)C={Ci}。

輸出Topk個結(jié)構(gòu)洞占據(jù)者集合VSH。

1)初始化VSH為空集；

2)當|VSH|

對每個非空S?{1,2,…,l}，利用源點ES=∪i∈SCi和匯點ET=∪i?SCi在誘導(dǎo)后的圖GVSH上計算最大流；

對每個節(jié)點v∈V添加通過其的流f(v)；

3) 選O(k)個具有最大f值的節(jié)點作候選者D；

4) 計算p*=argminp∈DMC(G(VSH∪{p}),C)；

5) 更新VSH=VSH∪{p*}

MaxD算法的輸入為網(wǎng)絡(luò)G=(V,E)和社團結(jié)構(gòu)C={Ci}，依據(jù)社團結(jié)構(gòu)并結(jié)合最小割理論，最后得到結(jié)構(gòu)洞解集VSH。但現(xiàn)實網(wǎng)絡(luò)中的社團結(jié)構(gòu)存在多粒度，本文主要研究多粒度對結(jié)構(gòu)洞占據(jù)者跨越結(jié)構(gòu)洞程度的影響。

1.3社團劃分算法

本文所使用的社團劃分方法為Shen等[24]提出的能夠同時探測出社團層次性和重疊性的算法EAGLE。通過凝聚的方法劃分社團，研究對象為網(wǎng)絡(luò)中的極大團，通過極大團之間的不斷凝聚來實現(xiàn)社團劃分。EAGLE算法分為2個步驟：1) 生成網(wǎng)絡(luò)的樹狀圖；2) 在生成樹上選擇合適位置斷開，得到相應(yīng)的社團劃分。為了評判社團劃分結(jié)果的質(zhì)量，該算法提出一種新的模塊度指標如式(2)所示：

(2)

式中Ov是節(jié)點v所屬社團的數(shù)目。通常選擇在EQ值最大的位置對生成樹進行切割，進而得到最合理的社團結(jié)構(gòu)。在EAGLE中，將算法應(yīng)用于已找到的社團中去，得到一些規(guī)模更小、聯(lián)系更緊密的子社團，就可得到在不同粒度下的社團結(jié)構(gòu)，即層次化社團結(jié)構(gòu)。不同粒度下會影響網(wǎng)絡(luò)的社團劃分結(jié)果，如粗粒度下的某個社團在細粒度下可能被劃分為多個社團，社團結(jié)構(gòu)變化如圖2和圖3所示。

圖2　粗粒度下的社團結(jié)構(gòu)Fig.2　Community structure in rough granularity

圖3　細粒度下的社團結(jié)構(gòu)Fig.3　Community structure in fine granularity

2多粒度結(jié)構(gòu)洞發(fā)現(xiàn)方法

算法2層次結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)洞發(fā)現(xiàn)方法MG_MaxD

輸入網(wǎng)絡(luò)G=(V,E)，結(jié)構(gòu)洞個數(shù)k，分層數(shù)r

2) 對Ch(1≤h≤r)層網(wǎng)絡(luò)

給每個節(jié)點v∈V初始化流量f(v)=0；

對每個非空Sh?{1,2,…,l}，l為當前層網(wǎng)絡(luò)社團個數(shù)；

對每個節(jié)點v∈V，對節(jié)點v添加通過其的流f(v)。

3) 選擇O(k)個具有最大f值的節(jié)點作為候選者D。

社團結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)最重要和最普遍的拓撲性質(zhì)之一。在信息傳播網(wǎng)中，同一社團內(nèi)的信息傳播較為迅速，而社團間的信息傳播較為緩慢。在分層網(wǎng)絡(luò)中，社團劃分粒度的變化將改變整個網(wǎng)絡(luò)的社團結(jié)構(gòu)，跨越社團的結(jié)構(gòu)洞占據(jù)者屬性也會隨之變化。對分層網(wǎng)絡(luò)中的結(jié)構(gòu)洞占據(jù)者進行發(fā)現(xiàn)及分析可以幫助揭露多粒度網(wǎng)絡(luò)中節(jié)點跨越結(jié)構(gòu)洞程度，即不同粒度下結(jié)構(gòu)洞節(jié)點在社團間信息傳播和異質(zhì)性資源獲取方面優(yōu)勢的變化，以及結(jié)構(gòu)洞位置的變化情況。

在MG_MaxD方法中，使用EAGLE算法首先獲得最優(yōu)模塊度下的社團結(jié)構(gòu)，然后在此社團結(jié)構(gòu)下，將網(wǎng)絡(luò)細化得到較細粒度下的社團結(jié)構(gòu)，重復(fù)此步驟直到獲得前r層的社團結(jié)構(gòu)。根據(jù)獲得的多粒度社團結(jié)構(gòu)，使用MG_MaxD算法獲得網(wǎng)絡(luò)G在不同粒度下的前k個結(jié)構(gòu)洞占據(jù)者。社團劃分粒度越細，則網(wǎng)絡(luò)中的社團個數(shù)越多，且社團規(guī)?？赡軠p小，即粗粒度下的社團在細粒度下可能被劃分為多個社團，使社團結(jié)構(gòu)產(chǎn)生很大變化。

3實驗設(shè)置與結(jié)果分析

3.1數(shù)據(jù)及衡量指標

本文所使用的數(shù)據(jù)包括公用數(shù)據(jù)和實例數(shù)據(jù)。公用數(shù)據(jù)為在清華大學(xué)ArnetMiner(研究者社會網(wǎng)絡(luò)分析與挖掘系統(tǒng))系統(tǒng)下載的數(shù)據(jù)Topic 131和Topic 145，是公用的合著網(wǎng)絡(luò)數(shù)據(jù)集。以論文中的作者作為網(wǎng)絡(luò)的節(jié)點，作者間的合著關(guān)系作為邊。實例數(shù)據(jù)為CCF推薦國際學(xué)術(shù)會議A類的ICML會議從2005年到2014年共10年出版的論文，統(tǒng)計論文標題和文章作者信息，對數(shù)據(jù)進行處理，若兩個作者出現(xiàn)在同一個文章里，則這兩個作者之間有一條邊，依據(jù)這些信息最后構(gòu)建為一個合著網(wǎng)絡(luò)，將數(shù)據(jù)集表示為ICML_10。

實驗數(shù)據(jù)具體信息如表1所示。

表1　數(shù)據(jù)集信息

下面對本文用到的結(jié)構(gòu)洞的度量指標進行介紹。

Rezvani等[17]根據(jù)伯特定義中的個體連接的社團數(shù)和個體的鄰居節(jié)點數(shù)，提出一種新度量指標。伯特提出，一個好的結(jié)構(gòu)洞占據(jù)者應(yīng)該連接許多社團，但為了更有影響力，它連接的社團數(shù)和它的鄰居節(jié)點數(shù)之比應(yīng)該要大。Rezvani等在網(wǎng)絡(luò)社團結(jié)構(gòu)已知的情況下，根據(jù)這個定義提出一個ρ(S)指標(本文中稱為結(jié)構(gòu)洞跨越程度指標)來衡量結(jié)構(gòu)洞占據(jù)者。給定圖G=(V,E)，假設(shè)S為找到的結(jié)構(gòu)洞占據(jù)者集合，那么這個解集的質(zhì)量如式(3)所示：

(3)

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

3.2.1MG_MaxD實驗結(jié)果

考慮到數(shù)據(jù)集的規(guī)模和網(wǎng)絡(luò)結(jié)構(gòu)的合理性，分別求得3種粒度的層次社團結(jié)構(gòu)，由粗到細分別表示為C1、C2和C3，其中C1是模塊度最優(yōu)時的網(wǎng)絡(luò)劃分，C2和C3是對C1進行逐次細化得到的社團結(jié)構(gòu)。使用MG_MaxD方法發(fā)現(xiàn)不同粒度下的前20個結(jié)構(gòu)洞占據(jù)者，根據(jù)ρ(S)指標計算不同粒度下的節(jié)點跨越結(jié)構(gòu)洞程度，最后分析不同粒度下結(jié)構(gòu)洞解集的質(zhì)量。使用EAGLE算法在不同粒度下進行社團劃分，得到Topic 131數(shù)據(jù)集在不同粒度下的社團劃分個數(shù)為|C1|=32，|C2|=97，|C3|=164。

從圖4可以看出，社團劃分粒度越細，結(jié)構(gòu)洞解集中的節(jié)點跨越結(jié)構(gòu)洞的程度越大，且隨著個數(shù)的增加，同一粒度下結(jié)構(gòu)洞解集的質(zhì)量也在不斷下降，但細粒度下的解集質(zhì)量總是保持最佳。Topic 131數(shù)據(jù)集上結(jié)構(gòu)洞解集的ρ(S)指標結(jié)果對比如圖4所示。

圖4　Topic 131在MG_MaxD算法下不同粒度結(jié)構(gòu)洞解集的質(zhì)量(top 20)Fig.4　Performance of structural holes for MG_MaxD on Topic 131 (top 20)

Topic 145數(shù)據(jù)集在不同粒度下的社團劃分個數(shù)為|C1|=50 、|C2|=130、|C3|=251，分別發(fā)現(xiàn)不同粒度下的前20個結(jié)構(gòu)洞占據(jù)者。Topic 145數(shù)據(jù)集上結(jié)構(gòu)洞解集的ρ(S)指標結(jié)果對比如圖5所示。

圖5　Topic 145在MG_MaxD算法下不同粒度結(jié)構(gòu)洞解集的質(zhì)量(top 20)Fig.5　Performance of structural holes for MG_MaxD on Topic 145 (top 20)

ICML_10數(shù)據(jù)集在不同粒度下的社團劃分個數(shù)為|C1|=342、|C2|=565、|C3|=806，分別發(fā)現(xiàn)不同粒度下的前20個結(jié)構(gòu)洞占據(jù)者，圖6顯示ICML_10數(shù)據(jù)集在不同粒度下找到的結(jié)構(gòu)洞占據(jù)者的結(jié)構(gòu)洞程度變化情況，隨著社團劃分粒度的變細，結(jié)構(gòu)洞占據(jù)者解集的ρ(S)值變大。

通過圖4～6可以發(fā)現(xiàn)，細粒度下結(jié)構(gòu)洞占據(jù)者解集的質(zhì)量總是優(yōu)于較粗粒度下的結(jié)構(gòu)洞占據(jù)者。在Topic 131、Topic 145和ICML_10數(shù)據(jù)集上，當社團劃分的粒度最粗時，由于此時的網(wǎng)絡(luò)拓撲結(jié)構(gòu)較為簡單，社團數(shù)較少，而發(fā)現(xiàn)的結(jié)構(gòu)洞占據(jù)者解集的效果并不好，說明此時個體的結(jié)構(gòu)洞作用并不明顯，即結(jié)構(gòu)洞程度較低；而當粒度變細時，網(wǎng)絡(luò)拓撲較為復(fù)雜，社團數(shù)較多，此時個體跨越的社團相對較多，可以更好得獲得異質(zhì)性信息和不同資源，且能更好的發(fā)揮結(jié)構(gòu)洞作用，即細粒度下的結(jié)構(gòu)洞占據(jù)者跨越結(jié)構(gòu)洞的程度較大。對應(yīng)于實際情況，將公司看作網(wǎng)絡(luò)，而公司里還有許多不同部門，部門分為許多工作小組等等。粗粒度下將公司的部門作為節(jié)點，細粒度下可能將個體作為節(jié)點，這對應(yīng)于不同粒度的層次結(jié)構(gòu)，而個體在網(wǎng)絡(luò)中的屬性關(guān)系和結(jié)構(gòu)洞程度會不斷變化。

圖6　ICML_10在MG_MaxD算法下不同粒度結(jié)構(gòu)洞解集的質(zhì)量(top 20)Fig.6　Performance of structural holes for MG_MaxD on ICML_10 (top 20)

3.2.2HIS對比實驗結(jié)果

為了驗證上面結(jié)論的可靠性，本文使用文獻[20]中的HIS算法進行對比試驗，分別在Topic 131、Topic 145和ICML_10數(shù)據(jù)集上進行實驗。當網(wǎng)絡(luò)劃分粒度變化時，網(wǎng)絡(luò)社團結(jié)構(gòu)也會發(fā)生變化，由于HIS算法中節(jié)點的重要性初始化是相對于社團的，所以HIS算法對社團結(jié)構(gòu)的變化會更加敏感。使用HIS算法進行對比可以有效地驗證上面結(jié)論。統(tǒng)計HIS算法在不同粒度下發(fā)現(xiàn)的結(jié)構(gòu)洞，并使用ρ(S)指標對結(jié)構(gòu)洞解集進行衡量，實驗結(jié)果如圖7～9所示。

圖7　Topic 131在HIS算法下不同粒度結(jié)構(gòu)洞解集的質(zhì)量(top 20)Fig.7　Performance of structural holes for HIS on Topic 131 (top 20)

圖7～9顯示在不同數(shù)據(jù)集上，使用HIS算法找到的前20個結(jié)構(gòu)洞解集的ρ(S)指標變化情況，可以發(fā)現(xiàn)隨著社團劃分粒度的變粗，HIS算法找到的結(jié)構(gòu)洞解集的質(zhì)量也隨之下降。粒度越粗，結(jié)構(gòu)洞解集的ρ(S)越低，則節(jié)點跨越的結(jié)構(gòu)洞的可能性越低。說明不同粒度下的網(wǎng)絡(luò)層次結(jié)構(gòu)對節(jié)點的結(jié)構(gòu)洞程度會產(chǎn)生重要影響。

圖8　Topic 145在HIS算法下不同粒度結(jié)構(gòu)洞解集的質(zhì)量(top 20)Fig.8　Performance of structural holes for HIS on Topic 145 (top 20)

圖9　ICML_10在HIS算法下不同粒度結(jié)構(gòu)洞解集的質(zhì)量(top 20)Fig.9　Performance of structural holes for HIS on ICML_10 (top 20)

3.2.3模塊度及社團數(shù)對結(jié)構(gòu)洞的影響

本文在T131、T145數(shù)據(jù)集上，考慮多粒度下社團劃分質(zhì)量和結(jié)構(gòu)洞解集質(zhì)量之間的關(guān)系，即網(wǎng)絡(luò)模塊度和ρ(S)變化情況。選取MG_MaxD和HIS算法在兩個數(shù)據(jù)集，和5種社團劃分結(jié)果的模塊度下發(fā)現(xiàn)的前20個結(jié)構(gòu)洞占據(jù)者，實驗結(jié)果如圖10和圖11所示。從圖10和圖11可以看出，模塊度越大說明社團劃分結(jié)果越好，但結(jié)構(gòu)洞解集質(zhì)量不斷降低。圖10顯示在T131數(shù)據(jù)集中，當模塊度為0.468時，此時社團劃分質(zhì)量最差，但MG_MaxD和HIS的結(jié)構(gòu)洞解集的質(zhì)量最佳，而隨著模塊度提高，這兩個算法的解集質(zhì)量也隨之下降；圖11顯示在T145數(shù)據(jù)集中也具有相同規(guī)律，且發(fā)現(xiàn)當模塊度為0.324時，MG_MaxD和HIS的結(jié)構(gòu)洞解集的質(zhì)量最差。通過兩組實驗對比，可以發(fā)現(xiàn)模塊度與結(jié)構(gòu)洞解集的質(zhì)量存在一定關(guān)系，在尋找網(wǎng)絡(luò)中的結(jié)構(gòu)洞時應(yīng)結(jié)合社團劃分結(jié)果的模塊度因素，并選擇合適的社團劃分粒度。

圖10　T131數(shù)據(jù)集多粒度下不同算法對比結(jié)果(top 20)Fig.10　Comparison of results of different algorithms on T131 in multi-granularity (top 20)

圖11　T145數(shù)據(jù)集多粒度下不同算法對比結(jié)果(top 20)Fig.11　Comparison of results of different algorithms on T145 in multi-granularity (top 20)

為驗證單一粒度下社團數(shù)對結(jié)構(gòu)洞解集質(zhì)量的影響，本文使用Fast-Newman算法[27]和Blondel算法[28]分別對T131數(shù)據(jù)集和T145數(shù)據(jù)集的原網(wǎng)絡(luò)進行社團劃分，并獲得單一粒度下相應(yīng)的社團結(jié)構(gòu)，使用MG_MaxD算法獲得單一粒度下的結(jié)構(gòu)洞占據(jù)者，最后對結(jié)構(gòu)洞解集的質(zhì)量進行分析。T131數(shù)據(jù)集在Blondel和Fast-Newman算法下分別得到25和30個社團，T145數(shù)據(jù)集在Blondel和Fast-Newman算法下分別得到16和30個社團。實驗結(jié)果如圖12和圖13所示。

圖12和圖13顯示，由于單粒度下T131和T145數(shù)據(jù)集在兩種社團劃分算法下得到的社團數(shù)相差不大，得到的結(jié)構(gòu)洞解集質(zhì)量也很相近。可以發(fā)現(xiàn)在單一粒度下，社團數(shù)量對結(jié)構(gòu)洞占據(jù)者跨越結(jié)構(gòu)洞程度存在一定影響，從整體上看，當社團數(shù)增加時，結(jié)構(gòu)洞解集質(zhì)量也隨之提高，即節(jié)點跨越結(jié)構(gòu)洞的程度變大。

圖12　T131數(shù)據(jù)集在單粒度下對比結(jié)果(top 20)Fig.12　Comparison of results of T131 in single granularity

圖13　T145數(shù)據(jù)集在單粒度下的對比結(jié)果(top 20)Fig.13　Comparison of results of T131in single granularity (top 20)

通過對比MG_MaxD算法和HIS算法在不同數(shù)據(jù)集上的實驗結(jié)果，發(fā)現(xiàn)在同一網(wǎng)絡(luò)下，不同的社團劃分粒度會影響結(jié)構(gòu)洞占據(jù)者的選取。所以在獲取網(wǎng)絡(luò)中的結(jié)構(gòu)洞占據(jù)者時，由于不同社團劃分粒度將影響節(jié)點跨越結(jié)構(gòu)洞的程度，可以綜合網(wǎng)絡(luò)的多粒度社團劃分結(jié)構(gòu)，找到合適的粒度，發(fā)現(xiàn)更加準確的結(jié)構(gòu)洞占據(jù)者。

4結(jié)束語

本文主要研究了多粒度對結(jié)構(gòu)洞占據(jù)者跨越結(jié)構(gòu)洞程度的影響，從社交網(wǎng)絡(luò)的結(jié)構(gòu)洞理論出發(fā)，考慮到不同社團劃分粒度將影響結(jié)構(gòu)洞占據(jù)者的選取，在多粒度社團劃分的基礎(chǔ)上，提出從多粒度角度分析結(jié)構(gòu)洞占據(jù)者的方法。在不同數(shù)據(jù)集上進行實驗，對結(jié)果進行分析，發(fā)現(xiàn)不同粒度的社團劃分將影響節(jié)點跨越結(jié)構(gòu)洞的程度。通過多組對比實驗發(fā)現(xiàn)，在細粒度上，結(jié)構(gòu)洞解集中的節(jié)點的結(jié)構(gòu)洞程度較高，而在粗粒度上，由于將整個網(wǎng)絡(luò)粗化，減弱了節(jié)點的結(jié)構(gòu)洞效果。探討多粒度下的結(jié)構(gòu)洞占據(jù)者的結(jié)構(gòu)洞程度的變化情況，可以幫助研究不同粒度下網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化、網(wǎng)絡(luò)資源的有效獲取和網(wǎng)絡(luò)信息傳播的有效控制。本文在結(jié)構(gòu)洞理論和商空間模型的基礎(chǔ)上，對多粒度網(wǎng)絡(luò)社團的結(jié)構(gòu)洞進行初步研究，發(fā)現(xiàn)不同粒度對節(jié)點的結(jié)構(gòu)洞程度具有重要影響，且分析了模塊度與結(jié)構(gòu)洞占據(jù)者跨越結(jié)構(gòu)洞程度之間的關(guān)系。根據(jù)結(jié)構(gòu)洞跨越程度指標，結(jié)構(gòu)洞解集質(zhì)量隨著社團數(shù)的增加而提高，然而社團數(shù)越多，社團結(jié)構(gòu)卻不一定最優(yōu)，所以需要權(quán)衡社團劃分粒度和結(jié)構(gòu)洞跨越程度指標找到最優(yōu)的結(jié)構(gòu)洞占據(jù)者，這是未來研究的主要工作。

參考文獻:

[1]BURT R S. Structural holes: The social structure of competition[M]//SWEDBERG R. Explorations in economic sociology. New York, USA: Russell Sage Foundations, 1993.

[2]MA Ning, LIU Yijun, RUYA Tian, et al. Recognition of online opinion leaders based on social network analysis[M]//HUANG Runhe, GHORBANI A A, PASI G, et al. Active media technology. Berlin Heidelberg: Springer, 2012: 483-492.

[3]YOO J, KIM W. The effect of structural holes on the corporate performance and strategic alliances network in pharmaceutical industry[J]. International proceedings of economics development and research, 2013, 67(5): 20-24.

[4]CAI Penghua, ZHAO Hai, LIU Hong, et al. Research and analysis of structural hole and matching coefficient[J]. Journal of software engineering and applications, 2010, 3(11): 1080-1087.

[5]TAN YONG, MOOKERJEE V S, SINGH P V. Social capital, structural holes and team composition: collaborative networks of the open source software community[C]//Proceedings of the international conference on information systems. Montreal, Quebec, Canada, 2007: 155.

[6]SHIPILOV A V, LI S X. Can you have your cake and eat it too? Structural holes' influence on status accumulation and market performance in collaborative networks[J]. Administrative science quarterly, 2008, 53(1): 73-108.

[7]RODAN S. Structural holes and managerial performance: identifying the underlying mechanisms[J]. Social networks, 2010, 32(3): 168-179.

[8]KLEINBERG J. Strategic network formation with structural holes[C]//Proceedings of the 9th ACM conference on electronic commerce. New York, USA, 2008: 284-293.

[9]BUSKENS V, VAN DE RIJT A. Dynamics of networks if everyone strives for structural holes1[J]. American journal of sociology, 2008, 114(2): 371-407.

[10]GOYAL S, VEGA-REDONDO F. Structural holes in social networks[J]. Journal of economic theory, 2007, 137(1): 460-492.

[11]BRUGGEMAN J, CARNABUCI G, VERMEULEN I. A note on structural holes theory and niche overlap[J]. Social networks, 2003, 25(1): 97-101.

[12]BURT R S. Structural holes and good ideas1[J]. American journal of sociology, 2004, 110(2): 349-399.

[13]BURT R S. Le capital social, les trous structuraux entrepreneur[J]. Revue francaise de sociologie, 1995, 36(4): 599-628.

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

[15]NEWMAN M E J, WATTS D J, STROGATZ S H. Random graph models of social networks[J]. Proceedings of the national academy of sciences of the united states of America, 2002, 99(3 Suppl. 1): 2566-2572.

[16]鄧世果, 吳干華, 楊會杰. 基于基尼系數(shù)的網(wǎng)絡(luò)結(jié)構(gòu)洞測量[J]. 上海理工大學(xué)學(xué)報, 2011, 33(5): 452-456.

DENG Shiguo, WU Ganhua, YANG Huijie. Gini-coefficient-based measurement of structural holes[J]. Journal of university of shanghai for science and technology, 2011, 33(5): 452-456.

[17]REZVANI M, LIANG Weifa, Xu Wenzheng, et al. Identifying top-k structural hole spanners in large-scale social networks[C]//Proceedings of the 24th ACM international on conference on information and knowledge management. Melbourne, Australia, 2015: 263-272.

[18]ZHANG Ende, WANG Guoren, GAO Kening, et al. Generalized structural holes finding algorithm by bisection in social communities[C]//Proceedings of the 2012 6th international conference on genetic and evolutionary computing. Washington, DC, USA, 2012: 276-279.

[19]HU Renjie, ZHANG Guangyu. Structural holes in directed fuzzy social networks[J]. Journal of applied mathematics, 2014, 2014: 452063.

[20]LOU Tiancheng, TANG Jie. Mining structural hole spanners through information diffusion in social networks[C]//Proceedings of the 22nd international conference on World Wide Web. New York, NY, USA, 2013: 825-836.

[21]韓忠明, 吳楊, 譚旭升, 等. 面向結(jié)構(gòu)洞的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點排序[J]. 物理學(xué)報, 2015, 64(5): 058902.

HAN Zhongming, WU Yang, TAN Xusheng, et al. Ranking key nodes in complex networks by considering structural holes[J]. Acta physica sinica, 2015, 64(5): 058902.

[22]蘇曉萍, 宋玉蓉. 利用鄰域“結(jié)構(gòu)洞”尋找社會網(wǎng)絡(luò)中最具影響力節(jié)點[J]. 物理學(xué)報, 2015, 64(2): 020101.

SU Xiaoping, SONG Yurong. Leveraging neighborhood “structural holes” to identifying key spreaders in social networks[J]. Acta physica sinica, 2015, 64(2): 020101.

[23]CHEN Fengjiao, LI Kan. Detecting hierarchical structure of community members in social networks[J]. Knowledge-based systems, 2015, 87: 3-15.

[24]SHEN Huawei, CHENG Xueqi, CAI Kai, et al. Detect overlapping and hierarchical community structure in networks[J]. Physica a: statistical mechanics and its applications, 2009, 388(24): 5045-5056.

[25]JIANG Feng, CHEN Yuming. Outlier detection based on granular computing and rough set theory[J]. Applied intelligence, 2015, 42(2): 303-322.

[26]QIAN Jiangbo, ZHU Qiang, CHEN Huahui. Multi-granularity locality-sensitive bloom filter[J]. IEEE transactions on computers, 2015, 64(12): 3500-3514.

[27]NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical review E, 2004, 69(6): 066133.

[28]BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast unfolding of communities in large networks[J]. Journal of statistical mechanics: theory and experiment,

2008, 30(2): 155-168.

趙姝，女，1979年生，教授，主要研究方向為機器學(xué)習、社交網(wǎng)絡(luò)、智能計算。主持國家自然科學(xué)基金、省部級項目等多項。已授權(quán)專利1項，獲軟件著作權(quán)3項，發(fā)表學(xué)術(shù)論文20余篇。

趙暉，男，1992年生，碩士研究生，主要研究方向為社交網(wǎng)絡(luò)。

陳潔，女，1982年生，博士研究生，主要研究方向為智能計算。

中文引用格式：趙姝，趙暉，陳潔，等.基于社團結(jié)構(gòu)的多粒度結(jié)構(gòu)洞占據(jù)者發(fā)現(xiàn)及分析[J]. 智能系統(tǒng)學(xué)報， 2016, 11(3): 343-351.

英文引用格式：ZHAO Shu，ZHAO Hui，CHEN Jie，et al.Recognition and analysis of structural hole spanner in multi-granularity based on community structure[J]. CAAI transactions on intelligent systems, 2016,11(3): 343-351.

Recognition and analysis of structural hole spanner in multi-granularity based on community structure

ZHAO Shu1,2， ZHAO Hui1,2， CHEN Jie1,2， CHEN Xi1,2， ZHANG Yanping1,2

(1.School of Computer Science and Technology, Anhui University, Hefei 230601, China; 2.Center of Information Support and Assurance Technology, Anhui University, Hefei 230601, China)

Abstract：Recently, more and more attentions have been paid to research of structural holes, and some methods have been proposed to identify the structural holes based on the community structure. However, the network indicates a hierarchical structure after dividing into communities in different granularity, and influences the nodes’ extent to span structural holes in community structure. A structural hole spanners mining algorithm, named MG_MaxD, is proposed which is in a hierarchical network based on the idea of network community division. First,different granular communities are partitioned by using hierarchical community dividing algorithm (such as EAGLE in this paper). Then, structural hole spanners mining algorithm MG_MaxD is used to identifying the structural hole spanners in each granularity. Finally, using the measurement of the extent of node spanning structural holes to analysis the effect of community structure under different granularity that influence the node’s extent to span structural holes. Experimental results on public data and real data indicate that the extent of nodes to span structural holes namely the node’s advantages will increase with the granularity get thinner.

Keywords：tructural hole; community structure;multi-granularity; hierarchical structure; community division; hierarchical networks; network structure; social network analysis

作者簡介：

中圖分類號：TP393

文獻標志碼：A

文章編號：1673-4785(2016)03-0343-09

通信作者：趙姝.E-mail:gongxs7@163.com.

基金項目：國家高技術(shù)研究發(fā)展計劃項目(2015AA124102);國家自然科學(xué)基金項目(61402006、61175046);安徽省高等學(xué)校省級自然科學(xué)研究項目(KJ2013A016);安徽省自然科學(xué)基金項目(1508085MF113);教育部留學(xué)回國人員科研啟動基金項目.

收稿日期：2016-03-20.網(wǎng)絡(luò)出版日期：2016-05-13.

DOI:10.11992/tis.201603048

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20160513.0910.002.html