Jon Kleinberg, Cornell University
Approved for Public Release
ABSTRACT
The proposed project will pursue basic research questions in network modeling and analysis. Networks as a mathematical and computational formalism have found wide application across the sciences and engineering, due to the flexible way in which they model pairwise interactions in many domains.
However, the conceptual architecture that networks provide is limited by the research community's lack of understanding of several fundamental issues. First, the field does not have theories that effectively interpolate between the local and global levels of scale in large networks: while there are effective ways of modeling what happens at both of these extremes, these models are not unified, and so there is correspondingly no way to translate observations at one extreme to predictions at the other. Second, the field does not have theories that extrapolate beyond an observable network to consider the network's interaction with its surrounding environment. This creates limitations in reasoning about the effect of external events or shocks to the network, or in leveraging information about structure or dynamics taking place outside the network. And third, even when considering possible network models, there is a lack of robust methods for evaluating or comparing different models to each other.
The project will pursue basic research to address these fundamental questions. The technical approach will be based on extending a set of formalisms that for modeling network structure using graph-theoretic and probabilistic approaches, together with dynamic models of node behavior rooted in game theory, discrete probability, and Bayesian inference. The research will exploit recently discovered but still unexplained commonalities in the properties of dynamic models across multiple formalisms, all of which suggest ways of imposing different levels of scale on the structure and dynamics of a network. The theoretical results will be supplemented with both computational simulations and analysis of publicly available open network data.
Progress on these fundamental questions would have a clear and transformative effect on the field of networks. Even with only a modest ability to transfer theoretical formalisms across different levels of scale both within networks and to their surrounding environments, it would already become possible to use insights about micro-level interactions and make predictions about network dynamics over larger aggregates of nodes and to global properties of the network itself; and it would become possible to translate in the other direction as well, making inferences about microlevel behaviors from what we observe about large-scale network structure and dynamics. Analogous possibilities would open up in transferring predictions between the events taking place inside a network and the events taking place in its surrounding environment. And this progress in turn would have potential impact on DoD capabilities through applied and empirical insights into the different levels of scale in technological and social systems that are modeled by networks, including communication systems, organizations, societal dynamics, and many other settings. None of this is possible at present, but it would be enabled by progress on these fundamental problems of bridging levels of scale in networks.