張勝兵

(西北工業(yè)大學計算機學院，陜西 西安 710072)

弱連接對不同類型在線社交網(wǎng)絡(luò)信息傳播范圍的影響研究*

張勝兵

(西北工業(yè)大學計算機學院，陜西 西安 710072)

按照連接強度的不同，在線社交網(wǎng)絡(luò)節(jié)點間的連接可以分為強連接和弱連接，可以通過網(wǎng)絡(luò)上兩個節(jié)點的鄰居相對重疊來測量連接強度。實驗表明，弱連接對于信息傳播范圍的影響與具體的網(wǎng)絡(luò)類型有關(guān)系，在基于信息交換的在線社交網(wǎng)絡(luò)中，例如移動電話通信網(wǎng)絡(luò)、Wiki投票網(wǎng)絡(luò)，移去弱連接并不會對信息收斂時傳播的范圍產(chǎn)生明顯的影響；而在基于合作關(guān)系形成的在線社交網(wǎng)絡(luò)中，例如Youtube、Facebook、CDBLP合作網(wǎng)，移去弱連接對信息傳播的范圍有明顯的阻礙作用。

社交網(wǎng)絡(luò)；弱連接；信息傳播

1 引言

弱連接(Weak Ties)理論是由美國社會學家Granovetter S M[1]于1974年提出的，弱連接是一種社會關(guān)系更為廣泛的，然而卻是膚淺的社會認知。研究發(fā)現(xiàn)：弱連接雖然不如強連接那樣堅固，卻有著極快的、可能具有低成本和高效能的傳播效率。在對于弱連接的研究中，弱連接在信息傳播中的影響是廣大學者研究的一個重要方面。然而長期以來由于傳統(tǒng)人類學和社會學研究中的“測不準原理”，使對弱連接的研究陷入困境，無法得到全部準確的數(shù)據(jù)。近年來，由于社交網(wǎng)絡(luò)應(yīng)用的興起，大規(guī)模的社會行為的真實詳細的數(shù)據(jù)可以通過網(wǎng)絡(luò)爬蟲方便地獲取，從而為研究弱連接對信息傳播的影響提供了極大的便利。

本文主要研究了弱連接在不同網(wǎng)絡(luò)結(jié)構(gòu)的社交網(wǎng)絡(luò)上對信息傳播范圍的影響。在本文中，首先提出了社交網(wǎng)絡(luò)信息傳播模型，通過朋友覆蓋率指標定義了連接強度和弱連接，然后在挑選出的四個網(wǎng)絡(luò)數(shù)據(jù)集上進行信息傳播實驗，分別計算去除強連接與去除弱連接前后的信息傳播范圍并分析實驗結(jié)果。

2 弱連接在不同數(shù)據(jù)集上對信息傳播影響不同

弱連接與強連接一樣可以應(yīng)用于各種類型網(wǎng)絡(luò)的研究中，Onnela J P等學者[4]研究了無線移動網(wǎng)絡(luò)中弱連接對網(wǎng)絡(luò)結(jié)構(gòu)和信息傳播的影響，文中以一個國家過去18周所有的電話通話記錄數(shù)據(jù)為實驗基礎(chǔ)，主要研究了在無線通信網(wǎng)絡(luò)中網(wǎng)絡(luò)的結(jié)構(gòu)和節(jié)點相互作用強度間的關(guān)系。文獻中的實驗得出結(jié)論：當從網(wǎng)絡(luò)中移去強連接時，網(wǎng)絡(luò)是健壯的，然而當從網(wǎng)絡(luò)中移去弱連接時，網(wǎng)絡(luò)陷入崩塌。在對信息傳播的影響方面，去掉弱連接可以明顯地減慢信息傳播的速率，然而強連接和弱連接對于信息傳播的范圍都沒有明顯的影響。

