Graph searching and 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.