MapReduce统计三角形数量

实验四 图的三角形计数

组号： 2015st30

组长：吴少博 MF1533055 组员： 王勇 MF1533054 刘拨杰 MF1533029

一、 Map和Reduce的设计思路

1、 逻辑一：IF (A->B) OR (B->A) THEN A-B： 设计思路：（1）为了统计三角形的数量，首先应该知道哪些点之间有边相连，所以会先读取输入文件的每一行，将点与点之间相连。然后，为了统计三角形数量，我们的基本思路是，对于一个顶点A，如果AB和AC存在，那么我们就去看BC存不存在，如果BC存在，则构成一个三角形。这样的“BC”有多少个，三角形就有多少。而AB，AC很容易以A为key的reduce的value中找到，所以基于此，我们的逻辑1的三角形个数统计算法设计如下：

算法设计：本程序总共包含3个mapreduce程序。第一个mapreduce程序：map函数具体操作为，读取本地数据，获取每条边，构成边的两个node按字典顺序排序构成key（smallnode-bignode）,value为“#”，构成中间结果(如果两个node值相等，那么表示这是一条自己指向自己的边，那么不做任何操作)，

reduce函数去掉重复的边，将去重的所有边输出到本地文件中，

第二个mapreduce程序：map函数的具体操作为，读取文件，获取上一步生成的所有边，每条边较小的节点为key值（smallnode），较大边为value值（bignode），构成中间结果，

Reduce阶段：每个reduce函数，value的值其实是以key为顶点的所有邻居节点，例如key是“A”，value里的值都是与“A”相连的所有顶点。对于其中两点，不妨设为“B”，“C”，那么，显然，“AB”和“AC”已经存在，我们只需要看“BC”是否存在，若“BC”存在，则构成三角形，若“BC”不存在，则不构成。所以我们在Reduce阶段输出两种类型的键值对。首先，对于像“AB”，“AC”这样的边，即以key为一个顶点，value数组里的一个值为另一个顶点构成的边，以这样的边为新的key,字母”e”为新的value,输出到文件，”e”表明图中存在这样的边。

而对于原来的value里的值，我们两两之间组合成一条边，因为若这样的边存在，则构成三角形。所以，这样的边是我们所需要的，所以我们以这样的边为新的key，“n”为新的value,输出。表明这样的边是我们所需要的。

第三个mapreduce程序：Map阶段：map函数获取上一步构成的所有key-value值，构成中间结果数据，

Reduce阶段：reduce函数，key值为边（smallnode-bignode），遍历values，我们看values里的内容，如果values里的存在“e”,表明这条边存在，而如果values里存在“n”,则表示

这条边被“需要”用来构造三角形，“n”的个数就是三角形的个数。所以我们统计边的时候，一条边必须既存在，又被“需要”着，才能构成三角形，也就是说，value里必须既有“e”又有“n”,则“n”的数目是几三角形的总个数就加几，最后把所有的这些都相加，就可以得到总个数。

cleanup函数输出这个Reduce节点上统计的三角形的总个数。 2、 逻辑二：IF (A->B) AND (B->A) THEN A-B： 设计思路：（1）读取本地数据集，获取所有边；（2）将每条存在的边标记为存在，并将该边的反向标记为需要，即（node1-node2，e），（node2-node1，*）；（3）以每条边为key，遍历value值，若该边既存在又需要，则证明该边满足条件，为双向的。（4）通过上面的方法，统计三角形的个数。

算法设计：共包含六个mapreduce程序。

第一个mapreduce程序：去掉重复的边和自己指向自己的边。Map函数直接获取所有边，不再大小排序（因为这一次边是有向的），key（node1-node2），value（”#”），reduce函数去除重复边并将所有边写入到本地文件。

第二个mapreduce程序：map函数获取上一步的所有边，key（node1）-value（node2），构成中间结果数据，reduce函数读取中间结果数据，将每条边标记为存在边输出到本地，将每条边的反向标记为需要的边输出到本地，即key（node1-node2）-value（“@“）， key（node2-node1）-value（”*”）。

