胡慶成 尹龑燊 馬鵬斐 高旸 張勇 邢春曉

(清華大學(xué)計算機系,信息技術(shù)研究院,清華信息科學(xué)與技術(shù)國家實驗室,北京 100084)

(2013年1月25日收到;2013年3月25日收到修改稿)

1 引言

現(xiàn)實世界中的諸多系統(tǒng)都以復(fù)雜網(wǎng)絡(luò)形式存在,比如互聯(lián)網(wǎng)、社會系統(tǒng)、計算網(wǎng)絡(luò)、生物網(wǎng)絡(luò)和社交網(wǎng)絡(luò)等.理解復(fù)雜網(wǎng)絡(luò)的拓撲結(jié)構(gòu)和功能是目前國際研究的熱點.在很多科學(xué)領(lǐng)域中,都使用網(wǎng)中絡(luò)用來節(jié)表點示代系表統(tǒng)人中,邊成代員表之人間與的人關(guān)之系間,如的在聯(lián)社系交.由網(wǎng)絡(luò)于這些網(wǎng)絡(luò)具有很高的復(fù)雜性,因此被稱為“復(fù)雜網(wǎng)絡(luò)(complex network)”[1-3],它已成為當(dāng)前最重要的多學(xué)科交叉研究領(lǐng)域之一.在復(fù)雜網(wǎng)絡(luò)中,找出最具影響力的節(jié)點[4-9]或意見領(lǐng)袖[10]在理論和現(xiàn)實應(yīng)用中都有重大的意義,例如有效地控制疾病傳播[11]、流言散布[12,13]、計算機病毒擴散,還可以傳播新產(chǎn)品[14]、新思想[15]以推進社會化進程.

在社會網(wǎng)絡(luò)分析中,常用“中心性(centrality)”來測量最有影響力的節(jié)點.文獻[16,17]利用度中心性(degree centrality)來測量最有影響力的節(jié)點,在符合冪律的非均勻網(wǎng)絡(luò)中,度數(shù)較大的hub節(jié)點的傳播影響力應(yīng)該相對較大,這也是目標免疫和熟人免疫策略的基本依據(jù).文獻[18]利用了介數(shù)中心性(betweenness centrality)來評價影響力,介數(shù)中心性是以經(jīng)過某個節(jié)點的最短路徑的數(shù)目來刻畫節(jié)點的重要性.文獻[19]提出PageRank算法來評價網(wǎng)頁的重要性,它認為一個網(wǎng)頁(節(jié)點)的重要性取決于其前向鏈接的數(shù)量與質(zhì)量.文獻[20,21]利用緊密度指標(closeness centrality)刻畫某個節(jié)點到其他節(jié)點的難易程度.文獻[22]提出通過K-shell(ks)[23]分解來確定最具有影響力的單源節(jié)點.

本文認為節(jié)點的影響力不只是由節(jié)點內(nèi)部屬性決定,而且其外部屬性緊密相關(guān),這與哲學(xué)范疇的內(nèi)因和外因思想一致.內(nèi)部屬性如度數(shù)、緊密性、介數(shù)等中心化指標,外部屬性如所屬社區(qū)的大小、社區(qū)內(nèi)關(guān)系緊密度等.社區(qū)[24,25]是一個有共同愛好的,或者位于一個共同地方的、或者同在某個工作場所的、或者具有家庭聯(lián)系的群體[26].社區(qū)內(nèi)的節(jié)點聯(lián)系緊密,社區(qū)間的節(jié)點聯(lián)系松散.

本文提出了KSC(K-shell and community centrality)指標模型.此模型不但考慮了節(jié)點的內(nèi)部屬性,而且還綜合考慮了節(jié)點的外部屬性,例如節(jié)點所屬的社區(qū)特性等.然后利用SIR(susceptible-infected-recovered)模型對傳播過程進行仿真,實驗證明本文提出的方法可以更好地發(fā)現(xiàn)最具有影響力的節(jié)點.本文為這項具有挑戰(zhàn)性研究提供了新的思想和方法.

2 相關(guān)研究

