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 条

[1]

Anthonisse J.M, 1971, 971 BN

[2] Emergence of scaling in random networks [J].

Barabási, AL ;

Albert, R .

SCIENCE, 1999, 286 (5439) :509-512

[3] Efficient generation of large random networks [J].

Batagelj, V ;

Brandes, U .

PHYSICAL REVIEW E, 2005, 71 (03)

[4]

Baumann N, 2005, LECT NOTES COMPUT SC, V3418, P341

[5] AN IMPROVED INDEX OF CENTRALITY [J].

BEAUCHAMP, MA .

BEHAVIORAL SCIENCE, 1965, 10 (02) :161-163

[6] The degree sequence of a scale-free random graph process [J].

Bollobás, B ;

Riordan, O ;

Spencer, J ;

Tusnády, G .

RANDOM STRUCTURES & ALGORITHMS, 2001, 18 (03) :279-290

[7] FACTORING AND WEIGHTING APPROACHES TO STATUS SCORES AND CLIQUE IDENTIFICATION [J].

BONACICH, P .

JOURNAL OF MATHEMATICAL SOCIOLOGY, 1972, 2 (01) :113-120

[8] STRUCTURAL-ANALYSIS OF HYPERTEXTS - IDENTIFYING HIERARCHIES AND USEFUL METRICS [J].

BOTAFOGO, RA ;

RIVLIN, E ;

SHNEIDERMAN, B .

ACM TRANSACTIONS ON INFORMATION SYSTEMS, 1992, 10 (02) :142-180

[9]

Brandes U, 2005, LECT NOTES COMPUT SC, V3404, P533

[10] A faster algorithm for betweenness centrality [J].

Brandes, U .

JOURNAL OF MATHEMATICAL SOCIOLOGY, 2001, 25 (02) :163-177

← 1 2 3 4 →