楊　凱,劉曉露,林堅(jiān)洪,成　曦,郭　強(qiáng),劉建國

(上海理工大學(xué)復(fù)雜系統(tǒng)科學(xué)研究中心，上海 200093)

?

“冰桶挑戰(zhàn)”誘導(dǎo)的社交網(wǎng)絡(luò)演化分析

楊凱,劉曉露,林堅(jiān)洪,成曦,郭強(qiáng),劉建國

(上海理工大學(xué)復(fù)雜系統(tǒng)科學(xué)研究中心，上海 200093)

摘要:考慮社交網(wǎng)絡(luò)初始階段的演化過程對于定量認(rèn)識和理解人際關(guān)系的形成與演化的重要意義，搜集“冰桶挑戰(zhàn)”事件國內(nèi)從事件發(fā)起到第6天的數(shù)據(jù)。以挑戰(zhàn)者為節(jié)點(diǎn)，點(diǎn)名關(guān)系為邊構(gòu)造社交網(wǎng)絡(luò)。通過分析該網(wǎng)絡(luò)的統(tǒng)計(jì)指標(biāo)，發(fā)現(xiàn)網(wǎng)絡(luò)密度一直減??；網(wǎng)絡(luò)效率先減小，后又緩慢增加；連通子圖的數(shù)量先迅速增加，最高增加了初始值的5倍，后又減小；網(wǎng)絡(luò)效率與子圖數(shù)量呈負(fù)相關(guān)關(guān)系?？紤]到該網(wǎng)絡(luò)構(gòu)建的特殊性，與其他社交網(wǎng)絡(luò)的演化做了對比分析。

關(guān)鍵詞：社交網(wǎng)絡(luò)；網(wǎng)絡(luò)演化；拓?fù)浣Y(jié)構(gòu)；冰桶挑戰(zhàn)

0引言

社會網(wǎng)絡(luò)是描述社會關(guān)系的工具之一[1]。社交網(wǎng)絡(luò)誕生初期的發(fā)展和演化對于理解人際關(guān)系的演化至關(guān)重要。2001年秋，哥倫比亞大學(xué)社會系的Watts等[2]建立了一個(gè)小世界項(xiàng)目的網(wǎng)站，開始在世界范圍內(nèi)進(jìn)行一個(gè)檢驗(yàn)六度分離假說是否正確的網(wǎng)上在線實(shí)驗(yàn)，該實(shí)驗(yàn)的目的是為了驗(yàn)證幾十億人口的整個(gè)世界是否有小世界現(xiàn)象。在一年多的時(shí)間里，總共有13個(gè)國家的18名目標(biāo)對象和166個(gè)國家和地區(qū)的6萬多名志愿者參與實(shí)驗(yàn)，最后有384個(gè)志愿者的電子郵件抵達(dá)了目的地。每封郵件平均轉(zhuǎn)發(fā)5到7次即可到達(dá)目標(biāo)對象。在Web2.0應(yīng)用模式下[3]，網(wǎng)絡(luò)人際關(guān)系可通過新的方式重新構(gòu)建。社交網(wǎng)絡(luò)服務(wù)(social networking services，SNS)和微博(如新浪微博、Twitter)是最新出現(xiàn)的兩種Web2.0應(yīng)用模式，都屬于在線社交網(wǎng)絡(luò)[4]。針對社交網(wǎng)絡(luò)的演化[5]，很多學(xué)者基于理論模型做了分析，復(fù)雜網(wǎng)絡(luò)中兩個(gè)較早且比較著名的模型是小世界模型[6-7]和無標(biāo)度模型[8]。張立等[9]在虛擬的社區(qū)網(wǎng)絡(luò)上做了演化分析，并研究其拓?fù)浣Y(jié)構(gòu)。發(fā)現(xiàn)虛擬社區(qū)網(wǎng)絡(luò)在演化過程中,節(jié)點(diǎn)的加入、邊的加入、網(wǎng)絡(luò)中度分布、節(jié)點(diǎn)的度與其加入網(wǎng)絡(luò)時(shí)間的關(guān)系、平均度隨時(shí)間的變化等方面與傳統(tǒng)的無標(biāo)度網(wǎng)絡(luò)有所不符。熊熙等[10]考慮社交網(wǎng)絡(luò)的聚類及連接隨機(jī)性提出了一種混合演化模型。數(shù)值仿真表明該網(wǎng)絡(luò)模型與實(shí)際社交網(wǎng)絡(luò)數(shù)據(jù)的統(tǒng)計(jì)結(jié)果基本吻合。Ravi Kumar等[11]實(shí)證分析了大型在線社會網(wǎng)絡(luò)結(jié)構(gòu)的演化，并提出了一種能識別組元結(jié)構(gòu)的網(wǎng)絡(luò)增長模型，但他們僅僅截取了網(wǎng)絡(luò)中間的部分?jǐn)?shù)據(jù)，并沒有從網(wǎng)絡(luò)誕生時(shí)開始分析。信息及輿論在社交網(wǎng)絡(luò)上的傳播過程[12]也可以看作是一個(gè)網(wǎng)絡(luò)演化的過程，當(dāng)信息傳播到一個(gè)用戶時(shí)，那么該用戶加入了這個(gè)信息網(wǎng)絡(luò)。當(dāng)前對于社會網(wǎng)絡(luò)演化的研究無論從模型還是實(shí)證角度都是基于全網(wǎng)絡(luò)的演化，并非局部關(guān)系的演化。

