Generic Constraint-based Block Modeling using Constraint Programming
Authors: Alex Mattenet, Ian Davidson, Siegfried Nijssen, Pierre Schaus
JAIR 2021 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this section, we validate empirically the performance of our different algorihtms. Firt, we compare our CP system to an existing mixed integer programming approach, and show that we outperform it. Then, we show the scalability of our exact search procedure on synthetic graphs of varying size. For our large neighbourhood approach, we compare it to an existing approach bundled in the software package Pajek, then we show its scalability on synthetic graphs up to 7000 vertices. Finally, we run experiments on our MDL approarch, first to validate our coding scheme, then to show the efficiency of our upper bound. |
| Researcher Affiliation | Academia | Alex Luc ıa Mattenet EMAIL Institute for Information and Communication Technologies, Electronics and Applied Mathematics, UCLouvain 3 place du Levant, 1348 Louvain-la-Neuve, Belgium Ian Davidson EMAIL Computer Science Department, University of California, Davis One Shields Ave., Davis, CA 95616-5270, USA Siegfried Nijssen EMAIL Pierre Schaus EMAIL Institute for Information and Communication Technologies, Electronics and Applied Mathematics, UCLouvain 3 place du Levant, 1348 Louvain-la-Neuve, Belgium |
| Pseudocode | Yes | The pseudocode for our LNS procedure is given in Algorithm 2. Algorithm 1 Propagation of our global constraint. Algorithm 3 Search for the number of clusters k. |
| Open Source Code | Yes | The code for the algorithms and CP models described in this article are available online on https://github.com/gadevoi/blockmodel-cp/, along with the executables and graph files used for the experiments. The code for the complete LNS algorithm is available online at https://github.com/gadevoi/blockmodel-cp/blob /master/src/main/scala/blockmodel/executables/Run LNS.scala. |
| Open Datasets | Yes | The migration graphs were built from an open dataset provided by the World Bank6. An edge Xab = 1 indicates that the number of migrants born in a living in b is more than 0.01% of the population of a. The dataset was limited to countries in continental Europe, 6. The World Bank: Migration and Remittances Data, retrieved http://www.worldbank.org/en/topic/migrationremittancesdiasporaissues/brief/ migration-remittances-dat Table 3: Results of the LNS procedure for MDL on real-wold datasets. Zachary s karate club (Zachary, 1977) Dolphin social network (Lusseau et al., 2003) Characters in Les Mis erables (Knuth, 1993) Political Books American College Football (Girvan & Newman, 2002) C. elegans neural network (Watts & Strogatz, 1998) Political blogs (Adamic & Glance, 2005) 2. Retrieved from http://www-personal.umich.edu/~mejn/netdata |
| Dataset Splits | No | The paper describes generating 'artificial graphs with a known block model structure, and added 20% of noise' and 'generated graphs with n = 20 vertices, kreal = 5 clusters, and varying levels of noise (0%, 5%, 10%, 15% and 20%)'. While it describes noise levels and graph generation, it does not specify explicit training, validation, or test dataset splits for reproducibility of data partitioning. |
| Hardware Specification | Yes | All experiments were run on a computer with Xeon Platinum 8160 24c/48t Hyper Thread processors. |
| Software Dependencies | Yes | The CP models were written and solved in Osca R (Osca R Team, 2012), and are available at https://github.com/gadevoi/blockmodel-cp/blob/master/src/main/scala/ blockmodel/executables/Run CPModel.scala. The MIP model was written and solved in Java using Gurobi (Gurobi Optimization, 2018). |
| Experiment Setup | Yes | The LNS procedure was run with initial relaxation factor α = 5%, max number of failed states fnodes = 1000, and max number of consecutive failed runs fruns = 100. We report the best solution with its number of clusters k, the description length (in bits) and the time our solver took to reach this solution. For all runs, the parameters are the same as in Figure 7: max number of failed states fnodes = 125, max number of consecutive failed runs fruns = 100, and number of restarts frestart = 10. |