Skip navigation
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 A
Kulkarni, Sanjeev R
Contributors: Applied and Computational Mathematics Department
Keywords: Clustering
Influence Maximization
Influence 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

Files in This Item:
File Description SizeFormat 
Lee_princeton_0181D_12662.pdf2.02 MBAdobe PDFView/Download


Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.