復(fù)雜網(wǎng)絡(luò)中的在線社交網(wǎng)絡(luò)演化模型

王景麗，許立波，龐超逸

(1. 寧波大紅鷹學(xué)院 信息工程學(xué)院，浙江 寧波 315175； 2. 浙江大學(xué) 寧波理工學(xué)院， 浙江 寧波 315000； 3. 浙江大學(xué) 寧波理工學(xué)院， 浙江 寧波 315000)

?

復(fù)雜網(wǎng)絡(luò)中的在線社交網(wǎng)絡(luò)演化模型

王景麗1，許立波2，龐超逸3

(1. 寧波大紅鷹學(xué)院 信息工程學(xué)院，浙江 寧波 315175； 2. 浙江大學(xué) 寧波理工學(xué)院， 浙江 寧波 315000； 3. 浙江大學(xué) 寧波理工學(xué)院， 浙江 寧波 315000)

摘要：在線社交網(wǎng)絡(luò)是一種廣泛存在的社會網(wǎng)絡(luò)，其節(jié)點度遵循冪率分布規(guī)律，但對于其結(jié)構(gòu)演化模型方面的相關(guān)研究還不多。基于復(fù)雜網(wǎng)絡(luò)理論研究在線社交網(wǎng)絡(luò)內(nèi)部結(jié)構(gòu)特征，提出一種結(jié)合內(nèi)增長、外增長及內(nèi)部邊更替的演化模型，借助平均場理論分析該模型的拓撲特性，實驗和理論分析表明由該模型生成的網(wǎng)絡(luò)，其度分布服從冪率分布，且通過調(diào)整參數(shù)，冪率指數(shù)在1~3，能較好地反映不同類型的真實在線社交網(wǎng)絡(luò)的度分布特征，因此具有廣泛適用性。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；社交網(wǎng)絡(luò)；度分布；冪率分布；演化；平均場；節(jié)點度；拓撲

中文引用格式：王景麗，許立波，龐超逸. 復(fù)雜網(wǎng)絡(luò)中的在線社交網(wǎng)絡(luò)演化模型[J]. 智能系統(tǒng)學(xué)報， 2015, 10(6): 949-953.

復(fù)雜網(wǎng)絡(luò)作為刻畫和研究復(fù)雜系統(tǒng)結(jié)構(gòu)及其動態(tài)發(fā)展的強有力工具之一，近年來迅速成為學(xué)術(shù)界研究的熱點，并與計算機科學(xué)、生物學(xué)、社會學(xué)、經(jīng)濟學(xué)等學(xué)科交叉融合，廣泛應(yīng)用于諸如生物網(wǎng)絡(luò)、傳染病控制、知識網(wǎng)絡(luò)、電力網(wǎng)、互聯(lián)網(wǎng)等各種自然和社會動態(tài)網(wǎng)絡(luò)及系統(tǒng)研究中.復(fù)雜網(wǎng)絡(luò)的研究涵蓋很多方面，其中網(wǎng)絡(luò)的演化及建模研究能夠相當(dāng)程度地揭示實際網(wǎng)絡(luò)及系統(tǒng)的結(jié)構(gòu)組成及變化規(guī)律，從而能夠?qū)ο到y(tǒng)的未來發(fā)展做出預(yù)測并提早設(shè)置改進措施。因此演化模型一直是復(fù)雜網(wǎng)絡(luò)研究的熱點之一，并提出了很多網(wǎng)絡(luò)演化模型，以刻畫現(xiàn)實中各種不同網(wǎng)絡(luò)的特征及結(jié)構(gòu)。

