Compression of Graphical Structures: Fundamental Limits, Algorithms, and Experiments

No abstract is available for this paper.

• Publication year

  2012

• Venue

  IEEE Transactions on Information Theory

• Publication date

  2012-02-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TIT.2011.2173710
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Symmetry in Complex Networks

  2011cited by this paper
• Tunstall Code, Khodak Variations, and Random Walks

  2010cited by this paper
• Compression of graphical structures

  2009cited by this paper
• Analytic Combinatorics

  2009cited by this paper
• Structural complexity of random binary trees

  2009cited by this paper
• On compressing social networks

  2009cited by this paper
• Sparse graphs: Metrics and random models

  2008cited by this paper
• Graph compression—save information by exploiting redundancy

  2007cited by this paper
• Metrics for sparse graphs

  2007cited by this paper
• Structure induction by lossless graph compression

  2007cited by this paper
• APPROXIMATION OF THE DILOGARITHM FUNCTION

  2007cited by this paper
• A Greedy Renormalization Method for Arithmetic Coding

  2007cited by this paper
• Systematic topology analysis and generation using degree correlations

  2006cited by this paper
• Elements of Information Theory

  2005cited by this paper
• Compression of words over a partially commutative alphabet

  2004cited by this paper
• Three great challenges for half-century-old computer science

  2003cited by this paper
• Precise average redundancy of an idealized arithmetic coding

  2002cited by this paper
• On the asymmetry of random regular graphs and random graphs

  2002influential reference
• Towards compressing Web graphs

  2001cited by this paper
• Average Case Analysis of Algorithms on Sequences

  2001influential reference
• Average Case Analysis of Algorithms on Sequences: Szpankowski/Average

  2001cited by this paper
• Complexity and Information in Data

  2000cited by this paper
• A Survey of Advances in Hierarchical Data Compression

  2000cited by this paper
• Limiting distributions for the costs of partial match retrievals in multidimensional tries

  2000cited by this paper
• Entropy Computations via Analytic Depoissonization

  1999cited by this paper
• Integral representations and asymptotic expansions for Shannon and Renyi entropies

  1998cited by this paper
• Analytical Depoissonization and its Applications

  1998influential reference
• Nearly perfect matchings in regular simple hypergraphs

  1997cited by this paper
• The context-tree weighting method: basic properties

  1995cited by this paper
• Asymptotic Behavior of the Lempel-Ziv Parsing Scheme and Digital Search Trees

  1995cited by this paper
• Graph entropy: A survey

  1993cited by this paper
• Succinct representation of general unlabeled graphs

  1990cited by this paper
• On a functional equation arising in the analysis of a protocol for a multi-access broadcast channel

  1986cited by this paper
• Random Graphs

  1985cited by this paper
• On the succinct representation of graphs

  1984cited by this paper
• Stochastic Processes

  1982cited by this paper
• Graphical enumeration

  1973cited by this paper
• The number of ways to label a structure

  1967cited by this paper
• Handbook of Mathematical Functions.

  1966cited by this paper
• A note on the information content of graphs

  1956cited by this paper
• Life, information theory, and topology

  1955cited by this paper
• The lattice theory of information

  1953cited by this paper
• A mathematical theory of communication

  1948cited by this paper
• ASYMMETRIC GRAPHS

  year unknowninfluential reference

• Information-Theoretic Limits on Exact Subgraph Alignment Problem

  2026influential citation
• On the Entropy of a Random Geometric Graph

  2026influential citation
• Predictability of complex systems

  2026cites this paper
• Duplication-divergence growing graph models

  2025cites this paper
• Gaussian Graphical Model Selection Using Graph Compression

  2025cites this paper
• Shotgun assembly of unlabeled Erdős–Rényi graphs

  2025cites this paper
• Networks Multiscale Entropy Analysis

  2025cites this paper
• Rate-Distortion-Perception Function of Bernoulli Vector Sources

  2025cites this paper
• Measuring the Predictability of Recommender Systems using Structural Complexity Metrics

  2024cites this paper
• The Prediction Error Bound in Urban Crime: Temporal Predictability

  2024cites this paper
• Practical Shuffle Coding

  2024cites this paper
• On the Lossy Compression of Spatial Networks

  2024cites this paper
• Entropy Coding of Unordered Data Structures

  2024influential citation
• SCHENO: Measuring Schema vs. Noise in Graphs

  2024cites this paper
• Practical Random Tree Generation: Information-Theoretic Analysis and Applications to IoT

  2023cites this paper
• Entropy of Exchangeable Random Graphs

  2023cites this paper
• On Random Tree Structures, Their Entropy, and Compression

  2023cites this paper
• Rate-Distortion Function of the Stochastic Block Model

  2023cites this paper
• Graph Compression with Side Information at the Decoder

  2023influential citation
• Compression with Unlabeled Graph Side Information

  2023cites this paper
• A Universal Lossless Compression Method Applicable to Sparse Graphs and Heavy–Tailed Sparse Graphs

  2023cites this paper
• Survey of Grammar-Based Data Structure Compression

  2022cites this paper
• A Universal Low Complexity Compression Algorithm for Sparse Marked Graphs

  2022cites this paper
• Entropy of labeled versus unlabeled networks

  2022cites this paper
• Structural Complexity of One-Dimensional Random Geometric Graphs

  2021cites this paper
• A Universal Lossless Compression Method applicable to Sparse Graphs and heavy-tailed Sparse Graphs

  2021cites this paper
• Partition and Code: learning how to compress graphs

  2021influential citation
• A Lower Bound for Regret in Logistic Regression

  2021cites this paper
• Lossy Compression for Lossless Prediction

  2021cites this paper
