改进PageRank算法在犯罪网络分析中的应用

余 奇

（国防科学技术大学理学院，长沙410073）

·微机软件·

改进PageRank算法在犯罪网络分析中的应用

余 奇

（国防科学技术大学理学院，长沙410073）

通过对已知部分嫌疑人的犯罪网络模型进行研究，较好解决了如何寻找潜在犯罪危险的问题。在网页排名算法PageRank的基础上，结合SNA（社会网络分析）方法，改进了PageRank算法迭代过程，有效评价了与嫌疑人沟通人员的犯罪可能性大小，为解决此类社会网络分析问题提出了一个新的思路。

PageRank算法；社会网络分析（SNA）；犯罪网络分析

1 引 言

Social Network Analysis（SNA）——社会网络分析，是研究社会网络关系的一个重要方法。在现今的大数据时代，尤其是与个人相关的电话、网络通讯信息量持续膨胀，SNA面临更大的挑战，如何在海量数据中获得有用的信息变得越来越困难。

传统的SNA方法不能考虑由于网络节点身份的特殊性带来的对于所关心问题的影响。比如，如何对已知的一名犯罪嫌疑人的社交网络进行分析找出潜在的同伙。解决问题的思路就是结合传统的SNA方法与排名算法PageRank，在已知部分嫌疑人的基础上评价与其沟通人员的犯罪可能性大小。

2 网页级别（PageRank）算法

PageRank（网页级别），这是一个经典算法，它是Google排名运算法则（排名公式）的一部分，是Google用来标识网页等级或重要性的一种方法，也是Google用来衡量一个网站好坏的重要标准之一。

它的基本思想就是：如果网页T存在一个指向网页A的链接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为：PR（T）／C（T），其中PR（T）为T的PageRank值，C（T）为T的出链数，则A的PageRank值为一系列类似于T的页面重要性得分值的累加。

设S为与A邻接节点全体构成的集合，则A的PageRank值可以表示为：

为了完善算法，保证迭代过程收敛，引入了阻尼因子d（d通常被设置成0.85），定义公式变为：

利用它对初值的不依赖性质，带入任意一组初始数据进行迭代计算，最终收敛值便是所求网站A的PageRank值。

PageRank算法虽然能作为网页排名的重要依据，但它还有一定的缺陷，其中最为突出的就是主题漂移现象：算法无法区分网页中的超链接与网页主题相关还是不相关，也就无法判断网页内容之间的相似相关性。

3 社会网络分析（SNA）方法

网络指的是各种关联，而社会网络（Social Network）即可简单地称为社会关系所构成的结构。社会网络分析（Social Network Analysis，SNA）问题起源于物理学中的适应性网络，通过研究网络关系，有助于把个体间关系、“微观”网络与大规模的社会系统的“宏观”结构结合起来，通过数学方法、图论等定量分析方法，对复杂的社会网络进行抽象化分析，得到相应结论。

社会网络分析的角度是多方面的，主要包括：中心性分析、凝聚子群分析、核心——边缘结构分析等等。

3.1 中心性分析

个体中心度（Centrality）度量个体处于网络中心的程度，反映该点在网络中的重要性程度。因此一个网络中有多少个节点，就有多少个个体中心度。除了计算网络中个体的中心度外，还可以计算整个网络的集中趋势，简称为中心势（Centralization）。与个体中心度刻画的个体特性不同，网络中心势刻画的是整个网络中各个点的差异性程度，因此一个网络只有一个中心势。

3.2 凝聚子群分析

当网络中某些行动者之间的关系特别紧密，以至于结合成一个次级团体时，这样的团体在社会网络分析中被称为凝聚子群。分析网络中存在多少个这样的子群，子群内部成员之间关系的特点，子群之间关系特点，一个子群的成员与另一个子群成员之间的关系特点等就是凝聚子群分析。由于凝聚子群成员之间的关系十分紧密，因此也将凝聚子群分析形象地称为“小团体分析”。

3.3 核心——边缘结构分析

核心——边缘（Core—Periphery）结构分析的目的是研究社会网络中哪些节点处于核心地位，哪些节点处于边缘地位。核心边缘结构分析具有较广的应用性，可用于分析精英网络、科学引文关系网络以及组织关系网络等多种社会现象中的核心——边缘结构。