Ferrara E等人[3]將弱連接理論應(yīng)用于Facebook上，研究了基于典型朋友關(guān)系的兩個大型數(shù)據(jù)集，發(fā)現(xiàn)去掉弱連接可以有效地減小信息傳播范圍。Zhao Ji-chang等人[6]通過設(shè)計一個信息傳播模型研究了弱連接在在線社交網(wǎng)絡(luò)信息傳播中的作用。文中提出，一方面弱連接作為溝通各個子社區(qū)的橋結(jié)構(gòu)而保證了整個網(wǎng)絡(luò)結(jié)構(gòu)的完整性；而另外一方面將弱連接作為優(yōu)先的信息傳播通道并不會對信息的擴散產(chǎn)生幫助，原因在于信息通常是通過中間連接傳播的。當在網(wǎng)絡(luò)中移去弱連接與移去強連接對比時，移去弱連接后信息傳播的范圍驟減，這說明了弱連接在在線社交網(wǎng)絡(luò)信息傳播中有著重要的作用。

以上研究中存在著一個很明顯的矛盾之處，Onnela J P等學者指出弱連接對信息收斂時信息傳播的范圍沒有影響，然而Ferrara E等人的研究和Zhao Ji-chang等人的研究結(jié)果認為弱連接對于信息收斂時信息傳播的范圍具有很大的影響。矛盾的原因可能是由于其研究是在不同類型在線社交網(wǎng)絡(luò)上進行所引起的，接下來本文將通過實驗分析產(chǎn)生這一矛盾的原因。

3 在線社交網(wǎng)絡(luò)中信息傳播模型和連接強度的定義

本節(jié)首先建立在線社交網(wǎng)絡(luò)信息傳播模型，然后進行連接強度定義，在信息傳播模型上驗證弱連接對于信息傳播范圍的影響。

在驗證弱連接對在線社交網(wǎng)絡(luò)信息傳播的影響時，需要選取一個合適的信息傳播模型來模擬信息的傳播過程。在研究節(jié)點的影響力時，Kempe D等人[5]在論述如何最大化社交網(wǎng)絡(luò)影響力的文獻中采用完全級聯(lián)模型來模擬信息的傳播并且最終利用貪心算法得出一組影響力最大的節(jié)點。由于完全級聯(lián)模型在社交網(wǎng)絡(luò)研究中的廣泛應(yīng)用和其簡單的形式，本文采用完全級聯(lián)模型來研究弱連接對社交網(wǎng)絡(luò)信息傳播范圍的影響。

信息傳播范圍可以歸結(jié)為影響最大化問題，通常，影響最大化的關(guān)鍵是在網(wǎng)絡(luò)中發(fā)現(xiàn)最有影響力的k個節(jié)點。將社區(qū)影響最大化問題變?yōu)檫x擇最好的k個節(jié)點初始激活，目的是在影響最大化過程的最終階段使得社區(qū)覆蓋最大。隨著時間的推移，某節(jié)點的鄰居節(jié)點中有越來越多的節(jié)點變活躍；在某個時間點上，可能使該節(jié)點變活躍。當一個節(jié)點在時間步t首先變活躍時，認為它具有感染力，它具有影響每個不活躍鄰居一次機會。一次成功的激活嘗試將使其鄰居在下一個時間步t+1成為活躍節(jié)點。如果某節(jié)點的多個鄰居節(jié)點在時間步t變活躍，則這些活躍的鄰居節(jié)點按任意順序嘗試激活他們的鄰居節(jié)點，但所有的這些嘗試都發(fā)生在時間步t。一個活躍節(jié)點u對其所有鄰居節(jié)點嘗試激活后，仍保持活躍，但已不具備感染力了。當不存在具備感染力的節(jié)點時，這個過程結(jié)束。

連接強度決定了一條連接的強弱，而連接強度可以通過網(wǎng)絡(luò)上兩個節(jié)點的鄰居相對重疊來測量[1]。我們選取一條邊兩端節(jié)點的鄰居覆蓋率作為評價連接強度的指標。具體公式如下：

(1)

其中，cij是節(jié)點i和節(jié)點j共同的鄰居數(shù)，ki和kj分別是節(jié)點i和節(jié)點j的鄰居數(shù)，wij是兩端分別為節(jié)點i和節(jié)點j的邊的連接強度值[2,4]。

