東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Incremental Centrality Algorithms fo...

Kas, Miray.

Linked to FindBook

Google Book

Amazon

博客來

Incremental Centrality Algorithms for Dynamic Network Analysis.

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Incremental Centrality Algorithms for Dynamic Network Analysis./
Author:	Kas, Miray.
Description:	312 p.
Notes:	Source: Dissertation Abstracts International, Volume: 75-02(E), Section: B.
Contained By:	Dissertation Abstracts International75-02B(E).
Subject:	Computer Science. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3575079
ISBN:	9781303526121

Incremental Centrality Algorithms for Dynamic Network Analysis.
Kas, Miray.

Incremental Centrality Algorithms for Dynamic Network Analysis. - 312 p.

Source: Dissertation Abstracts International, Volume: 75-02(E), Section: B.

Thesis (Ph.D.)--Carnegie Mellon University, 2013.

The increasing availability of online resources such as digital libraries and social networking websites has led to an upsurge of interest in the analysis of social networks. To date, a wealth of social centrality measures have been designed for determining the importance of nodes in a social network from different aspects. A significant number of social centrality metrics depend on the shortest paths in the network, usually requiring solving the all-pairs shortest path problem. However, most of these metrics were designed for static snapshots of 20-30 node networks. Computing centrality metrics in dynamically changing, large networks is almost unfeasibly costly, especially if it involves repeatedly calculating centralities from scratch for each incremental change.

ISBN: 9781303526121Subjects--Topical Terms:

626642
Computer Science.

Incremental Centrality Algorithms for Dynamic Network Analysis.
LDR:02894nam a2200301 4500 001 1959520
005 20140520124322.5
008 150210s2013 ||||||||||||||||| ||eng d
020 $a 9781303526121
035 $a (MiAaPQ)AAI3575079
035 $a AAI3575079
040 $a MiAaPQ $c MiAaPQ
100 1 $a Kas, Miray. $3 2094967
245 1 0 $a Incremental Centrality Algorithms for Dynamic Network Analysis.
300 $a 312 p.
500 $a Source: Dissertation Abstracts International, Volume: 75-02(E), Section: B.
500 $a Adviser: L. Richard Carley.
502 $a Thesis (Ph.D.)--Carnegie Mellon University, 2013.
520 $a The increasing availability of online resources such as digital libraries and social networking websites has led to an upsurge of interest in the analysis of social networks. To date, a wealth of social centrality measures have been designed for determining the importance of nodes in a social network from different aspects. A significant number of social centrality metrics depend on the shortest paths in the network, usually requiring solving the all-pairs shortest path problem. However, most of these metrics were designed for static snapshots of 20-30 node networks. Computing centrality metrics in dynamically changing, large networks is almost unfeasibly costly, especially if it involves repeatedly calculating centralities from scratch for each incremental change.
520 $a This thesis proposes incremental algorithms for the two of the most popular shortest-path based social centrality metrics (e.g. closeness centrality and betweenness centrality) to avoid computations from scratch by performing early-pruning and achieving substantial performance improvements in dynamically changing networks. It explores the computational time savings and the memory requirements as the realistic social networks being analyzed scale to very large sizes. The key idea is to start with the old output of the algorithm and to modify/update only the affected values such that the changes in the network (e.g. edge/node insertions/deletions/modifications) are reflected in the centrality values as well. The approximate versions of incremental closeness and betweenness centralities through k-hop bounded computations are also designed where the shortest paths included in the computations should be less than or equal to k; forcing the centrality computations to remain within a k-hop subgraph of a node instead of the entire graph. The performance results obtained via experiments on a wide variety of synthetic and real-life dynamic networks suggest substantial improvements over the state of the art.
590 $a School code: 0041.
650 4 $a Computer Science. $3 626642
650 4 $a Engineering, Computer. $3 1669061
650 4 $a Web Studies. $3 1026830
690 $a 0984
690 $a 0464
690 $a 0646
710 2 $a Carnegie Mellon University. $b Electrical and Computer Engineering. $3 2094139
773 0 $t Dissertation Abstracts International $g 75-02B(E).
790 $a 0041
791 $a Ph.D.
792 $a 2013
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3575079