在社會網(wǎng)絡(luò)中,發(fā)現(xiàn)最具有影響力的節(jié)點可以幫助我們有效地控制疾病傳播、流言散布、計算機病毒擴散,還可以傳播新產(chǎn)品、新思想以推進社會化進程.

圖1 網(wǎng)絡(luò)分析樣例圖

2.1 度中心化

度中心化[27,28]是一種最簡單的方法,用于描述在靜態(tài)網(wǎng)絡(luò)中節(jié)點所產(chǎn)生的直接影響力.設(shè)網(wǎng)絡(luò)G=(V,E)具有n=|V|個節(jié)點和m=|E|條邊,節(jié)點v的度數(shù)是指與節(jié)點v連接的節(jié)點個數(shù),用Cd(v)表示

其中d(v)稱為該節(jié)點的度.如圖1所示,盡管節(jié)點14度數(shù)最大為7,但作為初始節(jié)點,它最終的傳播范圍并不一定是最廣泛的,因為它的鄰居節(jié)點的度數(shù)都很小.

2.2 介數(shù)中心化

介數(shù)中心化刻畫了網(wǎng)絡(luò)中節(jié)點對于信息流動的影響力.節(jié)點v的介數(shù)[18]定義為

σst表示源節(jié)點s到目標節(jié)點t的最短路徑數(shù),σst(v)表示節(jié)點s經(jīng)過節(jié)點v到目標節(jié)點t的最短路徑數(shù).

2.3 緊密度

緊密度[20,21]用于刻畫節(jié)點到達其他節(jié)點的難易程度：

dG(s,t)表示源節(jié)點s到節(jié)點t的最短距離.

2.4 K-shell分解方法

K-shell給出了網(wǎng)絡(luò)中節(jié)點重要性的一種粗?；膭澐?用Cks(v)表示.網(wǎng)絡(luò)邊緣節(jié)點的K-shell為1,然后往內(nèi)像剝洋蔥一樣一層層進入網(wǎng)絡(luò)的核心.首先去除網(wǎng)絡(luò)中度數(shù)小于k的所有節(jié)點及其連邊;如果在剩下的節(jié)點中仍有度值小于k的節(jié)點,那么就繼續(xù)去除這些節(jié)點,直至網(wǎng)絡(luò)中剩下的節(jié)點的度值不小于k.依次取k=1,2,3,···,就得到了該網(wǎng)絡(luò)的K-shell分解.具體過程可參考圖一.Kitsak等[22]實驗研究表明,對于單個傳播源感染率低的情形,度數(shù)大或者高介數(shù)的節(jié)點不一定是最有影響力的節(jié)點,而通過K-shell分解分析確定的網(wǎng)絡(luò)核心節(jié)點(即K-shell值大的節(jié)點)才是最有影響力的節(jié)點;其研究表明,K-shell分解方法是一種比較好的影響力節(jié)點識別方法,可以更好地預(yù)測疾病等的傳播.當(dāng)傳染病在網(wǎng)絡(luò)的K-shell大的節(jié)點爆發(fā)時,病毒總是可以在網(wǎng)絡(luò)核心通過許多種路徑開始感染其他部分,無論該節(jié)點度數(shù)的大與小,這個結(jié)論都是有效的.這些通路的存在反過來也意味著如果以一個隨機節(jié)點為源爆發(fā)疫情,有高K-shell值的節(jié)點更有可能早于其他節(jié)點被感染(疾病預(yù)測).

2.5 社區(qū)劃分算法

社區(qū)[24,25]是一個有共同愛好的、或者位于一個共同地方的、或者同在某個工作場所的、或者具有家庭聯(lián)系的群體[26].社區(qū)內(nèi)的節(jié)點聯(lián)系緊密,社區(qū)間的節(jié)點聯(lián)系松散.社區(qū)劃分(community detecting)的概念前期在Lin的論文[29]中提出.如圖1,網(wǎng)絡(luò)劃分為4個社區(qū)(節(jié)點1—5,6—9,10—12,13—19).社區(qū)是復(fù)雜網(wǎng)絡(luò)信息傳播中最普遍和最重要的拓撲屬性之一,信息在同一社區(qū)內(nèi)傳播迅速,而在社區(qū)之間傳播緩慢.Kernighan-Lin(KL)算法[30]、快速Newman(FN)算法[31]和Guimera-Amaral(GA)算法[32]是經(jīng)典的復(fù)雜網(wǎng)絡(luò)社區(qū)劃分算法.

