Complex networks and vertex pursuit games

研究网络产生了基本问题，网络出现在自然和技术世界的方方面面。我们如何对网络中的影响力传播进行建模？网络是否有底层的几何体？如果有，我们如何使用网络结构来揭示几何体？我们如何最有效地中和网络中的敌对活动？*建议的项目使用图论、概率和几何中的最先进的数学工具来解决这些问题，并旨在实现以下目标：分析现实世界网络的新模型和现有模型，揭示网络基础几何和图结构之间的交互作用，并推进顶点追逐游戏的数学研究中的知识前沿。重点将放在建立在线社交网络的模型和模拟影响力在这些网络中的传播，并特别关注实际应用。*复杂网络给研究人员带来了大数据挑战。我们的研究结果对于那些关心数据环境的人来说将是重要的，例如，在谷歌或Facebook上发现的数据环境，谷歌上的页面被索引超过60万亿，Facebook上包含超过10亿用户账户。这项研究还将有助于我们理解复杂生物过程的网络模型中发现的极其复杂的环境，例如代表复杂碳水化合物、信号系统或各种威胁生命的疾病(如主要癌症)的代谢路径的网络模型。*顶点追逐游戏是用于停止对手在网络上的活动的组合模型。在这些游戏中，特工或警察试图抓获在网络顶点上逍遥法外的入侵者或强盗。这类游戏研究最多的是警察和强盗，在图中抓获强盗所需的最小警察数量是其警察数量。COPS和Robbers及其变种在图论中形成了一个活跃的主题，新的结果迅速出现在文献中。我们对该领域的具体贡献将是解决Meyniel猜想的特殊情况，该猜想提供了CoP数的界限，以期最终解决该猜想。*为实验数据量身定做的严格图形模型为复杂网络的结构和演化提供了丰富的洞察力。我们对复杂网络的研究回应了该领域的核心理论问题，具有潜在的应用前景，从改进的推荐系统到绘制情感在社会网络中的传播情况，以及利用蛋白质相互作用网络的性质来治疗疾病。在顶点追逐游戏(如警察和强盗)中的研究将加速该领域的发现，刺激图论中的新方向和新问题，并在复杂网络中监视或阻止对手活动方面有应用。

Fundamental questions arise from studying networks, which emerge in every aspect of the natural and technological world. How can we model the spread of influence in a network? Do networks have an underlying geometry, and if so, how can we use the network structure to uncover the geometry? How do we most efficiently neutralize adversarial activity in a network?***The proposed project addresses these questions using state-of-the-art mathematical tools from graph theory, probability, and geometry, and aims to achieve the following objectives: to analyze new and existing models for real-world networks, to uncover the interaction between the underlying geometry of the network and graph structures, and to advance the frontier of knowledge in the mathematical study of vertex pursuit games. Major emphasis will be placed on building models of on-line social networks and simulating the spread of influence in these networks, with special attention to practical applications.******Complex networks pose big data challenges to researchers. The results of our research will be important to those concerned with data environments such as the ones found, for example, on Google where over 60 trillion pages are indexed, or on Facebook, which contains over one billion user accounts. The research will also benefit our understanding of the extremely complicated environments found in network models of sophisticated biological processes like those representing the metabolic pathways of complex carbohydrates, signaling systems, or various life threatening diseases such as the major cancers.***Vertex pursuit games are combinatorial models for the halting of an adversary's activity on a network. In these games, agents or cops are attempting to capture an intruder or robber who is loose on the vertices of a network. The most studied such game is Cops and Robbers, and the minimum number of cops needed to capture the robber in a graph is its cop number. Cops and Robbers and its variants form an active topic in graph theory, with new results rapidly appearing in the literature. Our specific contribution to the field will be to settle special cases of Meyniel's conjecture, which provides bounds on the cop number, with a view of eventually settling the conjecture.***Rigorous graph models tailored to experimental data provide rich insight into the structure and evolution of complex networks. Our research on complex networks responds to central theoretical questions in the field, and has potential applications ranging from improved recommender systems, mapping the spread of emotional contagion in a social network, and the treatment of disease using properties of protein interaction networks. The research in vertex pursuit games such as Cops and Robbers will accelerate discoveries in that field, spur new directions and problems in graph theory, and have applications to the monitoring or halting of adversarial activity in complex networks.**