Konstantin E Avrachenkov
email: k.avrachenkov@inria.fr

Yu Aleksei

Vladimir V Kondratev

Dmytro Mazalov

Rubanov

Aleksei Y Kondratev

Vladimir V Mazalov

Dmytro G Rubanov

Network partitioning algorithms as cooperative games

Keywords: Network partitioning, Community detection, Cooperative game, Myerson value, Hedonic game, Gibbs sampling

published or not. The documents may come

Introduction

Community detection in networks is a very important topic which has numerous applications in social network analysis, computer science, telecommunications, and bioinformatics and has attracted the effort of many researchers. In the present work, we consider the framework of crisp community detection or network partitioning, where one would like to partition a network into disjoint sets of nodes. The consideration of overlapping, hierarchical, and local clustering we leave for future research. Even the literature on crisp community detection is huge. We refer to several extensive survey papers [START_REF] Rubanov | Community detection and stochastic block models: recent developments[END_REF][START_REF] Fortunato | Community detection in graphs[END_REF][START_REF] Fortunato | Community detection in networks: a user guide[END_REF][START_REF] Jonnalagadda | A survey on game theoretic models for community detection in social networks[END_REF][START_REF] Luxburg | A tutorial on spectral clustering[END_REF][START_REF] Schaeffer | Graph clustering[END_REF]. Let us just mention main classes of methods for network partitioning. The first very large class is based on spectral elements of the network matrices such as adjacency matrix and Laplacian (see e.g., the surveys [START_REF] Rubanov | Community detection and stochastic block models: recent developments[END_REF][START_REF] Luxburg | A tutorial on spectral clustering[END_REF] and references therein). The second class of methods is based on the use of random walks (see e.g., [START_REF] Avrachenkov | Pagerank based clustering of hypertext document collections[END_REF][START_REF] Avrachenkov | Graph clustering based on mixing time of random walks[END_REF][START_REF] Dongen | Performance criteria for graph clustering and Markov cluster experiments[END_REF][START_REF] Meilă | A random walks view of spectral segmentation[END_REF][START_REF] Newman | A measure of betweenness centrality based on random walks[END_REF][START_REF] Pons | Computing communities in large networks using random walks[END_REF] for the most representative works in this research direction). The third class of approaches to network partitioning is based on the optimization of some objective function [START_REF] Blatt | Clustering data through an analogy to the potts model[END_REF][START_REF] Blondel | Fast unfolding of communities in large networks[END_REF][START_REF] Girvan | Community structure in social and biological networks[END_REF][START_REF] Newman | Modularity and community structure in networks[END_REF][START_REF] Raghavan | Near linear time algorithm to detect community structures in large-scale networks[END_REF][START_REF] Reichardt | Statistical mechanics of community detection[END_REF][START_REF] Waltman | A unified approach to mapping and clustering of bibliometric networks[END_REF], with modularity function [START_REF] Girvan | Community structure in social and biological networks[END_REF][START_REF] Newman | Modularity and community structure in networks[END_REF] as a notable example in this category. Finally, the fourth class, directly related to the present work, is based on the notions from game theory. We recommend to an interested reader a recent survey [START_REF] Jonnalagadda | A survey on game theoretic models for community detection in social networks[END_REF] on the application of game-theoretic techniques to community detection. Most bibliography described in [START_REF] Jonnalagadda | A survey on game theoretic models for community detection in social networks[END_REF] is in fact dedicated to noncooperative game theory approaches. It appears that the application of the cooperative or coalition games to community detection problem is under-developed and thus with this article we advance this research area.

There are definitely many relations among the above-mentioned classes. In particular, the conditions for minima of the objective functions can often be interpreted in terms of the eigen elements of the network matrices. The eigen elements of the network matrices also characterize the stationary or quasi-stationary state of a random walk on a network. In the present work, we show more connections between the approach based on cooperative games and other approaches.

In essence, all the above-mentioned approaches, with exception of the game theory approach, try to detect dense subgraphs inside the network and do not address the question: what are the natural forces and dynamics behind the formation of network clusters. As noticed in [START_REF] Mcsweeney | A game theoretic framework for community detection[END_REF], most of traditional clustering methods pursue a top-down approach, whereas typically communities are formed by local interactions in self-organizing fashion, often driven by egocentric decisions. Thus, it is very natural to apply game theory, and in particular, coalition game theory for community detection problem. Also, in most of the above-mentioned methods, the number of communities is a prerequisite parameter. The game theory approach typically does not require a priori knowledge of the number of communities. One more very important benefit in using the methods from game theory is that such methods are naturally distributed and can easily be implemented in clouds and decentralized multi-agent systems.

In the present work, we explore two cooperative game theory approaches to explain possible mechanisms behind cluster formation. Our first approach is based on the Myerson value in cooperative game theory, which particularly emphasizes the value allocation in the context of games with interactions between players constrained by a network. The advantage of the Myerson value is in taking into account the impact of all coalitions. We extend the method developed in [START_REF] Mazalov | Generating functions and the myerson vector in communication networks[END_REF][START_REF] Mazalov | Game-theoretic centrality measures for weighted graphs[END_REF] to calculate efficiently the Myerson value in a network. A number of network centrality measures based on game-theoretic concepts have been developed, see [START_REF] Mazalov | Game-theoretic centrality measures for weighted graphs[END_REF][START_REF] Gomez | Centrality and power in social networks: a game theoretic approach[END_REF][START_REF] Suri | Proceedings of the 7th international joint conference on autonomous agents and multiagent systems[END_REF][START_REF] Szczepański | A new approach to betweenness centrality based on the shapley value[END_REF][START_REF] Michalak | Efficient computation of the shapley value for game-theoretic network centrality[END_REF][START_REF] Chen | Interplay between social influence and network centrality: a comparative study on shapley centrality and single-node-influence centrality[END_REF][START_REF] Skibski | Axiomatic characterization of game-theoretic centrality[END_REF] and references therein. It might be interesting to combine node ranking and clustering based on the same approach such as the Myerson value to analyze the network structure. Unfortunately, the computation of the Myerson value is a very difficult problem even for a moderately large number of players. Therefore, we propose the second approach which has efficient computational implementation and can easily be distributed.

The second approach is based on hedonic games [START_REF] Bogomolnaia | The stability of hedonic coalition structures[END_REF], which are games explaining well the mechanism behind the formation of coalitions. Both our approaches allow to detect clusters with varying resolutions and thus avoiding the problem of resolution limit [START_REF] Fortunato | Resolution limit in community detection[END_REF][START_REF] Leskovec | Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters[END_REF]. The hedonic game approach is especially well suited to adjust the level of resolution as the limiting cases are given by the grand coalition and sequential maximum clique decomposition, two very natural extreme cases of network partitioning. Furthermore, the modularity-based approaches as well as ratio cut [START_REF] Hagen | New spectral methods for ratio cut partitioning and clustering[END_REF] and normalized cut [START_REF] Meilă | A random walks view of spectral segmentation[END_REF][START_REF] Shi | Normalized cuts and image segmentation[END_REF] based methods can be cast in the setting of hedonic games. We find that this gives one more, very interesting, interpretation of the modularity-based methods. The advantage of casting the ratio cut and normalized cut in the framework of hedonic games is that we do not need to prespecify the number of clusters as was needed in the original formulations of these methods. Some hierarchical network partitioning methods based on tree hierarchy, such as [START_REF] Girvan | Community structure in social and biological networks[END_REF], cannot produce a clustering on one resolution level with the number of clusters different from the predefined tree shape. Furthermore, the majority of clustering methods require the number of clusters as an input parameter. In contrast, in our approaches we specify the value of the resolution parameter(s) and the method gives a natural number of clusters corresponding to the given resolution parameter(s).

Let us point out major differences between our approaches and approaches suggested in the other works on cooperative game theory for network clustering. In [START_REF] Zhou | Using coalitional games to detect communities in social networks[END_REF], a cooperative game theory approach based on Shapley value has been proposed. However, with the proposed characteristic function, the players tend to form the grand coalition. In the subsequent work [START_REF] Zhou | A game theory based approach for community detection in social networks[END_REF], a new characteristic function has been proposed, which combines both link-based as well as attribute-based information. The Shapley value associated with that characteristic function is very cumbersome to compute in comparison to the Myerson value for the characteristic function proposed in the first part of our paper. Of course, we admit that the computation of any type of Shapley value is computationally demanding and this is why we propose the second approach which has an efficient, naturally distributed, computational implementation.