本文使用了FN算法.FN算法是Newman提出的基于局部搜索的快速社區(qū)劃分算法.其優(yōu)化目標是極大化網(wǎng)絡(luò)模塊性(modularity)評價函數(shù)Q[26].FN算法屬于聚合算法,它初始假定所有節(jié)點各自成為一個社區(qū),然后每一步根據(jù)原有連接合并兩個社區(qū),計算Q值并記錄下來,直到所有社區(qū)都被合并成為一個社區(qū).最后根據(jù)記錄下的Q值,找到最優(yōu)的劃分結(jié)果.

3 算法模型

我們認為節(jié)點的傳播力不但與節(jié)點的內(nèi)部自身屬性有關(guān),如度數(shù)、緊密度、介數(shù)、K-shell等,還與它的外部環(huán)境屬性相關(guān),如節(jié)點所處外部環(huán)境：社區(qū)大小,社區(qū)關(guān)聯(lián)緊密度等.本文提出節(jié)點的影響力是由內(nèi)因與外因同時決定的這一新穎思想和方法,即KSC中心化指標模型.模型符合哲學(xué)內(nèi)因與外因?qū)κ挛锿瑯泳哂袥Q定作用這一思想理念.

復(fù)雜網(wǎng)絡(luò)G=(V,E)中,節(jié)點vo的KSC值定義如下：

其中 f internal(vo)為節(jié)點的內(nèi)部影響力,f external(vo)為節(jié)點的外部影響力,α為內(nèi)部影響因子,β為外部影響因子,且滿足α+β=1,α和β可以根據(jù)實際網(wǎng)絡(luò)結(jié)構(gòu)與功能設(shè)定.

f internal(v o)定義如下：

其中,K(v)為節(jié)點內(nèi)部屬性值,可取度數(shù)、介數(shù)、緊密度和K-shell等節(jié)點自身屬性,mv∈aVx(K(v))為歸一化因子.

f external(v o)定義如下：

其中C為FN算法劃分的社區(qū)集合,d(vo,c)為節(jié)點vo在社區(qū)c中的鄰居節(jié)點的總個數(shù),|c|為社區(qū)c的大小是歸一化因子.

本文實驗中α與β可以根據(jù)網(wǎng)絡(luò)的拓撲結(jié)構(gòu)設(shè)定;其中 finternal(vo)選取K-shell為內(nèi)部屬性,也可以為度數(shù)、緊密度和介數(shù)等,fexternal(vo)選取為社區(qū)屬性,俗語“物以類聚,人以群分”說明社區(qū)內(nèi)部節(jié)點之間有共同的興趣愛好等,相似性更大.

表1給出了圖1各節(jié)點的各種指標,如節(jié)點14度數(shù)最大,但是由于處在網(wǎng)絡(luò)的邊緣,所以最終影響力為2,而節(jié)點7雖然度數(shù)為6,但是它是其他幾個社區(qū)連通的樞紐,結(jié)構(gòu)洞[33,34]概念中重要節(jié)點.節(jié)點1—5雖然K-shell相同,但是節(jié)點1是2—5連接其他節(jié)點的橋接關(guān)系.從表1中可以看出各種方法得到的最具影響力節(jié)點排名各不相同.

表1 計算圖一中節(jié)點的傳播力

4 模型及實驗分析

4.1 SIR模型

SIR模型在現(xiàn)實社會網(wǎng)絡(luò)中已廣泛應(yīng)用于疾病傳播、信息傳播及謠言傳播的研究.為了驗證本文提出的模型,我們采用SIR模型[35-38]來模擬仿真?zhèn)鞑ミ^程,并將其結(jié)果與我們的模型實驗結(jié)果做比較.