根據(jù)弱連接的理論，如果節(jié)點i和節(jié)點j之間的連接強度高，那么由于兩個節(jié)點經(jīng)常聯(lián)系并且具有許多相同的屬性，兩個節(jié)點的共同朋友也會多，相應(yīng)的邊的連接強度值就會大。相反地，節(jié)點i和節(jié)點j之間的連接強度低，則兩個節(jié)點的共同朋友也少，相應(yīng)的邊的連接強度值就會小。我們把公式(1)定義的wij稱之為朋友覆蓋率指標，該指標的值在一定程度上反映連接的強度，我們把朋友覆蓋率指標值相對較小的連接定義為弱連接。

在信息傳播模型中，隨著信息在社交網(wǎng)絡(luò)上的傳播計算各個邊的連接強度值，具體計算流程如下所示：

步驟1 遍歷數(shù)據(jù)集，建立頭節(jié)點索引表index。因為邊的數(shù)量通常達到幾萬甚至幾十萬，每次順序?qū)ふ翌^節(jié)點的時間開銷很大，索引可以幫助我們在只遍歷一次數(shù)據(jù)集的前提下迅速找到頭節(jié)點所在位置。

步驟2 隨機選擇初始信息傳播節(jié)點并設(shè)置傳播概率prob。在此處為方便對比，我們簡單地設(shè)傳播概率為0.5。

步驟3 采用廣度優(yōu)先的策略模擬完全級聯(lián)模型信息傳播過程。定義待傳播節(jié)點隊列，并且用infect表標記已經(jīng)被感染的節(jié)點。計算已經(jīng)被感染節(jié)點的所有對應(yīng)邊的連接強度。

步驟4 傳播到信息收斂時計算infect表中被感染的節(jié)點數(shù)目和對應(yīng)邊的數(shù)目。

步驟5 考慮到信息傳播過程中的隨機作用，將步驟2～步驟4步過程重復10 000遍，并取其平均值。

4 實驗與結(jié)果分析

本文按照在線社交網(wǎng)絡(luò)的不同應(yīng)用方向，選取了CDBLP網(wǎng)、Arvix網(wǎng)、Wiki投票網(wǎng)絡(luò)和Enron電子郵件網(wǎng)作為數(shù)據(jù)源。CDBLP網(wǎng)是一個以作者為中心的中文學術(shù)作者合作網(wǎng)站，文獻原始數(shù)據(jù)庫中包括了中國計算機領(lǐng)域各著名期刊歷年的文章作者合作數(shù)據(jù)，其中作者的合作關(guān)系所構(gòu)建的合作網(wǎng)絡(luò)可以在一定程度上反映中國計算機領(lǐng)域的學者間合作情況。Arvix數(shù)據(jù)與CDBLP類似，為國外免費論文共享網(wǎng)站。本文將其數(shù)據(jù)集抽象為表現(xiàn)各個作者間合作關(guān)系的無向網(wǎng)絡(luò)。Wiki是一個由世界上眾多志愿者合作完成的在線免費百科全書，在眾多志愿者中有一小部分是管理者。為了能夠使一個普通用戶變成管理者，Wiki使用了一種志愿者間相互投票決定的機制。該數(shù)據(jù)集已經(jīng)在眾多文獻中被用來研究網(wǎng)絡(luò)拓撲特性，比較有代表性。Enron電子郵件網(wǎng)數(shù)據(jù)用來驗證弱連接對通過電子郵件收發(fā)方式進行信息傳播的影響程度。