The authors of [START_REF] Mcsweeney | A game theoretic framework for community detection[END_REF] have also proposed to use hedonic games for community detection. They consider only the modularity metric as value function. They have suggested an additional voting mechanism to overcome the resolution problem. Their algorithm is a version of greedy optimization. Our approach is much more general: not only we show that the modularity optimization is a particular case of our approach but we also demonstrate that such known methods as ratio cut and normalized cut are also particular cases of our approach. We also propose a couple of new functions that overcome the resolution problem without a need of additional voting mechanism. Our Gibbs samplingbased algorithm can be used with both fixed and decreasing temperature and hence can be used for local as well as global maxima search. Setting the temperature to a very low value corresponds to the greedy approach.

The authors of [START_REF] Basu | Community detection based on strong nash stable graph partition[END_REF] in the first part of their paper propose to use the concept of strong Nash equilibrium in addition to the concept of hedonic games. They also define a community as a ( , γ )-relaxation of the clique. There are several serious problems with their propositions. First of all, the strong Nash equilibrium might not exist (they acknowledge this fact themselves in their work), and such equilibrium is very hard to compute even if it exists. Furthermore, they give two definitions of a maximal ( , γ )-relaxation of the clique which are contradictory and therefore their algorithm can cycle.

We also note that our approaches based on cooperative games easily work with multigraphs, where several edges (links) are possible between two nodes. A multi-edge has several natural interpretations in the context of social networks. A multi-edge can represent a number of telephone calls; a number of exchanged messages; a number of common friends; or a number of co-occurrences in some social event.

Let us now summarize the main contributions of the paper (we place * in the items, which are new additions to the work in comparison with the conference version [START_REF] Avrachenkov | Cooperative game theory approaches for network partitioning[END_REF]):

• First the cooperative game theory approach based on the Myerson value is proposed for network partitioning. • Then the hedonic coalition formation framework is proposed for network partitioning which has more efficient computational implementation than the approach based on the Myerson value. • New interpretation in terms of hedonic games is given to modularity, ratio cut, and normalized cut network partitioning methods. * • Two new network partitioning methods based on potential hedonic games are proposed. (One method is a new addition with respect to the conference paper [START_REF] Avrachenkov | Cooperative game theory approaches for network partitioning[END_REF].) * These two methods are especially well suited to find partitions with different levels of resolution; the methods use only one or two parameters. We provide recommendations how to set these parameters.

• For methods constructed on potential hedonic games, we suggest to use a very efficient computational algorithm based on Gibbs sampling. * • Several numerical evaluations using real * as well as synthetic networks are carried out. These numerical evaluations in particular demonstrate the efficacy of the clustering methods based on potential hedonic games with resolution regularization.

The paper is structured as follows: in the following section, we provide necessary definitions from graph theory, network partitioning, and network games. Then, in "Myerson cooperative game approach" section, we present our first approach based on the Myerson value. The second approach based on the hedonic games is presented in "Hedonic coalition game approach" section. In both "Myerson cooperative game approach and Hedonic coalition game approach" sections, we provide small illustrative examples to explain the essence of the methods. In "Numerical validation" section, we evaluate our methods on a number of real as well as synthetic network examples. Finally, "Conclusion and future research" section provides conclusions and directions for future research.

Preliminaries of graph theory, network partitioning, and network stability

Let g = (N , E) denote an undirected multi-graph consisting of the set of nodes N and the set of edges E. We denote an edge (link) between node i and node j as ij. The interpretation is that if ij ∈ E , then the nodes i ∈ N and j ∈ N have a direct connection in network g, while ij / ∈ E , then nodes i and j are not directly connected. Since we generally consider a multi-graph, there could be several edges between a pair of nodes. Multiple edges can be interpreted for instance as a number of telephone calls or as a number of message exchanges in the context of social networks. We view the nodes of the network as players in a cooperative game. Let N (g) = {i : ∃j such that ij ∈ E(g)} . For a graph g, a sequence of different nodes {i 1 , i 2 , . . . , i k }, k ≥ 2 , is a path connecting i 1 and i k if for all h = 1, . . . , k -1 , i h i h+1 ∈ g .

The length l of a path is the number of edges in that path, i.e., l = k -1 . A path with no repeated nodes is called a simple path. Graph g on the set N is connected graph if for any two nodes i and j there exists a path in g connecting i and j.

We refer to a subset of nodes S ⊂ N as a coalition. The coalition S is connected if any two nodes in S are connected by a path which consists of nodes from S. The graph g ′ is a (connected) component of g, if for all i ∈ N (g ′ ) and j ∈ N (g ′ ) , there exists a path in g ′ connecting i and j, and for any i ∈ N (g ′ ) and j ∈ N (g) , ij ∈ g implies that ij ∈ g ′ . Let N|g be the set of all (connected) components in g and let g|S be the subgraph with the nodes in S.

Let gij denote the graph obtained by deleting edge ij from the graph g and g + ij denote the graph obtained by adding edge ij to the graph g.

The result of community detection is a partition of the network (N, E) into subsets (coalitions) {S 1 , . . . , S K } such that S k ∩ S l = ∅, ∀k, l and S 1 ∪ ... ∪ S K = N . This partition is internally stable or Nash stable if for any player from coalition S k it is not profitable to join another (possibly empty) coalition S l . We also say that the partition is externally stable if for any player i ∈ S l for whom it is beneficial to join a coalition S k , there exists a player j ∈ S k for whom it is not profitable to include there player i. The payoff definition and distribution will be discussed in the following two sections.

Myerson cooperative game approach

In general, a cooperative game of n players is a pair < N , v > where N = {1, 2, . . . , n} is the set of players and v: 2 N → R is a map prescribing for a coalition S ∈ 2 N some value v(S) such that v(∅) = 0 . This function v(S) is the total utility that members of S can jointly attain. Such a function is called the characteristic function of cooperative game. An interested reader can find more details on cooperative games in e.g., [START_REF] Myerson | Game Theory[END_REF][START_REF] Peleg | Introduction to the theory of cooperative games[END_REF][START_REF] Mazalov | Mathematical game theory and applications[END_REF].

Additionally, as in [START_REF] Myerson | Graphs and cooperation in games[END_REF], we assume that the cooperation is restricted by a network. The payoff to an individual player is called an imputation. The imputation specifies how the value associated with the network is distributed to the individual players. The imputation in our cooperative game will be based on the Myerson value [START_REF] Mazalov | Generating functions and the myerson vector in communication networks[END_REF][START_REF] Mazalov | Game-theoretic centrality measures for weighted graphs[END_REF][START_REF] Myerson | Graphs and cooperation in games[END_REF] which was designed to take into account the effect of the network.

The Myerson value [START_REF] Myerson | Graphs and cooperation in games[END_REF] is the allocation rule where Y i (v, g) is the payoff allocated to player i from graph g under the characteristic function v. The Myerson value is uniquely determined by the following two axioms [START_REF] Myerson | Graphs and cooperation in games[END_REF]:

Axiom 1 If S is a connected component of g, then the members of the coalition S ought to allocate to themselves the total value v(S) available to them, i.e., ∀S ∈ N |g, Axiom 2 ∀g, ∀ij ∈ g both players i and j obtain equal payoffs after adding or deleting a link ij, Characteristic function (payoff of coalition S) can be defined in different ways. Here we use a general idea from [START_REF] Mazalov | Generating functions and the myerson vector in communication networks[END_REF][START_REF] Mazalov | Game-theoretic centrality measures for weighted graphs[END_REF][START_REF] Mo | Allocation rules for network games[END_REF][START_REF] Mo | Social and economic networks[END_REF], which is based on discounting paths. However, unlike [START_REF] Mazalov | Generating functions and the myerson vector in communication networks[END_REF][START_REF] Mazalov | Game-theoretic centrality measures for weighted graphs[END_REF][START_REF] Mo | Allocation rules for network games[END_REF][START_REF] Mo | Social and economic networks[END_REF], we do not consider shortest paths but rather simple paths.

