一種動態的移動社交網絡拓撲模型

田雪穎,劉衍珩,孫 鑫,王亞洲,林佳佳

(1.吉林大學a.計算機科學與技術學院;b.符號計算與知識工程教育部重點實驗室,長春130012; 2.中國海洋大學信息科學與工程學院,山東青島266100)

一種動態的移動社交網絡拓撲模型

田雪穎1a,1b,劉衍珩1a,1b,孫 鑫2,王亞洲1a,林佳佳1a

(1.吉林大學a.計算機科學與技術學院;b.符號計算與知識工程教育部重點實驗室,長春130012; 2.中國海洋大學信息科學與工程學院,山東青島266100)

針對移動社交網絡的動態性、用戶不同重要性和信息交互有向性,基于4種初始網絡提出能準確描述移動社交網絡結構的拓撲模型。采用隨機游走理論和改進的PageRank算法,引入過渡概率使每兩時步之間的網絡拓撲結構相互聯系。通過PageRank算法得到節點的勢,進而求出概率過渡矩陣,利用隨機游走理論由上一時步邊存在概率矩陣和概率過渡矩陣得到當前時步邊存在概率矩陣,每一時步動態地增加一個節點并檢驗是否有離開的節點。仿真結果顯示,該模型在4種初始網絡下得到的網絡拓撲結構,入度、出度、勢分布以及度-勢相關性均具有明顯冪律特性,表明隨機游走理論和改進的PageRank算法能較準確描述移動社交網絡,具有一定的實踐意義。

社交網絡;網絡拓撲;隨機游走;PageRank算法;過渡概率;仿真模型

1 概述

近年來,隨著無線通信技術的飛速發展,無線網絡已經廣泛應用于我國的廣大地區,尤其是在經濟較為發達的城市。Wifi是無線局域網的重要部分,它可以最大限度地滿足個人、家庭和小型辦公系統對于移動網絡連接的需求。手機、電腦、iPad無疑成了人們在移動網絡中進行信息交互的主要工具。人們上班、購物、出游等社交行為賦予了移動自組網絡動態性的特征,使其具有社會流動性。因此,掌握移動社交網絡的行為特征,分析移動社交網絡的動態性和規律性,具有重要的理論價值和現實意義。

由于移動網絡具有規模大、增長快的特點,因此很難把它作為實驗對象來進行研究和分析[1]。對移動網絡所引發的一系列網絡問題的研究往往只能基于拓撲模型進行。網絡拓撲模型是對真實網絡拓撲結構的模擬,利用拓撲模型的方式研究移動網絡中用戶行為的方法由來已久。文獻[2]根據現實網絡中用戶行為的隨機性提出了經典的Waxman隨機網絡拓撲模型;文獻[3]基于邊概率隨節點距離增加而呈指數減少的思想提出了另外2種隨機網絡拓撲模型:指數模型和位置模型;文獻[4]提出了“小世界網絡”模型,即WS模型,該模型的主要貢獻是提出了介于規則網絡和隨機網絡之間的小世界網絡,并能通過重連概率p進行調節,從而可使網絡結構在規則網絡和隨機網絡之間轉化;文獻[5]在研究域間系統時發現節點度的冪律法則,無標度網絡由此成為了研究者關注的主要對象;文獻[6]通過向一個簡單的模型中動態地添加新節點和新連接模擬Internet網絡發展過程來生成符合冪法則的模型,稱之為BA模型,BA模型解釋了域間系統的節點度符合冪法則分布的現象。

以上模型大多未考慮現實網絡中信息交互的有向性、節點的動態加入和離開,以及節點的重要程度和節點間的聯系強度,存在一定的缺陷。同時,移動網絡的結構變化很快,限制了對移動網絡拓撲結構的確定。雖然可以知道其大致特征,但無法構造詳盡拓撲圖。因此,本文在隨機游走理論的基礎上,結合PageRank算法和移動網絡所具有的現實特點對移動網絡拓撲結構進行模型抽象,從而更真實地反映用戶在移動社交網絡中的行為規律。

