信息的传播、影响力的分析、木马和病毒的传播等是社交网络和信息网络中重要的研究领域^[1-3]，挖掘网络中信息传播模式将有助于这些问题的分析.网络中信息的传播模式指目标信息(木马、病毒、某个观点等)在网络中传播的模式，该模式难以通过观察得到.挖掘网络中信息的传播模式需要解决2个挑战:①网络中传播的信息内容是未知的、无法获取的；②网络中背景通信流量占比远高于目标信息流量.一般的场景下，能够利用的数据只有通联双方和通信发生的时间.比如，在挖掘僵尸网络中，比较容易获取节点间通信行为及通信时间，但节点间通信的负载难以进行分析.目前，关于信息传播的研究方法大都基于通信内容的方法^[4-5]、通信内容与通信属性结合的方法^[6-8]，或者是基于复杂网络的一些方法^[9-10].而这些方法在通信内容未知且通信属性只有时间时，难以发挥很好的效果.

笔者所研究的场景比较特殊，在仅知网络中用户通联双方及通联时间的情况下，推断用户间传递内容的相关性，进而分析用户间信息的传播模式.通常情况下，容易观测到某用户与其他用户发通信的时间序列，而通信内容未知，那么，如何通过这些通信数据分析网络中的信息是如何传播的呢？网络中什么样的信息传递模式能够来解释这些观测的通联数据呢？为了解决这些问题，采用生成模型对用户间通联数据的相关性和信息传播模式进行建模，并试图找到一个隐含的网络子图，使得通联数据的似然函数能够最大化.网络中的指令、僵尸网络中的指控数据等信息的传播存在一个固定的模式，如果网络中通联数据能够构成一个有向多边网络(multi-edge digraph)，信息的传播模式将是该网络的一个有向子图.

1 信息传递模式挖掘方法 1.1 问题定义

一般来说，网络中用户间信息的传播遵循一定的模式，而这个模式通常可以表示用户间信息传递的关系.下面给出网络中用户间信息传播模式的一个定义.

定义1   网络中用户间信息传播模式指在通信网络G_o(V, E)中代表用户间信息传播的一种固有模式.本节中用网络G(V, E)代表用户间信息传播关系的网络，那么G(V, E)是一个有向图，且是G_o(V, E)的一个子图，代表用户间的信息更加倾向于沿着网络G(V, E)中的边传播.网络G(V, E)中的每条边称为信息传递边，而网络G_o(V, E)的非信息传递边称为普通边.

定义2   用户间信息传递模式挖掘问题指给定节点的集合V，以及节点之间的通联数据A={(v_i, v_j, t_k)|v_i, v_j∈V, i≠j}，如何推测节点间传递信息的相关性，并得到G(V, E).

容易得到通信网络G_o(V, E)的拓扑，只需要将每条通联数据当作一条边，并将所有的边组合起来；而用户间信息的传递模式G(V, E)是不容易得到的.由于通信内容是未知的，为了得到网络中信息的传播模式，首先需要根据节点的通信行为，推测通信内容的相关性，然后分析信息的传播模式.文献[11-13]中指出，信息转发的时间间隔Δt满足指数分布或幂律分布，即p(Δt)~e^－αΔt或者p(Δt)~(Δt)^－α.如果用户收到某次通信后在短时间内又与其他用户通信，那么可以推测用户间传递的信息是相关的，这里使用f(t_{i, j}|t_{k, i})来衡量传递信息的相关性.

1.2 信息传播模型

为了方便后续数据处理，首先需要将通联数据A进行整理.这里定义用户的行为记录.

定义3   用户的行为记录指用户接收信息与发送信息的行为所构成的记录.那么，R_record={R_i|i∈V}, 其中

$ {R_i} = \left\{ \begin{array}{l} \cdots {r_x}{r_y} \cdots {s_p} \cdots |{r_x}: = {\rm{recievetime}}\;{\rm{of}}\;{\rm{node}}\;x \to i, \\ {s_p}: = {\rm{sendtime}}\;{\rm{of}}\;{\rm{node}}\;i \to p \end{array} \right\} $

(1)

