Many real-world phenomena can be represented as dynamic graphs, i.e., networks that
change over time. The problem of dynamic graph summarization, i.e., to succinctly
describe the evolution of a dynamic graph, has been widely studied. Existing methods
typically use objective measures to find fixed structures such as cliques, stars, and
cores. Most of the methods, however, do not consider the problem of online summarization, where the summary is incrementally conveyed to the analyst as the graph
evolves, and (thus) do not take into account the knowledge of the analyst at a specific moment in time. As a specific instance of this generic problem, online summarization
of dynamic graphs was introduced. We presented a framework to solve this problem,
which has been built on the existing ideas related to maximum entropy principle,
the minimum description length principle, and subjectively interesting subgraph patterns. We then introduced an efficient algorithm, called DSSG, which is followed
by extensive experiments on real-world datasets. Through experimental results, we
demonstrated the effectiveness of the proposed algorithm. The generated summaries
are found to be informative with regard to the analyst’s prior knowledge about the data.
We conclude this from the observed substantial compression ratios and the fact that
compression equates learning. We have also found different sequences of patterns,
which evolved over time in a network. We also presented a case study and demonstrated a potential use of the proposed method in the airline domain. Comparison of
two different summaries of the airline network, using the scheduled and the actual
123
124 S. Kapoor et al.
flight data, revealed potentially informative events.
As a part of future work, it would
be interesting to extend the proposed method to incorporate a feature to capture periodicity of the patterns; another is to extend this method to multigraphs, weighted graphs,
and attributed graphs. Finally, as a part of our ongoing/future work, we aim to develop
a tool for interactive visualization and exploration of the found patterns.