本文搜集了國內(nèi)“冰桶挑戰(zhàn)”事件從發(fā)起到發(fā)展到第6天的數(shù)據(jù)，以天為單位將數(shù)據(jù)劃分，構(gòu)造了不同時(shí)間上的網(wǎng)絡(luò)。按照該活動(dòng)的規(guī)則，該社交網(wǎng)絡(luò)具有其特殊性——選擇自己的親密好友所構(gòu)建的網(wǎng)絡(luò)，可認(rèn)為網(wǎng)絡(luò)中邊的關(guān)系為強(qiáng)關(guān)系。該網(wǎng)絡(luò)相當(dāng)于一般社交網(wǎng)絡(luò)的一個(gè)“骨架”，是非常重要的結(jié)構(gòu)。本文首先給出了該網(wǎng)絡(luò)每天的演化過程，分析了該網(wǎng)絡(luò)的密度、聚類系數(shù)及網(wǎng)絡(luò)效率等結(jié)構(gòu)特性，發(fā)現(xiàn)網(wǎng)絡(luò)密度從開始的0.120 9逐漸下降，與Yahoo!360網(wǎng)絡(luò)的密度演化有明顯區(qū)別。聚類系數(shù)從初始值零增加到0.016 7后又緩慢減小，而整體聚類系數(shù)相對較小；網(wǎng)絡(luò)效率先減小，從0.214 3降到最小值0.039 9，后又緩慢增加。聚類系數(shù)與網(wǎng)絡(luò)效率這兩個(gè)方面與Facebook網(wǎng)絡(luò)上的演化也有異同，本文分析了其中的原因，而對比分析可以體現(xiàn)出本文網(wǎng)絡(luò)的特殊性。最后，分析了網(wǎng)絡(luò)的最大連通子圖，連通子圖的數(shù)量先迅速增加最高增加了初始值的5倍，后又減小。發(fā)現(xiàn)連通子圖的數(shù)量與網(wǎng)絡(luò)效率成負(fù)相關(guān)關(guān)系。本文的研究可以為構(gòu)建相應(yīng)的理論模型提供一定依據(jù)。

1數(shù)據(jù)描述與網(wǎng)絡(luò)構(gòu)建

1.1數(shù)據(jù)描述

“冰桶挑戰(zhàn)”全稱為“ALS冰桶挑戰(zhàn)賽”，要求參與者在網(wǎng)絡(luò)上發(fā)布自己被冰水澆遍全身的視頻內(nèi)容，然后該參與者便可以要求其他人(規(guī)則為3個(gè)人)來參與這一活動(dòng)?；顒?dòng)規(guī)定，被邀請者要么在24小時(shí)內(nèi)接受挑戰(zhàn)，要么選擇為對抗“肌肉萎縮性側(cè)索硬化癥”捐出100美元。而事件發(fā)展到后來活動(dòng)者不僅接受挑戰(zhàn)并且也捐出善款。2014年8月中旬，冰桶挑戰(zhàn)賽活動(dòng)蔓延至中國，多名科技界、演藝界及體育界名人被點(diǎn)名參與了這一活動(dòng)。如率先完成挑戰(zhàn)的一加手機(jī)創(chuàng)始人劉作虎，同時(shí)點(diǎn)名奇虎360 CEO周鴻祎、錘子科技CEO羅永浩、華為榮耀業(yè)務(wù)部總裁劉江峰參與該挑戰(zhàn)?；谶@一活動(dòng)規(guī)則，由發(fā)起挑戰(zhàn)者點(diǎn)名接力，然后這樣傳下去，這樣就形成了一個(gè)社交網(wǎng)絡(luò)。

