Network Comparison, a Cornerstone of the Foundations of Network Science

“大数据”越来越多地意味着大网络，因为这些数据要么直接涉及人类和动物移动模式、基因相互作用网络等关系结构，要么受到流行病学研究、城市研究和文化传播等潜在关系结构的影响。网络的大多数应用都依赖于比较网络，例如检测一个网络在一段时间内的变化，对类似类型的多个网络进行分类或归类，或者通过比较不同来源的网络来建立跨领域的类比。如何以原则性的方式比较两个网络，而不依赖于许多当前比较方法所使用的统计数据的特设选择，这是网络科学基础的关键。该项目将为网络的原则性、结构性比较问题带来数学、计算机科学和统计物理学的新思想。通过现有的合作，PI将利用这些新的比较方法来解决几个不同领域的问题，例如：食物网如何在纬度、海拔和温度等梯度上变化，细菌菌落的形态生长模式，人类文化和社区的进化，以及社会经济指标和流行病学之间的联系。我们的项目将开发新的严格和原则性的方法来比较复杂网络的结构。所采用的方法旨在摆脱单一尺度的汇总统计;为了开创新局面，我们必须从结构距离而不是统计推断的角度进行思考。与机器学习工具相结合，这种结构比较方法是朝着定义“真实世界网络空间”迈出的重要一步，这可以作为复杂网络理论的更严格基础。这些方法具有四个有利的特征：（1）它们系统地考虑了网络组织的多个尺度，（2）它们不依赖于预先识别两个网络的节点，（3）它们可以比较不同大小的网络，以及（4）它们不依赖于任何特定的网络增长生成模型。现有的网络比较方法很少（如果有的话）具有所有这些特征，并且那些确实存在的方法尚未得到广泛开发。这些功能使许多新的应用在一系列领域，包括生态学，微生物学，文化进化，流行病学。这个奖项反映了NSF的法定使命，并已被认为是值得通过评估使用基金会的智力价值和更广泛的影响审查标准的支持。

"Big data" increasingly means big networks, because such data either directly concerns relational structures as in human and animal mobility patterns, gene interaction networks, or is influenced by an underlying relational structure as in epidemiological studies, urban studies, and cultural diffusion. Most applications of networks rely crucially on comparing networks, for example to detect changes in one network across time, to categorize or classify multiple networks of similar types, or to build analogies across fields by comparing networks of different origins. The question of how to compare two networks in a principled way, without relying on the ad hoc choice of statistics used by many current comparison methods, is key to the foundations of network science. This project will bring to bear new ideas from mathematics, computer science, and statistical physics on the problem of principled, structural comparison of networks. Through pre-existing collaborations, the PIs will leverage these new comparison methods to address questions in several different areas, for example, about: how food webs change across gradients like latitude, altitude, and temperature,morphological growth patterns of bacterial colonies, the evolution of human culture and communities, and links between socio-economic indicators and epidemiology.Our project will develop new rigorous and principled methods of comparing the structure of complex networks. The methods to be pursued aim to get away from single-scale summary statistics; to break new ground, we must think in terms of structural distance rather than statistical inference. In combination with tools from machine learning, such structural comparison methods are an important step towards defining the "space of real-world networks", which could serve as a more rigorous basis for a theory of complex networks. These methods have four advantageous features: (1) they systematically consider multiple scales of network organization, (2) they do not depend on an identification of the nodes of the two networks beforehand, (3) they can compare networks of different sizes, and (4) they are not dependent on any particular generative model of network growth. Very few, if any, of the existing network comparison methods have all of these features, and those that do exist have not been extensively developed. These features enable many new applications in a range of areas, including ecology, microbiology, cultural evolution, and epidemiology.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.