网络残缺度:共同好友间可否两步到达?

less than 1 minute read

网络是由节点和关系构成的,而对于关系的描述是社会网络的关键。我们已经知道对于节点的网络特性可以从中心度、近度、介度、特征度(eigenvalue centrality)等方式描述。那么对于关系呢?最简单的就是直接关系的强度了。

关系强度(tie strength)

通常对于关系强度的测量是基于两个节点之间链接的权重来衡量的。并不是说关系的强度越高越好,也不是说越多的强关系就越好。例如,格兰诺维特的论文The strength of weak ties强调了弱关系的重要性。

共同好友(common friends

但是以直接的链接强度度量一对关系的强度显然过于简单。它忽略的网络中的三角形(triads):网络的局部传递性(transtivity)。关系的传递性是社会网络分析的一种重要观点。比如,朋友的朋友成为自己的朋友的可能性很高。这种关系的强度不只限于一模网络中。在传播学中有ABX模型,A和B是两个人,X是一种对象(信息、意见、创新等)。A和B是好朋友,A喜欢X,那么B喜欢X的可能性就提高。也就是爱朋友及朋友喜欢的东西,有点像爱屋及乌。

怎么抓住网络的传递性?找两个节点(一对关系)的共同好友!找到共同好友就抓住了网络中的三角形。存在的三角形数量就表明了传递性的程度。这种思路其实对于做共引(co-citation)分析的学者来说并不陌生。如果一篇论文同时引用了两篇论文,那么这两篇论文就存在一定的相似性。因此,找共同好友类似于找共引关系。

嵌入度(embededness

共同好友数量是判断两个人亲密程度的一个重要变量。如果共同好友的数量足够多,表明这两个人彼此深度的融入了对方的社会关系当中。基于这种思路,我们可以计算嵌入型。对于i和j两个人, $k_{i}$、$k_{j}$分别表示i和j的好友数量。$n_{ij}$表示其共同好友数量。那么,我们可以如下计算嵌入度:

残缺性(dispersion

残缺度(dispersion, 或译为分散度)是Lars Backstrom & Jon Kleinberg (2013) 为了识别Facebook中亲密关系而提出的度量。它同样是基于共同好友的,主要测量的是共同好友之间的链接缺失程度。

‘dispersion’ — the extent to which two people’s mutual friends are not themselves well-connected. Lars Backstrom & Jon Kleinberg (2013)

Lars Backstrom & Jon Kleinberg使用了脸书的数据发现,使用残缺度这个度量方式,可以非常准确识别诸如夫妻、男女朋友、恋爱关系。

如上图中,u和v两个人有a、b、c、d四个共同好友。残缺度主要考察在多大程度上,这些共同好友不能两步之内到达彼此。如果两个共同好友之间不存在直接连接,且也不存在(除去u和v之外的)共同好友,那么残缺度就增加1。

以C_{uv}来表示u和v的共同好友之间的链接,那么在上图中只有a、b之间和c、d之间存在链接。a-c, a-d, b-c, b-d四对节点之间既没有直接链接又没有共同好友(除去了u和v)。所以残缺度是4。

再举一个例子,如果u和v的共同好友b-c之间存在直接的链接。那么残缺度会是多大?如下图:

因为只有a-d之间没有办法在两步内到达彼此,所以残缺度是1。

当然了这种定义残缺度的方法是基于节点间的距离的。例如以$d_{s,t}$表示共同好友中任意两个节点s和t之间的距离。在这个初始的定义中,两步内不能到达算是关系残缺。那么我们可以将其扩展为3步内不能到达算残缺,或者n步能不能到达算残缺。不过根据Lars Backstrom & Jon Kleinberg的实验,两步不能到达是一个较好的基准。

如果浪漫关系的确可以由高残缺度刻画,那么说明兔子不吃窝边草在国外是存在的。太熟了下不去手的现象在国内也是存在的。记得一个笑话说:找男女朋友的时候都说找互补的,实际上找到的都是类似的!白富美总是跟高富帅在一起嘛。这应该是对的,人的收入、相貌、工作都是匹配的(match),从这个角度上讲的确是相似的。但至少从网路结构的角度来说,男女关系依然是互补的!

参考文献

Lars Backstrom & Jon Kleinberg (2013) Romantic Partnerships and the Dispersion of Social Ties: A Network Analysis of Relationship Status on Facebook.arXiv