Many real world networks are considered temporal networks, in which the chronological ordering of the edges has importance to the meaning of the data. Performing temporal subgraph matching on such graphs requires the edges in the subgraphs to match the order of the temporal graph motif we are searching for. Previous methods for solving this rely on the use of static subgraph matching to find potential matches first, before filtering them based on edge order to find the true temporal matches. We present a new algorithm for temporal subgraph isomorphism that performs the subgraph matching directly on the chronologically sorted edges. By restricting our search to only the subgraphs with chronologically correct edges, we can improve the performance of the algorithm significantly. We present experimental timing results to show significant performance improvements on publicly available datasets for a number of different temporal query graph motifs with four or more nodes. We also demonstrate a practical example of how temporal subgraph isomorphism can produce more meaningful results than traditional static subgraph searches.
Motif analysis on temporal networks is a much more recent area of research. provide an algorithm for finding temporal subgraphs, but have the added restriction that edges in the motif must represent consecutive events for the node @cite_3 . While this allows for fast subgraph counting, it does not allow subgraph matching on graphs that have other edges occurring in between the edge events of a motif. Another approach was published by @cite_7 . The authors present a heuristic for counting temporal motifs, but provide only an estimated count with their approach, and do not exhaustively find all exact temporal subgraph matches.
@cite_7 @cite_3
34835763 2562676961 2006761268 1994987445
The problem of locating motifs in real-valued, multivariate time series data involves the discovery of sets of recurring patterns embedded in the time series. Each set is composed of several non-overlapping subsequences and constitutes a motif because all of the included subsequences are similar. The ability to automatically discover such motifs allows intelligent systems to form endogenously meaningful representations of their environment through unsupervised sensor analysis. In this paper, we formulate a unifying view of motif discovery as a problem of locating regions of high density in the space of all time series subsequences. Our approach is efficient (sub-quadratic in the length of the data), requires fewer user-specified parameters than previous methods, and naturally allows variable length motif occurrences and non-linear temporal warping. We evaluate the performance of our approach using four data sets from different domains including on-body inertial sensors and speech. Networks are a fundamental tool for modeling complex systems in a variety of domains including social and communication networks as well as biology and neuroscience. The counts of small subgraph patterns in networks, called network motifs, are crucial to understanding the structure and function of these systems. However, the role of network motifs for temporal networks, which contain many timestamped links between nodes, is not well understood. Here we develop a notion of a temporal network motif as an elementary unit of temporal networks and provide a general methodology for counting such motifs. We define temporal network motifs as induced subgraphs on sequences of edges, design several fast algorithms for counting temporal network motifs, and prove their runtime complexity. We also show that our fast algorithms achieve 1.3x to 56.5x speedups compared to a baseline method. We use our algorithms to count temporal network motifs in a variety of real-world datasets. Results show that networks from different domains have significantly different motif frequencies, whereas networks from the same domain tend to have similar motif frequencies. We also find that measuring motif counts at various time scales reveals different behavior. Several important time series data mining problems reduce to the core task of finding approximately repeated subsequences in a longer time series. In an earlier work, we formalized the idea of approximately repeated subsequences by introducing the notion of time series motifs. Two limitations of this work were the poor scalability of the motif discovery algorithm, and the inability to discover motifs in the presence of noise.Here we address these limitations by introducing a novel algorithm inspired by recent advances in the problem of pattern discovery in biosequences. Our algorithm is probabilistic in nature, but as we show empirically and theoretically, it can find time series motifs with very high probability even in the presence of noise or "don't care" symbols. Not only is the algorithm fast, but it is an anytime algorithm, producing likely candidate motifs almost immediately, and gradually improving the quality of results over time. Detecting and counting the number of copies of certain subgraphs (also known as network motifs or graphlets) is motivated by applications in a variety of areas ranging from biology to the study of the World Wide Web. Several polynomial-time algorithms have been suggested for counting or detecting the number of occurrences of certain network motifs. However, a need for more efficient algorithms arises when the input graph is very large, as is indeed the case in many applications of motif counting. In this paper we design sublinear-time algorithms for approximating the number of copies of certain constant-size subgraphs in a graph G. That is, our algorithms do not read the whole graph, but rather query parts of the graph. Specifically, we consider algorithms that may query the degree of any vertex of their choice and may ask for any neighbor of any vertex of their choice. The main focus of this work is on the basic problem of counting the number of length-2 paths and more generally on counting the number of...