弱連接對不同類型在線社交網絡信息傳播范圍的影響研究*

張勝兵

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

弱連接對不同類型在線社交網絡信息傳播范圍的影響研究*

張勝兵

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

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

社交網絡；弱連接；信息傳播

1 引言

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

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

2 弱連接在不同數據集上對信息傳播影響不同

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

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

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

3 在線社交網絡中信息傳播模型和連接強度的定義

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

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

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

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

(1)

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

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

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

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

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

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

步驟4 傳播到信息收斂時計算infect表中被感染的節點數目和對應邊的數目。

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

4 實驗與結果分析

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

由于對網絡特性的相關分析只有在一個連通子圖下才具有意義，因此在實驗之前需要抽取數據集中的最大連通子圖作為實驗對象。本文采用UCINET網絡分析集成軟件抽取最大子圖作為最終研究數據，采用廣度優先的搜索方法尋找最大連通子圖，從圖中的任意一個頂點出發，找出該頂點的等價類，然后再找出該頂點等價類中各元素的等價類，直到頂點等價類為空集，所得結果即為極大連通子圖。圖1為 CDBLP數據的最大連通子圖，有462個節點、1 950條邊。圖2為Arvix數據的最大連通子圖，有5 242個節點、28 980條邊。圖3為Wiki投票數據的最大連通子圖，有7 115個節點、103 689條邊。圖4為Enron電子郵件網絡數據的最大連通子圖，有36 692個節點、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) 通過朋友覆蓋率指標，分別計算社交網絡各條邊的連接強度。

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

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

(4) 計算收斂后網絡中被感染節點的個數。

實驗結果如表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中，第一列代表所移去邊的數量百分比，第二列、第三列分別代表移去強連接和移去弱連接時模擬信息傳播后信息可以覆蓋的范圍。

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

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

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

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

(1) 實體關系網絡中存在著明顯的社區特性，網絡由多個聯系緊密的社區組成。然而，在信息交換網絡中并沒有此類特性。

(2) 信息交換網絡中節點的度數差異很大，有很多節點的度數在200以上，同時又有很多的節點度數僅為1。通過統計分析發現，信息交換網絡中度的分布與指數和冪律分別類似。然而，在實體關系網絡中，大多數的節點度數相對穩定，通過統計分析發現，實體關系網絡中的度的分布基本服從正態分布。

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

5 結束語

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

參考文獻:

[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-),男,山西運城人，博士，講師，研究方向為社交網絡和P2P網絡。E-mail:zhangshengbing@nwpu.edu.cn

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

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