社会网络环境下用户关系网络结构的仿真描述，本文主要内容关键词为：网络论文,结构论文,关系论文,环境论文,社会论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
1 引言
社会网络环境下的用户关系网络是建立在用户交互基础上的，其复杂特征的研究对开发更加健壮和高效的搜索、推荐系统，以及构建复杂的信息服务系统和帮助用户更快捷地获取信息具有重要价值[1]。文献[2]通过数据调研和分析在一定程度上揭示了社会网络环境下的用户关系结构特征与演化趋势和规律，包括强弱关系并存、幂律等级分布、有序化、再中心化等[2]。但从总体上看，即使是在单个的社会化网络服务中也存在着大规模的用户数量，用户关系数量则更为庞大，所形成的结构更为复杂。而限于调查范围和能力的局限，无法揭示大规模用户的关系结构和特征，因此，为了进一步揭示和验证用户关系的结构特征和演化规律，本文在阐述社会化网络服务中用户关系结构和指数扩散增长原理的前提下，构建仿真模型，进行仿真实验，探索其演化规律。
社会网络环境下用户关系网络的形成和发展受到需求、认同、情感以及社会资本等多方面因素的影响，演化出了复杂的拓扑结构，表现出无尺度特性以及小世界效应（用户关系数量成指数增长时），同时具有复杂系统的独有特征，如开放性、非平衡性、自组织性、动态性等。众多学者将复杂网络理论及其模型引入关系网络的研究中，利用规则网络、随机网络、小世界网络、无尺度网络等研究关系网络的演化问题。在社会网络的研究中，影响较大的则为艾伯特·巴拉巴西（Albert Barabasi）和瑞卡·艾伯特（Reka Albert）基于优先选择的BA模型[3]、邓肯·华兹（Duncan J.Watts）和斯蒂文·斯特罗加茨（Steven Strogatz）基于较小平均距离和较大聚集系数的小世界模型（或WS模型）[4]。在此之后，研究者提出了较多的改进模型，以更好地模拟社会关系网络的演化，如基于距离优先连接的增长模型[5]、基于等级优先选取的增长模型[6]，但都未能充分考虑到实际关系网络的特征。因此，本文根据典型的社会化网络服务（如Facebook、MySpace、人人网）中用户关系的建立和增长规律，构建仿真模型进行仿真。
社会化网络服务中的用户关系建立和增长方式都随着时间的推移而改变，即关系网络中不断有用户（节点）加入，用户关系随之建立，其拓扑结构也处于动态演化中。现实中，新用户进入社交网站时，新用户往往是从社交网站给新用户呈现的潜在好友列表以及好友的好友列表（如人人网）中选择添加为自己的好友，建立好友关系。因此，本文基于上述思想提出了用户关系网络构建的机理：
①用户
主要是通过其朋友的介绍和推荐加入网络。
②新用户建立关系的主要方式是在朋友的好友中选择好友建立关系，加入朋友圈子。
用户关系网络的形成是建立在新用户节点的不断加入并相互关联的基础上的，通过信息机制实现关系的建立、增强或消亡。本文将仿真演化原则[7]定义为：
①增长特性。即随着用户数量的增多，用户关系则成倍增长，其增长速度远远超过用户数量的增长，甚至出现指数增长趋势。
②优先情结。新的用户更倾向于与影响力大、关系数多或权威级用户（本文使用度表示）相连，进而出现马太效应（Matthew effect）或富者愈富（rich get richer）现象[8]。
基于此，本文将从用户关系网络的拓扑结构和指数增长两个方面构建相应的仿真模型，进行仿真实验，以揭示其结构特征和增长规律。
2 用户关系网络的拓扑结构仿真
网络的拓扑结构对网络中节点和关系的演化过程具有重要的影响[9]，其表征参数主要为度分布（Degree distribution）、平均路径长度（Average path length）和聚集系数（Clustering coefficient）。因此，本文将从度分布和用户聚集两个方面对用户关系网络的拓扑结构进行仿真阐述。
在此仿真实验中，将关系网络中用户加入和关系建立规则设定如下：
①参数设定。关系网络的最终规模阈值设定为n；
为新用户进入时随机选取建立关系的旧用户数，在t时刻个用户所组成的用户集记为
；
为用户集
的邻居集，从中的随机选取
个用户建立关系。
②从T=0开始，关系网络中的用户数为m=++1。
③T=t时刻，1≤t≤n-m，新用户
进入网络，随机选取个用户与之建立关系。
④从中随机选取个用户与新用户建立关系。
⑤重复执行③和④，直到网络中的用户数达到阈值n。
在关系网络不断增长的过程中，每一次增长1个用户的同时，就会增加+条关系，经过t次增长，共增加t+m个用户和
条边。
2.1 度分布仿真
复杂网络中，节点的度数分布（特别是度数概率密度函数）通常是揭示复杂网络拓扑结构特征的重要依据，能够揭示如幂律分布、小世界效应等特征。
在本文的仿真实验中，网络中的用户定义为节点，用户关系定义为边，将用户的关系数表示为度。度分布P（k）则为度数为k的节点占总节点的比值，表示任何节点与其他k个节点相连的概率。在t时刻，第i个节点度数为k的概率记为P（k，i，t），则在整个网络中的度分布为：
但是，在实际关系网络中，用户的关系建立选择具有优先情结，因此在邻居集中度数较大的用户被选中的概率较大，其度数分布为：
据此可推导出主方程为：
对公式3两边i加和后求极限，可得：
本文在Matlab7.0平台上进行了最大用户数规模时的仿真实验。当、取值不同时，度数分布概率P（k）对应的幂指数不同（如表1所示），三者的拟合曲线如图1所示。大部分社会关系网络度分布的幂指数范围约为（1，4）[10]，此次度分布的仿真结果与其他互联网领域的仿真结果比较吻合，且显示出了其独有分布特征。
2.2 用户聚集仿真
在好友网络中，好友的好友之间在很大概率上也是好友，即好友会聚集在一起，称之为网络的聚集性，描述网络聚集程度的参数为聚集系数。两个用户之间的距离定义为连接这两个用户的最少关系数，称之为路径长度，而任意两个用户之间的距离平均值则为此关系网络的平均路径长度。仿真网络在不同用户数n、随机选择好友数和邻居集好友数情况下的平均路径长度和聚集系数如表2、表3、表4和图2所示。
综合考虑聚集系数和平均路径长度，在和不同取值的情况下，均有较大的聚集系数和较短的路径长度，此关系网络结构具有较为明显的小世界效应。特别指出的是，在=3，=3时，关系网络具有较大的聚集系数和较短的平均路径长度；在网络节点的平均度固定时，如果平均路径长度随着网络节点总数的增加以对数或者慢于对数的速度增长，则网络具有较为明显的小世界效应[11]；此仿真网络的平均路径长度大约以常数为2.3677的lnn缓慢增长，且较接近实际的关系网络构建情况[12]。
在=2，=4时，其聚集系数和平均距离均较大，与邻居集的连接数增加，加大了好友间的聚集程度，但随机连接的减少导致了网络连通性的降低。在=4，=2时，则与上述相反，聚集系数和平均距离均较小，随机连接的增多导致其连通性较强，而好友关系建立的减少，整体聚集系数也较小。
上述度分布仿真、聚集系数和平均路径长度的仿真，在不同的网络规模下均表现了幂律分布和较为明显的小世界效应。一般情况下，新用户进入关系网络时的选择数也在其左右[13]，因此，随机连接为3、随机连接邻居集为3时的仿真结果较为接近实际情况。
3 用户关系增长的指数规律仿真
上述更多的是对关系网络结构的静态仿真，得到了其静态网络规模下的结构特性。而关系网络作为一个由大量用户相互关联构成的复杂网络，随着用户的增加，其关系数量或基于关系的社会化行为（如分享）数量成指数增长，如Facebook基于用户关系的分享次数成指数增长态势[14]、国内社会化分享工具特别是微博类增长趋势迅猛[15]等。指数增长在一定时间范围内已经成为社会化网络服务的主要特征之一，本节将从用户关系指数增长仿真的角度[16]探索其演化规律，提出用户关系的指数增长模型（Exponential Growing for Users' Relationships，EGFUR），用来描述用户关系呈指数增长的演化规律。
3.1 用户关系的指数增长仿真模型
用户数量和关系数量增长的数学模型如下：
N（t）、R（t）表示t时刻用户（网络节点）数和关系（边）数，
为网络中新用户所包含的初始用户关系数，β表示新用户加入网络的速率，α表示新用户关系加入网络的速率。
当α≠β时，有上述方程可得：
其中，
为关系网络中的初始用户数，A和B为关系网络初始状态和和参数α和β的简单函数。
对公式8求导可得：
将公式7、公式8带入公式6可得：
将公式9和公式10等价对比可得：
因此，将公式13带入公式7和公式8可得出用户数量和关系数量的指数增长公式：
3.2 用户关系指数增长仿真
用户关系的指数增长，使得EGFUR模型的拓扑结构不断演化并呈现出复杂的结构特征。关系聚集的群体具有较高的知名度，新用户更倾向于加入高聚集的群体，即上述的优先选择规则。本文假定新用户与旧用户建立关系的概率
正比于旧用户当前的关系数量（ω（t）），或旧用户被新用户选中的概率正比于其关系数量，即为
（R（t）为t时刻的用户关系数
。
将EGFUR模型的初始参数设定为=10，α=0.04、β=0.03，以此来近似用户的增长速率，在N=10728的情况下仿真发现，其度分布服从幂律分布（图3），也验证了用户优先选择情结对其关系的幂律分布起主要作用。
如果一个网络在局部表现出较大的聚集系数，而在全局表现出比较小的平均路径长度的话，则此网络将具有小世界效应。在本文对EGFUR关系网络的演化仿真中，当用户关系增长指数大于用户的增长指数时，EGFUR表现出了小世界效应（如图4和图5），聚集系数为0.1至0.2之间，平均路径长度大约为1到6之间。
4 总结
结合用户在社交网站上的实际需求和行为意图，本文从静态和动态两个角度对大规模条件下用户关系的拓扑结构和指数增长规律进行了仿真实验。仿真结果验证了调研所归纳的关系结构特征，并指出了在用户关系成指数增长过程中所出现的演化规律：当用户关系数增长速度大于用户数量增长速度时，小世界现象将会出现。
社会化网络服务在帮助用户实现个人社会关系管理的同时，带动了其信息的交流和知识共享，以一种聚合效应，将人、社会、信息存在的无数和无序排列组合进行优化聚合[17]，加快了信息的产生和流动，改变了信息传播的模式[18]。本文对用户关系网络结构特征和演化规律的揭示，将有助于发现社会化网络服务中基于用户关系的信息机制，如产生机制、传播机制、创新机制等，在改善用户体验、提升信息服务质量（如推荐的效率和准确度）等方面具有重要意义。