Category Archives: 图挖掘

图挖掘

社交网络之间的帐号映射

Leave a comment

帐号映射的整体介绍

在现实生活中，用户通常会同时使用多个社交网络，例如国外的 Twitter，Instagram，Facebook，也可能使用微信，QQ，微博等国内的产品。基于这些产品的不同定位，用户自身的社交网络会有很大的差异，那么如何通过机器学习算法找到一个人的社交网络帐号就成为了一个有趣的问题。在学术界，有学者对开源的 Facebook，Twitter 等社交网络数据进行了研究，设计了一套帐号映射的技术方案。

帐号映射这个课题有很多的别名，例如：

  • Social identity linkage；
  • User identity linkage；
  • User identity resolution；
  • Social network reconciliation；
  • User account linkage inference；
  • Profile linkage；
  • Anchor link prediction；
  • Detecting me edges；

帐号映射的目的就是将社交网络上这些看似不同的帐号映射到自然人：帐号（user accounts）-> 真实的自然人（real natural person）。令社交网络 \mathcal{G}=\mathcal{G}(\mathcal{U},\mathcal{E}) 是一个图，顶点是帐号 \mathcal{U}=\{u_{1},\cdots,u_{n}\}, 边是由帐号之间的连线 \mathcal{E}\subseteq \mathcal{U}\times\mathcal{U} 所构成的。

帐号映射（User Identity Linkage）的定义是：给定两个社交网络 \mathcal{G}^{s}=(\mathcal{U}^{s},\mathcal{E}^{s}) 和 \mathcal{G}^{t}=(\mathcal{U}^{t},\mathcal{E}^{t}), 其目标是找到一个函数 \mathcal{F}:\mathcal{U}^{s}\times\mathcal{U}^{t}\rightarrow\{0,1\} 使得，
\mathcal{F}(u^{s},u^{t})=\begin{cases}1,\text{ if } u^{s} \text{ and } u^{t} \text{ belong to same person,}\\ 0, \text{ otherwise.} \end{cases}
其中 u^{s}\in\mathcal{U}^{s}, u^{t}\in\mathcal{U}^{t}.

上述函数 \mathcal{F} 就是模型需要学习的目标函数，进一步地，对于 u^{s}\in\mathcal{U}^{s}, u^{t}\in\mathcal{U}^{t}, 学习得到的预测函数 \mathcal{\hat{F}}(u^{s},u^{t})=p\in [0,1] 表示两个帐号属于同一个自然人的概率值。

一个帐号在社交网络的属性包括很多方面，例如：

画像属性（Profile Features）内容属性（Content Features）社交网络属性（Network Features）
ID（社交网络的唯一标识）时间戳（timestamp）关注，被关注，好友关系（Friendship）
身份证 ID（identity card）语音（speech）点赞（like）
手机号（phone）视频（video）评论（comment）
昵称（username）图片（image）@（at）
头像（head image）文本（text）收藏（collect）
性别（gender）设备信息（device）消息（message）
年龄（age）wifi 信息（wifi）回复（reply）
邮箱（email）地理位置（gps）
个人网页（url）
职业（occupation）
常见的社交网络数据

一般情况下，

  1. 画像属性：绝大多数帐号都会有基础的画像信息；
  2. 内容属性：不活跃的帐号较难获取；
  3. 社交网络属性：线上的社交网络关系并不代表线下的社交网络关系，存在一定的噪声数据。

帐号映射的技术框架可以基于特征工程来做，然后使用有监督算法，无监督算法，或者半监督算法来进行帐号对之间的训练和预测。

帐号映射的技术框架

帐号映射的特征工程

帐号的画像特征

对于社交网络 \mathcal{G}=\mathcal{G}(\mathcal{U},\mathcal{E}) 中的一个帐号 u\in\mathcal{U} 而言，用 \overrightarrow{p_{u}}=(p_{u}^{1},\cdots,p_{u}^{m}) 来表示画像特征向量，其中 m\geq 1 表示画像属性特征的个数。对于两个社交网络 \mathcal{G}^{s},\mathcal{G}^{t} 的帐号 u^{s},u^{t} 而言，可以得到相应的画像特征向量 \overrightarrow{p_{u^{s}}},\overrightarrow{p_{u^{t}}}, 然后可以用基于距离（distance-based）或者基于频率（frequence-based）的方法来获得向量的距离或者相似性。换句话说，就是通过加权平均算法来获得结果：

