[科普中国]-在线社交网络节点间相似性-

一、定义

在线社交网络节点间相似性，描述了在线社交网络用户之间的相似程度，根据不同的需求和定义，可以用相应的指标来进行度量，是在线社交网络分析研究的基础。

二、基于网络半结构信息定义节点相似性1. 基于共同邻居数的CN指标从网络拓扑结构角度出发，考虑两个节点的共同邻居数即common neighbors（CN）1，是基于网络半结构信息定义相似度的最简单的方法。共同邻居数越大，说明两个节点越相似，越有可能在同一社团。

其他6种规范化的指标在 CN 指标的基础上增加节点度的影响，便得到其他6 种规范的相似性指标。

（1）Salton 指标2

又称为余弦相似性，其定义方式是两个节点共同邻居数比上他们各自节点度之积的平方根。

（2）Jaccard 指标3

以Jaccard 的命名的相似度指标，其定义方式是两个顶点共同邻居数比上他们的所有邻居数之和。

（3）Sørenson 指标4

该指标用二倍两节点的共同邻居数比上他们的度之和得到。

（4）大度节点有利指标（hub promoted index,HPI）5

两个节点共同邻居数比上他们中较小节点度，因此大度节点与其他节点之间更容易具有高的相似性。

（5）大度节点不利指标（hub depressed index,HDI）6

与 HPI 相似，分母取两端节点度的最大值得到。

（6）LHN-I 指标7

两个顶点共同邻居数比上他们度之积。

三、基于网络结构信息定义节点相似性基于网络结构信息定义的方法中常见的有Adamic-Adar Index（AA 指标）和Resource allocaion Index (RA 指标)。它们都考虑了共同邻居的度信息，并且度小的共同邻居节点的贡献大于度大的共同邻居节点的。而两者只是在赋予节点权重上存在差异。对于两个节点来说，他们的每一个共同邻居对他们两者关系的强弱的贡献程度是不一样的8。

Adamic-Adar 指标Adamic-Adar9 简称AA，该指标根据共同邻居的节点的度给每个节点赋予一个权重值，即为每个节点的度的对数分之一。然后把节点对的所有共同邻居的权重值相加，其和作为该节点对的相似度值。
Resource Allocation 指标与 AA 指标定义很相似，Resource Allocation（RA）6指标假设网络中每一个节点都有一定的资源，没有直接相连的两个节点之间通过共同邻居作为媒介传递资源。每个节点都将自己的资源平均分配给它所有邻居。把此时目标节点接受到的资源数定义为这两个节点的相似度。

四、采用动力学方式定义节点相似性典型采用动力学方式定义节点相似度的方法是基于随机游走过程而定义的相似度，它包括平均通勤时间、Cos+指标、有重启的随机游走、SimRank 指标、局部随机游走指标等等。

基于网络全局随机游走的相似性指标基于网络全局随机游走的相似性指标有平均通勤时间、Cos+指标、有重启的随机游走、SimRank 指标。比较简单的几种方法有：

（1）平均通勤时间（average commute time, ACT）10

（2）基于随机游走的余弦相似性（Cos+）11

基于网络局部随机游走的相似性指标基于网络局部随机游走的相似性指标（local random，LRW12），考虑了有限步数的随机游走过程（通常选择的步数与网络的平均最短距离有关），其计算复杂度远远比全局随机游走的指标要低很多，运用于计算大规模网络的节点间相似性具有非常明显的优势。