本文主要基于新浪微博這一社交網(wǎng)站，搜集了2014年8月17日00:00點(diǎn)—8月22日24:00，6天的冰桶挑戰(zhàn)者的數(shù)據(jù)，挑戰(zhàn)者都會將視頻上傳到微博及相關(guān)社交網(wǎng)站，并在網(wǎng)站中點(diǎn)名其他人參與。基于此，搜集了參與挑戰(zhàn)者的相關(guān)信息包括自愿挑戰(zhàn)者(即沒被別人點(diǎn)名，自愿加入該活動(dòng)的人)——自動(dòng)加入網(wǎng)絡(luò)的節(jié)點(diǎn)，他們接受挑戰(zhàn)的時(shí)間(上傳視頻的時(shí)間)以及他點(diǎn)名的挑戰(zhàn)者，接下來被點(diǎn)名的人接受挑戰(zhàn)的時(shí)間及他點(diǎn)名的人。共搜集了6天786名挑戰(zhàn)者及他們的挑戰(zhàn)關(guān)系的數(shù)據(jù)。

1.2網(wǎng)絡(luò)構(gòu)建

本文以天為劃分單位，分別構(gòu)建了17日—22日6天的“冰桶挑戰(zhàn)”網(wǎng)絡(luò)。每個(gè)挑戰(zhàn)者作為網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)，點(diǎn)名關(guān)系用網(wǎng)絡(luò)連邊表示。為了便于觀察每天參與者的變化情況，本文把將挑戰(zhàn)者的關(guān)系統(tǒng)一編號，賦予不同的灰度，如圖1所示，不同灰度表示不同時(shí)間(以天為劃分單位)的網(wǎng)絡(luò)節(jié)點(diǎn)(由內(nèi)到外時(shí)間依次增加)。從圖1可以發(fā)現(xiàn)隨著時(shí)間變化，挑戰(zhàn)者數(shù)量不斷增加，相應(yīng)的網(wǎng)絡(luò)不斷擴(kuò)大。接下來分析具體網(wǎng)絡(luò)結(jié)構(gòu)的演化的過程。

2網(wǎng)絡(luò)的演化特性

首先分析網(wǎng)絡(luò)每天的結(jié)構(gòu)及其演化過程，圖2展示了該網(wǎng)絡(luò)的演化過程。

從圖2可以直觀看出該網(wǎng)絡(luò)的演化過程中的一些特點(diǎn)：開始時(shí)節(jié)點(diǎn)較少，即事件發(fā)生初期參與挑戰(zhàn)的人較少，接著有節(jié)點(diǎn)緩慢增加的過程，而后受到社交媒體的影響，參與者越來越多，網(wǎng)絡(luò)節(jié)點(diǎn)急劇增加到后面網(wǎng)絡(luò)演化已不可控制。該過程類似于在線社會網(wǎng)絡(luò)上的信息傳播，信息如果按照既定規(guī)則來，就會以某一節(jié)點(diǎn)為中心散發(fā)。然而從圖中觀察發(fā)現(xiàn)，在第1天有“劉作虎”、“古永鏘”和“葉丙成”3人加入網(wǎng)絡(luò)，并且“葉丙成”只點(diǎn)了兩個(gè)人并沒有遵循既定規(guī)則，所以網(wǎng)絡(luò)的演化并不會像既定規(guī)則那樣發(fā)展。網(wǎng)絡(luò)形成時(shí)的狀態(tài)對于以后的網(wǎng)絡(luò)演化有重要的影響，到了第2天自動(dòng)加入網(wǎng)絡(luò)的節(jié)點(diǎn)變得更多，這些節(jié)點(diǎn)增加也沒有一定的規(guī)則，是隨機(jī)加入到網(wǎng)絡(luò)的，因此網(wǎng)絡(luò)呈現(xiàn)不規(guī)律的增長。在實(shí)際社交網(wǎng)絡(luò)中，有些參與者會破壞既定規(guī)則——有的自動(dòng)加入到網(wǎng)絡(luò)，有的點(diǎn)名不是3人，導(dǎo)致網(wǎng)絡(luò)的演化沒有一定的規(guī)律，這也是現(xiàn)實(shí)社交網(wǎng)絡(luò)難以用現(xiàn)有理論模型擬合的主要原因。

2.1理論模型

根據(jù)“冰桶挑戰(zhàn)”網(wǎng)絡(luò)的演化規(guī)則，本文建立一個(gè)簡單的理論模型與實(shí)際情況對比分析，理論模型如下：

2.2網(wǎng)絡(luò)規(guī)模

網(wǎng)絡(luò)規(guī)模的變化體現(xiàn)整個(gè)網(wǎng)絡(luò)的演化特征，本文從網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)、邊數(shù)及每個(gè)網(wǎng)絡(luò)新增節(jié)點(diǎn)數(shù)的角度與理論模型對比分析，如圖3所示。

