# Flexible Optimization of Structural Measures for Community Detection

Arnold Hien, Cécile Bothorel, Laurent Brisson, Nicolas Jullien, Patrick Meyer, Grégory Smits

► To cite this version:

Arnold Hien, Cécile Bothorel, Laurent Brisson, Nicolas Jullien, Patrick Meyer, et al. Flexible Optimization of Structural Measures for Community Detection. 2025. hal-05299688

HAL Id: hal-05299688

https://hal.science/hal-05299688v1

Preprint submitted on 6 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
Graphical Abstract

Flexible Optimization of Structural Measures for Community Detection

Arnold Hien, Cécile Bothorel, Laurent Brisson, Nicolas Jullien, Patrick Meyer, Gregory Smits

Input

<figure><img src="image_1.png" /></figure>

Modularity

<figure><img src="image_2.png" /></figure>

Cut-ratio

<figure><img src="image_3.png" /></figure>

Conductance

<figure><img src="image_4.png" /></figure>

Density

Structural measures to optimize

<figure><img src="image_5.png" /></figure>

Graph

User constraints

<figure><img src="image_6.png" /></figure>

FO-SM-CD

Flexible Optimization Framework to graph partitioning

+ Connectedness constraint

+ Variable ordering strategy

+ ILS metaheuristic

<figure><img src="image_7.png" /></figure>
# Highlights

## Flexible Optimization of Structural Measures for Community Detection

Arnold Hien, Cécile Bothorel, Laurent Brisson, Nicolas Jullien, Patrick Meyer, Gregory Smits

* FO-SM-CD, a CP-based framework to community detection allowing for the selection and combination of various structural measures and the integration of user constraints.

* A connectedness constraint to reduce the search space and speed up the identification of an optimal partition.

* A variable ordering strategy used during the exploration of the search space to make more efficient the exploration process of the search space.

* Experiments were conducted to compare the proposed approach with the only other community detection framework based on CP.
Flexible Optimization of Structural Measures for
Community Detection

Arnold Hien<sup>c,*</sup>, Cécile Bothorel<sup>a</sup>, Laurent Brisson<sup>a</sup>, Nicolas Jullien<sup>b</sup>, Patrick Meyer<sup>a</sup>, Gregory Smits<sup>a</sup>

<sup>a</sup>IMT Atlantique, Lab-STICC, UMR CNRS 6285, F-29238 Brest, France

<sup>b</sup>IMT Atlantique, LEGO-Marsouin, Brest, France

<sup>c</sup>Univ. Orléans, INSA Centre Val de Loire, LIFO UR 4022, Orléans, France

**Abstract**

Community detection is a crucial task in many graph data analysis pipelines, with applications ranging from social networks to biology and transportation systems. This work introduces FO-SM-CD, a novel constraint programming framework for community detection. While existing approaches mainly rely on the modularity criteria to detect communities, FO-SM-CD allows for the combination of different structural measures such as conductance, density, and cut-ratio. It also supports user-defined constraints, providing unprecedented flexibility to tailor the detection process to specific needs.

On top of an agglomerative algorithm to community detection strategy, this article makes two major contributions. First, it provides a constraint-based modeling of different structural measures that can be combined in the objective function, and second, it exploits a connectedness property to reduce the search space and speed up the identification of optimal partitions. Extensive experiments on controlled synthetic datasets confirm the diversity of graph partitions obtained when different structural measures are used. It also demonstrates the computational efficiency of the connectedness constraint combined with iterative local search heuristics compared to existing approaches.

Email addresses: lobnury-arnold.hien@univ-orleans.fr (Arnold Hien), cecile.bothorel@imt-atlantique.fr (Cécile Bothorel), laurent.brisson@imt-atlantique.fr (Laurent Brisson), nicolas.jullien@imt-atlantique.fr (Nicolas Jullien), patrick.meyer@imt-atlantique.fr (Patrick Meyer), gregory.smits@imt-atlantique.fr (Gregory Smits)

<footnote>*Corresponding author.</footnote>
# 1. Introduction

Community detection in graphs is the process of identifying groups of nodes (called communities) that are more densely connected to each other than to the rest of the graph. Communities represent meaningful substructures or functional units within these graphs, providing valuable insights that can enhance the management and design of the systems they model. These substructures, such as social groups, functional modules, or geographical regions, can inform decision-making, optimize resource allocation, and reveal hidden patterns.

Consequently community detection has diverse applications across domains. In *social networks*, it identifies groups with shared interests or relationships, enhancing marketing strategies and group-based recommendations. In *biological networks*, it uncovers functional modules like protein complexes or metabolic pathways, aiding in drug discovery and disease understanding. For *recommendation systems*, it clusters users or products to improve personalized suggestions. In *citation networks*, it reveals research topics or academic communities, fostering collaborations and trend analysis. In *energy networks*, it helps optimize grid management, localize faults, and integrate renewables effectively. Finally, in *transportation networks*, it identifies traffic patterns or zones of high connectivity, improving urban planning and reducing congestion.

A wide range of algorithms exists to partition a network (i.e. a graph) into clusters that may represent communities. However, as highlighted in [1]:

1. the nature of the discovered communities is not always well understood;

2. and these algorithms rely on strong assumptions on the structural property that a subgraph should satisfy to be considered as a community.

Surveys [2, 3] point out a lack of consensus on the precise definition of a community, which has led to the development of numerous algorithms designed to address this ambiguity. Each algorithm captures different aspects of community behavior, reflecting the diverse contexts and goals in which community detection is applied. For practitioners, understanding the methodology behind these algorithms is crucial to ensure the reliability and applicability of the derived insights.
***Algorithmic Community Detection methods.*** The classification and relationships among different community detection methods remain a subject of ongoing discussion, with no universal agreement on how they can be grouped into distinct families or described in simple terms. [4] classifies community detection methods into different subgroups.

***Edge removal*** methods rely on detecting edge centrality to identify communities by dividing the graph into subgroups based on measures such as *betweenness centrality scores* [5] or the *edge clustering coefficient* [6]. *Modularity optimization* methods detect community structures by maximizing the modularity measure, either using a greedy approach [7, 8] or a spectral approach [9]. [10] proposed a *label propagation* method, inspired by message-passing paradigms, where the community membership of a node is determined based on the memberships of its neighbors. *Statistical inference* methods associate each community with a statistical significance probability distribution, calculated using measures like node degree distribution [11] or stochastic and Bayesian approaches [12]. Finally, the *Infomap* method proposed by [13] identifies communities by maximizing the compression of random walks encoded as a binary sequence.

These solutions may provide quite different groupings or sets of communities,
and the question arises as to their relevance and how these competing solutions
can be compared.

***Evaluating community structure.*** While the time complexity of community detection algorithms is undoubtedly important, the nature and quality of the partition are crucial too. Generally, two approaches are used to assess quality: *validation metrics* and *structural measures*.

