## 5 Experimental Evaluation
### Problem Instances  
We use three sets of benchmark instances for the experimental evaluation. The first two have already been used by other studies on the MPIDS problem, while the last one (SNAP networks) consists of large-scale complex networks that are studied for the first time in the context of the MPIDS problem.  
1. Small social networks: this class of instances contains four well-known real and synthetic networks namely _American College Football_ (Football) (Football) (Football, 1970), _Zachary's Karate Club_ (Karate) (Karate) (Karate, 1970), the _Dolphins Network_ (Dolphins) (Karate, 1970) and the _Jazz Network_ (Jazz) (Karate, 1970). Characteristics such as the number of vertices and the number of edges of these networks are provided in Table 2. The values of the optimal solutions for each instance (except for the last one) were taken from ([PERSON], 1970) in which the authors also made use of CPLEX.
2. Large-scale social networks: this class of instances contains 13 real social networks which were provided by the authors of ([PERSON], 1970) and some of them were originally downloaded from the Network Data Repository ([PERSON], 1970). Their characteristics, together with a brief description, are given in Table 3.
3. SNAP social networks: this class of instances contains 22 real complex networks with sizes ranging from \(10^{4}\) vertices to \(3\times 10^{7}\). It was download from the Stanford Large Network Dataset Collection ([PERSON], 1970). All these instances were originally directed graphs and they are transformed to undirected graphs by neglecting arc orientations and considering parallel edges as one edge. Table 4 gives a brief description of the SNAP networks used in our experiments after preprocessing.  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Network** & \(n\) & \(m\) & Opt ([PERSON], 1970) & **Description** \\ \hline Karate & 34 & 78 & 15 & Social network of friendships in a Karate club \\ Dolphins & 62 & 159 & 30 & Dolphin social network \\ Football & 115 & 613 & 63 & Network of American college football teams \\ Jazz & 198 & 2742 & - & Collaboration network between Jazz Musicians \\ \hline \hline \end{tabular}
\end{table}
Table 2: Small real social networks used in experiments.  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Network** & \(n\) & \(m\) & **Description** \\ \hline CA-GrQc & 5241 & 14,484 & Collaboration network of Arxiv General Relativity \\ CA-HepTh & 9875 & 25,973 & Collaboration network of Arxiv High Energy Physics Theory \\ CA-HepPh & 12,006 & 118,489 & Collaboration network of Arxiv High Energy Physics \\ CA-AstroPh & 18,771 & 198,050 & Collaboration network of Arxiv Astro Physics \\ CA-CondMat & 23,133 & 93,439 & Collaboration network of Arxiv Condensed Matter \\ Email-Enron & 36,692 & 183,831 & Email communication network from Enron \\ ncsrrhr92 & 6396 & 15,872 & Collaboration network between by scientists \\ actors-data & 10,042 & 145,682 & Collaboration network between by actors \\ ego-facebook & 4039 & 88,234 & Social circles from Facebook \\ socfb-nips-ego & 2888 & 2981 & Social friendship network extracted from Facebook \\ socfb-Mich67 & 3748 & 81,903 & Social friendship network extracted from Facebook \\ socfb-Brandeis99 & 3898 & 137,567 & Social friendship network extracted from Facebook \\ soc-gplus & 23,628 & 39,194 & Social network extracted from Google+ \\ \hline \hline \end{tabular}
\end{table}
Table 3: Large-scale real social networks used in experiments.  
In general, note that the benchmark instances are assumed to be simple connected graphs without isolated vertices. For this purpose, we employed a preprocessing step for removing isolated vertices, self-loops and parallel edges.