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

A black hole pattern mining algorithm in dynamic spatial network

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

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.