*Validation metrics* allow the comparison of the discovered community structure with a reference or ground-truth partition. As stated by [14], these metrics evaluate the similarity between two partitions, helping users compare the community structure of a given graph dataset with a reference and state-of-the-art methods. Commonly used association measures include NMI (*Normalized Mutual Information*) [15], RI (*Rand Index*) and ARI its normalized version (*Adjusted Rand Index*) [16], and FCC (*Fraction of Correctly Classified nodes*) [17].

While validation metrics have notable advantages, particularly in unsupervised
learning, they have a key limitation: they do not account for the structural charac-
teristics of communities. As noted in [14], these metrics only compare individual
node memberships without considering the edges between them.

*structural measures*, on the other hand, overcome this limitation by evaluating
the structural configuration of the partitions and the interactions between nodes.
They offer a complementary evaluation to validation metrics. Common structural measures include *modularity*, *cut-ratio*, and *density*. These evaluation methods provide insight into both the quality of the partitioning and the effectiveness of the community detection method used. Interestingly, from a structural perspective, the evaluation often reveals that the partition obtained by the method exhibits different, possibly more relevant, patterns compared to reference partitions that consider modularity only [4]. This observation suggests that there may be potential to improve community structure further by exploring new partitions that specifically optimize structural measures.

***Flexible optimization of structural quality measures.*** Several approaches have been proposed to find a graph partition optimizing a given structural measure, mostly modularity [7, 18, 13, 20, 21, 22, 23, 24] and, to a lesser extent, conductance [25, 26].

Declarative approaches, as a means of introducing flexibility into graph clustering, have influenced the development of Constrained Community Detection (CCD) methods, which aim to incorporate prior information and address the inherent resolution limitations of traditional algorithmic methods. [27]. These limits often prevent the identification of certain patterns in graphs. Early work in CCD, such as [28], introduced size constraints to overcome modularity's bias towards large communities. However, these early methods were limited to size constraints and lacked flexibility to handle other types of measures and constraints.

To overcome this lack of flexibility, declarative approaches inspired by Constraint Programming (CP) and Integer Linear Programming (ILP) techniques [29, 30, 31] can be used. For example, [20] proposed a CP-based method that allows users define complex constraints while maximizing modularity. [23] presented an ILP-based approach that improves previous methods [21, 32] by reducing graph size through clique filtering and node merging. A SAT-based framework by [33] further extends these methods by enabling overlapping community detection through graph partitioning with bounded diameters.

However most declarative CCD methods focus on optimizing modularity or other problem-specific measures. Other structural metrics, such as conductance or cut-ratio, remain underexplored, highlighting an area for future research and development.

***Research gap and contribution.*** Despite the proliferation of community detection algorithms across diverse domains, significant research challenges persist. While existing literature predominantly focuses on modularity optimization, there remains a critical research gap in the exploration of alternative structural measures.
Next to that, most algorithmic approaches lack flexibility in defining and enforcing specific structural constraints, limiting their adaptability to complex network scenarios. Also, the nature of discovered communities often remains poorly understood, with algorithms relying on diverse and sometimes incompatible assumptions about community composition.

These research challenges create a significant opportunity for developing more nuanced community detection frameworks. By introducing a CCD approach using CP, we propose to address these limitations and provide a more flexible framework for community structure detection and analysis. Our CP model, named FO-SM-CD that stands for Flexible Optimization of Structural Measures for Community Detection, forms the core of our contribution, addressing methodological limitations in current community detection research while providing a highly adaptable tool for practitioners across various domains. FO-SM-CD brings a significant improvement in flexibility to graph partitioning, as it is the first framework that makes it possible to combine different structural measures and user-defined constraints.

The article is structured as follows: Section 2 details existing structural measures and gives some backgrounds about the CP paradigm. In Section 3, we present our CP-based model and define our community-based search strategy. In Section 4, different experiments are conducted to assess the relevance of our approach and study the impact of the choice of a structural measure on the partition it yields. For this, we generated some synthetic datasets using the Python library networkx [34].

## 2. Preliminaries

Consider a graph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$, where $\mathcal{V}$ represents its set of vertices and $\mathcal{E}$ its set of edges, with $n = |\mathcal{V}|$ and $m = |\mathcal{E}|$. Consider a partition $\mathcal{P}$ of $\mathcal{G}$ into $k$ communities $\mathcal{P} = \{P_1, \dots, P_k\}$. Given a community $P_c$, we use the following notations: $n_c$ is the number of vertices of $P_c$; $m_c$ is the number of edges inside community $P_c$ s.t. $m_c = |\{(i, j) \in \mathcal{E} : i \in P_c, j \in P_c\}|$; $l_c$ is the number of edges that connect $P_c$ to the other vertices outside of $P_c$; $l_c = |\{(i, j) \in \mathcal{E} : i \in P_c, j \notin P_c\}|$.

<footnote n="1">¹https://networkx.org/</footnote>
## 2.1. Structural metrics

As previously stated, structural metrics are mainly used to evaluate partitions already found using algorithmic methods. These metrics quantify the extent to which a given structural property is observed in a obtained partition. While most of them are concerned with the density of connections within a community $P_c$, their interpretation and mathematical formulation may vary depending on the context they are employed. The following definitions are used in this work.

DENSITY is an internal measure that quantifies the fraction of existing edges to the total possible edges in $P_c$ ([11]). This metric is intrinsically tied to the community structure of graphs, as communities are expected to exhibit a higher density of internal edges compared to edges connecting the community to the rest of the graph. However, the current formula tends to favor smaller communities as the graph size increases [35]. To address this limitation, we adopt an alternative approach in this article, the scaled density, a normalized version of density defined as follows:

$$Dens(P_c) = \frac{m_c}{n_c - 1}$$

CUT-RATIO is an external measure that quantifies the fraction of existing edges between a community and the rest of the network, relative to the total possible edges of this type. It can therefore be interpreted as a measure of external density:

$$CutR(P_c) = \frac{l_c}{n_c(n - n_c)}$$

CONDUCTANCE quantifies the proportion of connections to other communities relative to the total number of connections. Unlike the two previous measures, it is a hybrid metric that considers both the internal and external edges of a community:

$$Cond(P_c) = \frac{l_c}{2m_c + l_c}$$

MODULARITY is also a hybrid metric defined as the difference between the number of internal edges in communities and the expected number of these edges. Thus, given a pair of nodes i and j, A the adjacency matrix of G, we have:

$$Mod(P) = \frac{1}{2m} \sum_{ij} (A_{ij} - \frac{k_i \cdot k_j}{2m}) \delta(c_i, c_j),$$

where $\delta(c_i, c_j)$ is the Kronecker function returning 1 if i and j are assigned to the same community, denoted by $c_i$ and $c_j$ for i and j respectively, 0 otherwise. $k_i$ and $k_j$ are the degrees of i and j.
## 2.2. Constraint Programming and Optimisation

CP is a flexible paradigm for modelling and solving combinatorial problems [36]. These problems include Constraint Satisfaction Problems (CSPs) and Constraint Optimization Problems (COPs).

