Abstract:
I will discuss mathematical aspects of my recent work on two related problems at the intersection of random graphs and information theory: (i) node order inference -- for a dynamic random graph model, determine the extent to which the order in which nodes arrived can be inferred from the graph structure, and (ii) compression of structures -- for a given graph model, exhibit an efficiently computable and invertible mapping from unlabeled graphs to bit strings with minimum possible expected code length.
Both problems are connected to the study of the symmetries of the graph model, as well as another combinatorial quantity -- the typical number of feasible labeled representatives of a given structure. I will focus on the case of the preferential attachment model, for which we are able to give a (nearly) complete characterization of the behavior of the size of the automorphism group, as well as a provably asymptotically optimal algorithm for (ii). I will also discuss progress on efficiently computable optimal estimators for certain natural formulations of (i).