Complex networks and 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.**