2 隨機游走理論和PageRank算法

2.1 隨機游走理論

隨機游走[7]是一種數學統計模型,它由一連串的軌跡所組成,其中每一次都是隨機的。在給定當前知識或信息的情況下,只有當前的狀態用來預測將來,過去(即當前以前的歷史狀態)對于預測將來(即當前以后的未來狀態)是無關的。

在隨機游走理論中,單個的隨機事件不可預測,但隨機大量的群體行為卻是精確可知的。隨機性造成了低尺度下的差異性,但在高尺度下又表現為相似性。利用隨機游走理論的這一特性,可以較準確地預測移動社交網絡中用戶行為在當前狀態下的下一時刻狀態。

2.2 PageRank算法

PageRank算法[8-9]可以看作是隨機游走模型的一個實例,基本思想主要來自傳統文獻計量學中的文獻引文分析,即一篇文獻的質量和重要性可以通過其他文獻對其引用的數量和引文質量來衡量。也就是說,一篇文獻被其他文獻引用越多,并且引用它的文獻的質量越高,則該文獻本身就很重要。

PageRank算法的簡單描述如下:

其中,每個網頁的pr值等于所有指向該網頁的pr值貢獻度之和;ε是阻尼常數因子,一般取0.85;N為網頁總數;IN(i)為所有指向i網頁的集合;OUT(r)為網頁r出鏈的集合。每個網頁的初始值為1/N,每一輪為每個網頁計算出pr值以后,下一輪用上一輪的值。

3 拓撲模型

3.1 模型簡介

為使本文構建的模型更加完善,貼近現實網絡,在現實移動社交網絡具有有向性和節點不同的重要程度特點的基礎上重點突出網絡的動態性特征。移動社交網絡拓撲結構在每一時步都可能發生變化,將每兩時步之間的拓撲結構用一個概率過渡矩陣聯系起來,當前時步的邊存在概率矩陣由上一時步邊存在概率矩陣和過渡矩陣得到,同時每一時步增加一個節點并驗證是否有離開的節點直至網絡節點數為1 000。為此,本文構造了4種初始網絡觀察對網絡拓撲結構生長演化產生的影響。在所構建的拓撲模型中,每個節點代表移動網絡中的一個用戶,節點間的有向邊表示這兩個節點所代表的用戶之間存在信息傳遞。節點間有向邊的邊存在概率越大,表明2個節點間信息傳遞的可能性就越大。模型中的節點可能是信息的接收者,也可能是信息的傳遞者,或者兼具這2種角色。

3.2 模型構建過程

模型構建過程如下:

(1)初始化

假設初始網絡節點數為n0,本文將初始網絡分為4種情況[10]:隨機網絡,環形網絡,星形網絡,全耦合網絡。

根據初始網絡產生邊存在矩陣G0如下:

(2)模型生長演化

Step 1 求概率過渡矩陣。PageRank公式中的阻尼因子ε來于隨機沖浪模型,然而在節點的拓撲連接中并不適宜,因此,改進的PageRank算法[11]如式(3)所示,使其更符合于求各節點的勢:

將任意2個節點i,j的過渡概率表示如下:

得到概率過渡矩陣:

Step 2 求下一時步邊存在概率矩陣。因為隨機游走理論具有當前狀態的變化僅與它前一個時刻的狀態有關,而與前面其他時刻的狀態無關這一特性,所以可以用上一時步的邊存在概率矩陣和概率過渡矩陣得到邊存在概率矩陣:

Step 3 求增加一個節點后邊存在概率矩陣。每一時步增加一個新的節點,直到網絡規模為1 000。加入的新節點的s值、加入的新節點與任一舊節點之間進行互相連接的概率均為 1/Nt,在式(6)的基礎上得到當前狀態邊存在概率矩陣:

