Information Technology Reference
In-Depth Information
pairs of the origin network, then to remove the edge of this node pairs. Repeat
the process and the whole network to be partitioned to increasingly small parts
gradually. The process can be terminated in any case and the whole network is
partitioned some communities finally.
The researches of the centrality of complex networks, especially social net-
works, were beginning in the middle of the last century [20]. Three classical cen-
trality indexes: degree, betweenness and closeness, were proposed by Freeman
[21] to describe the characteristic of a node communicating or controlling the
whole network. And he had proved that three centrality indices assign the star
or wheel network the maximum values and the circle and the complete graph the
minimum values. Degree index of a node describes its potential communication
activity in the network. Betweenness index describes its potential of a node for
control of communication. And closeness index describes its potential indepen-
dence or eciency of community. The measures of centrality for a network can
be classified into two categories: node centrality and entire network centrality.
Some new centrality indexes, such as group centrality, stress centrality, modified
betweenness centrality, have been studied recently [22, 23].
Degree centrality
of a node [21] is defined as
C
D
(
i
)=
k
i
/
(
n
−
1)
,
(13.3)
where
k
i
is the degree of node
v
i
.Let
C
D
(
i
∗
) be the largest value of
C
D
(
i
)for
any node in the network and
C
D
be a general formula for determining the degree
centrality index of the network. For the sake of simplicity, we adopt that
C
X
(
i
∗
)
is the largest value of
C
X
(
i
) for any node in a network, where
X
can be
D
(degree
index),
B
(betweenness index), and
C
(closeness index). Then the expression of
C
D
can be given by
i
=1
[
C
D
(
i
∗
)
n
−
C
D
(
i
)]
C
D
=
1)
.
(13.4)
(
n
2
−
3
n
+2)
/
(
n
−
Let
g
ij
be the number of geodesics linking node
v
i
and
v
j
.And
g
ij
(
k
)is
number of geodesics links
v
i
and
v
j
that contained
v
k
. Then the probability that
node
v
k
falls on a randomly selected geodesic linking
v
i
and
v
j
is
b
ij
(
k
)=
g
ij
(
k
)
/g
ij
.
(13.5)
So the
betweenness centrality
[21] can be calculated by
2
i<j
b
ij
(
k
)
(
n
2
C
B
(
k
)=
3
n
+2)
.
(13.6)
−
As far as the betweenness of the whole network be concerned, it is the average
value of the betweenness index of each node, so it can be calculated by the
following formula:
i
=1
[
C
B
(
i
∗
)
n
−
C
B
(
i
)]
C
B
=
.
(13.7)
n
−
1
