仝博

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0 引言

近年來，隨著信息技術(shù)的高速發(fā)展和通訊設(shè)備的成本不斷下降，推動(dòng)了如新浪微博、知乎、Facebook、Twitter 等各種社交網(wǎng)絡(luò)的快速普及。社交網(wǎng)絡(luò)中用戶規(guī)模龐大且還是快速增長中，據(jù)統(tǒng)計(jì)，2018 年全球社交網(wǎng)絡(luò)用戶已經(jīng)超過31.2 億且平均每天仍有大約100 萬社交網(wǎng)絡(luò)新增用戶。這些社交網(wǎng)絡(luò)隨著用戶的快速增長，產(chǎn)生了海量數(shù)據(jù)并存儲起來。社交網(wǎng)絡(luò)中關(guān)系復(fù)雜，例如Facebook 擁有超過10 億用戶和1000 億的好友關(guān)系。這些網(wǎng)絡(luò)中呈現(xiàn)出了社區(qū)的特性[1-2]，例如在一個(gè)社交網(wǎng)絡(luò)中，具有同樣的興趣愛好、成長背景、行為習(xí)慣的用戶更容易成為朋友，形成一個(gè)社區(qū)。用戶在社區(qū)中與同社區(qū)的用戶交流更加頻繁，聯(lián)系更加緊密，而較少地和其他社區(qū)的用戶交流，即社區(qū)中關(guān)系緊密，社區(qū)間關(guān)系稀疏。當(dāng)信息在社交網(wǎng)絡(luò)中傳播時(shí)，社區(qū)對信息的傳播具有重要的作用。由于同一社區(qū)內(nèi)用戶聯(lián)系更加緊密，那么信息就會在社區(qū)內(nèi)部迅速傳播。此外，信息可以通過同時(shí)存在于多個(gè)社區(qū)內(nèi)的用戶，從一個(gè)社區(qū)傳遞到另一個(gè)社區(qū)。

這些同時(shí)屬于多個(gè)社區(qū)的用戶，在信息傳播的過程中充當(dāng)了橋梁作用的節(jié)點(diǎn)被稱為結(jié)構(gòu)洞（Structural Holes）[3-4]。在弱關(guān)系理論（Weak Tie）的基礎(chǔ)上，Burt[3-4]首先提出結(jié)構(gòu)洞的概念，并利用結(jié)構(gòu)洞來解釋社會資本的差別起源。不同于只屬于一個(gè)社區(qū)的節(jié)點(diǎn)，結(jié)構(gòu)洞節(jié)點(diǎn)可以從多個(gè)社區(qū)中更多和更早地獲取信息，并且可以利用這些信息給自己建立競爭優(yōu)勢，從而獲得更多的收益。例如，在科研合作網(wǎng)絡(luò)中，一個(gè)社區(qū)代表了具有相似研究方向的學(xué)者，那些同時(shí)身處多個(gè)社區(qū)的學(xué)者更容易結(jié)合多個(gè)不同研究領(lǐng)域的思想來進(jìn)行跨學(xué)科的創(chuàng)新性工作。在公司職場中，那些和多個(gè)部門交流合作的員工，在跨部門協(xié)作中更容易獲得更高的評價(jià)和更快地晉升[4-5]。此外，在社交網(wǎng)絡(luò)中，當(dāng)謠言在網(wǎng)絡(luò)中傳播時(shí)，我們只需要在關(guān)鍵的結(jié)構(gòu)洞節(jié)點(diǎn)進(jìn)行信息審查，而不必審查所有的信息，即可有效地阻礙謠言信息在網(wǎng)絡(luò)中的傳播。

1 結(jié)構(gòu)洞識別研究現(xiàn)狀

最近幾年，由于結(jié)構(gòu)洞的廣泛的應(yīng)用前景，識別社交網(wǎng)絡(luò)中關(guān)鍵的結(jié)構(gòu)洞節(jié)點(diǎn)引起了專家學(xué)者們的注意。在提出結(jié)構(gòu)洞概念后，Burt 隨后又將結(jié)構(gòu)洞理論進(jìn)一步的擴(kuò)展[6-7]。隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，在大規(guī)模網(wǎng)絡(luò)中識別結(jié)構(gòu)洞節(jié)點(diǎn)也是異常困難的。學(xué)者們付出了諸多的努力，對結(jié)構(gòu)洞有了初步的了解?，F(xiàn)在的結(jié)構(gòu)洞識別研究可以分為以下三類。

