Database Reference
In-Depth Information
the other's partition so that the edge is preserved. The partitioning algorithm removes
one vertex at a time from the graph and puts the subgraph consisting of this vertex plus
all its neighbors in one partition. By repeatedly partitioning the graph, it generates
multiple subgraphs on which the maximum clique can be computed independently.
In addition, the algorithm uses a branch and bound approach to avoid computing the
maximum clique of a partition if the size of the maximum clique is smaller than the
largest clique found so far.
Tsourakakis et al. [
36
] proposed to mine the optimal quasi-clique. The density
function defined as
f
α
(
C
)
α
|
C
2
(
e
[
C
] is the number of edges in the induced
subgraph by
C
) measures the edge surplus of a vertex set
C
over the expected number
of edges under the random-graph model. An optimal quasi-clique is a vertex set
C
that
maximizes the function
f
α
(
C
). The optimal quasi-cliques are shown to be subgraphs
with a large edge density edge density and a small diameter.
=
e
[
C
]
−
5.2
K-Core and K-Truss
=
Given a graph
G
(
V
,
E
), the
k
-core of
G
is the largest subgraph of
G
in which
every vertex has degree of at least
k
within the subgraph. The
k
-truss of
G
is the
largest subgraph of
G
in which every edge is contained in at least (
k
−
2) triangles
within the subgraph.
The problem of core decomposition in a graph
G
is to find the
k
-cores of
G
for all
k
. There is a simple and efficient algorithm for core decomposition, by recursively
removing the lowest degree vertices and their incident edges. Cheng et al. [
11
]
proposed an external-memory algorithm, called EMcore, for core decomposition
in massive graphs which cannot fit into the main memory. EMcore first partitions
the original graph into small blocks, and then loads the relevant blocks into main
memory. It takes a top-down approach that recursively computes the
k
-cores from
larger values of
k
to smaller ones, and progressively reduces search space and disk I/O
cost by removing the vertices in each computed
k
-core. The algorithm requires only
O
(
k
max
) scans of the input graph, where
k
max
is the largest core number of the graph.
k
-truss (or called
triangle k
-
core
in [
52
]) is a type of more cohesive subgraph
pattern than
k
-core, as it is defined based on triangles instead of degrees. A
k
-truss
isa(
k
1)-core, but not vice versa. The problem of truss decomposition in a graph
G
is to find the
k
-trusses of
G
for all
k
. There exists a polynomial time algorithm for
computing
k
-truss. Wang and Cheng [
39
] proposed an efficient in-memory algorithm
for truss decomposition in
O
(
m
1
.
5
) time, where
m
is the number of edges in
G
.
They also developed two I/O-efficient algorithms for truss decomposition in massive
networks that cannot fit in memory. The first one is a bottom-up approach that
employs an effective pruning strategy by removing a large portion of edges before
computing each
k
-truss. The second one takes a top-down approach to find the
k
-
trusses of larger values of
k
. Zhang and Parthasarathy [
52
] proposed algorithms to
identify triangle
k
-cores in both static and dynamic graphs.
−
