Graph searching and modelling complex networks

网络出现在自然和技术世界的方方面面，从Facebook和Instagram等在线社交网络到比特币交易，再到活细胞中的蛋白质及其生化相互作用。网络或图模拟称为顶点的对象之间的交互；相互作用的两个顶点形成一条边。基本的方向来自对网络的研究，例如找到有效的方法来检测或中和对手活动，到对推动网络如何随时间形成的隐藏机制进行建模。在图搜索中，我们考虑简化的组合模型，用于检测或中和对手在网络上的活动。这类游戏研究最多的是警察和强盗，其中警察和强盗只能移动到与他们共享一条边的顶点。Cops和Robbers及其变种形成了图论中一个新兴的主题，新的结果迅速出现在文献中。复杂的网络是大规模的，并且会随着时间的推移而发展。例如，谷歌在网络上索引数万亿个页面，而Facebook上有超过10亿个用户账户。因此，数学模型是模拟从复杂网络中挖掘的大数据属性的强大工具；分析这些模型也带来了有趣的数学挑战。早期的优先连接和复制等模型成功地模拟了这些网络的许多性质，如幂函数度分布和节点之间的低距离。我的研究计划旨在在五年的拨款期间实现以下短期目标：1)推进图搜索领域，重点是局部化游戏、平面图上的顶点搜索以及由Meyniel猜想引发的节流数字。2)开发新的复杂网络模型，包括迭代局部模型和超图模型。我将使用图论、博弈论、几何学和概率论中的复杂数学工具来解决这些目标。我将非常重视HQP培训。图搜索研究的提出将推动这一领域的发展，并催生图论的新方向和新问题。在这些主题上的突破可能会在移动计算和机器人等领域产生创新的未来应用。为实验数据量身定做的严格图形模型提供了对现实世界复杂网络的结构和演变的丰富洞察力。我提出的关于复杂网络的研究回应了该领域的核心理论问题，并具有潜在的应用，从模拟社会传染的传播到使用超越现有二元范式的新方法绘制社区结构。这项工作的应用将使数学和理论计算机科学的研究人员感兴趣。

Networks emerge in every aspect of the natural and technological world, ranging from on-line social networks such as Facebook and Instagram, to Bitcoin transactions, to proteins in a living cell and their biochemical interactions. Networks, or graphs, model interaction between objects called vertices; two vertices that interact form an edge. Fundamental directions emerge from studying networks, such as finding efficient ways to detect or neutralize adversarial activity, to modelling the hidden mechanisms driving how networks form over time. In graph searching, we consider simplified, combinatorial models for the detection or neutralization of an adversary's activity on a network. The most studied such game is Cops and Robbers, where the cops and robber can only move to vertices with which they share an edge. Cops and Robbers and its variants form an emerging topic in graph theory, with new results rapidly appearing in the literature. Complex networks are large-scale and evolve over time. For example, Google indexes trillions of pages on the web, while there are over one billion user accounts on Facebook. Mathematical models, therefore, are powerful tools for simulating properties of the big networked data mined from complex networks; analyzing these models also presents fascinating mathematical challenges. Early models such as preferential attachment and copying successfully simulated many properties of these networks, such as power law degree distributions and low distances between nodes. My research program aims to achieve the following short-term objectives over the five-year period of the grant: 1) Advance the field of graph searching, with an emphasis on the localization game, vertex pursuit on planar graphs, and the throttling number motivated by Meyniel's conjecture. 2) Develop new models for complex networks, including iterated local and hypergraph models. I will address these objectives using sophisticated mathematical tools from graph theory, game theory, geometry, and probability. I will place on a strong emphasis on HQP training. The proposed research on graph searching will advance the state-of-the-art in that field, and spur new directions and problems in graph theory. Breakthroughs on these themes will potentially have innovative future applications in areas such as mobile computing and robotics. Rigorous graph models tailored to experimental data provide rich insight into the structure and evolution of real-world, complex networks. My proposed research on complex networks responds to central theoretical questions in the field, and has potential applications from modelling the spread of social contagion to mapping community structure using new approaches beyond existing dyadic paradigms. Applications of this work will be of interest to researchers in mathematics and theoretical computer science.