程婷婷，王恒山，劉建國

（上海理工大學(xué) 管理學(xué)院，上海 200093）

IM網(wǎng)絡(luò)模型與仿真算法的建立

程婷婷，王恒山，劉建國

（上海理工大學(xué) 管理學(xué)院，上海 200093）

0 引言

隨著互聯(lián)網(wǎng)的發(fā)展，即時(shí)通信（IM）系統(tǒng)的應(yīng)用正變得越來越普及，目前，IM系統(tǒng)的應(yīng)用正變得越來越普及，網(wǎng)民可以通過IM系統(tǒng)進(jìn)行溝通交流、娛樂消遣，實(shí)現(xiàn)文字、語音、視頻的實(shí)時(shí)互通交流。同時(shí)，許多組織還借助其來提高業(yè)務(wù)協(xié)同性及反饋的敏感度和快捷度。IM系統(tǒng)允許兩個(gè)用戶之間實(shí)時(shí)的進(jìn)行一對(duì)一（如QQ中好友之間的對(duì)話）或是一對(duì)多（如QQ群里的交流模式）的通信，每一個(gè)用戶都有一個(gè)用戶名和一個(gè)好友列表，列表中可以是該用戶經(jīng)常交流的其他用戶的用戶名，也可以是偶爾交流或是由于某種需要只進(jìn)行過一次交流的用戶名，同時(shí)還包括用戶所加入的有某種用途的群或社團(tuán)。這些好友既可以是用戶的工作同事，也可以是用戶的親朋好友。這種IM用戶間的相互連接關(guān)系構(gòu)成的邏輯網(wǎng)絡(luò)就是IM網(wǎng)絡(luò)[1-5]，從某種意義上說IM用戶的好友列表定義了一種internet中的虛擬社會(huì)關(guān)系網(wǎng)絡(luò)，也是一種復(fù)雜網(wǎng)絡(luò)。因此，本文可以利用復(fù)雜網(wǎng)絡(luò)的思想對(duì)IM網(wǎng)絡(luò)進(jìn)行科學(xué)的研究及統(tǒng)計(jì)學(xué)分析。本文利用圖論的知識(shí)對(duì)IM網(wǎng)絡(luò)進(jìn)行拓?fù)浣＃⒔⒎抡嫠惴▽?duì)模型進(jìn)行結(jié)果分析。

1 IM網(wǎng)絡(luò)拓?fù)淠Ｐ偷慕?/h2>

IM網(wǎng)絡(luò)是遵循無標(biāo)度網(wǎng)絡(luò)相類似的動(dòng)力學(xué)特征來進(jìn)行演化和發(fā)展的，那么可以利用無標(biāo)度網(wǎng)絡(luò)的建模思想和方法來進(jìn)行IM網(wǎng)絡(luò)的拓?fù)浣Ｑ芯抗ぷ?。即建?；A(chǔ)是無標(biāo)度網(wǎng)絡(luò)的BA模型[1-3]，同時(shí)考慮IM網(wǎng)絡(luò)與之不同之處以及IM網(wǎng)絡(luò)拓?fù)溲莼^程中特有的機(jī)制，對(duì)BA模型進(jìn)行改進(jìn)，得到符合IM網(wǎng)絡(luò)演化特點(diǎn)的拓?fù)淠Ｐ??；谇懊鎸?duì)模型假設(shè)和演化機(jī)制的分析，在BA模型的基礎(chǔ)上提出改進(jìn)后的IM網(wǎng)絡(luò)演化模型如下：

1）增長：初始網(wǎng)絡(luò)具有m0個(gè)節(jié)點(diǎn)n0條邊，每次增加一個(gè)新的節(jié)點(diǎn)，連接到m個(gè)已存在的節(jié)點(diǎn)上（m ≤ n0）；

2）局域優(yōu)先連接：在網(wǎng)絡(luò)中己存在的節(jié)點(diǎn)中隨機(jī)選擇M個(gè)構(gòu)成節(jié)點(diǎn)集?（m≤M≤m0＋t），新節(jié)點(diǎn)j與網(wǎng)絡(luò)中己經(jīng)存在的節(jié)點(diǎn)i相連的概率與節(jié)點(diǎn)i的度凡、節(jié)點(diǎn)j的度kj之間滿足如下關(guān)系：

2 仿真算法的建立

為易于仿真，本模型采用下面的運(yùn)算規(guī)則直接仿真。t＝0:m0個(gè)節(jié)點(diǎn)n0條邊（在m0個(gè)節(jié)點(diǎn)間隨機(jī)連接）。每個(gè)時(shí)間步，執(zhí)行下述4個(gè)步驟：