1.1 基于網(wǎng)絡(luò)拓?fù)涞慕Y(jié)構(gòu)洞識別研究

Goyal 等人[5]將結(jié)構(gòu)洞識別問題定義為存在于不同節(jié)點(diǎn)對之間的最短路徑上的節(jié)點(diǎn)，當(dāng)一個(gè)節(jié)點(diǎn)位于網(wǎng)絡(luò)中越多的最短路徑上，那么該節(jié)點(diǎn)的結(jié)構(gòu)洞重要性就越高。由于在網(wǎng)絡(luò)中尋找所有節(jié)點(diǎn)的最短路徑是非常消耗時(shí)間的，并且當(dāng)網(wǎng)絡(luò)規(guī)模很大時(shí)，消耗的時(shí)間更是無法接受，Tang 等人[8]提出只計(jì)算頂點(diǎn)所在的長度為2 的最短路徑，忽略所有長度超過2 的最短路徑。Rezvani 等人[9]提出利用網(wǎng)絡(luò)平均通信距離來衡量節(jié)點(diǎn)結(jié)構(gòu)洞重要性，在網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)的移除，將會增加某些節(jié)點(diǎn)間的通信距離。那么致使網(wǎng)絡(luò)間平均通信距離增長最多的節(jié)點(diǎn)，就是結(jié)構(gòu)洞重要性最大的節(jié)點(diǎn)。由于該問題是NP-難的，所以采取貪心算法迭代找出top-k個(gè)結(jié)構(gòu)洞。此外，利用節(jié)點(diǎn)的有界逆接近中心性和網(wǎng)絡(luò)中關(guān)節(jié)點(diǎn)的特殊性質(zhì)以及改進(jìn)后的深度優(yōu)先搜索方法，提出了兩種快速且可擴(kuò)展的線性時(shí)間的算法。Xu等人[10]在基于Rezvani 等的基礎(chǔ)上，將該問題表示為了一個(gè)優(yōu)化問題，設(shè)計(jì)出了創(chuàng)新的過濾方法，盡早地過濾出不太可能的節(jié)點(diǎn)，能夠快速地估計(jì)出最優(yōu)解的上下界，將該問題可以推廣到大規(guī)模網(wǎng)絡(luò)中。在真實(shí)數(shù)據(jù)集中的大量實(shí)驗(yàn)上可以表明，該方法可以準(zhǔn)確地捕捉到結(jié)構(gòu)洞的特征，并且計(jì)算迅速。Zhang 等人[11]在符號網(wǎng)絡(luò)中考慮到用戶間的信任問題，在有符號社交網(wǎng)絡(luò)中的信息傳播受鏈接極性和用戶位置的影響，在傳播過程中識別可信的聯(lián)系和不可信的聯(lián)系，進(jìn)而識別出可信的結(jié)構(gòu)洞。

基于網(wǎng)絡(luò)拓?fù)涞慕Y(jié)構(gòu)洞識別研究的不足在于網(wǎng)絡(luò)中節(jié)點(diǎn)與節(jié)點(diǎn)之間、節(jié)點(diǎn)與社區(qū)之間、社區(qū)與社區(qū)之間的連邊僅表示兩者有相互聯(lián)系的可能，不代表一定會產(chǎn)生信息交換。那么僅通過網(wǎng)絡(luò)拓?fù)浞椒ㄗR別出的結(jié)構(gòu)洞未必能帶來實(shí)際的收益。為了確保識別出的結(jié)構(gòu)洞能夠帶來收益，不僅需要在網(wǎng)絡(luò)拓?fù)渖夏軌蜻B接多個(gè)社區(qū)，而且還需要和這些社區(qū)建立并保持穩(wěn)定可信的聯(lián)系。

1.2 基于社區(qū)的結(jié)構(gòu)洞識別研究

