社交網絡中結構洞識別研究現狀及展望

仝博

（四川大學計算機學院，成都610065）

0 引言

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

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

1 結構洞識別研究現狀

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

1.1 基于網絡拓撲的結構洞識別研究

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

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

1.2 基于社區的結構洞識別研究

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

基于社區的結構洞識別研究的不足在于社區在網絡中往往是未知的，利用不同的社區發現的算法會得到不同的社區結果。所以Lou 等人[12]識別出的結構洞嚴重依賴于找到的社區的質量。He 等人[13]提出的方法，假定一個節點只能屬于一個社區，但在現實網絡中，一個節點往往屬于多個社區。

1.3 基于網絡形成的結構洞研究

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

基于網絡形成的結構洞研究的不足是需要對很多參數進行多次的調節才能使模型達到最優，這只能在小型網絡中實現，在大規模的網絡中是很難實現的。

2 結構洞識別研究總結和發展趨勢

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

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