## 5 Experimental Evaluation
### Results and Discussion  
The numerical results for the first two benchmark sets--that is, for social networks --are presented in Table 5 which has the following structure. The first column indicates the name of the social network. For each of the fives greedy algorithms the table contains two columns. The first one, labeled _Val_, provides the objective function values of the solutions found for the corresponding problem instances. The other one, labeled _Time(s)_, shows the corresponding running times in seconds. In this context, note that a computation time of 0.0 means that the time was below 0.01 s. The best result per table row is highlighted in bold font. Moreover, note that provenly optimal results--see Table 6 for the full CPLEX results--are underlined. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Network** & \(n\) & \(m\) & **Description** \\ \hline amazon0302 & 262,111 & 899,792 & Amazon product co-purchasing \\  & & & network from 2 March 2003 \\ amazon0312 & 400,727 & 2,349,869 & Amazon product co-purchasing \\  & & & network from 12 March 2003 \\ amazon0505 & 410,236 & 2,439,437 & Amazon product co-purchasing \\  & & & network from 5 May 2003 \\ amazon0601 & 403,394 & 2,443,408 & Amazon product co-purchasing \\  & & & network from 1 June 2003 \\ cit-HepPh & 34,546 & 420,877 & Arxiv High Energy Physics paper \\ cit-HepTh & 2777 & 352,285 & Arxiv High Energy Physics \\  & & & paper citation \\ email-EuAll & 265,214 & 364,481 & Email network from a EU \\  & & & research institution \\ p2p-Gnutella04 & 10,876 & 39,994 & Gnutella peer to peer network from 4 August 2002 \\ p2p-Gnutella24 & 26,518 & 65,369 & Gnutella peer to peer network from 24 August 2002 \\ p2p-Gnutella25 & 22,687 & 54,705 & Gnutella peer to peer network from 25 August 2002 \\ p2p-Gnutella30 & 36,682 & 88,328 & Gnutella peer to peer network from 30 August 2002 \\ p2p-Gnutella31 & 62,586 & 147,892 & Gnutella peer to peer network from 31 August 2002 \\ soc-Slashdot0811 & 7736 & 469,180 & Slashdot social network from 3 November 2008 \\ soc-Slashdot0922 & 82,168 & 504,230 & Slashdot social network from 3 February 2009 \\ soc-Epinions1 & 75,879 & 405,740 & Who-trusts-whom network of \\  & & & Epinions.com \\ wiki-Vote & 7115 & 100,762 & Wikipedia who-votes-on-whom \\ web-NotreDame & 325,729 & 1,090,108 & Web graph of Notre Dame \\ web-Stanford & 281,903 & 1,992,636 & Web graph of Stanford.edu \\ wiki-Talk & 2,394,385 & 4,659,565 & Wikipedia talk (communication) network \\ web-BerkStan & 685,230 & 6,649,470 & Web graph of Berkeley and Stanford \\ web-Google & 875,713 & 4,322,051 & Web graph from Google \\ cit-Patents & 3,774,768 & 16,518,947 & Citation network among US Patents \\ \hline \hline \end{tabular}
\end{table} 
Table 4: SNAP networks used in experiments. The experimental results allow us to make the following observations. IGA-PIDS is able to obtain the best solution for 15 out of 17 problem instances. In contrast, all competitors together only return the best solution in 7 out of 17 cases. In addition, we can observe that both [PERSON]'s greedy and IGA-PIDS are significantly faster than the other three competitors (approximately two orders of magnitude). Furthermore, IGA-PIDS is only marginally slower than [PERSON]'s greedy, which means that the improved solution quality obtained by IGA-PIDS is not achieved at the expense of a significantly increased computation time. Moreover, without taking our greedy approach into consideration, it is worth to note that [PERSON]'s greedy outperforms the other greedy algorithms both in term of solution quality and computational efficiency. Finally, while the performance of each of the