Y (v, g) = (Y 1 (v, g), . . . , Y n (v, g)), (1) i∈S
Y i (v, g) = v(S).
(2)

Y i v, g -Y i v, g -ij = Y j v, g -Y j v, g -ij .
Let us elaborate a bit more on the construction of the characteristic function. Each edge (or direct connection) gives to coalition S the value r, where 0 ≤ r ≤ 1 . Moreo- ver, players obtain a value from indirect connections. Namely, each simple path of length 2 belonging to coalition S gives to this coalition the value r 2 , a simple path of length 3 gives to the coalition the value r 3 , etc. Set Thus, for any coalition S, we can define the characteristic function as follows:

where a k (g, S) is the number of simple paths of length k in this coalition. Note that we write as infinity the limit of summation only for convenience. Clearly, the length of a simple path is bounded by n -1 . The following theorem provides a convenient way to calculate the Myerson value corresponding to the characteristic function [START_REF] Fortunato | Community detection in networks: a user guide[END_REF].

Theorem 1 Let the characteristic function of a coalition S ∈ 2 N be defined by Eq. (3).

Then the Myerson value of a node i is given by where a (i) k is the number of simple paths of length k containing node i.

Proof We shall prove the theorem by checking directly the Myerson value axioms, i.e., Axioms 1 and 2.

First, we note the following:

Since every simple path contains k + 1 different nodes, every simple path of the length k

is counted k + 1 times in the sum i∈S a (i) k (g, S).
Thus, Axiom 1 is satisfied:

For ij ∈ g , let a (ij)
k (g, S) denote the number of paths of length k traversing the edge ij. Then Thus, Axiom 2 is satisfied as well.

v(i) = 0, ∀i ∈ N . (3) v(S) = a 1 (g, S)r + a 2 (g, S)r 2 + • • • = ∞ k=1 a k (g, S)r k , (4) Y i (v, g) = a (i) 1 (g, S) 2 r + a (i) 2 (g, S) 3 r 2 + • • • = ∞ k=1 a (i) k (g, S) k + 1 r k , (k + 1)a k (g, S) = i∈S a (i) k (g, S). i∈S Y i (v, g) = i∈S ∞ k=1 a (i) k (g, S) k + 1 r k = i∈S a k (g, S)r k = v(S). a (i) k (g, S) -a (i) k (g -ij, S) = a (ij) k (g, S) = a (j) k (g, S) -a (j) k (g -ij, S) .
We can propose the following algorithm for network partitioning based on the Myerson value: Start with a partition of the network N = {1, . . . , n} , where each node forms her own coalition. Consider a coalition S l and a player i ∈ S l . In the cooperative game with partial cooperation presented by the graph g|S l , we find the Myerson value for player i, Y i (g|S l ) . This is the reward of player i in coalition S l . Suppose that player i decides to join the coalition S k . In the new cooperative game with partial cooperation presented by the graph g|S k ∪ i, we find the Myerson value Y i (g|S k ∪ i) . So, if for the player i ∈ S l : Y i (g|S l ) ≥ Y i (g|S k ∪ i) then player i has no incentive to join to new coali- tion S k , otherwise the player changes the coalition.

The partition N = {S 1 , . . . , S K } is the Nash stable or internally stable if for any player there is no incentive to move from her coalition. Notice that our definition of the characteristic function implies that for any coalition it is always beneficial to accept a new player (of course, for the player herself it might not be profitable to join that coalition). Thus, it is important that in the above algorithm, we consider the internal and not external stability. If one makes moves according to the external stability, then the result will always be the grand coalition.

We would like to note that the above approach also works in the case of multigraphs, where several edges (links) are possible between two nodes. In such a case, if two paths contain different links between the same pair of nodes, we consider these paths as different.

Example 1 Consider a weighted network of six nodes, N = {A, B, C, D, E, F } , presented in Fig. 1a. First, we transform this weighted graph to the multi-graph as shown in Fig. 1b.

A natural way of partition of this network is {S 1 = {A, B, C}, S 2 = {D, E, F }} . Let us determine under which condition this structure will present the internally stable partition.

Suppose that the characteristic function is defined by (3). To calculate the imputations, we use the formula (4) from Theorem 1. In the coalition S 1 , node A partici- pates in 2 simple paths of length 1 {{A, B}, {A, C}} and in 5 simple paths of length 2 {{A, B, C}, {A, B, C}, {A, C, B}, {A, C, B}, {B, A, C}} (note that since the network example is a multi-graph we count twice the paths {A,B,C} and {A,C,B}). Thus, we have In the coalition S 2 ∪ A , node A participates in 1 simple path of length 1 {A, D} , in 2 simple paths of length 2 {{A, D, E}, {A, D, F }} and in 4 simple paths of length 3 {{A, D, E, F }, {A, D, E, F }, {A, D, F , E}, {A, D, F , E}} (again these paths are counted twice for the multi-graph). Thus, We see that for player A it is not profitable to move from S 1 to S 2 ∪ A , if

Y A (g|S 1 ) = 2 2 r + 5 3 r 2 . Y A (g|S 2 ∪ A) = 1 2 r + 2 3 r 2 + 4 4 r 3 . 1 2 r + r 2 -r 3 > 0,
which is valid for all r in the interval (0, 1]. Therefore, in this partition node, A has no incentive to change the coalition under any choice of r. Now consider a slightly modified example, where we change the weight 2 on the edge {B, C} to weight 1 (see Fig. 2). This change results in the following imputations: and We see that now

Y A (g|S 2 ∪ A) > Y A (g|S 1 ) , if r > (1 + √ 19
)/6 ≈ 0.89 . Thus, if r is suf- ficiently large, the partition {S 1 , S 2 } becomes internally unstable and the grand coalition becomes the only stable configuration.

In the above example the parameter r can be used to tune the resolution of network partitioning. Resolution scale tuning will be even more natural in the next approach. We shall see that the next approach is also much more computationally efficient than the Myerson value-based approach.

Y A (g|S 1 ) = 2 2 r + 3 3 r 2 , Y A (g|S 2 ∪ A) = 1 2 r + 2 3 r 2 + 4 4 r 3 .

Hedonic coalition game approach

There is another game-theoretic approach for partitioning society into coalitions based on the ground-breaking work [START_REF] Bogomolnaia | The stability of hedonic coalition structures[END_REF] on hedonic games. Assume that the set of players N = {1, . . . , n} is divided into K coalitions by the parti- tion � = {S 1 , . . . , S K } . Let S � (i) denote the coalition S k ∈ such that i ∈ S k . A hedonic game is defined in terms of player preferences for various coalitions. A player i preferences are represented by a complete, reflexive, and transitive binary relation i over the set {S ⊂ N : i ∈ S} . Denote by ≻ i the strict part of this relation.

Let us now apply the framework of hedonic games [START_REF] Bogomolnaia | The stability of hedonic coalition structures[END_REF] to network partitioning problem, particularly, specifying the preferences. First, in the next subsection, we consider the case of additively separable preferences and then in "The case of non-additively separable preferences" section, we consider the case of non-additively separable preferences.

The case of additively separable preferences

The preferences are additively separable [START_REF] Bogomolnaia | The stability of hedonic coalition structures[END_REF] if there exists a value function

v i : N → R such that v i (i) = 0 and The preferences {v i , i ∈ N } are symmetric, if v i (j) = v j (i) = v ij = v ji
for all i, j ∈ N . The symmetry property defines a very important class of hedonic games.

As in the previous section, the network partition is Nash stable, if S � (i) � i S k ∪ {i} for all i ∈ N , S k ∈ ∪ {∅} . In the Nash-stable partition, there is no player who wants to leave her coalition.

A potential of a coalition partition � = {S 1 , . . . , S K } (see [START_REF] Bogomolnaia | The stability of hedonic coalition structures[END_REF]) is One natural method for detecting a stable community structure can be based on the following better response type dynamics:

Start with any partition of the network N = {S 1 , . . . , S K } . Choose any player i and any coalition S k different from S � (i) . If S k ∪ {i} ≻ i S � (i) , assign node i to the coalition S k ; otherwise, keep the partition unchanged and choose another pair of node-coalition, etc.

