Information Technology Reference
In-Depth Information
nent of scale-free complex networks and the number of communities, and the
changes of network centrality indices of the original and reconstructed network,
to design the evaluation criterion in the chapter. Some issues have emerged about
the evaluation criterion immediately. Firstly, although the algorithm based on
the Laplace matrix spectral decomposition satisfies the evaluation criterion and
it is proved an effective algorithm, the comparison of different community find-
ing algorithms according to the evaluation criterion is still interesting. Secondly,
three network indices are selected as one of three conditions of the criterion to
measure community finding algorithm. So it is worth discussing whether many
other important network centrality indices can be competent for the task or not.
Lastly, as mentioned above, there are some important topology characteristics
of complex networks. Average shortest path length describes the distance from
arbitrary node to the other node in average, and can be as the measurement of
speed of information dissemination in the sense. If the value of average shortest
path length scales logarithmically or slower with the network size for a given
mean degree, the network shows the small-world effect [26]. And clustering co-
ecient reflects the cliquishness of the mean closest neighborhood of a network
node, iconically in the friendship network, the probability that your friend's
friend is also your friend directly. However, we only introduce the degree distri-
bution of complex network to give some conditions in the criterion. Therefore, in
the evaluation criterion of community finding algorithm, the two characteristics
maybe serve as its relevant conditions through further analysis.
13.7
Conclusions
In this chapter, we have mainly presented some basis conceptions, such as com-
plex network, degree distribution, community structure, community finding algo-
rithm and network centrality index at first. Then, a new algorithm of community
finding based on Laplace matrix spectral decomposition is proposed. And the
key technology of the algorithm, the method of threshold selection of Euclidean
distances between nodes has been discussion. The evaluation criterion of algo-
rithms including three conditions is given according to the power-law exponent
of scale-free network and three network centrality indices. Finally, the algorithm
is implemented by the poster networks of a BBS forum in a period of time. And
three conditions are satisfied for the community finding algorithm, which proves
that it is an effective algorithm.
There are three major innovations in the chapter. One is combining scale-
free topology characteristic of complex network and network centrality indices
to analyze the algorithm of community finding. And the evaluation criterion of
community finding algorithm is also basis on the topology analysis of complex
network. It is the most important idea which is different from the previous
method distinctly. The Euclidean distance threshold in the algorithm of Laplace
matrix spectral decomposition is given by means of the analysis of ratio of nodes
and edges of the original network to that of the reconstructed network, which
is the second innovation. The third one is that, the relationship between the
