Information Technology Reference
In-Depth Information
Fig. 13.1.
An example of community structures [16]. There are three communities,
which are partitioned by the dashed circles, and the links between communities are
very sparser denoted by four blue lines.
complex networks, such as the Internet, the WWW, and biological networks. Some
new methods, including Girvan and Newman algorithm [11], the algorithm based
on the edge betweenness score [12], local community finding algorithm based on
the greedy maximization of local modularity [13], the algorithm based on the max-
imum modularity [14], the algorithm based on information centrality [15], etc., are
able to work well with these complex networks. For the two categories of these al-
gorithms, the evaluation criterion is typically the algorithm's time complexity.
On the other hand, there is a very dicult issue that how to determine the
optimal number of well-defined communities obtained by most algorithms of
community finding. If the number of well-defined communities is not clearly
known, some algorithms will not be able to run correctly. For the Kernighan-
Lin algorithm, it is necessary to know the number of communities in advance
[10]. If the number of nodes is very large, or the number of communities is
unknown, the algorithm will be failure. The new algorithms have the same issue
as the traditional community finding algorithms. For GN algorithm, it can not
determine the appropriate iterative step when the number is not determined.
Although in the Newman algorithm [17] the appropriate number of communities
can be determine according to the local maximum of the modality indices, the
number of the communities can not be obtained.
For each node, since the probabilities of connecting new edges to other nodes
are different according to preferential attachment of the scale-free network, not
all nodes have the same influences to distribute and transform the information
of the network. The centrality of a network aims at the foundational question
how to measure the importance of nodes. The importance of nodes in a complex
network has attracted a lot of attention of researches since it concerns crucial
subjects such as networks resilience to attacks [12]. In this chapter, it is believed
that there is a close relation between the number of the important nodes and the
number of well-defined communities. So some centrality indices of each node and
the whole network are considered to design the evaluation criteria of community
finding algorithms.