**CP Paradigm.** A CP model for a satisfaction problem consists of variables $\mathcal{X} = X_1, \dots, X_n$, domains $\mathcal{D}$ mapping each variable $X_i$ to possible values $dom(X_i)$, and constraints $\mathcal{C}$ on $\mathcal{X}$. Each constraint $c \in \mathcal{C}$ specifies allowed value combinations for its variables $\mathcal{X}(c)$. A solution is a complete assignment on $\mathcal{X}$ satisfying all constraints. COPs generalize CSPs [37] by introducing an objective function $f$ to optimize. Solving a COP involves finding an optimal solution by iteratively solving CSPs.

**Resolution Approaches.** Constraint solvers typically use backtracking search to explore partial assignments. For readers not familiar with this technique, Algorithm 1 recalls this process. Each node represents an assignment of a variable $X_i$ to a value $v$, guided by variable ordering and value selection heuristics (line 5). A solution is found when all domains are singletons, and constraints are satisfied (line 10). If a constraint is violated (i.e., a domain is empty, line 2), backtracking occurs (line 3). To accelerate the search, solvers reduce variable domains using constraint propagation (line 1). However, for large problems, propagation can be ineffective. Search metaheuristics like ILS [38] address this by enabling non-exhaustive exploration, which reduces complexity but does not ensure complete solution sets for CSPs or optimality for COPs.

# 3. A Flexible CP-based Framework to Community Detection

FO-SM-CD is a declarative community detection framework enhancing the approach introduced by [20] with a new constraint to reduce the size of the search space. Combined with an efficient variable ordering strategy, these two contributions significantly improve the efficiency of the resolution process.

## 3.1. General CP-based Model

Consider a graph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ and $\mathcal{M}$ that represents a set of structural quality measures to be optimized (maximized or minimized) using CP. The community detection problem involves partitioning $\mathcal{G}$ into a set of clusters $\mathcal{P} = \{P_1, \dots, P_k\}$ such that:

$$ \bigcup_{c \in [1, k]} P_c = \mathcal{V} \quad \wedge \quad P_i \bigcap_{i \neq j} P_j = \emptyset. $$
**Algorithm 1 Constraint-Search (D)**

**Input:** $\mathcal{X}$: a set of decision variables, $\mathcal{C}$: a set of constraints

**InOut:** $\mathcal{D}$: a set of variable domains

1: $\mathcal{D} \leftarrow \text{Filtering}(\mathcal{D}, \mathcal{C})$

2: **if** $\exists X_i \in \mathcal{X}$ s.t. $\text{dom}(X_i) = \emptyset$ **then**

3: **return** failure

4: **else if** $\exists X_i \in \mathcal{X}$ s.t. $|\text{dom}(D_i)| > 1$ **then**

5: Select $X_i \in \mathcal{X}$ s.t. $|\text{dom}(X_i)| > 1$

6: **for** $v \in \text{dom}(X_i)$ **do**

7: Constraint-Search($\mathcal{D} \cup \{X_i \to \{v\}\}$)

8: **end for**

9: **else**

10: **return** solution $\mathcal{D}$

11: **end if**

*Variables.* Our CP model, named FO-SM-CD, represents each node $i \in \mathcal{G}$ as an integer variable $X_i \in [1, n]$, indicating the index of the community to which it belongs. A solution to the problem is an assignment of a unique value $c \in [1, n]$ to each variable $X_i$, optimizing the objective function $\mathcal{M}$. Using a vector of variables $\mathcal{X} = (X_1, \dots, X_n)$, the model is defined as follows:

$$ \max / \min_{\mathcal{X}} \mathcal{M}(\mathcal{X}) \qquad (1) $$

$$ \text{s.t.} \quad \text{SymmetryBreaking}(\mathcal{X}) \wedge \qquad (2) $$

$$ \text{Connectedness}(\mathcal{X}, \mathcal{G}) \qquad (3) $$

*Symmetry Breaking Constraint.* When assigning values $c_i$ to each variable $X_i$, redundant symmetrical solutions may emerge, complicating the solving process. For example, given a graph with 5 nodes and a solution $\mathcal{X} = (1, 1, 2, 3, 3)$, two redundant symmetric solutions can also exist: $\mathcal{X}' = (1, 1, 3, 2, 2)$ and $\mathcal{X}'' = (2, 2, 1, 3, 3)$. For any solution with $k$ communities, there are $k!$ symmetric solutions, greatly expanding the search space. To address this, the CP constraint valuePrecedeChain [39] is used to ensure that a community $P_c$ can only be created and populated if all preceding communities $P_1 \dots P_{c-1}$ are non-empty.

*Connectedness Constraint.* This constraint ensures that the communities formed during the search are connected components. While optimizing structural measures typically implies community connectedness, the Connectedness constraint
**Algorithm 2 Connectedness**

**Input:** $\mathcal{G}$: the graph data

**InOut:** $\mathcal{X}$: the set of decision variables

1: $\mathcal{X}^* \leftarrow$ unassigned variables

2: **for** $X_i \in \mathcal{X}^*$ **do**

3: **for** $c \in \text{dom}(X_i)$ **do**

4: $\mathcal{R} \leftarrow$ all paths to a node $j \in P_c$

5: **if** $\forall R \in \mathcal{R}: \exists j \in R \text{ s.t. } X_j \neq c$ **then**

6: $\text{dom}(X_i) \leftarrow \text{dom}(X_i) - \{c\}$

7: **end if**

8: **end for**

9: **end for**

10: **return true**

explicitly eliminates inconclusive branches from the search tree, reducing the search space and speeding up the resolution process. This is achieved using the filtering rule in Algorithm 2. Given an unassigned variable $X_i$ and the set $\mathcal{R}$ of all paths connecting node $i$ to node $j$ in community $c$ (line 4), if every path contains a node from another cluster $d \neq c$, then $X_i$ cannot be assigned to $c$. This filtering ensures that community $c$ is not disconnected by nodes $j$ outside $c$.

*Objective Function.* Structural metrics that may take part of the objective function all incorporate the number of internal links $m_c$ and external links $l_c$, as well as the size of the community $n_c$. Modeling these objective functions therefore requires expressing these values as functions of $\mathcal{X}$:

$$m_c = \sum_{i,j} (X_i == c) \wedge (X_j == c),$$

$$l_c = \sum_{i,j} (X_i == c) \wedge (X_j \neq c),$$

$$\text{and } n_c = \sum_i (X_i == c).$$

## 3.2. User Constraints

As previously mentioned, CCD allows for the introduction of user prior information into the partitioning process to uncover structures that are often difficult to detect. CP provides a declarative framework that simplifies the customization of
solutions and facilitates the integration of external knowledge into the initial problem. These constraints can be defined at various levels, ranging from the entire partition to individual instances. Commonly used user constraints include:

* **Partition size constraints:** These constraints define the size of the partition $\mathcal{P}$, specifying the number of communities $k$, as well as the minimum $k_{min}$ and maximum $k_{max}$ allowable values:

$$ \max(\mathcal{X}) = k, \qquad (4) $$

$$ \max(\mathcal{X}) \geq k_{min}, \qquad (5) $$

$$ \max(\mathcal{X}) \leq k_{max}. \qquad (6) $$

