Public movement analysis using location based social network data

© 2020 Don Lashantha Sameera KannangaraLocation Based Social Networks (LBSNs) provide an inexpensive source of data to analyse public movement. However, it is difficult to process LBSN to get useful information due to the sparsity and irregularity associated with data. These inherent properties of LBSN data are caused by the voluntary posting to the LBSN. Therefore we can say voluntary posting of data is both a strength and a weakness of LBSN data. In this thesis, we propose several methods to process LBSN data to extract useful information. Information from LBSN data can be used to identify areas used for movement and the most popular paths. A clever way to extract these information is to first construct a graph structure based on the posted locations and query this graph. Neighbourhood graphs are useful structures to analyse the movement between a set of locations. More specifically we look at two candidates the Relative Neighbourhood Graph and the Shortest Path Graph, but both have weaknesses making them less suitable for our domain. By analysing the relationship between these two graphs, we propose the Stepping Stone graph with local criterion named the Diversion Neighbourhood which captures movement related information between two points. Due to the shape of the Diversion Neighbourhood, the Stepping Stone Graph is very effective in calculating movement related queries, and because the Diversion Neighbourhood is a local criterion, the Stepping Stone graph is efficient to create. In this thesis, we provide how the Stepping Stone Graph is related to other well-known graphs and empirically show how it is useful for LBSN data processing by answering a few spatial queries using real LBSN data. Modern use cases of LBSN data processing need to generate results in real time. Even though the Stepping Stone Graph is suitable to process LBSN data sets with moderate number of post with locations, it takes a considerable time to process very large data sets. Continuing our research on neighbourhood graphs, in order to address this scalability issue we propose the Diversion Graph by relaxing the evaluation criteria of the Stepping Stone Graph. Due to this relaxed criteria, the Diversion Graph takes 10\% of the time required to calculate the Stepping Stone Graph of the same location set. However, the Diversion Graph contains a maximum of 2% additional edges than the Stepping Stone Graph, which is an undesirable effect. When considering creation time reduction against the number of additional edges, the Diversion Graph provides a favourable trade off for LBSN data analysis in numerous scenarios. We show this increased performance of the Diversion Graph against the Stepping Stone Graph by processing a few application queries that require to process a large number of locations filtered from real LBSN data and synthetic data. Due to the sparsity and irregularity associated with LBSN data, there are use cases that cannot be solved by the data structures previously proposed. One such important use case useful for many fields is predicting group movement. Due to the lack of techniques to track multiple moving objects as a group using sparse irregular data, addressing this use case using LBSN data is difficult. To address this issue we turn our attention to algorithms in signal processing and time series analysis. LBSN trajectory of a single user can be considered a location signal collected over time. Group analysis relates to processing multiple of these signals together. We propose a new technique named the Group Kalman Filter, by extending the well-known technique named the Kalman filter which is used for processing multiple signals. When using LBSN data to track group movement, not all members of the group post continuously to the LBSN. Therefore we have to assume that locations of the members who are not posting are reflected by the members who are posting with the group. We develop a metric to quantify this behaviour and use it to detect complex group movement patterns such as group merging and group splitting. We propose four group movement models to track and predict the movement of detected groups with their advantages and disadvantages. Using real LBSN data and synthetic location data that mimic LBSN data distributions, we show that the Group Kalman Filter is both effective and efficient to detect and predict group movement using LBSN data as our final contribution to the area with this thesis