4 改进的PageRank算法

现考虑基于社会网络分析下的PageRank算法改进措施。由于算法对于初值并不敏感，只要在迭代过程中引入对于算法的修正即可。

对于一个已知部分犯罪嫌疑人的犯罪团伙构成的社交网络，要计算一个节点y的PR值，记与y有联系的已知犯罪嫌疑人集合为Sy，其他联系人员集合Uy，通讯记录中与犯罪事实相关的通讯主题集合Ts，与犯罪事实无关的通讯主题集合Tu。设已知犯罪嫌疑人的PR值恒为1，对于其他节点的PR值，迭代计算式如下：

其中a1（x，y），a2（x，y），a3（x，y），a4（x，y）为迭代系数，且满足

由SNA方法，确定各个系数的表达式如下：

其中，ni分别为各个集合与y之间通讯的次数，D（y）为节点y的度，ms（y）为节点y谈论与犯罪事实有关话题的总次数。

有了迭代关系式和关系式中的各项系数，就可以构造迭代算法来计算每个节点的PageRank值作为该节点成为一名犯罪嫌疑人的可能性度量。

5 计算实例

计算实例选自2012年美国大学生数学建模竞赛C题。在一家为银行、信用卡公司开发软件的公司中，根据可靠消息，有部分员工正在密谋盗用公款，损坏公司的利益。经过长期跟踪与调查，调查人员已经确定策划阴谋的一些成员，但是为了在逮捕嫌疑人之前找出其它犯罪成员和组织的领导人。现有数据为：公司中83名员工的名字，400条他们之间的信息，以及他们主要谈论的15个主题。而且，在这83名员工中，已知有7个是已知的嫌疑人，8个是已知的非嫌疑人，在15个主题中，已经确定有3个是与犯罪事实相关的。参照给定的数据建立图论模型。83名员工就相当于一个网络中83个节点，400条他们之间的信息就相当于他们之间所连接的边，每条边都有自己所代表的主题，其中有一些主题被认为是可疑的。所以就是要通过分析这些数据来确定这些人里面，谁最有可能是嫌疑人。

按照改进的PageRank算法进行分析，最终得到结果如图1所示。

图1 PR值与节点之间的对应关系图

最终得到PR值排在前十位的节点如表1所示。

这样就得到了未知人员参与犯罪的可能性排名，然后可以依次做进一步的调查。

表1 PR值排在前十位的节点

6 结束语

改进的PageRank算法很好的解决了在已知部分嫌疑人的犯罪网络模型中如何寻找潜在犯罪危险的问题，综合多方面因素，为此类犯罪行为的识别与分析提供了一个新思路。但是，与此同时，作为一个现实问题的数学模型，其中不免有很多简化和不足，尤其是像社会关系这样的复杂网络，在表面信息的背后很有可能隐藏着很多不容忽视的因素。所以犯罪网络分析的结果只能作为一个参考标准，真正的犯罪嫌疑人的确定还依赖于更多更深入的调查。

［1］王德广，周志刚，梁旭.PageRank算法的分析及其应用［J］.计算机工程，2010，23（22）：291-292.

［2］林聚任.社会网络分析［M］.北京：北京师范大学出版社，2009.

［3］姚文琳，刘文.一种基于本体的PageRank算法的改进策略［J］.计算机工程，2009，35（6）：50-51.

［4］姚金隆，王成良.原创优先的搜索引擎排序算法［J］.计算机工程，2008，34（18）：85-86.

［5］Xu J，H Chen.Criminal network analysis and visualization［J］.Communications of the ACM，2005，48（6）：100-107.

Application of Im proved PageRank Algorithm in Crim inal Analysis

YU Qi
（College of Science，National University of Defense Technology，ChangSha 410073，China）

Through the study on criminal network model，the problem of digging potential criminal menace is solved preferably.Combining with SNA（social network analysis），the iterative process of PageRank algorithm is improved.As a result，aman who contacts the suspicious is successfully evaluated as a real criminal.

PageRank Algorithm；Social Network Analysis（SNA）；Criminal Analysis

10.3969／j.issn.1002-2279.2014.04.018

TP3

：A

：1002-2279（2014）04-0056-03

余奇（1994-），男，河南信阳人，硕士研究生在读，主研方向：系统分析与集成。

2013-10-11