ONR Tracking Number: 21-000000617- New Perspectives on Critical Elements Detection in Complex Networ
Abstract
Assessing a complex network?s vulnerability and quantifying its robustness properties is an important research question that arises,in a variety of applications in telecommunication, transportation, social science, energy, homeland security and defense areas. This, research challenge is often addressed using the graph-theoretic concept of critical elements, namely a subset of elements (nodes an,d/or edges) in a network that satisfy some budget and structural constraints and whose removal (by some decision-maker) maximally de,grades desirable properties of the graph, e.g., its connectivity.From an application standpoint, the primary motivation for the crit,ical elements detection problem is two-fold. On the one hand, when attacking an adversarial network (e.g., to disrupt communications, in a terrorist network), the decision-maker can solve the critical elements detection problem to identify the most favorable nodes,(or edges, structures) to interdict. On the other hand, the critical elements detection problem can be used for vulnerability and ro,bustness analysis in the decision-maker?s own network. That is, the decision-maker seeks the nodes (or edges, structures) in their o,wn network, whose removal is most favorable to an adversary (e.g., a terrorist organization), or whose removal allows to estimate th,e worst-case network connectivity properties under random failures or a natural disaster.The critical elements detection concept has, natural applications in a number of other important domains, e.g., social network analysis and epidemic control. For example, in so,cial networks each node corresponds to a person, edges represent some type of relationship (or interaction) between two people (e.g.,, friendship, collaboration), and critical nodes are often referred to as the ?key players?, e.g., leaders of an organization, or co,mmunity. Thus, critical elements detection models can be used to identify which relationships are the most influential in the spread, of rumors in a social network. In the context of epidemic control, the notion of critical nodes , of vaccination strategies for containing pandemic disease spread.In recent years, the research stream outlined above has received a, significant amount of attention in the combinatorial optimization and network science literature. However, there are a number of si,mplifications in the existing combinatorial optimization studies that limit their applicability in many networks that arise in pract,ice. In this project, we propose three research directions that address these limitations, namely, we consider advanced critical ele,ments detection problems that involve: (i ) uncertainty with respect to the network structure, (ii ) complex connectivity/cohesivene,ss measures, and (iii ) network and decision dynamics.The main goal of the project is to develop sound methodological approaches for, dealing with general classes of the critical elements detection problem in uncertain and possibly dynamic settings. Our techniques,are based on the ideas at the intersection of robust and combinatorial optimization as well as network analysis. We propose to estab,lish relevant theoretical and structural properties of our mathematical optimization models, and to develop corresponding solution m,ethods (including both exact algorithms and those that provide near-optimal solutions). If successful, the proposed work will lead t,o mathematical models that are either directly applicable in practical network settings or provide useful insights that can be explo,ited for assessing a complex network?s vulnerability and its robustness properties.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 08, 2022
- Source ID
- N000142212674
Entities
People
- Jourdain Lamperski
Organizations
- Office of Naval Research
- United States Navy
- University of Pittsburgh