1）添加一個(gè)新的節(jié)點(diǎn)，新節(jié)點(diǎn)上帶有m條邊（m≤ m0）。

3）隨機(jī)選擇npr0對(duì)節(jié)點(diǎn)，在被選中的節(jié)點(diǎn)對(duì)間添加邊（己經(jīng)連接的不做處理）。（np為當(dāng)前網(wǎng)絡(luò)中存在的節(jié)點(diǎn)數(shù)）

4）以概率隨機(jī)選擇nmr1個(gè)節(jié)點(diǎn)，對(duì)每個(gè)被選中的節(jié)點(diǎn)j，隨機(jī)選擇他的兩個(gè)鄰接點(diǎn)，在被選中的鄰接點(diǎn)間添加邊。（已經(jīng)連接的不做處理）。（nm節(jié)點(diǎn)i所擁有的引薦人總數(shù)）

現(xiàn)在將上述算法的仿真過程進(jìn)行如下描述:

l）設(shè)置初始化參數(shù)：m0（初始網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)）、n0（初始網(wǎng)絡(luò)邊數(shù)）、t（演化時(shí)間）、r0（邊的增添速度）、r1（邊的增添速度）；

2）原始網(wǎng)絡(luò)拓?fù)鋱D的生成：在初始化參數(shù)的基礎(chǔ)上，生成原始網(wǎng)絡(luò)的鄰接矩陣，此鄰接矩陣是一個(gè)對(duì)稱矩陣，隨機(jī)生成m0個(gè)節(jié)點(diǎn)，根據(jù)鄰接矩陣確定各個(gè)節(jié)點(diǎn)之間的連接關(guān)系，作出此網(wǎng)絡(luò)的拓?fù)鋱D；

3）在原始網(wǎng)絡(luò)拓?fù)鋱D的基礎(chǔ)上做t步的網(wǎng)絡(luò)演化；

4）生成最終的網(wǎng)絡(luò)拓?fù)鋱D：經(jīng)過t步網(wǎng)絡(luò)演化后，按鄰接矩陣中反映出來的點(diǎn)與點(diǎn)之間的關(guān)系，連接相應(yīng)的節(jié)點(diǎn)對(duì)，生成最終的網(wǎng)絡(luò)拓?fù)鋱D。

3 仿真原理及相關(guān)算法

網(wǎng)絡(luò)以鄰接矩陣的形式存儲(chǔ)在計(jì)算機(jī)中，節(jié)點(diǎn)間有邊存在記為1，無邊存在記為0，如圖1所示，圖（b）即圖（a）所對(duì)應(yīng)的鄰接矩陣。節(jié)點(diǎn)數(shù)目的增長相當(dāng)于矩陣中維數(shù)的增長，邊的增加即將矩陣（b）中相應(yīng)元素改為1。

3.1 節(jié)點(diǎn)度分布的計(jì)算

圖 1 網(wǎng)絡(luò)仿真原理示意圖

一個(gè)節(jié)點(diǎn)擁有的度是該節(jié)點(diǎn)與其它節(jié)點(diǎn)相連的邊數(shù)，度是描述網(wǎng)絡(luò)局部特征性的基本參數(shù)，對(duì)矩陣的第i行求和可得節(jié)點(diǎn)i的度數(shù)。度分布p（k）定義為隨機(jī)選擇一個(gè)節(jié)點(diǎn)，度為k的概率，計(jì)算方法即p（k）等于網(wǎng)絡(luò)中度為k的節(jié)點(diǎn)數(shù)占網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)的比例。

3.2 聚類系數(shù)的計(jì)算

對(duì)與節(jié)點(diǎn)i相連的節(jié)點(diǎn)構(gòu)成的ki行ki列鄰接矩陣元素進(jìn)行求和再除2，即得節(jié)點(diǎn)i的鄰接點(diǎn)間實(shí)際存在的邊數(shù)ei，以圖1（a）中節(jié)點(diǎn)A為例，節(jié)點(diǎn)A的鄰接點(diǎn)間實(shí)際存在的邊數(shù)即節(jié)點(diǎn)B、C、E構(gòu)成的鄰接矩陣如圖2，計(jì)算得eA＝2。

圖 2 節(jié)點(diǎn)A鄰接點(diǎn)構(gòu)成的鄰接矩陣

計(jì)算得每個(gè)節(jié)點(diǎn)的聚類系數(shù)，對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的聚類系數(shù)求平均，即得整個(gè)網(wǎng)絡(luò)的聚類系數(shù)。

