張勝兵

(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，陜西 西安 710072)

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

張勝兵

(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，陜西 西安 710072)

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)與結(jié)果分析

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

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

實(shí)驗(yàn)具體步驟如下：

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

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

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

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

實(shí)驗(yàn)結(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ù)量百分比，第二列、第三列分別代表移去強(qiáng)連接和移去弱連接時(shí)模擬信息傳播后信息可以覆蓋的范圍。

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

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

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

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

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

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

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

5 結(jié)束語

弱連接對于不同類型社交網(wǎng)絡(luò)的信息傳播范圍影響不同，產(chǎn)生這一區(qū)別的原因是因?yàn)殡m然基于信息交換的社交網(wǎng)絡(luò)在一定程度上反映了社會關(guān)系網(wǎng)絡(luò)的結(jié)構(gòu)，然而其與實(shí)體關(guān)系網(wǎng)絡(luò)的結(jié)構(gòu)還是有所區(qū)別，具有不同的網(wǎng)絡(luò)拓?fù)涮匦院托畔鞑ヒ?guī)律，因此控制弱連接并不能有效地控制信息傳播范圍。

參考文獻(xiàn):

[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基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61103178)

TP393

A

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

張勝兵(1974-),男,山西運(yùn)城人，博士，講師，研究方向?yàn)樯缃痪W(wǎng)絡(luò)和P2P網(wǎng)絡(luò)。E-mail:zhangshengbing@nwpu.edu.cn

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

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