This constraint is of particular interest as, in contrast to CP-based clustering, the number of communities is not given as a parameter of the model.

* **Community size constraints:** These constraints relies on a threshold $\alpha$ to condition the size of the expected communities. To model this, it is essential to ensure the presence of at least one node associated with each community $c$ before applying the constraint. For a given community $P_c$, its size is represented as $n_c$: $n_c = \sum_{i=1}^{n} (X_i == c)$. Consequently, the community size constraints are expressed as follows:

$$ \forall c \in [1, n] : (n_c \geq 1) \land (n_c \leq \alpha). \qquad (7) $$

* The pairwise node constraints MUST-LINK and CANNOT-LINK express whether or not two nodes $i$ and $j$ belong to the same community:

$$ \text{MUST-LINK} (i, j) : X_i = X_j, \qquad (8) $$

$$ \text{CANNOT-LINK} (i, j) : X_i \neq X_j. \qquad (9) $$

* Finally, constraints can be applied to the value of the objective function. This allows the user to specify minimum and maximum values, denoted by $\gamma$, that must be reached for the result to be considered valid:

$$ \mathcal{M}(\mathcal{X}) \leq \gamma. \qquad (10) $$
**Algorithm 3 Community-based Variable Selection**

**Input:** $\mathcal{G}, \mathcal{X}$

**Output:** one variable of $\mathcal{X}$

1. $\mathcal{X}_u \leftarrow$ unassigned-nodes with the most instantiated-neighbours

2. order $\mathcal{X}_u$ by instantiated-neighbours and node-degree descending

3. **return** $X_0$

### 3.3. Community-based Search Strategy

In CP, the search strategy defines both the order in which decision variables are instantiated by the solver and the sequence in which values are selected for instantiation. As such, this strategy plays a crucial role in shaping the search tree and influencing the model's performance. For our model, we have devised a variable ordering heuristic that selects, at each search tree node, the variable corresponding to the node with the highest number of already instantiated neighbors. This strategy, described in Algorithm 3, thus expands the communities step by step, prioritizing the nodes with the highest degree of neighborhood. This approach is similar to agglomerative methods like LOUVAIN [8]. This variable ordering strategy is employed in line 5 of Algorithm 1.

## 4. Experiments

This section details experiments conducted on several artificial datasets so as to answer two research questions:

* To which extent the *Connectedness* constraint and the proposed variable ordering strategy improve a CP-based community detector?

* What is the impact of a structural measure on the obtained graph partition?

The proposed FO-SM-CD framework is compared with the one introduced in [20], which is, to the best of our knowledge, the only other approach allowing for the combination of different structural measures and the integration of user constraints in the partitioning process. All the necessary materials to reproduce these experiments are available at the following address: *provided as supplementary materials during the article reviewing phase*.
## 4.1. *Experimental Protocol*

**Hardware and Datasets.** To evaluate our method, we implemented it using Choco-Solver [40] version 4.10.14 and applied it to nine artificial datasets generated with Networkx (see Table 4 for data characteristics). The experiments were conducted on a Debian server with a 2.0 GHz Intel Xeon Gold 6138 processor. For each instance, we set a time limit of 24 hours for computation.

*Objective Functions.* As mentioned earlier, CP allows for the modeling of different objective functions. For our experiments, and given the limited space available, we selected four objective functions to evaluate: MODULARITY, CONDUCTANCE, DENSITY and CUT-RATIO.

*Search Strategies.* The size of certain datasets can impact FO-SM-CD's performance, requiring the use of resolution heuristics like ILS, which yield approximate results without guaranteeing optimality. However, depending on the chosen parameters, the solutions provided by ILS can be quite close to the optimum. Therefore, we will analyze the performance of our method using both our community-based search strategy and ILS.

## 4.2. *Performance Evaluation*

In this section, we evaluate the performance of FO-SM-CD using two search space exploration approaches.

*Complete Search Space Exploration.* This strategy ensures that the optimal solution is retrieved through a comprehensive exploration of the search space. We observe that the *Connectedness* constraint enables FO-SM-CD to outperform the Ganji *et al.* method. As shown indeed in Table 1 and 2, FO-SM-CD is more efficient, especially when the modularity and density measures are considered. Execution times are indeed notably lower and we observe a substantial reduction in the search space, with fewer nodes being traversed by FO-SM-CD compared to Ganji *et al.* For instance, on dataset 5, FO-SM-CD reduces execution time by half and even cuts it by a factor of 6 for modularity. The number of nodes is also reduced by factors of two, four, or even ten. In terms of density, it is clear that Ganji *et al.* fails to return certified optimum results within the set time limit.

*ILS Resolution.* Despite the performance gains over Ganji *et al.*'s method, FO-SM-CD's performance remains inconsistent. As shown in Table 1, the optimization of modularity and density remains time-consuming. One possible explanation is the exhaustive exploration of inconclusive nodes to refine the current
<table><caption>Table 1: CPU-time (in seconds) using Ganji *et al.* model (1) and FO-SM-CD (2) for optimising: *M*₁: MODULARITY, *M*₂: CONDUCTANCE, *M*₃: CUT-RATIO and *M*₄: DENSITY. — indicates a time out.</caption><thead><tr><th rowspan="3">Data ID</th><th colspan="8">CPUTime</th></tr><tr><th colspan="2">M<sub>1</sub></th><th colspan="2">M<sub>2</sub></th><th colspan="2">M<sub>3</sub></th><th colspan="2">M<sub>4</sub></th></tr><tr><th>(1)</th><th>(2)</th><th>(1)</th><th>(2)</th><th>(1)</th><th>(2)</th><th>(1)</th><th>(2)</th></tr></thead><tbody><tr><td>1</td><td>5569.0</td><td><strong>2142.17</strong></td><td>22.75</td><td><strong>23.2</strong></td><td>52.27</td><td><strong>35.17</strong></td><td>-</td><td><strong>22960.0</strong></td></tr><tr><td>2</td><td>2454.01</td><td><strong>256.16</strong></td><td>10.03</td><td><strong>4.86</strong></td><td>20.09</td><td><strong>5.17</strong></td><td>-</td><td><strong>1910.7</strong></td></tr><tr><td>3</td><td>434.82</td><td><strong>49.17</strong></td><td>2.81</td><td><strong>2.8</strong></td><td>6.93</td><td><strong>2.3</strong></td><td>-</td><td><strong>752.48</strong></td></tr><tr><td>4</td><td>329.7</td><td><strong>89.26</strong></td><td>4.77</td><td><strong>2.7</strong></td><td>1.89</td><td><strong>1.42</strong></td><td>-</td><td><strong>5269.0</strong></td></tr><tr><td>5</td><td>22099.0</td><td><strong>3438.37</strong></td><td>28.29</td><td><strong>10.57</strong></td><td>59.37</td><td><strong>20.16</strong></td><td>-</td><td><strong>27393.0</strong></td></tr><tr><td>6</td><td>95.87</td><td><strong>18.63</strong></td><td>4.22</td><td><strong>2.6</strong></td><td>4.16</td><td><strong>2.62</strong></td><td>-</td><td><strong>213.34</strong></td></tr><tr><td>7</td><td>483.68</td><td><strong>51.06</strong></td><td>4.74</td><td><strong>2.87</strong></td><td>3.85</td><td><strong>2.47</strong></td><td>-</td><td><strong>653.17</strong></td></tr><tr><td>8</td><td>1102.37</td><td><strong>432.25</strong></td><td>9.77</td><td><strong>6.03</strong></td><td>2.98</td><td><strong>2.33</strong></td><td>-</td><td><strong>7963.0</strong></td></tr><tr><td>9</td><td>49.3</td><td><strong>7.48</strong></td><td>3.09</td><td><strong>1.98</strong></td><td>2.81</td><td><strong>2.0</strong></td><td>-</td><td><strong>38.02</strong></td></tr></tbody></table>

