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

(a) The original network.

(b) The optimal subgraph for L =5. (c) The optimal subgraph for L =4.

Fig. 7.6. The CARDINALITY CONSTRAINED CRITICAL NODE DETECTION PROBLEM is solved for
the 77 primary interactions during the development of D. melanogaster .

Table 7.2. Results of the IP model and the genetic algorithm for the 77
primary interactions of D. melanogaster development.
Instance IP Model Genetic Alg Comb. Alg

Max Conn. Obj Comp Obj Comp Obj Comp

Index ( L ) Va l Ti m e ( s ) Va l Ti m e ( s ) Va l Ti m e ( s )

2 17 0 . 87 17 0 . 17 17 0 . 04

3 14 36 . 5 14 0 . 27 17 0 . 03

4 12 276 . 29 12 0 . 19 17 0 . 01

5 10 382 . 88 10 0 . 28 17 0 . 02