SIR模型中有三種狀態(tài),易感染狀態(tài)S(susceptible),感染狀態(tài)I(infected),免疫狀態(tài)(recovered).當(dāng)個體處于感染狀態(tài)時,以β的概率感染處于易感染狀態(tài)鄰居個體,感染狀態(tài)的節(jié)點以γ的概率恢復(fù)為免疫狀態(tài).

如果β值較大,節(jié)點傳播能力很強,節(jié)點將很快感染整個網(wǎng)絡(luò),從而很難區(qū)分單個個體的重要性;較小的β能在有限時間內(nèi)更好地顯示出感染范圍.本文中我們設(shè)定較小的β=0.04.

4.2 實驗數(shù)據(jù)

考慮到不同的社會網(wǎng)絡(luò)類型所代表不同的網(wǎng)絡(luò)拓撲結(jié)構(gòu)特性,我們選取了4個真實社會網(wǎng)絡(luò)數(shù)據(jù)集[39]進行分析比較,表2給出各個網(wǎng)絡(luò)的屬性特征：1)Blogs網(wǎng)絡(luò)數(shù)據(jù)[40],MSN博客空間中交流的關(guān)系網(wǎng)絡(luò);2)Netscience合著關(guān)系網(wǎng)絡(luò)[41],選擇了其中最大連通子圖379個作者的關(guān)系網(wǎng)絡(luò);3)Router網(wǎng)絡(luò),數(shù)據(jù)是由Rocketfuel Project[42]收集的互聯(lián)網(wǎng)中路由連接層級關(guān)系網(wǎng)絡(luò);4)Email網(wǎng)絡(luò)[43],是洛維拉·依維爾基里大學(xué)成員郵件通信的關(guān)系網(wǎng)絡(luò).我們的模型也可應(yīng)用于其他類型的復(fù)雜網(wǎng)絡(luò).

其中n是節(jié)點數(shù),m為邊數(shù),〈k〉表示網(wǎng)絡(luò)中平均度數(shù)據(jù),max(k)為節(jié)點中最大度數(shù),d為節(jié)點之間最短路徑的平均數(shù),max(Cks)為網(wǎng)絡(luò)中最大的K-shell,C為整個復(fù)雜網(wǎng)絡(luò)被劃分的社區(qū)數(shù).

表2 現(xiàn)實社會網(wǎng)絡(luò)的屬性情況

4.3 實驗效果

我們應(yīng)用章節(jié)4.1中所提到的SIR模型,對所提出的KSC指標與度、緊密性、介數(shù)和K-shell中心化指標進行了分析比較.實驗?zāi)M傳播過程中,每次只選取網(wǎng)絡(luò)中的一個節(jié)點作為初始傳播節(jié)點,設(shè)定較短傳播時間(t=10),對每個節(jié)點進行1000次重復(fù)實驗取均值,最終感染與恢復(fù)的節(jié)點總數(shù)定義為影響力F(t).

圖2 KSC模型中內(nèi)部影響因子α與外部影響因子β取不同對傳播影響力指標的影響分析

圖2 表示了在KSC模型中選取不同的內(nèi)部影響因子α與外部影響因子β(α+β=1)對結(jié)果的影響程度.哲學(xué)范疇中事物的運動和變化,是由它本身固有的內(nèi)部矛盾引起的,又是同它所處的一定的外在條件相聯(lián)系的,內(nèi)因和外因在事物發(fā)展中的地位和作用是不同的.這與模型中內(nèi)部影響因子α與外部影響因子β對傳播影響假設(shè)完全一致.如在圖2(c)中局部放大了最具影響力的前10位,當(dāng)0≤α≤0.2,1≥β≥0.8,或1≥α≥0.8,0≤β≤0.2時可以看到,影響力曲線波動較大,影響力排名靠后的節(jié)點影響反而大.即只是單純的考慮內(nèi)部屬性或外部屬性對發(fā)現(xiàn)最具有影響的節(jié)點來說準確性,適用性較差.

