Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(3)
Betweenness Centrality
Indexation
Social Network
Related Publications
(27)
Who is the best connected scientist? A study of scientiflc coauthorship networks
A set of measures of centrality based on betweenness
Community structure in social and biological networks
The anatomy of a largescale hypertextual Web search engine
Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality
Subscribe
Academic
Publications
A faster algorithm for betweenness centrality
A faster algorithm for betweenness centrality,10.1080/0022250X.2001.9990249,Journal of Mathematical Sociology,Ulrik Brandes
Edit
A faster algorithm for betweenness centrality
(
Citations: 385
)
BibTex

RIS

RefWorks
Download
Ulrik Brandes
Motivated by the fast‐growing need to compute centrality indices on large, yet very sparse, networks, new algorithms for betweenness are introduced in this paper. They require O(n + m) space and run in O(nm) and O(nm + n log n) time on unweighted and weighted networks, respectively, where m is the number of links. Experimental evidence is provided that this substantially increases the range of networks for which centrality analysis is feasible.The
betweenness centrality
index is essential in the analysis of social networks, but costly to compute. Currently, the fastest known algorithms require ?(n ) time and ?(n ) space, where n is the number of actors in the network.
Journal:
Journal of Mathematical Sociology  J MATH SOCIOL
, vol. 25, no. 2, pp. 163177, 2001
DOI:
10.1080/0022250X.2001.9990249
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
dx.doi.org
)
(
kops.ub.unikonstanz.de
)
(
www.inf.unikonstanz.de
)
Citation Context
(247)
...Since a graph can be represented as an adjacency matrix, we can naturally implement many graph algorithms, including BreadthFirst Search, PageRank and Approximate Betweeness Centrality [
10
, 20] and Markov Clustering (MCL) [34] which we discuss below...
Zhengping Qian
,
et al.
MadLINQ: largescale distributed matrix computation for the cloud
...In the case using weighted links, Brandes (
2001
) proposes to invert the weights while computing the betweenness centrality...
Kamil J. Mizgier
,
et al.
Bottleneck identification in supply chain networks
...Approximating the derivative using finite differences implies increasing the cost by a factor proportional to OðkV kÞ. Brandes presented a fast approximation of betweenness centrality [
6
] that runs in OðkV kkEkÞfor unweighted graphs...
...As a way to compare the complexity of eigenvector sensitivities, we also show the time complexity of edge betweenness using Brandes’ fast algorithm [
6
]...
Carlos D. Correa
,
et al.
Visual Reasoning about Social Networks Using Centrality Sensitivity
...is undefined. The measure can be applied to either weighted or unweighted graphs by substituting weighted or unweighted variants of betweenness centrality
...
Murray Shanahan
,
et al.
KnottyCentrality: Finding the Connective Core of a Complex Network
...Perhaps the most effective method currently used for identifying shortcut connections is based on edge betweenness centrality (EBC) (Brandes
2001
)...
Mike Gashler
,
et al.
Robust manifold learning with CycleCut
References
(28)
Introduction to Algorithms
(
Citations: 6563
)
Thomas H. Cormen
,
Charles E. Leiserson
,
Ronald L. Rivest
Published in 1990.
The centrality index of a graph
(
Citations: 208
)
Gert Sabidussi
Journal:
Psychometrika
, vol. 31, no. 4, pp. 581603, 1966
Satellite exchange in the Baltimore needle exchange program
(
Citations: 26
)
T. W. Valente
,
R. K. Foreman
,
B. Junge
Published in 1998.
Social Network Analysis: Methods and Applications
(
Citations: 4081
)
Stanley Wasserman
,
Katherine Faust
Published in 1994.
LEDA: A Platform for Combinatorial and Geometric Computing
(
Citations: 674
)
Kurt Mehlhorn
,
Stefan Näher
Published in 1999.
Sort by:
Citations
(385)
MadLINQ: largescale distributed matrix computation for the cloud
Zhengping Qian
,
Xiuwei Chen
,
Nanxi Kang
,
Mingcheng Chen
,
Yuan Yu
,
Thomas Moscibroda
,
Zheng Zhang
Published in 2012.
Bottleneck identification in supply chain networks
Kamil J. Mizgier
,
Matthias P. Jüttner
,
Stephan M. Wagner
Journal:
International Journal of Production Research  INT J PROD RES
, vol. aheadofp, no. aheadofp, pp. 114, 2012
Visual Reasoning about Social Networks Using Centrality Sensitivity
Carlos D. Correa
,
Tarik Crnovrsanin
,
KwanLiu Ma
Journal:
IEEE Transactions on Visualization and Computer Graphics  TVCG
, vol. 18, no. 1, pp. 106120, 2012
KnottyCentrality: Finding the Connective Core of a Complex Network
Murray Shanahan
,
Mark Wildie
Journal:
PLOS One
, vol. 7, no. 5, 2012
Robust manifold learning with CycleCut
Mike Gashler
,
Tony Martinez
Journal:
Connection Science  CONNECTION
, vol. aheadofp, no. aheadofp, pp. 113, 2012