語系:
繁體中文
English
說明(常見問題)
圖資館首頁
登入
回首頁
切換:
標籤
|
MARC模式
|
ISBD
Graph diffusions and matrix function...
~
Kloster, Kyle.
Graph diffusions and matrix functions: Fast algorithms and localization results.
紀錄類型:
書目-電子資源 : Monograph/item
正題名/作者:
Graph diffusions and matrix functions: Fast algorithms and localization results.
作者:
Kloster, Kyle.
出版者:
Ann Arbor : ProQuest Dissertations & Theses, 2016
面頁冊數:
114 p.
附註:
Source: Dissertation Abstracts International, Volume: 77-12(E), Section: B.
附註:
Adviser: David F. Gleich.
Contained By:
Dissertation Abstracts International77-12B(E).
標題:
Applied mathematics.
電子資源:
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
筆 0 讀者評論
全部
電子館藏
館藏
1 筆 • 頁數 1 •
1
條碼號
館藏地
館藏流通類別
資料類型
索書號
使用類型
借閱狀態
預約狀態
備註欄
附件
000000135059
電子館藏
1圖書
學位論文
TH 2016
一般使用(Normal)
在架
0
1 筆 • 頁數 1 •
1
多媒體
多媒體檔案
http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10149739
評論
新增評論
分享你的心得
Export
取書館別
處理中
...
變更密碼
登入