Home
This Title All WIREs
WIREs RSS Feed
How to cite this WIREs title:
WIREs Data Mining Knowl Discov
Impact Factor: 2.541

A survey of pattern mining in dynamic graphs

Full article on Wiley Online Library:   HTML PDF

Can't access this content? Tell your librarian.

Abstract Graph data is found in numerous domains such as for the analysis of social networks, sensor networks, bioinformatics, industrial systems, and chemistry. Analyzing graphs to identify useful and interesting patterns is an important research area. It helps understanding graphs, and hence support decision making. Since two decades, many graph mining algorithms have been proposed to identify patterns such as frequent subgraphs, paths, cliques, and trees. But most of them assume that graphs are static. This simplifying assumption makes it easy to design algorithms but discard information about how graphs evolve. This article provides a detailed survey of techniques for mining interesting patterns in dynamic graphs, which can serve both as an introduction and as a guide to recent advances and opportunities in this research area. The main tasks related to mining patterns in dynamic graphs are reviewed such as discovering frequent subgraphs, evolution rules, motifs, subgraph sequences, recurrent and triggering patterns, and trend sequences. In addition, an overview of strategies and approaches to solve dynamic graph mining problems is presented, and their advantages and limitations are highlighted. Various extensions are also discussed such as to discover patterns in data streams and big data. Finally, the article mentions several research opportunities. This article is categorized under: Algorithmic Development > Spatial and Temporal Data Mining Algorithmic Development > Association Rules
Main types of patterns discovered in dynamic graphs
[ Normal View | Magnified View ]
A directed labeled graph, three traversal paths, and some traversal patterns found for minsup = 2. (a) A directed labeled graph, (b) three graph traversal paths, and (c) traversal patterns extracted from (b) for minsup = 2
[ Normal View | Magnified View ]
A single graph and frequent subgraphs found for minsup = 2. (a) A single graph G and (b) frequent subgraphs for minsup
[ Normal View | Magnified View ]
Different types of subtrees of the tree of Figure 3d. (a) A bottom‐up subtree, (b) an induced subtree, and (c) an embedded subtree
[ Normal View | Magnified View ]
Different types of trees. (a) A tree, (b) a rooted tree, (c) an ordered rooted tree, and (d) an ordered rooted labeled tree
[ Normal View | Magnified View ]
A graph database and frequent subgraphs found for minsup = 2. (a) A graph database GD and (b) frequent subgraphs for minsup = 2
[ Normal View | Magnified View ]
Different types of static graphs. (a) A connected graph, (b) a disconnected graph, (c) a directed graph, (d) a weighted graph, (e) a labeled graph, (f) an attributed graph, (g) a multi‐labeled graph, and (h) a multi‐relational graph
[ Normal View | Magnified View ]
Examples of patterns found in the dynamic attributed graph of Figure 16. (a) A cohesive co‐evolution pattern, (b) a recurrent pattern, and (c) a significant trend sequence
[ Normal View | Magnified View ]
A sequence of trend graphs obtained by preprocessing the dynamic attributed graph of Figure 15. (a) ti1: t1 to t2; (b) ti2: t2 to t3 (c) ti3: t3 to t4, (d) ti4: t4 to t5, and (e) ti5: t5 to t6
[ Normal View | Magnified View ]
A dynamic attributed graph having six timestamps with raw numerical attribute values. (a) t1, (b) t2, (c) t3, (d) t4, (e) t5, and (f) t6
[ Normal View | Magnified View ]
A frequent induced pattern
[ Normal View | Magnified View ]
Two intrastate sequences and one of their subsequences. (a) Sid1 and (b) Sid2
[ Normal View | Magnified View ]
A graph sequence database containing two graph sequences
[ Normal View | Magnified View ]
A graph evolution rule found in a dynamic graph. (a) Union graph with edges’ first appearing time, (b) two embeddings of an equivalence class, and (c) an evolution rule (minimum support = 2)
[ Normal View | Magnified View ]
A dynamic graph, some frequent patterns and a periodic pattern. (a) A dynamic graph, (b) two frequent patterns, and (c) a periodic pattern
[ Normal View | Magnified View ]
A dynamic graph, the corresponding union graph, and a frequent subgraph. (a) A dynamic graph with topological evolution and edge label evolution, (b) union graph of the dynamic graph and (c) a frequent subgraph found in the dynamic graph
[ Normal View | Magnified View ]
Three types of dynamic graphs. (a) A dynamic graph with only topological evolution, (b) a dynamic graph with only label evolution, and (c) a dynamic graph with both topological and label evolution
[ Normal View | Magnified View ]

Browse by Topic

Algorithmic Development > Association Rules
Algorithmic Development > Spatial and Temporal Data Mining

Access to this WIREs title is by subscription only.

Recommend to Your
Librarian Now!

The latest WIREs articles in your inbox

Sign Up for Article Alerts