Spectral Sparsification For Directed Graphs Via Random Sampling

In scientific fields like network study, a graph is frequently used to represent practical problems. But the graph turns to be complicated when the scale of problem is getting large. In this case, a sparse graph would be a wonderful replacement if some properties can be preserved well, like Rayleigh Quotient. Many researchers paid attention to this problem and developed methods like cut sparsification and spectral sparsification.This thesis focuses on spectral sparsification for directed graphs via random sam-pling. Considering the fact that many practical issues like communication network should be represented by directed graphs due to the existence of asymmetric relationship be-tween individuals, we make improvement in this thesis to apply the spectral sparsifi-cation method to directed graphs. As the Laplace matrix of a directed graph is not symmetric, we modify the task and do random sampling for two interdependent vari-ables. Afterwards, we introduce the concept of effective resistance in directed graph, and subsequently calculate the probability for random sampling. The conclusion offers us a theoretical guarantee for this method. At the end, we provide a numerical simulation.