Text

theses

Given the topology of a graph G and a budget k, can we quickly find the best k edges to delete that minimize dissemination on G? Stopping dissemination on a graph is important in vari- ety of fields such as epidemic control and network administration. Understanding the tipping point is crucial to the success of minimizing dissemination. The tipping point of an entity (e.g, virus or memo) on an arbitrary graph only depends on (i) the topology of graph and (ii) the characteristics of the entity. In this work, we assume that we cannot control the characteristics of the entity such as its strength, death rate, and propagation rate. Thus, we can only modify the topology of the graph. In particular, we consider the problem of removing k edges from the graph. In order to minimize the dissemination, we need to reduce the graph’s connectivity. The connectivity of a graph is determined by the largest eigenvalue of its adjacency matrix. Therefore, reducing the leading eigenvalue can minimize the dissemination. In social graphs, the small gap between the largest eigenvalue and the second largest eigenvalue creates a chal- lenge for minimizing the leading eigenvalue. In this work, we propose a scalable algorithm called MET (short for Multiple Eigenvalues Tracking), which minimize the largest eigenvalue. MET can work well even if the gap between the top eigenvalues is small. We also propose a learning approach called LearnMelt, which is useful when the exact topology of graph is not available. We evaluate our algorithms on different types of graphs such as technological autonomous system networks and various social networks.

ETD_6161

M.S.

Includes bibliographical references

by Long T. Le

doi:10.7282/T3FB54P3

ETD graduate

The author owns the copyright to this work.