由圖3a與b可以看出網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大，開始時(shí)節(jié)點(diǎn)增加緩慢，接著急劇增加，到第5天第6天節(jié)點(diǎn)增加緩慢。同樣，網(wǎng)絡(luò)中邊的數(shù)量也不斷增加，開始時(shí)由于參加者較少，邊數(shù)增加緩慢，到第3第4第5天時(shí)由于節(jié)點(diǎn)數(shù)顯著增加，邊數(shù)也急速增加，而最后一天增加變緩。對比分析，理論模型有些不同：在開始階段網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)和邊數(shù)增加緩慢，到第5天第6天時(shí)增加迅速，與實(shí)際情況差別較大。因?yàn)閷?shí)際社交網(wǎng)絡(luò)的演化受一些人的主觀因素及外界客觀因素的影響，理論模型并沒有考慮這些因素。接下來，分析網(wǎng)絡(luò)每天新增加節(jié)點(diǎn)數(shù)的變化。

從圖3c可知，在網(wǎng)絡(luò)形成初期網(wǎng)絡(luò)每天實(shí)際新增加節(jié)點(diǎn)數(shù)從14到48到141再到224迅速增加，相比理論模型的指數(shù)式增長快。分析原因：一方面由于很多人打破了既定規(guī)則，另一方面由于社交媒體的顯著影響使得人們得到紛紛響應(yīng)。這也說明在該網(wǎng)絡(luò)生成與演化過程中，由于受其他因素的影響，現(xiàn)有的理論模型并不適用于類似社交網(wǎng)絡(luò)的演化。而第5第6天網(wǎng)絡(luò)的新增節(jié)點(diǎn)數(shù)由226變?yōu)榱?33，增加變緩并且有所下降，說明這一事件過了一定的熱度，相應(yīng)地參與者變少；另一方面觀察數(shù)據(jù)發(fā)現(xiàn)在第5天和第6天加入的用戶，在社交網(wǎng)絡(luò)上一般為普通用戶，粉絲量較少不會被社交媒體關(guān)注，大都不會在社交網(wǎng)絡(luò)上發(fā)布相關(guān)信息，因此該網(wǎng)絡(luò)就會在這些節(jié)點(diǎn)停止演化。

2.3網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)演化分析

分析了網(wǎng)絡(luò)規(guī)模的變化，接下來具體分析網(wǎng)絡(luò)結(jié)構(gòu)特性是如何演化的。由于“冰桶挑戰(zhàn)”規(guī)則所限，大家大都會點(diǎn)名自己的親密朋友(強(qiáng)關(guān)系)參加挑戰(zhàn)，體現(xiàn)在網(wǎng)絡(luò)中邊的方向只表示先后點(diǎn)名關(guān)系。在實(shí)際社交中他們互為朋友關(guān)系，體現(xiàn)在網(wǎng)絡(luò)中即為雙向關(guān)系。因此本文在計(jì)算網(wǎng)絡(luò)指標(biāo)時(shí)將該網(wǎng)絡(luò)看成無向網(wǎng)絡(luò)。

2.3.1網(wǎng)絡(luò)密度

一個(gè)包含N個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)的密度ρ定義為網(wǎng)絡(luò)中實(shí)際存在的邊數(shù)M與最大可能的邊數(shù)之比。因此，對于無向網(wǎng)絡(luò)有從圖4a可以看出，該網(wǎng)絡(luò)密度逐漸變小。網(wǎng)絡(luò)節(jié)點(diǎn)的增加，雖然網(wǎng)絡(luò)中邊也增加，但兩者不是同比例變化的，對于整個(gè)網(wǎng)絡(luò)來說逐漸變得稀疏。

(1)

圖4b為文獻(xiàn)[11]研究Yahoo!360這一社交網(wǎng)絡(luò)的密度演化。所用的數(shù)據(jù)是從該網(wǎng)站開始建立到第40周的數(shù)據(jù)。從圖4b可以發(fā)現(xiàn)：網(wǎng)絡(luò)有3個(gè)清晰的階段：起初增加到一個(gè)峰值然后開始減小，最后逐漸穩(wěn)步增加。文獻(xiàn)解釋了其中的原因：社交網(wǎng)絡(luò)建立后，存在少數(shù)對該網(wǎng)絡(luò)有好奇心的人加入，并瘋狂地邀請?jiān)S多朋友來加入體驗(yàn)，這引起了第一個(gè)階段的高峰期。第二階段對應(yīng)于這種新鮮感自然衰減，導(dǎo)致網(wǎng)絡(luò)密度的下降。第三階段對應(yīng)于網(wǎng)絡(luò)真正的有機(jī)增長(當(dāng)越來越多的人知道了該網(wǎng)絡(luò)時(shí))。越來越多的人加入該網(wǎng)絡(luò)，節(jié)點(diǎn)和邊的增加最終使得密度穩(wěn)步上升。對比圖4a圖4b，“冰桶挑戰(zhàn)”網(wǎng)絡(luò)的密度并沒有出現(xiàn)圖4b的3個(gè)階段，并且最大值也就達(dá)到0.12左右，而Yahoo!360網(wǎng)絡(luò)的密度最大達(dá)到0.9多，最小的也在0.3左右。分析其中的原因：“冰桶挑戰(zhàn)”網(wǎng)絡(luò)的密度并沒有增加，原因是該網(wǎng)絡(luò)是點(diǎn)名親密好友關(guān)系的網(wǎng)絡(luò)，不是所有好友，邊數(shù)增加是有限的，所以網(wǎng)絡(luò)密度不會增加。然而Yahoo!360網(wǎng)絡(luò)節(jié)點(diǎn)之間的關(guān)系是非常稠密的，因?yàn)橛脩艨梢匝埶械呐笥鸭尤?，但是其中的?qiáng)關(guān)系是非常稀少的。

