document: Compression of weighted graphs We propose to compress weighted graphs ( networks ) , 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 .
doc_bio_tags: B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O B I B O O O O O O O O O O O O O O O O O O B I B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O