• BernoulliZip: a Compression Algorithm for Bernoulli Processes and Erdos-Renyi Graphs

  2021cites this paper
• Graph Coding for Model Selection and Anomaly Detection in Gaussian Graphical Models

  2021influential citation
• Universal Graph Compression: Stochastic Block Models

  2021cites this paper
• A General Lower Bound for Regret in Logistic Regression

  2021cites this paper
• Multi-relation Graph Summarization

  2021cites this paper
• On Lossy Compression of Directed Graphs

  2021cites this paper
• Structural Entropy of the Stochastic Block Models

  2021influential citation
• Graph Compression with Application to Model Selection

  2021cites this paper
• Optimal compression for bipartite networks

  2021cites this paper
• Shotgun assembly of unlabeled Erdos-Renyi graphs

  2021cites this paper
• Revealing the predictability of intrinsic structure in complex networks

  2020cites this paper
• The Twelvefold Way of Non-Sequential Lossless Compression

  2020cites this paper
• A Universal Low Complexity Compression Algorithm for Sparse Marked Graphs

  2020cites this paper
• Degree Distribution for Duplication-Divergence Graphs: Large Deviations

  2020cites this paper
• Universal Graph Compression: Stochastic Block Models

  2020cites this paper
• Type Size Code for Compressing Erdos-Rényi Graphs

  2020cites this paper
• Compression and Symmetry of Small-World Graphs and Structures

  2020influential citation
• Scalable Computing of Betweenness Centrality based on Graph Reduction with a Case Study on Breast Cancer Analytics

  2020cites this paper
• Universal Tree Source Coding Using Grammar-Based Compression

  2019cites this paper
• Compression of Preferential Attachment Graphs

  2019cites this paper
• Universal Lossless Compression of Graphical Data

  2019cites this paper
• Query Based Graph Data Reduction Algorithms and Application in Education

  2019cites this paper
• Compression of Dynamic Graphs Generated by a Duplication Model

  2018cites this paper
• Frontiers of Science of Information: Shannon Meets Turing

  2018cites this paper
• Lossless Compression of Binary Trees With Correlated Vertex Names

  2018cites this paper
• Distributed Compression of Graphical Data

  2018cites this paper
• Coding of Graphs with Application to Graph Anomaly Detection

  2018influential citation
• Universal and Succinct Source Coding of Deep Neural Networks

  2018influential citation
• On the Distribution of Random Geometric Graphs

  2018cites this paper
• Entropy and Optimal Compression of Some General Plane Trees

  2018influential citation
• On the conditional entropy of wireless networks

  2018cites this paper
• Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations

  2018cites this paper
• Lossy Graph Data Reduction

  2018cites this paper
• GOLAP: Graph-Based Online Analytical Processing

  2018cites this paper
• Frontiers of Science of Information: Shannon Meets Turing

  2018cites this paper
• Recovery of vertex orderings in dynamic graphs

  2017cites this paper
• Structural Information in Graphs : Symmetries and Admissible Relabelings

  2017cites this paper
• Universal lossless compression of graphical data

  2017cites this paper
• Universal Source Coding of Deep Neural Networks

  2017influential citation
• Frontiers of Science of Information : Shannon Meets

  2017cites this paper
• Structural Information and Compression of Scale-Free Graphs

  2017cites this paper
• Data compression algorithm for computer vision applications: A survey

  2017cites this paper
• Topological entropy in wireless networks subject to composite fading

  2017cites this paper
• Hypotheses testing on infinite random graphs

  2017cites this paper
• Entropy of Spatial Network Ensembles

  2017cites this paper
• On structural entropy of uniform random intersection graphs

  2017cites this paper
• Summarizing Static and Dynamic Big Graphs

  2017cites this paper
• On Symmetries of Non-Plane Trees in a Non-Uniform Model

  2017cites this paper
• Entropy of some general plane trees

  2017cites this paper
• Universal tree source coding using grammar-based compression

  2017cites this paper
• Compressing data on graphs with clusters

  2017cites this paper
• Pattern maximum likelihood estimation of finite-state discrete-time Markov chains

  2016cites this paper
• Topological Uncertainty in Wireless Networks

  2016cites this paper
• Graph compression: The effect of clusters

  2016cites this paper
• Text compression using lexicographic permutation of binary strings

  2016cites this paper
• Lossless compression of binary trees with correlated vertex names

  2016cites this paper
• Information Sources on a Bratteli diagram

  2016cites this paper
• A Graph Summarization: A Survey

  2016cites this paper
• Graph Summarization Methods and Applications

  2016cites this paper
• Asymmetry and structural information in preferential attachment graphs

  2016cites this paper
• Preferential Attachment Graphs are All But Asymmetric

  2016cites this paper
• Learning of Graph Compressed Dictionaries for Sparse Representation Classification

  2016cites this paper
• Preferential Attachment Graphs Are All But Asymmetric ∗ July 6 , 2016

  2016cites this paper
• External Data Overcomplete Dictionary Similarity Graph ≈ + Probeimage Gallery Compressed Dictionary With Coefficient Design Phase : Operational Phase : CD Compressed Dictionary

  2016cites this paper
• Model-code separation architectures for compression based on message-passing

  2015cites this paper
• Automata and graph compression

  2015cites this paper
• Algorithms for graph compression: theory and experiments

  2015cites this paper
• A study on compressing graphical structures

  2014cites this paper
• On Symmetry of Uniform and Preferential Attachment Graphs

  2014cites this paper
• The behavioral approach to diagnostics of cyber-physical systems

  2014cites this paper
• A Matrix Factorization Approach to Graph Compression

  2014cites this paper