Inference and Compression Problems on Growing Networks
Networks in the real world are dynamic -- nodes and edges are added and removed over time, and time-varying processes (such as epidemics) run on them. In this talk, I will describe some of my recent work with collaborators on inference and compression problems that involve this time-varying aspect of networks. I will focus on two related problems along these lines: (i) node arrival order inference -- for a dynamic 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 efficient algorithm for invertibly mapping network structures (i.e., graph isomorphism types) to bit strings of minimum expected length. For both problems, I give both statistical limits and efficient algorithms for achieving those limits. Finally, I briefly describe some ongoing projects that continue these lines of work.