2.3.2聚類系數(shù)

(2)

其中，Ei為節(jié)點(diǎn)i的ki個(gè)鄰居節(jié)點(diǎn)之間事實(shí)存在的邊數(shù)。

在一個(gè)網(wǎng)絡(luò)中，聚類系數(shù)是衡量網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)的鄰居間緊密程度的一個(gè)指標(biāo)，用來考察節(jié)點(diǎn)及其鄰居所呈現(xiàn)出來的結(jié)構(gòu)。大多數(shù)真實(shí)網(wǎng)絡(luò)比如Facebook、Twitter、人人網(wǎng)及新浪微博等都表現(xiàn)出聚集結(jié)構(gòu)。

本文計(jì)算出網(wǎng)絡(luò)前6天的平均聚類系數(shù)，如圖5所示。

從圖5a中不難發(fā)現(xiàn)，聚類系數(shù)在前兩天為0，接著迅速增加，到后面又開始減小。分析其中的原因：可以看出網(wǎng)絡(luò)在形成初期，并沒有形成三角關(guān)系，而是類似于星型結(jié)構(gòu)，發(fā)散出去。如果按照既定規(guī)則演化網(wǎng)絡(luò)的聚類系數(shù)會一直為0，節(jié)點(diǎn)不會出現(xiàn)三角關(guān)系。然而該網(wǎng)絡(luò)演化到一定程度，在第3天時(shí)聚類系數(shù)變?yōu)?.016 7并且開始增加，網(wǎng)絡(luò)出現(xiàn)了三角關(guān)系，意味著實(shí)際網(wǎng)絡(luò)出現(xiàn)了共同好友關(guān)系。在現(xiàn)實(shí)中，由于人際關(guān)系的影響人的親密朋友可能不止一個(gè)，在信息傳播過程中由于獲取信息不及時(shí)等原因，被多個(gè)好友點(diǎn)名的情況就會發(fā)生，所以隨著該網(wǎng)絡(luò)的演化，聚類系數(shù)就變?yōu)榉橇阒?。網(wǎng)絡(luò)節(jié)點(diǎn)在增加的同時(shí)，整個(gè)網(wǎng)絡(luò)中挑戰(zhàn)者間彼此成為好友的機(jī)率也增加導(dǎo)致聚類系數(shù)不斷增加。而后平均聚類系數(shù)有所減小，說明網(wǎng)絡(luò)擴(kuò)展速度變快，網(wǎng)絡(luò)變得發(fā)散，導(dǎo)致網(wǎng)絡(luò)的平均聚類系數(shù)減小。

Bimal Viswanath研究了Facebook這一社交網(wǎng)絡(luò)的演化。搜集到的數(shù)據(jù)為2006年9月至2009年1月的數(shù)據(jù)。圖5b為文獻(xiàn)[14]中Facebook社交網(wǎng)絡(luò)的聚類系數(shù)演化過程。橫坐標(biāo)表示2007年及2008年不同的月份。從圖中不難發(fā)現(xiàn)，F(xiàn)acebook網(wǎng)絡(luò)的聚類系數(shù)平均在0.13左右。然而，本文研究的網(wǎng)絡(luò)集聚系數(shù)最大達(dá)到0.02左右，要比Facebook網(wǎng)絡(luò)小的多。分析其中的原因：首先Facebook網(wǎng)絡(luò)的數(shù)據(jù)是網(wǎng)絡(luò)誕生后中間時(shí)間段的數(shù)據(jù)，而在網(wǎng)絡(luò)中朋友間一旦建立好友關(guān)系，就不會有很大變動(dòng)。本文網(wǎng)絡(luò)聚類系數(shù)具有明顯的變化，是因?yàn)樵诰W(wǎng)絡(luò)形成初期，朋友關(guān)系會因?yàn)楣?jié)點(diǎn)的不斷加入而發(fā)生變化。其次，F(xiàn)acebook網(wǎng)絡(luò)考慮了用戶的所有關(guān)系，本文的網(wǎng)絡(luò)只有強(qiáng)關(guān)系，所以聚類系數(shù)相對較小。