3.3 平均最短距離的計(jì)算

Floyd算法是Floyd于1962年提出的用于計(jì)算所有節(jié)點(diǎn)對(duì)之間最短路徑的算法。該算法中，先將鄰接矩陣中非直接相連的節(jié)點(diǎn)間距離設(shè)為無窮大，對(duì)角線上的值設(shè)為0，其余元素保持不變，記為初始距離矩陣，如圖1（c），按式1循環(huán)更新距離矩陣，a從1循環(huán)到N即得節(jié)點(diǎn)對(duì)間的最短距離矩陣。

其中uij是距離矩陣第i行第j列的元素，代表節(jié)點(diǎn)i，j間的距離。每對(duì)節(jié)點(diǎn)的最短距離后，即可求得整個(gè)網(wǎng)絡(luò)的平均最短距離。

4 IM網(wǎng)絡(luò)拓?fù)浞抡娼Y(jié)果分析

利用MATLAB[3-5]對(duì)IM網(wǎng)絡(luò)拓?fù)溲莼Ｐ瓦M(jìn)行仿真，并對(duì)所生成的IM網(wǎng)絡(luò)的各項(xiàng)統(tǒng)計(jì)特征值進(jìn)行計(jì)算。仿真生成的網(wǎng)絡(luò)如圖3所示。其中模型中各參數(shù)分別為：

圖 3 仿真網(wǎng)絡(luò)生成示例

從仿真結(jié)果圖3可以看出，仿真生成的IM拓?fù)渚W(wǎng)絡(luò)的節(jié)點(diǎn)度分布并不服從冪律分布，這一點(diǎn)與無標(biāo)度網(wǎng)絡(luò)不同。這說明IM網(wǎng)絡(luò)中節(jié)點(diǎn)度很大和節(jié)點(diǎn)度很小的節(jié)點(diǎn)數(shù)量都比較少，大多數(shù)節(jié)點(diǎn)的節(jié)點(diǎn)度都處于某一個(gè)范圍內(nèi)。下文通過與真實(shí)的IM網(wǎng)絡(luò)中聯(lián)系人個(gè)數(shù)分布進(jìn)行對(duì)比（如圖4所示），可以看出兩個(gè)分布在趨勢(shì)上大致符合，即IM系統(tǒng)中擁有少量好友和大量好友的占少數(shù)，大多數(shù)IM用戶擁有的好友數(shù)都處于一個(gè)范圍內(nèi)。

圖 4 度分布曲線及數(shù)據(jù)擬合示意圖

圖5給出了IM網(wǎng)絡(luò)演化模型的平均聚類系數(shù)C隨網(wǎng)絡(luò)規(guī)模t的變化關(guān)系，發(fā)現(xiàn)在網(wǎng)絡(luò)規(guī)模較大時(shí)，IM網(wǎng)絡(luò)的聚類系數(shù)與網(wǎng)絡(luò)規(guī)模沒有明顯的依賴關(guān)系。從仿真結(jié)果可以看出，在網(wǎng)絡(luò)規(guī)模較小時(shí)（如1000步之內(nèi)）聚類系數(shù)隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大而快速增大；當(dāng)網(wǎng)絡(luò)規(guī)模在1000步以上時(shí)，聚類系數(shù)基本穩(wěn)定在C＝0.95附近?？傮w來說，IM網(wǎng)絡(luò)擁有較高的聚類系數(shù)。

綜上所述，IM網(wǎng)絡(luò)的節(jié)點(diǎn)度不服從冪律分布，度數(shù)極小和極大的節(jié)點(diǎn)出現(xiàn)的概率較小，這與實(shí)際情況相符合。同時(shí)，具有較短的平均路徑長度、較高的聚類系數(shù)和清晰的社團(tuán)結(jié)構(gòu)。

5 結(jié)論

IM網(wǎng)絡(luò)演化模型在本質(zhì)上反映的是IM用戶之間特定的社會(huì)關(guān)系網(wǎng)絡(luò)，了解IM網(wǎng)絡(luò)的統(tǒng)計(jì)特征，在一定程度上有助于更好地研究和分析其上消息、病毒等的傳播特性，更好地進(jìn)行IM消息傳播干預(yù)機(jī)制的研究。

1）該模型結(jié)合局部范圍擇優(yōu)連接機(jī)制、熟人引薦機(jī)制對(duì)BA模型進(jìn)行擴(kuò)展，生成的網(wǎng)絡(luò)中節(jié)點(diǎn)度分布不服從冪律分布，度數(shù)極小和極大的節(jié)點(diǎn)出現(xiàn)的概率密度較小，與問卷調(diào)查數(shù)據(jù)得出的聯(lián)系人個(gè)數(shù)分布形狀較為接近。