定义一个最大观测时间窗口T，并将每个用户的行为记录切成许多时间切片ts.由于需要挖掘用户传递信息的行为，所以仅从用户收到其他用户发送给其信息的时间开始作为时间切片的起点，并只考虑用户的发送行为.笔者认为，用户在时间窗口外的发送行为与窗口内收到信息的时间间隔过长而不会存在信息传递的可能. 图 1为用户i的行为记录及时间切片的示意图.在时间切片r_x与r_x+T之间只有2个发送行为，因此该时间切片可以表示为ts_{rx, i}={r_x, s_u, s_v}，每个时间切片由2个下标来确定，第1个下标代表该时间切片开始的时间，第2个下标代表用户i的时间切片，并且每个时间切片的第1个数据为该用户收到信息的用户及时间，后续的数据全部为该用户的发送行为及时间.切割所有用户的行为记录，将通联数据A转化为了时间切片的集合TS，容易证明，通联数据A与时间切片TS是可以互相转化的，时间切片只是对数据变换了一个表现形式.

在图 1中，由于并不知道用户i收到来自用户x的消息后，是否将消息转发给了用户u或者v，因此需要根据不同情况进行讨论.如果由用户x指向用户u之间的边属于G(V, E)，那么用户有很大的概率是进行信息传播的行为，使用f(t_{i, u}|t_{x, i})来表示衡量这种概率的大小；如果由用户x指向用户v之间的边不属于G(V, E)，那么可以使用一个非常小的数值ε来表示这种情况发生的概率.由于用户转发消息时可能会发送给G(V, E)中一个或多个子节点，那么用β表示用户未发送子节点的概率大小.这样可以得到一个时间切片的似然函数：