sim(\overrightarrow{p_{u^{s}}},\overrightarrow{p_{u^{t}}})=\sum_{1\leq i\leq m}w_{i}\cdot sim(p_{u^{s}}^{i},p_{u^{t}}^{i}), 或者

dis(\overrightarrow{p_{u^{s}}},\overrightarrow{p_{u^{t}}})=\sum_{1\leq i\leq m}w_{i}\cdot dis(p_{u^{s}}^{i},p_{u^{t}}^{i}),

其中 sim 表示相似度，dis 表示距离。

基于距离的方法（distance-based）的方法很多，例如：

  1. 文本（text field）之间的距离可以考虑用 Jaro-Winkler distance，Jaccard similarity，Levenshtein distance 等方法；
  2. 图像（visual field）之间的距离可以考虑用 mean square error，dot product，angular distance，peak signal-to-noise ratio，Levenshtein distance 等方法；

基于频率的方法（frequence-based）可以考虑 bag-of-word model，TF-IDF model，Markov-chain model 等方法；

帐号的内容特征

帐号所产生的内容数据包括三个部分：

  1. 时间上的数据（temporal）：时间戳的数据；
  2. 空间上的数据（spatial）：帐号的设备数据，IP 数据，WIFI 数据，地理位置数据等等；
  3. 内容上的数据（post）：帐号所产生的内容数据，包括但不限于视频，文本，语音，图片等。

用数学公式来描述就是 \overrightarrow{c_{u}}=\{(t_{1},s_{1},p_{1}), \cdots,(t_{m},s_{m},p_{m})\}, 其中 t_{i},s_{i},p_{i}(1\leq i\leq m) 分别表示时间戳，空间数据，内容数据。

在某个时间段内，帐号所产生的内容特征可以提炼出用户在社交网络上的行为数据和内容数据，形成一个行为序列。通过这个行为序列，可以得到用户的内容特征。

  1. 基于兴趣的特征（Interest-based）：可以基于内容数据判断帐号对哪些内容更感兴趣；
  2. 基于风格的特征（Style-based）：基于内容数据得到帐号的写作风格，例如常用词语等；
  3. 基于轨迹的特征（Trajectory-based）：基于帐号的行为轨迹数据，包括设备，IP，WIFI，地理位置以及相应的时间戳，得到帐号的足迹（footprint）。

帐号的社交网络特征

社交网络包括两种：

  1. 局部社交网络（local network）：查看帐号的邻居（关注，被关注，好友关系）等诸多数据；
  2. 全局社交网络（global network）：查看帐号在全局数据中的位置情况；

对于帐号的社交网络特征，包括以下两种常见形式：

  1. 基于邻居的特征（Neighborhood-based）：共同好友数，共同邻居个数，Jaccard Coefficient，Overlap Coefficient，Dice Coefficient，Adamic/Adar score；
  2. 基于嵌入的特征（Embedding-based）：通过计算帐号在相应的社交网络的嵌入特征，然后计算特征之间的距离或者相似性。

帐号映射的建模思路

机器学习的常见算法包括有监督算法（supervised model），无监督算法（unsupervised model）和半监督算法（semi-supervised model）。

基于上面的特征工程，加上合适的权重之和可以得到一个分数（score），也就是：

\mathcal{F}(u^{s},u^{t})=\alpha \cdot sim_{p}(\overrightarrow{p_{u^{s}}}, \overrightarrow{p_{u^{t}}})+\beta\cdot sim_{c}(\overrightarrow{p_{u^{s}}}, \overrightarrow{p_{u^{t}}})+\gamma\cdot sim_{n}(\overrightarrow{p_{u^{s}}}, \overrightarrow{p_{u^{t}}}),

其中 sim_{p}, sim_{c}, sim_{n} 分别表示画像（profile），内容（content），社交网络（network）之间的相似度。

如果有样本的话，全体样本是 \mathcal{Q}=\{(u^{s},u^{t}),\forall u^{s}\in\mathcal{U}^{s},\forall u^{t}\in\mathcal{U}^{t}\}, 那么正样本是 \mathcal{M}=\{(u^{s},u^{t}),u^{s}\in\mathcal{U}^{s},u^{t}\in\mathcal{U}^{t}, u^{s} \text{ and } u^{t} \text{ belong to the same person}\}, 负样本 \mathcal{N}=\mathcal{Q}-\mathcal{M}. 在实际使用的时候，要注意采样的比例和负样本的选择方法。

