2011 CompressionofWeightedGraphs

• (Toivonen et al., 2011) ⇒ Hannu Toivonen, Fang Zhou, Aleksi Hartikainen, and Atte Hinkka. (2011). “Compression of Weighted Graphs.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020566

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Compression+of+Weighted+Graphs
• http://dl.acm.org/citation.cfm?id=2020408.2020566&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; compression; data mining; experimentation; graph mining; graphs and networks; network; performance; weighted graph

Abstract

We propose to compress weighted graphs (network)s, motivated by the observation that large networks of social, biological, or other relations can be complex to handle and visualize. In the process also known as graph simplification, nodes and (unweighted) edges are grouped to supernodes and superedges, respectively, to obtain a smaller graph. We propose models and algorithms for weighted graphs. The interpretation (i.e. decompression) of a compressed, weighted graph is that a pair of original nodes is connected by an edge if their supernodes are connected by one, and that the weight of an edge is approximated to be the weight of the superedge. The compression problem now consists of choosing supernodes, superedges, and superedge weights so that the approximation error is minimized while the amount of compression is maximized.

In this paper, we formulate this task as the 'simple weighted graph compression problem'. We then propose a much wider class of tasks under the name of ' generalized weighted graph compression problem'. The generalized task extends the optimization to preserve longer-range connectivities between nodes, not just individual edge weights. We study the properties of these problems and propose a range of algorithms to solve them, with different balances between complexity and quality of the result. We evaluate the problems and algorithms experimentally on real networks. The results indicate that weighted graphs can be compressed efficiently with relatively little compression error.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 CompressionofWeightedGraphs	Hannu Toivonen Fang Zhou Aleksi Hartikainen Atte Hinkka			Compression of Weighted Graphs				10.1145/2020408.2020566		2011