$ \begin{array}{l} f\left( {{\rm{t}}{{\rm{s}}_{{r_x}, i}}|G, {G_{\rm{o}}}} \right) = \prod\limits_{k \in Vout\left( i \right)} {{\varepsilon ^m}{{\left( {1-\varepsilon } \right)}^n}{\beta ^q}f\left( {{t_{i, {s_k}}}|{t_{{r_x}, i}}} \right)} = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\prod\limits_{k \in {V_{{\rm{out}}}}\left( i \right)} {f'\left( {{t_{i, {s_k}}}|{t_{{r_x}, i}}, \varepsilon, \beta } \right)} \end{array} $

(2)

其中：t_{i, sk}为用户i发送信息给用户k的时间，n为时间切片中用户i发送信息给子节点的通信数量，m则为用户i发送信息给非子节点的通信数量，q为用户未发送给其子节点的数量，m+n为用户i在G_o(V, E)中的出度与G(V, E)中出度的差，V_out代表节点的出射边集合.

图 2给出了式(2)的一个说明.图中虚线表示G_o(V, E)中的非信息传递边，实线表示G(V, E)中的信息传递边.一般来说，用户间信息传递模式G(V, E)是未知的，可以发现，第1个潜在传递模式更加容易产生右边的时间切片，因此由式(2)表征的似然函数就要大一些.

考虑所有的时间切片集合TS，可以得到全部观测数据的似然函数为

$ f\left( {{\rm{TS}}|G, {G_{\rm{o}}}} \right) = \prod\limits_{i \in V, {r_x} \in {R_i}} {f\left( {{\rm{t}}{{\rm{s}}_{{r_x}, i}}|G, {G_{\rm{o}}}} \right)} $

(3)

这样，将通信网络中用户间信息传递模式挖掘问题转化为了如何找到G使得式(3)最大化.下面对式(3)的一些性质进行分析.首先，式(3)是非负的，因为式(2)是非负的；其次，式(3)是单调的，也就是说，对于G(V, E)及G′(V, E′)，$E \subset E'$，f(TS|G, G_o) < f(TS|G′, G_o)，因为根据式(2)，将一条普通边转变为信息传递边后，似然概率中的一个ε变为更大的概率值.那么，向G(V, E)中增加边后并不会降低解的性能，G(V, E)=G_o(V, E)应该是最佳的解，然而希望挖掘出的信息传播模式G(V, E)要稀疏一些，这样更能够表征原网络G_o(V, E)中的一些特性，尤其是得到信息传播的一些骨干路径图.因此，将网络G(V, E)中边的数据限制为k.重新改写通信网络中用户间信息传递模式挖掘问题为

$ G' = \mathop {\arg \max}\limits_{\left| G \right| \le k} f\left( {{\rm{TS}}|G, {G_{\rm{o}}}} \right) $

(4)

一般来说，采用暴力搜索的方法求解式(4)需要指数的时间，下面证明求解式(4)是NP-hard.

定理1   由式(4)定义的通信网络中用户间信息传递模式挖掘问题是NP-hard.

证明   见附录A.

定理1证明了通信网络中用户间信息传递模式挖掘问题为NP-hard，因此求解该问题难以在多项式时间内找到求解算法.通常，求解这类问题一般采用启发式的搜索算法或者是求解一个近似最优解.

1.3 NetMine算法

为了求解式(4)，先对其两边取对数，将似然函数f(TS|G, G_o)转化为log似然函数log f(TS|G, G_o).更进一步，对等式右边做等价转化，改为优化增量最大化.首先假设一个空网络K，其边全部是普通边.

$ G' = \mathop {\arg \max }\limits_G \left( {\log f\left( {{\rm{TS}}|G, {G_{\rm{o}}}} \right)-\log f\left( {{\rm{TS}}|K, {G_{\rm{o}}}} \right)} \right) $

(5)

将式(2)和式(3)代入式(5)得到

$ G' = \arg \;\max \sum\limits_{i \in V, {r_k} \in {R_i}} {\sum\limits_{j \in {V_{{\rm{out}}}}\left( i \right)} {\log w\left( {i, j} \right)} } $

(6)

其中：w(i, j)=ε^－1f′(t_{i, sj}|t_{rx, i}, ε, β).为了方便，定义

$ F\left( {{\rm{TS}}|G} \right) = \sum\limits_{i \in V, {r_k} \in {R_i}} {\sum\limits_{j \in {V_{{\rm{out}}}}\left( i \right)} {\log w\left( {i, j} \right)} } $

(7)

下面研究式(7)的一些性质.

定理2  假设V为节点的集合，TS为时间切片的集合，那么F(TS|G)是子模函数(submodular function)F: ${2^w} \to \mathbb{R}$, 其中，$W \subseteq V \times V$为有向边的集合.

证明   见附录B

一般来说，子模函数的最大化问题都是NP-hard^[14]，但是笔者通过贪婪算法求得了一个近似最优解，从一个空图K开始，每次循环向图里添加一个可以使式(7)的增量最大的边，直到K里有k条边为止.根据上述思想，下面给出了NetMine算法的伪代码.

算法1   NetMine算法

Require: TS, k, G_o

G←K

for all ts∈TS

  S_ts←all possible subordinates

While |G| < k

  For all(i, j)∈G_o\G

    δ_{i, j}=0, ${M_{i, j}} \leftarrow \emptyset $

  For all ts:(i, j)∈ts

    If w(i, j)≥w(Parent_ts(j), j) then

δ_{j, i}=δ_{j, i}+w(i, j)－w(Parent_ts(j), j)

      M_{i, j}←M_{i, j}∪{ts}

$\left( {{i^*}, {j^*}} \right) \leftarrow \arg \;\mathop {\max }\limits_{\left( {i, j} \right)} {\delta _{i, j}}$

  G←G∪{(i^*, j^*)}

  For all ts∈M_{i^*, j^*}

    Parent_ts(j^*)←i^*

Return G

在代码实现中，还采用了局部更新和延迟计算^[15]的方法来加快迭代的速度.因为通常每个时间切片并不是特别大，一般仅涉及网络中的几个点，如果一次循环中NetMine算法选择的边不涉及该时间切片中任何一个节点时，那么该时间切片对下一个循环的增量贡献为零，因此在计算下一次的循环过程中，仅需要计算有影响的时间切片即可.这样，可以大幅度减少每次循环中的计算量.而延迟更新的思想则是：在每次循环过程中，优先从选择较大增量的边来进行比较.假设G₁, G₂, …, G_k是贪心算法每次循环后依次得到的网络，令Δ_e(G_i)=F(TS|G_i∪{e})－F(TS|G_i)代表第i次循环中将边e添加到网络中后得到的增量.由于F(·|G)的子模性，那么当i≤j，有Δ_e(G_i)≥Δ_e(G_j).由此，在每次循环中，边e的增量只能是单调递减的，这意味着在一次循环中增量较小的边不可能在下一次的循环中使得增量突然变大.这样，每次循环都维护一个增量的序列，每次循环时，算法可以优先从最大增量的边开始，由于在新的循环中，该增量可能会降低，那么只要重新计算增量即可，并将改变重新插入到增量序列中；如果增量不变，就选取这条边作为本次循环的最优边.

NetMine算法也比较容易进行并行化处理，从而提升计算速度及对大规模网络的适应性.比如在初始化计算每个时间切片的似然函数及更新边的增量时，容易进行大规模的并行处理，这又可以增快算法的速度.

2 实验分析 2.1 模拟数据仿真

使用模拟数据对NetMine算法的性能进行分析，并与基本方法和静态图算法进行对比验证.为了生成模拟数据，首先确定一个节点的集合V，然后使用Kronecker图^[16-17]生成真实的有向网络结构，用户之间的信息将在网络的有向边上传播, 该网络结构通常代表用户间信息传递的传递模式.考虑随机图^[18](Kronecker参数矩阵为[0.5, 0.5;0.5, 0.5])、层次社区结构^[19](Kronecker参数矩阵为[0.962, 0.107;0.107, 0.962])及随机幂律随机树^[20]3种不同的网络结构.实验中，随机选择网络中一个节点作为信息传递的起始节点，并为每条边设置一个转发概率来控制信息传播的广度，然后设置一个转发时间间隔参数来控制用户转发信息速度的快慢.这样，可以模拟生成一系列用户传递信息的数据，且网络中每条边尽可能参与一次信息的传播.然后，生成大量的随机通联数据来模拟网络中用户的背景通信数据，为使模拟数据更加符合真实数据中低信噪比的情况，用户间信息传递数据与背景通信数据比值一般小于0.01，为了方便，采用信噪比来表示这一指标.

例如在实验中，模拟生成一个具有64个节点及75条有向边的层次型社交网络，然后模拟用户的信息传递行为，生成180条信息传递记录及1.2万条背景通信数据，使得层次社交网络中全部的边均至少参与了一次信息的传递.

比较2个算法：来自文献[9-10]的静态图算法和基本算法.静态图算法的基本思想是：选取通联数据中出现次数、通联性等得到的k个边作为挖掘结果；基础方法的思想是：采用$p\left( {u, v} \right) = \sum\limits_{{\rm{ts}} \in {\rm{TS}}} {{P_{{\rm{ts}}}}\left( {u, v} \right)} $作为边的权重，即信息由边u传给边v的似然程度，并选取权重最大的k个边作为挖掘结果.

为了评估算法的性能，通过对比挖掘出的信息传递模式图G与模拟生成的网络G′进行对比来确定结果的好坏.定义查全率为挖掘出的网络中的边在真实网络G′中的比例；准确率为挖掘出的边正确的比例.希望的结果是在高准确率的基础上，尽可能地提高查全率，也就是说，如果挖掘出少量边，希望这些边尽可能都在真实的网络G′中，而随着挖掘出的边增多，准确率会逐渐下降，而查全率单调升高.

图 3给出了3种算法的仿真实验结果.从结果可以看出，信噪比为0.03时的算法性能要好于信噪比为0.004时的算法性能.这说明信噪比对于算法的性能影响还是比较明显的.在3种算法中，无论是不同的网络结构类型还是不同的信噪比，静态图算法性能都是最差的，而且当信噪比降低到0.004之后，该算法在随机图网络中已经失效，无法挖掘出可信的结果.这说明了对于这种具有时序信息数据的挖掘，传统的基于复杂网络指标的挖掘算法难以挖掘出用户的信息传递模式.通联频率高的2个节点之间的边未必是对信息传递影响最大的边，这对于常识里面认为通联频率高、数据量大的线路最重要有一定出入.这些通联频率高的边可能在某种程度上说明这条线路的两个端点之间有大量的数据要传输，然而对于网络中用户间信息的传递来说，这条边可能并不是那么重要.这说明了不同的网络结构中，由于结构的不同，有的边可能需要承载大量的数据，然而这些数据以背景通联数据为主；而用户间信息的传递可能未必会通过该边进行传播，用户间信息的传递模式网络与观测到的通联数据网络存在很大差异.

提出的NetMine算法在信噪比为0.03时与基础方法性能差别不大，都能够达到不错的性能.这两种算法对于不同的网络结构均能够在查全率为0.9左右时准确率达到0.95以上，这说明了算法的可靠性及稳定性.而当信噪比降到0.004时，基础方法已经基本失效，只有在层次社交网络结构中还具有一定性能；而NetMine算法在这3种网络结构中均可以取得最好的效果.

一般来说，如果能够获取更多的用户间信息传递数据，就能够显著提高算法性能.而本实验中，仅模拟生成了180条用户间信息传递数据，这能够说明NetMine算法在有效数据量不大的情况下，仍可以很好地挖掘出用户间信息传递的模式.

从不同的网络结构看，算法对于层次社交网络结构的挖掘效果最好，而随机图和随机树这2个随机网络的挖掘性能要稍微差一些.一个可能的原因在于：随机网络中，模拟用户传递信息的通联数据与随机数据过于类似，从而导致算法难以获取有用的信息.尽管NetMine算法性能在不同的网络结构下有一定区别，但仍然相对比较稳定，这从稳定性的角度说明了NetMine算法的可靠性.

图 4给出了算法性能与数据信噪比在不同网络结构下的关系.实验中，每个网络具有512个节点以及755条边，每次仿真中仅生成了300条用户间信息传递的数据.从图中可以看出，固定内容相关的通联数据量之后，NetMine算法和静态图算法性能都随着信噪比的提升而提高，这在3种不同的网络结构下均表现出相同的趋势.更进一步，从图中可以看出，NetMine算法的性能无论信噪比为何值，均优于静态图算法；NetMine算法性能随着信噪比的提升，在信噪比为0.4之后达到平稳的状态，BreakPoint大约在0.94左右，而且算法性能在3种网络结构下都非常稳定，这说明了算法挖掘结果的准确率和查全率都非常高，而静态图算法的性能上限在0.7左右，而且不同的网络结构下，其性能起伏比较大.

提出了延迟计算和局部更新的技术来对算法进行加速，图 5给出了算法的加速性能.

实验中采用了层次社区结构这一网络结构，图中横坐标为观测到的总数据量，纵坐标为算法运行的时长.从图中可以看出，NetMine算法中采用的延迟计算和局部更新算法能够大幅度加快搜索最优解的速度，速度提升了近7倍，而且算法耗时随通联数据量的增长而增加缓慢.相比于贪心算法，NetMine算法的耗时曲线斜率要平缓得多，处理5万条通联数据仅需要500 s左右的时间.从图 5中还可以看出，算法耗时随着通联数据量的大小几乎是线性增长，相比于多项式级别的增长来说，这将非常有利于处理大规模的通联数据.

2.2 Enron邮件集数据实验

Enron邮件集^[21]是Enron公司几千名员工办公邮箱中的邮件数据集合，最初由联邦能源局公开，由卡内基梅陇大学的William Cohen收集并用于科学研究^[22].采用了其中一个含有151名标注了员工岗位职级的版本，由于仅需要邮件通信的双方和时间，所以舍弃了邮件的内容，仅提取了邮件的发送者、接收者及邮件发送时间，将这些数据存入MySQL数据库中.将有效的邮件数据输入到NetMine算法中，设置算法的参数k=11，也就是说，仅挖掘由11条边构成的信息传递网络，结果如图 6所示.

从图 6中可以看出，Enron公司员工间信息的传递模式大部分是由高级职位的员工传向低职位的员工，这可以看作是一种指令类信息的传播过程，由高层向低级别员工传递信息.但是，也不总是这样，比如Steven Harris这名高管，他属于信息的汇聚方，信息由下属流向了他.研究Steven Harris的邮件内容和标题发现，这名高管几乎所有的邮件都是在回复他人的邮件，很少主动发送邮件，也就是说，这名高管的工作流程通常是员工将信息汇总到他这里，然后他再进行相应处理，处理后再转发出去.因此，这是一个信息汇聚的传播模式.

从结果中看，网络中用户间信息传递的模式中每条信息传递路径的长度并不是特别长，电子信息技术的发展拉近了人与人之间的距离，从高管到员工需要的转发次数并不是太多.

3 结束语

研究了通信网络中用户间信息传递模式的挖掘问题，并提出了NetMine算法对用户间信息传递模式进行挖掘.通过模拟的仿真实验发现，NetMine算法能够较好地挖掘出相应的信息传递模式，且仅利用了通信发生的时间这一属性，就取得了出乎意料的结果.通过与基于静态网络的挖掘算法对比发现，网络中流量大的边在信息的传播中所起的作用未必会很大，这对于研究网络中信息的传播、市场营销等具有很强的指导意义.将算法应用于Enron邮件集合中，分析了Enron公司中员工间信息的传递模式.

进一步的研究内容将在运行速度方面对算法进行优化，使其能够更快地处理海量数据.

附录A

定理1证明.

将通信网络中用户间信息传递模式挖掘问题规约到MAX-k-COVER问题^[14]中来.在MAX-k-COVER问题中, 给定一个有限集合W(|W|=n)和一些子集${S_1}, \cdots, {S_m} \subset W$的集合, 目标函数为

$ {F_{MC}}\left( A \right) = \left| {\bigcup\nolimits_{i \in A} {{S_i}} } \right| $

(A1)

式(A1)表示由A索引的子集覆盖W中元素的个数. MAX-k-COVER的目标是选取k个子集使得F_MC最大化.假设一个势为n的时间切片集合TS及求解的目标网络G, 使得$\mathop {\max }\limits_{\left| G \right| \le k} {F_{{\rm{TS}}}}\left( G \right) = \mathop {\max }\limits_{\left| A \right| \le k} {F_{MC}}\left( A \right)$.网络G的节点为V={1, …, m}∪{r}, 可以做一个双射$\left( {i, r} \right) \leftrightarrow {S_i}$, 那么f(TS|G, G_o)将会增加(如果将一个普通边转化为信息传递模式的边), 因此可以做如下映射: $f\left( {{\rm{TS}}|G \cup \left( {i, r} \right)} \right) \leftrightarrow {S_i}$.如果在G中增加一条边(i, r)∈G, 则选择S_i进入A, 那么一个含有k条边的网络G等价于MAX-k-COVER问题中的一个解A.因此, MAX-k-COVER的每个解A都可以等效为由式(4)定义的问题的一个解G.

附录B

定理2证明.

首先考虑单个时间切片ts, 网络$G \subset G'$, 以及一条边$e = \left( {r, s} \right) \notin G'$.假设w_{i, j}为网络G中边(i, j)的权重, w′_{i, j}为G′中边(i, j)的权重.因为$G \subset G'$, 显然对于所有的边有w′_{i, j}≥w_{i, j}≥0.如果(i, j)为网络G和G′共同的边, 那么w_{i, j}=w′_{i, j}.设${M_{A, e}} = \sum\limits_{i \in A\backslash \left\{ r \right\}} {w\left( {i, s} \right)} $, 容易得到M_{G, e}≤M_{G′, e}, 因此

$ \begin{array}{l} F\left( {{\rm{ts}}|G \cup \left\{ e \right\}} \right)-F\left( {{\rm{ts}}|G} \right) = \\ \log \left( {\frac{{{M_{G, e}} + w\left( {r, s} \right)}}{{{M_{G, e}}}}} \right) \ge \log \left( {\frac{{{M_{G', e}} + w\left( {r, s} \right)}}{{{M_{G', e}}}}} \right) = \\ F\left( {{\rm{ts}}|G' \cup \left\{ e \right\}} \right)-F\left( {{\rm{ts}}|G'} \right) \end{array} $

(B1)

由于子模函数的非负线性组合仍然是子模函数, 所以F(TS|G)=∑F(ts|G)也是子模函数.