Watts等[1]提出小世界模型，具有短路徑、高聚類和強傳遞性特征，模擬人際關(guān)系網(wǎng)絡(luò)的演化過程。Barabási等[2]在研究萬維網(wǎng)時提出基于增長和優(yōu)先連接的無標(biāo)度BA模型，連接概率與節(jié)點度成線性正比，較好地模擬出萬維網(wǎng)中冪率度分布特征和馬太效應(yīng)。之后，研究者們發(fā)現(xiàn)冪率度分布特征廣泛存在于各種現(xiàn)實網(wǎng)絡(luò)，隨著Falatous等[3]發(fā)現(xiàn)互聯(lián)網(wǎng)拓撲的冪率特性，AB模型[4]被提出應(yīng)用于互聯(lián)網(wǎng)拓撲建模，其在BA模型基礎(chǔ)上增加了內(nèi)部連接和重配置過程；基于現(xiàn)實互聯(lián)網(wǎng)連接傾向度更高的觀測現(xiàn)象，廣義線性優(yōu)先模型[5]改進BA模型以模擬新節(jié)點連接對高度hub的優(yōu)先選擇性；動態(tài)優(yōu)先模型[6]基于不同層級AS間的關(guān)系，反映出互聯(lián)網(wǎng)中的小世界特性；多局域世界模型[7-8]考慮節(jié)點連接的局域特征，能較好反映節(jié)點層次性和聚類性。眾多研究表明，合作網(wǎng)絡(luò)[9]、軟件組件系統(tǒng)[10]、蛋白質(zhì)網(wǎng)絡(luò)[11]、在線社交網(wǎng)絡(luò)[12]、傳感器網(wǎng)絡(luò)[13]等都呈現(xiàn)出了度分布冪率特性，局部事件模型被用來模擬軟件組件系統(tǒng)的無標(biāo)度特性；頂點復(fù)制模型[14]描述知識引用網(wǎng)絡(luò)和新陳代謝網(wǎng)絡(luò)，新節(jié)點不完全遵循優(yōu)先連接機制，而是通過模仿已有節(jié)點來構(gòu)建模型。

在線社交網(wǎng)絡(luò)如微博、交友等是社會網(wǎng)絡(luò)的一種典型關(guān)系網(wǎng)絡(luò)，將每個用戶看作網(wǎng)絡(luò)節(jié)點，許多研究已經(jīng)表明其節(jié)點度遵循冪率分布規(guī)律，但對于其結(jié)構(gòu)演化模型方面的相關(guān)研究還比較少。一方面，目前研究集中于通過抽樣數(shù)據(jù)來進行數(shù)據(jù)分析，從統(tǒng)計角度發(fā)現(xiàn)拓撲特征，雖然能較好還原真實網(wǎng)絡(luò)特性，但這種研究屬于靜態(tài)分析，不能模擬動態(tài)過程以及添加行為過程；另一方面，研究表明在線社交網(wǎng)絡(luò)節(jié)點可能比一般網(wǎng)絡(luò)更傾向于連接度大的節(jié)點，很多傳統(tǒng)模型不能直接適用，需要進行一定的改進。

本文提出一種在線社交網(wǎng)絡(luò)演化模型，以注冊用戶作為網(wǎng)絡(luò)節(jié)點，節(jié)點間的連邊就是注冊用戶間的關(guān)注關(guān)系，節(jié)點和連邊共同構(gòu)成網(wǎng)絡(luò)，不失一般性，本文將此網(wǎng)絡(luò)抽象成無向網(wǎng)絡(luò)圖。演化模型考慮隨機增長、優(yōu)先連接、內(nèi)部增長及連接更替4種機制，采用平均場理論對模型度分布進行理論分析。理論分析和仿真表明，演化模型網(wǎng)絡(luò)的度呈現(xiàn)無尺度特征，且能夠模擬較大范圍的冪率分布，具有廣泛的適用性，并能一定程度地模擬真實在線社交網(wǎng)絡(luò)的度分布特征。

1在線社交網(wǎng)絡(luò)演化模型

本文構(gòu)造無向的網(wǎng)絡(luò)演化模型，模擬了內(nèi)部增長即網(wǎng)絡(luò)中現(xiàn)有節(jié)點間添加新連接、內(nèi)部調(diào)整即現(xiàn)有節(jié)點間重連接及網(wǎng)絡(luò)增長即新節(jié)點和現(xiàn)有節(jié)點的連接等機制，對于有向網(wǎng)絡(luò)亦可以參照文中分析。具體演化步驟如下：

1)初始化：初始網(wǎng)絡(luò)包含m0個節(jié)點，每個節(jié)點與其余m0-1個節(jié)點相連；

2)隨機增長：每個時間步添加一個新節(jié)點，并連接到m1個原有節(jié)點上，且滿足m1

3)優(yōu)先連接：新節(jié)點與原有節(jié)點i相連接的概率Πi表達式為

(1)

式中：ki為節(jié)點i的度；

4)內(nèi)部隨機增長：每個時間步在網(wǎng)絡(luò)內(nèi)增加m2條邊，節(jié)點i被選為新增邊的端點的概率Πi按式(1)計算，且m2

5)內(nèi)部優(yōu)先連接更替：每個時間步選擇m3條邊進行更替，更替方法為先隨機選擇節(jié)點i，隨機移除與節(jié)點i相連的某條邊lij，添加以連接節(jié)點j和節(jié)點r的邊ljr，節(jié)點r按Πr概率擇優(yōu)選取，Πr按式(1)計算。