第三个mapreduce程序：获取所有双向的边。map函数获取上一步处理的数据，reduce函数以每条边为key值，若values中既包含“e“，有包含“*“，则说明该边既存在，又被“需要”着，表明这条边的反向边也存在，这条边为双向边，故满足条件（IF (A->B) AND (B->A) THEN A-B），以该边两节点大小排序构成key（smallnode）-value（bignode）对，写入本地。

第四、五、六个mapreduce程序：以上程序已获取所有满足条件的边，后面的做法和逻辑一的三个mapreduce 是一样的，故不再赘述。

二、 统计的三角形的个数

IF (A->B) OR (B->A) THEN A-B 数据集 Twitter Google+

IF (A->B) AND (B->A) THEN A-B 数据集 三角形个数 Driver程序在集群上的运行三角形个数 13082506 1073677742 Driver程序在集群上的运行时间 3min6s 1h45min43s 时间 Twitter Google+ 1818304 27018510 4min6s 7min15s 三、 输出结果文件截图，文件在HDFS路径

文件输出的hdfs路径如下(我删除掉了中间的结果文件夹，只保留了最后一个job的输出)： /user/2015st30/GoogleOutput1 逻辑一(OR逻辑)谷歌数据集输出 /user/2015st30/GoogleOutput2 逻辑二(AND 逻辑)谷歌数据集输出 /user/2015st30/Twitter_1_Output 逻辑一 推特数据集输出 /user/2015st30/Twitter_S_Output 逻辑二 推特数据集输出 PS：这些结果我也进行了合并，并下载到了本地，一起打包上交。

由于设置的reduce个数的问题，所以输出结果需要将每个reduce的结果累加，才会得到最终的结果。

Twitter数据集：

IF (A->B) OR (B->A) THEN A-B

IF (A->B) AND (B->A) THEN A-B

数据集：

IF (A->B) OR (B->A) THEN A-B

Google+

IF (A->B) AND (B->A) THEN A-B

系统运行性能的分析

四、程序运行总体上性能比较让我满意，Twitter数据集运行逻辑一和逻辑二，总时间分别为3min 6s和4min 6s,这可能与我的算法一开始对数据进行了去除重复边的操作，以及在map之后设置了combiner有关。对于Google数据集，运行逻辑一和逻辑二的时间分别为1h45min43s以及7min15s,能够在三小时之内跑完让我很惊讶。总体感觉还是可以的，也可能与我在晚上12点多开始跑程序，集群上当时只有我一个作业有关。

五、 性能、扩展性等方面存在的不足和可能的改进之处

性能方面的不足之处应该就是感觉算法还能再优化，可以更快的的跑完Google数据集。

扩展性方面，因为本人的代码风格问题，感觉程序的可扩展性方面还不是很好，以后要多注意变成规范，编程时就注意扩展性的问题。

六、 源代码、可执行程序JAR包、JAR包运行方式说明

源代码在打包上交的文件夹的code文件夹里，共两个java文件，triangle_count.java

是逻辑一，而Triangle_count2.java是逻辑二。

可执行的jar包也在文件夹中，为“Triangle_last.jar”

JAR包的运行方式如下： 推特数据集逻辑一：

hadoop jar Triangle_last.jar lab04.triangle_count

hdfs://master01:54310/data/tritter_graph_v2.txt Twitter_1_Output

推特数据集逻辑二：

hadoop jar Triangle_last.jar lab04.Triangle_count2

hdfs://master01:54310/data/tritter_graph_v2.txt Twitter_S_Output

Google数据集 逻辑一：

hadoop jar Triangle_last.jar lab04.triangle_count

hdfs://master01:54310/data/gplus_combined.unique.txt GoogleOutput1

Google数据集 逻辑二：

hadoop jar Triangle_last.jar lab04.Triangle_Count2

hdfs://master01:54310/data/gplus_combined.unique.txt GoogleOutput2

七、 WebUI执行报告

由于本次实验job数量较多，故我将WebUI执行报告的文件下载并保存为pdf文件，放入到了打包文件夹的“WebUI执行报告”文件夹中。

本文来源：https://www.bwwdw.com/article/hiz2.html