动态空间网络中的黑洞模式挖掘算法

计算机工程与科学

动态空间网络中的黑洞模式挖掘算法

谭胜昔，贾金萍，赵斌，吉根林

（南京师范大学计算机科学与技术学院,江苏南京 210023）

收稿日期:2019-07-05 修回日期:2019-09-16 出版日期:2020-02-25 发布日期:2020-02-25

A black hole pattern mining algorithm

in dynamic spatial network

TAN Sheng-xi,JIA Jin-ping,ZHAO Bin,JI Gen-lin

（School of Computer Science and Technology,Nanjing Normal University,Nanjing 210023,China）

Received:2019-07-05 Revised:2019-09-16 Online:2020-02-25 Published:2020-02-25

摘要/Abstract

摘要：

黑洞模式是人类移动模式研究中的标志性成果，但在移动模式的演化建模方面存在局限性，因此研究具有时间演化特性的黑洞模式。新模式定义需要满足群体规模性、空间区域性和时间持续性3方面要求。提出具有时间演化特性的动态空间网络模型，基于此模型定义新的黑洞模式，并提出相应的挖掘算法。为了提升模式挖掘算法的效率，设计了基于时空划分的候选模式剪枝算法，有效降低了挖掘算法在时空维中的搜索代价。最后，基于真实数据的实验结果表明了该黑洞模式及其挖掘算法的有效性和可行性。

关键词: 时空数据挖掘, 黑洞模式, 人类移动性, 动态空间网络

Abstract:

The black hole pattern is a landmark achievement in the study of human moving patterns. However, the black hole pattern has limitations in the evolution modeling of human moving patterns. This paper proposes a black hole pattern with time evolution characteristics. The definition of the new pattern needs to meet the three requirements of group scale, spatial locality and time persistence. This paper proposes a dynamic spatial network model with time evolution characteristics. Based on this model, we define a new black hole pattern and propose a corresponding mining algorithm. In order to improve the efficiency of the pattern mining algorithm, we design a candidate pattern pruning algorithm based on spatiotemporal partitioning, which effectively reduces the searching cost of the mining algorithm in spatiotemporal dimension. Finally, experiments based on real data verify the effectiveness and efficiency of the proposed black hole pattern and mining algorithm.

Key words: spatiotemporal data mining, black hole pattern, human mobility, dynamic spatial network

谭胜昔，贾金萍，赵斌，吉根林. 动态空间网络中的黑洞模式挖掘算法[J]. 计算机工程与科学.

TAN Sheng-xi,JIA Jin-ping,ZHAO Bin,JI Gen-lin.

A black hole pattern mining algorithm

in dynamic spatial network

[J]. Computer Engineering & Science.