社交網(wǎng)絡(luò)中結(jié)構(gòu)洞識別研究現(xiàn)狀及展望

仝博

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

0 引言

近年來，隨著信息技術(shù)的高速發(fā)展和通訊設(shè)備的成本不斷下降，推動了如新浪微博、知乎、Facebook、Twitter 等各種社交網(wǎng)絡(luò)的快速普及。社交網(wǎng)絡(luò)中用戶規(guī)模龐大且還是快速增長中，據(jù)統(tǒng)計，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]，例如在一個社交網(wǎng)絡(luò)中，具有同樣的興趣愛好、成長背景、行為習慣的用戶更容易成為朋友，形成一個社區(qū)。用戶在社區(qū)中與同社區(qū)的用戶交流更加頻繁，聯(lián)系更加緊密，而較少地和其他社區(qū)的用戶交流，即社區(qū)中關(guān)系緊密，社區(qū)間關(guān)系稀疏。當信息在社交網(wǎng)絡(luò)中傳播時，社區(qū)對信息的傳播具有重要的作用。由于同一社區(qū)內(nèi)用戶聯(lián)系更加緊密，那么信息就會在社區(qū)內(nèi)部迅速傳播。此外，信息可以通過同時存在于多個社區(qū)內(nèi)的用戶，從一個社區(qū)傳遞到另一個社區(qū)。

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

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

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

1.1 基于網(wǎng)絡(luò)拓撲的結(jié)構(gòu)洞識別研究

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

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

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

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

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

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

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

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

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

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

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