一种动态的移动社交网络拓扑模型

田雪颖,刘衍珩,孙 鑫,王亚洲,林佳佳

(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