Sonia Cafieri
email: sonia.cafieri@enac.fr

Pierre Hansen
email: pierre.hansen@gerad.ca

Leo Liberti
email: liberti@lix.polytechnique.fr

Improving heuristics for network modularity maximization using an exact algorithm

Keywords: clustering, bipartition, network, graph, community, modularity, heuristic, exact algorithm, matheuristic

Heuristics are widely applied to modularity maximization models for the identification of communities in complex networks. We present an approach to be applied as a post-processing to heuristic methods in order to improve their performances. Starting from a given partition, we test with an exact algorithm for bipartitioning if it is worthwhile to split some communities or to merge two of them. A combination of merge and split actions is also performed. Computational experiments show that the proposed approach is effective in improving heuristic results.

Introduction

The identification of communities in complex networks has become in recent years a very active research domain [START_REF] Newman | Networks: an introduction[END_REF][START_REF] Fortunato | Community detection in graphs[END_REF] because of the common representation of complex real-world systems arising in a variety of fields as networks. One then aims to find communities, or clusters, of entities grouped on the basis of some relationship holding among them. Telecommunication networks such as the World Wide Web, biological networks representing interactions between proteins and social networks representing collaborations or conflicts between people or countries are some examples of real-life applications (see [START_REF] Newman | Networks: an introduction[END_REF] for a detailed introduction).

Intuitively, one would say that a set of vertices of a network form a community if edges joining two vertices of that set are frequent and edges joining a vertex of that set to a vertex outside are not. This concept has been refined in many ways, leading to the introduction of concepts of modularity [START_REF] Newman | Finding and evaluating community structure in networks[END_REF], modularity density [START_REF] Li | Quantitative function for community detection[END_REF], min-max cut [START_REF] Ding | A min-max cut algorithm for graph partitioning and data clustering[END_REF], normalized cut [START_REF] Shi | Normalized cuts and image segmentation[END_REF] and others. Among these concepts, modularity is by far the most popular.

Modularity of a community is defined in [START_REF] Newman | Finding and evaluating community structure in networks[END_REF] as the difference between the fraction of edges it contains and the expected fraction of edges it would contain if they were placed at random, keeping the same degree distribution. Then, modularity of a partition of a network into communities is defined as the sum of the modularities of these communities. Modularity expresses not only that a community contains a large fraction of the edges, but also that it contains a larger fraction of the edges than would be expected. It can be viewed as a measure of the extent to which the classes of a partition of a graph can be considered to be communities. Alternatively, modularity can be maximized to find an optimal partition of a network.

Modularity maximization has spawned in recent years numerous methods for cluster identification in networks. Despite its popularity, the accuracy and the significance of modularity maximizing modules are not well understood for real-world networks [START_REF] Good | The performance of modularity maximization in practical contexts[END_REF]. Furthermore, some criticism have been raised in recent literature, see, e.g., [START_REF] Good | The performance of modularity maximization in practical contexts[END_REF][START_REF] Fortunato | Resolution limit in community detection[END_REF][START_REF] Cafieri | Loops and multiple edges in modularity maximization of networks[END_REF][START_REF] Massen | Identifying communities within energy landscapes[END_REF][START_REF] Lancichinetti | Limits of modularity maximization in community detection[END_REF]. The two main concerns are the existence of a resolution limit and the fact that modularity function exhibits a degeneracy. The resolution limit, identified by Fortunato and Barthelemy [START_REF] Fortunato | Resolution limit in community detection[END_REF], implies that, in the presence of large clusters, some clusters smaller than a certain size which depends on the number of edges of the network can be undetectable. As a consequence, modular structures like small cliques can be hidden in larger clusters. This effect appears to be driven primarly by the assumption that inter-module connectivity follows a random graph model [START_REF] Good | The performance of modularity maximization in practical contexts[END_REF]. Degeneracy (see [START_REF] Good | The performance of modularity maximization in practical contexts[END_REF]) implies that there can be a large number of partitions, even very different from each other, having high modularity values. This makes it easy to find high-scoring partitions but difficult to identify the global optimum. To address these criticisms a few approaches have been proposed. Sales-Pardo et al. [START_REF] Sales-Pardo | Extracting the hierarchical organization of complex systems[END_REF] address the problem of degenearcy combining information from many distinct partitions with high modularity. Multires-olution methods [START_REF] Kumpula | Limited resolution and multiresolution methods in complex network community detection[END_REF][START_REF] Arenas | Analysis of the structure of complex networks at different resolution levels[END_REF][START_REF] Reichardt | Statistical mechanics of community detection[END_REF] allow to specify a target resolution limit and identify clusters on such given scale, though they do not solve the problem in a fully satisfactory manner. Despite these criticisms, modularity maximization still appears to be a very popular technique for network clustering. It exhibits, in fact, some clear advantages: modularity function has a clear and simple mathematical description and does not depend on parameters being decided arbitrarily (as an example, maximizing the number of intracluster edges requires some other parameter, e.g. the minimum cluster size); modularity maximization gives an optimal partition together with the number of clusters not to be specified in advance. Interestingly, one can use mathematical programming to model the community detection problem and, using modularity maximization, the splitting of a cluster into two can be expressed as a quadratic programming problem. This paper discusses such a formulations and exploits it within a procedure used as a refinement of previously computed partitions.

Numerous heuristics and a few algorithms have been proposed to find near optimal or optimal partitions respectively for the maximum modularity criterion. Heuristics are either partitioning methods or hierarchical divisive or agglomerative ones. Partitioning heuristics are based on simulated annealing [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF][START_REF] Massen | Identifying communities within energy landscapes[END_REF][START_REF] Medus | Detection of community structures in networks via global optimization[END_REF], mean field annealing [START_REF] Lehmann | Deterministic modularity optimization[END_REF], genetic search [START_REF] Tasgin | Community detection in complex networks using genetic algorithms[END_REF], extremal optimization [START_REF] Duch | Community identification using extremal optimization[END_REF], spectral clustering [START_REF] Newman | Modularity and community structure in networks[END_REF], linear programming followed by randomized rounding [START_REF] Agarwal | Modularity-maximizing graph communities via mathematical programming[END_REF], dynamical clustering [START_REF] Boccaletti | Detecting complex network modularity by dynamical clustering[END_REF], multilevel partitioning [START_REF] Djidjev | A scalable multilevel algorithm for graph clustering and community structure detection[END_REF], contraction-dilation [START_REF] Mei | Revealing network communities through modularity maximization by a contraction-dilation method[END_REF], quantum mechanics [START_REF] Niu | Detecting the community structure in complex networks based on quantum mechanics[END_REF] and several other approaches [27, 28? , 29, 30, 13]. Agglomerative hierarchical clustering [START_REF] Newman | Fast algorithm for detecting community structure in networks[END_REF][START_REF] Clauset | Finding community structure in very large networks[END_REF][START_REF] Danon | The effect of size heterogeneity on community identification in complex networks[END_REF][START_REF] Wakita | Finding community structure in mega-scale social networks[END_REF][START_REF] Blondel | Fast unfolding of communities in large networks[END_REF] proceeds from an initial partitions into communities each containing a single vertex to merging sequentially vertices or sets of vertices corresponding to communities. In [START_REF] Schuetz | Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement[END_REF] this approach is combined with a vertex mover routine which improves the partitions by changing the community of a vertex to that of one of its adjacent vertices. Divisive hierarchical clustering proceeds from an initial trivial partition in one community containing all vertices and sequentially selects a community and proceeds to its bipartitioning. Divisive heuristics are much less frequent than agglomerative ones. The best known of them is Newman's spectral heuristic [START_REF] Newman | Modularity and community structure in networks[END_REF], which uses the signs of the first eigenvector of the modularity matrix to perform successive bipartitions. In a companion paper [START_REF] Cafieri | Locally optimal heuristic for modularity maximization of networks[END_REF], we propose a hierarchical divisive heuristic which is locally optimal, i.e., in which all successive bipartitions are done in an optimal way.