Step 4 得到當前邊存在矩陣如下:

Step 5 刪除節點。由于現實移動網絡中人類的移動具有隨機性,在不斷有新節點加入的同時也會有舊節點隨機離開,因此在求得的網絡拓撲結構中,將沒有與任何節點相連同時也沒有任何節點與其相連的節點看作是已離開的節點,并將其刪除,即在網絡拓撲結構中滿足下列條件的節點刪除:

Step 6 返回Step 1。

3.3 模型分析

提出的模型借鑒PageRank算法,將拓撲模型中勢小于α的節點稱為普通節點,勢大于α的節點稱為關鍵節點[12]。當一個節點連接到另一節點時,它會向這個被相連的節點進行一次“投票”,節點得到的“票數”越多,其越重要,同時它投出的票也越重要。換句話說,一個與很多節點相連的節點被視為重要節點,一個被很多重要節點連接的節點是一個核心節點。聯系實際移動社交網絡可以很容易想到,核心節點往往是這個移動社交網絡中的領導人物,核心節點之間的聯系狀態在下一時步發生變化的可能性很小,而普通節點之間的聯系狀態在下一時步很容易發生變化,核心節點與普通節點之間的聯系狀態在下一時步發生變化的概率介于前2種情況之間。即核心節點間連接強度最強,普通節點間連接強度最弱。另一方面,同時連接兩個節點的節點個數越多,表明這兩個節點之間的關系越緊密。這些節點相當于真實網絡中的中間人,可以把與之有聯系的一個用戶介紹給與之有聯系的另一個用戶使之產生信息傳遞。由于在一個隨機過程中,網絡拓撲結構的變化僅與它的前一個狀態有關,而與它前面時刻的狀態無關,因此在當前狀態同時連接2個節點的節點數越多,在下一時刻這2個節點間失去聯系的可能性越小。基于以上觀點,模型在Step 1中利用改進的PageRank算法求得當前狀態到下一狀態的過渡概率,較真實地模擬了移動社交網絡環境的拓撲變化。

由模型構建過程可以看出,本文在構建模型時綜合考慮了節點的動態性、信息傳遞的有向性和現實生活中普遍存在的朋友介紹現象對移動社交網絡拓撲結構的影響,并且通過引入外部參數d來調節節點的勢對拓撲結構的影響。由式(3)可以看出,通過調節參數d的值,直接影響節點勢的大小。節點勢的大小直接影響2個節點間過渡概率的大小。過渡概率的改變又將改變下一時步的邊存在概率,從而影響下一時步的邊存在矩陣。邊存在矩陣的變化使整個網絡中節點的連接狀態發生改變,即節點的入度和出度發生變化,移動拓撲結構的生長演變隨之改變。

4 仿真實驗

為了驗證所構建的網絡模型的有效性,本文分析了所生成網絡的入度、出度、勢和度-勢相關性等拓撲參數。在仿真實驗中,設定初始網絡規模n0= 5,最后生成的網絡規模為N=1 000。仿真實驗得到的圖形均為無量綱的比率圖。

實驗中,隨機網絡的初始邊存在概率矩陣是一個隨機生成的邊存在概率在0～1之間的矩陣;因為環形、星形、全耦合網絡的初始邊存在矩陣是已知的,所以實驗假設與存在的邊相對應的邊存在概率是通過隨機數產生法得到的0.5～1之間的隨機數,其他節點之間的邊存在概率是0～0.5之間的隨機數,當然,與自身相連的邊的邊存在概率為0。

4.1 節點度分布

仿真實驗對比了4種初始網絡對網絡拓撲結構入度、出度分布的影響,以及控制參數d對節點入度、出度分布的影響。從圖1和圖2中可以看出,對應于不同的d值,同一初始網絡的節點入度、出度分布具有較大差異,但均符合冪律分布[13];在相同的d值下,不同初始網絡的節點入度、出度分布也不相同。然而,對同一初始網絡而言,隨著d值的變化,隨機初始網絡的度分布變化程度最大,環形初始網絡的變化程度最小;對不同的初始網絡而言,d=2.0時對網絡拓撲結構的生長演化影響最小,d=3.0時對網絡拓撲結構生長演化影響最大。由此可知,不同的初始網絡及控制參數d對網絡拓撲結構的生長有一定的影響。