相比一般網(wǎng)絡(luò)，在線社交網(wǎng)絡(luò)中的連接度大的節(jié)點可能更容易得到大量連接，因此在演化模型中，除了新節(jié)點和內(nèi)部增長具有優(yōu)先連接機制外，內(nèi)部優(yōu)先連接更替也不同于一般模型中的重連機制，后者通常是以邊lir替代lij，節(jié)點i的度不發(fā)生變化；而內(nèi)部優(yōu)先連接更替是以ljr替代lij，更加強化高連接度節(jié)點間的連接傾向，且為防止出現(xiàn)孤立節(jié)點，模型設(shè)定當(dāng)被選擇節(jié)點度為1時，進行重新選點。

2演化模型的度分布屬性

根據(jù)平均場理論對模型的度分布進行近似分析，假設(shè)節(jié)點度ki隨時間t連續(xù)變化，對ki變化率求解：

隨機增長：當(dāng)新節(jié)點加入時，按概率Πi連接到m1個原節(jié)點上，則ki變化率方程為

(2)

內(nèi)部隨機增長：邊的端點按概率Πi優(yōu)先選擇，邊有2個端點，則ki變化率方程為

(3)

(4)

綜合式(2)~(4)，得到演化模型ki變化率方程為

(5)

(6)

用變量分離法解此一階微分方程可得

(7)

設(shè)節(jié)點i是在ti時刻進入網(wǎng)絡(luò)，則有初始條件ki(ti)=m1，結(jié)合式(7)可得

網(wǎng)絡(luò)中節(jié)點i的度ki(t)小于k的概率為

(8)

P(ti)=1/N≈1/t

故有

假設(shè)時間t→∞時，網(wǎng)絡(luò)節(jié)點的度具有穩(wěn)態(tài)分布P(k)：

(9)

則度分布指數(shù)

(10)

3仿真實驗和討論

仿真實驗分為2部分：1)采用MATLAB軟件開發(fā)仿真程序，通過程序運行的結(jié)果來分析演化模型的度統(tǒng)計特性、相關(guān)參數(shù)的影響以及理論分析的準(zhǔn)確性；2)通過MATLAB軟件分析真實社交網(wǎng)絡(luò)數(shù)據(jù)的度統(tǒng)計特性，觀察演化模型理論分析值的模擬程度。

分析度分布指數(shù)γ的表達式(10)，可以看到3個參數(shù)的作用各不相同，m1和m3決定γ取值大于2或者小于2，m2則只影響值的大小，而m1和m2又影響網(wǎng)絡(luò)的節(jié)點規(guī)模和平均度數(shù)。圖1、2、3分別顯示了1 500節(jié)點網(wǎng)絡(luò)演化模型在不同參數(shù)取值下的度分布情況，演化網(wǎng)絡(luò)度分布呈現(xiàn)冪率特征，且根據(jù)參數(shù)取值的不同在1~3之間變化，圖中直線由度分布理論表達式(9)近似給出。

圖1　演化模型度分布(m1=2,m2=1,m3=0)Fig.1　Degree distribution of evolution model(m1=2 ，m2=1 ，m3=0)

可以看到，在m1和m2值不變的條件下，m3值越大，無標(biāo)度特性越大。圖4則顯示在m1和m3值不變的條件下，m2值變化對度分布冪率的影響，分布冪率值隨著m2值變大而增大，但逐步接近某固定值，由式(10)可知，此值為2。

圖2　演化模型度分布(m1=2，m2=1，m3=3)Fig.2　Degree distribution of evolution model(m1=2，m2=1，m3=3)

圖3　演化模型度分布(m1=2，m2=1，m3=6)Fig.3　Degree distribution of evolution model(m1=2，m2=1，m3=6)

圖4　m2取不同值時的度分布變化(m1=2，m3=8)Fig.4　Degree distribution changes according to different values of m2 (m1=2，m3=8)

采用真實在線社交網(wǎng)絡(luò)與本文演化模型的度分布進行對比分析。圖5顯示一個美國政治家博客用戶網(wǎng)絡(luò)[15]的度分布情況，該網(wǎng)絡(luò)節(jié)點為博客網(wǎng)頁，邊表示為網(wǎng)頁間的超鏈接，包含1 224個節(jié)點和16 714條無向邊。可以看到，博客網(wǎng)頁網(wǎng)絡(luò)的度分布冪率在1~2，傳統(tǒng)很多演化模型如BA及其變型模型的度分布冪率在2~3，不能較好地表征博客網(wǎng)絡(luò)的度分布特征。圖中擬合直線冪率值為1.4，由本文表達式(9)直接給出，其中參數(shù)取值m1=2、m2=0、m3=8，實際上有很多種參數(shù)取值方案，這里只給出其中一種僅用于說明效果。通過調(diào)整參數(shù)，演化模型能較好地模擬美國政治家博客用戶網(wǎng)絡(luò)的度分布特征。

