Information Technology Reference
In-Depth Information
has discussed by Wang and Dai [24]. They found that there exist lots of hub
nodes whose degree distribution exponents are between 1 and 2. And when the
exponents are between 2 and 3, there are a certain number of hub nodes, which
is less than the number of hub nodes in the first case. Only a few hub nodes
exist in the network when the exponent exceeds 3.
It is rational that each well-defined community of the network includes only
several or one hub nodes, so the numbers of communities and hub nodes have
the same order of magnitude. Therefore, the exponent of the network is prior
information of the number of well-defined communities. According to the distri-
bution of power-law exponent of real-world networks, four likelihoods of com-
munity number are considered as follows:
(i) Since the degree distribution exponents of real-world cannot be less than
1, it is only a theoretical possibility when the exponent is 0
<λ
1. In fact,
the network closes to a random graph network and the community finding is no
sense for this kind of network.
(ii) If the range of the power-law exponent is 1
<λ
≤
2, it is proved that
there are a lot of hub nodes in the network, so its community structure is very
dispersed and the number of well-defined communities have the hundred order
of magnitude at least.
(iii) If the exponent is between 2 and 3, which is a majority of the case for
real-world networks, there are a moderate number of hub nodes, so the network
has dozens of different communities.
(iv) When the exponent is
λ>
3, a very small number of nodes have con-
nected a very large number of edges according to the characteristic of power-low
distribution. Hence, there are very few hub nodes in the network and the number
of communities doesn't exceed ten.
≤
After the community structure is obtained by any algorithm of community
finding, we can reconstruct the network with the inverse process of the algo-
rithm. The topology structures of the original network and the new network re-
constructed by community finding algorithm should remain basically unchanged.
From these likelihoods of power-law exponent we can find that, if the number
of the communities detected by a certain community finding algorithm is incon-
sistent with the order of magnitude of the hub nodes, the algorithm is useless
or non-optimal. In other words, if the degree distribution of the reconstructed
network doesn't follow the power-law distribution any longer, or it does but the
new exponent has a large deviation to the original exponent, the algorithm is
not an effective one.
The power-law degree distribution of a network is one of the topology charac-
teristics, specifically which considers the network connectivity features. However,
network centrality indices mainly measure the activity, control or independence
of communication. So network centrality indices of the original network and
the new network will have no obvious deviation if the algorithm of community
finding is effective.