These heuristics are able to solve large instances with up to thousand or tens of thousands of vertices (and sometimes over a million) and therefore are often preferred to exact algorithms, even though they do not have a guarantee of optimality. Only a few papers propose exact algorithms for maximizing modularity. The first one, due to Xu et al. [START_REF] Xu | Finding community structures in complex networks using mixed integer optimization[END_REF], uses quadratic mixed-integer programming with a convex relaxation. Networks with up to 104 vertices were addressed successfully. Brandes et al. [START_REF] Brandes | On modularity clustering[END_REF] have shown that modularity maximization is NP-hard, even if there are only two communities. In addition, they propose to express modularity maximization as a clique partitioning problem. They maximize modularity of networks with up to 105 vertices. Their algorithm is close to that one of Grötschel and Wakabayashi [START_REF] Grötschel | A cutting plane algorithm for a clustering problem[END_REF][START_REF] Grötschel | Facets of the clique partitioning polytope[END_REF]. Aloise et al. [START_REF] Aloise | Column generation algorithms for exact modularity maximization in networks[END_REF] apply column generation to modularity maximization and solve exactly instances with up to 512 vertices. Given a partition found by a heuristic, one can apply another heuristic or an exact algorithm to the subnetworks induced by the communities found. This will eventually lead to a new, better, partition. Moreover, this refinement can be based on splitting a community or merging a pair of communities. In the spirit of matheuristics, an exact algorithm for bipartition is applied in our approach first to the communities considered one at a time, then merging pairs of communities and applying again the bipartition algorithm.

We employ our approach as post-processing of some known heuristics for modularity maximization, obtaining improved solutions and, for some datasets, the optimal partition.

The paper is organized as follows. In the next section, the proposed approach to improve heuristic results for modularity maximization is described, presenting in particular an exact algorithm for bipartition. Section 3 presents the results of computational experiments carried out applying the proposed approach as post-processing to three of the best heuristics available for modularity maximization of networks, i.e., the agglomerative hierarchical heuristic of Clauset et al. [START_REF] Clauset | Finding community structure in very large networks[END_REF], the partitioning heuristic of Noack and Rotta [START_REF] Noack | Multi-level algorithms for modularity clustering[END_REF] and the multistep greedy with vertex move heuristic of Schuetz and Caflisch [START_REF] Schuetz | Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement[END_REF]. We also apply this approach to the locally optimal divisive hierarchical heuristic of [START_REF] Cafieri | Locally optimal heuristic for modularity maximization of networks[END_REF]. Conclusions are given in Section 4.

Improving heuristics for modularity maximization

An exact algorithm for bipartition

We present in this section an exact algorithm for modularity maximizing bipartition of networks. Although it can be applied in full generality to any graph, we specifically apply it in the role of post-processing step to heuristics for the identification of communities in networks.

We model this bipartitioning problem using binary variables to identify to which community each vertex and each edge belongs. In this respect, our model is similar to that of Xu et al. [START_REF] Xu | Finding community structures in complex networks using mixed integer optimization[END_REF]. These authors proposed in 2007 [START_REF] Xu | Finding community structures in complex networks using mixed integer optimization[END_REF] a model for modularity maximization of networks which leads to an optimal partition generally with more than two communities. Their model is a mixed-integer quadratic program with a convex relaxation.

Let G = (V, E) be a graph, or network, with vertex set V of cardinality n and edge set E of of cardinality m. First, we recall the definition of modularity Q as a sum over communities of their modularities [START_REF] Newman | Finding and evaluating community structure in networks[END_REF]:

Q = s [a s -e s ],
where a s is the fraction of all edges that lie within community s, and e s is the expected value of the same quantity in a graph in which the vertices have the same degrees but edges are placed at random. Modularity can then be written equivalently as:

Q = s m s m - d s 2m 2 , (1)
where m s denotes the number of edges in community s, i.e., which belong to the subgraph induced by the vertex set V s of that community, and d s denotes the sum of degrees k i of the vertices of community s. Since we aim to find a bipartition, only two sub-modules of the original community have to be considered, i.e. s ∈ {1, 2}. We can express the sum of degrees d 2 of vertices belonging to the second community as a function of the sum of degrees d 1 of vertices belonging to the first one:

d 2 = d t -d 1 , (2)
where d t is the sum of degrees in the community to be bipartitioned. It is equal to 2m at the first iteration. We rewrite (1) for s ∈ {1, 2}, using (2):

Q = m 1 + m 2 m - d 2 1 4m 2 - d 2 2 4m 2 = = m 1 + m 2 m - d 2 1 4m 2 - d 2 t + d 2 1 -2d t d 1 4m 2 = = m 1 + m 2 m - d 2 1 2m 2 - d 2 t 4m 2 + d t d 1 2m 2 .
(

) 3
We then introduce binary variables X r1 , X r2 and Y i1 to model assignment of vertices and edges to the two communities of the bipartition. These variables are defined as follows:

X rs = 1 if edge r belongs to community s 0 otherwise (4)
for r = 1, 2, . . . m and s = 1, 2 and

Y i1 = 1 if vertex i belongs to community 1 0 otherwise, i.e., vertex i belongs to community 2 (5)
for i = 1, 2, . . . n.

We impose that any edge r = {v i , v j } with end vertices indiced by i and j can only belong to community s if both of its end vertices belong also to that community:

X r1 ≤ Y i1 ∀r = {v i , v j } ∈ E X r1 ≤ Y j1 ∀r = {v i , v j } ∈ E (6)
and

X r2 ≤ 1 -Y i1 ∀r = {v i , v j } ∈ E X r2 ≤ 1 -Y j1 ∀r = {v i , v j } ∈ E . (7)
Furthermore, we exploit the following expressions in terms of variables X r1 , X r2 , r = 1, 2, . . . m, and Y i1 , i = 1, 2, . . . n, for the number of edges of each of the two communities and the sum of vertex degrees of the first one:

m s = r X rs ∀s ∈ {1, 2}, (8)
d 1 = i∈V 1 k i Y i1 . (9)
Only the sum of vertex degrees of the first community is exploited, because of expression [START_REF] Fortunato | Community detection in graphs[END_REF].

We then have the following integrality constraints on the variables:

X rs ∈ {0, 1} ∀r = {v i , v j } ∈ E, ∀s ∈ {1, 2} Y i1 ∈ {0, 1} ∀i ∈ {1, . . . , n} m 1 , m 2 , d 1 ∈ N + . ( 10
)
Maximizing modularity (3) subject to constraints ( 6)-( 7) and ( 8)-( 9) and replacing the integrality constraints [START_REF] Massen | Identifying communities within energy landscapes[END_REF] by range constraints gives a quadratic mixed-integer program with a convex relaxation which can be solved by recent versions of CPLEX [START_REF]ILOG CPLEX 12.2 User's Manual[END_REF]. This model has 2m + n + 3 variables and 4m + 3 constraints. For sparse networks, as is the case in many applications, these sizes are reasonable.

Improving a partition by merging and splitting

The proposed post-processing heuristic aims at improving the modularity of a given partition obtained with some heuristic. A new partition is obtained in a sequence of steps, which act on the current communities by splitting and merging.

First, we split each community of the original partition into two subcommunities by applying the exact algorithm for bipartition described in subsection 2.1. We then check if the modularity value corresponding to the obtained bipartition is higher than the one of the original community. This comparison is justified by the definition of modularity of a partition as sum of modularities of its communities. If the new modularity value is higher than that one of the original community, this community is replaced by the two new communities. Otherwise the two obtained communities are discarded and the original one is kept. When all the original communities have been checked, a new partition is obtained with a higher modularity than before if at least one bipartition has been accepted.

Second, we merge provisionally pairs of communities and check if this induces an increased value for modularity. For each pair of communities, we consider the new community containing all vertices of this pair and check if the larger community has a modularity value higher than the sum of the modularities of the two original communities. If this is the case, the new large community is kept in place of the other two. Otherwise, if merge is not beneficial, we try to split the merged community using again the exact algorithm presented in subsection 2.1. As before, the two communities resulting from the bipartition are kept if the sum of their modularities is higher than the modularity of the splitted community. Obviously, pairs of clusters to be merged can be selected according to different criteria. We compute the number of edges joining pairs of clusters, that is the number of edges joining vertices belonging to the first cluster of the pair with vertices belonging to the second cluster. Then, the pairs are sorted by decreasing number of joining links. This gives the list of pairs of clusters to be considered for merging. In this way, we first attempt to improve the current partition by merging clusters which are more strongly connected than others, so that a merging can be expected to be beneficial.

A sketch of our algorithm is given in Alg. 1.

Computational results

