基于关键节点识别算法的重点人分析

韩奕; 孙百兵; 王军国; 杜彦辉

doi:10.13700/j.bh.1001-5965.2022.0588

基于关键节点识别算法的重点人分析

doi: 10.13700/j.bh.1001-5965.2022.0588

韩奕^{1, 2},
孙百兵¹,
王军国^{1, 3},
杜彦辉^1, ,

1.
中国人民公安大学信息网络安全学院，北京 100038
2.
公安部第一研究所，北京 100049
3.
南京森林警察学院，南京 210023

基金项目: 中央高校基本科研业务费专项资金(2021JKF105)；中央高校重大科研业务费专项资金(2021FZB13)

详细信息

通讯作者:
E-mail：dyh6889@126.com

中图分类号: V221⁺.3；TB553
计量
- 文章访问数: 221
- HTML全文浏览量: 100
- PDF下载量: 7
- 被引次数: 0
出版历程
- 收稿日期: 2022-07-05
- 录用日期: 2022-09-16
- 网络出版日期: 2022-12-15
- 整期出版日期: 2024-07-18

Target person analysis based on critical node recognition algorithm

HAN Yi^{1, 2},
SUN Baibing¹,
WANG Junguo^{1, 3},
DU Yanhui^{1
, ,}

1.
College of Information and Network Security，People’s Public Security University of China，Beijing 100038，China
2.
The First Research Institute of the Ministry of Public Security of PRC，Beijing 100049，China
3.
Nanjing Forest Police College，Nanjing 210023，China

Funds: The Fundamental Research Funds for the Central Universities (2021JKF105); Major Program of the Fundamental Research Funds for the Central Universities (2021FZB13)

More Information

Corresponding author: E-mail：dyh6889@126.com

摘要

摘要:
关键节点识别算法是社交网络研究领域的重要分支，但现有研究成果大多对数据的多样性、完整性、可用性等依赖程度高，导致在公安机关重点人分析场景中适用性较低。因此，对静态网络拓扑结构进行量化表示，同时结合局部最优算法和全局最优算法重新定义关系度指标，再基于该指标构建特征矩阵，提出适用于公安部门重点人分析的特征向量中心性（REC）算法。依托公开数据集、2部影视剧人物关系网络、境外社交平台账号网络和国内某诈骗团伙5个数据集，从网络传播能力、抗打击弹性和重点人分析结果一致性3个维度证实所提算法的有效性，相较于其他传统挖掘算法能准确识别社交网络重要节点，具有较为广泛的应用场景。
- 关键节点 /
- 社交网络 /
- 关系度 /
- 特征矩阵 /
- 肯德尔
Abstract:
The critical node recognition algorithm is an important branch in the field of social network research. However, most of the existing research results highly depend on the diversity, integrity, and availability of data. Therefore, they are less applied in the scene of target person analysis by public security organs. To address this issue, in this paper, a static network topology was first quantified, and a relationship degree index was redefined by the local and global optimization algorithms. Based on the index, a characteristic matrix was then constructed. Ultimately, a relationship eigenvector centrality (REC) algorithm suitable for target person analysis by public security organs was proposed. Based on five datasets such as the public dataset, the relationship network of characters in two TV series, the account network of overseas social platforms, and a Chinese fraud gang, the effectiveness of the proposed algorithm was verified from three dimensions of network communication ability, anti-attack elasticity, and the result consistency of target person analysis. Compared with other conventional data mining algorithms, the proposed one can identify the critical nodes in social networks accurately and can be widely applied.
- critical node /
- social network /
- relationship degree /
- characteristic matrix /
- Kendall

HTML全文

图 1 示例网络

Figure 1. Network example

下载: 全尺寸图片幻灯片

图 2 基于SI模型的网络传播实验结果

Figure 2. Experimental results of network communication based on SI model

下载: 全尺寸图片幻灯片

图 3 小范围扩散实验

Figure 3. Small-scale diffusion experiments

下载: 全尺寸图片幻灯片

图 4 删除重要节点后网络抗打击弹性下降效果

Figure 4. Anti-attack elasticity reduction of network after deleting critical nodes

下载: 全尺寸图片幻灯片

表 1 5个真实网络的基本拓扑特性

Table 1. Basic topology features of five real networks

