基于无标度网络结构的SNS识别方案

◆张 宇张 诚

（1.北京师范大学珠海分校 广东 519087；2.中国移动国际有限公司 香港 999077）

基于无标度网络结构的SNS识别方案

◆张 宇1张 诚2

（1.北京师范大学珠海分校 广东 519087；2.中国移动国际有限公司 香港 999077）

本文根据社交网络中存在大量无标度网络结构的特性，在分析聚合算法和剖分算法的基础上，提出基于无标度网络结构的社区识别算法，并利用微博数据作为方案分析和阐述的实证数据。首先根据中心节点划分网络，把剩余点连接到归属中心节点上，最终将社交网络划分成若干联系紧密的好友圈子。分析结果对移动互联网新产品的开发、潜在客户的挖掘和服务有参考意义。

SNS识别；无标度网络；中心节点

0 引言

随着4G网络的全面覆盖和智能手机全面普及，移动互联网得到飞速的发展，社交形式的网站和手机应用不断涌现，如国外的社交平台Facebook、Wikipedia、Twitter等，国内的微信、微博、QQ、陌陌等社交应用和社交网站用户破亿，其他照片分享、音乐分享、视频分享、交友等社交应用更是层出不穷，网络愈发呈现出社会性特征，即社交网络（Social Networking Services，简称SNS）。社交网络是一个虚拟社区，如何对这个社区进行有效识别并加以利用，对移动互联网产品的开发、营销与推广以及潜在客户的挖掘和服务有参考意义。

1 现有SNS识别方案分析

在社交网络领域的社区识别中，最具代表性的算法是聚集算法和剖分算法。聚集算法是从某个点开始向外扩展，将耦合性大的点逐步加入到当前集合，直至不再有满足条件的点，将这一部分的点划分为同一个社区，然后再重新选取尚未划分的点重复之前的步骤；剖分算法从整个网络开始，寻找连接性最小的边进行删除，重复此步骤可将该网络逐步细分，直至达到满意的剖分效果，算法的关键在于如何对整个网络中边的关联度进行适当的衡量，其方法有最短路径算法、随机漫步模型、电路模型等。

本文根据社交网络中存在大量无标度网络结构的特性，在聚合算法和剖分算法的基础上提出基于无标度网络结构的社区识别算法，该算法认为这些网络结构的中心也是网络中各个社区的中心，通过对这些具有“代表性”的中心节点的确定，可以简单的将网络分割成以这些节点为中心的社区，然后将其余的“链点”逐次聚合到各个社区中。

2 无标度网络结构SNS识别方案阐述

根据中心节点来划分网络，再把剩余的点连接到其归属的中心节点上，最终将社交网络划分成若干联系紧密的好友圈子。本文将利用微博数据作为方案分析的实证数据。

2.1 社交网络数据

本文的研究对象是社交网络中社区圈子划分及用户在圈中的地位和影响力，所以需要获得用户的好友连接数据，以此来建立连接的人际网络图。利用移动网络信令分析中的微博好友连接作为测试数据。

2.2 中心节点的识别

中心节点是指处于整个网络或社区中心位置的节点，本文定义中心节点为网络中好友数量较多的节点。由于无标度网络结构的中心的节点度数都比较大，根据我们对基础数据统计，大约有5%的节点其度数明显比其余节点多，因此实际计算时，选取度数最大前5%的节点作为中心节点。

2.3 中心节点的合并

NAM模型模拟的安阳站日径流过程的精度比较结果详见表1。NAM模型模拟的日径流过程，在率定期内，确定性系数大于0.9，等级属于甲等的有2年;确定性系数大于等于0.7小于等于0.9，等级属于乙等的有5年。在验证期内，确定性系数都在大于等于0.7小于等于0.9的范围内，等级都属于乙等。径流深相对误差，在率定期内，5年都合格，合格率为100%；验证期内，3年都合格，合格率为100%。

由于选取的多个中心节点可能属于同一个社区，必须对中心节点间的关系进行判定，将属于同一个社区的节点进行合并。

首先，定义两个中心节点之间的相关度为：

其中N(u)、N(v)分别表示节点u、v的好友数量，num(t)指节点u和v共同好友节点的数量，即ruv衡量的是共同节点占总节点的比重。

将ruv大于某一给定阈值α的两个中心节点认为是属于同一个社区，即如果两个中心节点的相关度大于α，则将其合并成同一个社区，具体合并算法如下：

（1）假设u1、u2……uk为选定的k个中心节点，依次计算每两个中心节点之间的相关度ruv，选取其中的最大值。

（2）若相关度ruv<α，则合并过程完成，否则将这两个节点视为同一个社区，并进行合并组成新节点。

（3）重复上边步骤，直至没有节点合并为止。

需要注意的问题是当两个节点合并时，应该同时将他们的边也合并在一起。根据α的大小还控制社区圈子规模，α值越高，则要求社区的藕合程度越高，社区数量较多，规模相对较小。

2.4 链点的聚合

中心成员完成合并后，形成若干以中心节点为成员的社区，下一步将非中心节点，即链点逐次聚合到现有的社区。聚合思路是计算该节点与各个社区的最短距离，将其归并到距离最近的社区。在聚合过程中，由于存在多个社区，必须进行多源的最短路径计算，每次聚合之后都重新计算的代价较大，所以我们的算法是聚合之后即时更新。具体计算过程如下：

（1）完成中心节点合并后，计算各社区到所有其他节点的路径，选取最短路径的社区。其中，属于同一社区的节点视为单独的点，即他们之间的距离为0。

（2）将节点u聚合到最近的社区T后，将所有非社区节点标记为“未访问”状态，更新节点u到社区T的距离为0，然后将节点u放到更新队列中，状态标记为“己访问”。

（3）从更新队列中选取最前面的节点v，标记状态为“已访问”，逐次访问节点v的所有状态为“未访问”的邻接节点，对最短距离进行更新，将更新过的节点放入更新队列中。

重复步骤（3），直至更新队列为空。

为提高算法中链点聚合的准确性，我们优先考虑连接数多的节点。

经过以上几步计算后，社交网络就被划分成联系紧密的好友圈子。

2.5 系统输出

根据计算结果，为方便其他系统调用，系统输出数据结构为：