Fast Computing Betweenness Centrality with Virtual Nodes on Large Sparse Networks
Speaker: | Patrick Roncal |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics and Computer Building (MC) 6486 |
Abstract:
Betweenness
centrality
is
an
essential
index
for
analysis
of
complex
networks.
However,
the
calculation
of
betweenness
centrality
is
quite
time-consuming
and
the
fastest
known
algorithm
uses
time
and
space
for
weighted
networks,
where
and
are
the
number
of
nodes
and
edges
in
the
network,
respectively.
By
inserting
virtual
nodes
into
the
weighted
edges
and
transforming
the
shortest
path
problem
into
a
breadth-first
search
(BFS)
problem,
we
propose
an
algorithm
that
can
compute
the
betweenness
centrality
in
time
for
integer-weighted
networks,
where
is
the
average
weight
of
edges
and
is
the
average
degree
in
the
network.
Considerable
time
can
be
saved
with
the
proposed
algorithm
when,
indicating
that
it
is
suitable
for
lightly
weighted
large
sparse
networks.
A
similar
concept
of
virtual
node
transformation
can
be
used
to
calculate
other
shortest
path
based
indices
such
as
closeness
centrality,
graph
centrality,
stress
centrality,
and
so
on.
Numerical
simulations
on
various
randomly
generated
networks
reveal
that
it
is
feasible
to
use
the
proposed
algorithm
in
large
network
analysis.
The
presentation
will
be
based
on
the
following
paper:
Fast
Computing
Betweenness
Centrality
with
Virtual
Nodes
on
Large
Sparse
Networks.