經(jīng)實驗分析得出四種不同拓撲結(jié)構(gòu)網(wǎng)絡(luò)的內(nèi)、外影響因子經(jīng)驗取值情況,如表3所示.可以看出在不同類型的網(wǎng)絡(luò)結(jié)構(gòu)中,內(nèi)、外因所起的權(quán)重是不同的,本文實驗中的α,β根據(jù)表3中取較好的經(jīng)驗值,這從另一方面證明了所提出模型的合理性及普遍性.

圖3所表示的是在不同的網(wǎng)絡(luò)中中心度指標與實際影響力之間的關(guān)系.

在Blogs網(wǎng)絡(luò)中,度,K-shell,介數(shù)指標與影響力F(t)關(guān)系都不是很明顯,例如在介數(shù)指標結(jié)果中,一些介數(shù)大的節(jié)點F(t)比一些介數(shù)很小的節(jié)點影響力還要低,但KSC指標可以較好地區(qū)分出最具影響力的節(jié)點.Email網(wǎng)絡(luò)中,所有指標表現(xiàn)都較好,緊密度與KSC更為理想,這與網(wǎng)絡(luò)的拓撲結(jié)構(gòu)有關(guān)系.在Netscience網(wǎng)絡(luò)中,介數(shù)衡量結(jié)果最差,緊密度,K-shell與節(jié)點F(t)影響力關(guān)系也不明顯,KSC的效果要優(yōu)于度數(shù).在路由網(wǎng)絡(luò)(Router)中K-shell與KSC結(jié)果接近,其他指標結(jié)果很難得到傳播力較大的節(jié)點.總之,在不同的網(wǎng)絡(luò)中傳統(tǒng)的中心度指標各有優(yōu)缺點,但是我們提出的KSC整體效果最好,都能有效地區(qū)分出最具有影響力的節(jié)點,通用性較強.

表3 內(nèi)、外影響因子取值情況

圖3 節(jié)點影響力分析比對,列代表5種不同中心化指標,行表示為4種不同的復(fù)雜網(wǎng)絡(luò)環(huán)境,傳播影響力F(t)(t=10),每個初始節(jié)點重復(fù)運行1000次取均值

對于單個傳播源的情形,最具有影響力的節(jié)點并非度數(shù)最大的節(jié)點或者介數(shù)最大的節(jié)點,而是K-shell最大的節(jié)點,這一結(jié)論在Kitsak等[22]已在《Nature Physics》指出.圖4比較了KSC與K-shell的實驗效果,KSC比K-shell增加了外部屬性的影響因素.例如在Email網(wǎng)絡(luò)中,當(dāng)K-shell為10時,傳播影響力F(t)(t=10)并不穩(wěn)定,而且變化范圍較大,并且影響力隨著KSC值的增大呈現(xiàn)增大趨勢.在4種復(fù)雜網(wǎng)絡(luò)中明顯可以看出當(dāng)KSC一定時F(t)相對穩(wěn)定,顏色變化范圍較小.

圖4 KSC與K-shell指標在4種不同復(fù)雜網(wǎng)絡(luò)中的分析比較,橫軸表示KSC的指標值,縱軸表示K-shell的指標值,顏色坐標代表SIR模型仿真出的實際影響力大小F(t)

圖5 比較了KSC與介數(shù)的實驗效果.可出看出在Email網(wǎng)絡(luò)中,KSC與介數(shù)表現(xiàn)正向同步較好,都能較好地發(fā)出最具影響力的節(jié)點,但在其他三個網(wǎng)絡(luò)環(huán)境中KSC表現(xiàn)明顯優(yōu)于介數(shù)指標.實驗結(jié)果表明KSC方法明顯優(yōu)于已有的4種典型方法.由此可見,考慮節(jié)點的外部屬性對于找出最有影響力的節(jié)點意義重大,且具有較強的通用性,驗證了我們所提出模型的合理性與普遍性.

