## 5 Experimental Evaluation
### Results and Discussion
In order to study the effect of the proposed function to eliminate redundant vertices --see function \(\mathsf{Reduce}(\cdot)\) described in Section 4.2--Table 6 reports the performance of our greedy algorithm before (IGA-PIDS) and after (IGA-PIDS-) removing redundant vertices. From these results it can be concluded that most solutions suffer from the existence of redundant vertices. Thus, removing them can provide more accurate results which comes, however, at the cost of additional computation time. Having said that, the increase of the average computation time is very moderate: from 0.014 s to only 0.017 s. In Table 6, we additionally present the results obtained from the ILP solver CPLEX. The obtained results show that the newest CPLEX version (12.10) is very efficient for the MPIDS problem. In fact, only in two cases (social networks socft-nips-ego and Dolphins) our greedy algorithm is able to match the results of CPLEX. Moreover, CPLEX provides provenly optimal solutions in 11 out of 17 cases (within 2 h of computation time). Provenly optimal results are marked by an asterisk. Nevertheless, the results provided by IGA-PIDS are, on average, only 2.53% worse than those of CPLEX (see last table column labeled Gap (%)). Finally, the results for the large-scale SNAP networks are presented in Table 7, in the same format as outlined above. The results of CPLEX are also included. Moreover, note that no result is provided in those cases in which the computation time of the respective algorithm exceeded 7200 s (two hours). The results on these larger networks confirm our findings from the first two benchmark sets. However, the differences between the algorithms are now even more pronounced. Observe, for example, that--on average--IGA-PIDS produces solutions with more than 2000 vertices less per instance when compared to Pan's greedy. Moreover, the limits of CPLEX are clearly reached in the application to problem instances of the size and the complexity found in the Amazon* instances and cit-Patents. The results provided by CPLEX in these cases are far worse than those of IGA-PIDS, as indicated by the gaps. In fact, the results of IGA-PIDS improve by approx. 55% over the results of CPLEX in these cases. Therefore, IGA-PIDS is overall the best algorithm, even outperforming CPLEX with an average gap of approx. 42% between the IGA-PIDS solutions and the CPLEX solutions. Finally, we decided to provide a statistical assessment of the obtained results by means of critical difference (CD) plots [31]. In order to produce the average rank of each greedy algorithm considering the complete set of 39 problem instances, the scmamp R package [31] first applies the Friedman test to compare the five approaches simultaneously. In this way, the hypothesis that the five techniques perform equally was rejected. Then, the package performs pairwise comparisons using the Nemenyi post-hoc test [32]. As mentioned above, the results are shown graphically by means of CD plots. Note that, in such a plot, each considered algorithm is placed on the horizontal axis according to its average ranking. The performances of those algorithms that are below the critical difference threshold (computed with a significance level of 0.05) are considered as statistically equivalent. This is indicated by bold horizontal bars joining the markers of the respective algorithm variants. Figure 2 shows two CD plots. The first one (Figure 2a) concerns the obtained solution quality. IGA-PIDS is clearly the best-performing algorithm, with statistical significance. Concerning computation times (Figure 2b) it can be observed that [PERSON]'s greedy is slightly faster than IGA-PIDS. However, no statistical difference can be detected between the running times of [PERSON]'s algorithm and those of IGA-PIDS.