Information Technology Reference
In-Depth Information
Therefore, how to evaluate the merits of the various community finding al-
gorithms and give a reasonable evaluation criterion, is an urgent problem of
community finding research. In addition, it is very important to obtain the prior
knowledge of the number of community finding. These two aspects are concerned
in this chapter. A new evaluate criterion of community finding is given accord-
ing to the topology analysis of the scale-free network, and a method predicted
the magnitude order of the number of communities for a scale-free network is
obtained.
13.2
Basic Conceptions
In this section, we give some important conceptions: complex network, degree
distribution, power law distribution, scale-free network, community structure,
community finding algorithm, centrality index.
The
complex network
that we consider in this chapter is graph consisting
of nodes connected by links, which has non-trivial topological structure [4]).
Clearly, the meanings of nodes and edges in different real-world networks are
different. The nodes of the WWW are the web pages and the edges are the
hyperlinks that point from one web page to another. The topology of the Internet
is considered at two different levels: router level and autonomous system level.
Andintheformerlevel,thenodesarethe routers and edges are the physical
connections between them, while the nodes are domains in the latter level. In the
movie actor network, the nodes are the actors, and two nodes have a common
edge if the corresponding actors have acted in a movie together.
The
degree
of a node in a complex network,
k
, is the total number of links
connected to the node. And the
degree distribution
of the network,
P
(
k
), is the
probability that a randomly selected node has
k
degree [18].
The popular distributions of real-world complex networks are various, which
can be broadly divided into two categories: one is relatively even distribution;
another is seriously uneven distribution. Poisson and Gauss distribution can
approximately describe the former distribution, whose probability distributions
have a ball-shaped curve [6]. And for seriously uneven distribution, it can be
described by power-law distribution commonly:
P
(
k
)=
Ck
−γ
,
γ>
0
,
k
=1
,
2
,...
(13.1)
The power-law distribution has an “L” shaped curve and on log-log scale the
distribution appears as a straight line, which is shown as Fig. 13.2.
Traditionally, the degree distribution of the random graph network described
by Erdos and Ranyi [19] follows a binomial distribution, or a Poisson distribution
in the limit of large number of nodes
N
,thatistosay,
P
(
k
)=
e
−μ
λ
μ
/k
!, and the
coecient
μ
=
p
(
N
1), where
p
is the probability that each random selected
nodes are connected. However, the topology structures of many real-world net-
works don't exhibit the characteristics of random graph. Real world networks are
nonrandom since some important evolving mechanisms are suggested to control
their topology structures in the whole evolving processes. Recently the data of
−
