Graph searching and modelling complex networks

图搜索和复杂网络建模

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

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.

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