《基于SNS社交网络的增长模型.pdf》由会员分享，可在线阅读，更多相关《基于SNS社交网络的增长模型.pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第3 3 卷第8 期2 0 1 0 年8 月合肥工业大学学报(自然科学版)J O U R N A LO FH E F E IU N I V E R S I T YO FT E C H N O L O G YV o l-3 3N o 8A u g 2 0 1 0D o i：1 0。3 9 6 9 1 i s s n 1 0 0 3-5 0 6 0 2 0 1 0 0 8 0 3 4 基于S N S 社交网络的增长模型钱大千，张晓东(上海交通大学数学系，上海2 0 0 2 4 0)摘要：随着网络信息技术的发展，社交网络(S N S)成为目前最热门的休闲交友平台。文章研究表明，这类网络具有3 个典型
2、的拓扑特征：幂律度分布、小平均距离和大聚集系数。为了进一步研究此类网络的拓扑结构及其动力学行为，文中基于社交网络的增长机制提出了一种二步式增长模型。运用平均场理论及数值仿真验证发现，该模型同时满足上述3 个拓扑特征，符合社交网络的基本结构特性。关键词：社交网络；幂律分布；度分布；平均距离；聚集系数；增长模型中图分类号：N 9 4 5文献标志码：A文章编号：1 0 0 3 5 0 6 0(2 0 1 0 0 8 1 2 6 4-0 4Ag r o w t hm o d e lf o rs o c i a ln e t w o r k i n gs i t e sQ I A ND a-q i a
3、n，Z H A N GX i a o-d o n g(D e p t o fM a t h e m a t i c s，S h a n g h a iJ i a o t o n gU n i v e r s i t y。S h a n g h a i2 0 0 2 4 0，C h i n a)A b s t r a c t：T h es o c i a ln e t w o r k i n gs i t e s(S N S)h a v eb e c o m eo n eo fm o s tp o p u l a rp l a t f o F I T If o rl e i s u r ea n
4、 df r i e n d s-m a k i n gw i t ht h ed e v e l o p m e n to fn e t w o r ki n f o r m a t i o nt e c h n o l o g y I ti sd i s c o v e r e dt h a tt h i sk i n do fn e t w o r kh a st h r e em a i nt o p o l o g i c a lf e a t u r e s：s m a l la v e r a g ed i s t a n c e，l a r g ec l u s t e r i
5、n gc o e f f i c i e n ta n dp o w e r-l a wd e g r e ed i s t r i b u t i o n,T h i sp a p e rp r e s e n t sat w o-s t a g eg r o w t hm o d e la c c o r d i n gt Ot h ef o r m i n gm e c h a n i s mo fS N Sf o rf u r t h e rs t u d yo fi t st o p o l o g i c a lf e a t u r e sa sw e l la sd y n a
6、 m i c a lb e h a v-i o r I ti ss h o w nb ym e a nf i e l dt h e o r ya n dn u m e r i c a ls i m u l a t i o nt h a tt h i sm o d e lo w n st h ea b o v et h r e em o s ti m p o r t a n tf e a t u r e so fS N S K e yw o r d s：s o c i a ln e t w o r k i n gs i t e s(S N S)；p o w e r-l a wd i s t r
7、i b u t i o n；d e g r e ed i s t r i b u t i o n；a v e r a g ed i s t a n c e；c l u s t e r i n gc o e f f i c i e n t；g r o w t hm o d e lO引言文献 1 基于度优先选取机制提出了著名的B A 模型，该模型反映了现实生活中网络的一个重要特性：度分布满足幂律分布 2 3，又称为无标度性。万维网、输电网和蛋白质网络等现实中的网络都具有这一特性 3 1 。在此之后，文献 8 提出了小世界模型，该模型具有较小的平均距离和较大的聚集系数，即满足通常所说的小世界性。这里
8、，网络G 的聚集系数C 定义如下：c=器。其中，T(G)代表G 中三角形的个数；P。(G)代表G 中长度为2 的道路的条数。本文研究表明，社会网络通常具有较小的平均距离和较大的聚集系数。也就是说，任意2 个人之间都可以通过很少的朋友联系起来，同时2个认识的人很可能会有共同的朋友。现实生活中很多网络同时具有无标度性和小世界性，如科研收稿日期：2 0 1 0 0 3 1 6基金项目：圈家自然科学基会资助项目(1 0 9 7 1 1 3 7；1 0 5 3 1 0 7 0)；9 7 3 国家基础科研基金资助项目(2 0 0 6 C B 3 0 0 4 0 6)和8 6 3 国家高科技发展基金资助项日
9、(2 0 0 6 A A 0 1 2 4 3 6)作者简介：钱大干(1 9 8 5-)，男，安徽蚌埠人，上海交通大学博士生；张晓东(1 9 6 5-)，男，江苏金湖人，博士，上海交通大学教授，博士生导师万方数据第8 期钱大千，等：基于S N S 社交网络的增长模型1 2 6 5合作网、特网和电网等 6 漕_ 1 1|。为了更好地研究现实生活中种类繁多的网络结构和特性，学者们提出了各种各样的模型。文献 1 2 提出了一种可以同时增加和删除节点的增长模型；文献 1 3 提出了一种可以同时增加和删除边的增长模型。这2 种模型反应了现实网络既可以增长又可以缩减的特性，如万维网中网页的添加和删除。为了模
10、拟社会网络，文献 1 4 提出了一种基于等级优先选取机制的增长模型，该模型在构造过程中只需要用到局部的等级顺序就可以生成一个无标度网络。上述模型都反映了现实中网络的一些特性，遗憾的是这些模型的聚集系数都很小。文献 1 5 提出了基于距离优先连接的增长模型，在该模型中，新加入的节点优先连接到距离较近的老节点，因此具有较大的聚集系数，然而该模型的度分布却不服从幂律分布。近年来，伴随着信息技术的高速发展，社交网络被越来越多的人所熟知 16 I。较著名的网络公司如M y s p a c e、F a c e b o o k、开心网和校内网拥有数以亿计的用户。人们已经习惯了在社交网络上交朋友、玩游戏和交换
11、信息。简单地说，这类网络的增长机制可以分为如下2 步：(1)一个新用户让可以通过其朋友们的介绍加入网络。(2)新用户讪会在其朋友们的好友名单中寻找认识的和想要认识的人，并同他们成为朋友。在本文中，基于该增长方式提出了一种同时满足小世界性和无标度性的模型，这和现实中的社交网络具有相同的特性。1 二步增长模型(T S G N)网络规模为咒，参数为m、m z 的二步增长模型T S G N(优，m z)增长规则定义如下：(1)开始时(T o)，从个节点数为m=m，+m z+1 的完全图出发。(2)T=t 时，1 疗一，l，在网络中加入一个新的节点+。，并随机选取m，个旧节点与之连接，将这m，个节点记为
12、N t()(随机连接)。(3)记N 1()的邻居为N 2(f)，从N 2()中随机选取优z 个节点与+。连接(邻域连接)。重复执行规则(2)和(3)，直到网络中节点数达到事先给定的网络规模咒。不难发现，每一次增长添加了1 个节点和7 n l+m z 条边。因此经过t 次增长，网络中共有t+T n 个节点和(m 一1)(仇+2 t)2 条边。2 度分布运用平均场理论可以得到T S G N 模型的度分布P(志)，也就是度为志的节点所占总节点数的比例。令P(k，i，)代表第t 步时第i 个节点度为k的概率，并记(1)式为第t 步时的度分布，即P(k，)一点P(k，i，)(1)m十l：=可以写出如下的
13、主方程：肌一件1)=(鼎+矗鸳杀)P(k 一1，i，)+(1 一再m l 一石而m，、z k。，)、m 十L m l，、mu。7(2)(2)式的初始条件为：P(k，i=1，2，m，t 一0)一&。，P(k，i=t+优，t 1)一文。这里要指出一个巧妙的方法：根据增长规则，在第t 次增长时从N：()中随机选取了m z 个节点与新节点+。连接。不难看出，N z()中节点的度分布为P 7(志，)，而不是P(k，)，即P，(愚，)：尝垫丛，己P(k，)这是因为度较大的节点有更大的概率成为某个节点的邻居。因此，N z()中任意节点度为k 的概率为最(m 一1)(优+2 一2)，这和度优先选取的情况类似。
14、在(2)式两端对i 加和有：(m+t+1)P(忌，t+1)一(m+)P(愚，f)=(m+警誉竺 黼)P c 忌一1，t，一，(优，+石著竺导揣P(k，)+文，一(3)记P(志)一l i m P(k，)为极限度分布，对(3)式两边求极限可得：2 P(k)一(2 m，+等)P(k-1)-(2 m 1+2 兰)P(志)+2 文一1(4)m 一1，化简(4)式可得：9P(m 一1)一2 m l-t-兰r a z 一 2，肌，=丽嘉错等等群镊而P(愚一1)，k m 一1(5)万方数据1 2 6 6合肥工业大学学报(自然科学版)第3 3 卷这里无法通过(5)式得到P(矗)一般的解析表达式，然而可以给出m。
15、m：等于某些特定值时P(矗)的解析表达式，即34 6 m o+P(愚)=P(愚)一，m l=m 2 一m o(6)I I 忌+4 低+t=023 1-6 m o+型一，m1，k+3 砜+I=012m o，m 222 m o(7)6 1 5 m o+P(忌)一1 型一，m 1=2 m o，耽一m ok+1 2 m o+t=0(8)从(6)(8)式中可以看到，当m，m z 取不同数值时(1，1 2，2)，对应模型的度分布分别是参数为5、4、7 的幂律分布。从中可以看出，幂律分布的参数随着比率m。m。的增大而增大。3 数值仿真本文运用平均场理论得到了一些特殊情形下T S G N(m，m z)网络的度
16、分布，现通过数值仿真验证这一结果。此外，还需要研究解聚集系数和平均距离是如何随着模型参数和网络规模的变化而变化的。在双对数坐标轴上给出了规模为50 0 0 的T S G N 网络在参数比率m 1 m 2 取不同数值时的度分布仿真结果，如图1 所示。从图1 可以发现，3 种参数比率下T S G N 网络度分布的仿真结果与(6)(8)式中的结论吻合，均为幂律分布且对应的参数随着比率仇。m。的增加而增加。T S G N 网络在不同网络规模咒、参数m，、m 2条件下的平均距离和聚集系数的仿真结果，见表1 表3 所列。(a)m l m 2=1 时(根据(6)式)(b)7 n 1 m 2=1 2 时(根据
17、(7)式)(c)m 1 m 2=2 时(根据(8)式)圈1 根据(6)(8)式得到的仿真结果裹l 每次增长添加3 条随机连接和3 条邻域连接的仿真结果表1 中，参数取值为m，=3，m 2=3。此时网络具有较大的聚集系数，这与很多现实中的网络有相同的特性 8 。实际上，还可以计算出这种情形下T S G N 网络聚集系数的一个理论下界。不难看出，网络在每一次的增长中都至少增加了3个三角形，同时P z(G)的估计为：3P：(G)咒4 i i l 8+t 扣砜愚+1 2+k(愚一1)2。因此，C，=警器是网络在此参数条件下聚集系数的下界。通过数值计算可得C，=0 0 9 98且与网络规模咒无关，这与表
18、l 中的仿真结果非常相近。此外，还可以看到网络的平均距离大约以I n 以的阶缓慢增长，这一点也和有关万维网的研究结果吻合 3 1。裹2 每次增长添加2 条随机连接和4 条邻域连接的仿真结果表2 中，参数取值为m。=2，优。=4，网络在每万方数据第8 期钱大千，等：基于S N S 社交网络的增长模型1 2 6 7次增长中都至少增加了4 个三角形，因此网络具有比表1 中更大的聚集系数。此时，网络的平均距离也相对较大，这是由于随机连接减少而导致网络连通性减弱。裹3 每次增长添加4 条随机连接和2 条邻域连接的仿真结果表3 中，参数取值为m。=4，m z 一2，网络在每次增长中都至少增加了2 个三角形
19、，因此网络的聚集系数相对较小。此时，网络的平均距离也相对较小，这是由于随机连接增加而导致网络连通性增强。4 结束语本文根据社交网络的增长机制构造了二步式增长网络模型T S G N(m 1，m z)。经验证，此模型满足社交网络的3 个重要特性：幂律度分布、小平均距离及大聚集系数。通过理论推导及数值仿真发现，当模型的规模和总边数一定时，参数比率m。m：对这3 种特性有直接的影响。比率m。m：较大，意味着添加了相对较多的随机连接，这使得幂律分布的参数增大，同时也减小了平均距离和聚集系数。1 3 2 3 参考文献B a r a b 缸iAL。A l b e r tRE m e 堰e n c eo fs
20、 c a l i n gi nr a n d o mn e t w o r k s 口 S c i e n c e，1 9 9 9，2 8 6(5 4 3 9)：5 0 9-5 1 2 B a r a b d s iAL。A l b e r tR，J e o n gH M e a n-f i e l dt h e o r yf o rs c a l e-f r e er a n d o mn e t w o r k s J P h y s i c aA，1 9 9 9，2 7 2(1 2)：1 7 3 1 8 7 A 1 b e r tR。J e o n gH，B a r a b d s iA
21、 LI n t e r n e t：d i a m e t e ro ft h er o r l d w 耐e W e b J N a t u r e，1 9 9 9，4 0 1(6 7 4 9)：1 3 0 1 3 1 4 H u b e r m a nBA，P i r o l lP LT，P i t k o wJE，e ta LS t r o n gr e g u l a r i t i e si nW o r l dW i d eW e bs u d i n g J S c i e n c e，1 9 9 8 2 8 0(5 3 6 0)：9 5 9 7 5 C a l d a r e
22、l l iG，M a r e h c t t iR，P i c t r o n e r oLn m r a e t a lp r o p e r-t i e so fI n t e m e t -J E u r o p h y sL c t t，2 0 0 0，5 2(4)：3 8 6-3 9 1 6 A m a r a lLAN，S c a l aA，B a n h e l e m yM，e ta LC l a s s e so fs m a l b w o r l dn e t w o r k s J P r o cN a t lA c a dS c iU S A，2 0 0 0，9 7(
23、2 1)：1 1 1 4 9 1 1 1 5 2 7 J e o n gH，M a s o nSP，B a r a h a s iAL，e ta LL e t h a l i t ya n dc a n t r a l i t yi np r o t e i nn e t w o r k s J N a t u r e，2 0 0 1，4 1 1(6 8 3 3)：4 1-4 2 8 W a t t sDJ，S t r o g a t zSH C o l l e c t i v ed y n a m i c so fs m a l l w o r l dn e t w o r k s 口 N
24、a t u r e，1 9 9 8，3 9 3(6 6 8 4)：4 4 0-4 4 2 9 N e w m a nMEJ 1 h es t r u c t u r eo fs c i e n t i f i cc o l l a b o r a t i o nn e t w o r k s J P r o cN a t lA c a dS e iU S A，2 0 0 1，9 8(2)：4 0 4-4 0 9 1 0 B a r a l x i s iAL，J e o n gH，N e d aZ，c ta LE v o l u t i o no ft h eS O-c i a ln e t
25、w o r ko fs c i e n t i f i cc o l l a b o r a t i o n s J P h y s i c aA，2 0 0 2，3 1 1(3 4)：5 9 0-6 1 4：1 1 M aYH，L iHJ。Z h a n gxD S t r e n g t hd i s t r i b u t i o no fn o v e ll o c a l-w o r l dn c t w o r k s J P h y s i c aA，2 0 0 9，3 8 8(2 1)：4 6 6 9-4 6 7 7 1 2 M o o r eC，G h o s h a lG，
26、N e w m a nME x a c ts o l u t i o n sf o rm o d e l so fe v o l v i n gn c t w o r k sw i t ha d d i t i o na n dd e l e t i o no fn o d e s 口 P h y sR e vE，2 0 0 6，7 4(3)：0 3 6 1 2 1(8)1 3 D e i j f e nM。L i n d h o l m aMG r o w i n gn e t w o r k sw i t hp r e f e r-e n t i a ld e l e t i o na n
27、 da d d i t i o no fe d g e s J P h y s i e aA，2 0 0 9，3 8 8(1 9)：4 2 9 7-4 3 0 3 1 4 F o r t u n a t oS，F l a m m i n iA，M e n c z e rF S c a l e-f r e en e t w o r kg r o w t hb yr a n k i n g J P h y sR e vL c t t，2 0 0 6，9 6(2 1)：2 1 8 7 0 1(4)1 5 O z i kJ，H u n tBR，O f tEG r o w i I l gn e t w
28、o r k sw i t hg e o-g r a p h i c a la t t a c h m e n tp r e f e r e n c e：e m e r g e n c eo fs m a l lw o r l d s J P h y sR e vE，2 0 0 4，6 9(2)：0 2 6 1 0 8(5)1 6 1 3 0 y dD，E l l i s o nN S o c i a ln e t w o r ks i t e s：d e f i n i t i o n，h i s t o r y，a n ds c h o l a r s h i p J J o u r n a lo fC o m p u t e r-M e d i a t e dC o m-m u n i c a t i o n，2 0 0 7。1 3(1)：2 1 0-2 3 0。(责任编辑张秋娟)万方数据