<table><caption>Table 2: Nodes count using Ganji *et al.* model (1) and FO-SM-CD (2) for optimising: *M*₁: MODULARITY, *M*₂: CONDUCTANCE, *M*₃: CUT-RATIO and *M*₄: DENSITY. — indicates a time out.</caption><thead><tr><th rowspan="3">Data ID</th><th colspan="8">#Nodes</th></tr><tr><th colspan="2">M<sub>1</sub></th><th colspan="2">M<sub>2</sub></th><th colspan="2">M<sub>3</sub></th><th colspan="2">M<sub>4</sub></th></tr><tr><th>(1)</th><th>(2)</th><th>(1)</th><th>(2)</th><th>(1)</th><th>(2)</th><th>(1)</th><th>(2)</th></tr></thead><tbody><tr><td>1</td><td>7,871,943</td><td><strong>2,716,432</strong></td><td>14,765</td><td><strong>11,387</strong></td><td>79,796</td><td><strong>37,369</strong></td><td>-</td><td><strong>12,038,462</strong></td></tr><tr><td>2</td><td>5,773,952</td><td><strong>245,517</strong></td><td>6,686</td><td><strong>1,634</strong></td><td>33,601</td><td><strong>3,610</strong></td><td>-</td><td><strong>997,846</strong></td></tr><tr><td>3</td><td>1,029,378</td><td><strong>61,179</strong></td><td>2,279</td><td><strong>695</strong></td><td>9,327</td><td><strong>1,028</strong></td><td>-</td><td><strong>315,554</strong></td></tr><tr><td>4</td><td>534,576</td><td><strong>94,970</strong></td><td>1,778</td><td><strong>571</strong></td><td>498</td><td><strong>240</strong></td><td>-</td><td><strong>2,744,744</strong></td></tr><tr><td>5</td><td>40,971,544</td><td><strong>4,562,464</strong></td><td>41,689</td><td><strong>10,925</strong></td><td>67,912</td><td><strong>28,006</strong></td><td>-</td><td><strong>14,073,493</strong></td></tr><tr><td>6</td><td>99,928</td><td><strong>20,639</strong></td><td>1,122</td><td><strong>709</strong></td><td>3,069</td><td><strong>1,019</strong></td><td>-</td><td><strong>138,566</strong></td></tr><tr><td>7</td><td>800,933</td><td><strong>57,562</strong></td><td>1,562</td><td><strong>466</strong></td><td>1,956</td><td><strong>460</strong></td><td>-</td><td><strong>286,485</strong></td></tr><tr><td>8</td><td>1,919,416</td><td><strong>638,323</strong></td><td>4,409</td><td><strong>2,961</strong></td><td>1,165</td><td><strong>758</strong></td><td>-</td><td><strong>3,553,730</strong></td></tr><tr><td>9</td><td>37,142</td><td><strong>3,933</strong></td><td>453</td><td><strong>210</strong></td><td>994</td><td><strong>292</strong></td><td>-</td><td><strong>11,994</strong></td></tr></tbody></table>
optimum. A possibility to avoid a complete exploration of the search space is to
apply a metaheuristic. Many metaheuristics exist [41], ILS is used in our case. As
shown in Table 3a, this approach significantly improved FO-SM-CD's execution
times and reduced the number of nodes traversed especially when the modularity
and density measures are optimized. However, for cut-ratio and conductance, ex-
ecution times worsened, with a marked increase in the number of nodes, leading
to degraded performance.

Table 3b shows that the values obtained by ILS are very close to the optimum, with differences being minimal. In some instances, ILS reaches the optimum, confirming our hypothesis that many inconclusive nodes impact FO-SM-CD's results.

4.3. Diversity of the Partitions wrt. structural Measures

To confirm how interesting it is to provide a flexible framework making it
possible to select and combine different structural measures, possibly with addi-
tional user constraints, the partitions maximizing the different structural measures
are compared. More precisely, we compared the partitions obtained by all metric
pairs using the ARI (Adjusted Rand Index) measure. It is worth recalling that this
measure quantifies the assignment (dis)agreement between two partitions. The
obtained results on the different datasets are aggregated into boxplots illustrated
in Figure 1. We observe that the results for optimal modularity, density, and LOU-
VAIN are quite similar, with very close outcomes. For all other metric pairs, the
node distributions differ, although for conductance and cut-ratio, we find similar
results in some datasets and varying results in others.

Figure 2 provides a more detailed view of the diversity in the results, show-
ing the distribution of communities for each dataset. Table 4 reveals variability in
the community size distribution for each measure, which accounts for the trends
observed in Figure 1 and further emphasizes the relevance of these structural mea-
sures.

Focusing on dataset 6 (see Figures 2a to 2d) illustrates this diversity and
demonstrates that the results align with the semantics of the optimized measures.
Specifically, by minimizing edges between communities, CUT-RATIO and CON-
DUCTANCE tend to form fewer but larger communities. In contrast, by maximiz-
ing internal links, DENSITY avoids this tendency and results in smaller commu-
nities.
<caption>Table 3: *ILS* performances for optimising: *M*₁: MODULARITY, *M*₂: CONDUCTANCE, *M*₃: CUT-RATIO and *M*₄: DENSITY.</caption>

(a) CPU-times and nodes count.

