Graph Searching and Dynamic Processes

点击翻译按钮获取中文摘要

From physical computer systems and roadways, to Facebook and Twitter; networks are all around us. Very often, assets (information, agents, etc.) are moved around networks in response to external forces that act in the form of spreading a virus, damaging targeted or random nodes, or by a simple network intrusion. In the event of no external forces, assets often are moved according to a set of prescribed rules. This movement of assets around a network is an example of a dynamic process.******Graph searching and dynamic domination models consider an adversary or intruder in a network (an external force) and focus on the following question: how can the activity of an adversary be neutralized in a network? In graph searching, the goal is generally to locate a hidden mobile adversary, while for dynamic domination problems, the goal is generally to defend against a sequence of adversarial attacks. The study of such network security problems has largely been inspired by foundational issues in discrete mathematics and theoretical computer science. A long-term objective of my research program is to determine optimal resource allocation in graph searching and dynamic domination models.******In systems with no external forces, assets are moved around the network according to a set of rules. Many dynamic processes naturally manifest critical behaviour over time. For example, in moving grains of sand around a network, one can observe that though the size and timing of sandpile avalanches are unpredictable, the distribution of avalanches display an interesting regularity. This property to organize spatial or temporal scale independent behavior is called self-organized criticality. A long-term objective of my research program is to describe the long-term behaviour of dynamic processes on networks. ******The training of undergraduate students forms an integral part of this proposal.