Date of Award

June 2020

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Electrical Engineering and Computer Science

Advisor(s)

Sucheta Soundarajan

Second Advisor

Graham Leuschke

Keywords

graph, k-core, network, resilience

Subject Categories

Engineering

Abstract

A k-core of a graph is defined as the maximal subgraph such that all the nodes in the subgraph has at least k neighbors within the subgraph. k-core have been used in a number of applications ranging from anomaly detection and finding influential spreaders in social networks, to studying the robustness of financial and ecological networks.

In our work, we study the effect of missing data (edges or nodes) to the k-core of a graph. In particular, we study three different type of changes. The first type of change is the core structural change, in which the rank order of nodes by k-core number is changed. The second type is the change in the size of the k -core, and it is called the core minimization. The final change we study is called graph unraveling, and it is associated with a change in the size of the graph itself.

We study a graph’s resilience changes – how can we efficiently tell if a graph is resilience to each of these changes? We then use our analysis to propose novel algorithms to make small modifications to a graph with the objective of maximizing its resilience. We show experimentally that our proposed method outperforms all considered baselines methods on real-world graphs.

Finally, we study the organization of the different k-shells in a graph (for different values of k). For example, in some graphs there are many connections between shells, while in other graphs, the shells are mostly disconnected from one another. We prove that this organization can have a huge impact on the resilience of a graph to the three changes we studied.

Access

Open Access

Download

Included in

Engineering Commons

Share

COinS