The Structure and Dynamics of Social Networks and Other Networked Systems

这笔赠款资助的研究将侧重于对社会网络和计算机网络等网络结构进行数学分析和建模。三个具体项目构成了将要开展的工作的核心。首先将开发计算机算法，用于检测和分析网络中的密集子图，也称为模块或社区，除了提供大规模网络结构的窗口外，还可以作为大型网络数据集中的粗粒化技术、可视化、图形布局以及自动网络摘要和特征提取的基础。第二个项目将着眼于网络对网络节点故障的弹性，这一主题在互联网等通信网络以及通过社会网络传播疾病的理论中具有直接应用。该项目将特别着眼于网络中多条独立路径的存在所产生的弹性，以及相关的k-分量的图论概念。第三个项目将侧重于开发探索性分析方法，以便利用机器学习和统计技术以无监督的方式发现大型网络数据集中的结构。这些技术旨在从大规模社会网络或生物网络等实验网络数据集中提取新知识。网络广泛存在于科学和技术中。互联网、万维网、在线社交网络和为活细胞提供动力的生物网络只是过去几年占据新闻头条的几个例子。这笔赠款资助的研究侧重于开发基本的新数学和实用的计算机方法，以了解和分析科学家正在获得的丰富的网络数据。我们目前对网络的理解存在一个重大问题，那就是我们面临的许多网络的巨大规模。例如，网络上有数十亿个节点，用现有的资源完全可视化整个网络是不可能的(即使有可能也不会很有用)。这里要开发的技术集中在回答网络“是什么样子”的问题上，即使我们不能直接看到它。一个项目将专注于网络中的“模块”--一组紧密相连的节点，它们可能对应于社会网络中的集团或社区，或者生物网络中的功能模块--并将开发自动发现这些模块的计算机方法，使实验者能够揭示网络的大规模结构。另一个项目将着眼于网络对其节点故障的复原力，这一问题对维持正常运行的通信网络至关重要，也与制定有效的疫苗接种战略有关，以防止疾病在社会网络上传播。第三个项目将开发自动化方法，揭示节点之间连接模式中迄今未见的规律，使科学家能够从网络数据中提取有用信息，即使在我们目前了解非常不完整的新兴领域也是如此。

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.