Technical Program

Paper Detail

Paper Title Compression of Preferential Attachment Graphs
Paper IdentifierWE2.R7.4
Authors Tomasz Luczak, Adam Mickiewicz University, Poland; Abram Magner, University of Michigan, United States; Wojciech Szpankowski, Purdue University, United States
Session Lossless Compression II
Location Bièvre, Level 5
Session Time Wednesday, 10 July, 11:40 - 13:20
Presentation Time Wednesday, 10 July, 12:40 - 13:00
Manuscript  Click here to download the manuscript
Abstract We study structural properties of preferential attachment graphs (with parameter $m \geq 1$ giving the number of attachment choices that each new vertex makes) which intervene in the problem of graph structural compression: we seek to compactly describe a graph's structure by a bit string, throwing away its label information. In particular, we study the typical size of the automorphism group, as well as some relevant shape parameters of the directed version of the graph. Our result on the automorphism group completes the characterization of the number of symmetries for all fixed $m$. We then give an algorithmically efficient, asymptotically optimal algorithm for compression of unlabeled preferential attachment graphs and a precise estimate of the model's structural entropy.