We apply our approach as a post-processing heuristic to three known heuristics due to Clauset, Newman and Moore [START_REF] Clauset | Finding community structure in very large networks[END_REF], Noack and Rotta [START_REF] Noack | Multi-level algorithms for modularity clustering[END_REF] and Schuetz and Caflisch [START_REF] Schuetz | Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement[END_REF]. We also apply it to the locally optimal divisive hierarchical heuristic of [START_REF] Cafieri | Locally optimal heuristic for modularity maximization of networks[END_REF]. Clauset et al. [START_REF] Clauset | Finding community structure in very large networks[END_REF] proposed in 2004 an efficient implementation of an agglomerative hierarchical scheme, that for sparse networks has a very low complexity and is considerably faster than previously proposed methods. Noack and Rotta [START_REF] Noack | Multi-level algorithms for modularity clustering[END_REF] presented in 2008 a comparison of heuristics for modularity maximization and proposed a heuristic based on a single-step coarsening with a multi-level refinement, which is competitive with other methods in the literature. Schuetz and Caflisch [START_REF] Schuetz | Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement[END_REF] introduced in 2008 a multistep extension of the greedy heuristic and combined it with a vertex-by-vertex refinement procedure, called vertex mover. Their main idea is to promote simultaneous merging of several pairs of communities. Moreover, the vertex mover acts as an efficient ascent heuristic, used repetitively. The present authors proposed in 2011 a hierarchical divisive heuristic where bipartitions are done exactly using the model of Section 2.

Our computational results have been obtained on some datasets that are often used to evaluate heuristics and algorithms for identification of communities in networks. These datasets correspond to various real-life applications: a social network of dolphins described by Lusseau [START_REF] Lusseau | The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Can geographic isolation explain this unique trait?[END_REF], a network describing interactions among the characters of Hugo's novel Les Misérables [START_REF] Knuth | The Stanford GraphBase: A Platform for Combinatorial Computing[END_REF], a network dealing with protein-protein interactions [START_REF] Dartnell | Self-similar community structure in a network of human interactions[END_REF], a network recording co-purchasing of political books on Amazon.com [47], a network represent-ing the schedule of games between American college football teams in the Fall of 2000 [START_REF] Girvan | Community structure in social and biological networks[END_REF], a network dealing with connections between US airports [49], a network describing electronic circuits [50], a network representing email interchanges between members of a university [START_REF] Guimerà | Selfsimilar community structure in a network of human interactions[END_REF], a network giving the topology of the Western States Power Grid of the United States [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF] and a network of authors collaborations [49].

In our implementation, the quadratic mixed-integer program with a convex relaxation which models the modularity maximizing bipartition problem is solved using CPLEX 12.2 [START_REF]ILOG CPLEX 12.2 User's Manual[END_REF], with the following parameters: the MIP cutting plane generation is disabled, the branching variable selection strategy is based on reduced pseudo costs, the number of nodes in the Branch-and-Bound tree is limited to 40000, and 1 only thread is used.

In Table 1 we report, for each dataset, the values of modularity computed by the four considered heuristics and by the proposed approach when applied as post-processing to the partitions obtained with these heuristics, together with the optimal value of modularity, when available in the literature. The number of vertices n and the number of edges m of the datasets are also reported.

It appears that:

• the best result obtained with the four heuristics and our proposed postprocessing approach is optimal 4 cases out of the 8 for which an optimal value is known.

• However, for the four cases in which the optimal solution could not be found, the error between the optimal value and the best value found by one of the heuristics appears to be very moderate, i.e., 0.00011 or 0.021% for p53 protein and 0.000016 or 0.043% for usair97, 0.000022 or 0.026% for netscience main and 0.00265 or 0.32% for s838.

• The proposed approach is very efficient in the sense that it improved the values given by the heuristics in all cases for all of them, except for les miserables for which the optimal solution was already obtained by Noack and Rotta's and Schuetz and Caflisch's heuristics.

• After post-processing, the Noack and Rotta's heuristic gives the best results in 8 cases over 11, the Schuetz and Caflish's heuristic in 4 cases over 11, which are a subset of the 8 cases solved by the Noack and Rotta's heuristic, the Clauset et al.'s heuristic found the best solution in 2 cases out of 11, i.e., political books (for which it was also obtained by the Noack and Rotta's and the Schuetz and Caflish's heuristics) and erdos02. Finally, the best solution after post-processing was found by the locally optimal divisive heuristic in 2 cases, i.e., s838 and power.

• The average value of modularity for the Clauset et al.'s heuristic over 11 problems is 0.616975 before post-processing and 0.634178 after postprocessing, the average improvement is 0.0172027 and the corresponding percentage of increase in modularity is 2.78824%. The average value of modularity for the Noack and Rotta's heuristic over 11 problems is 0.640711 before post-processing and 0.643135 after post-processing, the average improvement is 0.0024245 and the corresponding percentage of increase in modularity is 0.378415%. The average value of modularity for the Schuetz and Caflisch's heuristic over 11 problems is 0.640084 before post-processing and 0.643521 after post-processing, the average improvement is 0.0034373 and the corresponding percentage of increase in modularity is 0.537004%. Average value of modularity for the Cafieri et al.'s heuristic over 9 problems is 0.632559 before postprocessing and 0.633466 after post-processing, the average improvement is 0.000906667 and the corresponding percentage of increase in modularity is 0.143333%.

The approach proposed in the present paper is based on two main steps, which are applied sequentially. We call these steps split and merge+split for short. In order to evaluate the impact of the two steps, we report in Tables 2 and3 the modularity values obtained applying split and merge+split starting from Clauset et al.'s (CNM) solution and Noack-Rotta's (NR) solution for the first table and starting from Schuetz and Caflisch's (SC) solution and from Cafieri et al.'s (CHL) solution for the second table respectively. Note that modularity values for merge+split are the final results provided by our moves, already shown in Table 1. These results show that the splitting step provides in most cases a significant improvement of the original partition. Examples are given by dolphin, political books, football, usair97, netscience main and email datasets (that is, 6 cases out of 11) for CNM and by p53 protein dataset for SC, where an improvement on the second decimal digit of modularity value is obtained. Furthermore, the splitting step provides the optimal solution of political books dataset for NR and of political books and football datasets for SC. By contrast, this step does not provide for some instances a better partition [START_REF] Noack | Multi-level algorithms for modularity clustering[END_REF], Schuetz and Caflisch [START_REF] Schuetz | Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement[END_REF] and Cafieri et al. [START_REF] Cafieri | Locally optimal heuristic for modularity maximization of networks[END_REF]. Q ′ , Q ′′ , Q ′′′ , Q iv are modularities computed applying the proposed approach to the partitions obtained by these heuristics. Q opt are the optimal modularity values as reported in the literature. n and m are the number of vertices and the number of edges of the networks.

dataset n m Q CNM Q ′ Q NR Q ′′ Q SC Q ′′′ Q CHL Q iv Qopt
than the original one, leading to an unchanged modularity value. Examples are given by erdos02 dataset for CNM, by p53 protein, usair97, s838 and erdos02 datasets for NR, and by usair97 and erdos02 datasets for SC. The splitting step never improves solutions found by the fourth heuristic CHL, as expected being the splitting step of that divisive heuristic already performed by using the exact algorithm of Section 2.1. This behavior shows the importance of a combined use of both splitting and merging steps in the proposed approach to obtain eventually a new, better, partition. Table 4 shows computing time required by our post-processing strategy applied to the four considered heuristics to get an improved solution. Results have been obtained on a 2.4 GHz Intel Xeon CPU of a computer with 8GB RAM shared by three other similar CPU running Linux. As expected, times are roughly increasing with network dimension, even though they depend mostly on the quality of the initial partition and the cardinality of its communities to be handled. Times are in general reasonably moderate, and very short times are spent on most of the tested networks. The optimal partition is found in less than 1 second for dolphin dataset and in less than 4 seconds for football dataset starting from NR and SC solutions and in less than 4.30 seconds and slightly more than 5 seconds respectively for political books starting from CNM, NR and SC solutions.

dataset CNM NR Q CNM Q ′ split Q ′ merge+split Q NR Q ′′ split Q ′′ merge+split dolphin 0.
dataset SC CHL Q SC Q ′′′ split Q ′′′ merge+split Q CHL Q iv split Q iv merge+split dolphin 0

Conclusion

