Information Technology Reference
In-Depth Information
value of
β
implies a more precise community structure of the network. If there
is no one to satisfy Equation (13.12) for all eigenvalues, we will give a smaller
value of
β
(
β
= 2 or 1) to judge all the eigenvalues to satisfy the conditions once
again. From Table 13.1 we can find
β
=5.
Since there are only
q
∗
communities in a network, the Euclidean distance
between each pair of nodes can be described by the distance of the former
q
∗
components of their eigenvectors. That is, the Euclidean distances between node
v
i
and node
v
j
are calculated by
q
∗
=
D
ij
=
ξ
i
−
ξ
j
(
ξ
ik
−
ξ
jk
)
2
.
(13.13)
k
=1
The algorithm of community finding based on Laplace matrix spectral decom-
position are as follows:
(i) Construct the Laplace matrix
M
of the network, then calculate the eigen-
values and eigenvectors of
M
and sort in ascending order.
(ii) Determine the appropriate value of
q
∗
according to the conditions of Equa-
tion (13.12), which is the number of network well-defined communities.
(iii) Select the former
q
∗
components of each eigenvector and calculate the
Euclidean distance of pairs of nodes according to Equation (13.13).
(iv) Give the threshold
D
∗
of Euclidean distance and reconnect an edge of the
original empty network if the distance of two nodes is less than the threshold.
Redo the processes until there are not the distances more than the threshold.
(v) The original network is partitioned to
q
∗
communities according to its
subgraph of the reconstructed network.
In this algorithm, there is no suitable selection method to determine the
threshold
D
∗
of Euclidean distance currently. Numerical simulation results in
the following shows that, if the given threshold makes that the percentages of
the numbers of nodes and edges of the reconstructed network to the whole net-
work exceed 80% and 95%, respectively, it is very appropriate to community
finding.
13.4
Evaluating Criterion of Community Finding
Algorithm
Since many real-world networks have scale-free characteristic, this unique topol-
ogy can be used to detect their community structures. Meanwhile, it also provides
a new thinking to find the evaluation criteria of community finding algorithm.
In a scale-free network, its degree distribution displays power-law decay, so the
exponent of power-law distribution is an important coecient of its topology
structure. On the other hand, the number of hub nodes of a scale-free network
has a close relationship to the power-law exponent. The relationship between
the range of the exponent and the number of hub nodes in a scale-free network