如圖6所示,在Blogs網(wǎng)絡(luò)中,KSC曲線的某一點(x,y),橫坐標表示此點用KSC指標值得出的排名為x,縱坐標表示此點在SIR仿真的實際影響力為y.理論上,一個好的指標方法應(yīng)該表現(xiàn)為向右傾斜單調(diào)下降的曲線.因為對于一個好的指標方法,如果某個節(jié)點按該指標得出的排名越靠后,其實際影響力F(t)應(yīng)該隨之減小.

從圖6結(jié)果中分析,可以看到已有的4種典型方法在不同網(wǎng)絡(luò)中影響力均有所波動,這些方法在不同網(wǎng)絡(luò)中各有優(yōu)劣,通用性不強,特別是在影響力前10中波動范圍最為明顯.指標值小的傳播影響力反而比指標值大的傳播影響力要大,特別是在Blogs網(wǎng)絡(luò)中,已有的4種指標方法結(jié)果都不太精確,而我們提出的KSC指標幾乎在所有的網(wǎng)絡(luò)中都符合向右傾斜單調(diào)下降的理論曲線.

本實驗充分論證了節(jié)點影響力不但由內(nèi)部屬性決定,而且還與其外部屬性密切相關(guān),說明我們提出的KSC模型的合理性及普遍適用性.

圖5 KSC與介數(shù)指標在4種不同復(fù)雜網(wǎng)絡(luò)中的分析比較,橫軸表示KSC的指標值,縱軸表示介數(shù)的指標值,顏色坐標代表SIR模型仿真出的實際影響力大小F(t)

5 結(jié)論

在復(fù)雜網(wǎng)絡(luò)中發(fā)現(xiàn)最具影響力的節(jié)點,可以幫助我們提高新知識、新產(chǎn)品的傳播效率,同時可以有效地制定相應(yīng)的策略來阻止疾病及謠言傳播.復(fù)雜網(wǎng)絡(luò)中鑒別最具影響力的節(jié)點一直以來是研究的熱點與難點,我們提出了KSC中心化指標模型.實驗選取現(xiàn)實生活中常見的四種復(fù)雜網(wǎng)絡(luò)博客網(wǎng)、郵件網(wǎng)、路由網(wǎng)和科學(xué)合著網(wǎng),通過SIR模型模擬節(jié)點傳播過程,并對各種中心化指標得出的影響力進行排序分析,驗證了方法的高效性和正確性.

與傳統(tǒng)的度、緊密度、介數(shù)和K-shell方法相比,傳統(tǒng)方法在不同網(wǎng)絡(luò)中各有優(yōu)劣,通用性不強.而我們提出的KSC模型綜合考慮了節(jié)點的內(nèi)部屬性與外部屬性,實驗證明用此方法鑒別節(jié)點的影響力要精確得多,適用范圍更大.我們所提出的模型為這項具有挑戰(zhàn)性研究提供了新的思想和方法.

感謝審稿人對本文提出的寶貴意見和建議,使得文章邏輯更加完整合理.

[1]Watts D J,Strogatz SH 1998 Nature393 440

[2]Barab′asi A L,Albert R 1999 Science 286 509

[3]Barab′asi A L,Albert R,Jeong H,Bianconi G 2000 Science287 2115a

[4]Pastor-Satorras R,Vespignani A 2002 Phys.Rev.E 65 036104

[5]Kempe D,Kleinberg J,Tardos E 2003 Proc.9th ACM SIGKDD Intl.Conf.on Knowledge Discovery and Data Mining New Washington,DC,USA,August 24—27,2003 p137

[6]Gomez-Rodriguez M,Leskovec J,Krause A 2010 Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining Washington,DC,USA,July 25—28,2010 p1019

[7]Budak C,Agrawal D,El Abbadi A 2011 Proceedings of the 20th International Conference on World Wide Web Hyderabad,India,March 28—April 1,2011 p665

[8]Mislove A,Marcon M,Gummadi K P,Druschel P,Bhattacharjee B 2007 Proceedings of the ACM SIGCOMM 2007 Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications Kyoto,Japan,August 27—31,2007 p29

