IM網絡模型與仿真算法的建立

程婷婷，王恒山，劉建國

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

IM網絡模型與仿真算法的建立

程婷婷，王恒山，劉建國

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

0 引言

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

1 IM網絡拓撲模型的建立

IM網絡是遵循無標度網絡相類似的動力學特征來進行演化和發展的，那么可以利用無標度網絡的建模思想和方法來進行IM網絡的拓撲建模研究工作。即建模基礎是無標度網絡的BA模型[1-3]，同時考慮IM網絡與之不同之處以及IM網絡拓撲演化過程中特有的機制，對BA模型進行改進，得到符合IM網絡演化特點的拓撲模型。基于前面對模型假設和演化機制的分析，在BA模型的基礎上提出改進后的IM網絡演化模型如下：

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

2）局域優先連接：在網絡中己存在的節點中隨機選擇M個構成節點集?（m≤M≤m0＋t），新節點j與網絡中己經存在的節點i相連的概率與節點i的度凡、節點j的度kj之間滿足如下關系：

2 仿真算法的建立

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

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

3）隨機選擇npr0對節點，在被選中的節點對間添加邊（己經連接的不做處理）。（np為當前網絡中存在的節點數）

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

現在將上述算法的仿真過程進行如下描述:

l）設置初始化參數：m0（初始網絡節點數）、n0（初始網絡邊數）、t（演化時間）、r0（邊的增添速度）、r1（邊的增添速度）；

2）原始網絡拓撲圖的生成：在初始化參數的基礎上，生成原始網絡的鄰接矩陣，此鄰接矩陣是一個對稱矩陣，隨機生成m0個節點，根據鄰接矩陣確定各個節點之間的連接關系，作出此網絡的拓撲圖；

3）在原始網絡拓撲圖的基礎上做t步的網絡演化；

4）生成最終的網絡拓撲圖：經過t步網絡演化后，按鄰接矩陣中反映出來的點與點之間的關系，連接相應的節點對，生成最終的網絡拓撲圖。

3 仿真原理及相關算法

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

3.1 節點度分布的計算

圖 1 網絡仿真原理示意圖

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

3.2 聚類系數的計算

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

圖 2 節點A鄰接點構成的鄰接矩陣

計算得每個節點的聚類系數，對網絡中所有節點的聚類系數求平均，即得整個網絡的聚類系數。

3.3 平均最短距離的計算

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

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

4 IM網絡拓撲仿真結果分析

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

圖 3 仿真網絡生成示例

從仿真結果圖3可以看出，仿真生成的IM拓撲網絡的節點度分布并不服從冪律分布，這一點與無標度網絡不同。這說明IM網絡中節點度很大和節點度很小的節點數量都比較少，大多數節點的節點度都處于某一個范圍內。下文通過與真實的IM網絡中聯系人個數分布進行對比（如圖4所示），可以看出兩個分布在趨勢上大致符合，即IM系統中擁有少量好友和大量好友的占少數，大多數IM用戶擁有的好友數都處于一個范圍內。

圖 4 度分布曲線及數據擬合示意圖

圖5給出了IM網絡演化模型的平均聚類系數C隨網絡規模t的變化關系，發現在網絡規模較大時，IM網絡的聚類系數與網絡規模沒有明顯的依賴關系。從仿真結果可以看出，在網絡規模較小時（如1000步之內）聚類系數隨著網絡規模的擴大而快速增大；當網絡規模在1000步以上時，聚類系數基本穩定在C＝0.95附近。總體來說，IM網絡擁有較高的聚類系數。

綜上所述，IM網絡的節點度不服從冪律分布，度數極小和極大的節點出現的概率較小，這與實際情況相符合。同時，具有較短的平均路徑長度、較高的聚類系數和清晰的社團結構。

5 結論

IM網絡演化模型在本質上反映的是IM用戶之間特定的社會關系網絡，了解IM網絡的統計特征，在一定程度上有助于更好地研究和分析其上消息、病毒等的傳播特性，更好地進行IM消息傳播干預機制的研究。

1）該模型結合局部范圍擇優連接機制、熟人引薦機制對BA模型進行擴展，生成的網絡中節點度分布不服從冪律分布，度數極小和極大的節點出現的概率密度較小，與問卷調查數據得出的聯系人個數分布形狀較為接近。

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

3）IM拓撲網絡具有顯著的小世界特征，較大的聚類系數和明顯的社團結構，與真實網絡情況十分接近。

4）本模型仿真結果說明該模型的演化機制可以在一定程度上解釋真實IM網絡的形成機制。

[1]史明江, 李翔, 汪小帆.基于復雜網絡理論的即時通訊病毒研究[J]. 計算機工程與應用. 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]劉常星, 胡曉峰, 司光亞, 等. 基于小世界網絡的輿論傳播模型[J]. 系統仿真學報. 2006(l8): 3608.

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

IM網絡模型；仿真算法模型；仿真結果分析

程婷婷（1981－），女，山東聊城人，博士研究生，研究方向為系統工程、計算機應用技術。

TN915

A

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

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

2010-11-22

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