一种相对重要节点挖掘方法及其在犯罪网络中的应用

A Relatively Important Node Mining Method and Its Application in Criminal Networks

摘要: 网络科学中相对重要节点的挖掘具有重要的应用价值，例如，通过已知犯罪分子查找其他犯罪分子。为此，文中提出了一种基于带重启随机游走的相对重要节点挖掘方法，并结合犯罪网络的两个特征来把该方法应用于犯罪网络的挖掘：根据犯罪分子会隐藏自己的特点对随机游走的初值进行设计；根据犯罪分子之间的通信人物很有可能就是罪犯的特点对随机游走的概率转移矩阵进行改进。最后将提出的方法同4个经典的相对重要节点挖掘指标进行对比，同时通过实际的犯罪网络来进行实验和分析，结果表明，文中的算法比经典的方法更能准确预测出犯罪分子。

Abstract: The mining of relatively important nodes in network science has important application value, for example, searching for other criminals through known criminals. For this reason, this paper proposes a relatively important node mining method based on random walk with restart, and combines the two characteristics of criminal networks to apply this method to criminal network mining: Design the initial value of the random walk according to the characteristic of criminals hiding themselves; Improve the probability transition matrix of random walk based on the characteristic of the communication between criminals who are likely to be criminals. Finally, the proposed method is compared with four classic relatively important node mining indicators. At the same time, experiments and analysis are carried out through the actual criminal network. The results show that the algorithm in this paper can predict criminals more accurately than the classic method.

1. 引言

节点的重要性研究在复杂网络领域一直备受关注，具有非常重要的意义，其中最主要的作用是找出网络中的核心节点 [1] - [6]。但在实际生活中，通常是已知网络中的部分节点为重要节点，利用这些已知的重要节点和网络的拓扑结构，来计算其余节点相对于这些已知重要节点的重要性，从而找出相对重要的节点，这类问题的研究叫做相对重要节点挖掘 [7]。相对重要节点挖掘的方法可以成功地应用于犯罪网络的调查，如通过已知罪犯查找剩余罪犯 [7] [8] [9]。近几年相对重要节点的挖掘也成为了复杂网络科学中的热门研究方向之一，且有着广泛的应用，不仅可以用于犯罪网络，还可以应用于通过已知致病基因查找未知致病基因 [10]，在疾病传播中通过已知感染节点查找或预测风险节点并及时监控隔离等 [11]。

犯罪网络可以理解为在法律范围之外运作的网络，其网络成就是以牺牲其他个人、团体或社会为代价的 [12] [13]。犯罪网络遍及全球，对国防和安全产生重大影响。犯罪网络试图渗透合法企业和政府，进而获取暴利。因此，面对一些犯罪网络，如儿童色情制品、海上盗版、暗网、恐怖组织、毒品交易、地下洗钱等对社会造成重大损害，需要积极采取措施对其进行打击及破坏 [14] [15]。通过犯罪网络分析可以发现一些并不直观的线索，来协助公安机关破案，从而达到打击犯罪行为、维护社会稳定的目的。

在简单的犯罪网络中确定犯罪主体，犯罪分子相对较少，人脉关系很少，这通常可以通过肉眼来完成。随着时代的进步，犯罪行为以及犯罪网络变得越来越复杂，调查个人和团体犯罪需要大量资源，并且需要越来越多的领域知识、技能和时间 [16]。研究人员发现犯罪网络也可以理解为社交网络，因此可以利用社会网络分析的方法寻找犯罪网络的核心节点。但通常，寻找犯罪网络的核心节点是对犯罪网络掌握了大量信息后才能做的事。在犯罪网络分析的初始阶段，如何利用少量已知的犯罪分子和与其联系的网络知识来挖掘剩下的罪犯也是非常有价值的事。

2. 相对重要节点挖掘以及犯罪网络研究现状