由于對網(wǎng)絡(luò)特性的相關(guān)分析只有在一個連通子圖下才具有意義，因此在實驗之前需要抽取數(shù)據(jù)集中的最大連通子圖作為實驗對象。本文采用UCINET網(wǎng)絡(luò)分析集成軟件抽取最大子圖作為最終研究數(shù)據(jù)，采用廣度優(yōu)先的搜索方法尋找最大連通子圖，從圖中的任意一個頂點出發(fā)，找出該頂點的等價類，然后再找出該頂點等價類中各元素的等價類，直到頂點等價類為空集，所得結(jié)果即為極大連通子圖。圖1為 CDBLP數(shù)據(jù)的最大連通子圖，有462個節(jié)點、1 950條邊。圖2為Arvix數(shù)據(jù)的最大連通子圖，有5 242個節(jié)點、28 980條邊。圖3為Wiki投票數(shù)據(jù)的最大連通子圖，有7 115個節(jié)點、103 689條邊。圖4為Enron電子郵件網(wǎng)絡(luò)數(shù)據(jù)的最大連通子圖，有36 692個節(jié)點、367 662條邊。

Figure 1 Maximal connected subgraph of CDBLP

Figure 2 Maximal connected subgraph of Arvix

Figure 3 Maximal connected subgraph of Wiki

Figure 4 Maximal connected subgraph of Enron

實驗具體步驟如下：

(1) 通過朋友覆蓋率指標，分別計算社交網(wǎng)絡(luò)各條邊的連接強度。

(2) 按照連接強度值對邊進行排序，當移去強連接時按照強度值從大到小排序，當移去弱連接時按照強度值從小到大排序，從網(wǎng)絡(luò)中分別移去占總邊數(shù)10%、20%、30%、40%、50%、60%、70%、80%的連接，形成信息阻斷網(wǎng)絡(luò)。

(3) 在各個信息阻斷網(wǎng)絡(luò)中模擬信息傳播，直到收斂。

(4) 計算收斂后網(wǎng)絡(luò)中被感染節(jié)點的個數(shù)。

實驗結(jié)果如表1～表4和圖5～圖8所示。

Table 1 Comparison of the influence of weak ties in CDBLP on information spreading

Table 2 Comparison of the influence of weak ties in Arvix on information spreading

Table 3 Comparison of the influence of weak ties in Wiki on information spreading

Table 4 Comparison of the influence of weak ties in Enron on information spreading

Figure 5 Comparison of the influence of weak ties in CDBLP on information spreading

Figure 6 Comparison of the influence of weak ties in Arvix on information spreading

Figure 7 Comparison of the influence of weak ties in Wiki on information spreading

Figure 8 Comparison of the influence of weak ties in Enron on information spreading

在表1和表2中，第一列代表所移去邊的數(shù)量百分比，第二列、第三列分別代表移去強連接和移去弱連接時模擬信息傳播后信息可以覆蓋的范圍。

首先分析CDBLP和Arvix的實驗數(shù)據(jù)。從表1中可以發(fā)現(xiàn)，當網(wǎng)絡(luò)完整時，CDBLP網(wǎng)信息傳播的范圍為334個節(jié)點。當移去總邊數(shù)10%的邊后，移去強連接后信息擴散范圍為322，然而移去弱連接后信息擴散范圍為285，擴散范圍為前者的88%。隨著移去弱連接數(shù)量的增加，弱連接對于信息傳播的阻礙作用也更加顯著。Arvix網(wǎng)實驗數(shù)據(jù)與其類似。從圖5和圖6中可以直觀地看到，在移去弱連接為20%到30%時曲線斜率最陡峭，同時移去強連接的曲線依舊按照基本固定的斜率下降。隨著移去邊條數(shù)的增加，對弱連接的判斷精度也相應(yīng)地降低，因此朋友重疊率算法的效果會漸漸趨于好轉(zhuǎn)。當移去連接數(shù)為50%到80%時，弱連接曲線斜率平緩，原因是此時網(wǎng)絡(luò)已經(jīng)被分割成小塊，弱連接已經(jīng)起到了對信息的抑制作用。當移去連接數(shù)為50%到80%時，強連接曲線斜率平緩并且基本沒有變化，原因可能是移去強連接對信息傳播的阻礙作用并不明顯，其所產(chǎn)生的傳播范圍減小主要是由于連通性降低所致的。

