六度空间-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);
}