Biology Reference
In-Depth Information
outlier node '
h
' and classifies the hub node '
a
' into the more reasonable cluster
{
a,e,f,g
}
, which was our aim.
11.4. A Genetic Graph Partitioning Algorithm
Recall that finding the optimum similarity-based modularity in a graph is NP-
hard, and greedy-search based approaches all suffer from the local optimum draw-
back [2, 9, 15, 17, 19]. To evaluate the capability of the proposed modularity
function, we would like to use a global-search based approach to avoid the local
optimum trap, namely a Genetic Algorithm (GA):
Encoding
- For a graph with
n
vertices, a partition can be represented as an
array of integers, for which each index corresponds to a vertex and the value to its
cluster ID of this vertex. For example, the string “232351545” indicates that
there are 5 clusters in the graph, the 1
st
and the 3
rd
vertices belong to cluster 2, the
2
nd
and the 4
th
vertices belong to cluster 3, and so on. Since each array element
can have a value from 1 to
n
, the total search space is
n
n
, which is potentially
very large.
Initial Population
- the initial population can be generated randomly or using
some task related strategies. Here we use a random initialization.
Fitness Measure
- the function to be optimized. For the graph partitioning prob-
lem we use formulae (11.5) and (11.6).
Selection
- some individuals are selected according to their fitness or ranks and
they mate to produce offspring. We use a probabilistic selection
Fitness
(
h
i
)
k
P
r
(
h
i
)=
,
(11.8)
j
=1
Fitness
(
h
j
)
where
k
is the number of clusters.
Crossover
- this operator determines how to produce offspring from parents.
Either single point or multiple point crossovers can be used. An important param-
eter is the cross rate, which determines how many genetic elements are exchanged.
We use single point crossover. The exchanged point is chosen at random and the
length of the array block that is exchanged is set by the Crossover Rate parameter.
There are two cases in single point crossover: with or without roll back.
Search WWH ::
Custom Search