Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01hx11xj01k
DC FieldValueLanguage
dc.contributor.authorLee, Eun Jee-
dc.contributor.otherApplied and Computational Mathematics Department-
dc.date.accessioned2018-10-09T21:09:47Z-
dc.date.available2018-10-09T21:09:47Z-
dc.date.issued2018-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/dsp01hx11xj01k-
dc.description.abstractThe 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.-
dc.language.isoen-
dc.publisherPrinceton, NJ : Princeton University-
dc.relation.isformatofThe Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog: <a href=http://catalog.princeton.edu> catalog.princeton.edu </a>-
dc.subjectClustering-
dc.subjectInfluence Maximization-
dc.subjectInfluence Propagation-
dc.subject.classificationApplied mathematics-
dc.titleInfluence Propagation in Graphs and Applications to Network Analysis-