2.3.3網(wǎng)絡(luò)效率與最大連通子圖

網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的最短路徑是指連接著兩個(gè)節(jié)點(diǎn)的邊數(shù)最少的路徑。兩點(diǎn)間的距離dij定義為連接著兩個(gè)節(jié)點(diǎn)的最短路徑上的邊的數(shù)目。對于不連通的網(wǎng)絡(luò)，可能兩個(gè)節(jié)點(diǎn)之間不存在連通的路徑，即意味著這兩個(gè)節(jié)點(diǎn)之間的距離為無窮大，從而導(dǎo)致整個(gè)網(wǎng)絡(luò)的平均路徑也為無窮大。為了避免這種情況，定義一個(gè)網(wǎng)絡(luò)的平均效率[15]：

(3)

其中,N為網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)，dij為節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離。兩個(gè)點(diǎn)之間的距離越短那么兩點(diǎn)之間信息傳遞的效率則越高，即效率與兩點(diǎn)距離成反比關(guān)系。

網(wǎng)絡(luò)的連通子圖體現(xiàn)了一個(gè)網(wǎng)絡(luò)的連通比率，對于分析信息在網(wǎng)絡(luò)中的傳播有重要的作用，研究網(wǎng)絡(luò)動(dòng)態(tài)演化有著重要的意義。本文計(jì)算得到了6個(gè)網(wǎng)絡(luò)的效率如圖6a所示及每個(gè)網(wǎng)絡(luò)的子圖數(shù)量和最大連通子圖節(jié)點(diǎn)的個(gè)數(shù)，如圖6c～d所示。

根據(jù)網(wǎng)絡(luò)效率的定義也可以看出網(wǎng)絡(luò)效率受到網(wǎng)絡(luò)子圖個(gè)數(shù)的影響，當(dāng)網(wǎng)絡(luò)中子圖較多時(shí)網(wǎng)絡(luò)效率就會變小。具體分析，從圖6a中可以發(fā)現(xiàn)前3個(gè)網(wǎng)絡(luò)的效率由開始的0.214 3變?yōu)?.058 8又到0.039 9逐漸變小，且第2個(gè)網(wǎng)絡(luò)比初始網(wǎng)絡(luò)減小了81.4%。開始時(shí)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)較少，不連通子圖數(shù)量也較少，節(jié)點(diǎn)間相互達(dá)到的路徑很短，因此網(wǎng)絡(luò)效率較高。隨著新節(jié)點(diǎn)的不斷加入，不連通子網(wǎng)不斷增加導(dǎo)致節(jié)點(diǎn)間的路徑變得較大，網(wǎng)絡(luò)效率變小。隨后網(wǎng)絡(luò)效率從0.098 9到0.125 9變大，隨著網(wǎng)絡(luò)的不斷擴(kuò)大，網(wǎng)絡(luò)的密度變大因此效率就會增加。最后又有減小趨勢到0.121 8，同樣也受到網(wǎng)絡(luò)規(guī)模的影響，節(jié)點(diǎn)間的路徑變長。同樣，圖6b為文獻(xiàn)[14]中Facebook社交網(wǎng)絡(luò)的平均路徑長度演化過程。從圖不難發(fā)現(xiàn)，F(xiàn)acebook網(wǎng)絡(luò)節(jié)點(diǎn)間的平均最短路徑在7左右不會有很大變化，而本文網(wǎng)絡(luò)效率到最后也趨于穩(wěn)定在0.12左右。分析兩者異同的原因：當(dāng)網(wǎng)絡(luò)演化到一定程度時(shí)，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的連邊基本不會發(fā)生太大變化，使得網(wǎng)絡(luò)效率或者最短路徑趨于穩(wěn)定。而本文網(wǎng)絡(luò)由于節(jié)點(diǎn)連接邊較少、連通子圖數(shù)量較多等原因使得網(wǎng)絡(luò)效率較低。

