Entropy of some models of sparse random graphs with vertex-names

DOI10.1017/S0269964813000399zbMATH Open1288.05241arXiv1301.0337MaRDI QIDQ5416367FDOQ5416367

Authors: David Aldous, Nathan Ross 

Publication date: 20 May 2014

Published in: Probability in the Engineering and Informational Sciences (Search for Journal in Brave)

Abstract: Consider the setting of sparse graphs on N vertices, where the vertices have distinct "names", which are strings of length O(log N) from a fixed finite alphabet. For many natural probability models, the entropy grows as cN log N for some model-dependent rate constant c. The mathematical content of this paper is the (often easy) calculation of c for a variety of models, in particular for various standard random graph models adapted to this setting. Our broader purpose is to publicize this particular setting as a natural setting for future theoretical study of data compression for graphs, and (more speculatively) for discussion of unorganized versus organized complexity.

Full work available at URL: https://arxiv.org/abs/1301.0337

Recommendations

• Fast algorithm for optimal compression of graphs
• Compression of dynamic graphs generated by a duplication model
• scientific article; zbMATH DE number 780788
• Compression and symmetry of small-world graphs and structures
• scientific article; zbMATH DE number 1092008

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Cites Work

• Elements of Information Theory
• Processes on unimodular random networks
• Title not available (Why is that?)
• Complex graphs and networks
• Probability Estimation in the Rare-Events Regime
• A history of graph entropy measures
• The continuum random tree. I
• Inequalities with applications to percolation and reliability
• Pattern matching and lossy data compression on random fields
• Universal Compression of Memoryless Sources Over Unknown Alphabets
• The \(t\)-improper chromatic number of random graphs
• Compression of Graphical Structures: Fundamental Limits, Algorithms, and Experiments

Cited In (2)

• Compression and symmetry of small-world graphs and structures
• Fast algorithm for optimal compression of graphs

Uses Software

• WebGraph

This page was built for publication: Entropy of some models of sparse random graphs with vertex-names

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5416367)