Periodic Patterns in Dynamic Network: Mining and Parametric Analysis

Introduction

In recent times, an enormous amount of data is available around consumer behaviour, social interaction, weather forecast pattern, financial market, DNA pattern and many other different types of behavioral pattern. The volume of raw data available is put to better use when data visualisation and mining techniques Hassanein et al., (2015) are applied on it. Graph is one such effective way to arrange and organize such passive data into a meaningful form. It helps to visualize the relationship between entities with significant clarity. As amount of data available is immense and its nature varies with time, so it becomes more meaningful when data is modelled in form of dynamic network of graphs which evolve over a period of time. After modelling data in such a form, it becomes a lot easier to study the behaviour and nature of interactions between participating entities. Not only it provides insight about existing behaviour, but also assists to obtain significant information about the future and thereby making fruitful predictions.

A considerable amount of effort has already been put in to study the nature of interactions in dynamic network(Apostolico, A., Barbares, M., & Pizzi, C., 2011; Borgwardt, K. M., Kriegel, H. P., & Wackersreuther, P., 2006; Desikan & Srivastava, 2006; Duan, D., Li, Y., Jin, Y., & Lu, Z., 2009; Gupta, A., Thakur, K. H., & Kishore, P., 2014; Halder, S., Han, Y., & Lee, Y., 2013; Inokuchi, A., Washio, T., & Motoda, H., 2000; Lahiri & Wolf, 2010; Liu, G., Wong, L., & Chua, H. N., 2009; Obulesu, O., Reddy, M. R., & Reddy, T. M., 2014; Qin, G., Yang, J., Gao, L., & Li, J., 2011; Rasheed, F., Alshalalfa, M., & Alhajj, R., 2011; Yang, J., Wang, W., & Yu, P., 2014). Among these work, a significant amount of effort has been put in to understand frequent (Borgwardt, K. M., Kriegel, H. P., & Wackersreuther, P., 2006; Inokuchi, A., Washio, T., & Motoda, H., 2000; Yang, J., Wang, W., & Yu, P., 2014) and regular (Gupta, A., Thakur, K. H., & Kishore, P., 2014; Qin, G., Yang, J., Gao, L., & Li, J., 2011) behavior of interactions. Along with such patterns, there are other type of behavior that interactions exhibit, namely periodic patterns. Periodic patterns repeat itself over a period of time.

The initial step to explore and extract periodic patterns dates back to 1996 when Srikant and Agrawal (1996) developed a model based on similarity of time sequences. Later, a model for discovery of association rules has been developed by Ozden et al.(1998) which displays cyclic variations over time. And soon after this, Han et al. (1999) constructed a model for efficient mining of partial periodic patterns in time series database. Subsequently, Ma and Hellerstein (2001) have proposed an algorithm for mining partially periodic event patterns with unknown periods. Subsequently, Berberidis et al. (2002) have devised an approach to deal with datasets in which periodicity is initially unknown. Further, Yang (2003) developed a model to mine asynchronous periodic patterns. Later in 2010, Lahiri & Wolf came up with an algorithm to mine parsimonious periodic patterns in a dynamic network. It is soon followed by efforts of Apostolico et al. (2011), where the time complexity of algorithm (Lahiri & Wolf, 2010) has been improved. Subsequently, a noise resilient suffix tree based approach to detect all periodic patterns in a time series and sequence database has been put forward by Rasheed et al. (2011). Further, Halder et al. (2013) proposed super graph based approach to mine periodic patterns. Later, Obulesu et al. (2014) have proposed a framework to find frequent and maximal periodic patterns in Spatiotemporal Databases.