基于GitHub用户数据使用Greenplum中MADlib进行PageRank算法运算

GitHub是著名的代码共享平台,来自全球的开发者在GitHub成千上万的项目中协作开发,贡献代码。Github中有哪些明星项目,谁又是明星开发者?能不能基于我所关注的项目,推荐更多我感兴趣的项目?

为了回答以上问题,我们基于GitHubArchive网站所提供的自2015年至今的用户操作数据(events),通过MADlib PageRank算法分析和寻找这些权威的项目和开发者。 用户操作数据包含eventID、类型、开发者(people)和项目(repo)以及网址等具体信息。Event代表一个开发者在Github某个项目中的操作,可以是创建、点赞、提交PR、 添加评论、提交代码等等。我们选取其中三种类型的event来打分计算权威值,并进一步构建PageRank算法的边。三种event类型分别是:

1. pushEvent,这代表的是一个成功的对于一个repo的贡献,这将生成人对于repo做贡献提高repo分数的边和人因为对于repo做出贡献本身分的分数的边;
2. pullRequestEvent的本质逻辑和pushEvent类似,然而这个需要另外的review,所以虽然也有加分但加分更少;
3. watchEvent,这是一个单纯的开发者对于一个repo的喜爱,这是一个单向的开发者对于repo传达分数的边。

如下是一个event的源代码格式的例子:

{"id":"2489665828","type":"PushEvent","actor":{"id":1699414,"login":"floooh","gravatar_id":"","url":"https://api.github.com/users/floooh","avatar_url":"https://avatars.githubusercontent.com/u/1699414?"},
"repo":{"id":28096970,"name":"floooh/fips-hello-dep2","url":"https://api.github.com/repos/floooh/fips-hello-dep2"}

基于以上数据,我们应用MADlib的PageRank算法分析得到“权威值”排名前一百的开发者和项目的具体操作步骤如下,
步骤一:数据下载 (Data Load)
步骤二:数据清理 (Data Cleaning)
步骤三:数据分析 (Data Analysis)
步骤四:结果展示 (Result)

步骤一:GiHubArchive将用户的活动数据,以小时为单位存储在网上。用户可以根据链接来进行各个小时的数据的下载。原先的计划是用循环来执行每小时的下载命令。由于数据量过大,这么做下载速度过慢。我们在谷歌云在订阅大虚拟机,多线程同时下载不同时间段的数据。然后在虚拟机中对数据进行整合过滤,再下载到本地机器上。

步骤二:下载下来的数据也有超过10GB的大小,对于我们单机的MADlib而言,信息处理量太大。并且我们需要的不是一个操作数据,而是people和repo之间的关系。所以我们不仅要读取数据,也要对读取完的数据进行解读,生成节点表(node table)和关系表 (edge table)。但是我们在通过程序(Java, Python)对数据进行处理时发现,由于node过多,在当Java占用内存达到4.2GB之后,电脑运算能力断崖式下滑,无法完成对于所有数据的处理。于是我们选择先对于每个node出现的次数进行统计,最后设定一个阈值。低于阈值出现次数的node将不被保存。此举是为了过滤掉那些贡献数较少的用户和repo。同时我们根据不同的events对于每个node进行打分,只有分数高于一定阈值的node和与之相关的edge才会被存在生成的node和edge的表里。这样我们以2.6GB左右的内存占有量完成了2.55亿行数据的处理。最后筛选留下了8311个people的node和7639个repo的node。

步骤三:根据步骤二所得的node和edge数据(node.txt, edge.txt), 使用如下sql语句创建两张名为node和edge的数据表,并将本地里的数据导入这两张表。然后使用MADlib自带的PageRank算法对数据表里的数据进行分析,最终使用select + from的语句将所得的排名前一百的people和repo数据提取出来。

create table node(index int, id int, name text, type text);
copy node from '/home/gpadmin/node.txt' delimiter ',';
create table edge(src int, dest int);
copy edge from '/home/gpadmin/edge.txt' delimiter ',';
select madlib.pagerank('node','id','edge','src=src,dest=dest','pagerank_out', 0.85, NULL,NULL,NULL, NULL);
select * from pagerank_out, node where pagerank_out.id = node.id order by pagerank DESC limit 100;

与此同时,我们也考虑了如何得到带有兴趣偏好的结果,比如用户想要搜索machine learning相关的排名前一百的repo,根据用户已有的偏好的repo(Theano,scikitLearn,spark),使用PageRank算法对原始数据进行分析,此处用到的sql语法如下,

drop table if exists node;
create table node(index int, id int, name text, type text);
copy vertex from '/home/gpadmin/node.txt' delimiter ',';
drop table if exists edge;
create table edge(src int, dest int);
copy edge from '/home/gpadmin/edge.txt' delimiter ',';
drop table if exists pagerank_out;
drop table if exists pagerank_out_summary;
select madlib.pagerank('node','id','edge','src=src,dest=dest','pagerank_out', 0.85, NULL,NULL,NULL, '{"17165658","2183193","843222"}');
select * from pagerank_out, node where pagerank_out.id = nored order by pagerank DESC limit 100;

步骤四:在获得排名前一百的开发者和repo基础上,我们通过创建Word Cloud的形式展示成果。这里所采用的是Andreas Mueller发布在Github网站上的Word Cloud Generator,链接如下,
https://github.com/amueller/word_cloud。我们将所得的排名一百数据通过sql指令生成TXT格式文件,并用Python程序根据排名对数据进行复制,使得排名较前的people或repo出现的次数更多,从而满足generator的编译逻辑。图片则是选用了PNG格式的漫威知名角色Spiderman和GitHub吉祥物Octocat,经过多次的图片和文字调试我们得到了如下的结果。左图是没有偏好设置的原始结果图,右图是我们加了兴趣编号(机器学习)的只包含高权威值的repo的结果图。PS: 我们结果中所有的大写字母是因为word cloud无法包含“-”,所以我们将其后面的首个字母改为大写,当然也包括本身就自带大写字母的情况。


特别鸣谢:感谢李阳先生(Jasper Li)对于我们在如何安装GreenPlum和MADlib提出了指导,也感谢张桓先生(Hubert Zhang)指导我们在算法上进行学习和在项目过程中给我们提供了宝贵的意见、建议和协助。最后感谢冯雷先生(Ray Feng)给我们提供了这一次宝贵的机会,也要感谢北京上海研究中心的各位同仁和前辈给予的关心和支持。

  • 文章发表于2018年7月27日,Pivotal中国研发中心实习报告
  • 作者介绍:
    
    缪思好(Sihao Miao),Math Department,
    University of California at San Diego 
    
    周莅滨(Libin Zhou),   Computer Science Department, 
    University of Wisconsin at Madison

发表评论

您的电子邮箱地址不会被公开。