Identifying Critical Nodes in Protein-Protein Interaction Networks - Clustering Challenges in Biological Network - page 159

procedure CriticalNode ( G,L )

MIS ← MaximalIndepSet ( G )

OPT ← FALSE

!

NoAdd ← 0

"

while (OPT . NOT . TRUE ) do

#

for ( i =1to |V| ) do $

if |s| ( |s|− 1)
2

MIS then ≤ L ∀ s ∈ S ⊆ G (MIS ∪{ i } ): i ∈ V \ %

MIS ← MIS ∪{i}

&

else '

NoAdd ← NoAdd +1 (

end if

)

if (NoAdd = | V |−| MIS | ) then

OPT ← TRUE

!

BREAK

"

end if #

end for

$

end while %

return V \ MIS / ∗ set of nodes to delete ∗ /

&

end procedure CriticalNode

Fig. 7.2. Combinatorial heuristic for the CARDINALITY CONSTRAINED CRITICAL NODE PROBLEM .

7.4.2. Genetic Algorithms

Genetic algorithms (GAs) represent a broad class of heuristics for global opti-
mization problems. Intuitively, they are designed to mimic the biological process
of evolution, and follow Darwin's Theory of Natural Selection [10]. GAs store
a set of solutions, or a population , and the population evolves by replacing these
solutions with better ones based on certain fitness criteria represented by the ob-
jective function value. In successive iterations, or generations , the population
evolves by reproduction , crossover ,and mutation .
Reproduction is the probabilistic selection of the next generations elements
determined by their fitness level (i.e., objective function value). Crossover is the
combination of two current solutions, called parents , which produces one or more
other solutions, referred to as their offspring . Finally, mutation is the random per-
turbation of the offspring and is implemented as an escape mechanism to avoid
getting trapped at local optima. [13]. In successive generations, only those solu-
tions having the best fitness are carried to the next generation in a process which
mimics the fundamental principle of natural selection, survival of the fittest [10].