通過對比每個初始網絡的節點入度圖和出度圖可以發現,在不同的d值影響下,拓撲網絡節點入度和出度的變化幾乎是同步的,入度大出度大,入度小出度小。隨機初始網絡、環形初始網絡和全耦合初始網絡中均是d=2.5時,節點的入度和出度值最大,拓撲網絡間的聯系最緊密;對于星形初始網絡, d=2.5和d=3.0時,節點的入度、出度值相差不明顯。由此可以看出,不同的初始網絡在相同d值下的聯系緊密程度不同。

圖1 4種初始網絡下的節點入度分布情況

圖2 4種初始網絡下的節點出度分布情況

4.2 節點勢分布

由圖3可以看出,對同一初始網絡,控制參數d對網絡節點的勢也具有較明顯影響。具體而言, d值對全耦合初始網絡節點勢的影響最明顯,對環形和星形初始網絡的影響不是很大。隨機初始網絡和全耦合初始網絡中,d=3.0時節點的勢最大,但是全耦合初始網絡中節點勢的值波動較大;環形和星形初始網絡d分別為2.5和2.0時節點的勢最大。

圖3 4種初始網絡下的節點勢分布情況

4.3 度-勢相關性

本文以d=2.5為例,對4種初始網絡度-勢相關性進行分析。文獻[14]在研究了大量實際網絡數據集的基礎上,發現加權網絡中節點的度值與勢值是存在冪律關系的,若用s表示節點的勢,k表示節點的度,則節點度值與勢值的冪律相關性可以表示為:

通過仿真實驗得到4種初始網絡的有關節點的入度值、出度值與勢值,并對其進行線性擬合后發現,節點入度值、出度值與勢值之間存在冪律關系,如圖4所示。本文選取具有代表性的星形和全耦合初始網絡,圖4(a)、圖4(b)分別是星形初始網絡節點入度、出度與勢的相關性,其斜率分別為0.75和0.78;圖4(c)、圖4(d)分別是全耦合初始網絡節點入度、出度與勢的相關性,其斜率分別為0.90和0.90。另外,隨機初始網絡節點入度、出度值與勢值擬合后得到的直線斜率分別為0.72和0.73;環形初始網絡節點入度、出度值與勢值擬合后得到的直線斜率分別為0.76和0.74。

圖4 星形和全耦合網絡的度-勢相關性

5 結束語

本文結合現實生活中信息傳播所遵循的規律,提出通過加權有向拓撲模型模擬社會交往的動態性。使用PageRank公式求節點的勢將節點分為關鍵節點和普通節點,引入概率過渡矩陣,利用隨機游走理論中的當前狀態只與其上一時刻的狀態有關而與其他時刻狀態無關的特性,得到社交網絡在每時步的生長演化拓撲結構直至網絡規模N=1 000。仿真結果表明,在不同的初始網絡條件下,該模型所生成的網絡拓撲結構的入度、出度、勢分布以及度-勢相關性有較明顯差異,但又具有一定的相似性。下一步將對網絡拓撲的聚類系數、核數和基尼系數等進行仿真研究,檢驗模型是否能夠體現移動社交網絡的聚集特性、層次性和異質性等特點。

[1] 劉衍珩,李飛鵬,孫 鑫,等.基于信息傳播的社交網絡拓撲模型[J].通信學報,2013,34(4):5-13.

[2] Waxman B M.Routing of Multiple Connections[J]. IEEE Journal on Selected Areas in Communication, 1998,6(9):1617-1622.

