Information Technology Reference
In-Depth Information
topology. Network topology analysis can be considered to be a data mining
method in a widespread sense, which is one of the methods of mining complex
data sometimes.
Complex networks have drawn increasing interests in the community of mathe-
matics, computer science and physics. Many networks in the real world, including
the WWW and the Internet, metabolic and protein networks, social networks,
etc., have been revealed that these topology structures exhibit a scale-free prop-
erty [3, 4, 5]. That is to say, the probability that a node of these networks has
k
links obeys a power-law distribution
P
(
k
)
∼ k
γ
, with the exponent
γ
that ranges
between 2 and 3. The scale-free property is proposed formally by Barabasi and
Albert [3], so a network model having a power-law distribution is also titled by
a BA model. According to the evolving process of the BA model and the studies
of Barabasi, Albert and Jeong [6], there are two main mechanisms to produce a
scale-free power-law distribution: growth and preferential attachment. Growth
means that the numbers of nodes and links are increasing with the evolving time
t
, which accords with the evolving tendency of most networks. In the preferential
attachment mechanism, the probability of a new node will be linked to node
i
depends on the degree
k
i
, such that
Π
(
k
i
)=
k
i
/
j
k
j
. Therefore, the latter
mechanism indicates that there is a higher probability to be linked to a node
that already has a large number of links, which can effectively explain the phe-
nomenon of ”rich get richer” in many real world networks [7]. In fact, preferential
attachment is a deep depiction of “Survival of the fittest” and “Matthew effect”
[8]. In general, these two mechanisms can help to explain the existence of hub
nodes in a network, which hub nodes have very large degrees and play a key role
in influencing the topology of the whole network. An exceptional characteristic
of scale-free network is that, it displays an amazing robustness against random
attack, but when very few hub nodes are failed or removed its topology structure
is very fragility.
General speaking, most networks contain some groups in which the nodes are
more highly linked to each other within group than to the nodes outside of it. These
groups are usually called communities, clusters or modules of the networks [9].
The links of the nodes in a community are dense, while they are very sparse be-
tween communities. An example of community structure is shown in Fig. 13.1. Let
a well-defined community be an intrinsic community of the network. Since detect-
ing the community structure of a network can provide a lot of help in understand-
ing and visualizing the structure of networks, it is a very important issue that how
to achieve a suitable community structure by means of an excellent algorithm of
community finding. There are many successful algorithms to detect community
structure and they can be classified to two categories roughly, traditional algo-
rithms for some networks with small scale and some new algorithms for some com-
plex networks. Some traditional methods of community finding, including spectra
bisection, the Kernighan-Lin algorithm, hierarchical clustering, etc., can be used
to discover community structure of those networks with small scale [10]. For in-
stance, the karate club network Zachary can be divided roughly into two commu-
nities by these algorithms. However, none of these methods is ideal for the scale-free
