- 1 -
利用滚雪球采样检测新浪微博核心网络
翟柄宇，张闯**
（北京邮电大学信息与通信工程学院）
5 摘要：在像 Twitter 和微博这样的微博系统中，用户由定向的和不对称的关系联系在一起。
一些所谓的“明星”拥有很多粉丝并且在网络中占据主导的位置。这些用户组成了网络的核
心用户，他们控制了复杂系统中的信息流动。在实际中，由于很多技术的和隐私方面的限制，
要想收集到这些“明星”的信息并获得有代表性的网络采样来研究大型有向网络的典型结构
是一项非常艰巨的挑战。这篇论文研究了滚雪球采样在发现有向网络中核心节点的有效性。10
我们构建了一个拥有 3500 万新浪微博用户的网络，并在选择采样种子，采样 ，采样比方面
采用多种策略实施滚雪球采样。
关键词：社交网络；微博；网络核心；滚雪球采样
中图分类号：TP391
15
Detecting the core of XinLang Weibo with Snowball
Sampling
zhaibingyu
1
, zhangchuang
2
(1. Beijing University of Posts and Telecommunications School of Information and
Communication Engineering; 20
2. Beijing University of Posts and Telecommunications School)
Abstract: In microblogging systems such as Twitter and Weibo, users are connected by directed
and asymmetric relations. Some users, the so-called superstars, have many followers and possess
dominant positions in the networks. These users form the core of the networks, which controls the
information flow in the complex systems. In practice, with many technical and privacy restrictions, 25
collecting superstars’ information and acquiring representative network samples is a big challenge
for studying the critical structures of a large directed paper studies the effectiveness
of snowball sampling in recovering the core nodes in directed networks. We constructed a network
of 35 million users of the Sina Weiboand performed snowball sampling with various strategies of
choosing sampling seeds, waves, and branches. 30
Key words: SNS;Weibo;Core of Weibo;Snowball Sampling
0 引言
在线社交服务已经越来越受到欢迎，他们都提供了一个信息分享，信息传播，信息推广
的平台。用户线上的影响力是由他们在网络上的关系和交互来决定的，而线上的影响力又影35
响了他们的社会影响力：分为明星用户和普通用户两种[1][2][3]。拥有大影响力的用户和他们
的粉丝网络一起构成了有效节点的度中心性度量下的典型结构。这些结构就是网路的核心，
这在在线社交网路中是非常普遍的[4][5]。
为了计算和可视化的方便，这篇文章提供了对一个给定图采样的一些初步想法。为了保
留网络属性，他们集中在随机节点，随机边采样和基于连接的采样[6]。这些文章的其他部分40
检测了一些爬取方法，包括 Snowball Sampling，Forest Fire，RW 以及它的改进算法[7]。这
- 2 -
些方法分析了多种方法可能的偏差，并且试图在一些具体情况下纠正他们。由于滚雪球采样
在高度节点上有偏差，所以像 RWRW 和 MHRW 这样的方法被用来监管偏差[8]。不管怎样，
为了发现网络的核心以及高度节点与他们的粉丝，我们没有研究已知方法的有效性。事实上，
不同的采样方法获得的采样网络是十分不一样的[9]。在这项工作中，我们将会用滚雪球采样45
方法检测微博网络的核心，并更换采样的种子，采样的轮数，采样比例来验证他们的有效性。
1 目标和评价
核心检测的主要目的是发现核心用户并恢复他们的粉丝网络。在一个信息有限的大型在
线社交网络中，作为第一步，核心用户需要通过有效的基于爬取的采样技术识别出来。然后
是他们粉丝的网络。为了检测核心网络和找到核心网络的特征，我们提出两个网络采样的评50
价标准：核心节点覆盖范围，入度分布。
核心节点覆盖度
由于核心用户的身份是无法获得的，我们首要关注的问题就是核心节点的覆盖度，这直
观的反应了采样方法在发现未知核心用户的能力。核心节点覆盖度定义为被采样了的核心节
点与全部核心节点的比例。 55
c
s
N
n
C (1)
ns 是采样中核心节点的数量，Nc 是网络中核心节点的实际数量。
数值分析显示一个具有中等种子数量的采样能比较高概率的获得核心节点。根据用户的
喜好，种子的出边实际指向一些具体的节点。除此之外，对于那些具有相对较低入度的核心
节点（不是那些具有数百万粉丝的节点），他们的粉丝倾向于关注很少的社区，所以不是所60
有的种子都有相同的几率来到达这些节点的。因此，滚雪球采样对高度节点具有偏差。
入度分布
粉丝网络是一个有影响力用户的重要特征，它决定了消息能多好的被传播。级联信息最
开始是通过一个人的粉丝传播的。因此粉丝的数量能立即影响有影响力用户的信息。
让 G（V，E）表示一个有向图，d(v)是节点 v 的入度。核心的入度分布如下： 65
),...,,( 10 m (2)
θ i 表示入度为 i 的节点的比例，m 是核心节点的最大入度。入度分布描绘了核心用户
集体影响力的特征。
由于最多获得 5000 个粉丝的限制，微博中核心节点的粉丝网络大部分是不可见的。当
用到采样中核心节点的入度分布时，我们需要确定它是真的恢复了网络中的实际分布。 70
2 微博采样实验
采样策略
这篇文章聚焦在 Snowball Sampling，它迭代的扩大遍历的节点。多年来，它在很多领
域都得到应用并且显示了它在获得具体节点数量的能力。理论上，通过足够数量的迭代，网
络中所有的节点，关系，边除了孤立节点都可以被爬取到。在这种情况下实际的问题是花费75
和利益的考虑。所以通过适当的设定采样比，可以比较充分的了解网络。这带来种子选取，
采样深度的讨论。它们会严重影响度分布的评估。
- 3 -
理想情况下，种子都是随机选取的，也就是说选取每个节点的可能性符合独立的伯努利
分布。实际上越高的深度会使采样节点的独立性越好，但同时会由于更高的冲突度降低有效
性。如果可能的话，较少采样深度（例如一波具有大量随机分布种子的完全滚雪球采样）可80
以模仿随机种子采样的行为。它可以生成跟真实度分布较像的度分布。
结果和分析
我们设计了三个实验来验证我们检测大型在线社交网络核心的策略。这些实验都是在我
们的微博数据上进行的。
实验一用一波完整滚雪球采样，种子大小从一千到一百万变化。它模仿随机节点和随机85
边采样并证明了获得核心节点和网络中的所有节点的能力。
实验二用固定数量的种子大小（一千和一万）进行了数轮完整滚雪球采样。这个实验的
目的是揭示采样效率和每轮采样深度的评价准确度。
实验三用一万个种子进行数轮部分滚雪球采样。采样比例决定了采样覆盖的速度和采样
节点的独立性。我们希望实验能让我们看到采样独立性的效果。 90
实验一：种子数量
图 1 显示了核心节点的覆盖度和一波完整滚雪球采样下的全部网络。种子大小根据不同
的间隔从 1K 到 1M 进行变化。当种子大小为 10K 和 100K 时，核心节点的覆盖度分别是
%和 100%。结果显示即使是有很少种子的一轮滚雪球采样也能比较容易的获得高入度
的节点。同时很难探测到网络中的全部节点。当种子大小达到 1M 时，全网的覆盖率仍然低95
于 60%。
图 1 不同种子大小的节点覆盖度
请注意上面计算的前提是我们能够正确的从采样节点中选择核心节点。在一轮滚雪球采
样中，采样节点的粉丝数量在第二轮采样之前都是未知的。因此需要用采样准确率和召回率100
来评价结果。图 2、图 3 显示 10K 个种子的采样中的前 100K 个节点的覆盖度已经达到 80%，
但是准确度只有 40%。
- 4 -
中国科技论文在线
图 2核心节点覆盖度的准确率
105
图 3核心节点覆盖度的召回率
实验二：采样深度
一个完整的滚雪球采样有较高的扩张率。所以第二波、第三波能获得较大比例的核心节
点和全网节点。图 4 显示在第一波的末尾，1K 和 10K 种子的采样分别覆盖了 35%和 92%的
核心节点。然而，在第二波第一波中的空隙消失了，这是因为他们都覆盖了全部的采样节点。110
整个网络覆盖度的情形和核心节点十分相似。不管初始种子大小是如何的大，在完整滚雪球
采样的第三波能覆盖几乎整个网络。
- 5 -
中国科技论文在线
图 4 一千和一万种子时每轮采样的覆盖度
更多轮数的采样会给采样节点带来更好的独立性，入度分布也因此获得更多的偏差。不115
管核心节点的粉丝数量是十分的高还是十分的低，它会过低的估计核心节点的入度。图 5
显示，随着采样深度的增加，被采样的核心节点入度会以一个更加有效的方式接近真实值。
通过进行一个完整的滚雪球采样，全网的节点几乎都能够被覆盖，但是会引入更多的入度分
布偏差。更多的初始独立种子会使收敛加快，但是会给核心节点入度分布的较低尾巴带来更
多的偏差。 120
图 5 一万种子时核心节点的入度分布
实验三：采样比
图 6 显示不同采样深度下不同采样比的节点覆盖度。当采样比被设定为 30%时，它对
降低收敛速率的效果不大。所以如果我们想要多进行几轮采样的话，采样比应该相当低。中125
等采样比会在几轮之内降低覆盖核心节点和全网节点的速度。
图 6 不同采样比下核心节点的覆盖度
3 结论
影响滚雪球采样的主要因素是种子的选择，采样比和采样深度。主要的结论是带有中等130
大小随机种子的几波完整或部分滚雪球采样能够检测到核心网络。无论如何，这三个因素都
会影响覆盖度的准确性和核心节点入度分布的评价。
采样比控制着扩展速率，也就是采样路径长度和采样节点的独立性。事实上，只有很少
的采样比能够实际扩展采样路径长度。多波低采样比的采样类似于 RW，它产生较少的偏差。
采样深度实际上是由前两个因素决定的。但是在可控制的情况下，采样深度可以根据爬135
取源进行调整。如果种子和采样比是合适的和固定的，增加采样深度只会降低入度的绝对距
离，但不是采样的偏差。
这篇文章探索了不同滚雪球采样策略在检测一个大型有向网络的核心结构的作用。我们
- 6 -
中国科技论文在线
发现滚雪球采样对采样种子，采样深度，采样比是敏感的。
[参考文献] (References)140
[1] E. Bakshy, J. Hofman, W. Mason, and D. Watts. Identifying `inuencers' on twitter[A]. E. Bakshy. The Fourth
ACM International Conference on Web Seach and Data Mining (WSDM)[C].Hong Kong:World Scientific
Publishing，-10.
[2] D. Centola, V. Eguiluz, and M. Macy. Cascade dynamics of complex propagation[J]. Physica A:Statistical
Mechanics and its Applications,2007,374(1):449-456. 145
[3] M. Cha, H. Haddadi, F. Benevenuto, and K. Gummadi. Measuring user inuence in twitter:
The million follower fallacy[J]. ICWSM ,2010,14(7):8-9.
[4] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D. Hwang. Complex networks: Structure and dynamics[J].
Physics reports, 2006,424(4):175-308.
[5] R. Kumar, J. Novak, and A. Mining:Models, Algorithms, and Applications[M]. New 150
York:Springer New York,2010.
[6] G. Palla, A. Barabasi, and T. Vicsek. Quantifying social group evolution[J]. Nature,2007, 446(7136):664-667.
[7] S. Catanese, P. De Meo, E. Ferrara, G. Fiumara, and A. Provetti. Crawling facebook for social network analysis
purposes[J]. Mining and Semantics, 2011,91(30):1-7.
[8] M. Gjoka, M. Kurant, C. Butts, and A. in facebook: A case study of unbiased sampling 155
of osns[A].M. Gjoka. INFOCOM, 2010 Proceedings IEEE[C].San Diego: San Diego Press, 1-9.
[9] S. Lee, P. Kim, and H. Jeong. Statistical properties of sampled networks[J]. Physical Review E,2006,73(1):1-6.