觀察圖6a與圖6b不難發(fā)現(xiàn)，網(wǎng)絡(luò)效率與連通子圖數(shù)有很大相關(guān)性。即網(wǎng)絡(luò)效率下降時(shí)網(wǎng)絡(luò)子圖數(shù)量增加，當(dāng)網(wǎng)絡(luò)效率上升時(shí)，網(wǎng)絡(luò)子圖數(shù)量減小，說明網(wǎng)絡(luò)子圖數(shù)量影響網(wǎng)絡(luò)效率的變化。從圖6b中網(wǎng)絡(luò)子圖數(shù)量的演化可知，在網(wǎng)絡(luò)形成初期網(wǎng)絡(luò)子圖數(shù)量迅速增加，由3變?yōu)?0到18，說明該事件能夠得到很多人的響應(yīng)，自愿加入到網(wǎng)絡(luò)中。而后又有減小的趨勢，說明網(wǎng)絡(luò)連通性變好，一方面說明自愿挑戰(zhàn)者的數(shù)量減小，另一方面可能是很多獨(dú)立網(wǎng)絡(luò)連接到了一起，在現(xiàn)實(shí)中朋友關(guān)系更加密切。從圖6c也不難發(fā)現(xiàn)最大連通子圖的節(jié)點(diǎn)數(shù)量不斷增加，說明很多獨(dú)立子網(wǎng)絡(luò)很快融入到最大子網(wǎng)絡(luò)里，形成一個(gè)連通網(wǎng)絡(luò)。

3總結(jié)與展望

社交網(wǎng)絡(luò)的形成與演化從一定程度上來講是人際關(guān)系的不斷延伸，是一個(gè)復(fù)雜的過程，現(xiàn)實(shí)的和虛擬的各種因素相互影響，呈現(xiàn)多種特征。

本文主要從“冰桶挑戰(zhàn)”這一事件出發(fā)，構(gòu)造了一個(gè)真實(shí)的社交網(wǎng)絡(luò)。搜集從網(wǎng)絡(luò)形成到第六天的數(shù)據(jù)，從網(wǎng)絡(luò)規(guī)模等研究了該網(wǎng)絡(luò)的演化過程。通過分析發(fā)現(xiàn)該網(wǎng)絡(luò)密度不斷減小；聚類系數(shù)從初始值零增加到0.016 7后又緩慢減?。痪W(wǎng)絡(luò)效率從0.214 3開始減小，最大減小量為初始值的81.4%，后又緩慢增加；連通子圖的數(shù)量從3迅速增加，最高增加了初始值的5倍，后又減小。本文發(fā)現(xiàn)連通子圖的數(shù)量與網(wǎng)絡(luò)效率呈負(fù)相關(guān)關(guān)系。從這些結(jié)論中，可以清楚看出這一特殊網(wǎng)絡(luò)的演化過程，為社交網(wǎng)絡(luò)演化模型的建立提供一定依據(jù)。本文也與其他大型社交網(wǎng)絡(luò)的演化做了對比分析，從中也可以得出本文社交網(wǎng)絡(luò)演化的特殊性。

對于包括社交網(wǎng)絡(luò)在內(nèi)的復(fù)雜網(wǎng)絡(luò)而言，結(jié)構(gòu)與演化動(dòng)力學(xué)的研究正逐漸成為熱點(diǎn)。復(fù)雜網(wǎng)絡(luò)的研究重點(diǎn)也逐漸轉(zhuǎn)向基于結(jié)構(gòu)的信息傳播演化過程。只有理解了在這種結(jié)構(gòu)上的傳播機(jī)理后，才能夠有根據(jù)地進(jìn)行傳播的控制問題研究。在現(xiàn)實(shí)世界中，一些事件的發(fā)展社會媒體起到了很大的作用，而如何量化社交媒體的作用也是一個(gè)亟待解決的問題。本文在獲取“冰桶挑戰(zhàn)”數(shù)據(jù)的過程中，只搜集一些名人的數(shù)據(jù)，對于很多參與挑戰(zhàn)的普通人并沒有考慮在內(nèi)，這樣難免會影響到網(wǎng)絡(luò)的演化過程。另外，對于在統(tǒng)計(jì)數(shù)據(jù)時(shí)由于有時(shí)間差有些數(shù)據(jù)難免會有所遺漏，從一定程度上影響了結(jié)論的精確度。

參考文獻(xiàn):

[1]斯坦利·沃瑟曼，凱瑟琳·福斯特. 社會網(wǎng)絡(luò)分析: 方法與應(yīng)用[M]. 陳禹，孫彩虹,譯. 北京: 中國人民大學(xué)出版社, 2012.

[2]Dodds P S, Muhamad R, Watts D J. An experimental study of search in global social networks[J]. Science, 2003, 301(5634): 827-829.

[3]Shin D H. The effects of trust, security and privacy in social networking: a security-based approach to understand the pattern of adoption[J]. Interacting with Computers, 2010, 22(5): 428-438.

