國立高雄大學圖資館 |

Language: English

Back

Graph diffusions and matrix function...

Kloster, Kyle.

Graph diffusions and matrix functions: Fast algorithms and localization results.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Graph diffusions and matrix functions: Fast algorithms and localization results.
Author:	Kloster, Kyle.
Published:	Ann Arbor : ProQuest Dissertations & Theses, 2016
Description:	114 p.
Notes:	Source: Dissertation Abstracts International, Volume: 77-12(E), Section: B.
Notes:	Adviser: David F. Gleich.
Contained By:	Dissertation Abstracts International77-12B(E).
Subject:	Applied mathematics.
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10149739
ISBN:	9781369048353

Graph diffusions and matrix functions: Fast algorithms and localization results.
Kloster, Kyle.

Graph diffusions and matrix functions: Fast algorithms and localization results. - Ann Arbor : ProQuest Dissertations & Theses, 2016 - 114 p.

Source: Dissertation Abstracts International, Volume: 77-12(E), Section: B.

Thesis (Ph.D.)--Purdue University, 2016.

Network analysis provides tools for addressing fundamental applications in graphs such as webpage ranking, protein-function prediction, and product categorization and recommendation. As real-world networks grow to have millions of nodes and billions of edges, the scalability of network analysis algorithms becomes increasingly important. Whereas many standard graph algorithms rely on matrix-vector operations that require exploring the entire graph, this thesis is concerned with graph algorithms that are local (that explore only the graph region near the nodes of interest) as well as the localized behavior of global algorithms. We prove that two well-studied matrix functions for graph analysis, PageRank and the matrix exponential, stay localized on networks that have a skewed degree sequence related to the power-law degree distribution common to many real-world networks. Our results give the first theoretical explanation of a localization phenomenon that has long been observed in real-world networks. We prove our novel method for the matrix exponential converges in sublinear work on graphs with the specified degree sequence, and we adapt our method to produce the first deterministic algorithm for computing the related heat kernel diffusion in constant-time. Finally, we generalize this framework to compute any graph diffusion in constant time.

ISBN: 9781369048353Subjects--Topical Terms:

377601
Applied mathematics.

Graph diffusions and matrix functions: Fast algorithms and localization results.
LDR:02292nmm a2200301 4500 001 502121
005 20170619070727.5
008 170818s2016 ||||||||||||||||| ||eng d
020 $a 9781369048353
035 $a (MiAaPQ)AAI10149739
035 $a AAI10149739
040 $a MiAaPQ $c MiAaPQ
100 1 $a Kloster, Kyle. $3 766144
245 1 0 $a Graph diffusions and matrix functions: Fast algorithms and localization results.
260 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2016
300 $a 114 p.
500 $a Source: Dissertation Abstracts International, Volume: 77-12(E), Section: B.
500 $a Adviser: David F. Gleich.
502 $a Thesis (Ph.D.)--Purdue University, 2016.
520 $a Network analysis provides tools for addressing fundamental applications in graphs such as webpage ranking, protein-function prediction, and product categorization and recommendation. As real-world networks grow to have millions of nodes and billions of edges, the scalability of network analysis algorithms becomes increasingly important. Whereas many standard graph algorithms rely on matrix-vector operations that require exploring the entire graph, this thesis is concerned with graph algorithms that are local (that explore only the graph region near the nodes of interest) as well as the localized behavior of global algorithms. We prove that two well-studied matrix functions for graph analysis, PageRank and the matrix exponential, stay localized on networks that have a skewed degree sequence related to the power-law degree distribution common to many real-world networks. Our results give the first theoretical explanation of a localization phenomenon that has long been observed in real-world networks. We prove our novel method for the matrix exponential converges in sublinear work on graphs with the specified degree sequence, and we adapt our method to produce the first deterministic algorithm for computing the related heat kernel diffusion in constant-time. Finally, we generalize this framework to compute any graph diffusion in constant time.
590 $a School code: 0183.
650 4 $a Applied mathematics. $3 377601
650 4 $a Mathematics. $3 184409
650 4 $a Computer science. $3 199325
690 $a 0364
690 $a 0405
690 $a 0984
710 2 $a Purdue University. $b Mathematics. $3 766145
773 0 $t Dissertation Abstracts International $g 77-12B(E).
790 $a 0183
791 $a Ph.D.
792 $a 2016
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10149739