An Approximate Flow Betweenness Centrality Measure for Complex Network

被引：9

作者：

Liu, Jia-Rui ^{[1
]}

Guo, Shi-Ze ^{[2
]}

Lu, Zhe-Ming ^{[1
]}

Yu, Fa-Xin ^{[1
]}

Li, Hui ^{[1
]}

机构：

[1] Zhejiang Univ, Sch Aeronaut & Astronaut, Hangzhou 310027, Zhejiang, Peoples R China

[2] North Elect Syst Engn Corp, Beijing 100083, Peoples R China

来源：

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS | 2013年 / E96D卷 / 03期

基金：

中国国家自然科学基金;

关键词：

complex network; centrality; flow betweenness centrality; approximate flow betweenness centrality;

D O I：

10.1587/transinf.E96.D.727

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In complex network analysis, there are various measures to characterize the centrality of each node within a graph, which determines the relative importance of each node. The more centrality a node has in a network, the more significance it has in the spread of infection. As one of the important extensions to shortest-path based betweenness centrality, the flow betweenness centrality is defined as the degree to which each node contributes to the sum of maximum flows between all pairs of nodes. One of the drawbacks of the flow betweenness centrality is that its time complexity is somewhat high. This Letter proposes an approximate method to calculate the flow betweenness centrality and provides experimental results as evidence.

引用

页码：727 / 730

页数：4

共 16 条

[1]

[Anonymous], P 16 ANN C ADV SCH C

[2]

Bader DA, 2007, LECT NOTES COMPUT SC, V4863, P124

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

Barabási, AL ;

Albert, R .

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

[4] Eigenvector-like measures of centrality for asymmetric relations [J].

Bonacich, P ;

Lloyd, P .

SOCIAL NETWORKS, 2001, 23 (03) :191-201

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

Brandes, U .

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

[6] The stability of centrality measures when networks are sampled [J].

Costenbader, E ;

Valente, TW .

SOCIAL NETWORKS, 2003, 25 (04) :283-307

[7] Subgraph centrality in complex networks -: art. no. 056103 [J].

Estrada, E ;

Rodríguez-Velázquez, JA .

PHYSICAL REVIEW E, 2005, 71 (05)

[8] CENTRALITY IN SOCIAL NETWORKS CONCEPTUAL CLARIFICATION [J].

FREEMAN, LC .

SOCIAL NETWORKS, 1979, 1 (03) :215-239

[9] 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

[10] CENTRALITY IN SOCIAL NETWORKS .2. EXPERIMENTAL RESULTS [J].

FREEMAN, LC ;

ROEDER, D ;

MULHOLLAND, RR .

SOCIAL NETWORKS, 1980, 2 (02) :119-141

← 1 2 →