The Resilience of k-Cores in Graphs

<p>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.</p> <p>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.</p> <p>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.</p> <p>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.</p>

Name thesis:degree_name

Doctor of Philosophy (PhD)

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical Engineering and Computer Science

Year

2020

Author dc:creator

• Laishram, Ricky

Contributors dc:contributor

• Sucheta Soundarajan
• Graham Leuschke

• graph
• k-core
• network
• resilience
• Engineering

Repository record dc:identifier

https://surface.syr.edu/etd/1235

OAI identifier oai:identifier

oai:surface.syr.edu:etd-2236