Since the game has the potential (5), the above algorithm is guaranteed to converge in a finite number of steps.

Proposition 1 If players' preferences are additively separable and symmetric

( v ii = 0, v ij = v ji
for all i, j ∈ N ), then the coalition partition giving a local maximum of the potential P(�) is the Nash-stable partition.

S 1 � i S 2 ⇔ j∈S 1 v i (j) ≥ j∈S 2 v i (j).
(5)

P(�) = K k=1 P(S k ) = K k=1 i,j∈S k v ij .
One natural way to define a symmetric value function v with a parameter α ∈ [0, 1] is as follows:

For any subgraph g|S, denote the number of nodes in S as n(S), and the number of edges in S as m(S). Then, for the value function [START_REF] Schaeffer | Graph clustering[END_REF], the potential (5) takes the form We can characterize the limiting cases α → 0 and α → 1 . Towards this goal, let us introduce a special decomposition of the network into cliques. At first, let us find a maximum clique S 1 in the network G (a maximum clique of a graph, is a clique, such that there is no clique with more vertices). Remove all vertices of S 1 from G and consider the new network G ′ . Let us find a maximum clique S 2 in the network G ′ and continue this procedure until we derive the partition {S 1 , ..., S K } of the network G into cliques. Call this partition the sequential decomposition of the network into maximum cliques.

Proposition 2 If α = 0 , the grand coalition partition N = {1, . . . , n} gives the maxi- mum of the potential [START_REF] Avrachenkov | Pagerank based clustering of hypertext document collections[END_REF]. Whereas if α → 1 , the network sequential decomposition into maximum cliques corresponds to a maximum of the potential [START_REF] Avrachenkov | Pagerank based clustering of hypertext document collections[END_REF].

Proof It is immediate to check that for α = 0 the grand coalition partition N gives the maximum of the potential [START_REF] Avrachenkov | Pagerank based clustering of hypertext document collections[END_REF], and P α (N ) = m(N ).

For values of α closed to 1, the partition into maximum cliques � = {S 1 , . . . , S K } gives the maximum of [START_REF] Avrachenkov | Pagerank based clustering of hypertext document collections[END_REF]. Indeed, assume that a player i from the clique S � (i) of the size m 1 moves to a clique S j of the size m 2 < m 1 . The player i ∈ S � (i) and S j are connected by at most m 2 links. The impact on P α (�) of this movement is not higher than Now, suppose that player i from the clique S � (i) moves to a clique S j of the size m 2 ≥ m 1 . Notice that clique S j was constructed in the procedure of sequential decomposition before the clique S � (i) . The player i ∈ S � (i) is connected with the clique S j by at most m 2 -1 links. Otherwise, the clique S j can be increased by adding node i and this con- tradicts the fact that S j was a maximum clique at the procedure of decomposition. If i has an incentive to move from S � (i) to the clique S j , then for new partition the sum [START_REF] Avrachenkov | Pagerank based clustering of hypertext document collections[END_REF] would not be higher than for partition by For α close to 1, this impact is negative, so there is no incentive to join the coalition S j . [START_REF] Schaeffer | Graph clustering[END_REF]

v ij =    1 -α, (i, j) ∈ E, -α, (i, j) / ∈ E, 0, i = j. ( 7
) P α (�) = K k=1 m(S k ) -α n(S k )(n(S k ) -1) 2 . m 2 (1 -α) -(m 1 -1)(1 -α) ≤ 0. m 2 -1 -m 2 α -(m 1 -1)(1 -α) = m 2 -m 1 -α(m 2 -m 1 + 1).
The grand coalition and the sequential maximum clique decomposition are two extreme partitions into communities. By varying the parameter α we can easily tune the resolution of the community detection algorithm.

(N ) = 78 -325α , P({N 1 , N 2 ∪ N 3 ∪ N 4 }) = 77 -181α , P({N 1 , N 2 ∪ N 3 , N 4 }) = 76 -104α , P({N 1 , N 2 , N 3 , N 4 }) = 74 -74α.
Other coalition partitions give smaller potentials:

P({N 1 ∪ N 2 , N 3 ∪ N 4 }) = 76 -156α < 76 -104α , P({N 1 ∪ N 2 ∪ N 3 , N 4 }) = 77 -192α < 77 -181α , P({N 1 , N 2 , N 3 ∪ N 4 }) = 75 -116α < 76 -104α , P({N 1 ∪ N 2 , N 3 , N 4 }) = 75 -114α < 76 -104α.
We solve a sequence of linear inequalities in order to find maximum of the potential for all α ∈ [0, 1] . The result is presented in the table.

Nash-stable coalition partitions in Example 2

α

Coalition partition Potential

[0, 1/144] N 1 ∪ N 2 ∪ N 3 ∪ N 4 78 -325α [1/144, 1/77] N 1 , N 2 ∪ N 3 ∪ N 4 77 -181α [1/77, 1/15] N 1 , N 2 ∪ N 3 , N 4 76 -104α [1/15, 1] N 1 , N 2 , N 3 , N 4 74 -74α
Example 1 (ctnd) Note that for the unweighted version of the network example presented in Fig. 1, there are only two stable partitions: = N for small values of α ≤ 1/9 and = {{A, B, C}, {D, E, F }} for α > 1/9.

Another natural approach to define a symmetric value function is, roughly speaking, to compare the network under investigation with the configuration random graph model. The configuration random graph model can be viewed as a null model Fig. 3 Graph with four fully connected subgraphs for a network with no community structure. Namely, the following value function can be considered:

where A ij is the number of links between nodes i and j (multi-graph is allowed), d i and d j are the degrees of nodes i and j, respectively, m = 1 2 l∈N d l is the total number of links in the network, and β ij = β ji and δ are some parameters.

Note that if β ij = β, ∀i, j ∈ N , and δ = 1 , the potential (7) coincides with the network modularity [START_REF] Girvan | Community structure in social and biological networks[END_REF][START_REF] Newman | Modularity and community structure in networks[END_REF]. If β ij = β, ∀i, j ∈ N , and δ � = 1 , we obtain the generalized modularity presented first in [START_REF] Reichardt | Statistical mechanics of community detection[END_REF]. The introduction of the non-homogeneous weights was proposed in [START_REF] Waltman | A unified approach to mapping and clustering of bibliometric networks[END_REF] with the following particularly interesting choice:

The introduction of the resolution parameter δ allows one to obtain clustering with vary- ing granularity as well as to overcome the resolution limit [START_REF] Fortunato | Resolution limit in community detection[END_REF].

Thus, we now have an interpretation based on coalition game of the modularity method. Namely, the coalition partition � = {S 1 , . . . , S K } which maximizes the modularity gives the Nash-stable partition of the network in the hedonic game with the value function defined by [START_REF] Avrachenkov | Graph clustering based on mixing time of random walks[END_REF] with δ = 1 and β ij = β.

Example 1 (ctnd) For the network example presented in Fig. 1, we calculate P(N ) = 3/2, P({B, C} ∪ {A, D} ∪ {E, F }) = P({A, B, C, D} ∪ {E, F }) = 7/2 and P({A, B, C} ∪ {D, E, F }) = 5 . Thus, according to the value function [START_REF] Avrachenkov | Graph clustering based on mixing time of random walks[END_REF] with δ = 1 and β ij = β (modularity value function), = {{A, B, C}, {D, E, F }} is the unique Nash-stable coalition partition.

The case of non-additively separable preferences

Now let us consider a few cases of non-additively separable preferences which still have potentials. First, we consider a slight modification of preference structure (6) which makes it non-additively separable. Namely, define the preference relation as follows:

where 1{•} is the indicator function, giving one if the argument is true, v ij is defined as before in [START_REF] Schaeffer | Graph clustering[END_REF], and γ is a parameter representing the cost of coalition creation and allows us to control further the clustering resolution and granularity. As verified in the following proposition, in this case the game also has a potential. [START_REF] Avrachenkov | Graph clustering based on mixing time of random walks[END_REF]

v ij = β ij A ij -δ d i d j 2m , β ij = 2m d i d j . ( 9
) P(�) = K k=1 i,j∈S k ,i� =j A ij - d i d j 2m (10) S 1 � i S 2 ⇔ j∈S 1 v ij -γ 1{S 1 � = ∅} ≥ j∈S 2 v ij -γ 1{S 2 � = ∅},