相对重要节点挖掘的工作开始于Chang等 [17] 在2000年提出的一种个性化HITS算法。接着，Haveliwala等 [18] 和Jeh等 [19] 也分别提出了各自的个性化PageRank算法。随后White [7] 定义了相对重要节点挖掘问题，总结了一些相对重要节点挖掘算法，并给出一套相对重要节点挖掘的通用框架。Wang等 [20] 提出了基于随机游走的方法在相对重要节点挖掘的应用。Jocelyn [21] 对传统中心性指标在子网中的应用方法进行了总结归纳。朱军芳等人 [22] 整理了基于结构特征指标和基于随机游走指标的两套指标和方法，并对其中各种方法指标进行比较，对一些开放性问题和发展趋势进行了讨论。

其中文献 [22] 将相对重要节点的方法归为两大类，一类是基于结构特征的，一类是基于随机游走的，其实验表明基于随机游走的方法整体优于基于结构特征的方法；但基于随机游走的方法仍存在一些不足，如不能有效的利用已知重要节点在网络中位置的信息；对不同的已知重要节点集，仍用同样的概率转移矩阵进行随机游走。

在犯罪网络研究方面，目前，利用节点重要性方法对犯罪网络进行的研究有很多。如，自1991年以来，就开始有人使用社交网络分析法来提取犯罪情报 [23]。随后在2002年Kreb博士在国际社会网分析年会上分享了911事件的劫机恐怖分子及其联系人构成的犯罪网络 [24] 后，这种方法在犯罪网上得到了广泛的应用；Carley [25] 等针对恐怖组织结构和成员难以分析的问题，开发了一种工具NETEST用以模拟恐怖组织结构；2003年波士顿大学 Stephen P. Borgatti [26] 定义了特殊的社会网络核心人员挖掘问题并提出了挖掘算法。2005 年，Chen等人 [27] 基于移除核心成员对网络造成的破坏程度来挖掘犯罪网络的核心成员。2006年，S.P Borgatti [28] 利用社会网络的概念，分析数据来挖掘犯罪网络的核心成员。2014年，D’Orsogna [29] 对基于核心节点移除分析网络的破坏性的方案进行深入地调查和分析。2017 年，Taha [30] 等人引出最小生成树的概念，挖掘犯罪网络的核心领导者。Magalingam [31] 通过改进介数中心性指标来挖掘犯罪网络中的剩余罪犯。Troncoso等人 [5] 为了更加准确的识别犯罪嫌疑人，把个人犯罪倾向纳入节点重要性评估。

虽然犯罪网络方面的研究已取得不少的成果，但大多都是在已知整个犯罪网络信息的情况下来挖掘犯罪集团核心人物的。而在犯罪网络分析的初始阶段，更应该考虑利用少量的犯罪信息，来挖掘更多的信息。如：利用少量的已知罪犯和罪犯所属网络的结构信息，来挖掘剩余罪犯。至今，这类研究较少。

因此，本文提出了一种基于带重启随机游走的相对重要节点挖掘算法。随机游走是研究网络结构和特性的一种重要方法。相对重要节点挖掘中的随机游走是指粒子从已知重要节点出发，以一定的概率游走到它的邻居节点，然后再以一定的概率游走到邻居节点的邻居节点，这样反复达到平衡稳态后结束游走。在本文提出的游走方法中，粒子不仅有概率向邻居节点游走，还有一定概率跳回已知重要节点重新开始游走，而且当粒子游走遍历完整个网络后便结束游走，该方法更能有效的利用已知重要节点在网络中位置的信息。本文将此算法应用于犯罪网络，利用犯罪网络的特点，对随机游走的初值和概率转移矩阵进行设计。

3. 问题描述以及方法介绍

对于N个节点构成的网络 $G\left(V,E\right)$，其中N₁个构成重要节点集V₁，N₂个节点构成非重要节点集V₂，重要节点集V₁是由已知重要节点集R和未知重要节点集U组成。未知重要节点集U和非重要节点集V₂组成目标节点集T。相对重要节点挖掘是在目标节点集T中找到相对于已知重要节点集R较为重要的top_L个相对重要节点。

由公式表达如下：

$\begin{array}{l}V=V_1\cup V_2,V_1\cap V_2=\varnothing \\ V_1=R\cup U,R\cap U=\varnothing \\ T=U\cup V_2\end{array}$ (1)

本文提出的方法是基于带重启随机游走的相对重要节点挖掘方法，并将其根据犯罪网络的特点，对随机游走的初值和概率转移矩阵进行设计。步骤如下：