网络	N	E	<k>	k_max	k_smax	<d>
Zachary^[15-16]	34	78	4.5882	17	4	2.2706
Harry Potter	648	1738	4.802	93	10	3.8338
《红楼梦》	285	1657	11.628	127	16	2.615
Twitter	81	960	21.63	65	15	1.762
诈骗团伙	36	82	4.556	17	7	3.2095

下载: 导出CSV

表 2 诈骗团伙重点人判决文书（部分）^[23-24]

Table 2. Sentencing documents of target persons in fraud gang (part)^[23–24]

重点人	判决量刑
刘某	判处有期徒刑五年，并处罚金人民币五万元
谢某青	判处有期徒刑五年，并处罚金人民币五万元
谢某江	判处有期徒刑四年八个月，并处罚金人民币四万五千元
刘某桃	判处有期徒刑四年六个月，并处罚金人民币四万元
谢某	判处有期徒刑四年，并处罚金人民币三万元
戚某萍	判处有期徒刑三年八个月，并处罚金人民币二万五千元
刘某亮	判处有期徒刑三年八个月，并处罚金人民币二万五千元
陈某	判处有期徒刑三年，并处罚金人民币一万元
曾某	判处有期徒刑三年，缓刑四年，并处罚金人民币一万元

下载: 导出CSV

表 3 肯德尔系数对比结果

Table 3. Kendall coefficient comparison results

算法	Zachary^[15-16]	Harry Potter	《红楼梦》	Twitter	诈骗团伙
全局最优EB算法	0.327	0.067	0.211	0.289	0.356
特征矩阵算法	0.3	0.289	0.246	−0.067	0.422
局部最优Jaccard算法	0.341	−0.111	0.2	0.411	0.211
REC算法	0.404	0.344	0.321	0.467	0.477

下载: 导出CSV

参考文献(24)

