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

procedure CriticalNodeLS ( G,k )

X ∗ ←∅

f ( X ∗ ) ←∞

!

for j =1to MaxIter do

"

X ←

CriticalNode ( G,k )

#

X ← LocalSearch (X) $

if f ( X ) <f ( X ∗ ) then

%

X ∗ ← X

&

end if '

end

(

X ∗ )/ return ( V \ ∗ set of k nodes to delete ∗ / )

end procedure CriticalNodeLS

Fig. 7.3. The multi-start framework for the critical node heuristic.

procedure GeneticAlgorithm

Generate population P k

Evaluate population P k !

while terminating condition not met do

"

Select individuals from P k and copy to P k +1

#

Crossover individuals from P k and put in P k +1

$

Mutate individuals from P k and put in P k +1

%

Evaluate population P k +1

&

P k +1
( P k +1 ←∅
) end while
return best individual in P k
end procedure GeneticAlgorithm

P k ←

'

Fig. 7.4. Pseudo-code for a generic genetic algorithm.

Figure 7.4 provides pseudo-code for a standard genetic algorithm. Genetic algo-
rithms were introduced in 1977 by Holland, and were greatly invigorated by the
work of Goldberg. [13]

7.5. Computational Experiments

In this section, we present some preliminary computational results on real protein-
protein interaction networks obtained from the literature. In particular, three