Information Technology Reference
In-Depth Information
The independence or eciency of a node is determined by its closeness to all
other nodes in the network. Let
d
(
i, k
) be the number of edges in the geodesic
linking node
v
i
and
v
k
.Then
closeness centrality
index [21] is defined by
n −
1
C
C
(
k
)=
.
(13.8)
i
=1
d
(
i, k
)
n
Then the closeness index of the whole network is the average value of the corre-
sponding index of each node, i.e., the expression of this formula is
i
=1
n
[
C
C
(
i
∗
)
−
C
C
(
i
)]
C
C
=
.
(13.9)
n
−
1
Note that the variation ranges of three indexes are from 0 to 1, we can select
an appropriate percent as the single threshold of three indexes. If three indexes of
one node are larger than the threshold, the node will be joined into the set of the
central nodes. In fact, these centrality indices imply some competing methods of
how centrality might affect group processes. Since the communities of a complex
network are some separate groups in some sense, the centrality indices can be
used to design the algorithms of community finding of complex network, such as
GN algorithm.
13.3
Community Finding Algorithm Based on Laplace
Matrix Spectral Decomposition
We design the community finding algorithm based on Laplace matrix spectral
decomposition in the section. And the key threshold of Euclidean distance is
discussed to obtain an optimal value of the network. The main merit of this
algorithm is that the community structures of the network can be decomposed
thought one-time since other many algorithms take progressive iteration. In ad-
dition, the appropriate number of community structures can be determined ac-
cording to the characteristic of its Laplace matrix.
In many complex networks, there exist many isolated nodes or very small
cliques. It is no sense to analyze these nodes or cliques for community finding
or centrality. Hence only the largest connected component
L
of the network is
considered and other connected components are ignored for community finding.
For a complex network, let
M
be the Laplace matrix of the largest connected
component, which is a
n
n
square matrix. The
i
th diagonal element of the
Laplace matrix
M
is the degree of node
v
i
and the non-diagonal elements are
defined as follow:
m
ij
=
−
×
1
,
if there is an edge between node
v
i
and
v
j
;
(13.10)
0
,
otherwise.
Hence,
M
is the symmetric matrix and the total of the elements of each line or
column is always zero.
