Category Archives: 图挖掘

复杂网络中的节点相似性

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

相似性与距离

首先,我们来看一下相似性函数的含义。对于两个对象 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}, 它具有以下两个性质:

  1. 自反性:s(x,x)=s_{max} 对于所有的 x\in X 都成立;
  2. 对称性: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, 并不存在上界,它具有以下三个性质:

  1. 自反性:d(x,x)=0 对于所有的 x\in X 都成立;
  2. 对称性:d(x,y)=d(y,x) 对于所有的 x,y\in X 都成立;
  3. 三角不等式: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].

Pearson 系数

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})},

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

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

Jaccard 相似度(Jaccard Similarity)

对于集合 AB 而言,

\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 表示两个集合越不相似。

两个集合 A 和 B

重叠相似度(Overlap Similarity)

对于集合 AB 而言,

\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),它主要用于计算两个集合的重叠程度。

Overlap Similarity

类似的,可以将重叠相似度中的 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)

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

Preferential Attachment

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

Jaccard 相似度(Jaccard Similarity)

如果将两个节点 xy 的邻居分别作为两个集合 N(x), N(y), J(x,y)=CN(x,y)/TN(x,y) 就可以作为顶点 xy 的 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 相似度

该相似度描述了顶点 xy 的重叠程度,

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) 越大,表示顶点 xy 的相似度就越高;反之,如果 A(x,y) 越小,表示顶点xy 的相似度就越低。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 相似度类似,只是分母上没有增加对数函数而已。

参考文献:

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

随机图模型

数学家是一种把咖啡变成定理的机器。
Alfred Renyi

A mathematician is a machine for turning coffee into theorems.
Alfred Renyi

随机图的历史

在 1959 和 1968 年期间,数学家 Paul Erdos 和 Alfred Renyi 发表了关于随机图(Random Graph)的一系列论文,在图论的研究中融入了组合数学和概率论,建立了一个全新的数学领域分支—随机图论。

随机图的案例 p=0.01

随机图的定义

本文只关注无向图的场景。顾名思义,随机图(Random Graph)就是将一堆顶点随机的连接上边。好比在地上撒了一堆豆子,而豆子之间是否用线来相连是根据某个概率值来确定的。通常来说,对于随机图而言有两种定义方式

  1. 【定义一】给定 NM, G_{1}(N,M) 的定义是随机从 N 个顶点和 M 条边所生成的所有图集合中选择一个。其中,这样的图集合的势是 C(N(N-1)/2, M), 因此获得其中某一个图的概率是 1/C(N(N-1)/2, M).
  2. 【定义二】给定 NpG_{2}(N,p) 的定义是有 N 个顶点,并且两个顶点之间以概率 p\in[0,1] 来决定是否连边。

事实上,这两个定义是等价的,N 个顶点的图最多拥有的边数是 N(N-1)/2,G_{1}(N,M) 恰好有 M 条边,并且它们分配的概率是均等的,因此两个顶点之间是否存在边的概率就是 p = M/(N(N-1)/2), 这里的 C 指的是组合数。i.e.

G_{1}(N,M) = G_{2}(N, \frac{M}{N(N-1)/2}).

另一方面,对于 G_{2}(N,p) 而言,顶点两两之间是否存在边的概率是 p,N 个顶点的图最多拥有 N(N-1)/2 条边,于是边数为 pN(N-1)/2. i.e.

G_{2}(N,p)=G_{1}(N,pN(N-1)/2).

进一步地,通过以上两个公式可以得到:

G_{1}(N,M)=G_{2}(N,\frac{M}{N(N-1)/2}) = G_{1}(N,M).

在定义一中,可以直接算出所有顶点的平均度是 \langle k\rangle = 2 M /N. 但如果要计算图的其余指标,用第二种定义 G_{2}(N,p) 反而更加容易,因此后续将会重点关注第二种定义,为方便起见,记号简化为 G(N,p) = G_{2}(N,p).

随机图的度

图的度(degree)指的是对于某个顶点而言,与它相关联的边的条数。对于随机图 G(N,p) 而言,它的边数大约是 pN(N-1)/2, 最多与该节点相连接的顶点数为 N-1, 整个图的顶点平均度是(边数 * 2) / 顶点数,用记号 \langle k\rangle 来表示,意味着顶点平均度是 \langle k\rangle = p(N-1) \sim pN,N 充分大的时候成立。换言之,

