2018, Vol. 29
2. 成都信息工程大学 网络空间安全学院, 四川 成都 610225
2. School of Cybersecurity, Chengdu University of Information Technology, Chengdu 610225, China
如今, 随着社会的进步与科技的快速发展, 大数据[1]已经变得越来越普及, 逐渐成为一个耳熟能详的概念.在海量数据研究中, 高性能是必须予以解决的问题之一.虽然大数据研究面临着来自各个层面的挑战, 但同时也存在着机遇, 如利用复杂的算法和程序从大量数据中挖掘出关键有用的信息, 到利用高性能技术与系统及时获取有用的内容.当前, 如何利用主流的系统如Hadoop[2]来应对大数据应用挑战成了的一个热门的研究方向.在本文中, 主要研究如何利用分布式的存储和计算架构来构建海量图数据以及处理对图数据进行数据挖掘的问题.
在图数据挖掘中, 图聚类是基本的研究任务.图结构聚类(SCAN)是基于密度的聚类方法, 该方法不仅能够挖掘图中的聚类结构, 而且还能找到图中的Hub节点以及离群节点.随着图数据规模的不断扩大, 现有的SCAN算法已经无法满足大规模图数据的需求.目前的SCAN算法优化都是针对串行的SCAN算法的剪枝优化, 例如, Shiokawa等人[3]提出了剪枝的SCAN算法SCAN++, 以及Chang等人提出了pSCAN[4].尽管这些剪枝方法能够大幅提升SCAN算法的效率, 但在大规模图上依然比较耗时, 而且针对超大规模图数据依然无法处理.
为了解决SCAN算法对大数据的可扩展性问题, 本文提出一种基于MapReduce的结构图聚类算法.具体地, 首先设计了基于MapReduce的核心节点计算算法, 然后提出了两种合并聚类的MapReduce算法.算法能够有效地剪枝不必要的计算, 从而大幅度地减少IO的次数, 进而提升算法的性能.最后, 通过在真实的大规模图数据上进行实验验证, 提出的算法呈现接近线性的可扩展性.
本文的主要贡献包括以下两个方面.
1) 提出基于MapReduce分布式框架的图结构聚类算法及剪枝的优化方法;
2) 通过大规模的真实图数据测试, 实验结果表明, 提出的两个合并聚类算法具有较好的可扩展性.
1 相关概念在本节中, 主要简略介绍MapReduce分布式计算框架设计的流程及其原理, 同时引进结构聚类的相关基本概念.
1.1 MapReduce框架MapReduce是一种编程模型, 是Google公司于2004年提出的能并发处理海量数据的并行编程模型[5], 允许开发人员开发高度可扩展和容错的并行应用程序来处理分布式无共享环境中的大数据.MapReduce算法在执行时, 每轮涉及3个阶段:map, shuffle和reduce.假设输入数据作为一组键值对存储在分布式文件系统[6]中, 3个阶段的工作如下.
● map:在这个阶段, 每个机器从分布式文件系统读取一部分键值对$\{(k_{i}^{m}, v_{i}^{m})\}$, 并生成一组新的键值对$\{(k_{i}^{s}, v_{i}^{s})\}$在shuffle阶段[7]转移到其他机器, 其本质应用在于需要对数据一对一的元素进行映射转换, 通常是对数据进行截取过滤或者转化为算法需要的任何字符形式;
● shuffle:map阶段生成的键值对$\{(k_{i}^{s}, v_{i}^{s})\}$在所有机器上进行shuffle.shuffle阶段又可以分为Map端的shuffle和Reduce端的shuffle, 在shuffle阶段结束时, 保证具有相同键值$\{(k_{i}^{s}, v_{1}^{s}), $的所有键值对$(k_{i}^{s}, v_{2}^{s}), ...\}$
● reduce:每个机器将具有相同密钥$(k_{i}^{s}, \{v_{1}^{s}, v_{2}^{s}, ...\})$的密钥值对组合在一起作为$\{(k_{i}^{r}, v_{j}^{r})\}$, 从一组新的键值对$\{(k_{i}^{r}, v_{j}^{r})\}$生成并存储在分布式文件系统中, 以在下一轮中进行处理.
在每一轮中, 至少需要实现两个函数:map函数和reduce函数.map函数确定如何从$\{(k_{i}^{m}, v_{j}^{m})\}$生成$\{(k_{i}^{s}, v_{j}^{s})\}$, 而reduce函数决定如何从$(k_{i}^{s}, \{v_{1}^{s}, v_{2}^{s}, ...\})$生成$\{(k_{i}^{r}, v_{j}^{r})\}.$
1.2 结构聚类的基本概念结构聚类算法[8]是基于密度的聚类算法改良的一种社区结构发现算法, 其主要思想在于利用节点的邻居节点来作为聚类的标准.在详细描述使用MapReduce框架对网络图数据进行结构聚类之前, 首先给出结构聚类一些基本符号的解释和定义.
定义1(顶点网络). 假设v是图中节点, 令v∈V, 那么节点v∈V的结构由它和它的邻居节点所构成.用N(v)表示N(v)是一个点集, 其中包含的节点元素是与点v有边相连的节点, (v, u)表示以v为顶点的边, 如果该点集中不包括点v, 那么就称N(v)是点v的开邻居集合, 即N(v)={u|(v, u)∈E}; 若是包含点v本身, 则称为闭邻居集合, 即N(v)={u|(v, u)∈E}∪ v.
定义2(结构相似性). 用来描述有向图中任意两个节点结构相似性的符号是σ(v, u), 表示为两个节点共同邻居数与两个节点邻居数目的几何平均数的比值(邻居数包含节点本身), 其中, N[x]表示节点x及其相邻节点所组成的集合, 公式化为
| $ \sigma (v, u)=\frac{|N[v]\cap N[u]|}{\sqrt{|N[v]\cdot N[u]|}} $ | (1) |
定义3(ε邻居). 给定一个节点v, 与v节点满足一定的相似度的邻居, 称为v的ε邻居.ε是用于划分邻居与非邻居的相似度阈值.给定一个节点v, 所有满足σ(v, u)≥ε的节点都是v的ε邻居.若ε=0, 则图中所有节点均互为ε邻居节点; 若ε≠0, 则ε邻居的公式化表达是Nε[v]={u∈N[v]|σ(u, v)≥ε}.即, u满足是v的ε邻居必须满足以下两个条件:
| $ u\in N(v)\rm{, }\sigma (v, u) \geqslant \varepsilon $ | (2) |
定义4(核心节点). 当一个节点与其足够数目的邻居均满足一定相似度的时候, 该节点就是一个核心节点.核心节点v是特殊的节点, 满足有Nε[v]≥μ, 即满足ε邻居的数目大于μ, μ是阈值, 满足该条件的点就是核心点.直观而言, 核心节点在图中稠密处并且与周围的点相似度高.在本文中, 用isCore变量来标记一个节点是否为核心节点.
定义5(直接结构可达). 若节点u是核心节点的邻居的ε节点, 则称v直接可达u, 记作:
| $ DirREAC{{H}_{\varepsilon }}{{_{, }}_{\mu }}(v, u) $ | (3) |
若v和u都是核心节点, 那么这种可达的关系是具有对称性的, 记作:
| $ DirREAC{{H}_{\varepsilon }}{{_{, }}_{\mu }}(v, u)\Leftrightarrow DirREAC{{H}_{\varepsilon }}{{_{, }}_{\mu }}\left( u, v \right) $ | (4) |
若只有v是核心节点, 那么这种可达关系是不具有对称性的, 即, 不满足DirREACHε, μ(v, u).
定义6(结构可达). 如果存在一条节点链v1v2v3…vn-1中的点都是核心节点, 其中v1=v, vn=u, 若满足v1v2v3…vn-1是核心节点, vi和vi+1之间直接结构可达, 即DirREACHε, μ(vi, ui+1), 则就认为v和u之间是结构可达的, 表示为
| $ REACH(v, u)~ $ | (5) |
定义7(结构聚类cluster). 已知u∈C, 且u是核心节点, 对于∀u, 若u结构可达v, 即REACH(v, u), 则v∈C, 称为点最大性.对于∀v1, v2∈C, 有∀u∈V, 使得REACH(u, v1)和REACH(u, v2), 称为连通性.一个结构聚类需要同时满足点最大性和连通性.
2 算法整体研究框架基于MapReduce的结构聚类, 其研究框架如图 1所示.算法要求整体基于MapReduce实现, 因此在图 1中由7个小部分组成, 每部分都是基于MapReduce实现的.
|
Fig. 1 Overall process of distributed SCAN based on MapReduce 图 1 基于MapReduce的分布式结构聚类整体流程 |
图 1中, 算法主要分为分布式计算相似性、维度扩展[9]和分布式合并聚类这3个主要部分.
其中, 计算相似性分为4部分, 目的是为了检测核心与非核心节点, 主要包括数据处理、顶点度计算、边上三角形个数计算和相似度计算; 维度扩展是为了让图的每个节点带上核心节点信息, 在后期聚类阶段能够被识别, 从而正确聚类; 最后是本文提出的两个基于MapReduce的结构聚类算法.
具体算法过程在第3节详细给出.
3 基于MapReduce的结构聚类过程MapReduce框架很适合处理大规模的流数据, 而图算法的实现一直是MapReduce的难点.在本节中, 详细介绍如何在MapReduce上一步步求解出最终用于聚类的核心节点及其直接可达邻居集合, 并且对该核心节点以及局部聚类进行合并.
3.1 基于MapReduce求图中核心节点首先, 在求结构聚类的时候, 需要先求出网络图中的核心节点及其直接可达邻居集合.如图 2所示, 假设当ε=0时, 图 2(b)是图 2(a)中核心节点7与5个ε邻居的示例(假设ε满足条件), 类似于图 2(b), 每个节点都有一个同样性质的子图, 这些子图构成的集合是聚类[10]的基础.
|
Fig. 2 The Original graph and one of the local clusters constituted by cores 图 2 原始无向图及其中某个核心节点构成的局部聚类 |
计算核心节点分为以下几个部分:节点的度、节点之间的共同邻居(即边的三角形个数)、节点之间的相似性, 从而求出核心节点.
首先是求节点的度和边所在的三角形个数, 度是图节点最基本的特征, 而计算边所在三角形的个数在图结构中具有重要的特征.通过求出边上三角形的个数, 可以直接判断求出节点之间的共同邻居个数.在Hadoop中, 求节点度的方法比较简单, 比较有技巧的是求三角形, 这两个MapReduce算法在其他文献[11]中已经详细介绍.
以图 2(a)为例:节点度和边三角形个数的结果图如图 3所示, 图 3(a)表示顶点的度, 图 3(b)表示边(4, 7)有两个三角形, 分别是Δ347和Δ467, 表示节点4和节点7有两个共同邻居节点3和节点6.详细的MapReduce过程在此不做具体介绍.
|
Fig. 3 Node's degree and the edge (4, 7)'s triangle number 图 3 无向图节点度和边(4, 7)三角形个数 |
基于带度的边以及边上三角形的个数求图中两点之间的相似性.过程如下.
Map函数的输入为 < key, value>对, 该键值对有两种:一种是顶点以及顶点度, 以 < u|degree(u) v|degree(v)>的形式给出; 另一种是边以及边上三角形的个数, 以 < uv triangleNumber 的形式给出, 在算法1中, 将其当作已知条件作为输入.Map函数的key值输出是以边(u, v)为新的key', value输出是顶点度degree(u)|degree(v)和三角形个数triangleNumber作为value'.Reduce函数的输入是上一轮Map函数的输出, 输出是边以及边相似性.
算法1. 计算节点之间相似性.
输入:边及其顶点度 < edgeuv {u|degree(u), v|degree(v)}>, 边及其边上三角形个数<edgeuv triangleNumberuv>;
输出:边及其边上的相似性 < edgeuv similarityuv>.
1. Map(key, value)
2. key'←edgeuv
3. if value contains degree then
4. value'←d(u)|d(v)
5. else
6. value'←similariyuv
7. Emit < key', value'>pairs
8. Reduce(key', values')
9. du←0
10. dv←0
11. commonNeighborsuv←0
12. similarity←0
14. if value contains degree then
15. du←degree(u)
16. dv←degree(v)
17. else
18. commonNeighborsuv←triangleNumberuv
19.
20. Emit < edgeuv similarityuv>pairs
以图 2(a)为例:相似性的结果如图 4所示, 图 4(a)顶点数据表示顶点的度, 边上数据表示边的三角形个数; 图 4(b)的顶点数据代表节点编号, 边上数据是边两端点的相似性.图 5是详细的以无向图 2(a)为例子求出每条边的相似性的MapReduce过程.可以看到:在Map阶段, 将有序边作为key值, 因此, 同一条边的两个顶点的度和共同邻居就会进入到一个Reduce中, 在Reduce中, 可以利用这两个信息进行边相似性的计算.
|
Fig. 4 Calculate edge similarity based on the degree and the number of triangles 图 4 基于节点度和边三角形个数计算节点相似性 |
|
Fig. 5 MapReduce process for calculating edge similarity 图 5 计算节点相似性的MapReduce过程 |
接着, 本文需要根据边的相似性求出图中的核心节点.由核心节点的定义可知:当节点u的ε邻居不小于给定的阈值m时, u节点就被定义为核心节点.因此可以设计出检测核心节点的MapReduce程序, 算法是以边上两点作为key, 以边的相似性作为value构成 < u, v similarity 对输入; 以图的每个点作为key', 以布尔类型的变量isCore来标记该点是否为核心节点作为value'构成 < u, isCore>对输出, T表示该点是核心, F表示该点非核心.
算法2. 统计核心节点.
输入:边及其相似性 < edgeuvsimilarityuv>, 给定ε, μ;
输出:顶点及其核心变量isCore的(u, isCore)对.
1. Map(key, value)
2. u←key.u
3. v←key.v
4. Emit < u v, similarityuv>pairs
5. Emit < v u, similarityuv>pairs
6. Reduce(key', values')
7. ε-count←0
8. dv←0
9. for value in values' do
10. if similarityuv≥ε then
11. ε-count←ε-count+1
12.if ε-count≥μ then
13. value"←T
14. else
15. value"←F
16. Emit < u, value">pairs
例如, 在图 6(a)中, 当ε=0.7, μ=3时, 无向图的核心节点统计如图 6(b)所示, 核心节点为4b6和7, 节点填充颜色的是带T的核心节点, 无颜色的是带F的非核心节点.详细统计核心节点的MapReduce过程如图 7所示:在Map阶段, 算法将边及其相似性信息分割成该边的两个节点带上该边的相似性; 在Reduce阶段, 以每个节点作为key, 它的邻居和两者的相似性会进入到同一个Reduce.因此, 可以在Reduce阶段判断每个节点有多少个ε邻居, 从而判断该点是否为核心节点.
|
Fig. 6 Core(4, 6, 7) and non-core(1, 2, 3, 5) 图 6 核心(4, 6, 7)与非核心节点(1, 2, 3, 5) |
|
Fig. 7 MapReduce process for calculating cores 图 7 计算图中核心节点的MapReduce过程 |
3.2 基于MapReduce的图维度扩展
在第3.1节中, 我们对成功地对图的每个节点进行了是否为核心的标记, 但是每个节点还只是带着编号信息与单个节点是否为核心, 而且核心节点的所有邻居里面还有一些与核心节点只是邻居, 没有满足是核心节点e邻居的条件.如图 8所示, 图 8(a)是在某个条件得到的核心节点状态, 图 8(b)是维度扩展后的没有利用核心和ε剪枝的局部聚类.
|
Fig. 8 Node dimension extension 图 8 图节点维度扩展 |
接下来, 需将维度扩展后的最初状态剪枝掉与核心不构成ε邻居的节点, 并利用核心节点剪枝掉不需要合并的分支.
如图 9所示, 图 9(a)是最初聚类状态, 利用核心节点可以去掉1、2、3、5这4个非核心节点所在的局部聚类, 经过剪枝后得到图 9(b).可以看出:最终进入合并的局部聚类数量经过核心节点剪枝后与原来相比大量减少, 进入合并的聚类经过e剪枝也会变少(可以看出, 节点2不是节点7的ε邻居), 两者可以同时优化算法的时间和空间I/O次数.
|
Fig. 9 Core-Based and ε-based pruning 图 9 基于核心与ε的剪枝 |
算法3. 基于核心节点与边相似性的维度扩展与剪枝.
输入:顶点以及核心标记 < u isCore>, 边的两顶点以及边的相似性<u, v similarityuv>;
输出:顶点及其直接可达邻居集合构成的键值对 < u, set(Neighboru|isCore)>对.
1. Map1(key, value)
2. if value is T||value is F then
3. Emit < u, isCore>pairs
4. else
5. if similarityuv≥ε
6. Emit < u, v>pairs
7. Reduce1(key', values')
8. for value in values' do
9. if value is T||value is F then
10. isCore←value
11. else
12. valueList.add(value)
13.value"←key'|isCore
14.for val in valueList do
15. if key' < val do
16. key"←key'|val
17. else
18. key"←val|key
19.Emit < key", value">pairs
20.Map2(key, value)
21.Emit < key', value'>pairs
22.Reduce2(key', values')
23.for value in values' do
24. valueList.add(value)
25.Emit < valueList[1], valueList[0]> pairs
26.Emit < valueList[0], valueList[1]>pairs
27.Map3(key, value)
28.Emit < key, value>pairs
29.Reduce3(key', values')
30.for value in values' do
31. value"←value"+value+,
32.value"←value".length()-1
33.Emit < key, value">pairs
算法3包含了3个MapReduce程序, MapReduce过程如下.Map函数的输入为 < key, value>键值对, 该输入键值对有两种.其中一种是顶点以及isCore变量, 以 < u isCore>的形式给出; 另一种是边以及边的相似性, 以 < uv similarityuv>的形式给出.
本文基于MapReduce的结构聚类的主要创新在于设计了分布式计算相似性以及两种合并聚类的算法, 而维度扩展作为处理工具, 使得图中每个节点都附带核心信息, 在合并聚类中起到至关重要的作用, 使得聚类过程能够直接查看到当前节点是否为核心节点, 减少了冗杂的判断过程.其MapReduce过程如图 10所示, 通过图例中Reduce3的结果可以直观地看出:经过维度扩展和剪枝[12]后, 可以得到每个带有核心信息的节点及其结构可达的邻居.
|
Fig. 10 Dimension extension in MapReduce 图 10 维度扩展的MapReduce过程 |
3.3 基于MapReduce对分支进行结构聚类
由算法3, 我们可以得到每个节点及其全部ε邻居[13], 图中每个节点都是一个元组, 以(u|isCore)的形式存在.我们可以通过对图中核心节点及其直接可达邻居进行不断的迭代合并[14], 最终得到聚类.迭代合并的停止条件是当前聚类不能加入新的元素, 即不能够再继续与其他聚类合并.
过程见算法4:Map阶段在可达点中(初始集合里是直接可达邻居)找出是核心的节点, 将可达邻居中所有核心v作为key', 将当前可达邻居构成的集合Cu作为value'输出.在Reduce阶段, 对相同节点的不同聚类进行合并, 迭代得到最终聚类.
算法4. General Union.
输入:维度扩展后的顶点u及其直接可达邻居的初级聚类Cu;
输出:聚类.
1. Map(u, Cu)
2. while v∈Cu do
3. if v.isCoreisTrue then
4. Emit < v, Cu pairs
5. Reduce(u, {C1….Cn})
6. C←Merge(C1….Cn)
7. Emit < umin, C>
MapReduce聚类原理如图 11所示, 本文给出聚类的核心, 算法过程需要用到两个MapReduc[15], 但第2个MapReduce只是简单的去重[16]过程, 具体不给出.
|
Fig. 11 The process of general union 图 11 General union过程 |
算法4是一般的局部聚类合并[17]算法, 同时作为算法5的基准实验, 在实验结果图中也可以看出两种算法的性能差异.观察算法4可以发现:Map阶段每次都输出了核心节点及当前聚类的所有元素, 导致了IO次数[18]快速增长, 可以考虑使用最小编号的核心节点作为当前局部聚类的标记, 从而对算法4进行优化.具体如下.
首先, Map阶段, 我们在局部聚类中找出是核心的节点, 并且标注最小的核心, 将所有核心分别作为key, 最小核心作为value构造成键值对输出.同时, 以最小核心为key, 将当前局部聚类集合Cu作为value构造成键值对输出, MapReduce框架会将同一个key的键值对分到同一个reduce; 然后, 在Reduce阶段对相同节点的不同聚类进行合并; 最后, 查看迭代条件, 是否需要迭代, 得到最终聚类.
基于上述步骤可以看出:在两个分别以u, v标记的局部聚类里, 假如局部聚类Cu, Cv可以合并, Cu中必存在一点vmin, vmin也在Cv中, 利用vmin可以将两个聚类联系在一起, 合并过程见算法5, 图示过程如图 12所示, 迭代条件与算法4相同.
|
Fig. 12 Base min_coremerge subclusters 图 12 最小核局部聚类 |
算法5. Base Min_Core Union.
输入:维度扩展后的顶点u及其直接可达邻居的初级聚类Cu, 已知Neighbor[u];
输出:聚类.
1. Map(u, Cu)
2. vmin←v|v∈Cu∧v.isCoreisTrue
3. while v∈Neighbor[u] do
4. if v.isCoreisTrue then
5. Emit < v, vmin>pairs
6. Emit < vmin, Cu>pairs
7. Reduce(u, {C1….Cn})
8. C←Merge(C1….Cn)
9. Emit < u, C>
算法4、算法5中的Merge(C1…Cn)函数是合并可以合并的两个局部聚类函数, 本质上是一个集合的并[19]操作, 集合元素类型是点及其核心属性构成的元组.算法5中, Neighbor[u]数组表示u的可达邻居节点.合并函数的具体过程见算法6.
算法6. Merge SubCluster.
输入:维度扩展后的顶点u及其直接可达邻居的初级聚类Cu, 已知Neighbor[u];
输出:聚类C.
1. Merge(C1….Cn)
2. for i=0→n do
3. for c in Ci
4. if C contains c do
5. continue
6. else
7. C.add(c)
8. return C
4 实验与结果在已搭建的Hadoop分布式集群上, 使用本文提出的算法构建了一种面向无向图[20]的结构聚类模型, 并且在4个真实的数据集上(Skitter, Pokec, LiveJournal和Com-Orkut)上测试本文提出的方法.
4.1 实验平台与实验数据集实验环境为8台服务器构成的Hadoop集群, 1个master, 7个slaver, 每台服务器有两个CPU, CPU配置参数为:Intel(R) Xeon(R) CPU E5-2620 v3@2.40GHz, 每个CPU有6个核, 共12个核, 因此, 集群一共有96个核.实验过程中, 我们可以根据集群核数调整Reduce个数.单台服务器有32GB的内存, 统一安装Linux ubuntu16.04 64位操作系统.
实验数据集来源于斯坦福大学的公开数据集.数据的详细信息见表 1, 从4个数据集的边数可以看出, 实验数据具有一定的梯度性[21].
|
Table 1 Experimental data set and its vertex number and edge number 表 1 实验数据集及其顶点数和边数 |
4.2 实验结果及分析
实验采用4个数据集, 相似性ε和ε邻居数μ这两个参数分别取(0.4, 3)和(0.6, 6), 实验收集得到8个实验结果图如图 13所示.
|
Fig. 13 Efficiency comparison varying number of reduce 图 13 不同reduce数量运行效率对比 |
在图 13的实验结果中:前4个结果图采用了统一的ε和μ, 取值(0.6, 6), 后4个结果图取值(0.4, 3), 并且让reduce个数线性增加(12, 24, 36, 48, 60)来观察实验结果.这里不需要设置Map个数, Map个数是Hadoop集群根据数据集大小自动进行分配.
● 观察1.单独观察图 13每个实验结果可以发现:当数据集不变时, reduce个数增加, 算法的运行时间大致呈线性降低;
● 观察2.根据实验结果可以发现, 算法5(Base Min_Core Union)比算法4(General Union)的合并效率高;
● 观察4.ε和μ的取值越大, 剪枝效率越高.
5 总结为了解决图结构聚类算法的可扩展性问题, 本文提出一种基于MapReduce的结构聚类算法MRSCAN.具体地, 本文设计了一套计算核心节点以及两种有效的合并聚类的MapReduce算法.最后, 在多个真实的大规模图数据集上进行测试, 实验结果验证了本文算法的正确性、有效性以及可扩展能力.未来的工作包括:将我们实现的算法推广至其他的分布式计算框架, 例如Pregel[22]计算框架.
| [1] |
Mayer-SchoSnberger V, Cukier K, Wrote; Zhou T, et al. Trans. Big Data: A Revolution That Will Transform How We Live, Work, and Think. John Murray, 2013(in Chinese). |
| [2] |
Shvachko K, Kuang H, Radia S, Chansler R. The hadoop distributed file system. In:Proc. of the IEEE Symp. on MASS Storage Systems and Technologies. IEEE Computer Society, 2010: 1–10.
[doi:10.1109/MSST.2010.5496972] |
| [3] |
Shiokawa H, Fujiwara Y, Onizuka M. SCAN++:Efficient algorithm for finding clusters, hubs and outliers on large-scale graphs. Proc. of the VLDB Endowment, 2015.
[doi:10.14778/2809974.2809980] |
| [4] |
Chang L, Li W, Qin L, Zhang W. pSCAN:Fast and exact structural graph clustering. IEEE Trans. on Knowledge & Data Engineering, 2017, 29(2): 387–401.
[doi:10.1109/TKDE.2016.2618795] |
| [5] |
Li JJ, Cui J, Wang D, Yan L, Huang YS. Survey of MapReduce parallel programming model. Acta Electronic Journal, 2011, 39(11): 2635–2642(in Chinese with English abstract).
http://manu57.magtech.com.cn/Jwk_dzxb/CN/abstract/abstract6270.shtml |
| [6] |
Wang F, Lei BH. Model analysis of hadoop distributed file system. Telecommunications Science, 2010, 26(12): 95–99(in Chinese with English abstract).
[doi:10.3969/j.issn.1000-0801.2010.12.019] |
| [7] |
Chen F, Kodialam M, Lakshman TV. Joint scheduling of processing and Shuffle phases in MapReduce systems. In:Proc. of the IEEE INFOCOM. IEEE, 2012: 1143–1151.
[doi:10.1109/INFCOM.2012.6195473] |
| [8] |
Xu X, Yuruk N, Feng Z, Schweiger TAJ. SCAN: A structural clustering algorithm for networks. In: Proc. of the ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. ACM Press, 2007. 824-833. [doi: 10.1145/1281192.1281280] |
| [9] |
Zhou FF, Li JC, Huang W, Wang JW, Zhao Y. Based on dimension expansion Radviz visual clustering analysis method. Ruan Jian Xue Bao/Journal of Software, 2016, 27(5): 1127–1139(in Chinese with English abstract).
http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?file_no=4951&flag=1 [doi:10.13328/j.cnki.jos.004951] |
| [10] |
Guo QK. Study on connection method based on MapReduce[Ph. D. Thesis]. Jilin University, 2014(in Chinese with English abstract). |
| [11] |
Cohen J. Graph twiddling in a MapReduce world. Computing in Science & Engineering, 2009, 11(4): 29–41.
[doi:10.1109/MCSE.2009.120] |
| [12] |
Wang HY, Zhou L. Study on the maximum mission problem based on divide, prune and ant colony algorithm. Journal of Hefei Teachers College, 2011, 29(3): 59–62(in Chinese with English abstract).
[doi:10.3969/j.issn.1674-2273.2011.03.020] |
| [13] |
Qin L, Yu J X, Chang L, Cheng H, Zhang C, Lin XM. Scalable big graph processing in MapReduce. In:Proc. of the SIGMOD., 2014: 827–838.
[doi:10.1145/2588555.2593661] |
| [14] |
Feng XJ. Research on iterative distributed data processing based on MapReduce[Ph. D. Thesis]. Shandong University, 2013(in Chinese with English abstract). |
| [15] |
Liu T, Wu SH, Qiang Y. Task scheduling algorithm for multiple MapReduce jobs. Microelectronics & Computer, 2013, 30(12): 156–159(in Chinese with English abstract).
http://www.chinacloud.cn/upload/2014-06/14060509076490.pdf |
| [16] |
Gao SL. Research on Web page parallel de-emphasis algorithm based on MapReduce framework. Heilongjiang Science, 2010, 1(5): 13–18(in Chinese with English abstract).
http://www.cnki.com.cn/Article/CJFDTotal-HELJ201005007.htm |
| [17] |
Que X, Wang Y, Xu C, Yu WK. Hierarchical merge for scalable MapReduce. In:Proc. of the Workshop on Management of Big Data Systems., 2012: 1–6.
[doi:10.1145/2378356.2378358] |
| [18] |
Tiwari N, Sarkar S, Indrawan-Santiago M, Bellur U. Improving energy efficiency of IO-intensive MapReduce jobs. In:Proc. of the Int'l Conf., 2015: 1–4.
[doi:10.1145/2684464.2684484] |
| [19] |
Zhang X. Design of DBSCAN algorithm based on query and search. Journal of Yili Normal University:Natural Science Edition, 2014, 8(4): 62–65(in Chinese with English abstract).
[doi:10.3969/j.issn.1673-999X.2014.04.014] |
| [20] |
Ma J, Iwama K, Ma SH. Search for parallel algorithm in loop of undirected graph. Ruan Jian Xue Bao/Journal of Software, 1997, 18(6): 475–480(in Chinese with English abstract).
http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?file_no=19970611&flag=1 |
| [21] |
Hou ZL, Wei XH, Huang DN, Xu S. Application of parallel computing and its performance analysis in gravity totally gradient data inversion. Applied Geophysics, 2015, 12(3): 292–302.
[doi:10.1007/s11770-015-0495-z] |
| [22] |
Malewicz G, Austern MH, Bik AJC, Dehnert JC, Horn I, Leiser N, Czajkowski G. Pregel: A system for large-scale graph processing. In: Proc. of the ACM SIGMOD Int'l Conf. on Management of Data. ACM Press, 2010. 135-146. [doi: 10.1145/1582716.1582723] |
| [1] |
Mayer-Schonborger V, Cukier K, 著; 周涛, 等, 译.大数据时代:生活、工作与思维的大变革.杭州:浙江人民出版社, 2013.
|
| [5] |
李建江, 崔健, 王聃, 严林, 黄义双. MapReduce并行编程模型研究综述. 电子学报, 2011, 39(11): 2635–2642.
http://manu57.magtech.com.cn/Jwk_dzxb/CN/abstract/abstract6270.shtml
|
| [6] |
王峰, 雷葆华. Hadoop分布式文件系统的模型分析. 电信科学, 2010, 26(12): 95–99.
[doi:10.3969/j.issn.1000-0801.2010.12.019]
|
| [9] |
周芳芳, 李俊材, 黄伟, 王俊韡, 赵颖. 基于维度扩展的Radviz可视化聚类分析方法. 软件学报, 2016, 27(5): 1127–1139.
http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?file_no=4951&flag=1 [doi:10.13328/j.cnki.jos.004951]
|
| [10] |
郭骐恺. 基于MapReduce的连接方法研究[博士学位论文]. 长春: 吉林大学, 2014.
|
| [12] |
王会颖, 周琳. 基于分治、剪枝和蚁群算法求解最大团问题. 合肥师范学院学报, 2011, 29(3): 59–62.
[doi:10.3969/j.issn.1674-2273.2011.03.020]
|
| [14] |
冯新建. 基于MapReduce的迭代型分布式数据处理研究[博士学位论文]. 济南: 山东大学, 2013.
|
| [15] |
刘涛, 武淑红, 强彦. 用于多个MapReduce作业的任务调度算法. 微电子学与计算机, 2013, 30(12): 156–159.
http://www.chinacloud.cn/upload/2014-06/14060509076490.pdf
|
| [16] |
高殊丽. 基于MapReduce框架的网页并行去重算法研究. 黑龙江科学, 2010, 1(5): 13–18.
http://www.cnki.com.cn/Article/CJFDTotal-HELJ201005007.htm
|
| [19] |
张晓. 基于并查集的DBSCAN算法设计. 伊犁师范学院学报:自然科学版, 2014, 8(4): 62–65.
[doi:10.3969/j.issn.1673-999X.2014.04.014]
|
| [20] |
马军, 岩间一雄, 马绍汉. 寻找无向图中回路的并行算法. 软件学报, 1997, 18(6): 475–480.
http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?file_no=19970611&flag=1
|