Version 1.3

Code for VoG: Summarizing and Understanding Large Graphs Danai Koutra, U Kang, Jilles Vreeken, and Christos Faloutsos http://www.cs.cmu.edu/~dkoutra/papers/VoG.pdf

Contact: Danai Koutra, dkoutra@umich.edu

To run: type 'make'

Difference from Version 1.0: Using dynamic programming and the technique of memoization to speed up the application of the GREEDY'nFORGET heuristic.

Algorithm:

Input: graph G Step 1: Subgraph Generation. Generate candidate – possibly overlapping – subgraphs using one or more graph decomposition methods. Step 2: Subgraph Labeling. Characterize each subgraph as a perfect structure x \in Omega, or an approximate structure by using MDL to find the type x that locally minimizes the encoding cost. Populate the candidate set C. Step 3: Summary Assembly. Use the heuristics PLAIN, TOP10, TOP100, GREEDY’NFORGET (Sec. 4.3) to select a non-redundant subset from the candidate structures to instantiate the graph model M. Pick the model of the heuristic with the lowest description cost. Return graph summary M and its encoding cost.

Change Log:

July 1, 2015

January 9, 2015

  • Replaced the config.py file

July 30, 2014

  • Fixed ordering of nodes in cliques

June 15, 2014

  • Made the greedyNforget 100x faster by exploiting memoization

Vog_graph_summarization

Summarization of static graphs using the Minimum Description Length principle

Vog_graph_summarization Info

⭐ Stars25
πŸ”— Homepagewww.cs.cmu.edu
πŸ”— Source Codegithub.com
πŸ•’ Last Updatea year ago
πŸ•’ Created7 years ago
🐞 Open Issues0
βž— Star-Issue RatioInfinity
😎 AuthorGemsLab