p \sim \langle k\rangle / N.

顶点上的值就是该顶点的度

对于随机图 G(N,p) 中的一个顶点 i 而言,我们想计算它恰好有 d 条边的概率值。事实上,对于除了 i 之外的 N-1 个点而言,有 d 个顶点与 i 相连,N-1-d 个顶点与 i 不相连,其概率是 p^{d}(1-p)^{N-1-d}, 同时需要从这 N-1 个点中选择 d 个点,因此,顶点 i 的度恰好是 d 的概率是

p_{d}=C(N-1, d)\cdot p^{d}\cdot (1-p)^{N-1-d}.

特别地,当 d\ll N 时,上述概率近似于泊松分布(Possion Distribution)。事实上,p=\langle k\rangle / (N-1) 并且

C(N-1,d) = (N-1)(N-2)\cdots(N-d+1)/ d! \sim (N-1)^{d} / d!,

(1-p)^{N-1-d} \sim (1-\langle k\rangle /(N-1))^{N-1-d} \sim e^{-\langle k\rangle},

因此,在 d\ll N 时,p_{d} 近似于泊松分布,

p_{d} \sim \langle k\rangle^{d}e^{-\langle k\rangle}/d!.

随机图的连通分支

对于随机图 G(N, p) 而言,它的连通分支个数是与顶点的平均度 \langle k\rangle 息息相关的。特别地,当 \langle k\rangle=0 时,每个顶点都是孤立的,连通分支个数为 N;\langle k\rangle=N-1 时,任意两个顶点都有边相连接,整个图是完全图,连通分支的个数是 1. 顶点的平均度从 0N-1 的过程中,连通分支的个数从 N 演变到 1, 最大连通分支顶点数从 1 演变到 N, 那么在这个变化的过程中,最大连通分支的顶点数究竟是怎样变化的呢?是否存在一些临界点呢?数学家 Erdos 和 Renyi 在 1959 年的论文中给出了答案:

对于随机图 G(N,p) 而言,用 N_{G} 表示最大连通分支的顶点个数,那么对于图的平均度 \langle k\rangle 而言,

  1. \langle k\rangle = Np < 1, 那么 N_{G} = O(\ln(N));
  2. \langle k\rangle = Np = 1, 那么 N_{G} = O(N^{2/3});
  3. \langle k\rangle = Np \in (1, \ln(N)), 那么巨连通分支(Giant Component)存在,同时存在很多小的连通分支,在临界点 1 的附近时, N_{G} \sim (p-p_{c})N, 这里 p_{c}=1/N;
  4. \langle k\rangle = Np \in (\ln(N),+\infty), 那么图 G 是全连通图,i.e. N_{G}=N.

在这个定理中,对于顶点的平均度 \langle k\rangle 而言,存在两个临界点,分别是 1\ln(N).\langle k\rangle < 1 时,巨连通分支不存在,所有连通分支的量级都在 O(\ln(N)) 以下;当 \langle k\rangle = 1 时,巨连通分支开始出现,量级大约是 O(N^{2/3});1<\langle k\rangle <\ln(N) 时,随机图存在一个巨连通分支和很多小的连通分支;当 \langle k\rangle > \ln(N) 时,图是连通图。

图的平均度的临界点

整个定理的证明有点复杂,但本文将会介绍两个临界点的计算。先来考虑第一个临界点 \langle k\rangle = 1 的情况:

N_{G} 来表示随机图 G 中的最大连通分支的顶点个数,u 表示图 G 中不在最大连通分支的顶点比例,i.e.

u=(N-N_{G})/N = 1 - N_{G}/N= 图的顶点不在最大连通分支的概率。

对于不在最大连通分支的顶点 i 而言,其余的 N-1 个顶点分成两种情况,Case(1):要么 i 与之不相连,此时概率是 1-p; Case(2):要么 i 与之相连,但此时的顶点不能在最大连通分支中,那就只能在剩下的 uN 个顶点中,其概率是 pu. 于是,对于所有顶点而言,它不在最大连通分支的概率是 (1-p+pu)^{N-1}. 于是,

u=(1-p+pu)^{N-1}=(1-p(1-u))^{N-1}.