圖5　政治家博客用戶網(wǎng)絡(luò)度分布冪率Fig.5　Power-law degree distribution network of Political blogs

圖6顯示維基選舉社交網(wǎng)絡(luò)[15]度分布情況，該網(wǎng)絡(luò)節(jié)點為維基用戶，邊表示為用戶間的選舉行為，包含7 000多節(jié)點。該網(wǎng)絡(luò)度分布冪率也在1~2之間，傳統(tǒng)模型不能較準(zhǔn)確地表征。圖中擬合直線冪率值為1.5，由表達式(9)直接給出，其中參數(shù)取值m1=2、m2=0、m3=6，這里同樣只給出一種取值方案用于說明效果。可以看到，通過調(diào)整參數(shù)，演化模型能較好地模擬維基選舉社交網(wǎng)絡(luò)的度分布特征。

圖6　維基選舉社交網(wǎng)絡(luò)度分布冪率Fig.6　Power-law degree distribution of Wiki vote

4結(jié)束語

在線社交網(wǎng)絡(luò)作為一種普遍存在的社會網(wǎng)絡(luò)，已經(jīng)引起廣泛的研究并證實其具有無標(biāo)度特性，但對其結(jié)構(gòu)演化模型的研究相對較少。本文提出一種基于內(nèi)增長、外增長及內(nèi)部邊更替的在線社交網(wǎng)絡(luò)演化模型，其優(yōu)先連接機制具有強化高連接度節(jié)點間的連接傾向的特征。理論分析和實驗表明，該模型具有無標(biāo)度特性，且通過調(diào)整參數(shù)的不同取值，度分布冪率指數(shù)在1~3，具有普遍適用性。通過和真實在線社交網(wǎng)絡(luò)結(jié)構(gòu)的模擬分析，本文提出的演化模型能較好地反映出在線社交網(wǎng)絡(luò)的度分布特征，且能夠刻畫不同類型的社交網(wǎng)絡(luò)，具有較強的實用意義。

本文演化模型是基于最基本的無向無權(quán)網(wǎng)絡(luò)，下一步的工作考慮擴展到復(fù)雜的多屬性異構(gòu)網(wǎng)絡(luò)，這些屬性包括有向、權(quán)值、節(jié)點能力等。借助因素空間理論[16-17]，將多屬性異構(gòu)網(wǎng)絡(luò)映射成因素空間網(wǎng)絡(luò)，網(wǎng)絡(luò)節(jié)點映射成因素空間對象，使其更加貼近于現(xiàn)實網(wǎng)絡(luò)，通過權(quán)變、拓撲結(jié)構(gòu)、動態(tài)時空等因素空間理論工具研究演化網(wǎng)絡(luò)模型和實際在線社會網(wǎng)絡(luò)的生成、發(fā)展及其特征。

參考文獻:

[1]WATTS D J, STROGATZ S H. Collective dynamics of 'small-world′ networks[J]. Nature, 1998, 393(6684): 440-442.

[2]BARABASI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.

[3]FALOUTSOS M, FALOUTSOS P, FALOUTSOS C. On power-law relationships of the Internet topology[J]. ACM SIGCOMM Computer Communication Review Homepage, 1999, 29(4): 251-262.

[4]ALBERT R, BARABASI A L. Topology of evolving networks: local events and universality[J]. Physical Review Letters 2000, 85(24): 5234-5237.

[5]BU T, TOWSLEY D. On distinguishing between Internet power law topology generators[C]//Proceedings of INFOCOM 2002. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. New York, NY: IEEE, 2002, 2: 638-647.

[6]PARK S T, PENNOCK D M, GILES C L. Comparing static and dynamic measurements and models of the Internet's as topology[C]//Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies. Hong Kong: IEEE, 2004, 3: 1616-1627.

[7]CHEN Guangrong, FAN Zhenping, LI Xiang. Modeling the complex Internet topology[C]//KOCAREV L, VATTAY G. Complex Dynamics in Communication Networks. Berlin Heidelberg: Springer, 2005.

[8]田思, 李慧嘉, 趙岳. 一種新型多局域世界網(wǎng)絡(luò)模型分析[J]. 計算機應(yīng)用研究, 2013, 30(3): 869-872.

TIAN Si, LI Huijia, ZHAO Yue. Analysis of novel multi-local world network model[J]. Application Research of Computers, 2013, 30(3): 869-872.

