SocialGraph的一些计算

  一直想看看实际的social graph是如何的.
  或者说六度空间在实际中到底是到达一个什么样的量.

  毕竟六度这个东西是基于一个纯数学上的假设的演算.
  即,每个人有固定数目的关系,并隐性假设了所有人都是相互联通的.

  实际情况可能是,一个群体"蔓延"到一定程度上之后,就再也无法扩展了.
  实际的例子是,一个与世隔绝的生活群体.
  或者说未发现的人类聚积地等.

  即使在简化地多的social networ里,也可能存在大量的鼓励点.
  极端的特例就是一个用户,没有任何好友.
  这就构成了纯粹的孤立点.

  于是,对于social graph,首先要确定的这个graph的连通性如何.
  或者说覆盖率如何.

  对于给定的一组好友关系,如何确定是不是一个连通图呢?
  
  换个思路,如果是一个连通图,那么就意味这任意两点之间存在着一条路径,使得这两点是连通的.
  
  推广一下就是,在一个连通图里,对于一个给定的点,其他所有点都存在一条路径使之到达这个给定点.
  也就是,一个graph可以退化为一个tree.

  回到最初的问题.
  即,对于给定一组形如:
  peer | friend_1,friend_2
  的输入数据,其中peer表示一个节点,friend_N表示这个节点的好友.
  如何从这个graph里过滤出一个sub graph,使得这个sub graph是连通图呢?

  前面提到,连通图的一个充要条件是它可以退化为一个tree. 
  于是,要做的就是把这组数据生成一个尽可能大的tree.

  一个直接的思路是,把id号最小的peer作为tree的root节点,然后往下爬.

  另一个思路是让每个节点自己聚集起来.
  即,每个节点寻找自己能够达到的id最小的节点.
  这样的好处在于,即使原来的graph不是连通的,但是迭代结束后,也能得到一个cluster了的结果.
  即,几个独立的互不连通的grpah.每组graph有着以graph中最小id为root的tree.

  那么,具体怎么做呢?
  其实是类似路由广播的思路.
  对于每一个节点peer,在每一次迭代开始前,都存在一个可以达到的最远节点parent.
  
  比如,在第一轮迭代开始前,这个peer可以达到的最远节点就是friend中id号最小的(包括自身在内的friend)

  于是,在每一轮迭代开始的时候,把当前的parent广播给friends就可以了.
  同时,由于这个peer同时也是被人的friend,所以,自然会收到来自friend的广播.
  在这一轮迭代结束前,该peer根据收到的广播和原来的parent比较,并从中选出最小的id的作为新的parent,进入下一个迭代.
  这样,当所有节点都不在更新parent的时候,就代表tree的生成结束了.

  用这样的思路对一个有大概4000w个peer的graph跑hadoopjob,大概是7轮左右就停下来了.
  结果是有大概存在12000个互不联通的graphtree.
  看上去碎片化很严重?
  
  其实有将近4000w用户是在同一个tree下面的.
  其余的tree都是最多只有几百人小group.   
  99.27%的人都是可以回溯到同一个root节点的.

  也就是说,虽然social graph不是完全连通的,但是基于这个样本的结果,也大致可以认为是连通的.
  
  基于这个结果,就开始考虑,在去除了那些不连通的部分之后,在身下的graph中,任意两点间,最多需要经过多少个中间节点才能到达彼此.
  也就是六度空间中的"度"数在一个具体的样本中会是多少?

  理论上说,这是一个寻找一个连通图中,给定所有任意两点间的最短路径的集合,寻找这个集合的最大值.
  
  按照前面广播的思路,可以对任一给定点,算出其到其他所有点的最短路径,然后取最大值.
  扩展开,把这个过程迭代,应用的所有点之后就能得出这个六度空间的度数.
  
  但这似乎只是理论上可行.

  用前面的tree的思路的话.
  算出tree的深度,可以得到这个度数的下限.
 
  即,给定一个tree,理论上的最短路径的最大值就是tree的depth*2.即两个最底层节点之间的通过root才能互通的情况.
  这是这个度数的理论上限.
  而且是以当前tree的root为特例的上限.

  实际情况可能会更复杂.
  所以这个思路意义不是很大.

  一个模糊的直觉是,可以把这个不要退化为tree.
  直接是graph,那么这个graph如果存在一个高阶/多维的数学模型的话,那么是否可以让他低纬投影之类的.
  这样,就能退化成算distance或者取值区间范围之类的问题了.

  比如对于一个特定的样本,对于peer本身,必然存在一个最大的friend数目上限N.
  也就是说,也许可以把它描述为N维空间或者N阶方程式之类的么..?

  这个估计还需要想一想.