Complex networks and vertex pursuit games

复杂网络和顶点追踪游戏

• 批准号: RGPIN-2015-05409
• 负责人: Bonato, Anthony
• 金额: $ 1.46万
• 依托单位: Ryerson University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=645773
• 关键词: Complex; networks; vertex; pursuit; games

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.**

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