Special Machine Learning Seminar

  • ABRAM MAGNER
  • Postdoctoral Research Fellow
  • NSF Center for the Science of Information
  • Purdue University
Seminars

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.

For More Information, Please Contact: 
Keywords: