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 |
|
|
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 graphclustering 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
|
|
|
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. |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|