Graph Searching and Dynamic Processes

图搜索和动态过程

• 批准号: RGPIN-2018-04059
• 负责人: Messinger, MargaretEllen
• 金额: $ 1.17万
• 依托单位: Mount Allison University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=675735
• 关键词: Graph; Searching; 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.

从物理计算机系统和道路，到Facebook和Twitter;网络无处不在。通常，资产（信息、代理等）在网络中移动，以响应以传播病毒、破坏目标节点或随机节点或简单网络入侵的形式起作用的外部力量。 在没有外力的情况下，资产往往根据一套规定的规则转移。 资产在网络中的这种移动是动态过程的一个例子。图搜索和动态支配模型考虑网络中的对手或入侵者（外部力量），并关注以下问题：如何在网络中中和对手的活动？在图搜索中，目标通常是定位隐藏的移动的对手，而对于动态支配问题，目标通常是防御一系列对抗性攻击。这些网络安全问题的研究在很大程度上受到离散数学和理论计算机科学中基础问题的启发。 我的研究计划的一个长期目标是确定图搜索和动态支配模型中的最优资源分配。在没有外力的系统中，资产根据一组规则在网络中移动。 随着时间的推移，许多动态过程自然会表现出临界行为。例如，在一个网络中移动沙粒，人们可以观察到，尽管沙堆雪崩的大小和时间是不可预测的，但雪崩的分布显示出一种有趣的规律性。这种组织空间或时间尺度独立行为的特性称为自组织临界性。 我的研究计划的一个长期目标是描述网络上动态过程的长期行为。 ****** 大学生的培训是本提案的一个组成部分。