Please wait a minute...
JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE)
Service Computing     
KeyGraph-based community detection algorithm for public security intelligence
WANG Hua, HAN Tong-yang, ZHOU Ke
Wuhan National Laboratory for Optoelectronics, Huazhong University of Science and Technology, Wuhan 430074, China
Download:   PDF(1131KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

A KeyGraph-based community detection algorithm (KCD) was put forward in order to cluster the characteristics of human behavior, so as to detect the crowds with similar properties and classify them to provide decision support for the department of public security intelligence. KCD was proceeded from the features of human behavior; the identification of relational crowds was realized through establishing KeyGraph and employing graph cluster algorithms. Firstly, the multi-dimension behavior features between human behaviors were quantified, and quantized features were merged to generate the co-occurrence set in the form of a triad: “people-people-value”. Then noise data was filtered and the undirected graph based on the characteristics of human behavior was established. Finally graphclustering algorithm SCAN was applied to find out a number of different groups on undirected graph, where hubs and outliers were also located. As results, KCD could solve the problem of detecting the key persons among communities in the context of public security intelligence.



Published: 11 June 2017
CLC:  TP 391  
Cite this article:

WANG Hua, HAN Tong-yang, ZHOU Ke. KeyGraph-based community detection algorithm for public security intelligence. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2017, 51(6): 1173-1180.


公安情报中基于关键图谱的群体发现算法

为了在公安情报场景下将人的行为特征量化聚类,从而发现行为特征相似的人群并将其归类以提供决策支持,提出一种基于关键图谱的群体发现算法(KCD).KCD从人的行为特征入手,通过建立关键图谱并利用图聚类算法来进行群体发现.KCD首先将人与人之间的多个维度的行为特征进行量化计算,并将多维行为特征的量化值融合,形成三元组“人-人-值”的共现度集合;然后过滤噪音数据,建立基于行为特征的无向图;最后应用聚类算法SCAN从无向图中找出多个不同的群体,同时找出图的中心点和离群点,解决了公安情报场景中群体之间关键人物的挖掘问题.

参考文献(References):
[1] JACOB L. Moreno [EB/OL]. [2016-10-01]. https:∥en.wikipedia.org/wiki/Jacob_L._Moreno.
[2] WEST D B. Introduction to graph theory [M]. Upper Saddle River: Prentice hall, 2001: 1-36.
[3] SCOTT J. Social network analysis [M]. Sage: socialogy, 2012: 109-127.
[4] ALSABTI K, RANKA S, SINGH V. An efficientK-means clustering algorithm [C] ∥ Proceeding of IPPS/SPDP Workshop on High Performance Data Mining, 1998. New York: ACM, 2011: 1-6.
[5] KAUFMAN L, ROUSSEEUW P J. Finding groups in data: an introduction to cluster analysis [M]. New York: John Wiley and Sons, 2009.
[6] KAUFMAN L, PETER J R. Finding Groups in Data: An Introduction to Cluster Analysis [M]. New York: John Wiley and Sons, 1990.
[7] ESTER M, KRIEGEL H P, SANDER J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise [C] ∥ Proceeding of Second International Conference on Knowledge Discovery and Data Mining. Menlo Park: AAAI Press, 1996: 226-231.
[8] WANG W, YANG J, MUNTZ R. STING: a statistical information grid approach to spatial data mining [C] ∥ Proceeding of 23rd International Conference on Very Large Data Bases. San Francisco: Morgan Kaufmann, 1997: 186-195.
[9] 张浩明.数据挖掘在公安情报系统中的研究与应用[D].上海:同济大学, 2008.
ZHANG Hao-ming. Research and application on data mining for systems of public security intelligence [D]. Shanghai: Tongji University, 2008.
[10] 陆巧.公安大情报应用体系建设研究 [D]. 四川:电子科技大学, 2013.
LU Qiao. Research on the construction of the application system of public security intelligence [D]. Sichuan: University of Electronic Science and Technology, 2013.
[11] 杨正涛.基于数据仓库的公安情报分析系统的设计与实现[D].四川:电子科技大学, 2012.
YANG Zheng-tao. Design and implementation of public security information system based on data warehouse [D]. Sichuan: University of Electronic Science and Technology, 2012.
[12] ZHANG Z, CHENG H, WANG X. From data mining to chance/sign discovery [J]. Computer Science, 2007, 10: 188-191.
[13] ZHANG Z Y, CHENG H M, ZHANG S G. Research on approach of simple scenario map construction in chance discovery [J]. Computer Engineering, 2011,37(8):192-193.
[14] 程泽凯,张佳玉.基于节点相似度的社团发现算法[J].计算机工程与设计,2014, 35(5): 1689-1693.
CHENG Ze-kai, ZHANG Jia-yu. Community discovery algorithm based on node similarity [J]. Computer Engineering and Design, 2014, 35(5): 1689-1693.
[15] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks [J]. Physical Review E, 2004, 69(2): 026113.
[16] XU X, YURUK N, FENG Z, et al. Scan: a structural clustering algorithm for networks [C] ∥ Proceedings of the 13rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Jose: ACM, 2007: 824-833.

[1] Shou-guo ZHENG,Yong-de ZHANG,Wen-tian XIE,Hu FAN,Qing WANG. Aircraft final assembly line modeling based on digital twin[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2021, 55(5): 843-854.
[2] Shi-lin ZHANG,Si-ming MA,Zi-qian GU. Large margin metric learning based vehicle re-identification method[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2021, 55(5): 948-956.
[3] Peng SONG,De-dong YANG,Chang LI,Chang GUO. An adaptive siamese network tracking algorithm based on global feature channel recognition[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2021, 55(5): 966-975.
[4] Jun CAI,Gang ZHAO,Yong YU,Qiang-wei BAO,Sheng DAI. A rapid reconstruction method of simulation model based on point cloud and design model[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2021, 55(5): 905-916.
[5] Hong-li WANG,Bin GUO,Si-cong LIU,Jia-qi LIU,Yun-gang WU,Zhi-wen YU. End context-adaptative deep sensing model with edge-end collaboration[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2021, 55(4): 626-638.
[6] Teng ZHANG,Xin-long JIANG,Yi-qiang CHEN,Qian CHEN,Tao-mian MI,Piu CHAN. Wrist attitude-based Parkinson's disease ON/OFF state assessment after medication[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2021, 55(4): 639-647.
[7] Ying-jie ZHENG,Song-rong WU,Ruo-yu WEI,Zhen-wei TU,Jin LIAO,Dong LIU. Metro location point matching and false alarm elimination based on FCM algorithm of target image[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2021, 55(3): 586-593.
[8] Zi-ye YONG,Ji-chang GUO,Chong-yi LI. weakly supervised underwater image enhancement algorithm incorporating attention mechanism[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2021, 55(3): 555-562.
[9] Yong YU,Jing-yuan XUE,Sheng DAI,Qiang-wei BAO,Gang ZHAO. Quality prediction and process parameter optimization method for machining parts[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2021, 55(3): 441-447.
[10] Hui-ya HU,Shao-yan GAI,Fei-peng DA. Face frontalization based on generative adversarial network[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2021, 55(1): 116-123.
[11] Yang-bo CHEN,Guo-dong YI,Shu-you ZHANG. Surface warpage detection method based on point cloud feature comparison[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2021, 55(1): 81-88.
[12] You-kang DUAN,Xiao-gang CHEN,Jian GUI,Bin MA,Shun-fen LI,Zhi-tang SONG. Continuous kinematics prediction of lower limbs based on phase division[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2021, 55(1): 89-95.
[13] Tai-heng ZHANG,Biao MEI,Lei QIAO,Hao-jie YANG,Wei-dong ZHU. Detection method for composite hole guided by texture boundary[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2020, 54(12): 2294-2300.
[14] Dong LIANG,Xin-yu LIU,Jia-xing PAN,Han SUN,Wen-jun ZHOU,Shun’ichi KANEKO. Foreground segmentation under dynamic background based on self-updating co-occurrence pixel[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2020, 54(12): 2405-2413.
[15] Yao JIN,Wei ZHANG. Real-time fire detection algorithm with Anchor-Free network architecture[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2020, 54(12): 2430-2436.