帐号映射的评价指标

对于 u^{s}\in\mathcal{U}^{s}, u^{t}\in\mathcal{U}^{t}, 假设
\mathcal{Q}=\{(u^{s},u^{t}),\forall u^{s}\in\mathcal{U}^{s},\forall u^{t}\in\mathcal{U}^{t}\} 是所有的帐号对，
\mathcal{M}=\{(u^{s},u^{t}),u^{s}\in\mathcal{U}^{s},u^{t}\in\mathcal{U}^{t}, u^{s} \text{ and } u^{t} \text{ belong to the same person}\} 是所有属于相同自然人的帐号对，
\mathcal{N}=\mathcal{Q}-\mathcal{M} 是所有属于不同自然人的帐号对。
令\mathcal{A}= {被算法映射成相同自然人的帐号对}，\mathcal{B}= {被算法映射成不同自然人的帐号对}；用 TP, TN, FN, FP 来描述就是：

  • True Positive（TP）：|\mathcal{A} \cap \mathcal{M}|;
  • True Negative（TN）：|\mathcal{B}\cap\mathcal{N}|;
  • False Negative（FN）：|\mathcal{B}\cap\mathcal{M}|;
  • False Positive（FP）：|\mathcal{A}\cap\mathcal{N}|;

那么，Precision = TP / (TP + FP)=|\mathcal{A}\cap\mathcal{M}|/|\mathcal{A}|, Recall = TP / (TP + FN)= |\mathcal{A}\cap\mathcal{M}|/|\mathcal{M}|.

另外，F1=2\cdot Precision \cdot Recall / (Precision + Recall), Accuracy=(TP+TN)/(TP+TN+FP+FN).

部分论文细节

  1. Liu, Jing, et al. “What’s in a name? An unsupervised approach to link users across communities.” Proceedings of the sixth ACM international conference on Web search and data mining. 2013. 本篇文章主要是基于用户的名字来识别跨网络的用户的，提取用户的特征之后，使用 SVM 分类器来进行识别；
  2. Riederer, Christopher, et al. “Linking users across domains with location data: Theory and validation.” Proceedings of the 25th International Conference on World Wide Web. 2016. 本篇文章主要是基于用户的内容特征来进行建模；
  3. Labitzke, Sebastian, Irina Taranu, and Hannes Hartenstein. “What your friends tell others about you: Low cost linkability of social network profiles.” Proc. 5th International ACM Workshop on Social Network Mining and Analysis, San Diego, CA, USA. 2011. 本篇论文是根据社交网络中的用户邻居数据，来判断用户之间相似性的。

参考文献

  1. Shu, Kai, et al. “User identity linkage across online social networks: A review.” Acm Sigkdd Explorations Newsletter 18.2 (2017): 5-17.
  2. Liu, Jing, et al. “What’s in a name? An unsupervised approach to link users across communities.” Proceedings of the sixth ACM international conference on Web search and data mining.
  3. Riederer, Christopher, et al. “Linking users across domains with location data: Theory and validation.” Proceedings of the 25th International Conference on World Wide Web. 2016.
  4. Labitzke, Sebastian, Irina Taranu, and Hannes Hartenstein. “What your friends tell others about you: Low cost linkability of social network profiles.” Proc. 5th International ACM Workshop on Social Network Mining and Analysis, San Diego, CA, USA. 2011.
图挖掘

复杂网络中的节点相似性

Leave a comment

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

相似性与距离

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

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

两个集合 A 和 B

重叠相似度（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），它主要用于计算两个集合的重叠程度。

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）

类似地，将顶点 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 相似度类似，只是分母上没有增加对数函数而已。

参考文献：

  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.
图挖掘

随机图模型

Leave a comment

数学家是一种把咖啡变成定理的机器。
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. 【定义一】给定 N 和 M, G_{1}(N,M) 的定义是随机从 N 个顶点和 M 条边所生成的所有图集合中选择一个。其中，这样的图集合的势是 C(N(N-1)/2, M), 因此获得其中某一个图的概率是 1/C(N(N-1)/2, M).
  2. 【定义二】给定 N 和 p，G_{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. 顶点的平均度从 0 到 N-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.