关于本站
人大经济论坛-经管之家：分享大学、考研、论文、会计、留学、数据、经济学、金融学、管理学、统计学、博弈论、统计年鉴、行业分析包括等相关资源。
经管之家是国内活跃的在线教育咨询平台!
获取电子版《CDA一级教材》
完整电子版已上线CDA网校，累计已有10万+在读~ 教材严格按考试大纲编写，适合CDA考生备考，也适合业务及数据分析岗位的从业者提升自我。
TOP热门关键词
坛友互助群 |
扫码加入各岗位、行业、专业交流群 |
最近做了一个项目，要求找出二度人脉的一些关系，就好似新浪微博的“你可能感兴趣的人” 中，间接关注推荐；简单描述：即你关注的人中有N个人同时都关注了 XXX 。
在程序的实现上，其实我们要找的是：若 User1 follow了10个人 ｛User3，User4，User5，... ，User12｝记为集合UF1，那么 UF1中的这些人，他们也有follow的集合，分别是记为： UF3（User3 follow的人），UF4，UF5，...，UF12；而在这些集合肯定会有交集，而由最多集合求交产生的交集，就是我们要找的：感兴趣的人。
我在网上找了些，关于二度人脉算法的实现，大部分无非是通过广度搜索算法来查找，由于深度已经明确了2以内；这个算法其实很简单，第一步找到你关注的人；第二步找到这些人关注的人，最后找出第二步结果中出现频率最高的一个或多个人，即完成。
但如果有千万级别的用户，那在运算时，就肯定会把这些用户的follow 关系放到内存中，计算的时候依次查找；先说明下我没有明确的诊断对比，这样做的效果不一定就不如 基于hadoop实现的好；只是自己，想用hadoop实现下，最近也在学；若有不足的地方还请指点。
首先，我的初始数据是文件，每一行为一个follow 关系 ida+‘\t’+idb；表示 ida follow idb。其次，用了2个Map/Reduce任务。
Map/Reduce 1：找出 任意一个用户 的 follow 集合与 被 follow 的集合。如图所示：
http://static.oschina.net/uploads/space/2012/0827/231920_8Lp2_100580.jpg
代码如下：
Map任务： 输出时 key ：间接者 A 的ID ，value：follow 的人的ID 或 被follow的人的ID
01 | public void map(Text key, IntWritable values, Context context) throws IOException,InterruptedException{ |
[backcolor=rgb(248, 248, 248) !important]
02 | int value = values.get(); |
03 | //切分出两个用户id |
[backcolor=rgb(248, 248, 248) !important]
04 | String[] _key = Separator.CONNECTORS_Pattern.split(key.toString()); |
05 | if(_key.length ==2){ |
[backcolor=rgb(248, 248, 248) !important]
06 | //"f"前缀表示 follow；"b" 前缀表示 被follow |
07 | context.write(new Text(_key[0]), new Text("f"+_key[1])); |
[backcolor=rgb(248, 248, 248) !important]
08 | context.write(new Text(_key[1]), new Text("b"+_key[0])); |
09 |
[backcolor=rgb(248, 248, 248) !important]
10 |
11 | } |
[backcolor=rgb(248, 248, 248) !important]
12 | } |
Reduce任务： 输出时 key ：间接者 A 的ID ， value为 两个String，第一个而follow的所有人（用分割符分割），第二个为 被follow的人（同样分割）
01 | protected void reduce(Text key, Iterable<TextPair> pairs, Context context) |
[backcolor=rgb(248, 248, 248) !important]
02 | throws IOException,InterruptedException{ |
03 | StringBuilder first_follow = new StringBuilder(); |
[backcolor=rgb(248, 248, 248) !important]
04 | StringBuilder second_befollow = new StringBuilder(); |
05 |
[backcolor=rgb(248, 248, 248) !important]
06 | for(TextPair pair: pairs){ |
07 | String id = pair.getFirst().toString(); |
[backcolor=rgb(248, 248, 248) !important]
08 | String value = pair.getSecond().toString(); |
09 | if(id.startsWith("f")){ |
[backcolor=rgb(248, 248, 248) !important]
10 | first_follow.append(id.substring(1)).append(Separator.TABLE_String); |
11 | } else if(id.startsWith("b")){ |
[backcolor=rgb(248, 248, 248) !important]
12 | second_befollow.append(id.substring(1)).append(Separator.TABLE_String); |
13 | } |
[backcolor=rgb(248, 248, 248) !important]
14 | } |
15 |
[backcolor=rgb(248, 248, 248) !important]
16 | context.write(key, new TextPair(first_follow.toString(),second_befollow.toString())); |
17 | } |
其中Separator.TABLE_String为自定义的分隔符；TextPair为自定义的 Writable 类，让一个key可以对应两个value，且这两个value可区分。
Map/Reduce 2：在上一步关系中，若B follow A，而 A follow T ，则可以得出 T 为 B 的二度人脉，且 间接者为A ，于是找出 相同二度人脉的不同间接人。如图所示：
http://static.oschina.net/uploads/space/2012/0828/000046_p35h_100580.jpg
代码如下：
Map 任务：输出时 key 为 由两个String 记录的ID表示的 二度人脉关系，value 为 这个二度关系产生的间接人的ID
01 | public void map(Text key, TextPair values, Context context) throws IOException,InterruptedException{ |
[backcolor=rgb(248, 248, 248) !important]
02 | //Map<String, String> first_follow = new HashMap<String, String>(); |
03 | //Map<String, String> second_befollow = new HashMap<String, String>(); |
[backcolor=rgb(248, 248, 248) !important]
04 | //String _key = key.toString(); |
05 | String[] follow = values.getFirst().toString().split(Separator.TABLE_String); |
[backcolor=rgb(248, 248, 248) !important]
06 |
07 | String[] befollow = values.getSecond().toString().split(Separator.TABLE_String); |
[backcolor=rgb(248, 248, 248) !important]
08 |
09 | for(String f : follow){ |
[backcolor=rgb(248, 248, 248) !important]
10 | for(String b : befollow){ |
11 | //避免自己关注自己 |
[backcolor=rgb(248, 248, 248) !important]
12 | if(!f.equals(b)){ |
13 | context.write(new TextPair(f.getKey() ,b.getKey()), new Text(key)); |
[backcolor=rgb(248, 248, 248) !important]
14 | } |
15 | } |
[backcolor=rgb(248, 248, 248) !important]
16 | } |
17 | } |
Reduce任务：输出时 key 仍然为二度人脉关系， value 为所有间接人 的ID以逗号分割。
01 | protected void reduce(TextPair key, Iterable<Text> values, Context context) |
[backcolor=rgb(248, 248, 248) !important]
02 | throws IOException, InterruptedException { |
03 |
[backcolor=rgb(248, 248, 248) !important]
04 | StringBuilder resutl = new StringBuilder(); |
05 | for (Text text : values){ |
[backcolor=rgb(248, 248, 248) !important]
06 | resutl.append(text.toString()).append(","); |
07 | } |
[backcolor=rgb(248, 248, 248) !important]
08 |
09 | context.write(key, new Text(resutl.toString())); |
[backcolor=rgb(248, 248, 248) !important]
10 | } |
到这步，二度人脉关系基本已经挖掘出来，后续的处理就很简单了，当然也可以基于二度人脉挖掘三度，四度：）
原创博客，转载请注明：http://my.oschina.net/BreathL/blog/75112
免流量费下载资料----在经管之家app可以下载论坛上的所有资源，并且不额外收取下载高峰期的论坛币。
涵盖所有经管领域的优秀内容----覆盖经济、管理、金融投资、计量统计、数据分析、国贸、财会等专业的学习宝库，各类资料应有尽有。
来自五湖四海的经管达人----已经有上千万的经管人来到这里，你可以找到任何学科方向、有共同话题的朋友。
经管之家（原人大经济论坛），跨越高校的围墙，带你走进经管知识的新世界。
扫描下方二维码下载并注册APP
您可能感兴趣的文章
人气文章
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性，不作出任何保证或承若；
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
