Graph Theory: Interesting Concept of Graph Summarization

Many real-world problems can be modeled as graphs/networks. Some examples are transportation networks, brain neural networks, flight route networks, malware distribution networks, biological networks, and email networks etc. In this age of Big Data, size of these graphs are growing in exponential rates and mammoth proportions. Because of scale of these graphs, even simplest of the graph algorithms are becoming difficult to execute. It would be ideal if these graphs can be summarized in some way. One way to summarize graph is by sparsifying it, by deleting less important edges and nodes from the graph. Most interesting way to summarize a graph is by smartly collapsing nodes into supernodes and then connect these supernodes with superedges.

Summarizing graphs can have massive impact where it can speedup computations by orders of magnitude. Since it hides fine-grained relationships between the nodes and masks them with more coarse-grained ones, it can provide certain privacy and anonymization benefits. Overall, graph summarization is a beautiful and fairly new concept in graph theory.