六度空间--Friends of my friend
个人博客：http://coolgo-zq.appspot.com/
?
?
前段时间，忽然想到做一个关于“六度空间”的应用-找出两个不认识人的联系。在自己经过一些准备以后，于是，故事开始了。
考虑到数据的敏感性，就不提供代码和数据的下载。在这里探讨一下，抛砖引玉，欢迎大家积极讨论。
?
“六度空间”理论：你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任何一个陌生人。
我们来假设一种场景：Z希望认识某个人X，但是到底采用什么方式去接近X呢。现在如果Z的好友F认识X的话，那么你可以通过F的关系，和X取得了正大光明的交往机会，然后从此一段美好的姻缘就此展开。(三者的关系：Z-->F-->X）
?
最初，我随意的看了一下几个sns的api，发现大多是对一个用户的好友列表有比较严格的控制，因此如果通过api的访问好友关系的话，会有个很大的弊端：需要用户授权。这样的话，在数据量很小的情况下，基本上就是个废品。这个时候，我又一次深刻的感受到了数据的重要性。
?
后来，发现rr网可以通过一种方式（下文详细展开）获得好友列表，因此就有了想法，想法之后就有了行动。
?
首先，要面对的第一个问题就是：在假设已经有了数据的情况下，如果找出两个不认识人之间的关系。先引入2个人X，Y。稍微分析一下，就会发现，好友关系图展开的话就是一张无向图。因此X，Y之间的关系问题就转化为：无向图中找出XY之间的最短路径。于是就考虑到了双向搜索，从X,Y两个人开始进行搜索。找出X的好友的集合SetX,同时找出Y的好友集合setY。setX，setY是否有交集，如果有的话，说明找出了他们之间的联系。如果没有，那么在把找出setX里面的人的好友，即X的好友的好友，同样找出setY。以此类推，直到找到发现两个存在交集。那么这些交集里面的人就是关键性人物了。找到这些人，XY的关系自然也就出来了。
以上是从算法方面考虑，本身并不复杂。
?
关于数据规模假设每个人有100个好友，那么每当把好友关系拓展一次，就上升2个数量级，这种指数级的增长太可怕。
因此必须对好友的范围进行控制，于是我打算把好友范围控制在自己的学校。我粗略的估计了一下，我们一届算是4k个人，然后算上研究生博士生，那么也大概在1w吧，然后在算上rr网的年龄，我推算rr网上我们学校的注册用户数可能在8w左右。8w的数据规模虽然不小，但是还是可以接受的。
进过我自己的测试：基本上下载量与有效数据的比例是:400:1,单个人(以200个好友来算)的数据量为2kb~以8万人来计算:有效数据量160mb,下载量达到了64gb。这个下载量还是挺恐怖的。但是还是硬着头皮做了下去。
最后从爬虫爬下来的数据来看，每个人在校内平均大概100个好友，总体人数在4.5w左右。有效数据在30mb左右。
?
接下来，就是具体的工作：
1.如何实现模拟登录?
2.如何获取好友列表?
3.如何本地存储个人信息?
?
1.模拟登录：通过对登陆协议的分析,有抓包工具抓到了post信息，然后发现rr网的登录模拟还是比较简单的。抓包的时候发现一个挺不错的工具，HttpAnalyzer，这个比wireshark好用一点。
在rr网登录过程中，只返回四个有效信息：email，password，origURL，domain。而且还是明文传输的。因此只要简单写一个登录方法，把这些值传过去就自然登录成功了。
?
2.获得好友列表：http：//friend.renren.com/GetFriendList.do?curpage=【页码】&id=【你需要找的id】
这个页码会返回一个此id的好友列表的页面，然后对这个页面提取有效信息就行了。
这是我的正则表达式
String regex = "<p class="avatar"><a href="http://www.renren.com/profile.do\\?id=[0-9]+"><img src="http://.+" alt="http://.+" /></a></p>";
值得一提的是，注意一下img 的src，里面的url的前缀不是每一个都相同的。我估计是rr网在升级的时候，一部分用户的头像还是取自老服务器，新用户在新服务器。
?
3.本地存储：我使用了json格式来储存，使用的是gson包，操作起来比较简单。为了减少本地信息量，我存储了四个信息：id,name,imgUrl,school,friends。
?
public class Person {private String id;private String name;private String school;private String imgUrl;private List<String> friends;}?然后把所有的person放到了一个hashMap<id,Person>里面了。这样方便通过id直接找到person对象。
?
在最初阶段，我以为数据存储会比较大，所以没有考虑存到同一个文件中。而是每个person存放到了一个文件，这样下来的话，一共有4w+个小文件，每个文件只有1k左右。
缺点：当进行查询的关系的时候，IO资源太可怕，每找一个好友就要进行一次IO，当进行双向搜索的时候，这样磁盘扛不住啊这样很蛋疼。
后来参考了Create Chen的做法，把所有的都存放到了同一个文件中。于是就像把所有的person在程序刚启动时就load到内存的hashMap<id,Person>中。
?
?
import java.io.BufferedReader;import java.io.File;import java.io.FileReader;import java.io.IOException;import java.util.HashMap;import java.util.LinkedList;import java.util.List;import java.util.Map;import java.util.Queue;import java.util.Scanner;import java.util.Vector;import com.google.gson.Gson;import com.google.gson.reflect.TypeToken;public class FFinder {public Gson gson = new Gson();private Map<String, Person> map;private int[] step = new int[50000];/** 记录v[i]记录的是到达person[i]的前一个节点。 */private Vector<Vector<String>> from = new Vector<Vector<String>>();private Queue<String> q1 = new LinkedList<String>();private Queue<String> q2 = new LinkedList<String>();/** 将person.id映射到step数值中 */private Map<String, String> idmap = new HashMap<String, String>();public void getRelation(String id1, String id2) throws IOException {System.out.println(map.get(id1).getName()+"-->"+map.get(id2).getName());init();q1.add(id1);from.add(new Vector<String>());from.get(0).add(id1);idmap.put(id1, String.valueOf(idmap.size()));step[0] = 1;q2.add(id2);from.get(1).add(id2);idmap.put(id2, String.valueOf(idmap.size()));step[1] = -1;// 是否交集boolean isMeet = false;Queue<String> join = new LinkedList<String>();while (!q1.isEmpty() && !q2.isEmpty()) {Queue<String> nextQ = new LinkedList<String>();isMeet = deepFindHead(join, nextQ);if (isMeet)break;q1 = nextQ;nextQ = null;nextQ = new LinkedList<String>();isMeet = deepFinderTail(join, nextQ);q2 = nextQ;}System.out.println("join=" + gson.toJson(join));}private void init() {step = new int[50000];from = new Vector<Vector<String>>();q1 = new LinkedList<String>();q2 = new LinkedList<String>();idmap = new HashMap<String, String>();/** * @param join * @param nextQ * @return */private boolean deepFinderTail(Queue<String> join, Queue<String> nextQ) {String cur;Person p;int curIdnum;while (!q2.isEmpty()) {cur = q2.poll();curIdnum = Integer.parseInt(idmap.get(cur));p = map.get(cur);List<String> friends = p.getFriends();for (String id : friends) {int idnum;if (idmap.containsKey(id)) {idnum = Integer.parseInt(idmap.get(id));/** * 说明已经到达过此人 如果step[idnum]为-，则说明是从id2出来的,continue; * 如果为+，则说明找到了双向搜索出现了交集。 */if (step[idnum] < 0)continue;else if (step[idnum] > 0) {// 找到交集isMeet = true;System.out.println("="+step[curIdnum]+"，通过"+(-2*step[curIdnum]-1));from.get(idnum).add(cur);join.add(id);}}idmap.put(id, String.valueOf(idmap.size()));idnum = idmap.size() - 1;step[idnum] = step[curIdnum] - 1;from.add(new Vector<String>());from.get(idnum).add(cur);if (!isMeet)nextQ.add(id);}return isMeet;private boolean deepFindHead(Queue<String> join, Queue<String> nextQ) {while (!q1.isEmpty()) {cur = q1.poll(); * 说明已经到达过此人 如果step[idnum]为正，则说明是从id1出来的,continue; * 如果为负数，则说明找到了双向搜索出现了交集。if (step[idnum] > 0)else if (step[idnum] < 0) {System.out.println("="+step[curIdnum]+"，通过"+(2*step[curIdnum]-2));step[idnum] = step[curIdnum] + 1;public Map<String, Person> loadData(String path) throws IOException {File f = new File(path);BufferedReader in = new BufferedReader(new FileReader(f));Map<String, Person> t = gson.fromJson(in.readLine(),new TypeToken<Map<String, Person>>() {}.getType());in.close();this.map = t;System.out.println("load ok!");return t;public static void main(String[] argv) throws IOException {Scanner scan = new Scanner(System.in);FFinder f = new FFinder();f.loadData("D:/1/allData_save.data");String id1, id2;while (true) {id1 = scan.next();id2 = scan.next();System.out.println(id1 + "-->" + id2);f.getRelation(id1, id2);}