State Transition Graphs for Semantic Analysis of Movement Behaviours

Abstract

A behaviour can be defined as a sequence of states or activities occurring one after another. A behaviour consisting of a finite number of reoccurring states/activities may be represented by a directed weighted graph with nodes and edges corresponding, respectively, to the possible states and transitions between them, while the weights represent the probabilities or frequencies of the state and transition occurrences. The same applies to multiple behaviours sharing the same set of possible states. In analysis of movement data, state transition graphs can be used to represent semantic abstractions of mobility behaviours, where states correspond to semantic categories of visited places (such as ‘home’, ‘work’, ‘shop’), activities of moving objects (‘driving’, ‘walking’, ‘exercising’, etc.) or characteristics of the movement (‘straight movement’, ‘sharp turn’, ‘acceleration’, ‘stop’, etc.). Such a representation supports the exploration and analysis of the semantic aspect (i.e. the meaning or purposes) of movement. For comprehensive analysis of movement data, state transition graphs need to be combined with representations reflecting the spatial and temporal aspects of the movement. This requires appropriate coordination between different visual displays (graphs, maps and temporal views) and appropriate reaction to analytical operations applied to any of the representations of the same data. We define in an abstract way the reactions of a graph display to analytical operations of querying, partitioning and direct selection. We also propose visual and interactive display features supporting comparisons between data subsets and between results of different operations. We demonstrate the use of the display features by examples of real-world and synthetic data sets.