Broad-Scale Modeling of Complex Networks

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

Many objects of interest in technology, science, and medicine can be represented as networks, including the internet, the power grid, neural networks in the brain, and the contact networks between individuals over which diseases spread. Network theory, which is the subject of this research project, provides a mathematical representation of systems like these which helps us to understand and predict their behavior. This project focuses on modeling networked systems, using mathematical models and computer models. Network models have seen impressive successes in recent years, in areas such as computer and information networks and epidemiology, but a fundamental shortcoming of previous work has been an inability to accurately represent network structure at both small and large scales simultaneously. This project develops new classes of models that achieve this goal, thereby more accurately representing networks as they appear in real life and improving our understanding and ability to predict their behavior. Specific goals of the project include: development of new multiscale mathematical and computer models of networked systems; testing and validation of models to demonstrate how well they capture the features of the systems they represent; model selection methods for determining how best to represent a particular system; anomaly detection in networks; improved computational methods to allow calculations to run efficiently on current computer hardware; and a range of specific applications, for instance to modeling of network resilience and the spread of disease. This project will develop and apply new classes of mathematical models for representing and analyzing networked systems. Network models find wide uses in methods for the analysis of network data, such as community detection, embedding, and visualization, and as the foundation for simulation and modeling of network processes, such as resilience of systems to failure of their components, the spread of diseases over contact networks, or the design and refinement of network protocols and algorithms. A fundamental shortcoming of current network models, however, is their inability to capture network structure accurately on both small and large scales. Models based on local structural motifs, such as the configuration model or subgraph models, capture small-scale structure well, but fail with large-scale structure such as communities, stratification, or core-periphery structure. Models that capture large-scale structure, such as block models, are normally locally tree-like and hence fail badly to capture the small scale. This project will develop a new class of random graph models that naturally integrates the large and small, along with methods for analyzing the models' properties and for rapid Monte Carlo sampling. Maximum-likelihood fitting methods will be developed to fit models to real-world network data, enabling accurate generalization, link prediction, and network reconstruction. Statistical methods for the models will also be developed, including goodness-of-fit tests and model selection methods, along with specific applications, for instance to anomaly detection, network resilience, and epidemic modeling.