Influence Propagation in Graphs and Applications to Network Analysis

Abstract

The phenomenon of influence propagation is concerned with how influence spreads in a network from a set of seeds. One of the most widely adopted models that describe such propagation phenomena is the independent cascade model, where influence propagates from the seed-nodes along the edges with independent probabilities. This thesis focuses on influence propagation in the independent cascade model and studies its applications to various problems concerned with graphs and networks.

A fundamental problem in influence propagation is to measure the size of the influence spread, and perhaps, the most basic measure is the influence, the expected number of nodes that a seed set can influence in the independent cascade model. Unfortunately, this is #P hard to compute. Thus, many estimators on the influence were proposed. In this thesis, we propose deterministic bounds on the influence. We develop mainly two types of bounds: (i) using the spectral norm of a modified Hazard matrix to handle sensitive edges and (ii) exploiting r-nonbacktracking walks and Fortuin-Kasteleyn-Ginibre (FKG) type inequalities to compute bounds via message passing algorithms.

We then study influence maximization problem, which aims to select the $k$ nodes in a network that maximize the influence when the propagation starts from these k nodes. In this thesis, we investigate this problem in boundary cases and provide solutions to tree networks.

Finally, this thesis introduces the mutual influence (MI), a measure of how similarly influential two nodes in a network are. We establish properties of the MI and investigate its application to clustering. We propose two clustering methods based on MI: (i) we use MI as a similarity metric for spectral clustering, and (ii) we use MI to identify cluster leaders that are individually influential but not influential on each other.