Mathematical optimization and social networks
Full text
Trabajo Fin de Grado Mathematical Optimization and Social Networks Presented by: Lourdes D´ıaz Mena Supervisors: Dr. Rafael Blanquero Bravo, Universidad de Sevilla Dr. Emilio Carrizosa Priego, Universidad de Sevilla June 22, 2015
Contents 1 Introduction 4 2 Basic concepts 5 2.1 Shortestpaths........................... 7 2.1.1 Linearprogram...................... 7 2.1.2 Dijkstra Algorithm . . . . . . . . . . . . . . . . . . . . 9 2.1.3 Floyd Algorithm . . . . . . . . . . . . . . . . . . . . . 11 3 Probabilistic models for social networks 15 3.1 The Erd¨os-R´enyi-Gilbert Random Graph Model . . . . . . . . 15 3.2 Exponential Random Graph Models . . . . . . . . . . . . . . . 17 3.3 Barab´asi-Albert Model . . . . . . . . . . . . . . . . . . . . . . 19 4 Centrality concepts 21 4.1 Centrality Measures . . . . . . . . . . . . . . . . . . . . . . . . 22 5 Association concepts 32 5.1 Clusterconcepts.......................... 32 5.2 Integer programming formulations . . . . . . . . . . . . . . . . 34 5.2.1 Maximum k-clique problem . . . . . . . . . . . . . . . 35 5.2.2 Maximum k-club problem . . . . . . . . . . . . . . . . 39 5.2.3 Maximum k-plex problem . . . . . . . . . . . . . . . . 42 2
Chapter 1 Introduction In recent years, social networks have become a vital part of the everyday life of most people. In 2014, 73% of the Spanish population actively used social networks, Facebook being the most used. Besides the important role they play in the relations between people, social networks can be used as a free showcase to advertise any product or service. Hence, companies use them more every day as a mean to publicize their products. On the other hand, social networks allow any company to extract data about how its customers are, to study what they like, and thus improve sales. Therefore, the analysis of social networks is currently extremely important, as much from the sociological viewpoint, as economic and political. Being aware of its importance, we have used in this work graph theory, seeing a social network as a set of nodes and their relationships. The work is structured in four more chapters. In Chapter 2 we define some concepts that we need along the work. In addition, we study the shortest paths problem between nodes using three different methods. In Chapter 3 we introduce some probabilistic models for social networks. These models are the Erd¨os-R´enyi-Gilbert model, the Exponential model and the Barab´asi- Albert model, which are used to generate networks. In Chapter 4 we study some centrality concepts for social networks like degree centrality or closeness centrality. These measures of centrality allow us to know the relative importance of a node in a graph. Finally, in Chapter 5 we introduce some concepts of association like k-clique or k-club, as well as integer programming formulations to find the maximum according to these concepts in a graph. 4
Chapter 2 Basic concepts Definition 2.1 A graph is a pair G≡G(N, E)where Nis a finite set whose elements are called nodes and Eis a subset of N×Nwhose elements are called edges. Definition 2.2 A network or valuated graph is a graph where each edge (i, j)∈Ehas associated a weight cij ∈R. We are going to study the concept of graph, so for each edge (i, j)∈E cij = 1. 1 2 3 4 5 Figure 2.1: Graph T. Definition 2.3 The adjacency matrix Aof a graph Gwith nnodes is an n×nmatrix where: aij =1if (i, j)∈E 0otherwise For instance, for the graph Tgiven in Figure 2.1, we obtain the adjacency matrix A: 5
A= 01100 10110 11001 01000 00100 Different types of graph exits. A directed graph is a graph where each edge is directed from one node to another. For example, Twitter is a directed network, since you can follow another user which does not follow you. In contrast, a graph where the edges are bidirectional is called undirected graph. For example, Facebook is a undirected network, because if you are friend to another user, the user is friend to you too. While the terminology of network, nodes and edges is standard in Statistics and Operations Research, in Social Sciences the corresponding terminology is actors for nodes and ties for edges. In what follows, we are going to consider Gas an undirected graph with a set of nodes N, a set of edges E,Aits adjacency matrix and n=|N|. Definition 2.4 A graph Gis complete if for every pairs of nodes i, j ∈N one has (i, j)∈E. Definition 2.5 A path in a graph is a sequence of edges which connects a sequence of nodes. Definition 2.6 A connected component of an undirected graph is a subgraph in which any two nodes are connected by a path. As an illustration, in Figure 2.2 one can see a graph with three connected components. Definition 2.7 The distance between two nodes iand jin a graph G“dG(i, j)” is the length of a shortest path between them. This is also known as the geodesic distance. For example, the distance matrix of the graph T(Figure 2.1) is the following one: DT= 01122 10112 11021 21203 22130 6
Figure 2.2: Graph formed by three connected components Definition 2.8 The diameter of a graph Gis the maximum distance between any two nodes in the graph: diam(G) = max i,j∈NdG(i, j) For example, in graph Tin Figure 2.1 one has diam(T) = 2. 2.1 Shortest paths We are going to study three methods to find the shortest path between two nodes in the graph G, analyzed in the following subsections. 2.1.1 Linear program Given two nodes sand t, our aim is to find the shortest path Pbetween them. The formulation considers originally directed graphs, so we define E0={(i, j) : (j, i)∈E}, and, for each (i, j)∈E∪E0, we consider the binary variables xij: xij =1 if (i, j) belongs to P 0 otherwise (2.1) Then the shortest path problem can be formulated as a linear program as follows, [1]: 7
minimize X (i,j)∈E∪E0 xij subject to X (s,j)∈E∪E0 xsj −X (j,s)∈E∪E0 xjs = 1 X (t,j)∈E∪E0 xtj −X (j,t)∈E∪E0 xjt =−1 X (i,j)∈E∪E0 xij −X (j,i)∈E∪E0 xji = 0 ∀i∈N:i6=s, t xij ∈ {0,1} ∀(i, j)∈E∪E0 (2.2) Since the matrix of constraints is totally unimodular, i.e. a matrix for which every square non-singular submatrix is a square integer matrix having determinant +1 or 1 (see [2]), the integrality constraints can be replaced by their continuous relaxations 0 ≤xij ≤1∀(i, j)∈E∪E0. As an illustration, we are going to compute the shortest path between nodes 3 and 9 in the graph S(Figure 2.3). 1 2 3 4 5 6 7 8 9 10 Figure 2.3: Graph S. This problem is written in AMPL, a modeling language for mathematical optimization (see [3]), as shown in Table 2.1. 8
Chapter 3 Probabilistic models for social networks In this chapter we summarize important probabilistic models for social networks. Probabilistic models allow us to make inferences about whether certain network substructures are more commonly observed in the network than might be expected by chance, or to understand a network evolution. 3.1 The Erd¨os-R´enyi-Gilbert Random Graph Model Given a network G, the probability of an edge between each pair of nodes equal to p, independently of the other edge. It is known as the network model G(n, p), e.g., see [5] and [6]. From a probabilistic viewpoint, if Adenotes the (random) adjacency matrix associated with a network G=G(N, p) generated by Erd¨os-R´enyi- Gilbert model, then Ahas the probability function given by: P(A=˜ A|p) = Y i6=j,i<j p˜aij (1 −p)1−˜aij (3.1) Property 3.1 The number of edges follows a binomial distribution with parameters n 2and p,Bi n 2, p: P(G(n, p)has eedges |p) = n 2 epe(1 −p)(n 2)−ee= 0, .., n 2(3.2) So the expected number of edges is pn 2. 15
Property 3.2 Let G(N;p)be a network following the Erd¨os-R´enyi-Gilbert model. For nodes i, j,i6=jlet Eiand Ejdenote the degree of nodes iand j, i.e. the number of edges connected to them. Then, cov(Ei, Ej) = p(1 −p) ρ(Ei, Ej) = 1 n−1 In particular, ρ(Ei, Ej)−→ 0when n−→ ∞. Proof: Consider the Bernoulli variable Ikl as follows: Ikl =1if akl = 1 0otherwise It follows that Ei=X l6=i Iil, Ej=X l06=j Ijl0 and hence var(Ei) = X l6=i var(Iil) + : 0 2X l6=i,l<k cov(Iil, Iik)=(n−1)p(1 −p) = var(Ej) cov(Ei, Ej) = cov(Iij+X l6=i,j Iil, Iij+X l06=j,i Ij,l0) = cov(Iij, Iij)+ : 0 cov(Iij,X l06=j,i Ij,l0)+ + : 0 cov(X l6=i,j Iil, Iij) + : 0 cov(X l6=i,j Iil,X l06=j,i Ij,l0) = var(Iij) = p(1 −p) ρ(Ei, Ej) = p(p−1) p(n−1)p(1 −p)p(n−1)p(1 −p)=p(1 −p) (n−1)p(1 −p)=1 n−1 Proposition 3.1 Let λ=pn, •If λ < 1: a graph in G(n, p)will have no connected components of size larger than O(log n), almost surely as n−→ ∞. 16
•If λ= 1: a graph in G(n, p)will have a largest component whose size is of O(n2/3), almost surely as n−→ ∞. •If λ > 1: a graph in G(n, p)will have a unique “giant” component containing a positive fraction of the nodes, almost surely as n−→ ∞. No other component will contain more than O(log n)nodes, almost surely as n−→ ∞. For a proof, see [7]. There is a huge number of mathematical papers that study the Erd¨os- R´enyi-Gilbert model. But few of them are relevant for the actual statistical analysis of networks because the model imposes that every node has approximately the same number of neighbors and we can find few real networks with such simple structure. ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● n=20, p=0.1 n=20, p=0.5 n=20, p=1 Figure 3.1: Graphs generated by the binomial model of Erd¨os-R´enyi-Gilbert. Some instances of the binomial model of Erd¨os-R´enyi-Gilbert can be seen in Figure 3.1. These graphs have been generated with the library igraph ([22]) in Rand using the function erdos.renyi.game. 3.2 Exponential Random Graph Models An exponential random graph model is a parametric model of random graph whose adjacency matrix Ahas the following probability function: P(A=˜ A) = 1 κexp (X Y ηYgY(˜ A))(3.3) where: 17
•The summation is over all configurations Y. A configuration is a set of nodes and a subset of edges among them, such that, if a set of edges represents a configuration in the model, then any subset of possible edges is also a configuration. •gY(˜ A) is a statistic corresponding to configuration Ydefined as gY(˜ A) = Q˜aij ∈Y˜aij. Thus, gY(˜ A) = 1 if the configuration Yis observed in ˜ A, and is 0 otherwise. •κis a normalizing quantity. •ηYis a parameter corresponding to configuration of type Y. See more in [8] and [9]. The Markov random graphs are a particular sub-class of exponential random graph models, introduced by Frank and Strauss (see [10]), in which configurations consist of edges such that any pair of edges share a node. See Figure 3.2. edge(θ) 2-star(σ2) 3-star(σ3) 4-star(σ4) ... triangle(τ) Figure 3.2: Configurations and parameters for non-directed Markov random graphs For example, in a Markov random graph, the probability of observing a particular non-directed network ˜ Awith edges, 2-stars, 3-stars and triangles is given by the equation (3.4). 18
P(A=˜ A) = 1 κexp(θL(˜ A) + σ2S2(˜ A) + σ3S3(˜ A) + τT(˜ A)) (3.4) where L(˜ A) is the numbers of edges in ˜ A,S2(˜ A) and S3(˜ A) are the number of 2-star and 3-star, respectively in the network ˜ A, and T(˜ A) is the number of triangles in ˜ A. 3.3 Barab´asi-Albert Model The Barab´asi-Alber (BA) model is used for generating scale-free networks, i.e, networks where the probability that a node has kedges follows a power law, see [11]. The Erd¨os-R´enyi-Gilbert Model or Exponential models, which we have already explained, lack two aspect that most real-world networks have. These models assume that the network has a fixed numbers of nodes (n), in contrast with most real-world networks formed by the continuous addition of new nodes to the network. On the other hand, these models assume that the probability that two nodes are connected is random and uniform; on the contrary, most real networks show preferential attachment. A new node usually has higher probability to be connected to a node that already has a larger number of connections. The BA model incorporates these two aspects. The model is defined in two steps: 1. The network starts with a small number (n0) of nodes. At every timestep (t) we add a node with m(≤n0) edges (connected to a node that is already present in the network). 2. A new node (j) will be connected to a node iwith a probability that depends on the number of edges of i(ki): P((j, i)∈E) = ki Σj∈Nt−1kj where Nt−1is the set of nodes which are already present in the network. 19
t=0 t=1 1 2 3 1 2 3 4 t=2 t=3 1 2 3 4 5 1 2 3 4 5 6 Table 3.1: Example of a Barab´asi-Albert graph After Ttimesteps we obtain a random network with n=T+n0nodes and mT edges. As an illustration, in Table 3.1 one can see a graph generated by the Barab´asi-Albert model. 20
Chapter 4 Centrality concepts In the study of Social Networks, an important objective is to know who are the most important or influential users in a network. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Figure 4.1: Graph G In Figure 4.1 it seems logical to think that the nodes 1,4,11,15,18 are the most important ones in the network Gbecause of their number of links. The process of counting how many links each node in a network has leads to the concept of degree centrality. But how can we know who is connected to important nodes? Or what if the network is not neatly partitioned into core and periphery like happens in Figure 4.1? In this chapter we introduce 21
some measures of centrality in a network, which allow us to know the relative importance of a node in a graph. 4.1 Centrality Measures We are going to study different centrality measures of a graph G. See more in [17]. Definition 4.1 The degree centrality of a node iis equal to the number of edges connected to the node: CDi= n X j=1 aij We can standardize the measure to compare with other networks. To do this, we divide by the number of possible edges a node can have, namely, n−1: C∗ Di=1 n−1 n X j=1 aij As an illustration, we are going to study the degree centrality of a Barab´asi- Albert random graph Swith 50 nodes, of a Erd¨os-R´enyi-Gilbert random graph Twith 50 nodes and probability 0.5 and of a graph Uusually found in the literature. In Figure 4.2 and 4.3 the three so obtained graphs are represented. To calculate the degree centrality we can use the function degree of the library igraph in R. In Figure 4.4 the standardized degree centrality of each node in Sis shown. We see that there are two nodes (1 and 6) whose degree centrality is clearly bigger than the remaining ones, and can be identified as the most important ones in the graph. In Figure 4.5 (left) we depict the standardized degree centrality of the nodes in T. It is seen that the degree centrality is more or less homogeneous, and then this measure can not identify the most relevant nodes, if any. The standardized degree centrality of the nodes in the graph Uis shown in Figure 4.5 (right). As in graph Shappened, we can observed that there are two nodes (7 and 9) whose degree centrality is bigger than the all other ones, so we can identify the nodes 7 and 9 as the most important ones in the graph U. 22
Graph SGraph T Figure 4.2: Barab´asi-Albert random graph Sand Erd¨os-R´enyi-Gilbert random graph T ● ● ● ● ● ● ●●● ● ● ● ● ●● 1 2 3 4 5 6 789 10 11 12 13 14 15 Figure 4.3: Graph U A complementary viewpoint is represented in Figure 4.6, which shows the histograms of the standardized degree centrality of the graphs S(left) and T(right), and in Figure 4.7 which shows the histograms of the standardized 23
Figure 4.4: Representations of the degree centrality of the graph S ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ●●● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● 0 10 20 30 40 50 0.40 0.45 0.50 0.55 0.60 Index degree_centrality_T ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● 2 4 6 8 10 12 14 0.1 0.2 0.3 0.4 0.5 Index degree_centrality_U Figure 4.5: Representations of the degree centrality of the graphs T(left) and U (right) degree centrality of the graph U. We can observe that the graph Shas a lot of nodes with low degree centrality and few of them with high degree centrality. The degree centrality of the nodes of Sfollows a power law, as we expected. On the contrary, the histogram of T(Figure 4.6 right) has a gaussian like shape. Finally, in the histogram of U(Figure 4.7) we observe that the majority of the nodes has low degree centrality. 24
(right). We observe that all the nodes have betweenness centrality equal to 0 except nodes 7, 8 and 9 whose betweenness centrality is bigger than 0.54. So, we can identify these nodes as the most relevant ones in U. Figure 4.13: Representations of the betweenness centrality of the graph S Figure 4.13 (right) shows the standardized betweenness centrality of the graph S. We observe that the nodes 1, 2, 5 and 6 have betweenness centrality bigger than the remaining ones, so these nodes can be identified as the most important ones in S. 31
Chapter 5 Association concepts In the actual study of social networks there is a need for useful concepts to represent closely knit groups. Many of these can be developed with the help of the theory of graphs. A well-known concept is the clique: a group in which all its members are in contact with each other or are friends. In this chapter we will introduce four different cluster concepts of graphs: k-cliques, k-clans, k-club and k-plex. 5.1 Cluster concepts Consider an undirected graph G=G(N, E). Given a subset of nodes S⊆N,G(S) denotes the subgraph induced by Son G,G(S) = (S, S×S∩E). Definition 5.1 A clique of a graph Gis a subset of nodes Tsuch that for all pairs of nodes u, v ∈T:(u, v)∈E, i.e., its induced subgraph G(T)is a complete graph. The problem of finding maximal cliques in a graph, i.e., find complete subgraphs that are not contained in any other complete subgraph, is in general a hard problem. To do this, it is usually used backtracking algorithms that apply branch-and-bound techniques to cut off branches that can not lead to a clique. The Bron-Kerbosch algorithm is an example [12]. Luce introduced the concept of “k-clique” (see [13]), given by the following definition 32
Definition 5.2 Ak-clique Lof a graph Gis a maximal subgraph of Gsuch that for all pairs of nodes u,vof L:dG(u, v)≤k. In other words, a k-clique Lis a set of nodes in which any two nodes are a distance of at most kfrom each other in G, and no other node in the graph is of distance kor less from every other node in L. For example, in the graph Zthe subset of nodes C1={1,2,4,5,6}forms a 2-clique. 1 2 3 45 6 Figure 5.1: Graph Z By definition, if two nodes u, v ∈Nbelong to a k-clique L, then dG(u, v)≤ k, however this does not imply that dG(L)(u, v)≤k. So the diameter of L may be larger than k. For example, in the graph Zthe subset of nodes C2={1,2,3,4,5}forms a 2-clique, although the diameter of G(C2) is 3. Hence, the concept of k-clique lacks the requirement of “tightness” in the group of nodes corresponding of a k-clique, while this requirement is essential to applications in Social Networks. Because of this, Alba introduced the concept of a “sociometric clique” (see [14]), which was later renamed to “k-clan” by Mokken. Definition 5.3 Ak-clique Lis called k-clan if the diameter of the induced subgraph G(L)is no more than k. So for example C1also forms a 2-clan. In 1979, Mokken defined the concept of “k-club” (see [15]): Definition 5.4 A maximal subset of nodes D⊆Nis a k-club if the diameter of the induced subgraph G(D)is at most k. Hence for a k-club Dof Gthe following clauses are true: 1. ∀u, v ∈D:dG(D)(u, v)≤k 33
2. Because of the maximality of D,∀w∈G−D,∃u∈D:dG(u,w)> k The 2-clubs of the graph Zare D1={1,2,3,4},D2={2,3,4,5}and D3=C1. By definition a k-clan is a k-clique of diameter k. But how is a k-clique related to a k-club? See Proposition 5.1 (proof in [15]). Proposition 5.1 Every k-club Nof a graph Gis contained in some k-clique Lof G. Let N(u) and degG(u) denote respectively the set of neighbors of a node u∈N(N(u) = {v: (u, v)∈E}) and the number of neighbors of uin G. Let L[u] denote the closed neighborhood of a node u,N[u] = {u} ∪ N(u). Definition 5.5 A subset of nodes S⊆Nis a k-plex if degG(S)(v) = |N(v)∩S|≥| S| −k,∀v∈S, (see [20]). For example the subset of nodes E2={2,3,4}forms a 1-plex. Seidman and Foster proposed an equivalent characterization of k-plexes (proof in [21]): Proposition 5.2 S⊆Nis a k-plex if and only if for any subset of knodes, {v1, .., vk} ⊂ S:S=Sk i=1 N[vi]. 5.2 Integer programming formulations This section presents integer programming (IP) formulations for the maximum k-clique, maximum k-club and maximum k-plex problems. In order to do that, consider for every i∈N, the binary variable xiequal to 1 if and only if ibelongs to the solution. 34
2-clique 2-clan 2-club 1-plex Figure 5.2: Examples of clusters 5.2.1 Maximum k-clique problem Consider the following formulation for the k-clique problem, [18]: maximize X i∈N xi subject to xi+xj≤1 + k dG(i, j)∀i, j ∈V:i<j xi∈ {0,1} ∀i∈V (5.1) The constraints expres the fact that if two actors have dG(i, j)> k, they can not be simultaneously included in a k-clique. We are going to see a example. We consider a set of twenty actors in a social network and the relationship among themselves. It is represented by the Erd¨os-R´engy-Gilbert random graph Ewith probability 0.5 which was introduced in Section 2.1 (Figure 5.3). The matrix of distances of the graph E,dE, has been calculated with the program Grafos ([23]). 35
● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Figure 5.3: Network Eand its adjacency matrix which has been obtained with the library igraph in Rand using the function get.adjacency dE= 02211111212212221222 20112211122122221222 21012221211211122111 11101121122121122212 12210212112212111222 12212021212211222121 11221202211221212212 11112120222121212211 21211222012211222121 12121112101222111211 22122212210312222222 21212221223021211121 12121122121201212122 22112111122110212112 22111222212222012211 22221211212111102111 11221222212122220222 22122122122111212011 22112211212221112102 22122121112122112220 This problem is written in AMPL, as shown in Table 5.1. 36
param n; param k; param d{1..n,1..n}; var x{1..n}binary; maximize f: sum{i in 1..n}x[i]; subject to r1{j in 1..n, i in 1..j-1}: x[i]+x[j]<=1+k/d[i,j]; Table 5.1: Code of maximum k-clique problem The diameter is the largest element in the distance matrix dE, so Ehas diameter 3. Hence we can search the maximum 1-clique, 2-clique and 3-clique. The optimal solutions for these problems provided by the solver Gurobi are given in Table 5.2. k= 1 xi=1 if i= 3,4,8,14,19 0 everywhere else k= 2 xi=0 if i= 12 1 everywhere else k= 3 xi=1 if i= 1,2,3,4,5,6... 0 never Table 5.2: Results So, the maximum 1-clique of Eis E(S) where S={3,4,8,14,19}. In 37
others words, E(S) is the maximum maximal subgraph of Ein which every two nodes are adjacent in E. See the Figure 5.4. Figure 5.4: Maximum 1-clique of E The subset Vformed by all the nodes excluding number 12 forms the maximum 2-clique, i.e., every two nodes of Veither are adjacent in Eor are adjacent of a common node in E. Logically Eis the maximum 3-clique because its diameter is three. We have observed that the nodes 11 and 12 are the only pair of nodes whose distance between them is 3. Hence we study if the maximum 2-clique problem has multiple solutions. For it, we impose the constraint r2 which makes the node 12 belongs to the solution. See the code in Table 5.3. The optimal solution for this problem provided by the solver Gurobi is given in Table 5.4. The induced subgraph E(W) where W=N\{12}is a 2-clique and this problem has the same objective value than the previous one. Then E(W) is also a maximum 2-clique. 38
param n=20; param k; param d{1..n,1..n}; var x{1..n}binary; maximize f: sum{i in 1..n}x[i]; subject to r1{j in 1..n, i in 1..j-1}: x[i]+x[j]<=1+k/d[i,j]; subject to r2: x[12]=1; Table 5.3: Code of the maximum k-clique problem in which we impose that the node 12 belongs to the solution k= 2 xi=0 if i= 11 1 everywhere else Table 5.4: Optimal solution of the problem in Table 5.3 5.2.2 Maximum k-club problem For any two nodes i, j ∈N, let Ck ij be the sets of all chains of length at most klinking iand j. Denoted by Ntthe nodes set of a chain t. Let ytbe an auxiliary binary variable associated with every chain t∈Si,j∈NCk ij =C. Then the maximum k-club problem can be formulated as an integer linear program as follows, [19]: 39
maximize X i∈N xi subject to xi+xj≤1 + Pt∈Ck ij yt∀(i, j)/∈E, Ck ij 6=∅ yt≤xr∀t∈C, ∀r∈Nt xi+xj≤1∀(i, j)/∈E, Ck ij =∅ xi∈ {0,1} ∀i∈N yt∈ {0,1} ∀t∈C (5.2) The constraints ensure that if two nodes iand jare not linked by an edge but are linked at least by a chain of length at most k, then both nodes can belong to the solution if and only if yt= 1 for at least one chain t∈C. Also, if yt= 1 then all nodes of the chain tbelong to the solution. Finally, if two nodes are not linked neither by an edge nor by a chain of length at most k, can not simultaneously belong to the solution. We are going to study the maximum k-club in the same graph Eof the previous subsection, see Figure 5.3. Table 5.5 shows this problem which is written in AMPL. The maximum 1-clique is a complete subgraph, so its diameter is 1. Then the maximum 1-clique problem and the maximum 1-club problem are the same. In addition, the diameter of Eis 3, so the maximum 3-club is E. Hence, we only study the maximum 2-club problem, which optimal solution provided by the solver Gurobi is given in (5.3). xi=0 if i= 11 1 everywhere else (5.3) The induced subgraph E(W) is also the maximum 2-club. 40