# Data

This directory contains the graph instances used in the computational experiments of the paper.

## Real-world benchmark instances (Table 1)

These 14 instances were previously used as benchmarks by Yezerska et al. (2019) and Gschwind et al. (2021). They are publicly available network datasets obtained from Mark Newman's network data repository (http://www-personal.umich.edu/~mejn/netdata/) and other standard sources in network science.

| File | n | m | Description | Source |
|---|---|---|---|---|
| `karate.graph` | 34 | 78 | Zachary's karate club social network | Zachary (1977) |
| `chesapeake.graph` | 39 | 170 | Chesapeake Bay food web | Pajek datasets |
| `dolphins.graph` | 62 | 159 | Bottlenose dolphin social network | Lusseau et al. (2003) |
| `lesmis.graph` | 77 | 254 | Les Misérables character co-appearance | Knuth (1993) |
| `polbooks.graph` | 105 | 441 | Political books co-purchasing network | V. Krebs (unpublished) |
| `adjnoun.graph` | 112 | 425 | Adjacency of common adjectives and nouns | Newman (2006) |
| `football.graph` | 115 | 613 | American college football schedule | Girvan and Newman (2002) |
| `jazz.graph` | 198 | 2,742 | Jazz musician collaboration network | Gleiser and Danon (2003) |
| `celegansneural.gml` | 297 | 2,148 | *C. elegans* neural network | Watts and Strogatz (1998) |
| `celegans_metabolic.graph` | 453 | 2,025 | *C. elegans* metabolic network | Duch and Arenas (2005) |
| `netscience.graph` | 1,589 | 2,742 | Network science co-authorship | Newman (2006) |
| `polblogs.graph` | 1,490 | 16,715 | Political blogs hyperlink network | Adamic and Glance (2005) |
| `email.graph` | 1,133 | 5,451 | University email network | Guimerà et al. (2003) |
| `data.graph` | 2,851 | 15,093 | Roget's Thesaurus semantic network | Pajek datasets |

Files with the `.graph` extension use an adjacency-list format, where the first line gives the number of vertices and subsequent lines list the neighbors of each vertex (1-indexed). The `.gml` file uses the standard Graph Modelling Language format.

## Randomly generated instances

The following subdirectories contain instances generated by the authors using NetworkX (Hagberg et al. 2008). These instances are used in the experiments reported in Section 5.3 and the Appendix.

### `Barabasi/`

Barabási–Albert preferential attachment graphs (Barabási and Albert, 1999). Each file is named `n = X_ m = Y.txt`, where `X` is the number of vertices and `Y` is the attachment parameter. Parameters: n ∈ {100, 200, 300, 400, 500}, m ∈ {1, 2, 3, 4, 5}. Results are reported in Appendix Tables 13–14.

### `gnp/`

Erdős–Rényi G(n, p) random graphs (Erdős et al. 1960). Each file is named `n = X_ p = Y.txt`, where `X` is the number of vertices and `Y` encodes the edge probability p = Y/X. Parameters: n ∈ {100, 200, 300, 400, 500}, p ∈ {2/n, 4/n, 6/n, 8/n, 10/n}. Results are reported in Appendix Tables 11–12.

### `random graphs/`

LFR benchmark graphs (Lancichinetti et al. 2008) with planted community structure. Each file is named `X nodes Y degree Z.txt`, where `X` is the number of vertices, `Y` is the degree parameter, and `Z` is the instance index (1–10). Parameters: n ∈ {100, 200, ..., 1000}, degree ∈ {5, 10, 15, 20, 25}. Results for n ∈ {100, ..., 500} are reported in Tables 9–10.

All `.txt` files in these subdirectories use an edge-list format, where the first line gives the number of vertices and edges, and subsequent lines list edges as vertex pairs.

## References

- Adamic, L.A. and Glance, N. (2005). The political blogosphere and the 2004 US election: divided they blog. *Proceedings of the 3rd International Workshop on Link Discovery*, 36–43.
- Barabási, A.L. and Albert, R. (1999). Emergence of scaling in random networks. *Science*, 286(5439):509–512.
- Duch, J. and Arenas, A. (2005). Community detection in complex networks using extremal optimization. *Physical Review E*, 72(2):027104.
- Erdős, P. and Rényi, A. (1960). On the evolution of random graphs. *Publ. Math. Inst. Hung. Acad. Sci.*, 5(1):17–60.
- Girvan, M. and Newman, M.E.J. (2002). Community structure in social and biological networks. *PNAS*, 99(12):7821–7826.
- Gleiser, P.M. and Danon, L. (2003). Community structure in jazz. *Advances in Complex Systems*, 6(4):565–573.
- Gschwind, T. et al. (2021). A branch-and-price framework for decomposing graphs into relaxed cliques. *INFORMS Journal on Computing*, 33(3):1070–1090.
- Guimerà, R. et al. (2003). Self-similar community structure in a network of human interactions. *Physical Review E*, 68(6):065103.
- Hagberg, A. et al. (2008). Exploring network structure, dynamics, and function using NetworkX. *Technical report, LANL*.
- Knuth, D.E. (1993). *The Stanford GraphBase: A Platform for Combinatorial Computing*. Addison-Wesley.
- Lancichinetti, A. et al. (2008). Benchmark graphs for testing community detection algorithms. *Physical Review E*, 78(4):046110.
- Lusseau, D. et al. (2003). The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. *Behavioral Ecology and Sociobiology*, 54(4):396–405.
- Newman, M.E.J. (2006). Finding community structure in very large networks. *Physical Review E*, 74(3):036104.
- Watts, D.J. and Strogatz, S.H. (1998). Collective dynamics of 'small-world' networks. *Nature*, 393(6684):440–442.
- Yezerska, O. et al. (2019). Exact algorithms for the minimum s-club partitioning problem. *Annals of Operations Research*, 276(1-2):267–291.
- Zachary, W.W. (1977). An information flow model for conflict and fission in small groups. *J. Anthropological Research*, 33(4):452–473.
