Information Technology Reference
In-Depth Information
All these current algorithms are successful approaches to listing all maximal
cliques in different ways. However, just as mentioned before, the growing interests
in complex systems have prompted many scientists to reconsider
Erdos
-
Renyi
modeling paradigm and ask a simple question: are the real networks behind such
diverse complex systems as the Internet fundamentally random? Fortunately, in
the past few years, several breakthroughs in the study of real world networks
have brought about many new concepts and ideas. More and more grown evi-
dence could show that real networks in our world can be modeled as complex
networks. These networks are often large sparse graphs with the properties of
short average path-length, power-law degree distribution and high clustering co-
ecient. Compared with the classic random network, which has short average
path-length, Poisson degree distribution and law clustering coecient, it is ap-
parent that complex network is essentially a different kind of network model.
Since most existing algorithms are based on the classic random network, it is
necessary for us to propose a new method which is optimized on the complex
network model and can be ecient to enumerate all the maximal cliques in
practical scenarios.
12.4
Algorithm
Peamc
For most complex networks, they are often sparse in global yet dense in local.
Because triangle structure is the basic building block of the clique, our basic idea
is to search for every possible triangle to form larger clique recursively until the
finally obtained clique becomes the maximal one. During this process, we use
several pruning strategies to improve the eciency. Finally, by extending this
basic idea, we provide a parallel model of the algorithm to make
Peamc
ecient
and scalable enough when dealing with large-scale networks.
12.4.1
Notations and Definitions
In this paper, we consider simple graphs only, i.e., the graphs without self-loops
or multi-edges. For graph
G
,
V
(
G
)and
E
(
G
) denote the sets of vertices and
edges of
G
respectively.
Definition 1.
S
E
(
G
)
,thenS is a
clique in G and n-clique denotes a clique of size n. If any other S
is a clique and
S
⊆
⊆
V
(
G
)
,
∀
u, v
∈
S, u
=
v such that
(
u, v
)
∈
S iff S
=
S,thenS is a maximal clique of G. In addition, the maximum
clique is a maximal clique with the largest size in all.
Definition 2.
Given vertex v
i
∈
V
(
G
)
,letN
(
v
i
)=
{
v
j
∈
V
(
G
)
|
(
v
i
,v
j
)
∈
E
(
G
)
}
, N
(
v
i
)
is called the
neighbor
set of v
i
and the
degree
of v
i
is thus
|
N
(
v
i
)
|
.LetM
(
v
i
)=
{
v
j
|
i<j,v
j
∈
N
(
v
i
)
}
, T
(
v
i
)=
{
v
k
|
v
k
,v
j
∈
M
(
v
i
)
,i <
j, j
< k,
(
v
i
,v
j
)
∈
E
(
G
)
,
(
v
j
,v
k
)
∈
E
(
G
)
}
, T
(
v
i
)
is called the
triangle
neighbor
set of v
i
.