[3] Zegura E W,Calvert K L,Bhattacharjee S.How to Model an Internetwork[C]//Proceedings of the 15th Annual Joint Conference of the IEEE Computer Societies.San Fransisco,USA:IEEE Press,1996:594-602.

[4] Watts D J,Strogatz S H.Collective Dynamicsof‘Small-world' Networks[J].Nature,1998,393 (6684):440-442.

[5] Faloutsos M,Faloutsos P,Faloutsos C.On Power-law Relationships of the Internet Topology[C]//Proceedings of SIGCOMM'99.[S.l.]:ACM Press,1999:251-262.

[6] Barabasi A,Albert R.Emergence of Scaling in Random Networks[J].Science,1999,286(5439):509-512.

[7] 徐曉華.圖上的隨機游走學習[D].南京:南京航空航天大學,2008.

[8] 趙 國,宋建成.Google搜索引擎的數學模型及其應用[J].西南民族大學學報,2010,36(3):160-166.

[9] 黃德才,戚華春.PageRank算法研究[J].計算機工程, 2006,32(4):151-152,168.

[10] 楊 莉.網絡拓撲模型的研究[J].湖北第二師范學院學報,2008,25(8):5-9.

[11] 王德廣,周志剛,梁 旭.PageRank算法的分析及改進[J].計算機工程,2010,36(22):297-299.

[12] 劉衍珩,孫 鑫,王 健,等.基于用戶行為和網絡拓撲的 Email蠕蟲傳播[J].吉林大學學報,2010,40 (6):196-203.

[13] 周 苗,楊家海,劉洪波.Internet網絡拓撲建模[J].軟件學報,2009,20(1):113-127.

[14] Barrat A,Barthelemy M,Pastor-Satorras R.The Architecture ofComplexWeighted Networks[J]. Proceedings of the National Academy of Sciences of the United States of America,2004,101(11):3747-3752.

編輯 金胡考

A Dynamic Mobile Social Network Topology Model

TIAN Xue-ying1a,1b,LIU Yan-heng1a,1b,SUN Xin2,WANG Ya-zhou1a,LIN Jia-jia1a
(1a.College of Computer Science and Technology;1b.Key Laboratory of Symbolic Computation and Knowledge Engineering,Ministry of Education,Jilin University,Changchun 130012,China;
2.College of Information Science and Engineering,Ocean University of China,Qingdao 266100,China)

A topological model that can describe the mobile social network accurately is proposed based on four initial networks considering the dynamic of social network,the different importance of users and the direction of information interaction.Random walking theory and improved PageRank algorithm are adopted,and transition probability is introduced to associate the network topological structure between two time-steps.Firstly,PageRank algorithm is used to obtain the strength of the nodes in order to get the probability transition matrix.Then random walking theory is used to get the current time-step edge existence probability matrix based on the last time-step edge existence probability matrix and the probability transition matrix.During each time-step,a node is added and it is checked if there is any departure node.Finally,simulation model is used to simulate the four initial networks in in-degree,out-degree,strength distribution and the correlation between degree and strength.The results indicate that the four initial networks'in-degree,out-degree,strength distribution and the correlation between degree and strength show obvious power-law character.It shows that the random walking theory and improved PageRank algorithm can describe the mobile social network better,which is of certain practical significance.

socialnetwork;network topology;random walking;PageRank algorithm;transition probability; simulation model

1000-3428(2014)09-0124-06

A

TP393

10.3969/j.issn.1000-3428.2014.09.025

國家自然科學基金資助項目(60973136,61073164);吉林省科技發展計劃青年科研基金資助項目(201101033);吉林大學國家級創新基金資助項目(2012A53143)。

田雪穎(1990-),女,碩士研究生,主研方向:網絡拓撲建模,網絡安全;劉衍珩,教授、博士、博士生導師;孫 鑫,博士;王亞洲,學士;林佳佳,碩士研究生。

2013-05-17

2013-08-26E-mail:txy_0902@126.com