[4]MisloveA, Marcon M, Gummadi K P, et al. Measurement and analysis of online social networks[C]//Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement. ACM, 2007: 29-42.

[5]Hellmann T, Staudigl M. Evolution of social networks[J]. European Journal of Operational Research, 2014, 234(3): 583-596.

[6]Watts D J, Strogatz S H. Collective dynamics of ‘small-world’networks[J]. Nature, 1998, 393(6684): 440-442.

[7]Newman M E J, Watts D J. Renormalization group analysis of the small-world network model[J]. Physics Letters A, 1999, 263(4): 341-346.

[8]Barabási A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.

[9]張立, 劉云. 虛擬社區(qū)網(wǎng)絡(luò)的演化過程研究[J]. 物理學(xué)報(bào), 2008, 57(9): 5419-5424.

Zhang L, Liu Y. Research on the evolution process of virtual community networks[J].Acta Physica Sinica, 2008, 57(9): 5419-5424.

[10] 熊熙,曹偉, 周欣, 等. 社交網(wǎng)絡(luò)形成和演化的特征模型研究[J]. 四川大學(xué)學(xué)報(bào): 工程科學(xué)版, 2012, 44(004): 140-144.

Xiong X, Cao W, Zhou X, etal. Research on the feature model of the formation and evolution of social networks[J]. Journal of SichuanUniversity(Engineering Science Edition), 2012, 44(004): 140-144.

[11] Kumar R, Novak J, Tomkins A. Structure and evolution of online social networks[M]//Link Mining: Models, Algorithms, and Applications. Springer New York, 2010: 337-357.

[12] 郭海霞. 新型社交網(wǎng)絡(luò)信息傳播特點(diǎn)和模型分析[J]. 現(xiàn)代情報(bào), 2012, 32(1): 56-59.

GuoHaixia. New Social networking features andmodel analysis of information dissemination[J]. Journal of Modern Information, 2012, 32(1): 56-59.

[13] 汪小帆,李翔,陳關(guān)榮.網(wǎng)絡(luò)科學(xué)導(dǎo)論[M].北京:高等教育出版社,2012.

[14] Viswanath B, Mislove A, Cha M, et al. On the evolution of user interaction in Facebook[C]//Proceedings of the 2nd ACM Workshop on Online Social Networks. ACM, 2009: 37-42.

[15] Latora V, Marchiori M. Efficient behavior of small-world networks[J]. Physical Review Letters, 2001, 87(19): 198701.

(責(zé)任編輯李進(jìn))

The Evolution of Social Networks Constructed by “Ice Bucket Challenge”

YANG Kai, LIU Xiaolu, LIN Jianhong, CHENG Xi, GUO Qiang, LIU Jianguo

(Research Center of Complex Systems Science, University of Shanghai for Science and Technology, Shanghai 200093)

Abstract：The evolutionary process of social networks at initial period is very important, especially for the quantitative understanding of the formation and the evolution of interpersonal relationships. In this paper, combining with the “Ice Bucket Challenge”, we collect the data of this event from the launch to the sixth day in our country. The nodes stand for the challengers and the edges are the relations of called people in the social networks. By analyzing the rules of the structural characteristics, including the network size, the clustering coefficient, density, network efficiency and connectivity sub-graphs, we find that the clustering coefficient increased from zero to 0.0167 at the beginning and then decreases; the densityof the network declines from 0.1209 over time; the network efficiency reduces by 81.4% at first and then slowly increases; the connected sub-graphs rapidly increases five times and then decreases; the network efficiency and the number of sub-graphs are negatively correlative. Taking into account the specificity of the network,we compare with evolution of other social networks.Thiswork will be helpful for understanding the law of the formation and development of the early social networks.

Key words：social networks; network evolution; topological structure; Ice Bucket Challenge

文章編號：1672—3813(2016)02—0090—07;

DOI:10.13306/j.1672-3813.2016.02.011

收稿日期：2014-10-29；修回日期：2015-01-12

基金項(xiàng)目：國家自然科學(xué)基金(71171136，61374177，71371125)；上海市一流學(xué)科建設(shè)項(xiàng)目(XTKX2012)；教育部人文社科基金(13YJA630023)；上海出版?zhèn)髅窖芯吭洪_放基金(SAYB1407)

作者簡介：楊凱(1987-)，男，山東泰安人，博士研究生，主要研究方向?yàn)樵诰€社會網(wǎng)絡(luò)結(jié)構(gòu)與演化分析。 通訊作者：劉建國(1979-)，男，山西臨汾人，教授，主要研究方向?yàn)榫W(wǎng)絡(luò)科學(xué)，商務(wù)智能，知識管理。

中圖分類號：N941

文獻(xiàn)標(biāo)識碼：A