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阶方程式之类的么..?

  这个估计还需要想一想.   

从药家鑫案想到的

  对于药家鑫案,最开始直觉上的伪善让我觉得不该死刑.

  但某群里某同学的一句话让我想了很多.
  "(不判死刑)效果就好像当年南京老太案件一样"

  确实,药的自述作案动机也承认,在交通肇事中"他不死就是我死"这种观念其实应该一直存在的.
  药案本身已经算是很有社会影响力的一个案件,不严惩,确实有可能会对社会造成不良影响.

  也就是说,死刑是必须的.

  然后,抛开这个案件,死刑是不是必须的呢?

  死刑的目的是起到震慑作用.
  换句话说,就是起到增加犯罪成本的作用.

  以故意杀人为例.
  对于受害人一方来说,无论执不执行死刑,从纯理性角度来说,只要罪犯受到制裁,收益都是正的.

  所以,从这个角度来说,死刑对于受害人一方来说,意义不是特别大.
  也许除了短期的一些情绪意思之外.
  当然,有可能长期收益.
  
  不管怎样,受害人一方,理性收益是正的.

  对于罪犯一方.
  不死刑的话,面临的成本是监禁和劳动.
  长期来说,损失在于服刑期间的损失,以及潜在的出狱后的损失.
  
  对于拥有平等观念和健全劳动体系的社会来说,出狱后的损失也许不大.
  但,如果固有偏见比较大,且劳动体系不健全的社会来说,出狱损失可能比服刑期更大.
  
  而死刑的话.
  对罪犯一方基本是短期损失.
  因为作为独立客体的存在已经终止了.

  唯一的特例是比如作为家庭唯一劳力的情况.
  这时候的损失就会牵涉到无谓的家庭.
  也就是引入了无谓损失.

  于是,对于罪犯一方.
  死刑不死刑,以及犯罪的成本问题,跟社会总体环境有关.
  即,家庭劳动力的普遍构成结构,社会观念,社会劳动体系构成有关.

  对于区别于受害人和罪犯的第三方,社会来说.
  如果以有罪论出发,即认为存在潜在犯罪的话,那么以上的成本计算就是有效的手段.
  毕竟,在有罪论的基本假设之下,成本的核算自然会被考虑到犯罪决策中.

  如果以无罪论处发,即承认犯罪都是偶发性的.
  那么就没有所谓的犯罪预算了.
  
  在这种情况下,就应该不启用死刑了.
  毕竟,基于犯罪是偶发性的假设,也就是犯罪是没有必然性的,死刑的惩罚也就没有意义了.

  于是,综上,如果死刑要有意义的话,需要
  1.有罪假设,即存在潜在的犯罪分子.
  2.家庭劳动力结构比较单一,或者社会偏见小且劳动就业体系完备的社会.

  这似乎是一个有违直觉的谬论.
  如果以贵国的社会情况来说的话,似乎更不适合以死刑来作为震摄手段.
  而是一个中长期的监禁刑罚?

  而传说中的美好的基于有罪假设的部分西方社会,则似乎更适合于启用死刑?  

  于是,回到药家鑫一案来说,似乎死刑并不是最好的处理方式.

  当然,药案目前的发展已经脱离的纯粹刑事案件的范畴了.
  
  CCAV和有关部门错误的舆论引导,已经把它变成李刚案的后续.
  于是,对于李刚案的不满,群众和媒体们只能通过向药案施压的方式发泄.

  这已经不是法律或者其他足够纯粹的问题了.
   
  这已经是一个社会矛盾驱动下的情绪性对抗了.

  所以,药家鑫只能死.
  不然,下一个药家鑫会被要求死的更惨.