2）通過對(duì)IM用戶行為特征的調(diào)查研究發(fā)現(xiàn)，IM用戶使用點(diǎn)對(duì)點(diǎn)方式的頻率高于群組方式，同時(shí)群組方式的消息傳遞針對(duì)性較差，且IM用戶對(duì)群組消息的關(guān)注程度較弱。因此，本文主要研究IM系統(tǒng)中點(diǎn)對(duì)點(diǎn)方式下的消息傳播情況。

3）IM拓?fù)渚W(wǎng)絡(luò)具有顯著的小世界特征，較大的聚類系數(shù)和明顯的社團(tuán)結(jié)構(gòu)，與真實(shí)網(wǎng)絡(luò)情況十分接近。

4）本模型仿真結(jié)果說明該模型的演化機(jī)制可以在一定程度上解釋真實(shí)IM網(wǎng)絡(luò)的形成機(jī)制。

[1]史明江, 李翔, 汪小帆.基于復(fù)雜網(wǎng)絡(luò)理論的即時(shí)通訊病毒研究[J]. 計(jì)算機(jī)工程與應(yīng)用. 2006(11): 110-115.

[2]YangGang, ZhouTao, WangJie, etal. Epidemic spread in weighted seale-free networks. Chinese Physics Letters,2005, 22(2): 501.

[3]Morenol Y, Pastor-Satorras R, Vespignanil A. Epidemic outbreaks in complex heterogeneous networks. Eur. Phys. J.B, 2002, 26(4): 521-529.

[4]劉常星, 胡曉峰, 司光亞, 等. 基于小世界網(wǎng)絡(luò)的輿論傳播模型[J]. 系統(tǒng)仿真學(xué)報(bào). 2006(l8): 3608.

[5]劉常星, 胡曉峰, 司光亞, 等. 輿論涌現(xiàn)模型研究[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué). 2oo7(l): 24-27.

The construction of model of IM topological network and simulation algorithm

CHENG Ting-ting, WANG Heng-shan, LIU Jian-guo

IM系統(tǒng)的應(yīng)用正變得越來越普及，網(wǎng)民可以通過IM系統(tǒng)進(jìn)行溝通交流、娛樂消遣，實(shí)現(xiàn)文字、語音、視頻的實(shí)時(shí)互通交流。同時(shí)，許多組織還借助其來提高業(yè)務(wù)協(xié)同性及反饋的敏感度和快捷度。IM系統(tǒng)允許兩個(gè)用戶之間實(shí)時(shí)的進(jìn)行一對(duì)一或是一對(duì)多的通信，這種IM用戶間的相互連接關(guān)系構(gòu)成的邏輯網(wǎng)絡(luò)就是IM網(wǎng)絡(luò)，從某種意義上說IM用戶的好友列表定義了一種internet中的虛擬社會(huì)關(guān)系網(wǎng)絡(luò)，也是一種復(fù)雜網(wǎng)絡(luò)。因此，本文可以利用復(fù)雜網(wǎng)絡(luò)的思想對(duì)IM網(wǎng)絡(luò)進(jìn)行科學(xué)的研究及統(tǒng)計(jì)學(xué)分析。本文結(jié)合局部范圍擇優(yōu)連接機(jī)制、熟人引薦機(jī)制對(duì)BA模型進(jìn)行擴(kuò)展，生成的網(wǎng)絡(luò)中節(jié)點(diǎn)度分布不服從冪律分布，度數(shù)極小和極大的節(jié)點(diǎn)出現(xiàn)的概率密度較小，與問卷調(diào)查數(shù)據(jù)得出的聯(lián)系人個(gè)數(shù)分布形狀較為接近,主要研究IM系統(tǒng)中點(diǎn)對(duì)點(diǎn)方式下的消息傳播情況。

IM網(wǎng)絡(luò)模型；仿真算法模型；仿真結(jié)果分析

程婷婷（1981－），女，山東聊城人，博士研究生，研究方向?yàn)橄到y(tǒng)工程、計(jì)算機(jī)應(yīng)用技術(shù)。

TN915

A

1009-0134(2011)4(下)-0128-03

10.3969/j.issn.1009-0134.2011.4(下).37

2010-11-22

國家自然科學(xué)基金（71071098）；上海市重點(diǎn)學(xué)科管理科學(xué)與工程（S30504）