根据 p\sim\langle k\rangle /N\lim_{N\rightarrow +\infty}(1+x/N)^{N}=e^{x} 可以得到当 N 充分大时,有

u = (1-p(1-u))^{N-1} = (1-(1-u)\langle k\rangle /N)^{N-1} \sim e^{-(1-u)\langle k\rangle}.

s= 1-u = N_{G}/N, 它表示最大连通分支的顶点个数在所有顶点个数的占比,从而可以得到近似方程

1-s=e^{-\langle k\rangle s}.

g(s) = 1 - s - e^{-\langle k\rangle s},g(0) = 0, g(1) = -e^{\langle k\rangle}<0. 它的导数是 g'(s) = - 1 + \langle k\rangle e^{-\langle k\rangle s}, 通过计算可以得到:

  1. \langle k\rangle \leq 1 时,g'(s)<0(0,1) 上成立,i.e. g(s) = 0[0,1] 上的唯一解是 s=0, 换言之,N_{G}/N = s \rightarrow 0;
  2. \langle k\rangle > 1 时,g'(s)>0(0,\ln\langle k\rangle/\langle k\rangle) 成立,g'(s)<0(\ln\langle k\rangle /\langle k\rangle,1) 成立。换言之,g(s)=0[0,1] 上除了零之外还有解 s_{0}\in(0,1). 此时会存在巨连通分支,N_{G}/N = s_{0}\in (0,1) 是解。

因此,最大连通分支的顶点数在这个点会出现突变,1 是该方程的第一个临界点,并且是出现巨连通分支的临界点。

再来考虑第二个临界点 \langle k\rangle = \ln(N) 的情况。对于极限状况而言,假设仅有一个顶点不在最大连通分支中,那么 s = N_{G}/N = (N-1)/N, 此刻,

1/N=1-s=e^{-\langle k\rangle s}=e^{-\langle k\rangle (N-1)/N},

两边求对数可以得到 \langle k\rangle = \ln(N), 因此,\ln(N) 也是一个临界点,并且是出现全连通图的临界点。

随机图的六度分离

六度分离又称为小世界现象,它的含义是在地球上任意选择两个人,他们之间最多相隔 6 个相识关系。换言之,来自世界上任何地方的两个人都可以通过不超过 6 个相识关系所连接起来。

The Six Degrees of Larry Stone

图中两个顶点的距离定义为两个顶点之间的最短路径长度,图的直径就是图中任意两点的距离的最大值。对于随机图 G(N,p) 而言,如果 \langle k\rangle \leq 1 则是不连通的,因此通常只需要考虑 \langle k\rangle>1 的情况,甚至只考虑 \langle k\rangle >\ln(N) 的全连通图。任取一个顶点 i,则有

  1. \langle k\rangle 个距离为 1 的顶点;
  2. \langle k\rangle^{2} 个距离为 2 的顶点;
  3. \langle k\rangle^{3} 个距离为 3 的顶点;
  4. \langle k\rangle^{d_{max}} 个距离为 d_{max} 的顶点;

同时,G(N,p) 而言,顶点的个数为 N, 这意味着 \langle k\rangle + \langle k\rangle^{2}+\cdots+\langle k\rangle^{d_{max}}\leq N. 通过等比级数的公式可以得到 \langle k\rangle^{d_{max}} \leq N, 因此,

d_{max} = O(\ln(N)/\ln(\langle k\rangle)).

而随机图的直径的量级是与 d_{max} 成正比的,因此,随机图的直径量级同样是 O(\ln(N)/\ln(\langle k\rangle)). 如果 N = 10^9 并且每个人认识 \langle k\rangle = 200 个人,于是随机图的直径量级是 \ln(6*10^9) / \ln(200) = 4.25 < 6.

参考文献

  1. Erdos Renyi Model:https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model
  2. Giant Component:https://en.wikipedia.org/wiki/Giant_component
  3. Erdős P, Rényi A. On the evolution of random graphs[J]. Publ. Math. Inst. Hung. Acad. Sci, 1960, 5(1): 17-60.
  4. Albert R, Barabási A L. Statistical mechanics of complex networks[J]. Reviews of modern physics, 2002, 74(1): 47.
  5. 《巴拉巴西网络科学》,艾伯特-拉斯洛·巴拉巴西(Albert-LászlóBarabási),2020.