Networks are crucial to the future; these networks may govern the effectiveness of sensing and communication, social interactions, and power transmission. Current network research primarily proceeds on a disconnected problem-by-problem basis; this ignores the underlying similarities of problem domains, and is increasingly untenable as technology challenges proliferate. This proposal takes first steps towards a more universal science for network algorithms. The intellectual foundations of our approach are new connections between networks and Markov Random Fields (MRFs) - a classic formalism for statistical inference. We develop general-purpose algorithmic frameworks for two broad classes of network problems: (a) distributed combinatorial optimization; based on message-passing MRF estimation heuristics, like Belief Propagation. This simultaneously provides new algorithms for scheduling, network formation, facility location etc. (b) network data analysis; based on regularization and rank-minimization techniques used for learning in MRFs. This enables new methods for tomography, social network clustering, localization etc. For any particular application, our framework generates a new and competitive first-cut solution, which domain knowledge easily improves into a state-of-the-art solution. This research will significantly impact both how we control large-scale networks, and interpret the high-dimensional data they generate. By providing a common algorithmic language, it will facilitate the easy migration of techniques across fields. Industry will continuously influence and absorb this research, via the WNCG industrial affiliates program at UT. We will build a social network for education, which will expose K-12 and undergraduates to network research, enhance pedagogical resources at UT, and generate real-world social network data.
