東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Influence Propagation in Graphs and ...

Lee, Eun Jee.

Linked to FindBook

Google Book

Amazon

博客來

Influence Propagation in Graphs and Applications to Network Analysis.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Influence Propagation in Graphs and Applications to Network Analysis./
Author:	Lee, Eun Jee.
Published:	Ann Arbor : ProQuest Dissertations & Theses, : 2018,
Description:	108 p.
Notes:	Source: Dissertations Abstracts International, Volume: 80-04, Section: B.
Contained By:	Dissertations Abstracts International80-04B.
Subject:	Applied Mathematics. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10829636
ISBN:	9780438535275

Influence Propagation in Graphs and Applications to Network Analysis.
Lee, Eun Jee.

Influence Propagation in Graphs and Applications to Network Analysis. - Ann Arbor : ProQuest Dissertations & Theses, 2018 - 108 p.

Source: Dissertations Abstracts International, Volume: 80-04, Section: B.

Thesis (Ph.D.)--Princeton University, 2018.

This item must not be sold to any third party vendors.

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.

ISBN: 9780438535275Subjects--Topical Terms:

1669109
Applied Mathematics.

Influence Propagation in Graphs and Applications to Network Analysis.
LDR:02933nmm a2200313 4500 001 2210443
005 20191121124221.5
008 201008s2018 ||||||||||||||||| ||eng d
020 $a 9780438535275
035 $a (MiAaPQ)AAI10829636
035 $a (MiAaPQ)princeton:12662
035 $a AAI10829636
040 $a MiAaPQ $c MiAaPQ
100 1 $a Lee, Eun Jee. $3 3437582
245 1 0 $a Influence Propagation in Graphs and Applications to Network Analysis.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2018
300 $a 108 p.
500 $a Source: Dissertations Abstracts International, Volume: 80-04, Section: B.
500 $a Publisher info.: Dissertation/Thesis.
500 $a Advisor: Abbe, Emmanuel A.;Kulkarni, Sanjeev R.
502 $a Thesis (Ph.D.)--Princeton University, 2018.
506 $a This item must not be sold to any third party vendors.
520 $a 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.
590 $a School code: 0181.
650 4 $a Applied Mathematics. $3 1669109
690 $a 0364
710 2 $a Princeton University. $b Applied and Computational Mathematics. $3 3182352
773 0 $t Dissertations Abstracts International $g 80-04B.
790 $a 0181
791 $a Ph.D.
792 $a 2018
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10829636