- 1 -
基于MapReduce的大规模社会网络结构分析
刘国俊，张铭，燕飞**
（北京大学信息科学技术学院，北京 100871）
摘要：社会性网络服务(Social Networking Services(SNS))，是旨在帮助人们建立社会性
网络的互联网应用服务。在当下的 Web 时代，SNS 变得越来越活跃。对 SNS 社会网络的
结构进行分析，可以挖掘社会网络潜在规律特点，以利于提供更优质的服务。然而，随着
SNS 规模的不断膨胀，单台机器无法处理 TB、PB 数量级的海量数据，传统的基于单台机器
的分析方法已经不适应 SNS 的迅猛发展。MapReduce 作为 Google 提出的一个编程模型，提
供了一种利用多台机器运算能力的处理大规模社会网络分析问题的新途径。本文利用了
MapReduce 的开源实现——Hadoop，完成了一系列大规模社会网络分析的实验，包括测量节
点强度、边权值等一系列的度分布，研究图的边权值的动态演化，测量大型网络的聚类系数
和直径。本文实现的分布式海量数据分析方法，将为社会网络的数据分析处理提供很好的借
鉴作用。
关键词：社会网络分析；SNS；海量数据；MapReduce
中图分类号：TP311
Large-Scale Social Networks Structure Analysis based on
MapReduce
Liu Guojun, Zhang Ming, Yan Fei
(School of Electronics Engineering and Computer Science, Peking University, Beijing 100871)
Abstract: Social Networking Services are web services aiming to help people establishing on-line
social network and social networking applications. SNS is becoming more and more popular in Web
era. Analyzing the structural properties of social networks help us understand the dynamics of
social networks and promote the service quality. As an important part of social network analysis, a lot
of researches have been carried out in this area. However, with ever expanding scale, a single machine
can not handle TB, PB magnitude of the mass of data. Traditional analysis methods based on a single
machine is not scalable to the rapid development of SNS. MapReduce, a programming paradigm
proposed by Google, shows us a new approach to deal with large scale social network analysis
problems by taking advantage of multi-machines. This paper studies a series of large scale social
network structural properties by using an open source implementation of MapReduce - Hadoop. The
structural properties include distribution laws, the evolution of the weight of edges，diameters and the
clustering coefficients of real world social networks. We believe that our work will shed light on the
study of measuring large-scale social networks.
Keywords:Social Network Analysis;Social Network Services (SNS);Large-scale;MapReduce
0 引言
随着 技术的发展，用户参与网络内容建设的积极度越来越高，各种网络服务层
出不穷，但当下最流行的要数 SNS（Social Network Services）。社交网站掀起了全球流行新
风尚，国外的知名网站 Facebook 作为 SNS 的代表性站点，已经有了超过 4 亿的注册用户。
根据分析服务机构 Hitwise 公布的最新数据，其流量一度超过了搜索引擎巨头 Google。此外，
- 2 -
还有像 Twitter， MySpace，Flickr 等用户众多的网站。有报道称，SNS“吸引了近半数的上
网用户”[1]。
SNS 网站背后对应的庞大的用户群构成了一个贴近真实世界的社会网络。通常把社会
网络的结构抽象成一个图，社会行动者用节点表示、行动者之间的联系用边来表示。研究社
会网络的结构和性质等价于研究其对应的图的性质。随着 SNS 的迅猛发展，对应的图规模
在急剧的扩张，用户群的数量达到千万量级。因此，基于单机内存，将整个网络信息导入内
存的传统分析方法已不再适宜 SNS 的发展步伐。
如何对大规模社会网络结构进行分析？一般来说，有两种解决方案：一是使用处理能力
更强大的工作站，特别是要有大容量的内存；另外一个方法是利用廉价的机器组成的集群，
比如网格计算或分布式计算。第一种方法不能满足学术界使用的需要，一是因为价格太贵，
二是这种方法只能满足暂时的需要，随着网络图的扩大，可以预见不久之后，这种方法仍然
会遇到先前的瓶颈，也就是说这种方法不具备“可扩展性”。对于第二种方法，虽然其相对
花费较少，但是写并行的程序难度很大，程序员必须对集群的架构、网络要有相当的了解并
且还要考虑到并行环境下可能出现的各种问题：网络通信故障、单点故障、同步、容错，等
等。
Google 在 2004 年的 OSDI 会议上提出的 MapReduce 的编程模型无疑给这个问题的解决
带来了一个好消息[2]。“MapRedcue”这个概念来源于函数式编程，并且它充分利用了廉价
机器的潜力。它并不要求程序员处理并行工作的机器会遇到的诸如通信故障、延迟等问题。
Hadoop 作为 MapReduce 原理的开源实现[3]，提供了一个分布式的文件系统 HDFS 和一个
MapReduce 运行环境。因此，可以使用集群的力量来解决大规模社会网络分析问题。
1 数据集描述
本文目的在于研究真实网络的结构性质及其演化过程。所以，研究的第一步是要找到一
些的真实数据集。但是如何获取真实的社会网络数据是一个很困难的问题，即使一个社会成
员自己也不能完全确定自己参与了多少社会活动，才导致他自己目前所处的社会网络结构。
而且传统的数据来源基本上是通过调查表、问卷的形式获得，样本数量太少，对结果的影响
的偏差性较大。但是，可以在一些近似的易获取数据集上开展研究，如“共同关系
(co-relationship)”的网络，代表社会参与者之间有某种共同的兴趣爱好。比如，论文共同作
者网络，书籍共同借阅网络等。包含了论文信息的共同作者网络是一个理想的数据集。
DBLP[4]发布了一系列包含论文、作者、发表时间的数据集。有了这个数据集就容易得到论
文“共同作者(co-author)”网络。更进一步，如果越来越多的用户参与到 Web 内容的构建，
可以从 Internet 得到更多类似这种隶属关系网络的数据。CiteULike[5]和 Delicious[6]是两个著
名的社会书签网站。通过爬取，可以得到带时间戳的“user-post-tag”数据集。这类数据集
又可细分为“用户-资源”和“用户-标签”关系网络。这些数据集为本文的研究提供了丰富
的隶属关系网络资源。下文将对来自于 CiteULike，Delicious 和 DBLP 的数据集做详细介绍。
CiteULike 数据集
CiteULike 是一个提供在线的、免费的组织学术出版情况的网站。该网站提供了
“who-post-what”数据集，表示了某一作者在某一时间发表了什么文章。数据集里共有从
到 的 5,665,479 条原始记录。如果考虑收藏文章和打标签是两种不同的
行为，可以得到两种不同的社会网络：“用户-资源”和“用户-标签”网络。此外，一个真
- 3 -
实的社会网络是多种事件共同发生导致的结果。不区分收藏和标签的而把它们看作同一种行
为，建立“用户-事件”网络对模拟真实的社会网络是很重要的。
从 CiteULike 数据集得到三个隶属关系网络：一个“用户-资源”网络，一个“用户-标
签”网络，一个“用户-事件”网络，分别表示为 2
C
u rG ， 2
C
u tG ， 2
C
u eG 。表 1 前 3 行展示
了这三个网络的统计信息。
表 1 原始数据集的信息
Details about Datasets
参与者 事件 边数 时间跨度
2
C
u rG
2
C
u tG
2
C
u eG
47,431
47,431
47,431
1,547,286
314,513
1,861,799
1,801,254
1,185,886
2,987,140
2004-11 至 2009-5
2004-11 至 2009-5
2004-11 至 2009-5
2
De
u rG 238,624 16,463,050 1,724,941 2008-1至 2008-12
2
DB
a pG 757,646 1,263,493 3,265,576 1995 至 2009
Delicious 数据集
本文从 Delicious 的网站抓取了“who-post-what”的数据集。这个数据集时间跨度是 5
年，从 2004 到 2009。Delicious 数据集的规模远远大于 CiteULike，所以本文只选取
的一年的数据信息，然后构建了一个用户-资源网络，表示为 2
De
u rG 。表 1 第
4 行展示了这个数据集的统计信息。
DBLP 数据集
本文从 DBLP 网站上获得了“author-to-paper”的信息。它包含了作者发表论文的信息。
本文选取了自 1995 年以来发表的论文构建了一个“作者-论文”网络，表示为 2
DB
a pG 。表 1
第 5 行展示了这个数据集的统计信息。
表 2 原始数据对应的共同关系图的信息
Details about co-relationship network
节点数 边数 快照
'
2
C
u rG
'
2
C
u tG
'
2
C
u eG
25,930
34,523
39,139
925,942
41,399,356
41,815,224
29
29
29
'
2
De
u rG 224,201 438,079,524 24
'
2
DB
a pG 712,783 2,397,435 15
在本文的数据集中，如 Delicious 数据里某些资源拥有成千上万个用户，如果一个资源
- 4 -
中国科技论文在线
有 N 个用户，那么每个用户与其他 N-1 个用户有一个“共同收藏”的关系，总共有 ( 1)
2
N N −
条边。假想 N=10000 的话，那么结果将会十分的巨大以至于一台机器无法处理据，所以本
文将数据分布到 20 台机器上，并利用 MapReduce 编程模型得到共同关系(co-relationship)的
网络图。本文从原始的数据集里得到 5 个共同关系网络，如表 2 所示。
2 使用 MapReduce 的分析方法
本文使用 MapReduce 方法，对大规模共同关系社会网络的分布律（包括节点度分布、
节点强度分布、边权值分布、附属网络的事件度分布）、边的权值的增量和期望、聚类系数、
和网络直径尽心了测量。下文将逐一介绍 MapReduce 测量算法。
分布律测量
节点的度分布
网络里面的点一般都不是孤立的。对一个节点，与之有联系的其他节点的个数称为该节
点的度。在社会网络中，结点代表了社会行动者，直观来看，结点度数越高，说明该社会行
动者某种意义上的“重要性”越大。研究整个网络中结点度分布的情况，可以帮助了解网络
的结构。
MapReduce 测量节点度分布的算法中，输入数据的格式是“用户 A-用户 B-边的权值”
（“UserA-UserB-Weight”），通过如图 1 所示的的步骤来得到节点的度分布。
图 1 MapReduce 得到节点度分布过程
Map and Redcue phase to get Degree Distribution
节点的强度分布
一个节点的强度等于连到该节点上的边的权重之和 Si表示如下
- 5 -
中国科技论文在线
( )
i ij
j v i
s w
∈
= ∑
其中 ( )v i 是连接到节点 i 的所有节点的集合，wij是边权重。
由于本文研究的网络图是带权的，带权意味着点和点之间不仅连通，而且反映了连接的
紧密程度。所以节点的强度更能表明了它的连通性。
在求度分布的时候未考虑网络图边的权值，在求节点强度的时候需要把权值考虑上。所
以，处理的过程十分类似与求节点的度分布，Map 的输入是" | | "i jnode node weight ，Map
阶段的输出是" | "inode weight 和" | "jnode weight ，Reduce 阶段对于同一个节点的所有权值
统计相加，Reduce 的输出是" | "knode TotalWeight 。
边的权值分布
本文所研究网络的边是带权边。如果用户 A 和用户 B 共享一些资源或者打过同样的标
签，那么他们之间边的权重就是 1。两个用户之间很可能不只共享过一个资源，所以它们之
间边的权重很可能大于 1。
用 MapReduce 处理方法如下：Map 阶段输出的<key, value>对是 ,1Weight< >，代表有 1
条权重为 Weight 的边，在 Reduce 阶段把权重相同的边的数量进行统计从而得到分布。
附属网络的事件度分布
在本文的研究里，“事件”是一个广泛意义上的概念。一个社会行动者参与或者属于的
活动都可以被视为事件。事件必须是和社会行动者相关联。比如，事件可以是一群足球迷的
俱乐部，一个学生讨论组，一个研究者的会议，等等。
一个社会关系链接是如何形成的？一个社会行动者如何与一个陌生人成为朋友呢？他
们只有参与一个特定的事件，比如学术会议，才有机会成为朋友。所以说，社会关系链接的
形成是由事件驱动的。
一个事件可能有很多行动者参加，参与的行动者的人数被称为事件的度。用 MapReduce
求出事件度分布比较容易。把原始数据里用户打标签的行为（或者对资源做标记）看作是一
个事件，Map 的输入是" | | "user resource tag ，Map 的输出是" |1"tag ，Reduce 阶段对同一
key 值的记录进行统计个数，即为事件的度分布。
边的权值的增量和期望
如上文所述，如果两个行动者参与过一个事件，那么他们对应的网络图里的节点就会形
成一条边。很可能两个人参与了不止一个事件，所以两个节点之间边的权值会有区别。直观
意义上来看，权值大的边表明这两个人的关系更紧密。
边的权值的增量，可以深刻的揭示一个网络图是如何演化的。本文已经得到了网络图按
照时间做出的图快照，在相邻的快照之间如果能够知道有哪些边是新形成的、哪些边的权值
增长了，对了解网络的演化是很有意义的。
这一步的输入数据是时间上相邻的两个快照。Map 的输出是 ( | , )i jnode node Weight ，在
Reduce 阶段，对于某个 key 来说，如果对应的只有一个 value，说明这条边是新生成的；否
则，如果有两个对应的 value，看对应的边权是否有变化，有变化的话，增量即为
2 1| |w W W= −+ 。然后做一个统计就可以得到权值增量的度分布。
- 6 -
中国科技论文在线
权值增量的期望就是对增量做一个加权平均，在此不再赘述。
聚类系数
现实中，很多网络都具有一个共性-社区效应。即，整个网络是由若干个“群(group)”
或“团(cluster)”组成。每个群内部节点之间的连接相对紧密，但各个群之间的连接相对稀
疏。这种社区效应在社会网络中特别明显。而聚类系数就是描述社区效应的重要指标。
整个网络的聚类系数（用 C 表示）就是所有节点的聚类系数的平均值。显然，0 =<C <=1，
C 越大说明网络的聚集程度越高。一个有趣的现象是，现实中的社会网络的聚类系数往往比
具有相同节点和边的随机网络大许多，例如，Watts[7] 等发现演员网络的聚类系数是 （如
果两个演员共同演了一部电影，那么他俩之间就有一条边），而相同数量节点和边的随机网
络的聚类系数却只有 。
一个节点的聚类系数是与它连接的其他节点中，存在边的比率。对于一个网络
( , )G V E= ，聚类系数 iC 定义如下
2 || ( , ) | ( , ), ( , ), ( , ) ||
( 1)i i i
v w i v i w v w EC
k k
∈= − （其中 ki是节点 i 的度）
聚类系数可以被解释成任意随机选取拥有共同邻居的两个节点，它们之间有一条边的概
率。一个网络的聚类系数是所有节点的聚类系数的平均。由于需要遍历所有可能的 n3组合，
所以最朴素的算法的时间复杂度 O（n3）。
在求聚类系数的时候，会有三元组(Triple)和三角形(Triangle)的概念。所谓的三元组，
就是指如果节点 A 跟节点 B 和 C 都有一条边，那么边 AB 和 AC 就形成了一个三元组。如
果节点 B 和 C 之间也存在一条边的话，那么节点 A、B、C 构成了一个三角形。下图中，左
边是一个三元组，右边是一个三角形。
一个节点的聚类系数就是其邻接的三角形的数目除以三元组的数目。
图 2 三元组和三角形示例
example of Triple and Triangle
本文的方法是先找出所有的三元组，然后找出所有的三角形。 Cohen[8]介绍了利用
MapReduce 在大的图里面寻找三角形的方法。本文采用了 Cohen 的思想，细节参照文献[8]。
算法的核心思想是，穷举所有可能的三元组然后检查第三条边是否存在。如果第三条边存在，
就意味着找到了一个三角形。分析可以发现，Cohen 的算法并没有从本质上降低时间复杂度，
但是利用了多台机器的优势。
算法的伪码描述如下：
- 7 -
中国科技论文在线
算法 1：网络图中求出节点 Triple 元组个数
输入：用边表示的图信息，格式为 | , deg | degi j i jnode node ree ree
输出：用两条边表示的 Triple
Map 阶段：
1 if deg degi jree ree<
2 then 向 Reduce 发射出 Record： ( , | )i i jnode node node
3 else 发射出 Record： ( , | )j i jnode node node
Reduce 阶段：
1 if inode 作为 key 对应的 value 的个数大于等于 2
2 对于 value 集合 v(i)，如果有 , ( )j knode node v i∈ 并且 j k≠
3 那么发射出记录 ( | , )j k inode node node
算法 2：网络图中的节点求 Triangle 三角个数
输 入 ： 算 法 1 的 输 出 ， 以 及 用 边 表 示 的 图 的 信 息 ， 格 式 为
| , deg | degi j i jnode node ree ree
输出 ：用三个点表示的 Triangle
Map 阶段：
1 if 输入数据来源于算法 1
2 那么，向 Reduce 发射出： ( | , )i j knode node node
3 else 发射出： ( | , | )i j i jnode node node node
Reduce 阶段：
1 ();TripleList newTripleList=
2 ;isThirdEdgeExist false=
3 for 对于这个 key 的所有 value
4 if value 来自于算法 1
5 . ( );TripleList insert value
6 else ;isThirdEdgeExist true=
7 end
8
9 if isThirdEdgeExist true== ，then
10 for 所有属于TripleList的Triple
11 发射出 ( , )iedge key
网络的直径
对于网络的直径，首先要明确两个概念：
（1）节点的离心率。对节点 i，它的离心率 ei定义为 i 到网络中其他节点最大
的距离，即
i ije max d=
- 8 -
中国科技论文在线
（2）网络的直径。网络的半径 D 定义为网络所有节点中最大的离心率，即
iD max e=
传统的图里面计算点和点之间最短距离的方法是 Dijkstra 提出的“最短路径算法”，一
般都是在单台机器上运行。这种方法需要获得图的全局信息，必须把整个网络图载入到内存。
但是本文网络图的规模非常大，不可能采用这种简单方法。
一个并行的宽度优先遍历（Breadth-First-Search，BFS）算法已经被提出来[9]。这个算法
里面，图里的节点不需要知道全局的状态信息，也不需要和其他节点通信交流信息。
算法的主要思想是，从根节点(root)出发（根节点是起始点），然后层次的访问其邻居
节点（与之相邻的节点）。每个节点都知道它自己的邻居（可通过 1-趟 MapReduce 程序得
出来），并且它们维护了一个到根节点的距离（初始时，为无限大）。每个节点有一个 flag
标志位表明这个节点是否被访问过，flag 的取值为 0、1、2，分别代表未访问、正在访问、
已访问。如果节点 A 正在被访问，其到根节点的距离为 N。那么其邻居节点，比如 B，将
会被标记其到根节点的距离为 N+1，并且被标记为“下次待访问”，这就是对一个节点层次
进行扩展。当然，节点 B 在下次遍历时是否被访问还要看其以前的状态，如果 B 已经被扩
展过了的话那么就会不做任何其他操作。
这种算法就是图的“层次遍历”的思想。比如在上图中，从节点 1 开始访问，每次都遍
历下一层。算法可以保证所有的点一定会被访问一次，如果它在连通分支上的话。
并行的 BFS 算法的伪码表示如下：
算法 3：求图中某一点到其他点距离的分布式宽度优先算法
输入：图信息，用 | ( ,node outlinks dista , )nce flag
输出： | ( , | )node outlinks distance flag
Map 阶段：
1 if inode 是当前正在访问的节点
2 for 对于这个节点的邻居节点 jnode
3 . . 1;jnode distance nodei distance= +
4 . 1;jnode flag =
5 发射 ( , | . | . );j j jnode NULL node distance node flag
6 . 2;jnode flag =
7 发射 ( , . | . | . );i i i inode node outlinks node distance node flag
8 else 发射出： ( , . | . | . );i i i inode node outlinks node distance node flag
Reduce 阶段：
1 对于以这个node为 key的所有 value来说
2 .node distance = 最短的distance
3 .node flag = 值最大的 flag
4 发射出 ( , | . | . )node outlinks node distance node flag
- 9 -
中国科技论文在线
图 3 并行 BFS 示意图
parallel BFS procedure
3 实验和结果分析
图 4 节点度分布
ode degree distribution
本文在一个 20 台机器组成的 Hadoop 集群上完成了实验。每台机器 4GB 内存，1 个 4
核 Intel® Xeon 的 CPU，运行的是 Red Hat Linux，Hadoop 的版本是 。 所有
的机器通过 1Gbps 的全双工网卡通过千兆以太网交换机连接。
度分布律
节点的度分布
通过测量得到，一个共同关系社会网络的每个快照的节点的强度分布遵从 power-law[10]
并且 power-law的指数随着时间保持不变。下图中，为了保证简洁性，只展示了各个网络的
最终的快照。
- 10 -
中国科技论文在线
图 4 分别是 ' 2
C
u rG ，
'
2
C
u tG ，
'
2
C
u allG ，
'
2
De
u rG ， ' 2Dblpa pG 的度分布。
节点的强度分布
通过节点强度分布测量得到，节点的强度分布也遵循 power-law分布，并且指数参数γ
随着时间变化保持稳定。如图 5 所示。
图 5 节点强度分布
node strength distribution
边的权值分布
通过边权值分布测量得到，边的权值分布也遵循 power-law，并且其指数参数γ 随着时
间的增长保持稳定。如图 6 所示。
附属网络的事件度分布
经测量发现，附属网络的事件的分布也符合 power-law，power-law的参数γ 随着时间表
现得稳定不变。如图 7 所示。
- 11 -
中国科技论文在线
图 6 边权值分布
edge weight distribution
图 7 事件度分布
event degree distribution
边的权值增量和期望
在实验里，t 时刻权值为 W、t+△t 时刻增量为△W 的边的数量随着 W 的增加而较少，
- 12 -
中国科技论文在线
并且随着时间变化保持稳定。并且，权值大的边倾向于有更大的增量期望。权值增量的期望
与边的权重呈线性相关。如图 8 所示。
图 8 权值增量示意图
edge weight addition
网络的聚类系数
使用 MapReduce 方法并未从本质上降低算法复杂度，但是利用多台机器并行工作提高
运行速度。本文算法是纯枚举的方法，时间复杂度达到 3( )O n 。由于要枚举出所有的三元组
和三角形，所以中间数据达到 250G。表 3 展示了测量结果。
表 3 网络的聚类系数
clustering coefficient of network
数据集 聚类系数
CiteULike
Delicious
DBLP
实验结果说明，真实世界的社会网络的聚类系数比随机网络的聚类系数大，说明真实世
界联系更紧密。并且由于 DBLP 是真实的论文发表关系网络，行动者之间联系更紧密，所以
聚类系数 CiteULike 和 Delocious 的都大一些。
网络的直径
计算直径的过程是迭代进行的。每迭代一次就进行图上一层的遍历。由于事先不知道图
的深度，所以设置了一个比较大的阈值。并且，分布式算法对于每个点到其他点的距离都需
要遍历整个图一遍，所以不可能求出每个点到其他点的距离。所以本文采用了抽样的方法抽
取了一些点作为“代表”来求距离。
为了避免偏差，根据点的度数，分层抽取了一些样本点。实验中，一共迭代 35 次，发
- 13 -
中国科技论文在线
现有 9%的点始终访问不了。这说明本文所研究网络不是全连通的，存在多个连通分支。实
验结果如表 4 所示。
图 9 网络连通情况示例
connected components
表 4 网络的直径
diameter of each network
数据集 直径
CiteULike 10
Delicious 11
DBLP 14
4 结论
传统的社会网络分析方法只能应用于早期的小规模的、手工收集的数据，而互联网上用
户的广泛参与使得社会网络的数据成千上万倍的增长导致传统的方法并不适用。
针对 Web 上海量的社会网络数据，本文研究了利用 MapReduce 进行并行化分析处理的
有效方法：
（1）网络结构图的性质测量，揭示了节点的度分布律等规律；
（2）对网络结构图的演化进行了动态测量，揭示了网络演化的规律；
（3）基于 MapReduce 的分布式计算方法，测量了大型网络图的直径测量，并测量了大
型网络的聚类系数，提高网络图的可计算规模。
给定一个图，对图挖掘的研究有两个基本的问题：第一个是测量出能代表真实网络的某
些性质。其次是能构造生成模型，揭示出图的演化规律下。本文已经使用 MapReduce 分布
式的解决了问题一，下一步的工作是如何利用 MapReduce 的并行计算的能力揭示出图的更
多规律，并构造出满足这些规律的生成模型。
[参考文献] (References)
[1] Techweb[OL]. ..
[2] J. Dean and S. Ghemawat. Mapreduce: Simplified data processing on large clusters[A]. In OSDI, 2004.
[3] Apache Hadoop[OL].
[4] DBLP[OL].
[5] CiteULike[OL].http://
[6] Delicious[OL]. http://
[7] D. J. Watts and S. H. Strogatz. Collective dynamics of’small-world’networks[J]. Nature,393(6684):409–10,
1998.
[8] J. Cohen. Graph twiddling in a mapreduce world[A]. In Computing in Science and Engineering, pages 29–41,
2009.
[9] J. Lin. Graph algorithms with mapreduce[OL].
[10] Clauset, C. R. Shalizi, and M. E. J. Newman. Power-law distributions in empirical data[A], SIAM Review,
(51):661-703, Feb 2009.
