An implementation of the Slice Tree algorithm to summarize a network.
In many real-life dynamic graphs, vertex attributes can be represented as numerical values. For instance, in a traffic network, the average speeds in a particular location can be modeled as a numerical attribute that changes over time. Due to the large scale of these attributed graphs, compressing the values of the attributes is an effective strategy to reduce their processing, communication, and storage requirements. This research proposes a new graph compression scheme based on a value-sensitive graph decomposition, which we call a slice tree. Slices are defined as spherical partitions that capture regions with homogeneous values in the graph. Values are compressed to the average value of their respective partitions, minimizing the overall compression error. We show that our approach outperforms baseline strategies in four real datasets, achieving error reductions up to 78%.
To compile:
make
To generate a synthetic graph with 100000 nodes and 5 edges per node (on average):
./graph_generator.py --output synthetic --num-vertices 100000 --num-edges 5 \
--num-partitions 32 --radius 2 --sse 200000 --reduction 100000
To compress the graph with the Slice Tree method using 8 cores:
./graph_compression --compression ST \
--values synthetic.data --graph synthetic.graph --partsizes synthetic.index \
--maxradius 2 --numpart 20 --numthreads 8
To compress the graph with the Slice Tree using sampling:
./graph_compression --compression STBS \
--values synthetic.data --graph synthetic.graph --partsizes synthetic.index \
--maxradius 2 --numpart 20 --numthreads 8 --sampling-rate 0.01 --rho 0.9 --delta 0.1
To generate a tree, add the --print-tree
option:
./graph_compression --compression STBS \
--values synthetic.data --graph synthetic.graph --partsizes synthetic.index \
--maxradius 2 --numpart 20 --numthreads 8 --sampling-rate 0.01 --rho 0.9 --delta 0.1 \
--print-tree > synthetic.tree
This can be used to generate an image with GraphViz:
./viztree synthetic synthetic.data
eog synthetic.svg &