Information Technology Reference
In-Depth Information
Fig. 10.3. The 13 possible schemes of connectivity that can be achieved in a graph of 3 nodes.
10.3.6.
Network structure
Two measures are frequently used to characterize the local and global structure
of unweighted graphs: the average shortest path
L
and the clustering index
C
. The
former measures the efficiency of the passage of information among the nodes,
the latter indicates the tendency of the network to form highly connected clusters
of vertices. Recently, a more general setup has been examined in order to
investigate weighted networks. In particular, Latora and Marchiori considered
weighted networks and defined the efficiency coefficient
e
of the path between
two vertices as the inverse of the shortest distance between the vertices (note that
in weighted graphs the shortest path is not necessarily the path with the smallest
number of edges). In the case where a path does not exist, the distance is infinite
and
e
= 0. The average of all the pair-wise efficiencies
e
ij
is the global-efficiency
E
g
of the graph. Thus, global-efficiency can be defined as:
1
1
∑
∈
E
(
A
)
=
g
(10.17)
N
(
N
−
1
d
i
,
j
i
≠
j
V
where
N
is the number of vertices composing the graph. Since the efficiency
e
also applies to disconnected graphs, the local properties of the graph can be
characterized by evaluating for every vertex
i
the efficiency coefficients
of
A
i
,
which is the sub-graph composed by the neighbors of the node
i
. The local-
efficiency
E
l
is the average of all the sub-graphs global-efficiencies:
1
∈
E
(
A
)
=
E
(
A
)
(10.18)
l
glob
i
N
i
V