This paper describes the application of an approach based on an exact algorithm for bipartitioning a network, in the framework of split and merge movements on communities of a network partition. Computational results obtained on a set of examples from the literature, applying the proposed approach as post-processing to four heuristics for modularity maximization of networks, show the impact of an exact approach on the improvement of heuristic results.

The presented approach can be easily applied in full generality to any modularity maximization based heuristic to improve the quality of the partition provided by the heuristic.

It has been succesfully exploited to develop a hierarchical divisive clustering heuristic which is locally optimal [START_REF] Cafieri | Locally optimal heuristic for modularity maximization of networks[END_REF] and may be further developed including the described moves directly in a local search heuristic. split CL i into CL 1 , CL 2 using algorithm in subsection 2.1

Algorithm 1 1 :

 1 /* ncl = number of communities of the partition found by a heuristic */ 2: /* CL i = community of the partition found by a heuristic, ∀i = {1, . . . , ncl} */ Require: V, E, ncl, CL i ∀i = {1, . . . , ncl} 3: ncl split ← 0 4: for all i ≤ ncl do 5:

Table 1 :

 1 Results on real-world datasets: comparison between the modularity values found by heuristics and by the proposed approach applied as post-processing. Q CNM , Q NR , Q SC and Q CHL are modularities computed using heuristics by Clauset et al.[START_REF] Clauset | Finding community structure in very large networks[END_REF], Noack and Rotta

	dolphin	62	159	0.49549	0.52011	0.52377	0.52852 0.52456	0.52852 0.52646	0.52680	0.52852
	les miserables	77	254	0.50060	0.52438	0.56001	0.56001 0.56001	0.56001 0.54676	0.55351	0.56001
	p53 protein	104	226	0.52052	0.52621	0.53216	0.53502 0.51825	0.52910	0.53000	0.53004	0.53513
	political books	105	441	0.50197	0.52724 0.52694	0.52724 0.52694	0.52724 0.52629	0.52678	0.52724
	football	115	613	0.57728	0.59121	0.60028	0.60457 0.60316	0.60457 0.60091	0.60112	0.60457
	usair97	332	2126	0.32039	0.36221	0.36577	0.36808 0.36374	0.36458	0.35959	0.35975	0.3682
	netscience main	379	914	0.83829	0.84551	0.84745	0.84842 0.84567	0.84754	0.84702	0.84703	0.8486
	s838	512	819	0.80556	0.80666	0.81624	0.81656	0.81274	0.81364	0.81663	0.81675	0.8194
	email	1133	5452	0.51169	0.54736	0.57740	0.57776 0.57425	0.57660	-	-	-
	power	4941	6594	0.93402	0.93658	0.93854	0.93873	0.93679	0.93752	0.93937	0.93941	-
	erdos02	6927	11850	0.78092	0.79543 0.75926	0.76958	0.77481	0.78941	-	-	-

Table 2 :

 2 Modularity values corresponding to the partition found by the heuristic and by our approach after the splitting step only (Q ′ split , Q ′′ split ) and after the successive application of the merging and splitting step (Q ′ merge+split , Q ′′ merge+split ) for Clauset et al.'s heuristic (CNM ) and Noack and Rotta's heuristic (NR).

		49549 0.51693	0.52011	0.52377 0.52773	0.52852
	les miserables	0.50060 0.50732	0.52438	0.56001 0.56001	0.56001
	p53 protein	0.52052 0.52518	0.52621	0.53216 0.53216	0.53502
	political books 0.50197 0.52708	0.52724	0.52694 0.52724	0.52724
	football	0.57728 0.58232	0.59121	0.60028 0.60237	0.60457
	usair97	0.32039 0.36157	0.36221	0.36577 0.36577	0.36808
	netscience main 0.83829 0.84537	0.84551	0.84745 0.84828	0.84842
	s838	0.80556 0.80639	0.80666	0.81624 0.81624	0.81656
	email	0.51169 0.53939	0.54736	0.57740 0.57741	0.57776
	power	0.93402 0.93605	0.93658	0.93854 0.93867	0.93873
	erdos02	0.78092 0.78092	0.79543	0.75926 0.75926	0.76958

Table 3 :

 3 Modularity values corresponding to the partition found by the heuristic and by our approach after the splitting step only (Q ′′′ split , Q iv split ) and after the successive application of the merging and splitting step (Q ′′′ merge+split , Q iv merge+split ) for Schuetz and Caflisch's heuristic (SC) and Cafieri et al.'s heuristic (CHL).

		.52456 0.52852	0.52852	0.52646 0.52646	0.52680
	les miserables	0.56001 0.56001	0.56001	0.54676 0.54676	0.55351
	p53 protein	0.51825 0.52663	0.52910	0.53000 0.53000	0.53004
	political books 0.52693 0.52724	0.52724	0.52629 0.52629	0.52678
	football	0.60316 0.60457	0.60457	0.60091 0.60091	0.60112
	usair97	0.36374 0.36374	0.36458	0.35959 0.35959	0.35975
	netscience main 0.84566 0.84587	0.84754	0.84702 0.84702	0.84703
	s838	0.81274 0.81338	0.81364	0.81663 0.81663	0.81675
	email	0.57425 0.57557	0.57660	-	-	-
	power	0.93678 0.93718	0.93752	0.93937 0.93937	0.93941
	erdos02	0.77481 0.77481	0.78941	-	-	-

Table 4 :

 4 Computing time (seconds) required by the proposed approach applied as postprocessing to Clauset at al.'s heuristic (time CNM ), Noack and Rotta's heuristic (time NR ), Schuetz and Caflisch's heuristic (time SC ) and Cafieri et al.'s heuristic (time CHL ). Solutions have been obtained on a 2.4 GHz Intel Xeon CPU of a computer with 8GB RAM shared by three other similar CPU running Linux.

	dataset	time CNM time NR	time SC	time CHL
	dolphin	0.58	0.20	0.38	0.26
	les miserables	0.32	0.67	0.68	0.35
	p53 protein	0.18	1.02	0.15	0.26
	political books	4.25	5.10	5.10	3.41
	football	0.95	3.26	2.51	0.99
	usair97	1000.96	334.72	525.91	454.64
	netscience main	1.02	1.38	0.75	0.77
	s838	0.73	1.20	0.63	1.06
	email	15591.40	57.80	1196.91	-
	power	21.63	18.62	20.53	17.50
	erdos02	525.37	919.74 15043.85	-

6 :

 6 if Q(CL 1 ) + Q(CL 2 ) > Q(CL i ) then 7:replace CL i with CL 1 , CL 2 ncl split ← number of communities of the new partition 12: end for 13: ncl merge+split ← ncl split 14: for all i ≤ ncl split do 15: listcl ← list of pairs of communities (CL j , CL k ), j, k ∈ {1, . . . , ncl split } select a pair of communities CL j , CL k from listcl 18: merge CL j and CL k into CL m 19:if Q(CL m ) > Q(CL j ) + Q(CL k ) then 20: replace CL j , CL k with CL m = CL j ∪ CL k split CL m into CL m1 , CL m2 23: if Q(CL m1 ) + Q(CL m2 ) > Q(CL m ) then 24:replace CL m with CL m1 , CL m2 end for 32: ncl merge+split ← number of communities of the new partition 33: compute modularity Q =

	8:	else
	9:	keep CL i
	10:	end if
	11:
	16:	while listcl = ∅ do
	17:
	21:	else
	22:
	25:	else
	26:	keep CL m
	27:	end if
	28:	end if
	29:	update listcl
	30:	end while
	31: i=ncl merge+split i=1	Q(CL i )
	34: return final partition, Q


Sonia Cafieri
email: sonia.cafieri@enac.fr

Gilles Caporossi
email: gilles.caporossi@gerad.ca

Pierre Hansen
email: pierre.hansen@gerad.casylvain.perron@gerad.ca

Sylvain Perron

Alberto Costa
email: costa@lix.polytechnique.fr

Finding Communities in Networks in the Strong and Almost-Strong Sense

] define a susbset of vertices of a network to be a community in the strong sense if each vertex of that subset has a larger inner degree than its outer degree. A partition in the strong sense has only strong communities.

