## 5 Experimental Evaluation
### Results and Discussion
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Network**} & \multicolumn{2}{c}{**Before**} & \multicolumn{2}{c}{**After**} & \multicolumn{2}{c}{**CPLEX**} \\ \cline{2-7}  & **Val** & **Time (s)** & **Val** & **Time (s)** & **Val** & **Gap (\%)** \\ \hline CA-GrQc & 2610 & 0.0 & **2607** & 0.0 & 2587 * & 0.77 \\ CA-HepTh & 4559 & 0.0 & **4544** & 0.0 & 4471 * & 1.63 \\ CA-HepPh & 4855 & 0.0 & **4817** & 0.015 & 4718 & 2.1 \\ CA-AstroPh & 7034 & 0.031 & **6953** & 0.031 & 6740 & 3.16 \\ CA-CondMat & 9804 & 0.015 & **9748** & 0.015 & 9584 & 1.71 \\ Email-Enron & 11,914 & 0.047 & **11,843** & 0.031 & 11,682 * & 1.38 \\ ncstrlwg2 & 3014 & 0.0 & **3010** & 0.015 & 2994 * & 0.53 \\ actors-data & 3214 & 0.015 & **3174** & 0.016 & 3092 & 2.65 \\ ego-facebook & 1977 & 0.062 & **1975** & 0.078 & 1973 * & 0.1 \\ soch-nips-ego & **1398** & 0.015 & **1398** & 0.016 & 1398 * & 0 \\ soch-Mich67 & 1452 & 0.0 & **1427** & 0.015 & 1329 & 7.37 \\ socfb-Brandeis99 & 1517 & 0.016 & **1502** & 0.032 & 1400 & 7.29 \\ soc-gplus & 8294 & 0.031 & **8289** & 0.031 & 8244 * & 0.55 \\ \hline Karate & **31** & 0.0 & **31** & 0.0 & 30 * & 3.33 \\ Dolphins & **15** & 0.0 & **15** & 0.0 & 15 * & 0 \\ Football & 70 & 0.0 & **68** & 0.0 & 63 * & 7.93 \\ Jazz & 82 & 0.0 & **81** & 0.0 & 79 * & 2.53 \\ \hline
**Avg** & 3637.65 & 0.014 & **3616.59** & 0.017 & 3552.88 & 2.53 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Results before and after removing redundant vertices, and the comparison to CPLEX. \begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Network**} & \multicolumn{2}{c}{**[PERSON]’s Greedy**} & \multicolumn{2}{c}{**[PERSON]’s Greedy**} & \multicolumn{2}{c}{**[PERSON]’s Greedy**} & \multicolumn{2}{c}{**[PERSON]’s Greedy**} & \multicolumn{2}{c}{**IGA-PIDS**} \\ \cline{2-11}  & **Val** & **Time (s)** & **Val** & **Time (s)** & **Val** & **Time (s)** & **Val** & **Time (s)** & **Val** & **Time (s)** \\ \hline CA-GrQc & 2626 & 0.28 & 2623 & 0.30 & 2622 & 0.36 & 2612 & 0.0 & **2607** & 0.0 \\ CA-HepTh & 4598 & 0.95 & 4602 & 0.94 & 4582 & 1.17 & 4565 & 0.0 & **4544** & 0.0 \\ CA-HepPh & 4887 & 2.91 & 4886 & 2.91 & 4876 & 3.27 & 4857 & 0.015 & **4817** & 0.015 \\ CA-AstroPh & 7081 & 7.92 & 7085 & 7.91 & 7062 & 8.59 & 7030 & 0.031 & **6953** & 0.031 \\ CA-CondMat & 9869 & 7.58 & 9853 & 7.64 & 9837 & 8.11 & 9816 & 0.0 & **9748** & 0.015 \\ Email-Enron & 12,015 & 13.52 & 12,184 & 15.75 & 11,958 & 15.23 & 11,952 & 0.047 & **11,843** & 0.031 \\ ncstrlwg2 & 3034 & 0.39 & 3025 & 0.39 & 3023 & 0.44 & 3026 & 0.0 & **3010** & 0.015 \\ actors-data & 3199 & 2.33 & 3205 & 2.41 & 3187 & 2.44 & 3215 & 0.015 & **3174** & 0.016 \\ ego-facebook & 1976 & 0.75 & **1975** & 0.84 & **1975** & 0.84 & 1978 & 0.062 & **1975** & 0.078 \\ socfb-nips-ego & **1398** & 0.02 & **1398** & 0.05 & **1398** & 0.05 & **1398** & 0.0 & **1398** & 0.016 \\ socfb-Mich67 & 1481 & 0.56 & 1478 & 0.63 & 1473 & 0.55 & 1458 & 0.016 & **1427** & 0.015 \\ socfb-Brandeis99 & 1535 & 0.97 & 1539 & 1.64 & 1529 & 0.98 & 1522 & 0.031 & **1502** & 0.032 \\ soc-gplus & 8341 & 1.97 & **8247** & 2.22 & 8267 & 2.56 & 8351 & 0.031 & 8289 & 0.031 \\ \hline Karate & 31 & 0.0 & 31 & 0.0 & **30** & 0.0 & 32 & 0.0 & 31 & 0.0 \\ Dolphins & **15** & 0.0 & **15** & 0.0 & **15** & 0.0 & **15** & 0.0 & **15** & 0.0 \\ Football & **68** & 0.015 & **68** & 0.0 & 69 & 0.0 & 69 & 0.0 & **68** & 0.0 \\ Jazz & **81** & 0.015 & 82 & 0.0 & **81** & 0.0 & 83 & 0.0 & **81** & 0.0 \\ \hline
**Avg** & 3660.88 & 2.363 & 3664.47 & 2.565 & 3646.12 & 2.623 & 3645.82 & 0.015 & **3616.59** & 0.017 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Numerical results for the small and large-scale real social networks. four greedy algorithms starts to degrade in the context of the largest problem instances, this is not the case for IGA-PIDS.