<table><caption>(b) Comparison of the optimal value (1) with the one returned by *ILS* (2).</caption><thead><tr><th rowspan="2">Data ID</th><th colspan="4">CPUTime</th><th colspan="4">#Nodes</th></tr><tr><th>M<sub>1</sub></th><th>M<sub>2</sub></th><th>M<sub>3</sub></th><th>M<sub>4</sub></th><th>M<sub>1</sub></th><th>M<sub>2</sub></th><th>M<sub>3</sub></th><th>M<sub>4</sub></th></tr></thead><tbody><tr><td>1</td><td>13.892</td><td>171.059</td><td>383.389</td><td>31.112</td><td>4.974</td><td>22.703</td><td>62.673</td><td>9.783</td></tr><tr><td>2</td><td>53.41</td><td>108.698</td><td>97.432</td><td>96.561</td><td>15.732</td><td>27.572</td><td>41.608</td><td>20.837</td></tr><tr><td>3</td><td>54.551</td><td>75.553</td><td>55.954</td><td>63.874</td><td>16.051</td><td>27.178</td><td>36.258</td><td>19.778</td></tr><tr><td>4</td><td>16.305</td><td>133.809</td><td>27.032</td><td>33.905</td><td>7.751</td><td>23.370</td><td>8.737</td><td>11.091</td></tr><tr><td>5</td><td>47.403</td><td>171.515</td><td>97.214</td><td>32.589</td><td>18.543</td><td>40.408</td><td>36.287</td><td>18.142</td></tr><tr><td>6</td><td>37.549</td><td>26.35</td><td>20.427</td><td>44.149</td><td>8.402</td><td>2.201</td><td>8.414</td><td>8.988</td></tr><tr><td>7</td><td>20.872</td><td>37.83</td><td>52.507</td><td>20.321</td><td>9.666</td><td>6.122</td><td>44.103</td><td>11.610</td></tr><tr><td>8</td><td>37.805</td><td>45.943</td><td>139.392</td><td>12.856</td><td>18.885</td><td>8.367</td><td>50.259</td><td>7.349</td></tr><tr><td>9</td><td>29.799</td><td>15.466</td><td>22.922</td><td>39.025</td><td>9.603</td><td>1.587</td><td>7.442</td><td>12.194</td></tr></tbody></table>

<table><thead><tr><th rowspan="2">Data ID</th><th colspan="2">M<sub>1</sub></th><th colspan="2">M<sub>2</sub></th><th colspan="2">M<sub>3</sub></th><th colspan="2">M<sub>4</sub></th></tr><tr><th>(1)</th><th>(2)</th><th>(1)</th><th>(2)</th><th>(1)</th><th>(2)</th><th>(1)</th><th>(2)</th></tr></thead><tbody><tr><td>1</td><td><strong>0.3586</strong></td><td>0.2017</td><td><strong>0.3324</strong></td><td>0.5946</td><td><strong>0.1389</strong></td><td>0.1778</td><td><strong>0.0374</strong></td><td>0.0231</td></tr><tr><td>2</td><td><strong>0.3812</strong></td><td>0.3678</td><td><strong>0.325</strong></td><td>0.3852</td><td><strong>0.1143</strong></td><td><strong>0.1143</strong></td><td><strong>0.0391</strong></td><td>0.0314</td></tr><tr><td>3</td><td><strong>0.3846</strong></td><td>0.3725</td><td><strong>0.2732</strong></td><td>0.2909</td><td><strong>0.0952</strong></td><td>0.0995</td><td><strong>0.0394</strong></td><td>0.0343</td></tr><tr><td>4</td><td><strong>0.4317</strong></td><td>0.4118</td><td><strong>0.3337</strong></td><td><strong>0.3337</strong></td><td><strong>0.0588</strong></td><td><strong>0.0588</strong></td><td><strong>0.0437</strong></td><td>0.0357</td></tr><tr><td>5</td><td><strong>0.2764</strong></td><td>0.1793</td><td><strong>0.4762</strong></td><td>0.5952</td><td><strong>0.125</strong></td><td>0.1905</td><td><strong>0.0282</strong></td><td>0.0187</td></tr><tr><td>6</td><td><strong>0.3846</strong></td><td>0.303</td><td><strong>0.3428</strong></td><td><strong>0.3428</strong></td><td><strong>0.1091</strong></td><td><strong>0.1091</strong></td><td><strong>0.0394</strong></td><td>0.0311</td></tr><tr><td>7</td><td><strong>0.316</strong></td><td>0.2304</td><td><strong>0.2954</strong></td><td><strong>0.2954</strong></td><td><strong>0.0833</strong></td><td><strong>0.0833</strong></td><td><strong>0.0328</strong></td><td>0.025</td></tr><tr><td>8</td><td><strong>0.28</strong></td><td>0.2584</td><td><strong>0.3977</strong></td><td><strong>0.3977</strong></td><td><strong>0.1333</strong></td><td><strong>0.1333</strong></td><td><strong>0.0293</strong></td><td>0.025</td></tr><tr><td>9</td><td><strong>0.4723</strong></td><td>0.467</td><td><strong>0.1773</strong></td><td><strong>0.1773</strong></td><td><strong>0.0417</strong></td><td><strong>0.0417</strong></td><td><strong>0.0485</strong></td><td>0.0445</td></tr></tbody></table>
<figure><img src="image_8.png" /><figcaption>Figure 1: Comparison of the community structure: boxplot of the ARI aggregated over the datasets</figcaption></figure>

4.4. *Flexible Configuration*

To mitigate the natural tendencies observed when optimizing structural metrics, additional user constraints can be applied. Figures 2a to 2d illustrate, for each metric, the evolution of the partitions obtained with and without these additional constraints. The inclusion of the *CommunitySize* constraint (Figure 2a) reduced the size of each community, indirectly increasing the number of communities. Similarly, the *MustLink* and *CanNotLink* constraints (Figure 2c) modified the partition generated when density is maximized. Community 2, for instance, was expanded to include nodes 11 and 16 to maximize its internal links. Finally, Figure 2d demonstrates that it is also possible to influence the objective function's value directly, constraining its evolution.

5. Conclusion

In this paper, we presented FO-SM-CD, a Constraint Programming (CP) model designed for constrained community detection. Compared to existing approaches to community detection, FO-SM-CD brings a significant gap in terms of flexibility as it allows to choose and combine different structural measures to optimize. The CP-based model FO-SM-CD also makes it possible to take into
<figure><img src="image_9.png" /><figcaption>(a) CONDUCTANCE: left optimal, right adding (CommunitySize ≤ 3) constraint.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(b) CUT-RATIO: left optimal, right adding (PartitionSize ≥ 4 ∧ CommunitySize ≥ 3) constraints.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>(c) DENSITY: left optimal, right adding (MUST-LINK (3,15) ∧ CANNOT-LINK (6,13)) constraints.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>(d) MODULARITY: left optimal, center adding (PartitionSize = 5 ∧ MODULARITY($\mathcal{X}$) ≤ 0.35) constraint, right LOUVAIN.</figcaption></figure>