In this paper we first define an enumerative algorithm to list all partitions in the strong sense of a network of moderate size. The results of this algorithm are given for the Zachary karate club dataset, which is solved by hand, as well as for several well-known real-world problems of the literature. Moreover, this algorithm is slightly modified in order to apply it to larger networks keeping only partitions with the largest number of communities. It is shown that some of the partitions obtained are informative, although they often have only a few communities, while they fail to give any information in other cases, having only one community. It appears that degree two vertices play a big role in forcing large inhomogeneous communities. Therefore, a weakening of the strong condition is proposed and explored: we define a partition in the almost-strong sense by substituting a non-strict inequality to a strict one in the definition of strong community for all vertices of degree two. Results, for the same set of problems as before, then give partitions with a larger number of communities and are more informative.

Introduction

Networks, or graphs, are composed of a set of vertices and of a set of edges which join pairs of vertices [START_REF] Newman | Networks: An Introduction[END_REF][START_REF] Wasserman | Social Network Analysis. Methods and Applications[END_REF][START_REF] Berge | Graphs and Hypergraphs[END_REF][START_REF] Gross | Handbook of graph theory[END_REF][START_REF] Zhang | [END_REF][START_REF] Wang | Proceedings of the 3rd International Symposium on Optimization and Systems Biology[END_REF]. As vertices can be associated with entities and edges with relations defined on all pairs of vertices, networks are extensively and increasingly used in many areas of science and its applications.

An ubiquitous phenomenon in networks is the presence of communities (also called clusters or modules) where inner edges, joining two vertices of the same community, are dense and cut edges, joining two vertices of different communities, are sparse. As shown below, there are many ways to define and/or evaluate communities as well as partitions of the vertex set into communities. There are three main approaches to the evaluation of a partition of the vertex set of a network:

(i) one can specify a heuristic and evaluate informally the result obtained. For instance, Girvan and Newman [7] present a hierarchical divisive heuristic in which the edge with largest betweenness is iteratively removed and communities correspond to connected components obtained each time a community is split into two. This heuristic therefore proceeds from an initial (trivial) partition in a single community containing all vertices to a final partition in which each community contains a single vertex. Divisions of communities are graphically represented by a dendrogram;

(ii) a criterion function, to be maximized or minimized, is chosen. There are many examples, the best known of which is modularity, initially proposed as a stopping rule for the divisive heuristic mentioned above and later considered as an independent criterion. Other well-known criteria are the k-way cut [8,9], the normalized cut [10,11], the ratio cut [9], the modularity density and its variants [12,13], and strength maximization subject to strong or weak constraints on the communities (see Section 2) [14,15]. More recently, several promising criteria have been put forward: information compression [16], maximum likelihood and the expectation maximization (EM) algorithm [17] and the constant Potts model [18].

(iii) conditions to be satisfied by a community are specified. Several such conditions have been proposed; the early ones are reviewed in the book [START_REF] Wasserman | Social Network Analysis. Methods and Applications[END_REF]. They include the cliques, in which every pair of vertices must be joined by an edge, the k-cliques in which the indegree of each vertex must be at least k, and LS (Luccio-Sami) set [19], i.e., a set of vertices S such that each of its proper subsets has more ties to its complement within S than to the outside of S. These three criteria tend to be too stringent and/or too difficult to compute, except on the smallest networks. Two others intuitive and well-known criteria have been proposed by Radicchi et al. [20]: a subset S of vertices of a network forms a community in the strong sense if the number of neighbors of each vertex within S is larger than the number of neighbors outside S. A set of vertices S forms a community in the weak sense if the sum, for all of its vertices, of the difference between the number of neighbors within S and the number of neighbors outside S is positive. As these concepts capture the intuitive idea of a community, they are very often cited. Recently, weakened versions have been proposed, in which instead of comparing the numbers of neighbors within and outside the community, one compares the numbers of neighbors within a community, and outside that community but within another specific community [13].

In this paper we focus on communities in the strong sense. We first give an exact algorithm for finding all partitions of a network into communities in the strong sense. There are several reasons to consider exact algorithms instead of heuristics: while exact algorithms are limited to problems of moderate size (in modularity maximization the largest instance solved exactly up to now is the S838 dataset which has 512 vertices and 819 edges, solved by the column generation algorithm [21]). Smaller networks are of interest in several domains, e.g., sociology, mathematical psychology and ecology. Then, using an exact algorithm allows discrimination of errors due to an inadequate model or to a non-optimal resolution by heuristics. Moreover, exactly solved problems provide a benchmark for evaluating and comparing heuristics. Comparing the exact solution with those obtained by some heuristic focuses on parts of the problem which are badly solved and can suggest how to improve the heuristic. Conversely, heuristics can be used in order to accelerate one or several steps of the exact algorithm, e.g., by providing a hot start. A more complete discussion of merits and demerits of exact algorithms and heuristics is given in the first section of [21].

The paper is organized as follows: definitions and notation are specified in the next section. The main algorithm, called Strong Communities (SC), is presented in Section 3. Its application is illustrated step-by-step by hand resolution of the classical Zachary karate club network [22]. A variant of SC, called Almost-Strong Communities (ASC), and in which the definition of strong community is weakened, is presented in Section 4. Results obtained by both algorithms for several real-world networks, described in the Pajek database (http://vlado.fmf.uni-lj.si/pub/networks/data/), are presented and discussed in Section 5. Conclusions are drawn in Section 6.

Definitions and notation

We denote a network, or graph, by G = (V, E) where V is the set of n vertices, and E is the set of m edges which join pairs of vertices. A vertex v j is represented by a point and an edge e i,j = {v i , v j } by a line joining its two end vertices v i and v j . The shape of this line does not matter, only the presence or absence of an edge is important. A loop e i,i = {v i , v i } is an edge for which both end vertices coincide. In a simple graph, there is at most one edge between any pair of vertices, and no loops. The degree k i of a vertex v i ∈ V is the number of edges incident with v i . In this paper, we focus on unweighted simple graphs.

The adjacency matrix A = (a i,j ) of G is a square n by n matrix such that a i,j = 1 if vertices v i and v j are joined by an edge, and equal to 0 otherwise.

A subgraph G S = (S, E S ) of a graph G = (V, E) induced by a set of vertices S ⊆ V is a graph with vertex set S and edge set E S equal to all edges with both vertices in S. Such a subgraph corresponds to a community and many heuristics, as well as exact algorithms, aim at finding a partition of V into pairwise disjoint nonempty subsets S 1 , S 2 , . . . , S N inducing subgraphs of G. Various objective functions have been proposed for evaluating such a partition. Roughly speaking, one seeks modules which contain more inner edges (with both vertices in the same module) than cut edges (with vertices in different modules). The degree k i of the vertex v i can be split in two parts: the indegree k in i or number of neighbors of v i within its community and the outdegree k out i or number of neighbors of v i outside its community. Several concepts of community follow.

A set S of vertices is a clique if all pairs of vertices of S are joined by an edge, i.e., k i = |S| -1, ∀v i ∈ S. A set S is a k-clique if every vertex of S has at least k neighbors within S, where k is a parameter.

In 2004, Radicchi et al. [20] defined a community in the strong sense as a subgraph all vertices of which have larger indegree than outdegree: k in i > k out i , ∀v i ∈ S or equivalently j∈S a i,j > j∈V \S a i,j , ∀v i ∈ S. Note that the concept of defensive alliance, studied in graph theory (see the thesis [START_REF] Shafique | Partitioning a graph in alliances and its application to data clustering[END_REF] and references therein), is very close to that of community in the strong sense and is obtained by substituting non-strict inequalities to strict ones.

In the same paper [20], a community in the weak sense is defined as a subgraph for which the sum of vertex indegrees is larger than the sum of vertex outdegrees:

vi∈S k in i > vi∈S k out i or equivalently vi∈S vj ∈S a i,j > vi∈S vj ∈V \S a i,j .
As an inner edge contributes by two to the sum of the indegrees and a cut edge contributes by one to the sum of outdegrees, the number of inner edges in a community in the weak sense must be at least as large as half the number of cut edges. As cut edges contribute by one to the sum of degrees of two communities, this definition entails that for the network as a whole the number of inner edges is larger than the number of cut edges. Recently, several extensions of the definition of the community in the strong and weak sense have been proposed [13]. In these extensions one considers all outgoing edges from the set S to another subset S t of E instead of the sum for all such sets: k in i (S) > max t=1,...,M|St =S vj ∈St a i,j , ∀v i ∈ S, where M is the number of communities. The second extension is similar but uses sums of degrees instead of individual degrees: vi∈S k in i (S) > max t=1,...,M|St =S vi∈S vj ∈St a i,j . One may also consider the difference for each community of the sum of indegrees and the sum of outdegrees. Then summing these contributions for all communities gives a k-way cut problem. Another approach is to normalize the contribution of each community by dividing it by its number of vertices [12]. The resulting function, to be maximized, is called modularity density. Alternatively, contributions of communities may be divided by their number of edges [15]. Finally, one may consider maximizing, in a divisive hierarchical method, the minimum ratio of the number of edges in a community divided by the number of cut edges [START_REF] Cafieri | [END_REF].

Algorithm SC

We next present the rules of an algorithm, called SC (Strong Communities), for enumerating all the partitions in the strong sense of a given network G = (V, E). Note that this problem always has a solution, i.e., the trivial partition consisting in a single community containing all the vertices. The algorithm will make use of two types of labels associated with the vertices and the edges of G respectively: label l i associated with vertex v i , i = 1, . . . , n (initially l i = i for all vertices, and at the current iteration the label of the vertex v i is equal to the smallest label of a vertex of the community to which v i belongs); the label t i,j associated with edge (v i , v j ) can take three values (-1, 0, 1). It is equal to -1 if it has already been decided that the vertices v i and v j belong to different communities; it is equal to 1 if it has already been decided that vertices v i and v j belong to the same community. If no decision has been taken, t i,j = 0.

It turns out that the rules of our algorithm are simple and effective. To illustrate, we next list these rules and show at the same time that all partitions in the strong sense of the Zachary karate club network [22] can be found by hand.

Rules of the algorithm SC are the following:

• Rule 1 (pending edges): if the edge (v i , v j ) is a pending one, set its label t i,j to 1 and set both l i and l j to min(l i , l j ). In words, both vertices of a pending edge must belong to the same community.

-Example 1 (Karate club): this network has a single pending edge, i.e., [START_REF] Newman | Networks: An Introduction[END_REF]12), so we set t 1,12 = 1 and l 12 = 1.