1) 将带重启的随机游走方法用于相对重要节点挖掘。

2) 利用犯罪网络中犯罪分子会有意识地隐藏自己的特点，即罪犯会更加偏向于和不易于暴露的节点连接，来设计随机游走的初值概率分布P₀。

3) 利用犯罪网络中罪犯之间的通信人物很有可能就是罪犯的特点，对概率转移矩阵W进行改进。

3.1. 带重启随机游走的相对重要节点挖掘方法

带重启的随机游走RWR (Random Walk with Restart) [32]，从一个节点开始随机游走，在每一步游走时面临两个选择：或者移动到一个随机选择的邻点，或者跳回起点，仅通过一个参数 $\alpha$ 来调节节点跳回起点的概率，在多次模拟第一步随机游走实验过后，会得到这个节点进行第一步随机游走后的稳定概率分布：

$P^1=\left(1-\alpha \right)P^0+\alpha W^{\text{T}}{P}^0$ (2)

P¹是网络中起始节点随机游走一步到所有节点的概率分布向量，P⁰是一个初始概率分布向量，P⁰中除了对应的随机游走起始节点(已知重要节点)数值设置为1，其余所有值都设置为0，W是概率转移矩阵。多步随机游走后的概率分布P^t+1可以描述为：

$P^{t+1}=\left(1-\alpha \right)P^0+\alpha W^{\text{T}}{P}^t$ (3)

带重启随机游走的结束游走条件是当节点遍历完整个网络后结束，即P^t+1向量中的所有值都大于0时候，我们认为它已经遍历完整个网络，这是RWR方法能设置初始概率分布P⁰的重要原因。若让随机游走达到稳态才停止，那么无论如何设置初始概率分布P⁰，最终得到的节点的排名是不会发生变化的。最终得到的向量P^t+1即为相对重要性向量，代表图中所有节点对已知重要节点的相对重要性。如果已知重要节点集中有多个节点，那么我们将根据3.2节中的方法确定如何对初值进行设定，同时从多个已知重要节点开始随机游走，最终得到的向量P^t+1即为相对重要性向量，代表图中所有节点对已知重要节点集的相对重要性。

3.2. 初始概率分布P⁰的设计

已知重要节点在网络中的位置是设置初始概率分布P⁰的关键，本文认为在网络中越重要的节点，应赋予对应节点更大的概率分布初值，那么在网络中与初值较大节点直接相连的节点，在随机游走后，越可能获得比与初值较小节点直接相连节点更大的概率分布分数。

为了避免犯罪网络数据的不完整或有多余节点和边所带来的误差，我们希望得到一个节点重要性的大致的排名即可。而k-shell方法 [16] 恰好能对节点进行一个大致的分层，得到我们想要的结果，因此我们采用k-shell方法来计算节点重要性。

k-shell方法是通过递归的移除网络中所有节点度值不大于k的节点，并将这些节点归为k-shell，剩余网络中不含有度值小于或等于k的节点时，再递归移除度值不大于k + 1的节点，归为k + 1-shell，直到网络中所有节点被移除。

犯罪分子通常会有意识的隐藏自己，因此，罪犯会倾向于和在显性指标下重要程度较低的节点相连。而k-shell方法是基于节点度的大小进行分层的方法，度指标是一个显性指标，因此本文设定越外层的节点初始概率分布分数越大。

在用k-shell方法分层的情况下，本文认为同层的节点拥有相同的重要性，每一层内节点的重要性为该层的基准重要性，属于第i层内节点的基准重要性记为Z_i。

若一个网络 $G\left(V,E\right)$ 用k-shell方法被分为了t层，第i层中的节点个数为 $n_i\left(1\le i\le t\right)$，令 $N={\displaystyle {\sum }_{1\le i\le t}{n}_i}$， $n_{t+1}=1$ (使t层节点的节点重要性不为0)， $N_i={\displaystyle {\sum }_{i\le j\le t+1}{n}_j\left(1\le i\le t+1\right)}$,则第i层中的基准重要性Z_i的计算

公式如下：

$Z_i=N_{i+1}/N$ (4)

因此利用k-shell方法得到节点v的重要性为 $I\left(v\right)=Z_i,\left(v\in i\text{-shell}\right)$。于是初始概率分布值如下：