<caption>Figure 2: Partitions obtained with different structural measures using DATA-6.</caption>
<table><caption>Table 4: Communities Size Distribution.</caption><thead><tr><th rowspan="2">Data ID</th><th rowspan="2">n</th><th rowspan="2">m</th><th colspan="2">CONDUCTANCE</th><th colspan="2">CUT-RATIO</th><th colspan="2">DENSITY</th><th colspan="2">MODULARITY<br>(optimal)</th><th colspan="2">LOUVAIN</th></tr><tr><th>Size</th><th>Dist.</th><th>Size</th><th>Dist.</th><th>Size</th><th>Dist.</th><th>Size</th><th>Dist.</th><th>Size</th><th>Dist.</th></tr></thead><tbody><tr><td>1</td><td>18</td><td>37</td><td>2</td><td>6,12</td><td>2</td><td>6,12</td><td>4</td><td>5,3,6,4</td><td>4</td><td>5,3,6,4</td><td>4</td><td>6,4,5,3</td></tr><tr><td>2</td><td>17</td><td>26</td><td>2</td><td>10,7</td><td>2</td><td>10,7</td><td>4</td><td>4,6,3,4</td><td>4</td><td>4,6,3,4</td><td>4</td><td>6,6,3,2</td></tr><tr><td>3</td><td>16</td><td>24</td><td>2</td><td>9,7</td><td>2</td><td>9,7</td><td>4</td><td>4,4,3,5</td><td>4</td><td>4,4,3,5</td><td>4</td><td>4,4,3,5</td></tr><tr><td>4</td><td>19</td><td>30</td><td>2</td><td>9,10</td><td>2</td><td>17,2</td><td>4</td><td>6,3,4,6</td><td>4</td><td>6,3,4,6</td><td>4</td><td>6,3,4,6</td></tr><tr><td>5</td><td>17</td><td>35</td><td>2</td><td>12,5</td><td>2</td><td>1,16</td><td>3</td><td>7,5,5</td><td>3</td><td>7,5,5</td><td>3</td><td>8,4,5</td></tr><tr><td>6</td><td>16</td><td>24</td><td>2</td><td>8,8</td><td>2</td><td>5,11</td><td>4</td><td>4,4,5,3</td><td>4</td><td>4,4,5,3</td><td>4</td><td>2,6,5,3</td></tr><tr><td>7</td><td>16</td><td>26</td><td>2</td><td>12,4</td><td>2</td><td>12,4</td><td>4</td><td>3,4,6,3</td><td>4</td><td>3,4,6,3</td><td>4</td><td>3,5,4,4</td></tr><tr><td>8</td><td>16</td><td>35</td><td>2</td><td>6,10</td><td>2</td><td>15,1</td><td>3</td><td>6,6,4</td><td>3</td><td>6,6,4</td><td>3</td><td>6,8,2</td></tr><tr><td>9</td><td>16</td><td>18</td><td>2</td><td>4,12</td><td>2</td><td>4,12</td><td>3</td><td>4,6,6</td><td>4</td><td>4,5,5,2</td><td>4</td><td>4,5,5,2</td></tr></tbody></table>

account user-constraints to control the shape of the expected graph partition. Experiments have first confirmed the relevance of considering different structural measures when partitioning a graph as they exhibit different structural patterns. The connectedness constraint combined with the ILS metaheuristic significantly reduces the size of the search space and outperforms other related approaches in terms of computational cost.

This paper clearly shows that incorporating structural measures beyond modularity allows for more varied, insightful community structures. Combining CP's flexibility with search heuristics like ILS offers a robust framework for community detection. While FO-SM-CD is a clear improvement in terms of flexibility, CP-based approaches still suffer of a lack of efficiency when applied on large graphs. Despite a clear improvement of flexibility and efficiency, compared to other CP-based approaches, scalability remains challenging. Future work could introduce monotonic or anti-monotonic constraints to filter inconclusive solutions more effectively and improve scalability. Additionally, exploring hybrid methods combining CP with optimization techniques like machine learning could enhance community detection capabilities.

## References

[1] V. L. Dao, C. Bothorel, P. Lenca, Community structure: A comparative evaluation of community detection methods, Network Science 8 (1) (2020) 1–41.

[2] S. Fortunato, Community detection in graphs, Physics reports 486 (3-5) (2010) 75–174.
[3] G. Rossetti, R. Cazabet, Community discovery in dynamic networks: a survey, ACM computing surveys (CSUR) 51 (2) (2018) 1–37.

[4] V. Dao, Characterizing community detection algorithms and detected modules in large-scale complex networks. (évaluation de structures de commutautés), Ph.D. thesis, IMT Atlantique, Lab-STICC CNRS, Brest, France (2018).
URL https://tel.archives-ouvertes.fr/tel-02121358

[5] M. E. J. Newman, M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E 69 (2004) 026113.
doi:10.1103/PhysRevE.69.026113.
URL https://link.aps.org/doi/10.1103/PhysRevE.69.026113

[6] F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, D. Parisi, Defining and identifying communities in networks, Proceedings of the National Academy of Sciences of the United States of America 101 (2004) 2658–63. doi: 10.1073/pnas.0400054101.

[7] A. Clauset, M. E. J. Newman, C. Moore, Finding community structure in very large networks, Phys. Rev. E 70 (2004) 066111.
doi:10.1103/PhysRevE.70.066111.
URL https://link.aps.org/doi/10.1103/PhysRevE.70.066111

[8] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, E. Lefebvre, Fast unfolding of communities in large networks, Journal of Statistical Mechanics: Theory and Experiment 2008 (10) (2008) P10008.
doi:10.1088/1742-5468/2008/10/P10008.
URL https://dx.doi.org/10.1088/1742-5468/2008/10/P10008

[9] M. E. J. Newman, Modularity and community structure in networks, Proceedings of the National Academy of Sciences 103 (23) (2006) 8577–8582.
arXiv:https://www.pnas.org/doi/pdf/10.1073/pnas.0601602103, doi:10.1073/pnas.0601602103.
URL https://www.pnas.org/doi/abs/10.1073/pnas.0601602103
[10] U. N. Raghavan, R. Albert, S. R. T. Kumara, Near linear time algorithm to detect community structures in large-scale networks., Physical review. E, Statistical, nonlinear, and soft matter physics 76 3 Pt 2 (2007) 036106.
URL https://api.semanticscholar.org/CorpusID:18741059

[11] A. Lancichinetti, F. Radicchi, J. J. Ramasco, S. Fortunato, Finding statistically significant communities in networks, PLOS ONE 6 (4) (2011) 1–18.
doi:10.1371/journal.pone.0018961.
URL https://doi.org/10.1371/journal.pone.0018961

[12] M. A. Riolo, G. T. Cantwell, G. Reinert, M. E. J. Newman, Efficient method for estimating the number of communities in a network, Phys. Rev. E 96 (2017) 032310. doi:10.1103/PhysRevE.96.032310.
URL https://link.aps.org/doi/10.1103/PhysRevE.96.032310

[13] M. Rosvall, C. T. Bergstrom, Maps of random walks on complex networks reveal community structure, Proceedings of the National Academy of Sciences 105 (2007) 1118–1123.
URL https://api.semanticscholar.org/CorpusID:15478415

[14] G. K. Orman, V. Labatut, H. Cherifi, Comparative evaluation of community detection algorithms: A topological approach, CoRR abs/1206.4987 (2012).
arXiv:1206.4987.
URL http://arxiv.org/abs/1206.4987

[15] L. Danon, A. Diaz-Guilera, A. Arenas, The effect of size heterogeneity on community identification in complex networks, Journal of Statistical Mechanics: Theory and Experiment 2006 (11) (2006) P11010.

[16] W. M. Rand, Objective criteria for the evaluation of clustering methods, Journal of the American Statistical association 66 (336) (1971) 846–850.

[17] M. Girvan, M. Newman, Community structure in social and biological networks, Proceedings of the National Academy of Sciences of the United States of America 99 (12) (2002) 7821–7826. doi:10.1073/pnas.122653799.
[18] M. Cordeiro, R. P. Sarmento, J. Gama, Dynamic community detection in evolving networks using locality modularity optimization, Social Network Analysis and Mining 6 (2016) 1–20.

