On the epidemic threshold of a network
Time and place
12:45–1:45 PM on Thursday, July 14th, 2022; MR1
Sandra Kingan (Brooklyn College)
Abstract
Many real-world phenomena can be modeled as graphs. A graph consists of a set of vertices or nodes and pairs of unordered vertices called edges or links. For example, a social network of people where the vertices are people and the edges are relationships is a graph. A vertex centrality measure assigns a number to every vertex of the graph with the goal of ranking vertices. The degree of a vertex is a straightforward measure of importance in the sense that a person who knows many people in a social network is important. There are a few other measures of centrality such as betweenness centrality, closeness centrality, eigenvector centrality, PageRank etc.
In this talk I will present an approach to vertex centrality based on the deck of vertex deletions. It is motivated by the Vertex Reconstruction Conjecture, which asks whether or not a graph G with n vertices v1, v2, ..., vn can be reconstructed from its deck of vertex deleted subgraphs G-v1, G-v2, … , G-vn. The impact of vertex v is measured by removing it and considering the subgraph G-v. Then various parameters can be calculated for G and compared with the corresponding parameters for G-v. When this is done for all the vertices, a ranking of the vertices is obtained.
The parameter we examined is the largest eigenvalue of the adjacency matrix of the graph. It is a key quantity in the study of processes such as a virus spreading on a network of people or computers, ideas spreading on social media, viral marketing, energy levels of electrons in molecules, etc. The inverse of the largest eigenvalue is the epidemic threshold in a non-linear dynamical system model of viruses spreading on a network. We define the spread centrality of a vertex as the difference between the largest eigenvalues of G and G-v and examine its relationship to other centrality measures. We will show that for graphs with large girth, the average spread centrality tends to zero as the number of vertices grows. Finally, we will present two vaccination strategies and a simulation of their effectiveness. This is joint work with V. Cherniavskyi and G. Dennis.