下面分析Wiki投票網(wǎng)和Enron電子郵件網(wǎng)的實驗數(shù)據(jù)。從表3和表4中可以發(fā)現(xiàn)，移去連接后信息傳播的范圍基本沒有變化。無論是移去強連接還是弱連接，對信息傳播的阻礙作用均不明顯，信息傳播的范圍只是隨著移去連接數(shù)據(jù)的增加，圖連通性的減弱而緩慢下降。從圖7和圖8中可以直觀地看到，移去弱連接的曲線并沒有比移去強連接的曲線整體斜率更加陡峭。兩條曲線基本趨勢一致，弱連接并沒有顯示出其對信息傳播過程的阻礙作用。通過實驗數(shù)據(jù)分析我們可以發(fā)現(xiàn)，去掉弱連接或者強連接并不能有效地對此種網(wǎng)絡(luò)的信息傳播范圍產(chǎn)生抑制作用。

實驗結(jié)果表明，去掉弱連接對CDBLP合作網(wǎng)和Arvix網(wǎng)信息阻斷的作用非常明顯，而對于Wiki投票網(wǎng)和Enron電子郵件網(wǎng)，去掉弱連接或者強連接并不能有效地控制網(wǎng)絡(luò)信息的傳播范圍。

這一實驗結(jié)果與之前第2節(jié)中的矛盾結(jié)論相一致。Onnela J P等學者采用的網(wǎng)絡(luò)是移動電話通話記錄所形成的網(wǎng)絡(luò)，這是一個信息網(wǎng)絡(luò)而非實體關(guān)系網(wǎng)絡(luò)。Zhao Ji-chang等人采用的網(wǎng)絡(luò)是Facebook和YouTube朋友關(guān)系網(wǎng)絡(luò)，這是一個實體朋友關(guān)系網(wǎng)絡(luò)。通過本文的實驗結(jié)果分析，可以認為社交網(wǎng)絡(luò)應(yīng)該分為實體關(guān)系網(wǎng)絡(luò)和信息交換網(wǎng)絡(luò)兩種類型，而弱連接對于信息傳播范圍的影響與具體的網(wǎng)絡(luò)類型有關(guān)系。通過作圖分析以及具體數(shù)據(jù)分析總結(jié)兩類網(wǎng)絡(luò)之間存在著如下幾點主要差異：

(1) 實體關(guān)系網(wǎng)絡(luò)中存在著明顯的社區(qū)特性，網(wǎng)絡(luò)由多個聯(lián)系緊密的社區(qū)組成。然而，在信息交換網(wǎng)絡(luò)中并沒有此類特性。

(2) 信息交換網(wǎng)絡(luò)中節(jié)點的度數(shù)差異很大，有很多節(jié)點的度數(shù)在200以上，同時又有很多的節(jié)點度數(shù)僅為1。通過統(tǒng)計分析發(fā)現(xiàn)，信息交換網(wǎng)絡(luò)中度的分布與指數(shù)和冪律分別類似。然而，在實體關(guān)系網(wǎng)絡(luò)中，大多數(shù)的節(jié)點度數(shù)相對穩(wěn)定，通過統(tǒng)計分析發(fā)現(xiàn)，實體關(guān)系網(wǎng)絡(luò)中的度的分布基本服從正態(tài)分布。

中移動電話通話記錄所形成的網(wǎng)絡(luò)與本文中的Wiki投票網(wǎng)絡(luò)和 Enron電子郵件網(wǎng)絡(luò)同屬于信息交換網(wǎng)絡(luò)，在這一類型的網(wǎng)絡(luò)中移去弱連接并不能實現(xiàn)對信息傳播范圍的抑制。而Facebook和YouTube等朋友關(guān)系網(wǎng)絡(luò)與本文中的CDBLP合作網(wǎng)和Arvix網(wǎng)同屬于基于朋友關(guān)系的實體關(guān)系網(wǎng)絡(luò)，在這一類型網(wǎng)絡(luò)中弱連接對于信息傳播起著重要的作用，通過對弱連接的控制可以有效地實現(xiàn)對信息傳播范圍的控制。