Proposition 3 The hedonic clustering game defined by the preference relation (10) has the following potential:

Proof Suppose that partition = {S 1 , ..., S K } maximizes the function [START_REF] Newman | A measure of betweenness centrality based on random walks[END_REF], possibly locally. Then, if i moves from S � (i) to S k , the value of ( 11) corresponding to the new par- tition ′ is different from the value corresponding to by note that K is not changing. If i creates its own cluster, then the value of (11) corresponding to ′ is different from that for by and in the case S � (i) = {i} , the difference is If provides a maximum of [START_REF] Newman | A measure of betweenness centrality based on random walks[END_REF], all these differences are negative. So, according to relation [START_REF] Meilă | A random walks view of spectral segmentation[END_REF], player i indeed has no incentive to move from her coalition S � (i) to another coalition and the function [START_REF] Newman | A measure of betweenness centrality based on random walks[END_REF] can be interpreted as a potential.

Let us provide a few recommendations for the choice of α and γ . Similarly to [START_REF] Reichardt | Statistical mechanics of community detection[END_REF], from the analysis of the mean field model corresponding to a stochastic block model (SBM), one can show that the value of α close to the link density ensures the internal stability of clusters in the mean field model of SBM. Thus, if a network has one main scale, such value of α gives good result. If a network has nested clustering structure, one can vary α to obtain clustering with the needed level of granularity. Again using the mean field model for SBM, one can show that the good value of γ corresponds to the product of α and the smallest size of the cluster we would like to obtain.

We mention that interestingly under a specific choice of parameters the globally optimal partition may contain disconnected clusters. However, such a choice of parameters is typically not natural.

Example 3 Let us consider a graph that consists of a clique of four nodes and two cliques of three nodes connected to it (see Fig. 4). [START_REF] Newman | A measure of betweenness centrality based on random walks[END_REF]

) P α,γ (�) = K k=1 m(S k ) -α n(S k )(n(S k ) -1) 2 -γ K . j∈S k v ij - j∈S � (i) v ij , -γ - j∈S � (i) v ij , j∈S k v ij + γ .
One can check that for α = 0.5 and γ = 5, the partitioning gives the maximum value to the potential P α,γ ( �) = -8.5 , while

An intuitive interpretation for this choice of parameters is that α is chosen significantly large to encourage splitting of clusters from the grand coalition and γ is also chosen sig- nificantly large to penalize the creation of independent clusters.

Next we would like to note that two well-known network partitioning methods: normalized cut [START_REF] Meilă | A random walks view of spectral segmentation[END_REF][START_REF] Shi | Normalized cuts and image segmentation[END_REF] and ratio cut [START_REF] Hagen | New spectral methods for ratio cut partitioning and clustering[END_REF] can also be viewed as particular instances of potential hedonic clustering games with non-additively separable preferences. Towards this end, let us introduce a few more definitions. Let S, T ⊂ N be two, possibly overlapping sets of nodes. Then, we define a cut W(S, T) as Note that an edge is counted twice if its both ends lie in the same set. The volume of a set S ∈ N is defined as the number of edges between its vertices

The normalized cut of a set S is defined by where S = N \S . If vol(S) = 0 , we define h NCUT (S) = +∞ . One can also define the ratio cut ˜ = {{0, 1, 2, 7, 8, 9}, {3, 4, 5, 6}} P α,γ ({{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}}) = -18.5, P α,γ ({{0, 1, 2, 3, 4, 5, 6}, {7, 8, 9}}) = -9, P α,γ ({{0, 1, 2}, {3, 4, 5, 6}, {7, 8, 9}}) = -9.

W (S, T ) = i∈S,j∈T 1{(i, j) ∈ E}. vol(S) = 1 2 W (S, S). h NCUT (S) = W (S, S) W (S, S) = 1 2 W (S, S) vol(S) , h RCUT (S) = W (S, S) |S| .

Fig. 4 Graph consisting of three cliques

Similar to the normalized cut, we assign h RCUT (S) = +∞ , if |S| = 0 , i.e., S = ∅ . Then, the normalized cut [START_REF] Meilă | A random walks view of spectral segmentation[END_REF][START_REF] Shi | Normalized cuts and image segmentation[END_REF] and ratio cut [START_REF] Hagen | New spectral methods for ratio cut partitioning and clustering[END_REF] network partitioning methods are based on the following potentials respectively. Similar to the proof of Proposition 3, one can check that the above potentials correspond to the following preferences: for the normalized cut and the ratio cut respectively. Thus, two more, well-known network partitioning methods can be cast into our general framework. A very important benefit of such interpretation is that in contrast to the original formulations, we now do not require a priori knowledge of the number of clusters.

Gibbs sampling approach for hedonic games with potential

We note that finding Nash equilibrium in a game with potential is equivalent to finding a maximum of the game's potential. To find a maximum of the game's potential, we can follow the approach based on Gibbs sampling. Let us consider the following Gibbsian distribution over all partitions:

It is easy to see that as β → ∞ , the distribution concentrates on the partition corre- sponding to the maximum of the potential P(�).

Next, denote by the set of indices of the network clusters and by � i→σ the (re)assign- ment of node i to cluster σ ∈ � and run the Glauber dynamics [START_REF] Reichardt | Statistical mechanics of community detection[END_REF][START_REF] Levin | Markov chains and mixing times[END_REF] according to [START_REF] Pons | Computing communities in large networks using random walks[END_REF]

) P NCUT (�) = - S∈� h NCUT (S), ( 13
) P RCUT (�) = - S∈� h RCUT (S), (14)
S 1 � i S 2 ⇔ W (S 1 {i}, S1 \{i}) vol(S 1 {i}) - W (S 1 , S1 \{i}) vol(S 1 ) ≤ W (S 2 {i}, S2 \{i}) vol(S 2 {i}) - W (S 2 , S2 \{i}) vol(S 2 ) (15)
S 1 � i S 2 ⇔ W (S 1 {i}, S1 \{i}) |S 1 | + 1 - W (S 1 , S1 \{i}) |S 1 | ≤ W (S 2 {i}, S2 \{i}) |S 2 | + 1 - W (S 2 , S2 \{i}) |S 2 | , ( 16
) ρ(�) = exp (βP(�)) ∀ � exp βP( �) . ( 17
) P �→� ′ = 1 n        � i∈N exp (βP(�)) � s∈� exp (βP(� i→s )) , if � ′ = �, exp (βP(� ′ )) � s∈� exp (βP(� i→s )) , if � ′ = � i→σ , 0, otherwise,
that is, we choose randomly a node and reassign this node to a new cluster according to the conditional Gibbsian distribution (clearly, it can happen that the node remains in its current cluster). It is well known that the Glauber dynamics corresponds to the reversible Markov chain with the stationary distribution given by [START_REF] Newman | Modularity and community structure in networks[END_REF], see e.g., [START_REF] Levin | Markov chains and mixing times[END_REF]. One can also cool down the temperature as in simulated annealing [START_REF] Hajek | Cooling schedules for optimal annealing[END_REF] in order to find the partition with the global maximum of the potential. We define one iteration as n updates of nodes according to [START_REF] Raghavan | Near linear time algorithm to detect community structures in large-scale networks[END_REF]. Typically and as will be demonstrated in the next section, if we take a reasonably high inverse temperature β , the process ( 17) often finds good-quality partition already after 5-10 iterations. The complexity of one iteration is very light in the case of sparse graphs, i.e.

, O(|E|).

A sample generated by the above-described Glauber dynamics appears to have significant variance. To reduce it, the generalized empirical covariance matrix of several samples can be used, similar to [START_REF] Berthet | Exact recovery in the ising blockmodel[END_REF] where the standard covariance matrix has been used for the case of two clusters. For one sample, the elements of the generalized covariance matrix are defined as follows:

The empirical generalized covariance matrix of a set of samples is the average of their generalized covariance matrices, i.e., An (i, j)th value of the generalized covariance matrix indicates how often the ith and jth nodes appear in the same cluster.

Then, given a generalized covariance matrix one can extract the community structure using threshold-based or PCA-based methods.