[9]NEWMAN M E J. The structure of scientific collaboration networks[C]. Proceedings of National Academy Sciences, 2001, 98(2): 404-409.

[10]MYERS C R. Software systems as complex networks: structure, function, and evolvability of software collaboration graphs[J]. Physical Review E, 2003, 68(4Pt2): 046116.

[11]JEONG H, MASON S P, BARABASI A L, et al. Lethality and centrality in protein networks[J]. Nature, 2001, 411(6833): 41-42.

[12]王亞奇, 王靜, 楊海濱. 基于復(fù)雜網(wǎng)絡(luò)理論的微博用戶關(guān)系網(wǎng)絡(luò)演化模型研究[J]. 物理學(xué)報, 2014, 63(20): 208902.

WANG Yaqi, WANG Jing, YANG Haibin. An evolution model of microblog user relationship networks based on complex network theory[J]. Acta Physica Sinica, 2014, 63(20): 208902.

[13]劉浩然, 尹文曉, 董明如, 等. 一種強容侵能力的無線傳感器網(wǎng)絡(luò)無標(biāo)度拓撲模型研究[J]. 物理學(xué)報, 2014, 63(9): 090503.

LIU Haoran, YIN Wenxiao, DONG Mingru, et al. Study on the scale-free topology model with strong intrusion-tolerance ability in wireless sensor networks[J]. Acta Physica Sinica, 2014, 63(9): 090503.

[14]SOLE R V, PASTOR-SATORRAS R, SMITH E, et al. A model of large-scale proteome evolution[J]. Advances in Complex Systems, 2002, 5(1): 43-54.

[15]維基選舉社交網(wǎng)絡(luò)[OL/EB].[2014-12-21].http://www.linkprediction.org/index.php/link/resource/data.

[16]汪培莊. 因素空間與因素庫[J]. 遼寧工程技術(shù)大學(xué)學(xué)報: 自然科學(xué)版, 2013, 32(10): 1297-1304.

WANG Peizhuang. Factor spaces and factor data-bases[J]. Journal of Liaoning Technical University: Natural Science, 2013, 32(10): 1297-1304.

[17]汪培莊. 因素空間與數(shù)據(jù)科學(xué)[J]. 遼寧工程技術(shù)大學(xué)學(xué)報: 自然科學(xué)版, 2015, 34(2): 273-280.

WANG Peizhuang. Factor spaces and data science[J]. Journal of Liaoning Technical University: Natural Science, 2015, 34(2): 273-280.

王景麗，女，1981年生，講師。主要研究方向為復(fù)雜網(wǎng)絡(luò)。

許立波，男，1976年生，講師，博士。主要研究方向為復(fù)雜網(wǎng)絡(luò)、overlay網(wǎng)絡(luò)。

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20151110.1354.012.html

英文引用格式：WANG Jingli, XU Libo, PANG Chaoyi. Evolution model of online social networks based on complex networks[J]. CAAI Transactions on Intelligent Systems, 2015, 10(6): 949-953.

Evolution model of online social networks based on complex networks

WANG Jingli1, XU Libo2, PANG Chaoyi3

(1. Information Engineering, Ningbo Dahongying University, Ningbo 315175, China; 2. Research Center on Intelligent Computing and Data Management Ningbo Institute of Technology, Zhejiang University, Ningbo 315000, China; 3. Research Center on Intelligent Computing and Data Management Ningbo Institute of Technology, Zhejiang University, Ningbo 315000, China)

Abstract：As a widespread social network, the node degree of online social networks has been proven by many researchers to follow the power-law distribution. However, there are few studies modeling the evolution of its structure. In this paper, we propose an evolution model that combines the inside growth, outside growth, and edge replacement based on those of complex networks. The topology properties of this model are analyzed using the mean-field theory. Experiment and theoretical analyses show that the degree of a node in a network generated by the new evolution model follows the power-law distribution and that the power-law index ranges between 1 and 3. Therefore, the proposed model can better reflect the node degree distribution characteristics of different types of real online social networks and will have wide applicability.

Keywords：complex network; social network; degree distribution; power-law distribution; evolution; mean field; node degree; topology

作者簡介：

通信作者：王景麗.E-mailjingli.wang@nbdhyu.edu.cn

基金項目：國家自然科學(xué)基金資助項目(71271191)；寧波市自然科學(xué)基金資助項目(2015A610138).

收稿日期：2015-07-05. 網(wǎng)絡(luò)出版日期：2015-11-10.

中圖分類號：TP393

文獻標(biāo)志碼：A

文章編號：1673-4785(2015)06-0949-05

DOI:10.11992/tis.201507042