Date of Award
Doctor of Philosophy (PhD)
Electrical Engineering and Computer Science
Complex Networks, Computer Science, Contagion, Graph Theory, Protection, Spread
Computer Sciences | Physical Sciences and Mathematics
In real-world complex networks, harmful spreads, commonly known as contagions, are common and can potentially lead to catastrophic events if uncontrolled. Some examples include pandemics, network attacks on crucial infrastructure systems, and the propagation of misinformation or radical ideas. Thus, it is critical to study the protective measures that inhibit or eliminate contagion in these networks. This is known as the network protection problem.
The network protection problem investigates the most efficient graph manipulations (e.g., node and/or edge removal or addition) to protect a certain set of nodes known as critical nodes. There are two types of critical nodes: (1) predefined, based on their importance to the functionality of the network; (2) unknown, whose importance depends on their location in the network structure. For both of these groups and with no assumption on the contagion dynamics, I address three major shortcomings in the current network protection research: namely, scalability, imprecise evaluation metric, and assumption on global graph knowledge.
First, to address the scalability issue, I show that local community information affects contagion paths through characteristic path length. The relationship between the two suggests that, instead of global network manipulations, we can disrupt the contagion paths by manipulating the local community of critical nodes.
Next, I study network protection of predefined critical nodes against targeted contagion attacks with access to partial network information only. I propose the CoVerD protection algorithm that is fast and successfully increases the attacker’s effort for reaching the target nodes by 3 to 10 times compared to the next best-performing benchmark.
Finally, I study the more sophisticated problem of protecting unknown critical nodes in the context of biological contagions, with partial and no knowledge of network structure. In the presence of partial network information, I show that strategies based on immediate neighborhood information give the best trade-off between performance and cost. In the presence of no network information, I propose a dynamic algorithm, ComMit, that works within a limited budget and enforces bursts of short-term restriction on small communities instead of long-term isolation of unaffected individuals. In comparison to baselines, ComMit reduces the peak of infection by 73% and shortens the duration of infection by 90%, even for persistent spreads.
Hozhabrierdi, Pegah, "Protection against Contagion in Complex Networks" (2022). Dissertations - ALL. 1643.