Compression of Weighted Graphs
| Contribuinte(s) |
University of Helsinki, Department of Computer Science University of Helsinki, Department of Computer Science University of Helsinki, Department of Computer Science University of Helsinki, Department of Computer Science |
|---|---|
| Data(s) |
2011
|
| Resumo |
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 simplication, 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 dierent 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. |
| Identificador | |
| Idioma(s) |
eng |
| Relação |
The 17th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) Proceedings |
| Direitos |
Rights Retained by Authors and Original Copyright Holders Under the ACM copyright transfer agreement, the original copyright holder retains: * All other proprietary rights to the work such as patent; * The right to reuse any portion of the Work, without fee, in future works of the Author’s (or Author’s Employer’s) own, including books, lectures and presentations in all media, provided that the ACM citation, notice of the Copyright and the ACM DOI are included (See Section 4 below). Requests made on behalf of others, however (i.e. contributions to the work of other authors or other editors), usually require payment of a fee; * The right to revise the work. (See Policy §2.4 <http://www.acm.org/publications/policies/copyright_policy##Definitive> Definitive Versions and Revisions); * The right to post author-prepared versions of the work covered by ACM copyright in a personal collection on their own Home Page and on a publicly accessible server of their employer, and in a repository legally mandated by the agency funding the research on which the Work is based. Such posting is limited to noncommercial access and personal use by others, and must include this notice both embedded within the full text file and in the accompanying citation display as well: */"© ACM, (YEAR). This is the author’s version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in PUBLICATION, {VOL##, ISS##, (DATE)} http://doi.acm.org/10.1145/{nnnnnn.nnnnnn}"/. * /(You may find the nnnnnn.nnnnnn number for your article DOIs on its citation page in the ACM Digital Library.) / * The right of an employer who originally owned the copyright to distribute definitive copies of its author-employees’ Work within its organization. Posting these works for worl access requires explicit permission from ACM. Authors may post works on public repositories before acceptance but must incorporate the ACM copyright notice upon transfer of copyright. After acceptance, authors may post the work on public repositories only with the explicit permission of ACM. Authors or their employers may retain copyright to embedded images (e.g., figures) with independent artistic value. Authors must grant permission for ACM to use the image in the context of the article in current and future formats. Such images must be declared at the time of article copyright transfer, and declaration of copyright must be included within the image or the caption. *Requests made on behalf of others, i.e., for contributions to the work of other authors or other editors, may require payment of the fee." |
| Fonte |
Toivonen , H , Zhou , F , Hartikainen , A & Hinkka , A 2011 , ' Compression of Weighted Graphs ' in The 17th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) : Proceedings , pp. 965-973 . , 10.1145/2020408.2020566 |
| Palavras-Chave | #113 Computer and information sciences |
| Tipo |
A4 Article in conference publication (refereed) info:eu-repo/semantics/conferencePaper info:eu-repo/semantics/acceptedVersion |
