第1章 网络传播模型概述和分类

网络传播模型的种类繁多，侧重点各有不同。本章抽取常用传播模型的共性，给出了一般随机传播模型的基本定义，并基于这一一般定义将常用传播模型加以分类。第2章会在这个基本定义的基础上介绍若干常用的传播模型及其性质。

本书以社交网络及其上的传播为主要的研究对象，当然网络及其上的传播并不限于人与人之间的社交网络。本书的内容在很大程度上也适用于其他类型的网络，如计算机网络中的信息和计算机病毒的传播、动物网络中的病毒传播等。但为了叙述直观方便，统一用人与人之间的社交网络作为描述对象。

社交网络中传播的实体也多种多样。从具有物理实体的病毒和细菌，到虚拟形式的信息、想法、观念、文化基因（Meme，也称迷因）等，都可在社交网络中传播。因此，关于网络传播的模型种类也很多。本章抽取出这些模型的基本共性将其作为网络传播模型的基础，并在此基础上根据不同模型的特点，将模型分类。本章的目的是让读者对网络传播模型有一个总体的认识，然后在后续章节中对几个典型模型再加以具体论述。本章统一用“实体”一词来表示网络中传播的对象。在后面章节中再根据模型的具体应用场景将“实体”具体化为影响力或病毒等更为具体的对象。

在后续各章中，我们会把一个社交网络描述成一个有向图（Directed Graph）G=(V, E )，其中V是结点（Vertex，Node）的集合，是有向边（Directed Edge）的集合。统一用n=|V|表示图中的结点数，m=|E|表示图中的有向边数。每一个结点v∈ V代表一个社交网络中的人，每一条边(u, v )∈E代表结点u和v有某种直接的社交关系，如他们是朋友、熟人、网友等。边是有方向的，(u, v )表示边从u指向v。这个方向表示了实体在这个关系或这条边上的传播方向，即(u, v )表示信息、病毒或观念等实体会从u传向v。有向边(u, v )对于u来讲是一条出边，对于v来讲是一条入边；u是这条边的起点，v是这条边的终点。如果(u, v )∈E，那么u是v的一个入邻居（In-Neighbor），v是u的一个出邻居（Out-Neighbor）。在图G中，用表示结点v的所有出邻居的集合，用表示结点v的所有入邻居的集合。当需要指明所讨论的图时，用和表示。我们称N+(v)的大小|N+(v)|为v的出度（Out-Degree），N-( v )的大小|N-(v)|为v的入度（In-Degree），由有向边组成的图称为有向图。本书还会用到有关有向图的其他术语，比如有向图中的一个（有向）路径（Path）是一个图中的结点序列(v1, v2,B,vk)，使得每两个相邻结点vi-1和vi（i=2,B,k）都在图中对应一条有向边(vi-1,vi )。一个简单路径（Simple Path）是指除了首尾两个结点外没有任何两个结点相同的路径。其他相关概念和术语在需要时再做介绍。本书附录中列出了常用符号列表，便于读者统一查找。

在线社交网络中一个典型的有向图是微博网络，如新浪微博和推特（Twitter）。在微博网络中，当一个用户v关注了另一个用户u时，u的微博消息就会从u传到v，所以建一条从u到v的有向边。如果u并没有关注v，那么v的微博消息是不会直接传到u的，所以在图上就没有v到u的反向边。这也是我们用有向边和有向图来表示微博网络的原因。在这样建起的有向图中，结点v的出邻居集合N+ (v )就是所有关注v的用户，即v的粉丝，而v的出度就是v的粉丝数。反之，v的入邻居集合

N-(v )就是所有v关注的用户，v的入度就是v关注的人的个数。如果一条微博从结点v1产生，从v1传到v1的出邻居v2后，v2加以转发又传给了v2的出邻居v3，而v3又转发给了v4，那么（v1, v2, v3, v4）就是这条微博传播的一个路径。

如果想表示实体在这个关系中可以双向传播，可以用两条边(u,v)和(v,u)来表示。比如微信的朋友圈和脸书（Facebook）的朋友关系都是双向的，需要一方发出邀请另一方接受才能建立朋友关系，之后信息可以在这个朋友关系上双向传播。对于这样的网络我们用双向边或无向边来表示，对应的图称为无向图。在无向图中，一个结点v的出邻居和入邻居集合是重合的，统称为邻居集合，用N( v )表示，它的大小|N ( v )|称为v的度。