• Rule 2 (degree two vertices): if vertex v i has degree k i = 2, and its neighbors are v j and v k , set t i,j = 1, t i,k = 1 and l i = l j = l k = min(l i , l j , l k ). In words, if a vertex v i has degree 2 and neighbors v j and v k , it follows from the strong condition that all three vertices v i , v j , v k must belong to the same community.

-Example 1 (continued): this network has eleven degree two vertices; applying Rule 2 we get the following labels (see Fig. 1):

Figure 1: Zackary karate club communities after application of Rule 2; empty vertices are isolated at the current stage of resolution (color online).

• Rule 3.b (negative transitivity): -Example 1 (continued): this Rule does not apply yet because no edges have a negative label.

if l i = l j and t i,j = -1, set t a,b = -1 ∀(v a , v b ) : l a = l i , l b = l j ,
• Rule 4.a (majority 1 ): if the majority of neighbors of the vertex v i belong to the same community and the label of the vertices belonging to this community is l, set l i = l = min(l, l i ) and apply the positive transitivity Rule. In words, if half or more of the neighbors of v i have the same label l, the only way to satisfy the strict inequality of the strong condition is to add the vertex v i to the community where its vertices have label l.

-Example 1 (continued): after application of Rule 4.a we get the following labels (see Fig. 2): • Rule 4.c (majority 3 ): if the number of negative edges, i.e., edges labeled with -1, incident with the vertex v i is equal to ⌈ ki 2 ⌉ -1, for all the neighbor vertices v j of v i having t i,j = 0, set t i,j = 1, and for all the vertices v k with l k = l j , set l k = l i . In words, when the number of negative edges incident to v i is almost the majority there is only one way to satisfy the strong condition at vertex v i , i.e., set the label associated to all other incident edges to 1.

-Example 1 (continued): this Rule does not apply yet because no edges have a negative label. Rules 3 and 4 must be repeated as long as there is at least one change of label.

• Rule 5 (branching): if no more labels of edges can be modified according to the previous rules, one selects an edge with label 0 and, subject to that condition, joining the two largest communities. Set the label of this edge to -1 (left branch). Then set separately this label to 1 (right branch), store the current subproblem and return to Rule 3.a. • Rule 6.a (no majority): if the number of negative edges incident with the vertex v i is larger than ⌈ ki 2 ⌉ -1, apply Rule 8 below. • Rule 6.b (no coherent labels): if there exists two vertices v i and v j with l i = l j and t i,j = -1, apply Rule 8 below. • Rule 7 (feasible solution): if all edges have a label -1 or 1, store the corresponding partition, then apply Rule 8.

• Rule 8 (backtracking): return to the latest application of the branching rule and consider the right hand-side branch as current subproblem.

-Example 1 (continued): the branching is done on edge [START_REF] Newman | Networks: An Introduction[END_REF][START_REF] Wang | Proceedings of the 3rd International Symposium on Optimization and Systems Biology[END_REF] which first gets a label equal to -1, and later to 1. * t 1,6 = -1. For the negative transitivity also t 1,7 = -1. For the majority 3 Rule applied to vertex v 6 we can set t 6,11 = 1 and l 11 = 6. Again, for the negative transitivity t 1,11 = -1.

Then, for the majority 1 Rule applied to vertex v 5 , l 6 = l 7 = l 11 = l 17 = 5 and t 5,7 = t 5,11 = 1 and at the end for the negative transitivity t 1,5 = -1. Since all the labels are now fixed, we apply Rule 7, and save the solution, whose labels are: l 5 = l 6 = l 7 = l 11 = l 17 = 5, and all the other vertices have label 1; t 1,5 = t 1,6 = t 1,11 = -1 and all the other edges have label 1. The obtained partition is presented in Fig. 4. After storing this partition we apply Rule 8, and we continue with the right branch below. * t 1,6 = 1. For the positive transitivity also t 1,7 = 1 and l 6 = l 7 = l 17 = 1. For the majority 1 Rule applied to vertex v 5 we can set l 5 = 1 and t 5,7 = t 1,5 = 1. Then, we apply again the majority 1 Rule to vertex v 11 and we can set l 11 = 1, t 1,11 = t 5,11 = t 6,11 = 1. Since all the labels are now fixed, we apply Rule 7, and save the solution, where all the vertices have label 1 and all the edges have label 1. After storing this partition we apply Rule 8, and the algorithm stops.

So, only two partitions have been found, including the trivial partition with a single community. The other one isolates a small and dense community connected to the remaining part of the network by a cut vertex, i.e. v 1 whose removal disconnects the network. This partition is far from that one observed by Zachary in which there were two clusters of equal size. Note however that the small cluster is contained in one of the clusters of Zachary's partition. A similar result was obtained by Medus and Dorso in [15], Fig. 1, when optimizing their strong figure of merit subject to the constraint that communities are strong ones.

A variant of the algorithm SC: ASC

From the discussion of the real-word example of community detection in the strong sense presented in the previous section it appears that: (i) results are often satisfactory in terms of individual communities, as the strong conditions are not easily satisfied; (ii) communities are however often too large and correspond in fact to the union of several distinct communities; (iii) in the limit one finds a single community regrouping all vertices, which of course is not informative; (iv) the main reason for having large heterogeneous communities appears to be due to the degree two vertices. Indeed, the strong condition imposes that them and both of their two neighbors belong to the same community, while these neighbors can be very different in terms of their own neighbors.

This suggests to weaken the strong condition when it appears to be unjustified, i.e., for the degree two vertices. We call a community almost-strong if it satisfies the condition k in i ≥ k out i for all vertices of degree two, and the strong condition k in i > k out i for the remaining vertices.

Modifications to be brought to the algorithm of the previous section in order for it to find partitions in the almost-strong sense are minimum. They lead to a modified algorithm called ASC (Almost-Strong Communities). Indeed, it sufficies to remove Rule 2 and update Rules 4.a, 4.b, 4.c and 6.a by specifying that in the case of a vertex v i of degree 2, one uses majority and not strict majority.

Rules of the modified algorithm ASC are the following:

