复杂网络中的节点相似性

在机器学习领域，很多时候需要衡量两个对象的相似性，特别是在信息检索，模式匹配等方向上。一般情况下，相似性与距离是都是为了描述两个对象之间的某种性质。但在实际使用的时候，需要根据具体的情况来选择合适的相似度或者距离函数。

相似性与距离

首先，我们来看一下相似性函数的含义。对于两个对象 $x,y \in X,$ 相似性函数 $s:X\times X\rightarrow \mathbb{R}$ 是将 $X\times X$ 映射到实数域 $\mathbb{R}$ 的有界函数，i.e. 存在上下界使得 $s_{min}\leq s\leq s_{max},$ 它具有以下两个性质：

自反性： $s(x,x)=s_{max}$ 对于所有的 $x\in X$ 都成立；
对称性： $s(x,y)=s(y,x)$ 对于所有的 $x,y\in X$ 都成立；

一般情况下，不要求相似度函数具有三角不等式的性质。相似度越大，表示两个元素越相似；相似度越小，表示两个元素越不相似。

其次，我们来看一下距离函数的含义。对于两个对象 $x,y\in X,$ 距离函数 $d:X\times X\rightarrow \mathbb{R}^{+}\cup\{0\}$ 是将 $X\times X$ 映射到非负实数域的函数，它只存在下界 $0,$ 并不存在上界，它具有以下三个性质：

自反性： $d(x,x)=0$ 对于所有的 $x\in X$ 都成立；
对称性： $d(x,y)=d(y,x)$ 对于所有的 $x,y\in X$ 都成立；
三角不等式： $d(x,y)+d(y,z)\geq d(x,z)$ 对于所有的 $x,y,z\in X$ 都成立。

距离越小，表示两个元素越近；距离越大，表示两个元素越远。

相似度（Similarity）

对于欧式空间 $\mathbb{R}^{n}$ 中的两个点 $A=(a_{1},a_{2},\cdots,a_{n})$ 和 $B=(b_{1},b_{2},\cdots,b_{n})$ 而言，可以多种方法来描述它们之间的相似性。

余弦相似度（Cosine Similarity）

$\text{Cosine Similarity}(A,B)=\frac{A\cdot B}{||A||_{2}\cdot ||B||_{2}}=\frac{\sum_{i=1}^{n}a_{i}b_{i}}{\sqrt{\sum_{i=1}^{n}a_{i}^{2}}\cdot\sqrt{\sum_{i=1}^{n}b_{i}^{2}}}.$

根据 Cauchy 不等式可以得到 Cosine Similarity 的取值范围是 $[-1,1].$

Pearson 相似度（Pearson Similarity）

$\text{Pearson Similarity}(A,B)=\frac{cov(A,B)}{\sigma_{A}\cdot\sigma_{B}}=\frac{\sum_{i=1}(a_{i}-\overline{A})\cdot(b_{i}-\overline{B})}{\sqrt{\sum_{i=1}^{n}(a_{i}-\overline{A})^{2}}\cdot\sqrt{\sum_{i=1}^{n}(b_{i}-\overline{B})^{2}}}.$

其中 $\overline{A}=\sum_{i=1}^{n}a_{i}/n,$ $\overline{B}=\sum_{i=1}^{n}b_{i}/n.$ 同样根据 Cauchy 不等式可以得到 Pearson Similarity 的取值范围是 $[-1,1].$

Dice 相似度（Dice Similarity）

$\text{Dice Similarity}(A,B)=\frac{2\sum_{i=1}^{n}a_{i}b_{i}}{\sum_{i=1}^{n}(a_{i}^{2}+b_{i}^{2})},$

其中 $A$ 和 $B$ 不能同时是零点，并且由均值不等式可以得到 Dice Similarity 的范围也是 $[-1,1].$

除了欧式空间的点之外，在有的情况下需要对两个集合 $A$ 和 $B$ 来做相似度的判断。特别地，欧式空间 $\mathbb{R}^{n}$ 里面的点可以看成 $n$ 个点所组成的集合。因此，下面的集合相似度判断方法同样适用于欧式空间的两个点。

Jaccard 相似度（Jaccard Similarity）

对于集合 $A$ 和 $B$ 而言，

$\text{Jaccard Similarity}=\frac{|A\cap B|}{|A\cup B|} = \frac{|A\cap B|}{|A|+|B|-|A\cap B|},$

其中， $|\cdot|$ 表示集合的势，并且 Jaccard 相似度的取值范围是 $[0,1].$ 越靠近 $1$ 表示两个集合越相似，越靠近 $0$ 表示两个集合越不相似。

重叠相似度（Overlap Similarity）

对于集合 $A$ 和 $B$ 而言，

$\text{Overlap Similarity}=\frac{|A\cap B|}{\min\{|A|, |B|\}}$

$= \max\bigg\{\frac{|A\cap B|}{|A|}, \frac{|A\cap B|}{|B|}\bigg\}$

$= \max\{P(B|A), P(A|B)\},$

其中 $P(B|A), P(A|B)$ 指的是条件概率，意思分别是 $A$ 发生的时候 $B$ 同时发生的概率， $B$ 发生的时候 $A$ 同时发生的概率。重叠相似度的另外一个名称是 Hub Promoted（HP），它主要用于计算两个集合的重叠程度。