$P_v^0=\{\begin{array}{l}I\left(v\right),v\in R\\ 0,v\notin R\end{array}$ (5)

3.3. 带游走偏好的概率转移矩阵W的设计

White和Smyth指出，节点相对重要性计算指标和方法并非全局重要性指标在子网络中的简单应用，而是对已知重要节点的偏好设计，偏好设计是节点相对重要性方法和指标设计的核心 [7]。众多文献表明，介数中心性对于确定犯罪网络的核心节点是非常重要的指标 [33] [34]。在犯罪网络中，根据罪犯之间的通信人物很有可能就是罪犯的特点，本文设计了一个在犯罪网络中寻找相对重要节点的偏好策略：在随机游走时，更倾向于向位于已知重要节点对(r₁, r₂)，之间的中间节点b进行游走。

传统的概率转移矩阵T是根据邻接矩阵A得到的，在一个无向无权网络 $G\left(V,E\right)$，邻接矩阵A中的元素A_ij的含义如下：

$A_{ij}=\{\begin{array}{l}1,如果顶点i和顶点j之间存在边\\ 0,其他\end{array}$ (6)

则概率转移矩阵W的生成规则如下：

$W_{ij}=\frac{A_{ij}}{{{\displaystyle {\sum }_{0\le i<n}A}}_{ij}}$ (7)

概率转移矩阵有以下两个特性：

$\begin{array}{l}0\le W_{ij}\le 1\\ {\displaystyle {\sum }_{0\le i<n}{W}_{ij}=1}\end{array}$ (8)

其中W_ij表示节点从节点j位置游走时向节点i位置游走的概率，若想增大游走到节点b的概率，增大 $A_{bj}\left(0\le j<n\right)$ 即可。

若存在这样的中间节点b，将修改邻接矩阵A中的元素：

$A_{bj}\left(0\le j<n\right)=\{\begin{array}{l}2,如果原A_{bj}=1\\ 0,如果原A_{bj}=0\end{array}$ (9)

利用中间节点集B中所有节点修改完邻接矩阵A后，再根据修改后的矩阵A按照概率转移矩阵生成规则重新计算的得到新的带游走偏好的概率转移矩阵W，再利用3.4中的方法计算目标节点的相对重要性。

判定节点位于已知重要节点对之间的条件如下：

$sd\left(t,r_1\right)+sd\left(t,r_2\right)=sd\left(r_1,r_2\right)$ (10)

其中， $sd\left(t,r_1\right)$ 表示目标节点t到已知重要节点r₁的最短距离，当且仅当目标节点t距离已知重要节点r₁的最短距离与已知重要节点r₂的最短距离之和等于r₁与r₂之间的最短距离时，便认为它是一个中间节点。已知重要节点也可能是一个中间节点。

3.4. 带游走偏好的概率转移矩阵W的设计

将带重启的随机游走方法(RWR)结合犯罪网络的特点，用3.2和3.3中的方法改进RWR算法中的初始概率分布和概率转移矩阵后应用于犯罪网络中的相对重要节点挖掘，本文简称这种方法为RWR*算法。

RWR*算法伪代码如下：

4. 实验

4.1. 评价指标

本文采用精确率对相对重要节点挖掘的结果进行比较，该指标考虑目标节点集中相对重要性总和排在前L位的节点是否预测准确，公式如下：

$\text{precision}=N_r/L$ (11)

其中，precision为预测的准确率，N_r为相对重要性排名前L个节点在未知重要节点集中出现的个数。

4.2. 数据集

以911恐怖袭击事件真实犯罪关系网络为数据集 [24]，该网络有37个节点，85条边。该数据是Krebs通过案件公开的19个已死亡的劫机者展开调查，分析整理得到的。其中节点编号为1、4、35、36、37对应的人物劫持了11号航班，节点编号为1的是本机上的核心犯罪人员，也是本次恐怖袭击事件的主策划者；节点编号为2、17、32、28、31对应的人物劫持了175号航班，节点编号为2的是本机上的核心犯罪人员；节点编号为16、18、15、22、21对应的人物劫持了77号航班，节点编号为16的是本机上的核心犯罪人员；节点编号为14、30、29、27对应的人物劫持了93号航班，节点编号为14的是本机上的核心犯罪人员。其他人员没有直接参与本次恐怖袭击事件，节点编号为10的是辅助前四个团伙完成任务的核心犯罪分子。本文认为该网络有19个重要节点，10号节点未直接参与本次袭击。该数据的网络结构及分工如图1所示。

4.3. 实验比较与分析

实验方法，本文进行三轮实验，每轮分别抽取重要节点集中的三个、四个、五个节点作为已知重要节点集，把剩下的未知重要节点的个数作为我们的预测的个数，进行20次独立实验，最后对预测的准确性结果取均值。本文会把10号节点考虑为非重要节点和重要节点分别进行实验。

其中通过抽取四个节点作为已知重要节点集来确定RWR*方法中超参数：随机游走重启概率。

图2表明，当 $\alpha =0.7$ 时，RWR*方法的准确率最佳。

犯罪节点挖掘实验的对比方法为常用效果最好的PPR [18]、PHIST [7]、KSMar [7] 和Katz [35]，其中

Figure 1. Schematic diagram of the division of labor of the criminals in the 911 terrorist attack

图1. 911恐怖袭击事件犯罪分子分工示意图

Figure 2. RWR* algorithm hyperparameter experiment

图2. RWR*算法超参数的实验

PPR方法中的 $s=0.75$，PHIST中的 $s=0.1$，KSMar中 $K=3$，Katz中 $\phi =0.0001$，前三种方法是文献 [22] 实验中基于随机游走效果最好的方法，Katz是文献 [22] 实验中基于结构特征效果最好的方法。

从图3的实验结果可以看出，本文提出的RWR*方法在911犯罪网络数据上更能准确的利用已知罪犯挖掘剩余罪犯。无论在已知三名、四名、五名罪犯的情况下都是表现最好的算法。且在三次实验的平均值准确率上，RWR*算法比平均准确率排第二的算法高出4个百分点左右。

PPR算法与本文的RWR*算法最大的区别是，PPR算法当概率分布达到稳态时才终止随机游走，无论如何改变初始概率分布，最终节点概率分布的排名都不会发生变化，因此RWR*算法较PPR更能有效利用已知重要节点提供的信息。

Figure 3. Comparison of relatively important node mining experiments

图3. 相对重要节点挖掘实验对比

K步马尔可夫方法(KSMar)，利用前K步随机游走后的概率分布的累积总和来衡量节点的相对重要性。K步马尔可夫方法公式如下：

$I\left(t|R\right)=\left[TP+T^{2}P+\cdots +T^{K}P\right]$ (12)

其中TP为第一步随机游走后得到的概率分布，T²P代表第二步随机游走后得到的概率分布，离初始随机游走越近的节点会获取越高的相对重要性，即与犯罪分子越亲密的人嫌疑越大。

而本文提出的改进后的带重启的随机游走方法，更能考虑已知重要节点的重要性，根据犯罪网络的特点对不同的已知重要节点集设计不同的概率转移矩阵，用于挖掘罪犯时效果会更佳。

5. 结束语

本文提出了一种新的带重启随机游走的相对重要节点挖掘方法，并在应用于犯罪网络中时，根据犯罪网络的特点对随机游走方法的初值概率分布和概率转移矩阵进行改进：根据犯罪分子会隐藏自己的特点对随机游走的初值进行改进，根据罪犯之间的通信人物很有可能就是罪犯的特点对随机游走的概率转移矩阵进行改进。最后通过911恐怖袭击事件犯罪网络实验证明，在符合一定条件的犯罪网络中，本文提出的方法比经典的相对重要节点挖掘方法更能准确地挖掘出罪犯。在未来的工作中，仍有许多值得深入研究的地方：1) 如何利用已知重要节点挖掘得到的相对重要节点作为已知重要节点进一步挖掘。2) 本文是在等概率随机游走转移矩阵的基础上进行修改的，还可以尝试用不等概率随机游走概率转移矩阵进行研究，并对不等概率随机游走概率转移矩阵进行修改。3) 在使用相对重要节点挖掘方法实际落地应用时，对于不同类型的网络应该设计不同的偏好设计。

NOTES

^*通讯作者。