[19] M. J. Brusco, D. Steinley, A. L. Watts, On maximization of the modularity index in network psychometrics, Behavior Research Methods 55 (7) (2023) 3549–3565.

[20] M. Ganji, J. Bailey, P. J. Stuckey, A declarative approach to constrained community detection, in: J. C. Beck (Ed.), Principles and Practice of Constraint Programming - 23rd International Conference, CP 2017, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings, Vol. 10416 of Lecture Notes in Computer Science, Springer, 2017, pp. 477–494.
doi:10.1007/978-3-319-66158-2_31.
URL https://doi.org/10.1007/978-3-319-66158-2_31

[21] L. H. N. Lorena, M. G. Quiles, L. A. N. Lorena, Improving the performance of an integer linear programming community detection algorithm through clique filtering, in: S. Misra, O. Gervasi, B. Murgante, E. N. Stankova, V. Korkhov, C. M. Torre, A. M. A. C. Rocha, D. Taniar, B. O. Apduhan, E. Tarantino (Eds.), Computational Science and Its Applications - ICCSA 2019 - 19th International Conference, Saint Petersburg, Russia, July 1-4, 2019, Proceedings, Part I, Vol. 11619 of Lecture Notes in Computer Science, Springer, 2019, pp. 757–769.
doi:10.1007/978-3-030-24289-3_56.
URL https://doi.org/10.1007/978-3-030-24289-3_56

[22] S. Srinivas, C. Rajendran, Community detection and influential node identification in complex networks using mathematical programming, Expert Syst. Appl. 135 (2019) 296–312.
doi:10.1016/j.eswa.2019.05.059.
URL https://doi.org/10.1016/j.eswa.2019.05.059

[23] A. Belyi, S. Sobolevsky, Network size reduction preserving optimal modularity and clique partition, in: O. Gervasi, B. Murgante, E. M. T. Hendrix, D. Taniar, B. O. Apduhan (Eds.), Computational Science and Its Applications - ICCSA 2022 - 22nd International Conference, Malaga, Spain, July 4-7, 2022, Proceedings, Part I, Vol. 13375 of Lecture Notes in Computer Science, Springer, 2022, pp. 19–33.
doi:10.1007/978-3-031-10522-7_2.
URL https://doi.org/10.1007/978-3-031-10522-7_2
[24] D. Heymann, C. Schwantes, V. Pavon-Harr, I. McCulloh, Methods in con-
strained community detection: An integer optimization model and heuristic
approach for cohort creation, in: 2021 Eighth International Conference on
Social Network Analysis, Management and Security (SNAMS), IEEE, 2021,
pp. 1–8.

[25] Z. Lu, J. Wahlström, A. Nehorai, Community detection in complex networks
via clique conductance, Scientific reports 8 (1) (2018) 5982.

[26] Z. Lu, J.-K. Hao, Q. Wu, A hybrid evolutionary algorithm for finding low conductance of large graphs, Future Generation Computer Systems 106 (2020) 105–120.

[27] S. Fortunato, M. Barthélemy, Resolution limit in community detection,
Proceedings of the National Academy of Sciences 104 (1) (2007) 36–41.
arXiv:https://www.pnas.org/doi/pdf/10.1073/pnas.
0605965104, doi:10.1073/pnas.0605965104.
URL https://www.pnas.org/doi/abs/10.1073/pnas.
0605965104

[28] M. Ciglan, K. Nørvåg, Fast detection of size-constrained communities in large networks, in: Proceedings of the 11th International Conference on Web Information Systems Engineering, WISE’10, Springer, 2010, p. 91–104.

[29] T. Guns, S. Nijssen, L. De Raedt, Itemset mining: A constraint programming perspective, Artificial Intelligence 175 (12-13) (2011) 1951–1983.

[30] S. Gilpin, I. Davidson, Incorporating sat solvers into hierarchical clustering algorithms: an efficient and flexible approach, in: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, 2011, pp. 1136–1144.

[31] A. Ouali, S. Loudni, Y. Lebbah, P. Boizumault, A. Zimmermann, L. Loukil, Efficiently finding conceptual clustering models with integer linear programming, in: S. Kambhampati (Ed.), Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, IJCAI/AAAI Press, 2016, pp. 647–654.
URL http://www.ijcai.org/Abstract/16/098
[32] G. Agarwal, D. Kempe, Modularity-maximizing graph communities via mathematical programming, The European Physical Journal B 66 (2008) 409–418.

[33] S. Jabbour, N. Mhadhibi, B. Raddaoui, L. Saïs, Finding overlapping communities in networks using propositional satisfiability, in: EDA 2017: Journées francophones sur les Entrepôts de Données et l'Analyse en Ligne, Business Intelligence & Big Data, Editions RNTI, 2017, pp. 67–80.

[34] A. A. Hagberg, D. A. Schult, P. Swart, J. Hagberg, Exploring network structure, dynamics, and function using networkx, Proceedings of the Python in Science Conference (2008).
URL https://api.semanticscholar.org/CorpusID:16050699

[35] A. Lancichinetti, M. Kivelä, J. Saramäki, S. Fortunato, Characterizing the community structure of complex networks, PLoS ONE 5 (2010).
URL https://api.semanticscholar.org/CorpusID:623333

[36] F. Rossi, P. van Beek, T. Walsh (Eds.), Handbook of Constraint Programming, Vol. 2 of Foundations of Artificial Intelligence, Elsevier, 2006.
URL https://www.sciencedirect.com/science/bookseries/15746526/2

[37] E. C. Freuder, A. K. Mackworth, Constraint satisfaction: An emerging paradigm, in: F. Rossi, P. van Beek, T. Walsh (Eds.), Handbook of Constraint Programming, Vol. 2 of Foundations of Artificial Intelligence, Elsevier, 2006, pp. 13–27.
doi:10.1016/S1574-6526(06)80006-4.
URL https://doi.org/10.1016/S1574-6526(06)80006-4

[38] H. R. Lourenço, O. C. Martin, T. Stützle, Iterated local search, in: Handbook of metaheuristics, Springer, 2003, pp. 320–353.
doi:10.1007/0-306-48056-5_11.
URL https://doi.org/10.1007/0-306-48056-5_11

[39] Y. C. Law, J. H. Lee, Global constraints for integer and set value precedence, in: Principles and Practice of Constraint Programming–CP 2004: 10th International Conference, CP 2004, Toronto, Canada, September 27-October 1, 2004. Proceedings 10, Springer, 2004, pp. 362–376.
[40] C. Prud'homme, J.-G. Fages, X. Lorca, Choco solver documentation, TASC, INRIA Rennes, LINA CNRS UMR 6241 (2016) 13-42.

[41] S. T. W. Mara, R. Norcahyo, P. Jodiawan, L. Lusiantoro, A. P. Rifai, A survey of adaptive large neighborhood search algorithms and applications, Computers & Operations Research 146 (2022) 105903.