网络传播虽然多种多样，但实质上都可看成结点上与传播实体有关的状态依据网络的连通结构而发生有规律的改变。下面给出网络传播的形式化表达，用R+表示所有非负实数的集合。对于任意结点v∈ V及任意时刻，用表示结点v在时刻t的状态，用Xt表示在时刻t所有结点状态的向量，为方便起见，有时也用表示该向量。这个状态可取值集合∑与传播实体的特性有关，比如我们可以规定，0表示结点v在时刻t没有得到传播实体，而1表示结点v在时刻t得到了传播实体。状态Xv,t也可以是个实数，如区间[0,1]的任意实数，用以表达v拥有实体的程度。如果被传播的实体是对某一观点的支持态度，那么0表示完全反对，1表示完全支持，而0到1之间的数可以表示部分支持的程度。状态Xv,t根据需要还可以取其他更复杂的形式，比如在多实体同时传播的模型中，状态Xv,t本身可以是个向量，表示结点v对每个实体的拥有情况。作者在后面章节的具体传播模型描述中会给出对结点状态的具体描述。本章用抽象的Xv,t来表示结点状态。

实体在网络中的传播就是在网络中的结点上发生了一系列传播事件，而每一个传播事件引起结点状态的变化，并且一个结点状态的改变会进一步造成它的邻居结点的状态发生改变。下面给出传播事件和结点状态变化的数学表述。我们用表示结点v在时刻t之前的状态；用(t,v)表示一个传播事件，即在时刻t结点v发生了一个传播事件。它的意义是指结点v受其自身在时刻t之前的状态及v的所有入邻居在时刻t之前的状态的共同影响，在时刻t从状态改变为Xv,t。一般在这种状态改变中会引入随机性，使得和并不唯一确定状态Xv,t，而是只决定可能的状态分布，而是在这个状态分布下的一个随机取样。为方便起见，我们用Ω表示一个抽象的概率空间，而一个随机元代表了一次传播过程中的所有随机性取值。那么可以说、和ω共同唯一确定了t时刻v的状态。我们用传播函数Fv来表达这种状态转换，即。

举个例子。假设所有结点的状态都是二值{0,1}状态，结点v有两个入邻居u、w。如果定义Fv为，这意味着只要u或w中有一个结点在时刻t之前的状态是1，且结点v在时刻t发生一个传播事件，那么v在时刻t发生了（可能的）状态改变，改变之后的状态是1。如果ω是从[0,1]区间随机均匀抽取的一个数，我们定义，则当u或w中有一个点在时刻t之前的状态是1时，有50%的概率v在时刻t也变成1。因此传播函数Fv给出了状态在网络邻居间转化的准确数学表达。

要完整地描述一个网络传播过程，还需要给出传播在0时刻的初始状态以及所有传播事件发生的时刻和所在结点(t,v)。事件发生的时刻和结点可以是确定的，也可以有自己的随机性。

综上所述，我们可以给出如下关于随机传播模型（Stochastic Diffusion Model）的一般定义。

定义1.1 （随机传播模型）。一个随机传播模型由下列元素给出完整刻画：（a）图结构G=(V,E)；（b）每个结点的状态空间∑；（c）传播概率空间Ω；（d）传播事件的时间序列：(t1, v1 ),(t2, v2 ),B,(ti, vi ),B, 其中,该序列可能是个确定性序列，也可能是个随机序列，且随机性由随机元ω∈Ω确定，并与结点状态有关，如果是后者，模型要给出序列的产生方法；（e）每个结点的传播函数。对于任何一个在0时刻给定的各结点初始状态，传播过程如下：采样此次传播的随机元ω∈Ω；在传播事件时刻ti，i≥1，结点vi改变其状态至；在任何其他时刻，结点的状态保持不变。

备注1.1补充说明一下，传播概率空间Ω包括了模型在传播过程中的所有随机性可能。在文献及本书后文中我们也把它称为可能世界（Possible World）的空间，而其中一个随机元ω∈Ω表达了一个可能世界。直观地说，可能世界ω表达了传播过程的一种可能结果以及这种可能对应的概率值或概率密度（当可能世界空间是连续空间时）。可能世界的具体形式会因模型的不同而不同，后面介绍具体模型时会给出与之对应的可能世界和可能世界空间，可能世界空间对于模型的分析和其上算法的设计常有重要意义。它的具体描述也不是唯一的，要根据模型分析的需求给出合适的定义。在后文中，名词传播概率空间和可能世界空间、随机元和可能世界会互换使用，而且在具体模型中它们还可能有对应的具体术语。

