The research funded under this grant will focus on the mathematical analysis and modeling of the structure of networks such as social networks and computer networks. Three specific projects form the core of the work to be undertaken. The first will develop computer algorithms for the detection and analysis of dense subgraphs within networks, also called modules or communities, which, in addition to providing a window on large-scale network structure, can serve as a foundation for coarse-graining techniques, visualization, graph layout, and automated network summarization and feature extraction in large network data sets. The second project will look at the resilience of networks to the failure of network nodes, a topic that has direct applications in communications networks such as the Internet as well as in the theory of the spread of disease through social networks. The project will look in particular at the resilience created by the existence of multiple independent paths in networks and the related graph theoretical concept of k-components. The third project will focus on the development of exploratory analysis methods for discovering structure in large network data sets in an unsupervised fashion, making use of machine learning and statistical techniques. These techniques are aimed at the extraction of new knowledge from experimental network data sets such as large-scale social networks or biological networks.
Networks occur widely in the sciences and technology. The Internet, the World Wide Web, online social networks, and the biological networks that power living cells are just a few of the examples that have grabbed headlines in the last few years. The research funded under this grant focuses on the development of both fundamental new mathematics and practical computer methods for understanding and analyzing the wealth of network data that is becoming available to scientists. A significant problem with our current understanding of networks is created by the sheer size of many of the networks we are faced with. The web, for example, has nodes numbering in the billions, and a complete visualization of the entire network is impossible with current resources (and probably wouldn't be very useful even if it were possible). The techniques to be developed here focus on answering the question of what a network "looks like," even when we can't look at it directly. One project will focus on "modules" in networks -- groups of tightly connected nodes, which may correspond to cliques or communities in a social network or functional modules in a biological network -- and will develop computer methods for automatically discovering these modules, allowing the experimenter to uncover the large-scale structure of a network. Another project will look at resilience of networks to the failure of their nodes, an issue that is of prime importance for the maintenance of functioning communication networks and is also related to the development of efficient vaccination strategies to prevent the spread of disease over social networks. A third project will develop automated methods for revealing hitherto unseen regularities in the connection patterns between nodes, allowing scientists to extract useful information from network data even in emerging areas where our current understanding is very incomplete.
