Centrality estimation in large networks

被引：207

作者：

Brandes, Ulrik ^{[1
]}

Pich, Christian ^{[1
]}

机构：

[1] Univ Konstanz, Dept Comp & Informat Sci, D-78457 Constance, Germany

来源：

INTERNATIONAL JOURNAL OF BIFURCATION AND CHAOS | 2007年 / 17卷 / 07期

关键词：

complex networks; betweenness centrality; approximate computation;

D O I：

10.1142/S0218127407018403

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Centrality indices are an essential concept in network analysis. For those based on shortest-path distances the computation is at least quadratic in the number of nodes, since it usually involves solving the single-source shortest-paths (SSSP) problem from every node. Therefore, exact computation is infeasible for many large networks of interest today. Centrality scores can be estimated, however, from a limited number of SSSP computations. We present results from an experimental study of the quality of such estimates under various selection strategies for the source vertices.

引用

页码：2303 / 2318

页数：16

共 32 条

[11]

Brandes U., 2005, Lecture Notes in Computer Science

[12] The anatomy of a large-scale hypertextual Web search engine [J].

Brin, S ;

Page, L .

COMPUTER NETWORKS AND ISDN SYSTEMS, 1998, 30 (1-7) :107-117

[13]

CARPENTER T, 2002, W MULT C WMC 2002

[14] Studying complex discursive systems - Centering resonance analysis of communication [J].

Corman, SR ;

Kuhn, T ;

McPhee, RD ;

Dooley, KJ .

HUMAN COMMUNICATION RESEARCH, 2002, 28 (02) :157-206

[15]

Eppstein D., 2004, J GRAPH ALGORITHMS A, V8, P39, DOI [DOI 10.7155/jgaa.00081, 10.7155/jgaa.00081]

[16] CENTRALITY IN VALUED GRAPHS - A MEASURE OF BETWEENNESS BASED ON NETWORK FLOW [J].

FREEMAN, LC ;

BORGATTI, SP ;

WHITE, DR .

SOCIAL NETWORKS, 1991, 13 (02) :141-154

[17] SET OF MEASURES OF CENTRALITY BASED ON BETWEENNESS [J].

FREEMAN, LC .

SOCIOMETRY, 1977, 40 (01) :35-41

[18] RANDOM GRAPHS [J].

GILBERT, EN .

ANNALS OF MATHEMATICAL STATISTICS, 1959, 30 (04) :1141-1144

[19] ECCENTRICITY AND CENTRALITY IN NETWORKS [J].

HAGE, P ;

HARARY, F .

SOCIAL NETWORKS, 1995, 17 (01) :57-63

[20] A UNIFIED APPROACH TO APPROXIMATION ALGORITHMS FOR BOTTLENECK PROBLEMS [J].

HOCHBAUM, DS ;

SHMOYS, DB .

JOURNAL OF THE ACM, 1986, 33 (03) :533-550

← 1 2 3 4 →