仝博

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

0 引言

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

這些同時(shí)屬于多個(gè)社區(qū)的用戶，在信息傳播的過(guò)程中充當(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)洞來(lái)解釋社會(huì)資本的差別起源。不同于只屬于一個(gè)社區(qū)的節(jié)點(diǎn)，結(jié)構(gòu)洞節(jié)點(diǎn)可以從多個(gè)社區(qū)中更多和更早地獲取信息，并且可以利用這些信息給自己建立競(jìng)爭(zhēng)優(yōu)勢(shì)，從而獲得更多的收益。例如，在科研合作網(wǎng)絡(luò)中，一個(gè)社區(qū)代表了具有相似研究方向的學(xué)者，那些同時(shí)身處多個(gè)社區(qū)的學(xué)者更容易結(jié)合多個(gè)不同研究領(lǐng)域的思想來(lái)進(jìn)行跨學(xué)科的創(chuàng)新性工作。在公司職場(chǎng)中，那些和多個(gè)部門交流合作的員工，在跨部門協(xié)作中更容易獲得更高的評(píng)價(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)洞識(shí)別研究現(xiàn)狀

最近幾年，由于結(jié)構(gòu)洞的廣泛的應(yīng)用前景，識(shí)別社交網(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ò)中識(shí)別結(jié)構(gòu)洞節(jié)點(diǎn)也是異常困難的。學(xué)者們付出了諸多的努力，對(duì)結(jié)構(gòu)洞有了初步的了解。現(xiàn)在的結(jié)構(gòu)洞識(shí)別研究可以分為以下三類。

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

Goyal 等人[5]將結(jié)構(gòu)洞識(shí)別問(wèn)題定義為存在于不同節(jié)點(diǎn)對(duì)之間的最短路徑上的節(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í)間更是無(wú)法接受，Tang 等人[8]提出只計(jì)算頂點(diǎn)所在的長(zhǎng)度為2 的最短路徑，忽略所有長(zhǎng)度超過(guò)2 的最短路徑。Rezvani 等人[9]提出利用網(wǎng)絡(luò)平均通信距離來(lái)衡量節(jié)點(diǎn)結(jié)構(gòu)洞重要性，在網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)的移除，將會(huì)增加某些節(jié)點(diǎn)間的通信距離。那么致使網(wǎng)絡(luò)間平均通信距離增長(zhǎng)最多的節(jié)點(diǎn)，就是結(jié)構(gòu)洞重要性最大的節(jié)點(diǎn)。由于該問(wè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ǔ)上，將該問(wèn)題表示為了一個(gè)優(yōu)化問(wèn)題，設(shè)計(jì)出了創(chuàng)新的過(guò)濾方法，盡早地過(guò)濾出不太可能的節(jié)點(diǎn)，能夠快速地估計(jì)出最優(yōu)解的上下界，將該問(wèn)題可以推廣到大規(guī)模網(wǎng)絡(luò)中。在真實(shí)數(shù)據(jù)集中的大量實(shí)驗(yàn)上可以表明，該方法可以準(zhǔn)確地捕捉到結(jié)構(gòu)洞的特征，并且計(jì)算迅速。Zhang 等人[11]在符號(hào)網(wǎng)絡(luò)中考慮到用戶間的信任問(wèn)題，在有符號(hào)社交網(wǎng)絡(luò)中的信息傳播受鏈接極性和用戶位置的影響，在傳播過(guò)程中識(shí)別可信的聯(lián)系和不可信的聯(lián)系，進(jìn)而識(shí)別出可信的結(jié)構(gòu)洞。

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

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

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

基于社區(qū)的結(jié)構(gòu)洞識(shí)別研究的不足在于社區(qū)在網(wǎng)絡(luò)中往往是未知的，利用不同的社區(qū)發(fā)現(xiàn)的算法會(huì)得到不同的社區(qū)結(jié)果。所以Lou 等人[12]識(shí)別出的結(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ā)生，如果是直接交換，則收益兩者平分。如果是通過(guò)中介進(jìn)行間接交換，則包括中介在內(nèi)，一起平分收益，一個(gè)節(jié)點(diǎn)可以充當(dāng)多個(gè)節(jié)點(diǎn)之間的中介，那么成員之間將傾向于更短的路徑。在沒(méi)有鏈路容量限制的條件下，會(huì)形成一個(gè)星型網(wǎng)絡(luò)。然而，這顯然和實(shí)際網(wǎng)絡(luò)不同，為此Kleinberg 等人[14]借鑒博弈論中的方法提出一個(gè)模型來(lái)刻畫充當(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)衡。通過(guò)理論分析和計(jì)算實(shí)驗(yàn)，該收益與經(jīng)過(guò)此節(jié)點(diǎn)兩跳的路徑數(shù)量成正比。此外，即使在相同的環(huán)境下，個(gè)體也會(huì)不斷分化，占據(jù)不同的社會(huì)階層，并獲得不同的回報(bào)。

基于網(wǎng)絡(luò)形成的結(jié)構(gòu)洞研究的不足是需要對(duì)很多參數(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)洞識(shí)別研究總結(jié)和發(fā)展趨勢(shì)

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

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