类似的，可以将重叠相似度中的 min 函数换成 max 函数，那就是所谓的 Hub Degressed（HD），用公式来描述就是

$\text{HD}(A,B)=\frac{|A\cap B|}{\max\{|A|,|B|\}},$

它可以用于描述两个集合不重叠的程度。

距离（Distance）

欧氏距离（Euclidean Distance）

$d_{2}(A,B)=\sqrt{\sum_{i=1}^{n}(a_{i}-b_{i})^{2}}.$

另外，如果将 $2$ 进行推广，则可以引导出 $L^{p}(1\leq p\leq +\infty)$ 距离如下：

$d_{p}(A,B)=\bigg(\sum_{i=1}^{n}|a_{i}-b_{i}|^{p}\bigg)^{\frac{1}{p}},$ 其中 $p\geq 1.$

$d_{\infty}(A,B)=\max_{1\leq i\leq n}|a_{i}-b_{i}|.$

复杂网络中的节点相似性

在复杂网络 $G=(V,E)$ 中， $G$ 表示顶点集合， $E$ 表示边的集合。为了简单起见，这里暂时是考虑无向图的场景。对于顶点 $x \in V$ 而言， $N(x)$ 表示其邻居的集合。在复杂网络中，同样需要描述两个顶点 $x,y\in V$ 的相似性，于是可以考虑以下指标。

共同邻居相似度（Common Neighbours Similarity）

对于两个顶点 $x,y\in V$ 而言，如果它们的共同邻居数越多，表示它们的相似度越高，反之，相似度越低。

$CN(x,y)=|N(x)\cap N(y)|=\sum_{u\in N(x)\cap N(y)}1.$

所有邻居相似度（Total Neighbours Similarity）

类似地，将顶点 $x$ 和 $y$ 的邻居求并集，也可以得到一个指标， $TN(x,y)=|N(x)\cup N(y)|.$

Preferential Attachment

$PA(x,y)=|N(x)|\cdot |N(y)|,$ 它将 $x$ 和 $y$ 的邻居数乘起来，获得一个指标。

Jaccard 相似度（Jaccard Similarity）

如果将两个节点 $x$ 和 $y$ 的邻居分别作为两个集合 $N(x), N(y),$ $J(x,y)=CN(x,y)/TN(x,y)$ 就可以作为顶点 $x$ 和 $y$ 的 Jaccard 相似度指标，其相似度是通过邻居来衡量的。

Sorensen-Dice 相似度（Sorensen-Dice Similarity）

$SI(x,y)=\frac{2|N(x)\cap N(y)|}{|N(x)|+|N(y)|},$

该相似度与 Jaccard 相似度有恒等变换， $J(x,y)=\frac{SI(x,y)}{2-SI(x,y)}$ 和 $SI(x,y)=\frac{2\cdot J(x,y)}{1+J(x,y)}.$

Hub Promoted 相似度

该相似度描述了顶点 $x$ 与 $y$ 的重叠程度，

$HP(x,y) = \frac{|N(x)\cap N(y)|}{\min\{|N(x)|,|N(y)|\}}.$

Hub Depressed 相似度

$HD(x,y)=\frac{|N(x)\cap N(y)|}{\max\{|N(x)|,|N(y)|\}}.$

好友度量（Friend Measure）

$\text{Friend-measure}(x,y)=\sum_{u\in N(x)}\sum_{v\in N(y)}\delta(u,v),$

其中 $\delta$ 用于判断 $u,v$ 之间是否有边相连接。如果相连接，则取值为 $1,$ 否则取值为 $0.$

Adamic Adar 相似度（Adamic Adar Similarity）

$A(x,y)=\sum_{u\in N(x)\cap N(y)}\frac{1}{\ln |N(u)|},$

因此， $0\leq A(x,y)\leq \frac{CN(x,y)}{\ln(2)}.$ 事实上，当 $u\in N(x)\cap N(y)$ 时， $|N(u)|\geq 2.$ $A(x,y)$ 越大，表示顶点 $x$ 和 $y$ 的相似度就越高；反之，如果 $A(x,y)$ 越小，表示顶点 $x$ 和 $y$ 的相似度就越低。Adamic Adar Algorithm 相当于在共同邻居的计算上增加了权重，如果 $x,y$ 的共同邻居 $u$ 拥有较多的邻居，则降低权重，否则增加权重。

Resource Allocation 相似度（Resource Allocation Similarity）

$RA(x,y)=\sum_{u\in N(x)\cap N(y)}\frac{1}{|N(u)|},$

该相似度函数与 Adamic Adar 相似度类似，只是分母上没有增加对数函数而已。

参考文献：

Silva, Thiago Christiano, and Liang Zhao. Machine learning in complex networks. Vol. 2016. Switzerland: Springer, 2016.
Barabási, Albert-László. Network science. Cambridge university press, 2016.
Wang, Peng, et al. “Link prediction in social networks: the state-of-the-art.” Science China Information Sciences 58.1 (2015): 1-38.

M	T	W	T	F	S	S
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

ZHANG RONG

复杂网络中的节点相似性