Community Finding of Scale-Free Network: Algorithm and Evaluation Criterion - Mining Complex Data - page 214

Fig. 13.2. Poisson distribution, power-law distribution and its log-log plot

complex networks obtained by the researchers of many fields show that: some
nodes have a tremendous number of links to other nodes, whereas most nodes
have just a handful links. And these important nodes are called hub nodes in the
network, which have thousands or even millions of links. In the sense, Barabasi
et al. suggest the network appears to have no scale. Generally speaking, a com-
plex network is a scale-free network if its degree distribution follows power-law
distribution. From Equation (13.1), we can find that:

P ( C k )= C ( C k ) −γ = CC −γ k −γ = C 1 k −γ . (13.2)

That is, the exponent of power-law distribution γ is independent on the variable
k . In other words, if the multiplicative factor C is taken as a scale of variable k ,
the functional form P ( k )= Ck −γ remains unchanged when the scale k changes
to C k . Therefore, the exponent γ of power-law distribution of the network is
scale-free in this sense.
Community structure of a network means that the nodes are often found to
cluster into highly knit groups with a high density of within-group edges and a
low density of between-group edges. Since the component of a node is the set of
nodes that can be reached from it by paths running along edges of the graph,
which is the connected subgraph in undirected graph, the community structure
is not equivalent to the connected subgraphs or components.
Community finding algorithm is an algorithm to detect and partition the
community structure of a network. All community finding algorithms fall into
two rough classes depending on whether they focus on the addition or removal of
edges to or from the network. The main idea of the first category of algorithms is
agglomerative. That is, the network is divided into N communities and there are
no edges between each pair of nodes at first, where the total number of nodes is
N , the new edges are added to link two nodes according to a certain connected-
edge rule of the algorithm. For example, the rule can be that the higher the
similarity between pairs of nodes is, the more priority the link between the nodes
is connected. The key technology of another category of algorithms is divisive.
Divisive community finding algorithms try to find the lowest similarity of node