Xiaoran Yan (University of Southern California)
Abstract. In this talk, we highlight the interplay between a dynamic process and the structure of the network on which it is defined. Specifically, we examine the impact of this interaction on the quality-measure of network clusters and node centrality. This enables us to effectively identify network communities and important nodes participating in the dynamic process. As the first step towards this objective, we introduce an umbrella framework for defining and characterizing an ensemble of dynamic processes on a network as linear operators. We show that the traditional Laplacian framework for diffusion and random walks is a special case of this framework. This generalization also allows us to model some epidemic processes over a network.
Theoretically, we prove that the classic Cheeger’s inequality (which relates a spectral quantity of the Laplacian matrix of the network to the conductance of the best cluster in the network) can be extended from the Laplacian-conductance setting to our operator-quality setting. Empirically, we demonstrate that the operators under this framework can lead to divergent views about who the central nodes are and what are the corresponding communities for both synthetic and real-world networks.