1网络中的传播1.1一些传播的例子我们现在来研究网络中的传播。事实上，在网络中存在许多从节点到节点级联的行为，就像传染病一样。这在不同领域中都有所体现，比如：生物学传染性疾病信息技术级联故障，信息的传播社会学谣言、新闻、新技术的传播，虚拟市场下图就展示了一个信息经由媒体扩散（diffusion）的过程：1.2基于网络构建传播模型接下来我们看如何基于网络构建传播模型。以传染病为例，传染病会沿着网络的边进行传播。这种传播形成了一个传播树，也即级联，如下图所示：我们定义一些术语：将其中传播的对象为contagion；被传染这一事件称为adoption、infection或activation；已被传

1六度分隔理论先来看两个有趣的例子。我们建立一个好莱坞演员的网络，如果两个演员在电影中合作或就将他们链接起来。我们定义一个演员的贝肯数（baconnumber）是他们与演员凯文·贝肯有多少步的距离，贝肯数越高，演员离凯文·贝肯越远。研究发现，直到2007年12月，最高（有限）的贝肯数仅为\(8\)，且大约只有12%的演员没有路径链接到凯文·贝肯。此外，在学术合作中，埃尔德什数(Erdősnumber)被用来描述数学论文中一个作者与PualErdős的“合作距离”(PualErdős就是我们在博客《图数据挖掘：Erdos-Renyi随机图的生成方式及其特性》中提到的那位巨佬)。菲尔茨奖获得者的埃

1度分布网络的度分布\(p(k)\)表示了一个随机选择的节点拥有度\(k\)的概率。我们设度为\(k\)的节点数目\(N_k=\sharp\text{nodeswithdegree}k\)，除以节点数量\(N\)则可得到归一化后的概率质量分布：\[P(k)=N_k/N(k\in\mathbb{N})\]我们有：\(\sum_{k\in\mathbb{\mathbb{N}}}P(k)=1\)。对于下面这个网络：其归一化后的度分布直方图可表示如下：2路径2.1图的路径图的路径(path)指一个节点序列，使得序列中的每个节点都链接到序列中的下一个节点(注意：这里的术语不同教材不一样，有的教材把这里的

最近《复杂网络建模》这门课要考试了，正好也在跟Stanford的《CS224W：MachineLearningWithGraphs》这门课，这里就一边整理笔记一边复习了。1.网络的定义网络(network)是一些通过链接(links)连接起来的对象集合，它包含以下成分：对象：节点(nodes)/顶点(vertices)，用\(N\)表示；交互：链接(links)/边(edges)，用\(E\)表示；对象和交互组成的系统我们就称为网络(或图，graph)，用\(G(N,E)\)表示。一般而言，我们用术语网络来称呼一个真实的系统，如Web、社交网络、代谢网络等，此时伴随着术语节点和链接进行使用；而

简介无旋树堆(一般统称\(\text{FHQ-Treap}\))，是一种平衡树。可以用很少的代码达到很优秀的复杂度。前置知识：二叉搜索树\(\text{BST}\)\(\text{Treap}\)基本知识普通平衡树例题引入P6136【模板】普通平衡树（数据加强版）您需要写一种数据结构，来维护一些整数，其中需要提供以下操作：插入一个整数\(x\)。删除一个整数\(x\)（若有多个相同的数，只删除一个）。查询整数\(x\)的排名（排名定义为比当前数小的数的个数\(+1\)）。查询排名为\(x\)的数（如果不存在，则认为是排名小于\(x\)的最大数。保证\(x\)不会超过当前数据结构中数的总数）。求

1幂律分布和指数分布我们在博客中《图数据挖掘（二）：网络的常见度量属性》提到，节点度分布\(p(k)\)为关于\(k\)的函数，表示网络中度为\(k\)的节点占多大比例。我们发现，现实世界许多网络的节点度分布与幂函数乘正比：\[p(k)\proptok^{-\alpha}\]比如下图就是对Flick社交网络中\(p(k)\)的概率分布图像的可视化：由于对\(y=x^{-\alpha}\)两边取对数可以得到\(\log(y)=-\alpha\log(x)\)，因此我们使用原数据在log-log尺度上绘制图像得到：可以看到此时幂律分布像一条斜率为\(-\alpha\)的直线。事实上，我们可以用该方

1导引在上一篇博客《图数据挖掘：网络中的级联行为》中介绍了用基于决策的模型来对级联行为进行建模，该模型是基于效用(Utility)的且是是确定性的，主要关注于单个节点如何根据其邻居的情况来做决策，需要大量和数据相关的先验信息。这篇博客就让我们来介绍基于概率的传播模型，这种模型基于对数据的观测来构建，不过不能对因果性进行建模。2基于随机树的流行病模型接下来我们介绍一种基于随机树的传染病模型，它是分支过程（branchingprocesses）的一种变种。在这种模型中，一个病人可能接触\(d\)个其他人，对他们中的每一个都有概率\(q>0\)将其传染，如下图所示：接下来我们来看当\(d\)和\(q

1网络中的传播1.1一些传播的例子我们现在来研究网络中的传播。事实上，在网络中存在许多从节点到节点级联的行为，就像传染病一样。这在不同领域中都有所体现，比如：生物学传染性疾病信息技术级联故障，信息的传播社会学谣言、新闻、新技术的传播，虚拟市场下图就展示了一个信息经由媒体扩散（diffusion）的过程：1.2基于网络构建传播模型接下来我们看如何基于网络构建传播模型。以传染病为例，传染病会沿着网络的边进行传播。这种传播形成了一个传播树，也即级联，如下图所示：我们定义一些术语：将其中传播的对象为contagion；被传染这一事件称为adoption、infection或activation；已被传

1六度分隔理论先来看两个有趣的例子。我们建立一个好莱坞演员的网络，如果两个演员在电影中合作或就将他们链接起来。我们定义一个演员的贝肯数（baconnumber）是他们与演员凯文·贝肯有多少步的距离，贝肯数越高，演员离凯文·贝肯越远。研究发现，直到2007年12月，最高（有限）的贝肯数仅为\(8\)，且大约只有12%的演员没有路径链接到凯文·贝肯。此外，在学术合作中，埃尔德什数(Erdősnumber)被用来描述数学论文中一个作者与PualErdős的“合作距离”(PualErdős就是我们在博客《图数据挖掘：Erdos-Renyi随机图的生成方式及其特性》中提到的那位巨佬)。菲尔茨奖获得者的埃

1度分布网络的度分布\(p(k)\)表示了一个随机选择的节点拥有度\(k\)的概率。我们设度为\(k\)的节点数目\(N_k=\sharp\text{nodeswithdegree}k\)，除以节点数量\(N\)则可得到归一化后的概率质量分布：\[P(k)=N_k/N(k\in\mathbb{N})\]我们有：\(\sum_{k\in\mathbb{\mathbb{N}}}P(k)=1\)。对于下面这个网络：其归一化后的度分布直方图可表示如下：2路径2.1图的路径图的路径(path)指一个节点序列，使得序列中的每个节点都链接到序列中的下一个节点(注意：这里的术语不同教材不一样，有的教材把这里的