Lou 等人[12]假設(shè)社交網(wǎng)絡(luò)中所有的社區(qū)都是給定的，提出了第一個(gè)社交網(wǎng)絡(luò)中結(jié)構(gòu)洞識別模型。他們模型的目標(biāo)是利用一個(gè)效用函數(shù)來最大化的衡量結(jié)構(gòu)洞節(jié)點(diǎn)跨越社區(qū)的程度。效用函數(shù)是在網(wǎng)絡(luò)中找到一組節(jié)點(diǎn)，刪除這些節(jié)點(diǎn)會使得網(wǎng)絡(luò)中不同的社區(qū)之間的邊的數(shù)量得到最大的減少。為了實(shí)現(xiàn)該效用函數(shù)，Lou等人開發(fā)了兩個(gè)實(shí)例模型。對于第一個(gè)實(shí)例模型，給出了精確的算法來求解，并證明了該算法的收斂性。對于第二個(gè)實(shí)例模型，證明了其最優(yōu)化是NP-難的，并設(shè)計(jì)了一個(gè)可證明的近似保證的有效算法。除此之外，Lou等人在Twitter 的實(shí)驗(yàn)表明，在Twitter 網(wǎng)絡(luò)中1%的結(jié)構(gòu)洞節(jié)點(diǎn)控制了25%的信息傳播，進(jìn)一步說明結(jié)構(gòu)洞在社交網(wǎng)絡(luò)中的重要性。He 等人[13]提出一種新的諧波模塊化（Harmonic Modularity）方法，只利用網(wǎng)絡(luò)拓?fù)湫畔?，即可同時(shí)識別出社區(qū)和結(jié)構(gòu)洞節(jié)點(diǎn)。假設(shè)一個(gè)節(jié)點(diǎn)只屬于一個(gè)社區(qū)，利用調(diào)和函數(shù)來衡量社區(qū)結(jié)構(gòu)的平滑程度并獲得社區(qū)指標(biāo)。然后重點(diǎn)研究連接多個(gè)社區(qū)的節(jié)點(diǎn)在社區(qū)間交互作用，來判斷是否是結(jié)構(gòu)洞。

基于社區(qū)的結(jié)構(gòu)洞識別研究的不足在于社區(qū)在網(wǎng)絡(luò)中往往是未知的，利用不同的社區(qū)發(fā)現(xiàn)的算法會得到不同的社區(qū)結(jié)果。所以Lou 等人[12]識別出的結(jié)構(gòu)洞嚴(yán)重依賴于找到的社區(qū)的質(zhì)量。He 等人[13]提出的方法，假定一個(gè)節(jié)點(diǎn)只能屬于一個(gè)社區(qū)，但在現(xiàn)實(shí)網(wǎng)絡(luò)中，一個(gè)節(jié)點(diǎn)往往屬于多個(gè)社區(qū)。

1.3 基于網(wǎng)絡(luò)形成的結(jié)構(gòu)洞研究

Goyal 等人[5]提出了一個(gè)網(wǎng)絡(luò)形成模型，在貨物交易或者信息交換中，當(dāng)成員之間產(chǎn)生關(guān)聯(lián)，交換才能發(fā)生，如果是直接交換，則收益兩者平分。如果是通過中介進(jìn)行間接交換，則包括中介在內(nèi)，一起平分收益，一個(gè)節(jié)點(diǎn)可以充當(dāng)多個(gè)節(jié)點(diǎn)之間的中介，那么成員之間將傾向于更短的路徑。在沒有鏈路容量限制的條件下，會形成一個(gè)星型網(wǎng)絡(luò)。然而，這顯然和實(shí)際網(wǎng)絡(luò)不同，為此Kleinberg 等人[14]借鑒博弈論中的方法提出一個(gè)模型來刻畫充當(dāng)結(jié)構(gòu)洞的節(jié)點(diǎn)收益。當(dāng)網(wǎng)絡(luò)中原本不相連的各方，為了收益，網(wǎng)絡(luò)中的個(gè)體有動(dòng)機(jī)形成連接。Kleinberg 等人將收益建模為連接不相鄰節(jié)點(diǎn)的好處和維護(hù)連接成本之間的權(quán)衡。通過理論分析和計(jì)算實(shí)驗(yàn)，該收益與經(jīng)過此節(jié)點(diǎn)兩跳的路徑數(shù)量成正比。此外，即使在相同的環(huán)境下，個(gè)體也會不斷分化，占據(jù)不同的社會階層，并獲得不同的回報(bào)。

