DOI: 10.6084/m9.figshare.15043911
title: Efficient Enumeration of Correlation Clustering Optimal Solution Space

description: This is the data used in the experiments of our paper submitted to the journal of Global Optimization:<br><i>N. Arinik, R. Figueiredo, V. Labatut (</i><i>submitted), Efficient Enumeration of Correlation Clustering Optimal Solution Space, Journal of Global Optimization.</i> The code sources are accessible from here: <i>https://github.com/</i><i><i>CompNet</i>/Sosocc</i>, <i>https://github.com/CompNet/EnumCC</i><br>We detail below the structure of the zip file 'article_materials.zip:'<br> <i>Experiments for Dataset 1networks: We generate these complete and incomplete networks through our random signed network generator, which is publicly available online. For complete unweighted signed networks, this model relies on only three parameters: n (number of vertices), l<sub>0</sub> (initial number of modules) and <i>q<sub>m</sub></i> (proportion of misplaced edges, i.e. edges meant to be frustrated by construction). Moreover, we make the assumption that the proportion of misplaced edges is the same inside and between the modules. When it comes to incomplete unweighted signed networks, we introduce two more parameters, which are the density d of the graph and the proportion q neg of the negative edges. The last parameter q<sub>neg</sub> allows to control the ratio of positive to negative edges. For complete unweighted signed networks with d = 1, we generate 20 replications for parameter values l<sub>0</sub> = 3, n <i>∈</i> {32, 36, 40, 45, 50} and <i>q<sub>m</sub></i> <i>∈</i> {0.1, 0.2, 0.3, 0.4, 0.5, 0.6}. In these networks, the value of <i>q<sub>neg</sub> </i> with the considered parameters is approximately equal to 0.7. For incomplete unweighted signed networks with d <i>∈</i> {0.25, 0.50}, we generate 20 replications for parameter values l<sub>0</sub> = 3, n <i>∈</i> {32, 36, 40}, q<sub>m</sub> <i>∈</i> {0.1, 0.2, 0.3, 0.4, 0.5, 0.6} and <i>q<sub>neg</sub> </i><i>∈</i> {0.3, 0.5, 0.7}. In total, we produce 600 and 1,080 instances for complete and incomplete networks, respectively, which makes a total of 1,680 instances. partitions: folder containing the partitioning results of two methods: EnumCC(3) vs. OneTreeCC(). Note that the results of OneTreeCC() are not shown for space considerations, except for those with n=50. Resultsdelay_exec_time: all the results and plots regarding the difference of execution times between EnumCC(3) and OneTreeCC() (i.e., EnumCC(3) minus OneTreeCC()), represented on the log-scaled y-axis of the plots. When such difference takes a negative value, this means our proposed method EnumCC(3) runs faster than OneTreeCC(). EnumCC_nb-jumps: all the results regarding the number of jumps related to EnumCC(3), i.e. n<sub><i>jump</i></sub>(EnumCC(3)) exec_time: all the results regarding the execution times of EnumCC(3) and OneTreeCC().nb-sols: all the results regarding the number of optimals solutions based on EnumCC(3). Note that we show the results of OneTreeCC() only for those with n=50, since both methods run out of the time limit of 12h for several networks with n=50.<br> Experiments for Dataset 2benchmark netwoks: We generate these complete and incomplete networks through our random signed network generator, which is publicly available online. The optimal solution for a generated network is known by construction. For a given n, d and l<sub>0</sub>, we first create a perfectly structurally balanced (i.e., internally positive and externally negative) signed network with a built-in module structure. The underlying module structure constitutes the optimal partition. Then, in order to take into account different positive to negative ratio values for internal and external edges we generate several signed networks by perturbing the initial signed network without affecting its underlying optimal partition, thanks to its definition of stability range. We generate signed networks with parameter values n <i>∈</i> {30, 40, 50, 60, 70, 90}, d <i>∈</i> {0.25, 1.00} and l<sub>0</sub> <i>∈</i> {2, 4, 6}. In total, we produce 214 and 184 instances for complete and incomplete networks, respectively, which makes a total of 398 instances. benchmark partitions: folder containing the partitioning results of two methods: CoNS(<i>r<sub>max</sub></i>) with vs. without MVMO pruning, where <i>r<sub>max</sub></i> ∈ {3,4}. results: two csv files containing benchmark results between CoNS(<i>r<sub>max</sub></i>) with vs. without MVMO pruning, where r<sub>max</sub> ∈ {3,4}. <br></i>