[1]	CAMACHO D, PANIZO-LLEDOT Á, BELLO-ORGAZ G, et al. The four dimensions of social network analysis: An overview of research methods, applications, and software tools[J]. Information Fusion, 2020, 63: 88-120. doi: 10.1016/j.inffus.2020.05.009
[2]	LIAO H, MARIANI M S, MEDO M, et al. Ranking in evolving complex networks[J]. Physics Reports, 2017, 689: 1-54. doi: 10.1016/j.physrep.2017.05.001
[3]	LÜ L Y, CHEN D B, REN X L, et al. Vital nodes identification in complex networks[J]. Physics Reports, 2016, 650: 1-63. doi: 10.1016/j.physrep.2016.06.007
[4]	LIU J G, REN Z M, GUO Q, et al. Node importance ranking of complex networks[J]. Acta Physica Sinica, 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
[5]	任晓龙, 吕琳媛. 网络重要节点排序方法综述[J]. 科学通报, 2014, 59(13): 1175-1197. doi: 10.1360/972013-1280 REN X L, LYU L Y. Review of ranking nodes in complex networks[J]. Chinese Science Bulletin, 2014, 59(13): 1175-1197(in Chinese). doi: 10.1360/972013-1280
[6]	许慧. 社会网络中节点重要性度量方法研究[D]. 哈尔滨: 哈尔滨工程大学, 2020. XU H. Research on nodes importance measurement in social networks[D]. Harbin: Harbin Engineering University, 2020(in Chinese).
[7]	UGANDER J, BACKSTROM L, MARLOW C, et al. Structural diversity in social contagion[J]. Proceedings of the National Academy of Sciences of the United States of America, 2012, 109(16): 5962-5966.
[8]	顾亦然, 朱梓嫣. 基于LeaderRank和节点相似度的复杂网络重要节点排序算法[J]. 电子科技大学学报, 2017, 46(2): 441-448. doi: 10.3969/j.issn.1001-0548.2017.02.020 GU Y R, ZHU Z Y. Node ranking in complex networks based on LeaderRank and modes similarity[J]. Journal of University of Electronic Science and Technology of China, 2017, 46(2): 441-448(in Chinese). doi: 10.3969/j.issn.1001-0548.2017.02.020
[9]	LALOU M, TAHRAOUI M A, KHEDDOUCI H. The critical node detection problem in networks: A survey[J]. Computer Science Review, 2018, 28: 92-117. doi: 10.1016/j.cosrev.2018.02.002
[10]	YAN G, ZHOU T, HU B, et al. Efficient routing on complex networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2006, 73(2): 046108.
[11]	郑文萍, 吴志康, 杨贵. 一种基于局部中心性的网络关键节点识别算法[J]. 计算机研究与发展, 2019, 56(9): 1872-1880. doi: 10.7544/issn1000-1239.2019.20180831 ZHENG W P, WU Z K, YANG G. A novel algorithm for identifying critical nodes in networks based on local centrality[J]. Journal of Computer Research and Development, 2019, 56(9): 1872-1880(in Chinese). doi: 10.7544/issn1000-1239.2019.20180831
[12]	FREEMAN L C. Centrality in social networks conceptual clarification[J]. Social Networks, 1978, 1(3): 215-239. doi: 10.1016/0378-8733(78)90021-7
[13]	FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35. doi: 10.2307/3033543
[14]	STEPHENSON K, ZELEN M. Rethinking centrality: Methods and examples[J]. Social Networks, 1989, 11(1): 1-37. doi: 10.1016/0378-8733(89)90016-6
[15]	汪小帆, 李翔, 陈关荣. 复杂网络理论及其应用[M]. 北京: 清华大学出版社, 2006. WANG X F, LI X, CHEN G R. Complex network theory and its application[M]. Beijing: Tsinghua University Press, 2006(in Chinese).
[16]	ZACHARY W W. An information flow model for conflict and fission in small group[J]. Journal of Psycholog, 1975, 12: 328-383.
[17]	周涛, 韩筱璞, 闫小勇, 等. 人类行为时空特性的统计力学[J]. 电子科技大学学报, 2013, 42(4): 481-540. doi: 10.3969/j.issn.1001-0548.2013.04.001 ZHOU T, HAN X P, YAN X Y, et al. Statistical mechanics on temporal and spatial activities of human[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(4): 481-540(in Chinese). doi: 10.3969/j.issn.1001-0548.2013.04.001
[18]	XU W B ,LI W T,RUAN S G. Spatial propagation in an epidemic model with nonlocal diffusion: The influences of initial data and dispersals[J]. Science China (Mathematics), 2020, 63(11): 2177-2206.
[19]	BONACICH P. Factoring and weighting approaches to status scores and clique identification[J]. The Journal of Mathematical Sociology, 1972, 2(1): 113-120. doi: 10.1080/0022250X.1972.9989806
[20]	DEREICH S, MÖRTERS P. Random networks with sublinear preferential attachment: Degree evolutions[J]. Electronic Journal of Probability, 2009, 14: 1222-1267.
[21]	VRAGOVIĆ I, LOUIS E, DÍAZ-GUILERA A. Efficiency of informational transfer in regular and complex networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2005, 71(3): 036122. doi: 10.1103/PhysRevE.71.036122
[22]	LATORA V, MARCHIORI M. A measure of centrality based on network efficiency[J]. New Journal of Physics, 2007, 9(6): 188. doi: 10.1088/1367-2630/9/6/188
[23]	浙江省长兴县人民法院. 刘罗亮郑顺平刘发英等诈骗案: 浙江省长兴县人民法院刑事判决书(2020)浙0522刑初15号[EB/OL]. (2020-08-15) [2022-07-05]. https://wenshu.court.gov.cn/. Zhejiang Changxing County People’s Court. Liu Luoliang Zheng Shunping Liu Faying el al. Fraud case: Criminal judgment of the People’s Court of Chanagxing County, Zhejiang Province (2020) Zhe 0522 Xingchu No. 15[EB/OL]. (2020-08-15) [2022-07-05]. https://wenshu.court.gov.cn/(in Chinese).
[24]	浙江省长兴县人民法院. 刘东谢传青谢思江等诈骗案: 浙江省长兴县人民法院刑事判决书(2020)浙0522刑初16号[EB/OL]. (2020-08-18) [2022-07-05] . https://wenshu.court.gov.cn/. Zhejiang Changxing County People’s Court. Liu Dong Xie Chuanqing Xie Sijiang el al. Fraud case: Criminal judgment of the People’s Court of Chanagxing County, Zhejiang Province (2020) Zhe 0522 Xingchu No. 16[EB/OL]. (2020-08-18) [2022-07-05]. https://wenshu.court.gov.cn/(in Chinese).