[9]Yuan W G,Liu Y,Cheng J J 2013 Acta Phys.Sin.62 038901(in Chinese)[苑衛(wèi)國,劉云,程軍軍2013物理學(xué)報62 038901]

[10]Weng J,Lim EP,Jiang J,He Q 2010 Proceedingsof the Third International Conferenceon Web Search and Web Data Mining,WSDM 2010 New York,NY,USA,February 4—6,2010 p261

[11]Xu D,Li X,Wang X F 2007 Acta Phys.Sin.56 1313(in Chinese)[許丹,李翔,汪小帆2007物理學(xué)報56 1313]

[12]Naveed N,Gottron T,Kunegis J,Alhadi A C 2011 Proceedingsof the 20th ACM International Conference on Information and Knowledge Management Koblenz,Germany,June 14—17,2011 p1

[13]Gu Y R,Xia L L 2012 Acta Phys.Sin.61 238701(in Chinese)[顧亦然,夏玲玲2012物理學(xué)報61 238701]

[14]Swamynathan G,Wilson C,Boe B,Almeroth K,Zhao B Y 2008 Proceedings of the First Workshop on Online Social Networks ACM New York,USA,August 18,2008 p1

[15]Mislove A,Marcon M,Krishna PG,Druschel P,Bhattacharjee B 2007 Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement(IMC’07)ACM New York,USA,October 24—26,2007 p29

[16]Albert R,Jeong H,Barabasi A L 2000 Nature406 378

[17]Pastor-Satorras R,Vespignani A 2001 Phys.Rev.Lett.86 3200

[18]Freeman L C 1977 Sociometry 40 35

[19]Brin S,Page L 1998 Comput.Netw.ISDNSyst.30 107

[20]Opsahl T,Agneessens F,Skvoretz J2010 Soc.Networks32 245

[21]Sabidussi G 1966 Psychometrika 31 581

[22]Kitsak M,Gallos L K,Havlin S,Liljeros F,Muchnik L,Stanley H E,Makse H A 2010 Tech.Rep.Phys.Soc.1001 5285

[23]Carmi S,Havlin S,Kirkpatrick S,Shavitt Y,Shir E 2007 Proc.Natl.Acad.Sci.USA 104 p1150

[24]Girvan M,Newman M EJ2002 Proc.Natl.Acad.Sci.USA 99 7821

[25]Fortunato S2010 Phys.Rep.486 75

[26]Newman M EJ,Girvan M 2004 Phys.Rev.E 69 026113

[27]Freeman L C 1979 Social Networks1 215

[28]Sabidussi G 1966 Psychometrika 31 581

[29]Lin K 1970 Bell Syst.Tech.J.49 291

[30]Newman M EJ2004 Phys.J.B 38 321

[31]Newman M EJ2004 Phys.Rev.E 69 066133

[32]Guimera R,Amaral L A N 2005 Nature 433 7028

[33]Burt R 2004 Am.J.Soc.110 349

[34]Granovetter M 1973 Am.J.Soc.78 1360

[35]Roy M Anderson,Robert M May 1992 Infectious Diseasesof Humans:Dynamicsand Control.(New York：Oxford University Press)p66

[36]Diekmann O,Heesterbeek JA P 2001 Mathematical Epidemiology of Infectious Diseases：Model Building,Analysisand Interpretation(New York：Wiley Seriesin Mathematical&Computational Biology)

[37]Hethcote H W 2000 Soc.Industr.Appl.Math.42 599

[38]Bernoulli D,Blower S 2004 Rev.Med.Virol.14 275

[39]Chen D B,Lu L Y,Shang M S,Zhang Y C,Zhou T 2012 Physica A 391 1777

[40]Xie N 2006 M.S.Dissertation(Bristo：University of Bristol)

[41]Newman M EJ2006 Phys.Rev.E 74 36104

[42]Spring N,Mahajan R,Wetherall D,Anderson T 2004 Acm.Sigcomm.Comp.Commu.Rev.32 3

[43]Guimer`a R,Danon L,D′?az-Guilera A,Giralt F,Arenas A 2003 Phys.Rev.E 68 065103