Information Technology Reference
In-Depth Information
Therefore, the criterion evaluating the correctness and eciency of a certain
community finding algorithm is that three fundamental conditions as follows
must be satisfied:
(i) The number of the well-defined communities detected by the algorithm
has the same order of magnitude to the hub nodes of the network according to
the exponent of power-law distribution.
(ii) There is not an obvious deviation between the exponent of the original
network and the corresponding exponent of the reconstructed network.
(iii) There is not conspicuous change between three network centrality indices,
degree index, betweenness index and closeness index, of the original network and
the reconstructed network.
13.5
Implementation
In this section, we firstly construct a new reply network of a BBS data and
prove that its topology has scale-free characteristic. Then, the community finding
algorithm based on Laplace matrix spectral decomposition is implemented for
this network. Finally, though the calculations and comparisons of the power-
law exponent of degree distribution and three network centrality indices of the
network, the evaluation criterion of community finding algorithm is validated.
The data used in the chapter are downloaded from China Forum, Current
Affairs Board, which listed in Table 13.2.
From the table we can find that, the number of nodes and edges of the largest
connected component account for 99.9% and 98.8% of the effective network.
Hence, the main information of the whole network is contained in the largest
connected component, and it is enough to only analyze the corresponding charac-
teristics, such as degree distribution, community structure and centrality indices,
of the largest connected component.
By means of the community finding algorithm mentioned above, the numbers
of well-defined communities of six months are shown as Figure 13.3.
In the community structure of a BBS network, there is a largest community
which contains a lot of nodes. And the number of nodes in other communi-
ties is significantly less than that of the largest community, which is shown as
Figure 13.3. It shows that there exists only one hot-topic talk which is concerned
by many users in BBS forum each month. The hot-topic talk enables them to
participate in the discussion and post some different perspective articles. Since
other communities contain few number of nodes, the contents which be concerned
by these communities are not hot-topic talk.
According to the data of the forum in April, with the different selection thresh-
olds of Euclidean distance, the numbers of nodes and edges of the largest con-
nected component of the reconstructed network are listed in Table 13.3.
It is shown from Table 13.3 that, when the Euclidean distance thresholds are
increasing, the numbers of nodes and edges of the reconstructed network are
increasing accordingly, and the same tendency in the largest connected compo-
nent. Since the threshold increases, the exiguous distances between nodes are
