程婷婷，王恒山，劉建國

（上海理工大學 管理學院，上海 200093）

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

程婷婷，王恒山，劉建國

（上海理工大學 管理學院，上海 200093）

0 引言

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

1 IM網(wǎng)絡(luò)拓撲模型的建立

IM網(wǎng)絡(luò)是遵循無標度網(wǎng)絡(luò)相類似的動力學特征來進行演化和發(fā)展的，那么可以利用無標度網(wǎng)絡(luò)的建模思想和方法來進行IM網(wǎng)絡(luò)的拓撲建模研究工作。即建?；A(chǔ)是無標度網(wǎng)絡(luò)的BA模型[1-3]，同時考慮IM網(wǎng)絡(luò)與之不同之處以及IM網(wǎng)絡(luò)拓撲演化過程中特有的機制，對BA模型進行改進，得到符合IM網(wǎng)絡(luò)演化特點的拓撲模型?；谇懊鎸δＰ图僭O(shè)和演化機制的分析，在BA模型的基礎(chǔ)上提出改進后的IM網(wǎng)絡(luò)演化模型如下：

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

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

2 仿真算法的建立

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

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

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

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

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

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

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

3）在原始網(wǎng)絡(luò)拓撲圖的基礎(chǔ)上做t步的網(wǎng)絡(luò)演化；

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

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

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

3.1 節(jié)點度分布的計算

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

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

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

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

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

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

3.3 平均最短距離的計算

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

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

4 IM網(wǎng)絡(luò)拓撲仿真結(jié)果分析

利用MATLAB[3-5]對IM網(wǎng)絡(luò)拓撲演化模型進行仿真，并對所生成的IM網(wǎng)絡(luò)的各項統(tǒng)計特征值進行計算。仿真生成的網(wǎng)絡(luò)如圖3所示。其中模型中各參數(shù)分別為：

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

從仿真結(jié)果圖3可以看出，仿真生成的IM拓撲網(wǎng)絡(luò)的節(jié)點度分布并不服從冪律分布，這一點與無標度網(wǎng)絡(luò)不同。這說明IM網(wǎng)絡(luò)中節(jié)點度很大和節(jié)點度很小的節(jié)點數(shù)量都比較少，大多數(shù)節(jié)點的節(jié)點度都處于某一個范圍內(nèi)。下文通過與真實的IM網(wǎng)絡(luò)中聯(lián)系人個數(shù)分布進行對比（如圖4所示），可以看出兩個分布在趨勢上大致符合，即IM系統(tǒng)中擁有少量好友和大量好友的占少數(shù)，大多數(shù)IM用戶擁有的好友數(shù)都處于一個范圍內(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ī)模較大時，IM網(wǎng)絡(luò)的聚類系數(shù)與網(wǎng)絡(luò)規(guī)模沒有明顯的依賴關(guān)系。從仿真結(jié)果可以看出，在網(wǎng)絡(luò)規(guī)模較小時（如1000步之內(nèi)）聚類系數(shù)隨著網(wǎng)絡(luò)規(guī)模的擴大而快速增大；當網(wǎng)絡(luò)規(guī)模在1000步以上時，聚類系數(shù)基本穩(wěn)定在C＝0.95附近。總體來說，IM網(wǎng)絡(luò)擁有較高的聚類系數(shù)。

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

5 結(jié)論

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

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

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

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

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

[1]史明江, 李翔, 汪小帆.基于復(fù)雜網(wǎng)絡(luò)理論的即時通訊病毒研究[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)仿真學報. 2006(l8): 3608.

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

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

程婷婷（1981－），女，山東聊城人，博士研究生，研究方向為系統(tǒng)工程、計算機應(yīng)用技術(shù)。

TN915

A

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

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

2010-11-22

國家自然科學基金（71071098）；上海市重點學科管理科學與工程（S30504）