Space of Optimal Solutions of the Correlation Clustering Problem for Complete Signed Graphs

<p><strong>Description. </strong>This is the data used in the experiments of the following paper:</p> <ul> <li>N. Arınık, R. Figueiredo, and V. Labatut, &ldquo;Multiplicity and Diversity: Analyzing the Optimal Solution Space of the Correlation Clustering Problem on Complete Signed Graphs,&rdquo;&nbsp;<em>Journal of Complex Networks&nbsp;</em>8(6):cnaa025, 2020.&nbsp;DOI:&nbsp;<a href="http://doi.org/10.1093/comnet/cnaa025">10.1093/comnet/cnaa025</a>&nbsp;⟨<a href="https://hal.archives-ouvertes.fr/hal-02994011">hal-02994011</a>⟩</li> </ul> <p>This dataset contains:</p> <ul> <li>Plot files used in the article;</li> <li>Input signed networks;</li> <li>All optimal solutions (i.e. optimal solution space) of the corresponding networks;</li> <li>Evaluation files.</li> </ul> <p><strong>Source code. </strong>The code source is accessible on GitHub:&nbsp;<a href="https://github.com/CompNet/Sosocc">https://github.com/CompNet/Sosocc</a></p> <p><strong>Citation. </strong>If you use the data or source code, please cite the above article.</p> <p><br><code>@Article{Arinik2020,</code><br><code>&nbsp; author &nbsp; &nbsp;= {Arınık, Nejat and Figueiredo, Rosa and Labatut, Vincent},</code><br><code>&nbsp; title &nbsp; &nbsp; = {Multiplicity and Diversity: Analyzing the Optimal Solution Space of the Correlation Clustering Problem on Complete Signed Graphs},</code><br><code>&nbsp; journal &nbsp; = {Journal of Complex Networks},</code><br><code>&nbsp; year &nbsp; &nbsp; &nbsp;= {2020},</code><br><code>&nbsp; volume &nbsp; &nbsp;= {8},</code><br><code>&nbsp; number &nbsp; &nbsp;= {6},</code><br><code>&nbsp; pages &nbsp; &nbsp; = {cnaa025},</code><br><code>&nbsp; doi &nbsp; &nbsp; &nbsp; = {10.1093/comnet/cnaa025},</code><br><code>}</code><br><br></p> <p>--------------------------------------------</p> <p><strong>Details.</strong></p> <p><br><strong># PLOT FILES</strong><br>* `<em>Figure1.zip</em>`: Figures showing that there might be many distinct optimal solutions of a small-sized network.<br>* `<em>Figure2.zip</em>`: Figures showing that distinct optimal solutions of a given network might be partition-wise very similar or different.<br>* `<em>Figure4: All Results.zip</em>`: Figure 4 in the article contains only a few plots regarding the results for space considerations. This zip file contains all plots, and it is organized by the values of `<em>l<sub>0</sub></em>`. In each `<em>l<sub>0</sub></em>` folder, the results are shown in three different perspectives:<br>--- Detected Imbalance Percentage vs Graph Order (i.e. number of vertices)<br>--- Prop mispl vs Graph order<br>--- Graph order vs Prop mispl<br>* `<em>workflow.pdf</em>`: The workflow of the methodology used in the article.<br>* `<em>Syrian network With All Solutions.pdf</em>`: Syrian network (on top) with core part information through node colors, and its optimal solutions in which node colors represent partition information (on bottom).<br>&nbsp;</p> <p><strong>#NETWORKS</strong><br>All networks are in `<em>Input Signed Networks.tar.gz</em>`.<br>Networks are generated through a simple random model (available in&nbsp;<em>https://github.com/CompNet/SignedBenchmark</em>) designed to produce complete (or uncomplete) unweighted networks with built-in modular structure.<br>There are 3 parameters used for the generation:</p> <ol> <li>number of nodes (`<em>n</em>`)</li> <li>initial number of modules (`<em>l<sub>0</sub></em>`)</li> <li>proportion of misplaced links, i.e. proportion of frustrated links, (`<em>q<sub>m</sub></em>`)</li> </ol> <p>Inside `<em>Input Signed Networks.tar.gz</em>`:<br>NETWORKS<br>|__n=NB-NODE_l0=INIT_NB_MODULE_dens=1.0000<br>....|__propMispl=PROP_MISPL<br>........|__propNeg=PROP_NEG<br>............|__network=NETWORK_NO<br><br>- The first hierarchy =&gt; the folders are named as follows: n=NB-NODE_l0=INIT-NB-MODULE_dens=1.0000<br>The number of nodes, the initial number of modules and the network density are given. The network density is always 1, since we treat only complete signed networks.<br>- The second hierarchy =&gt; the folders are named as follows: propMispl=PROP_MISPL<br>Proportion of misplaced links is given.<br>- The third hierarchy =&gt; the folders are named as follows: propNeg=PROP_NEG<br>Proportion of negative links (`<em>q<sub>n</sub></em>`) is specified. `<em>q<sub>n</sub></em>` changes depending on `<em>n</em>` and `<em>l<sub>0</sub></em>`. Since only complete signed networks are studied, this parameter is automatically computed from the other input parameters.<br>- The fourth hierarchy =&gt; the folders are named as follows: network=NETWORK_NO<br>Network numbers are shown.<br>In the end, thre are three file formats describing the same network content: GraphML (.graphml), Pajek NET (.net) or .G format.<br><br><strong># PARTITIONS</strong><br>All partition results are in `<em>Partition Results.tar.gz</em>`. Note that all optimal partitions of a signed network are obtained through an exact partitioning method. The code source is accessible here:&nbsp;<em>https://github.com/arinik9/ExCC</em><br>Inside `<em>Partition Results.tar.gz</em>`:<br><br>PARTITIONS<br>|__n=NB-NODE_l0=INIT_NB_MODULE_dens=1.0000<br>....|__propMispl=PROP_MISPL<br>........|__propNeg=PROP_NEG<br>............|__network=NETWORK_NO<br>................|__"<em>ExCC-all</em>"<br>....................|__"<em>signed-unweighted</em>"<br><br>- The first hierarchy =&gt; the folders are named as follows: n=NB-NODE_l0=INIT-NB-MODULE_dens=1.0000<br>- The second hierarchy =&gt; the folders are named as follows: propMispl=PROP_MISPL<br>- The third hierarchy =&gt; the folders are named as follows: propNeg=PROP_NEG<br>- The fourth hierarchy =&gt; the folders are named as follows: network=NETWORK_NO<br>- The fifth hierarchy =&gt; the folders are named as follows: "<em>ExCC-all</em>"<br>The name of the partitioning method are shown. Since an exact partitioning method is used to obtain all distinct optimal solutions, it is named as "<em>ExCC-all</em>".<br>- The sixth hierarchy =&gt; the folders are named as follows: "<em>signed-unweighted</em>"<br>The type of signed networks are shown: signed and unweighted</p> <p>In the end, the partition results are located, and the file names are named as follows:&nbsp;<em>membership.txt</em>. Note that the first partition result number starts from zero.</p> <p>&nbsp;</p> <p><strong># EVALUATIONS</strong><br>Evaluation results related to our plots are in `<em>Evaluation Results.tar.gz</em>. Note that the hierarchy of this folder is the same as that of 'Partitions'. Inside `<em>Evaluation</em><em>&nbsp;Results.tar.gz</em>`:</p> <p>- `Best-k-for-kmedoids.csv`: It contains three columns. 1) the number of solution classes via kmedoids, 2) the best Silhouette score, 3) the best clustering in terms of Silhouette score, which represents solution classes.</p> <p>- `class-core-part-size-tresh=1.00.csv`. It indicates the proportion of core part size for each solution class.</p> <p>- `exec-time.csv`: It indicates the execution time in seconds.</p> <p>- `imbalance.csv`: It contains the information of imbalance as 1) count and 2) percentage</p> <p>- `nb-solution.csv`: It indicates the total number of solutions<br>--------------------------------------------</p> <p>Funding:&nbsp;this research benefited from the support of the Agorantic FR 3621, as well as the FMJH Program PGMO and from the support to this program from EDF-THALES-ORANGE-CRITEO.</p>