5 結(jié)束語

弱連接對于不同類型社交網(wǎng)絡(luò)的信息傳播范圍影響不同，產(chǎn)生這一區(qū)別的原因是因為雖然基于信息交換的社交網(wǎng)絡(luò)在一定程度上反映了社會關(guān)系網(wǎng)絡(luò)的結(jié)構(gòu)，然而其與實體關(guān)系網(wǎng)絡(luò)的結(jié)構(gòu)還是有所區(qū)別，具有不同的網(wǎng)絡(luò)拓撲特性和信息傳播規(guī)律，因此控制弱連接并不能有效地控制信息傳播范圍。

參考文獻:

[1] Granovetter M S. The strength of weak ties[M].Chicago:University of Chicago Press, 1983.

[2] Onnela J P, Saramaki J, Hyvonen J, et al. Structure and tie strengths in mobile communication networks[C]∥Proc of PNAS’07, 2007:7332-7336.

[3] Bakshy E, Rosenn I, Marlow C, et al. The role of social networks in information diffusion[C]∥Proc of the 21st International Conference on World Wide Web, 2012:519-528.

[4] Zhao Ji-chang, Wu Jun-jie, Xu Ke. Weak ties:Subtle role of the information diffusion in online social network[J].Physical Review E, 2010:82(1):016105-016112.

[5] Kempe D, Kleinberg J, Tardos E. Maximizing the spread of

influence through a social network[C]∥Proc of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2003:137-146.

[6] Fu F, Chen X, L iu L, et al. Social dilemmas in an online social network： The structure and evolution of cooperation [J]. Physics Letters A, 2007, 371(1-2)：58-64.

[7] Estrada E, Hatano N. Communicability in complex networks[J]. Physical Review E, 2008, 77(3):036111.

[8] Newman M.Modularity and community structure in networks[J].Proceedings of the National Academy of Sciences, 2006, 103(23):8577-8582.

[9] Pathak N, DeLong C, Banerjee A, et al. Social topics models for community extraction[C]∥Proc of the 2nd SNA-KDD Workshop, 2008:1.

[10] Porter M A, Onnela J P, Mucha P J. Communities in networks[J].Notices of the American Mathematical Society, 2009, 56(9):1082-1097.

[11] Sachan M, Contractor D, Faruquie T A, et al. Probabilistic model for discovering topic based communities in social networks[C]∥Proc of CIKM’11, 2011:2349-2352.

[12] Yang J, Leskovec J. Patterns of temporal variation in online media[C]∥Proc of ACM Conference on Web Search and Data Mining, 2010:177-186.

ZHANG Sheng-bing,born in 1974,PhD,lecturer,his research interests include social network, and P2P network.

Weak ties’ influence on information spreading for different types of online social networks

ZHANG Sheng-bing

(School of Computer Science,Northwestern Polytechnical University,Xi’an 710072,China)

There are strong ties and weak ties in terms of strength between two nodes in online social networks.The strength of ties can be measured by the relative overlap of two neighboring nodes in the network.Our experimental results show that weak ties’ influence on information spreading varies in different online social networks.There is little influence on information diffusion when we remove the weak ties in the information-exchang-oriented online social networks,such as mobile phone communication network and Wiki voting network.The coverage of the information will drop sharply when we remove weak ties in the relationship-oriented online social network,such as YouTube, Facebook and CDBLP cooperation network.

social network;weak ties;information diffusion

1007-130X(2015)01-0042-06

2013-05-03;

2013-08-19基金項目：國家自然科學基金資助項目(61103178)

TP393

A

10.3969/j.issn.1007-130X.2015.01.007

張勝兵(1974-),男,山西運城人，博士，講師，研究方向為社交網(wǎng)絡(luò)和P2P網(wǎng)絡(luò)。E-mail:zhangshengbing@nwpu.edu.cn

通信地址：710072 陜西省西安市西北工業(yè)大學計算機學院

Address:School of Computer Science,Northwestern Polytechnical University,Xi’an 710072,Shaanxi,P.R.China