• Rule 1 (pending edges): if the edge (v i , v j ) is a pending one, set its label t i,j to 1 and set both l i and l j to min(l i , l j ). In words, both vertices of pending edge must belong to the same community. • Rule 3.a (positive transitivity): if l i = l j and t i,j = 0, set t i,j = 1. In words, if two vertices v i and v j belong to the same community, and are joined by an edge which does not specify that, set the label of this edge as positive. Then, apply the positive transitivity Rule. In other words, merge the communities with labels l 1 and l 2 , and put in this new community the vertex v i , too. • Rule 4.c.1 (majority 3 ): if the number of negative edges incident with the vertex v i with degree k i = 2 is equal to ⌈ ki 2 ⌉ -1, for all the neighbor vertices v j of v i having t i,j = 0, set t i,j = 1, and for all the vertices v k with l k = l j , set l k = l i .

• Rule 3.b (negative transitivity): if l i = l j and t i,j = -1, set t a,b = -1 ∀(v a , v b ) : l a = l i , l b = l j ,
• Rule 4.c.2 (majority 3' ): if the number of negative edges incident with the vertex v i with degree k i = 2 is equal to 1, for all the neighbor vertices v j of v i having t i,j = 0, set t i,j = 1, and for all the vertices v k with l k = l j , set l k = l i . Rules 3 and 4 must be repeated as long as there is at least one change of label. • Rule 5 (branching): if no more labels of edges can be modified according to the previous rules, one selects an edge with label 0 and subject to that condition joining the two largest communities. Set the label of this edge to -1 (left branch). Then set separately this label to 1 (right branch), store the current subproblem and return to Rule 3.a. • Rule 6.a.1 (no majority): if the number of negative edges incident with a vertex v i with degree k i = 2 is larger than ⌈ ki 2 ⌉ -1, apply Rule 8 below. • Rule 6.a.2 (no majority' ): if the number of negative edges incident with a vertex v i with degree k i = 2 is larger than 1, apply Rule 8 below. • Rule 6.b (no coherent labels): if there exists two vertices v i and v j with l i = l j and t i,j = -1, apply Rule 8 below. • Rule 7 (feasible solution): if all edges have a label -1 or 1, store the corresponding partition, then apply Rule 8.

• Rule 8 (backtracking): return to the latest application of the branching rule and consider the right hand-side branch as current subproblem.

Results

In this section we compare the results obtained for finding partitions in the strong and the almost-strong sense. As partitions in the almost-strong case may be very numerous, we only store those which have the largest number of communities. Further discriminations between them could be obtained according to the values they give to some objective function. This topic will not be discussed here.

Let us first consider again Zachary's karate club. The largest number of communities in almost-strong partition is three. This partition is unique and it is represented in Fig. 5. There are also 22 partitions into two clusters, including one where the yellow and green clusters communities are joined into a single one. This partition coincides with the partition between followers of the karate club administrator and the instructor in the split observed by Zachary except for member 10 (which is often misclassified). Another partition into two clusters is of course the strong partition of Fig. 4 and finally there is also the trivial partition. A second real-world dataset concerns informal communications within a sawmill on strike [25]. Vertices are associated with the 24 employees of a wood processing facility where a new management team proposes changes to the compensation package. The workers refuse and a strike ensues. Facing a stalemate, the management asks a consultant to analyze the communications among the employees. Edges of the network correspond to frequent discussions on the strike between pairs of colleagues. Two partitions into strong communities were obtained with the SC algorithm; one of them is a clique on 4 vertices (10,11,12,13) corresponding to all spanish-speaking employees, the remaining 20 employees are english-speaking; see Fig. 6(a). The ASC algorithm gives 20 partitions. A single one of them has 4 communities (see Fig. 6(b)), and none had more. The small community with 4 spanish-speaking employees remains the same. The second community of 20 employees is split into 3 communities: a first one corresponds to 9 english-speaking employees with age less than or equal to 30. The second community with 9 employees and the third one with 2 employees correspond to older english-speaking workers. The partition of the 24 employees in three communities, i.e., spanish-speaking, young english-speaking and older english speaking employees obtained by joining the two last communities corresponds exactly to the partition obtained by the consultant. As the strong conditions and the almost-strong conditions remain satisfied when communities are merged, the ASC algorithm did also find the optimal three community partition. Detection of the small community with employees 16 and 21 may be interpreted in that these employees are less talkative, or less concerned by the strike, than most of the others. It thus appears that algorithm SC recognises well a small, almost isolated community but groups unduly the others. Algorithm ASC finds the optimal partition and it perhaps provides a little more information.

A next example purports to graph theory. Mr. Cherowitzo compiled a glossary of graphs and digraphs. 1The version of 2003, in Pajek format, contains 72 vertices associated with terms. An arc from v i to v j means that the concept associated with v i is used in the definition of v j . We neglected orientation of arcs and considered only the largest connected component, which has 60 vertices and 114 edges. Applying algorithm SC only the trivial partition was found. Turning to algorithm ASC, many partitions were obtained, 5 of which have the largest number of communities, i.e., 6. The most intuitively appealing of them is presented on Fig. 7.

We next comment on these communities going from the smallest to the largest. The first community corresponds to two terms, i.e., {complete, clique}. They are clearly close, as a complete graph is a clique. The second community also has two terms, pertained to computer searh, i.e., {child, ordered tree}. These two communities appeared unchanged in all 5 partitions into 6 communities. A third community contains 7 terms, i.e., {decision tree, binary search tree, m-ary tree, rooted tree, offspring, level, height}. All those terms correspond, as did those of community 2, to computer search. Community three is similar in the 4 other partitions into 6 communities except for that the term decision tree is assigned to another community. A fourth community contains 8 terms, i.e., {diameter, distance, hamiltonian, walk, trail, path, aciclyc graph, cycle}. These terms correspond to concepts related to paths and cycles. A fifth community contains 17 terms, i.e., {strongly connected, tournament, digraph, orientation, arc list, neighborhood, node, order, internal vertex, vertex, pendant vertex, leaf, degree, regular, adjacency structure, adjacent, closure}. It seems difficult to find a concept encompassing all of these terms. The five first, i.e., {strongly connected, tournament, digraph, orientation, arc list} correspond to oriented graphs. The remainder corresponds to vertices and adjacency. Note that this community contains several pairs of synonims, i.e., {node} and {vertex}, and {pendant vertex} and {leaf}. The sixth community contains 24 terms, i.e., {label, isomorphic, planar, edge, size, topological order, adjacency matrix, loop, reduced graph, condensed graph, homeomorphic, bipartite graph, spanning subgraph, subgraph, spanning tree, connected component, bridge, connected, forest, tree, graph, cromatic number, k-colorable, arc}. This community appears to be less homogeneous than the others. Some concepts are related to edges, i.e., {edge, loop, size, label}. Others correspond to properties or families of graphs: {isomorphic, homeomorphic, condensed graph, reduced graph, bipartite graph, spanning subgraph, spanning tree, subgraph, connected component, connected, bridge, tree, k-colorable, cromatic number, graph}. Although this partition appears to be quite informative, it is not perfect, e.g. because {forest} and {acyclic graph} are synonyms but attributed to different communities. Or yet close terms such as {adjacency matrix} and {adjacency structure} are also attributed to different communities.

A fourth example comes from the well-known paper on dolphins due to Lusseau et al. [27]. However, it does not concern the set of all 62 dolphins, but another network giving the sociogram of the community for groups followed between 1995 and 2001. This network has 40 vertices and 70 edges. When trying to find communities in the strong sense four partitions were obtained, one with three communities, represented on Fig. 8(a), two obtained by merging pairs of adjacent communities, and the trivial partition.

Finding communities in the almost-strong sense gives a partition in eight communities, which is represented in Fig. 8(b). It refines one of the communities by isolating a small two vertices community with one vertex of degree two. It also refines more drastically the largest community by isolating four subnetworks with two, two, three and four entities. Each of these subnetworks contains a vertex of degree two. It appears clearly that this almost-strong partition is more informative than any other strong one.

We next studied the full set of 62 dolphins, for which a real-world partition into two communities has been observed by Lusseau et al. [27]. Algorithm SC found four strong partitions, all of which have two communities, plus the trivial partition. None of these bipartitions is close to the optimal one, observed by Lusseau. The closest bipartition is presented in Fig. 9(a) and has 14 misclassified dolphins. Turning to the ASC algorithm it was found that it became quite time consuming. A partial resolution gave 7 partitions into 4 communities. One of them (see Fig. 9(b)) has a community which is the same as the 21 dolphins community of Lusseau, and consequently the union of the other three communities is equal to the 41 dolphins community of Lusseau. 2 We also use a mixed-integer program [START_REF]Linear programming[END_REF] with the almost-strong condition on communities and as objective to find a partition in as many communities as possible. This gives us a partition very close to that one obtained by partial resolution with ASC. It has 4 communities which are equal to those obtained previously, except for the fact that dolphins 16 and 56 now belong to a community adjacent to their own (yellow instead of green color online).

