Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01hx11xj01k
 Title: Influence Propagation in Graphs and Applications to Network Analysis Authors: Lee, Eun Jee Advisors: Abbe, Emmanuel AKulkarni, Sanjeev R Contributors: Applied and Computational Mathematics Department Keywords: ClusteringInfluence MaximizationInfluence Propagation Subjects: Applied mathematics Issue Date: 2018 Publisher: Princeton, NJ : Princeton University 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. URI: http://arks.princeton.edu/ark:/88435/dsp01hx11xj01k Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog: catalog.princeton.edu Type of Material: Academic dissertations (Ph.D.) Language: en Appears in Collections: Applied and Computational Mathematics