Numerical validation

In this section, we validate the proposed approaches on synthetic and real-world networks. As a benchmark, we take a widely used clustering method sklearn.cluster.spectralclustering from [START_REF] Pedregosa | Scikit-learn: machine learning in python[END_REF]. The method is based on the eigen elements of the normalized Laplacian and K-means postprocessing and have demonstrated good performance in many previous studies.

If it is available, the ground truth clustering is denoted by true and the clustering obtained by an algorithm as test . Each time we specify which algorithm we test against the ground truth. We measure the difference between these two partitions by the following function from [START_REF] Meilă | An experimental comparison of model-based clustering methods[END_REF]:

M (1) i,j = 1, if σ (i) = σ (j), -1, otherwise. . M = 1 T T t=1 M (t) . ( 18
) E(� true , � test ) = 1 - 1 n max π :� true →� test σ ∈� true n σ ,π(σ ) .

Synthetic network: stochastic block model

We first evaluate various clustering algorithms based on potential hedonic games on stochastic block model (SBM), a synthetic network with known community structure. An SBM with | | clusters is represented by a symmetric square matrix P where p σ ,σ is a den- sity of edges inside the cluster σ and p σ ,σ ′ = p σ ′ ,σ is a density between clusters σ and σ ′ . Specifically, we use SBM with two communities of 50 and 150 nodes, intra-cluster density p 11 = p 22 = 0.1 and inter-cluster density p 12 = p 21 = 0.02 . We start from a random coloring and run the process for 100 iterations. In Fig. 5, we show an example of the Glauber dynamics using NCUT potential [START_REF] Pons | Computing communities in large networks using random walks[END_REF]. For small β = 10 we observe unstable behavior, while for large β = 500 the process evolves around a local maximum that provides relatively bad clustering (49 out of 50 nodes of the first community and only 116 out of 150 of the second community are clustered correctly). Now let us take a closer look at RCUT [START_REF] Blatt | Clustering data through an analogy to the potts model[END_REF]. We discovered that in our example the ground truth partition does not maximize the potential. The process converges fast to a clustering that differs from the ground truth and has larger P RCUT than the ground truth partition. We tested the algorithm on a set of 100 graph instances generated according to the SBM and we show the results in Fig. 6 where we also compare it to the spectral clustering from [START_REF] Pedregosa | Scikit-learn: machine learning in python[END_REF]. One can see that while the Glauber dynamics generally ends up with P RCUT (� test ) > P RCUT (� true ) . The spectral clustering procedure provides a solu- tion that has smaller P RCUT but is closer to the ground truth.

Next let us evaluate the performance of the clustering based on the potential P α , see [START_REF] Avrachenkov | Pagerank based clustering of hypertext document collections[END_REF]. Empty clusters do not cause any singularities in P α unlike in P NCUT and P RCUT . Hence, the final partition can have less clusters than | | . Let us at first restrict the num- ber of clusters by setting = {0, 1} . In this context, we have two natural choices for ini- tial coloring of a graph: either, as before, we can choose colors uniformly at random, or we can assign same color to all nodes. We tested both settings on a set of 100 SBM graph instances. The best results are obtained with α = 0.05 and β = 10 . If we assign clusters at random at initialization, the process may not converge to a good coloring. Assigning the same initial color to all the nodes leads to better results. Fig. 7a andb shows evolution on the same graph with different initial colorings. The average E after 20 iterations for random-cluster initialization is 0.033, for single-cluster initialization it is 0.006; while the standard spectral clustering, i.e., the continuous relaxation of the NCUT [START_REF] Shi | Normalized cuts and image segmentation[END_REF] provides a result with average E(� true , � test ) = 0.025 . We can conclude that the P α -based clustering significantly outperforms the spectral clustering in terms of accuracy. However, it depends on the parameter α that determines the penalty for large clusters. If α is too small, the uniform coloring becomes the ground state, as already indicated in Proposition 2. If α is too large, the obtained clusters will be relatively of the same size but may not represent the real community structure.

We can also try to detect the real number of clusters, if we choose large . Here we can test the case when initially all nodes receive different colors | | = |V | . We discovered that the final clustering consists of 9 or 10 clusters on average, most of which contain very few nodes. See Fig. 7c for an example of such clustering process.

To prevent the problem described in the previous paragraph, we modify P α to P α,γ , see Eq. [START_REF] Newman | A measure of betweenness centrality based on random walks[END_REF], by introducing a penalty term proportional to the number of non-empty clusters. The potential P α,γ depends on parameters α and γ that determine penalties for disparate clusters and for the total number of them, respectively. We tested the respective Glauber dynamics on the same set of random instances of SBM with parameters α = 0.05 , γ = 5 , β = 10 , and | | = |V | = 200 . We run the process for 20 iterations and averaged the coloring over the last 10 of them. We obtained the following results: 2 clusters were determined in every graph instance and the average E(� true , � test ) is 0.0057. The average E(� true , � test ) for the spectral clustering is 0.0252.

In order to validate further the method based on P α,γ -potential, we tried it on dif- ferent sets of graphs of different clustering structures with the same algorithm parameters α , γ , and β . On a set of 100 homogeneous Erdős-Rényi random graphs of 200 nodes with edge density 0.1, our algorithm ended up with a uniform coloring on 99 of them and on one graph it finished with 2 clusters where the smaller one contains only two nodes. Given a set of 100 graph instances of SBM with clusters of 50, 150, and 200 nodes, the algorithm correctly determined the number of clusters in each graph and provided on average E(� true , � test ) = 0.006 , while spectral clustering provided on x-axis corresponds to the node index and y-axis corresponds to the iteration number. Different colors correspond to different clusters and 3 clusters for the others. The average E(� true , � test ) becomes 0.0185. The average E(� true , � test ) of the spectral clustering on the same set of graphs is 0.0375.

The above results can be further improved by using the generalized covariance matrix. The application of the generalized covariance matrix will be illustrated in some of the following network examples.

Real-world network with ground truth: Karate club

Consider the popular example of the social network from Zachary karate club (see Fig. 8). In his study [START_REF] Zachary | An information flow model for conflict and fission in small groups[END_REF], Zachary observed 34 members of a karate club over a period of 2 years. Due to a disagreement developed between the administrator of the club and the club's instructor there appeared two new clubs associated with the instructor (node 1) and administrator (node 34) of sizes 16 and 18, respectively.

The authors of [START_REF] Girvan | Community structure in social and biological networks[END_REF] divide the network into two groups of roughly equal size using modularity and hierarchical clustering tree. They show that this split corresponds almost perfectly with the actual division of the club members following the break-up. Only one node, node 3, is classified incorrectly by the method of [START_REF] Girvan | Community structure in social and biological networks[END_REF].

Let us first apply the Myerson value approach to the karate club network. To perform the analytic study, let us start from the ground truth partition [START_REF] Zachary | An information flow model for conflict and fission in small groups[END_REF] By using subindex 3, we emphasize the importance of player 3. By enumerating all simple paths and using formula (4), we find the Myerson value for player 3 in coalition R 3 and in the coalition 3, 4, 5, 6, 7, 8, 11, 12, 13, 14, 17, 18, 20, 22} and We have plotted both Y 3 (g|R 3 ) and Y 3 (g|L 3 ∪ {3}) as functions of r in Fig. 9. If r is smaller than 0.231, node 3 has no incentive to move from coalition R 3 to coalition L 3 . Recall that the modularity-based method of [START_REF] Girvan | Community structure in social and biological networks[END_REF] would displace player 3 into the wrong coalition L 3 .