基于網(wǎng)絡(luò)形成的結(jié)構(gòu)洞研究的不足是需要對很多參數(shù)進(jìn)行多次的調(diào)節(jié)才能使模型達(dá)到最優(yōu)，這只能在小型網(wǎng)絡(luò)中實(shí)現(xiàn)，在大規(guī)模的網(wǎng)絡(luò)中是很難實(shí)現(xiàn)的。

2 結(jié)構(gòu)洞識別研究總結(jié)和發(fā)展趨勢

經(jīng)過對上述社交網(wǎng)絡(luò)中結(jié)構(gòu)洞識別研究的分析，將結(jié)構(gòu)洞識別分為三類：基于網(wǎng)絡(luò)拓?fù)涞慕Y(jié)構(gòu)洞識別研究、基于社區(qū)的結(jié)構(gòu)洞識別研究和基于網(wǎng)絡(luò)形成的結(jié)構(gòu)洞研究?；诰W(wǎng)絡(luò)拓?fù)涞慕Y(jié)構(gòu)洞識別研究最為常見，類似于介數(shù)中心性和接近中心性，僅根據(jù)節(jié)點(diǎn)在網(wǎng)絡(luò)拓?fù)渲械奈恢?，來判斷是否為結(jié)構(gòu)洞。這種方法便于理解，但可擴(kuò)展性差，在大規(guī)模網(wǎng)絡(luò)中需要耗費(fèi)大量的時(shí)間計(jì)算。只能采取啟發(fā)式算法和近似算法來加速計(jì)算?；谏鐓^(qū)的結(jié)構(gòu)洞識別研究和基于網(wǎng)絡(luò)形成的結(jié)構(gòu)洞研究局限更多，不僅不適合在大規(guī)模網(wǎng)絡(luò)中運(yùn)行，而且獲得結(jié)果并不穩(wěn)定。通過網(wǎng)絡(luò)拓?fù)鋪碜R別的結(jié)構(gòu)洞的過程中，連接多個(gè)社區(qū)的節(jié)點(diǎn)比只在一個(gè)社區(qū)內(nèi)的節(jié)點(diǎn)是更好的結(jié)構(gòu)洞，因?yàn)樵摴?jié)點(diǎn)的移除將會顯著增加社區(qū)間的節(jié)點(diǎn)距離。連接大型社區(qū)的節(jié)點(diǎn)比連接較小型社區(qū)的節(jié)點(diǎn)是更好地結(jié)構(gòu)洞，因?yàn)槠湟瞥龑?dǎo)致網(wǎng)絡(luò)中更多節(jié)點(diǎn)的斷開。連接多個(gè)社區(qū)的節(jié)點(diǎn)比連接少數(shù)社區(qū)的節(jié)點(diǎn)是更好的結(jié)構(gòu)洞，因?yàn)樗囊瞥龑⒃黾痈嗌鐓^(qū)間的距離。由此可見，目前在社交網(wǎng)絡(luò)中結(jié)構(gòu)洞識別研究仍處于初級階段，對結(jié)構(gòu)洞的衡量還處于定性研究而非定量研究。

介于目前結(jié)構(gòu)洞識別研究的不足，未來在社交網(wǎng)絡(luò)中結(jié)構(gòu)洞識別研究不僅要考慮網(wǎng)絡(luò)拓?fù)?，還需要考慮節(jié)點(diǎn)間關(guān)系強(qiáng)度和信息是否可靠。只有保持穩(wěn)定的聯(lián)系才能讓結(jié)構(gòu)洞產(chǎn)生收益。目前對結(jié)構(gòu)洞的定性研究過于粗糙，需要精確地衡量節(jié)點(diǎn)結(jié)構(gòu)洞重要性。只有對結(jié)構(gòu)洞節(jié)點(diǎn)精確定義和準(zhǔn)確計(jì)算重要性才能加深對結(jié)構(gòu)洞的認(rèn)識，產(chǎn)生更多更有意義的應(yīng)用。此外，隨著網(wǎng)絡(luò)規(guī)模的不斷迅速擴(kuò)大，所以需要設(shè)計(jì)出適合于大規(guī)模網(wǎng)絡(luò)中的快速、有效且可擴(kuò)展的識別算法。