上面对随机传播模型的定义是一个一般性定义，它涵盖了所有本书中介绍的具体传播模型。这个一般性定义对于我们了解传播模型的共性有所帮助。比如传播模型都是在刻画结点状态受邻居状态影响而变化的情形、状态转变都是由传播事件触发的、传播事件由时刻和结点唯一确定等。因为在后面各章中会介绍具体的传播模型，所以在这里不再给出传播模型的具体实例。下面根据传播模型的性质将一般性的模型分类，这对后面理解不同模型的特点和适用范围会有帮助。

我们可以在很多维度上对传播模型加以分类。首先，分类可以基于传播过程是单一实体还是多实体的传播进行。对于单一实体，我们可以考虑实体的二值状态传播或多值状态传播。单实体二值状态传播，即∑={0,1}，是一类被广泛研究的经典模型。在这种情况下，结点或拥有实体或不拥有实体。这时我们常用集合

St={v∈ V | Xv,t=1}表示在时刻t拥有实体的集合，集合St等价表示了时刻t的状态。在这类模型中，我们经常会研究两类模型：第一类为递进性模型（Progressive Model），其中集合St随着时间t的增长只可能增大，不可能有其他改变，即对任何；第二类为非递进性模型（Nonprogressive Model），即集合St不具有随时间增加而单调递增的特性。递进性模型常用来刻画信息和商品的传播，比如用户一旦接受了信息或产品，就会一直拥有，一般不会再撤销。而非递进性模型常用来刻画观点的传播，比如一个人可能因为网络环境的变化在两个相反的观点之间反复转化。单实体二值状态传播的递进性模型是后面章节中讨论的一个重点。

多值状态传播是另一类传播模型。这时结点不只是简单地拥有或不拥有传播实体，还可以有程度之分。前面已举例提到可以用0到1之间的实数来表达结点对某一观点的支持程度。这一程度可以随着网络中结点的邻居的态度产生相应的增减变化。对于多值状态模型，我们仍可以将其划分为递进性和非递进性模型：在递进性模型中每个结点的状态值只会单调增加，即对任何v∈ V，任何而非递进性模型不具备这一性质。可以看出，这种递进性模型的定义是对二值状态模型的一个直接推广。但对于我们提到的对观点支持度的例子，非递进性模型应该更合适，因为个人对某观点的支持度应该会随着其社交网络中朋友的观点的变化而变化。

另一个分类维度是离散时间模型和连续时间模型。在离散时间模型中，传播事件是在每个结点的每个整数时刻点固定发生的，即传播事件序列是。这样在每个整数时刻点，每个结点都根据其入邻居在前一整数时刻点的状态发生一次状态变化。当然，离散模型也允许传播事件只在某些时刻和某些结点上发生，且可以随机发生，但这些都可以用传播概率空间和传播函数来等价表达。比如，如果一个结点v在任何整数时刻点t都有一个独立的概率q发生一个随机事件，那么我们可以在传播概率空间Ω中附加关于传播事件发生点的事件，并且在每个结点的传播函数Fv的定义中根据随机元ω的值限制状态转换只在传播事件发生点完成。所以在离散时间模型中，统一规定传播事件序列就是。在连续时间模型中，传播事件可以发生在任何正实数点t，传播事件发生的时刻一般有随机性。这种随机性或由单独的随机过程序列产生，或基于结点的状态改变。比如在二值状态递进性模型中，常用的模型是当一个结点v的状态从0变为1的那一时刻t，结点v向它的每一个出邻居u传播，而传播延迟是服从某一分布的随机变量，所以在时刻结点u将发生一次传播事件。具体的模型在后面章节（如第5章第1节）中会详细描述。

以上描述的模型都属于随机传播模型。另外还有一类模型利用博弈论的工具来描述结点对传播实体的选择：结点总是选择使其收益最大化的实体，而结点的收益与其邻居结点的状态有关。这样的模型通过对结点收益函数的分析，一般可以被转化为结点的转播函数，从而也可被纳入随机传播模型的框架中。我们在第7章第4节中会简要介绍基于博弈论的模型。

本书将单一实体二值状态离散时间的传播模型作为介绍的重点。这类模型已经涵盖典型的影响力传播模型、病毒传播模型、观点传播的选举模型等。其中影响力传播模型作为典型的递进性模型，选举模型作为典型的非递进性模型，本书会分章重点介绍模型的特点和在其上研究的问题和算法。在此基础上，也会对其他模型，如多实体影响力传播模型、病毒传播模型、基于博弈论的模型等进行介绍。

归纳起来，网络中的传播模型多种多样，纷繁复杂。从单实体到多实体、从二值状态到多值状态、从离散时间到连续时间等，在实际中要针对具体的应用选择恰当的模型。为方便读者，我们总结了上文谈到的各种模型分类，具体见表1-1。

表1-1 网络传播模型的分类