Inference and information processing in networked systems

This dissertation examines theoretical and algorithmic aspects of two fundamental problems arising in the study of networked systems: (1) efficient information processing in sensor networks, and (2) inferring the structure of a network from incomplete data.;Costs associated with sensing, computing, and communicating give rise to a communication-accuracy tradeoff in sensor networks: communicating consumes significantly more resources than computing or sensing, but also enables nodes to collaboratively exchange information and obtain more accurate results. We describe and analyze a framework for decentralized optimization based on communicating sequentially along a cycle that passes through every node, rigorously demonstrating that, for a broad class of applications, in-network processing is more efficient than transmitting raw data to a fusion center. We also describe a novel family of consensus algorithms for practical, robust decentralized optimization, in which nodes are not required to maintain any routing information beyond their immediate neighbors. Finally, we describe a decentralized system using consensus algorithms for robust distributed computation and information dissemination.;Obtaining the structure of the network from experimental data is a core challenge at the heart of network science. Unfortunately; it is often difficult or impossible to obtain measurements which directly reveal network structure. The second part of this dissertation addresses the problem of inferring network structure from co-occurrence data: unordered lists of the nodes appearing in paths through the network. Co-occurrence data arise naturally in applications ranging from telecommunications to systems biology. The main challenge in network inference stems from the fact that co-occurrence data does not directly reveal the order of nodes in each path. Every permutation of co-occurring nodes produces a different feasible solution, leading to combinatorial explosion of the feasible set. However, physical principles underlying most networks suggest that not all feasible solutions are equally plausible. We develop network inference methods based on the intuition that nodes which co-occur frequently are probably closely connected. Because networks are inherently discrete objects, inference can be computationally demanding. Combining techniques born probabilistic modeling and statistical machine learning, we develop efficient inference methods that break the curse of dimensionality using randomization.