Our last dataset is the set of characters of Victor Hugo's Les Misérables [START_REF] Hugo | Les Misérables[END_REF][START_REF] Knuth | The Stanford GraphBase: a platform for combinatorial computing[END_REF]. 77 vertices correspond to these characters and 254 edges indicate direct interaction i.e., an edge joins vertices v i and v j if and only if the corresponding characters appear jointly in at least one of the many, usually short, chapters of the novel. Algorithm SC gives a partition into 4 strong communities, and it is represented in Fig. 10(a). Algorithm ASC was too time and space consuming and did not give useful results for this dataset. So we used again the mixed-integer program mentioned above. We then obtained an almost-strong partition with 7 communities presented in Fig. 10(b).

Comparing results of SC and ASC we observe that the partition of ASC is clearly more discriminant than that of SC. The largest community is broken up into 2 communities and slightly mixed with the second largest community. This second largest community is broken up into 3 communities. One of the remaining communities is unchanged, and the second one slightly modified by moving vertices 3 and 4 to the largest community. This is arbitrary as in both cases the ASC condition is satisfied.

Moreover, in absence of a generally accepted substantively justified partition for les misérables, we compare both partitions obtained by SC and the mixed-integer version of ASC, with the partition obtained by the edge ratio (ER) algorithm [START_REF] Cafieri | [END_REF], which has an excellent intuitive interpretation. The ER partition contains 10 communities, represented in Fig. 11. They can be described as follows: 2 Medus and Dorso present in [15], Fig. 4, a partitioning of the 62 dolphin dataset into five weak communities. The union of two of them and of the three others gives a bipartition of the set of dolphins into communities in the strong sense. It appears however that the dataset used by Medus and Dorso differs from the standard one of Lusseau (i.e., there are 157 edges instead of 159 and the number of vertices of equal degree differs in several places). A. Medus kindly applied his algorithm for strenght maximization subject to Radicchi strong condition to Lusseau standard network and obtained the same partition as we do. As can be seen on Fig. 10, algorithm SC finds exactly the two communities C 5 and C 6 . However, it groups several other communities. Indeed, it groups the community C 2 but omitting Marius (vertex 56), together with the two small communities C 1 and C 4 . These two mergings are less damaging than omitting Marius as the four protagonists of these two communities are minor characters connected only to Gavroche (vertex 49) in community C 2 . All other characters are joined into a big communities of 44 characters. So once again algorithm SC determines exactly some of the communities, but gives a fuzzy description of another one, and merges all the remaining ones.

Comparing now the partitions obtained for ASC and ER we find that they are much closer than those of SC and ASC, as well as of those of SC and ER. Indeed, the ASC partition contains without errors 3 of the communities of the ER partition, i.e., C 1 , C 4 and C 6 . Three other communities, i.e., C 2 , C 5 and C 7 ,

Conclusions

Several conditions which should be satisfied by communities in a network have been proposed by various authors. In this paper we studied one of the most intuitively appealing, i.e., the condition to have a community in the strong sense proposed by Radicchi et al. [20]. It states that to be a community in the strong sense, a subset S ⊆ V of vertices should be such that the indegree must be larger than the outdegree for each vertex v i ∈ S.

A too stringent condition will not have a high degree of resolution, i.e., it may have a tendency to regroup several natural communities into large ones. Conversely, a too lax condition can generate a large number of small and not necessary relevant communities. We have investigated the question of whether the definition of strong community is too stringent or too lax. To that effect we have proposed an exact enumeration algorithm which guarantees finding all partitions of a network into strong communities. This algorithm is quite efficient, as illustrated by the fact that it could be applied by hand to the well-known Zachary karate club network. Actually, it has solved problems with up to 77 vertices. The results are the following: while some not too large communities are found in a crisp way, it is not uncommon for several network communities to be joined in larger, heterogeneous ones. In the limit, one can obtain only the trivial partition in which all vertices belong to the same community. The reason for the formation of too large communities appears to be the presence of degree two vertices. Indeed, when a vertex has degree two, the strong condition imposes that itself and both of its neighbors belong to the same community.

To test this simple hypothesis, we have modified the definition of community in the strong sense in a minimal but sufficient way. In the definition of community in the strong sense we modify the strict inequality between indegree and outdegree to a non-strict inequality for all vertices of degree two and only them. We say that this new condition defines a community in the almost-strong sense. Then we have modified, slightly but sufficiently, the algorithm SC to conform to this new condition. Indeed, the resulting algorithm ASC usually gives partitions into more communities than algorithm SC. Moreover, they are usually more intuitively appealing.

Combining a criterion for community evaluation with constraints on each community has been pioneered by Medus and Dorso [15]. This work can be pursued in two ways: (i) modifying the models and the corresponding algorithms or heuristics to incorporate the constraints on the communities from the outset, or (ii) using a standard algorithm or heuristic then checking if the obtained communities satisfy the given constraints; if not, apply some specific heuristic to restore feasibility. Those two approaches are the topic of a paper in preparation.

  and t a,b = 0. In words, if two vertices belong to different communities and are joined by a negative edge, all the edges with label 0 joining two vertices of these communities are set to -1.

Figure 2 :

 2 Figure 2: Zackary karate club communities after application of Rule 4.a (color online).

Figure 3 :

 3 Figure 3: Zackary karate club communities after Rule 4.b (color online).

Figure 4 :

 4 Figure 4: Solution with two strong communities found by algorithm SC for Zachary karate club network (color online).

  and t a,b = 0. In words, if two vertices belong to different communities and are joined by a negative edge, all the edges with label 0 joining two vertices of these communities are set to -1.• Rule 4.a.1 (majority 1 ): if the majority of neighbors of the vertex v i with k i = 2 belong to the same community and the label of the vertices belonging to this community is l, set l i = l = min(l, l 1 ) and apply the positive transitivity Rule. • Rule 4.a.2 (majority 1' ): if both neighbors of the vertex v i with k i = 2 belong to the same community and the label of the vertices belonging to this community is l, set l i = l = min(l, l 1 ) and apply the positive transitivity Rule. • Rule 4.b (majority 2 ): if a vertex v i has degree k i = 2d = 2, and there are d neighbors with label l 1 and d neighbors with label l 2 , set l i = min(l 1 , l 2 ), and for all the vertices v k with l k = l 1 or l 2 , set l k = l i .

Figure 5 :

 5 Figure 5: Partition into three almost-strong communities obtained by algorithm ASC for Zachary karate club network (color online).

Figure 6 :

 6 Figure 6: Partitions into strong communities and into almost-strong communities obtained by algorithms SC and ASC respectively for the strike dataset (color online).

Figure 7 :

 7 Figure 7: Partition into almost-strong communities obtained by algorithm ASC for the graph and digraph glossary dataset (color online).

Figure 8 :

 8 Figure 8: Partitions into strong communities and into almost-strong communities obtained by algorithms SC and ASC respectively for the small dolphin dataset (color online).

Figure 9 :

 9 Figure 9: Partitions into strong communities and into almost-strong communities obtained by algorithms SC and ASC respectively for the dolphin dataset (color online).

Figure 10 :

 10 Figure 10: Partitions into strong communities and into almost-strong communities obtained by algorithms SC and ASC respectively for Les misérables dataset (color online).

Figure 11 :

 11 Figure 11: Partition obtained by algorithm ER for Les misérables dataset (color online).

The glossary can be found at http://vlado.fmf.uni-lj.si/pub/networks/data/DIC/TG/glossTG.pdf.

Financial support by Grants Digiteo 2009-14D "RMNCCO" and Digiteo 2009-55D "ARM" is gratefully acknowledged. G.C., P.H., and S.P. were partially supported by fqrnt (Fonds de recherche du Québec -Nature et technologies ) team grant PR-131365. S.P. has been partially supported by nserc (Natural Sciences and Engineering Research Council of Canada) grant 327435-06.

G-2011-