Biology Reference
In-Depth Information
research has seen a lot of efforts in this problem over decades, and many algo-
rithms have been proposed, studied, and used.
The problem is defined as: Given a graph
G
=
,where
V
is a set of
vertices and
E
is a set of weighted edges between vertices, optimally divide
G
into
k
disjoint sub-graphs
G
i
=
{
V,E
}
{
V
i
,E
i
}
,inwhich
V
i
∩
V
j
=Φfor any
i
=
j
and
i
=1
V
i
. The number of sub-graphs,
k
, may or may not be prior known.
In this paper, we focus on partitioning problem of un-weighted graphs, that is,
graphs for which the weight of all edges is 1.
Two question need to be answered, one that is mathematical and one that is
algorithmic. First, what is the definition of
optimal
when partitioning a graph,
and second, how does one find the optimal partition efficiently.
Regarding the first question, there is no consensus in the literature. Different
approaches use different criteria for different applications. Examples are the min-
max cut [3, 8, 16], modularity [1, 13, 14] and betweenness [6, 12]. To the second
question, since finding the optimal partition in a graph is normally a NP-complete
problem, most current approaches use heuristics to reduce the running time and
find only near-optimal partitions.
k
V
=
Fig. 11.1.
Two types of graphs
These approaches, though work well for some applications, their performance
deteriorates as graphs become more confused. Graphs may present three kinds
of complications. Figure 11.1 illustrates two types of un-weighted graphs. The
first and main source of confusion is “random” interconnections between clusters,
illustrated by the Type I graph. These have dense clusters that are sparsely inter-
connected. As the number of interconnections increase, discerning the underlying
structure becomes more challenging. Such structures have been the focus of past
study.
The second and third source of confusion is what we call hubs and outliers,
and these have been little discussed in the literature. The Type II graph in Fig.
11.1 has clusters that are connected by “hub” vertex 'a' that is difficult to place
in one cluster or another. It also has an outlier vertex 'h' that may be best placed
Search WWH ::
Custom Search