Information Technology Reference
In-Depth Information
5.2.1
Distances and Closeness
Although reachability essentially relies on the
existence
of paths between nodes,
one can attempt to provide a measure of
how easily
a node
u
V
can be reached
in
G
- with the idea that longer paths require more effort to be traversed. Thus, the
reachability of a node can be expressed in terms of graph distances.
The metrics we are about to describe use the graph theoretical distance to infer
the properties of nodes and ultimately indicate how/where information flows in the
graph. The rationale underlying all these metrics is that nodes sitting close to most
other nodes have the easiest access to information; here, ease is measured in terms
of distances.
∈
)=
v
∈
V
d
G
(
u
,
v
)
s
G
(
u
(5.1)
The metric in Eq. (
5.1
) was introduced by Harary (
1959
)asthe
status
of a
node (in a graph). Observe that this metric is integer valued and can take any
positive value (and even
S
G
(
can occur when
G
is disconnected). Beauchamp
(
1965
) (although often cited through
Sabidussi
,
1966
) later suggested computing
the inverse ratio, which is currently called the
closeness centrality
of a node:
u
)=
∞
1
∑
v
∈
V
d
G
(
C
G
(
u
)=
)
.
(5.2)
u
,
v
Note that
C
G
(
)
∈
[
,
]
and that
C
G
(
)
>
u
0
1
u
0when
G
is connected. Additionally,
1
d
G
(
u
)
C
G
(
)
≤
; the equality
C
G
(
)=
u
u
1 can only occur in the very special case of a
two node graph.
An alternate definition is the
eccentricity
of a node
e
G
(
(see
Hage & Harary
,
1995
), with the idea that central nodes are those having minimal eccentricity because
they sit relatively close to all other nodes in the graph:
u
)
e
G
(
u
)=
max
v
∈
V
d
G
(
u
,
v
)
.
(5.3)
Note, however, that the eccentricity of nodes does not lie in a bounded interval,
which makes it difficult to compare nodes of different graphs.
Node centrality
(see
Hage & Harary
,
1995
) overcomes this problem by taking the inverse ratio 1
/
e
G
(
u
)
.
The
diameter
of a graph is defined as the maximum eccentricity:
diam
(
G
)=
max
u
V
d
G
(
u
,
v
)=
max
u
e
G
(
u
)
.
(5.4)
,
v
∈
∈
V
The
average distance
in a graph is also often used as an indicator of the graph
structure:
1
∑
u
,
v
∈
V
d
G
(
u
,
v
)
.
(5.5)
|
V
|
(
|
V
|−
1
)
2
Search WWH ::
Custom Search