CAREER: Discovering Hidden Structure in Networks: Algorithms and Barriers

The objective of this project is to study properties of network data when the total data is too large to look at or the access to the data in some other way restricted, e.g., we can look only at the neighborhoods of some data points. Much real-world data is indeed of this type, like the link structure of web pages or the call records of cell phones. From this partial data, we still want to answer questions about the entire network, like finding communities within the network. This network inference and network reconstruction is made possible by making assumptions on the process that generated the network. In addition to the research on network inference and reconstruction algorithms, the investigator will train students, from the secondary to graduate level, in this topic, and disseminate knowledge through a monograph. The investigator has partnered with the Kohl Children's Museum of Greater Chicago to develop exhibits and programming to raise children’s interest and understanding of probability theory and will continue to engage with the public through the media. The project will study three research directions. (1) Community Detection in Spatial Networks: Traditionally, probabilistic network models have not included a spatial dimension and thus do not accurately reflect transitive behavior in real-world networks, for example, “the friend of my friend is also my friend.'' The project will work towards a theory for spatial networks, answering foundational questions on statistical limits and developing efficient algorithms for inference. (2) Optimization for Inference: Optimization algorithms have been used with great success for inference problems on networks, yet there are some problems for which we do not know whether an optimization algorithm is the best algorithm for a given task. The project will investigate the power of optimization algorithms for network inference tasks, including semidefinite programming for community detection and quadratic programming for graph matching. (3) Reconstructing Networks: Network reconstruction tasks involve determining the connectivity structure of a large network given a noisy or fragmented copy of the network. The project will tackle open problems in reconstructing a network from unlabeled local neighborhoods of nodes, identifying a graph’s isomorphism class from its local neighborhoods, and planted subgraph recovery. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.