L 3 ∪ {3} R 3 = {1, 2,
L 3 = N \ R 3 . Y 3 (g|R 3 ) = 5 2
It is also interesting to investigate the imputations of the other two border nodes 9 and 10. If we plot the imputations for node 10: Y 10 (g|L 3 ) and Y 10 (g|R 3 ∪ {10}) (see Fig. 10), we observe that as for node 3, for smaller values of r (i.e., for r < 0.363 ), node 10 has no incentive to leave the coalition L 3 ; whereas for the values of r greater than 0.363, node 10 has incentive to change the coalition.

As it is clear from Fig. 11, node 9 has no incentive to leave the coalition L 3 with any value of r. Thus, we can conclude that the ground truth partition [START_REF] Zachary | An information flow model for conflict and fission in small groups[END_REF] is internally stable according to the Myerson value approach if r < 0.231 . This has a nice intuitive interpretation. Humans cannot count easily long paths and consequently one needs to apply heavy discounting to mimic humans' decisions.

Let us now apply the hedonic game approach with Glauber dynamics to the karate club network. We started from a random partition into two clusters and run the algorithm using the potential [START_REF] Avrachenkov | Pagerank based clustering of hypertext document collections[END_REF] with α = 0.046 , which corresponds to 1/3 of the edge density, and β = 20 . The algorithm stabilizes after around 5 iterations and the mean error after 10 iterations in 100 runs was 20.0%, which roughly corresponds 7 misclassified nodes. However, the partitioning results differ significantly from run to run.

By applying the spectral clustering algorithm from [START_REF] Pedregosa | Scikit-learn: machine learning in python[END_REF] to Zachary karate club network, we obtain an average error of 25.8%.

To reduce the variance of the Glauber dynamics and hence the clustering error, we computed the empirical generalized covariance matrix M for the results of 10 independent runs of 10 iterations of the Glauber dynamics and then extracted the community structure using the PCA algorithm. Only node 9 was misclassified, which is a border node. The application of the generalized covariance matrix in addition to the Gibbs sampling really helps to consistently obtain high-quality results.

We would like to note that the application of the generalized covariance matrix to the spectral clustering method from [START_REF] Pedregosa | Scikit-learn: machine learning in python[END_REF] does not improve significantly its results since spectral clustering gives less noisy, however, more biased results compared to the hedonic game approach.

Real-world network with ground truth: Dolphins

Consider now the Dolphins social network from [START_REF] Lusseau | The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[END_REF]. This network presented in Fig. 12 was constructed from observations of a community of 62 bottle nose Dolphins over a period of 7 years from 1994 to 2001. The nodes in the network represent the Dolphins, and the ties between nodes represent the associations between dolphin pairs occurring more often than expected by chance. The ground truth partition is presented by two coalitions: and We studied the Dolphins network using the hedonic game approach with Glauber dynamics in a similar way as we did for Zachary karate club. Note that because of a very large number of simple paths in this network, the application of the Myerson value approach was not feasible. The following parameter values were used: α = 0.028 , which corresponds to 1/3 of the edge density, and β = 20 . The algorithm stabilizes after around 10 iterations and the mean error after 20 iterations in 100 runs was 24.8%. As with Zachary karate club, the partitioning results differ significantly from run to run.

By applying the spectral clustering algorithm from [START_REF] Pedregosa | Scikit-learn: machine learning in python[END_REF], we obtain an average error of 7.5%.

We computed the empirical generalized covariance matrix M of the results of 10 inde- pendent runs of 20 iterations of the Glauber dynamics and then extracted the community structure using the PCA algorithm. Then, only one node, node 39, was misclassified. This is a border node connected to only two nodes of different clusters.

In contrast, computing the covariance matrix of 10 results of independent runs of spectral clustering algorithm from [START_REF] Pedregosa | Scikit-learn: machine learning in python[END_REF] led to 4 misclassified nodes: 22, 31, 48, 60.

Real-world network with many clusters and ground truth: Football

The American College Football network [START_REF] Girvan | Community structure in social and biological networks[END_REF] represents the games between Division IA Colleges during the regular fall 2000 season (see Fig. 13).

The nodes in the network represent the teams and the links are the games between the teams. There are 115 teams and each team belongs to one of the 12 conferences. The communities in the network are the conferences. So, the ground truth partition is given by 12 coalitions: L = {1, [START_REF] Luxburg | A tutorial on spectral clustering[END_REF][START_REF] Schaeffer | Graph clustering[END_REF][START_REF] Avrachenkov | Pagerank based clustering of hypertext document collections[END_REF][START_REF] Dongen | Performance criteria for graph clustering and Markov cluster experiments[END_REF][START_REF] Blatt | Clustering data through an analogy to the potts model[END_REF][START_REF] Raghavan | Near linear time algorithm to detect community structures in large-scale networks[END_REF][START_REF] Waltman | A unified approach to mapping and clustering of bibliometric networks[END_REF][START_REF] Mazalov | Game-theoretic centrality measures for weighted graphs[END_REF][START_REF] Szczepański | A new approach to betweenness centrality based on the shapley value[END_REF][START_REF] Michalak | Efficient computation of the shapley value for game-theoretic network centrality[END_REF][START_REF] Chen | Interplay between social influence and network centrality: a comparative study on shapley centrality and single-node-influence centrality[END_REF][START_REF] Leskovec | Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters[END_REF][START_REF] Hagen | New spectral methods for ratio cut partitioning and clustering[END_REF][START_REF] Myerson | Graphs and cooperation in games[END_REF][START_REF] Meilă | An experimental comparison of model-based clustering methods[END_REF]54,56, 57, 60} R = {0, 2, [START_REF] Fortunato | Community detection in networks: a user guide[END_REF][START_REF] Jonnalagadda | A survey on game theoretic models for community detection in social networks[END_REF][START_REF] Avrachenkov | Graph clustering based on mixing time of random walks[END_REF][START_REF] Meilă | A random walks view of spectral segmentation[END_REF][START_REF] Newman | A measure of betweenness centrality based on random walks[END_REF][START_REF] Pons | Computing communities in large networks using random walks[END_REF][START_REF] Blondel | Fast unfolding of communities in large networks[END_REF][START_REF] Girvan | Community structure in social and biological networks[END_REF][START_REF] Newman | Modularity and community structure in networks[END_REF][START_REF] Reichardt | Statistical mechanics of community detection[END_REF][START_REF] Mcsweeney | A game theoretic framework for community detection[END_REF][START_REF] Mazalov | Generating functions and the myerson vector in communication networks[END_REF][START_REF] Gomez | Centrality and power in social networks: a game theoretic approach[END_REF][START_REF] Suri | Proceedings of the 7th international joint conference on autonomous agents and multiagent systems[END_REF][START_REF] Skibski | Axiomatic characterization of game-theoretic centrality[END_REF][START_REF] Bogomolnaia | The stability of hedonic coalition structures[END_REF][START_REF] Fortunato | Resolution limit in community detection[END_REF][START_REF] Shi | Normalized cuts and image segmentation[END_REF][START_REF] Zhou | Using coalitional games to detect communities in social networks[END_REF][START_REF] Zhou | A game theory based approach for community detection in social networks[END_REF][START_REF] Basu | Community detection based on strong nash stable graph partition[END_REF][START_REF] Avrachenkov | Cooperative game theory approaches for network partitioning[END_REF][START_REF] Myerson | Game Theory[END_REF][START_REF] Peleg | Introduction to the theory of cooperative games[END_REF][START_REF] Mazalov | Mathematical game theory and applications[END_REF][START_REF] Mo | Allocation rules for network games[END_REF][START_REF] Mo | Social and economic networks[END_REF][START_REF] Levin | Markov chains and mixing times[END_REF][START_REF] Hajek | Cooling schedules for optimal annealing[END_REF][START_REF] Berthet | Exact recovery in the ising blockmodel[END_REF][START_REF] Pedregosa | Scikit-learn: machine learning in python[END_REF][START_REF] Zachary | An information flow model for conflict and fission in small groups[END_REF][START_REF] Lusseau | The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[END_REF][START_REF] Zhizhchenko | The information system Math-Net.Ru. Application of contemporary technologies in the scientific work of mathematicians[END_REF]52,53,55,58,59, 61}.

Fig. 12 Dolphins social network

As was the case of the Dolphins network, we could not apply the Myerson value approach to the football network because of the difficulty in enumerating all simple paths. In contrast, the hedonic game approach can easily be applied.

One of the main advantages of the hedonic game approach with P α,γ potential ( 11) is the fact that it does not require the number of clusters as a parameter. Let us test on the football network, which consists of 12 clusters, how the hedonic game approach with P α,γ potential can perform without a priori knowledge of the number of clusters.

We set the following parameters of the potential: α = 0.093 (edge density), γ = 10 . We run the Glauber dynamics with random initial partition into 20 clusters and the inverse noise β = 10 for 20 iterations. The clustering dynamics stabilizes after around 10 iterations. We performed 50 independent runs. The average number of detected clusters was 10.22 and the average percentage of misclassified nodes is 13.5%.

As with Zachary and Dolphins networks, we computed the empirical generalized covariance matrix of the clustering results. Since our goal was to determine the clusters without providing its number to the algorithm, we used a simple threshold-based clustering algorithm instead of the PCA algorithm: we build a weighted graph using the generalized covariance matrix as its adjacency matrix and removed the edges with The resulting graph contained 13 connected components, i.e., we identified 13 clusters in the initial network that is quite close to the ground truth value 12. The percentage of the misclassified nodes is 6.9%, which signifies that the generalized covariance matrix improved significantly the quality of the clustering results.

Large real-world network without ground truth: Co-authorships in Math-Net.ru

To test scalability and efficiency of the hedonic game approach, we have chosen to cluster a fairly large social network. We have crawled the site Math-Net.ru, Russian Mathematical Portal, for the co-authorship graph [START_REF] Zhizhchenko | The information system Math-Net.Ru. Application of contemporary technologies in the scientific work of mathematicians[END_REF]. We further extracted the giant connected component of this co-authorship network, which includes 41,840 authors. We have applied the hedonic game with the potential [START_REF] Avrachenkov | Pagerank based clustering of hypertext document collections[END_REF] and run the modified Glauber dynamics using round robin node schedule with random permutation. Twenty iterations of the modified Glauber dynamics run for about 2 min on Intel Core Duo 1.6 GHz processor and 5GB RAM. We have initialized process with a single cluster and restricted the number of clusters to ten. We have again observed stabilization of the modified Glauber dynamics at 15-20 iterations. Recall that one iteration of the modified Glauber dynamics requires O(|E|) operations, which is quite a reasonable cost in the case of sparse networks and which is the case of most real-world networks. We have chosen significantly high value of β , which corresponds to nearly greedy algorithm. First, we have run the modified Glauber dynamics with α corresponding to the average edge density. This has lead to unbalanced clusters, see Table 1. By expecting clusters, we have observed that nearly all academicians (aka leaders of scientific schools) have been clustered to one largest cluster. However, when we have increased α tenfold, the clustering became much more balanced and the academicians have been distributed more evenly among the clusters.

Large synthetic SBM network with ground truth

To continue testing scalability and efficiency of the hedonic game approach and in particular to confirm a rapid convergence of the Glauber dynamics to a good solution, we consider a large stochastic block model graph with known communities. Specifically, we have generated an SBM with two clusters of sizes 50,000 and 150,000 nodes. We have generated the intra-cluster links with probability 0.0002 and the inter-cluster links with probability 0.00005. We run the Glauber dynamics associated with the potential [START_REF] Avrachenkov | Pagerank based clustering of hypertext document collections[END_REF], setting α = 0.0001 and β = 10 . In a typical run, after 7 iterations, only 97 nodes from the smaller cluster were misclassified to the larger cluster and only 65 nodes from the larger cluster were misclassified to the smaller cluster. It is not surprising that by the "gravity" effect the larger cluster attracted more nodes. We find that 7 iterations of the Glauber dynamics are not at all a large cost for partitioning 200,000 node network.

Conclusion and future research

We have presented two cooperative game theory-based approaches for network partitioning. The first approach is based on the Myerson value for graph constrained cooperative game, whereas the second approach is based on hedonic games which explain coalition formation. We find the second approach especially interesting as it gives a very natural way to tune the clustering resolution and generalizes the modularity, ratio cut, and normalized cut-based approaches. Within the hedonic games framework, we have proposed two new methods which particularly well regularize clustering resolution and help to adjust the level of granularity. We have shown that normalized cut and ratio cut methods can be modified to avoid the requirement of the number of clusters.

All approaches that can be represented as hedonic games with potentials can be very efficiently implemented using Gibbs sampling with Glauber dynamics and generalized covariance matrix. The application of the generalized covariance matrix significantly improves the quality and stability of the clustering results. Our research plans are to test and to compare our methods on more social networks and to study analytically the convergence rate of Gibbs sampling.

Fig. 2 Fig. 1

 21 Fig. 2 Network of six nodes with changed weight

Example 2

 2 Consider graph G = (N , E) , which consists of n = 26 nodes and m = edges (see Fig. 3). This graph includes 4 fully connected subgraphs: G 1 with 8 vertices N connected by 28 links, G 2 with 5 vertices N 2 connected by 10 links, G 3 with 6 vertices N connected by 15 links, and G 4 with 7 vertices N 4 connected by 21 links. Subgraph G 1 is connected with G 2 by 1 edge, G 2 with G 3 by 2 edges, and G 3 with G 4 by 1 edge.Firstly, calculate the potentials[START_REF] Avrachenkov | Pagerank based clustering of hypertext document collections[END_REF] for large-scale decompositions of G for any parameter α ∈ [0, 1] . It is easy to check, that P

Fig. 5

 5 Fig. 5 The iterations of NCUT-based Glauber dynamics for different β ; P NCUT (� true ) = -1.40 . x-axis corresponds to the node index and y-axis corresponds to the iteration number. Different colors correspond to different clusters

Fig. 6 Fig. 7

 67 Fig. 6 The iterations of RCUT-based Glauber dynamics for β = 200 and comparison to the ground truth and spectral clustering

Fig. 9

 9 Fig. 9 Imputations for node 3 in Zachary karate club network: Y 3 (g|R 3 ) (solid line) vs Y 3 (g|L 3 ∪ {3}) (dashed line) in semilog scale

Fig. 10 Fig. 11

 1011 Fig. 10 Imputations for node 10 in Zachary karate club network: Y 10 (g|L 3 ) (solid line) vs Y 10 (g|R 3 ∪ {10}) (dashed line) in semilog scale

Fig. 13

 13 Fig. 13 Football network

  C 1 = [112,[START_REF] Meilă | An experimental comparison of model-based clustering methods[END_REF] 92,[START_REF] Levin | Markov chains and mixing times[END_REF] 75, 66, 91, 86, 57, 110]; C 2 = [50, 24, 69, 11, 97, 59, 63]; C 3 = [80, 82, 42, 36, 90]; C 4 = [45, 109, 37, 25, 1, 33, 103, 105, 89]; C 5 = [9, 4, 104, 0, 93, 16, 41, 23]; C 6 = [5, 74, 3, 98, 10, 40, 84, 81, 52, 102, 107, 72]; C 7 = [68, 108, 78, 77, 8, 51, 21, 22, 7, 111]; C 8 = [32, 6, 13, 47, 39, 100, 15, 106, 64, 60, 2]; C 9 = [61, 99, 43, 14, 12, 31, 38, 18, 54, 34, 71, 26, 85]; C 10 = [29, 19, 94, 35, 55, 30, 101, 79]; C 11 = [46, 67, 73, 83, 114, 88, 53, 49, 58, 28]; C 12 = [62, 65, 95, 17, 70, 56, 113, 27, 87, 20, 76, 96].

Table 1 Cluster sizes in Math-Net.ru

 1

	α	|S 1 |	|S 2 |	|S 3 |	|S 4 |	|S 5 |	|S 6 |	|S 7 |	|S 8 |	|S 9 |	|S 10 |
	0.000112	16,457	2820	2820	2820	2821	2821	2820	2821	2820	2820
	0.001124	4184	4184	4184	4185	4183	4184	4184	4184	4184	4184

Acknowledgements

We would like to thank the editor and the referees for very useful remarks and suggestions that helped to significantly improve the presentation of the results. The work of the first and fourth authors is partly supported by the joint laboratory Inria-Nokia Bell Labs, the joint Inria-UFRJ team THANES and by UCA-JEDI Idex Grant "HGAPHS. " The second and the third authors are supported by Russian Fund for Basic Research (Projects 16-51-55006, 16-01-00183). The third author is supported by Russian Science Foundation (Project 17-11-01709).

Authors' contributions

The contribution of all four authors to the manuscript is quite balanced. All authors read and approved the final manuscript.

Author details

Competing interests

The authors declare that they have no competing interests.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.