Hasan Yilmaz

A GENERALIZATION OF MULTIPLIER RULES FOR INFINITE-DIMENSIONAL OPTIMIZATION PROBLEMS

Keywords: Mathematical Subject Classification 2010: 90C30, 49K99 Multiplier rule, Fritz John theorem, Karush-Kuhn-Tucker theorem

We provide a generalization of first-order necessary conditions of optimality for infinite-dimensional optimization problems with a finite number of inequality constraints and with a finite number of inequality and equality constraints. Our assumptions on the differentiability of the functions are weaker than those of existing results.

Introduction

We provide an improvement of first-order necessary conditions of optimality for infinite-dimensional problems under a finite number of inequality constraints and under a finite number of inequality and equality constraints in the form of Fritz John's theorem and Karush-Kuhn-Tucker's theorem. In this paper, we give a proof of multiplier rules by following the same approach as Michel in [START_REF] Michel | Cours de mathématiques pour économistes[END_REF] p. 510. To prove his result, Michel uses the Brouwer fixed-point theorem that is why, at the first slight, his proof seems specific to finite-dimensional optimisation problems. However, we remark that we can extend this result for infinite-dimensional optimizaton problems. The proof of Michel is explained in detail in [START_REF] Blot | Infinite-horizon optimal control in the discrete-time framework[END_REF], Appendix B. Another proof of the multiplier rules was established by Halkin in [START_REF] Halkin | Implicit functions and optimization problems without continuous differentiability of the data[END_REF] but his proof is completely different. Indeed, Halkin uses an implicit function theorem with only Fréchet differentiable at a point framework instead of the continuously Fréchet differentiable framework. The improvement of Michel and Halkin is to replace the assumption of continuously Fréchet differentiable on a neighborhood of the optimal solution (see in [START_REF] De | Cours d'Automatique Théorique[END_REF] Chapter 13 section 2) with the assumptions of the continuity on a neighborhood of the optimal solution and the Fréchet differentiability at the optimal solution. Note that there are another way to generalize the assumption of continuous Fréchet differentiability by using locally Lipschitzian mappings e.g. [START_REF] Clarke | Optimization and nonsmooth analysis[END_REF]. The statement of Halkin and Michel is not similar with the statements of locally Lispchitzian. Indeed, in general, a mapping which is Fréchet differentiable at a point is not locally Lipschitzian arround this point and conversely a mapping which is locally Lipschitzian arround a point is not Fréchet differentiable at this point. In [START_REF] Blot | On the multipliers rules[END_REF], Blot gave also a proof of multiplier rules for finite-dimensional optimization problems under only inequality constraints and under inequality and equality constraints. For the problems with inequality constraints, Blot reduced the assumptions of Pourciau in [START_REF] Pourciau | Modern multiplier rules[END_REF] by replacing, at the optimal solution, the Fréchet differentiability with the Gâteaux differentiability. For the problems with inequality and equality constraints, Blot deleted the assumptions of local continuity on a neighborhood for the objective function and for the functions in the constraints of inequality. Therefore, Blot improved the multilplier rules of Michel and Halkin by lightening the assumptions on the continuity of the functions. The main contributions of this paper are as follows.

• Contrary to Blot and Michel, we do not assume the finiteness of the dimension of the space. Therefore, we extend the main theorems of [START_REF] Blot | On the multipliers rules[END_REF] and [START_REF] Michel | Cours de mathématiques pour économistes[END_REF] in infinite-dimensional vector spaces. • Moreover, in comparison with Blot's multiplier rules, we replaced the assumptions of Fréchet differentiability by the Hadamard differentiability which is weaker in infinite-dimensional vector. For consequently, our assumptions on the differentiability of the functions are weaker than [START_REF] Blot | On the multipliers rules[END_REF], [START_REF] Michel | Cours de mathématiques pour économistes[END_REF] and [START_REF] Halkin | Implicit functions and optimization problems without continuous differentiability of the data[END_REF]. We summarize the content of this paper as follows.

In Section 2, we state the main theorems of the paper. In Section 3, we specify the definition of Gâteaux differentiability and Hadamard differentiability. Besides, we recall a supporting hyperplane theorem and the Schauder fixed-point theorem. In Section 4, in order to proof our first-order necessary conditions under inequality constraints, we delete the inactive inequality constraints. Next, we use a supporting hyperplane theorem to find the multipliers. In Section 5, we give a proof of first-order necessary conditions of optimality under inequality and equality constraints. As in Section 4, we delete the inactive inequality constraints. In order to use the supporting hyperplane theorem, we use the Schauder fixed-point theorem.

Statements of the Main Results

The paper deals with infinite-dimensional optimization problems with a finite list of inequality constraints and with a finite list of inequality and equality constraints. Let E be a normed vector space, let Ω be a nonempty open subset of E, let f i : Ω → R when i ∈ {0, ..., m} be functions, let f : Ω → R, g i : Ω → R when i ∈ {1, ..., p}, h j : Ω → R when j ∈ {1, ..., q} be functions and m, p and q are integer number. We consider the two following problems (I)

   Maximize f 0 (x) subject to x ∈ Ω ∀i ∈ {1, ..., m}, f i (x) ≥ 0 and (P)        Maximize f (x) subject to x ∈ Ω ∀i ∈ {1, .
.., p}, g i (x) ≥ 0 ∀j ∈ {1, ..., q}, h j (x) = 0. The main theorems of the paper are the following ones.

Theorem 2.1. Let x be a solution of (I). We assume that the following assumptions are fulfilled. (i) For all i ∈ {0, ..., m}, f i is Gâteaux differentiable at x. (ii) For all i ∈ {1, ..., m}, f i is lower semicontinuous at x when f i (x) > 0.

Then, there exist λ 0 , ..., λ m ∈ R + which satisfy the following conditions. (a) (λ 0 , ..., λ m ) = (0, ..., 0). (b) For all i ∈ {1, ..., m}, λ

i f i (x) = 0. (c) m i=0 λ i D G f i (x) = 0.
In addition, if we assume that the following assumption is verified (iii) there exists w ∈ E such that for all i ∈ {1, ..., m}, D G f i (x)w > 0 when f i (x) = 0 then we can take (d) λ 0 = 1.

Theorem 2.2. Let x be a solution of (P). We assume that the following assumptions are fulfilled.

(i) f is Hadamard differentiable at x. (ii) For all i ∈ {1, ..., p}, g i is Hadamard differentiable at x when g i (x) = 0. (iii) For all i ∈ {1, ..., p}, g is lower semicontinuous at x and Gâteaux differentiable at x when g i (x) > 0. (iv) For all j ∈ {1, ..., q}, h j is continuous on a neighborhood at x and Hadamard differentiable at x. Then, there exist λ 0 , ..., λ p ∈ R + and µ 1 , ..., µ q ∈ R which satisfy the following conditions.

(a) (λ 0 , ..., λ p , µ 1 , ..., µ q ) = (0, ..., 0). (b) For all i ∈ {1, ..., p}, λ i g i (x) = 0. (c) λ 0 D H f (x) + p i=1 λ i D G g i (x) + q j=1 µ j D H h j (x) = 0.
Futhermore, if we assume that the following assertion hold (v) D H h 1 (x), ..., D H h q (x) are linearly independent we have (d) (λ 0 , ..., λ p ) = (0, ..., 0). Moreover, under (v) and the following assertion (vi) there exists w ∈ ∩ q i=1 KerD H hj(x) such that for all i ∈ {1, ..., p}, D G g i (x)w > 0 when g i (x) = 0 we can take (e) λ 0 = 1.

Recall and Notations

We set N the set of positive integer and N * = N \ {0}. R denotes the set of real numbers and R + the set of non negative real numbers. Let E, F and G be three normed vector spaces, let Ω be a nonempty open subset of E, let f : Ω → F be a mapping, let x ∈ Ω, let y ∈ E and r ∈]0, +∞[. The closed ball centered at y with a radius equal to r is denoted by B(y, r). Let A ⊂ E and B ⊂ F , C 0 (A, B) denotes the continuous mappings from A into B. bdA denotes the topological boundary of A. We denote by L(E, F ) the space of the bounded linear mappings from E into F . Let l ∈ L(E, F ), we note Iml = l(E). Let l 1 ∈ L(E, F ) and l 2 ∈ L(E, G), we note by (l 1 , l 2 ) the mapping in L(E, F ×G) defined by for all x ∈ E, (l 1 , l 2 )x = (l 1 x, l 2 x). f is called Gâteaux differentiable at x when there exists

D G f (x) ∈ L(X, Y ) such that for all h ∈ E, lim t↓0 f (x+th)-f (x) t = D G f (x)h.
We say that f is Hadamard differentiable at x when there exists D H f (x) ∈ L(X, Y ) such that for all h ∈ E, for all sequence (h n ) n∈N converging to h and for all sequence (t n ) n∈N of positive numbers converging to 0 we have

lim n→+∞ f (x+tnhn)-f (x) tn = D H f (x)
h which is equivalent to (see [START_REF] Flett | Differential analysis[END_REF] p. 265) for each

K compact in E, lim t↓0 sup h∈K f (x+th)-f (x) t = D H f (x)h. When f is Hadamard differentiable at x, f is also Gâteaux differentiable at x and D H f (x) = D G f (x)
. But the converse is false when the dimension of E is greater than 2. More information on these notions can be found in [START_REF] Flett | Differential analysis[END_REF].

If n ∈ N * , we note •, • the canonical scalar product on R n , (e n,i ) 1≤i≤n the canonical basis of R n and • ∞ the maximum norm on R n . Moreover, we note by B • ∞ (y, r) the closed ball centered at y with a radius equal to r in R n with the maximum norm. We recall a supporting hyperplane theorem. This theorem is a corralary of Hahn-Banach theorem. We can find a proof in [START_REF] Van Tiel | Convex analysis[END_REF] p. 37. Note that if z = 0 we have γ = 0. Next, we recall the Schauder fixed-point theorem.

Theorem 3.2. (Schauder fixed-point theorem) Let E be a normed vector space, let C be a nonempty convex and compact subset of E and let f : C → C be a continuous mapping, then f admit a fixed point i.e. there exists x ∈ C such that f (x) = x.

We can find a proof of the Schauder fixed-point theorem in [START_REF] Dugundji | Fixed point theory[END_REF] p. 119.

Proof of Theorem 2.1

We set S := {i ∈ {1, ..., m} : f i (x) = 0}. If S = ∅ we have for all i ∈ {1, ..., m}, f i (x) > 0 using the lower semicontinuous of f i , there exists an open neighborhood Ω 1 of x in Ω such that for all i ∈ {1, ..., m}, for all x ∈ Ω 1 , f i (x) > 0. Since x is a solution of (I), we have x maximize f 0 on Ω 1 . Therefore by using (i), we have D G f 0 (x) = 0. By taking λ 0 = 1 and for all i ∈ {1, ..., m}, λ i = 0, we proved (a), (b), (c) and (d). We assume that S = ∅ in the rest of the proof.

4.1.

To delete all inactive inequality constraints. By doing a change of index, we can assume that S = {1, ..., s} where 1 ≤ s ≤ m. Since for all i ∈ {s + 1, ..., m}, we have f i (x) > 0, using (ii) there exists an open neighborhood U of x in Ω such that for all i ∈ {s + 1, ..., m}, for all x ∈ U , we have f i (x) > 0. For consequently, we have x is a solution of the following problem

(N I)    Maximize f 0 (x) subject to x ∈ U ∀i ∈ {1, ..., s}, f i (x) ≥ 0. 4.2.
Proof of (a), (b), (c). We consider the mapping F : U → R s+1 defined by ∀x ∈ U , F (x) = (f 0 (x), ..., f s (x)). Since for all i ∈ {0, ..., s}, f i is Gâteaux differentiable at x, we have F is Gâteaux differentiable at x and

D G F (x) = (D G f 0 (x), ..., D G f s (x)).
We set C := ImD G F (x)+R s+1 -. We note that C is a convex set of R s+1 . Moreover, C is not a neighborhood of 0. To prove this, we proceed by contradiction, by assuming that C is a neighborhood of 0. Therefore, there exists r > 0 such that

B • ∞ (0, r) ⊂ C. Since b = (r, ..., r) ∈ B • ∞ (0, r) we have b ∈ C then there exists u ∈ E and z = (z 0 , ..., z s ) ∈ R s+1 - such that D G F (x)u + z = b. For consequently, we have ∀i ∈ {0, ..., s}, D G f i (x).u = r -z i ≥ r. (4.1)
By using (4.1), we remark that u = 0. Since F is Gâteaux differentiable at x, we have

∃δ > 0 ∀t ∈]0, δ] (x + tu ∈ U ) F (x + tu) -F (x) -tD G F (x)u ∞ < rt. (4.2)
Then, using (4.2) with t = δ, we have

F (x+δu)-F (x)-δD G F (x)u ∞ < rδ which implies that ∀i ∈ {0, ..., s}, f i (x + δu)-f i (x)-δD G f i (x)u > -rδ.
For consequently, by using (4.1) we have for all i ∈ {0, ..., s},

f i (x + δu) -f i (x) > δD G f i (x)u -δr ≥ 0.
Therefore, we have f 0 (x + δu) > f 0 (x) and for all i ∈ {0, ..., s}, f i (x + δu) > 0 which implies that x is not a solution of (N I). This is a contradiction. Since 0 ∈ C and C is not a neighborhood of 0, we have 0 ∈ bdC. Since C is a convex of R s+1 and 0 ∈ bdC, by using Theorem 3.1 there exists v = (λ 0 , ..., λ s ) ∈ R s+1 \ {0} such that for all x ∈ C, v, x ≤ 0. For consequently, we have

∀u ∈ E, ∀z = (z 0 , ..., z s ) ∈ R s+1 -, s i=0 λ i (D G f i (x)u + z i ) ≤ 0. ( 4.3)
We set for all i ∈ {s + 1, ..., m} λ i = 0. Since (λ 0 , ..., λ s ) = 0, we have (λ 0 , ..., λ m ) = 0. Let i ∈ {0, ..., s}, by using (4.3) with u = 0 and z = -e s+1,i+1 , we have -λ i ≤ 0 which implies that λ i ≥ 0. We have also for all i ∈ {1, ..., m}, λ i f i (x) = 0. By using (4.3), with z = 0, we have ∀u ∈ E,

s i=0 λ i D G f i (x)u ≤ 0 which implies that s i=0 λ i D G f i (x) = 0, (4.4) therefore m i=0 λ i D G f i (x) = 0.
We proved (a), (b) and (c).

Proof of (d).

In addition, if we assume (iv), we have λ 0 = 0. We proceed by contradiction by assuming that λ 0 = 0. Since (iii) and (λ 1 , ..., λ s ) ∈ R s + \ {0}, we have s i=1 λ i D G f i (x)w > 0. By using (4.4), we have s i=1 λ i D G f i (x)w = 0. This a contradiction. Since, λ 0 = 0, by taking for all i ∈ {0, ..., m}, λ ′ i = λi λ0 , we proved (d).

Proof of Theorem 2.2

We set S := {i ∈ {1, ..., p} : g i (x) = 0}. Without loss of generality, we can assume that S = ∅. If S = ∅ we can delete all inequality constraints. Indeed, we have for all i ∈ {1, ..., p}, g i (x) > 0, by using (iii), there exists a neighborhood Ω 1 of x in Ω such that for all i ∈ {1, ..., p}, for all x ∈ Ω 1 , g i (x) > 0. For consequently, x is a solution of the following problem (SP )

   Maximize f (x) subject to x ∈ Ω 1 ∀j ∈ {1, ..., q}, h j (x) = 0.
5.1. To delete all inactive inequality constraints. In the rest of the proof, we assume that S = ∅. By doing a change of index, we can assume that S = {1, ..., s} where 1 ≤ s ≤ m. Since for all i ∈ {s + 1, ..., m}, we have g i (x) > 0, using (iii) and (iv) there exists an open neighborhood U of x in Ω such that for all i ∈ {s+1, ..., m}, for all x ∈ U , we have g i (x) > 0 and for all j ∈ {1, ..., q}, h j is continuous on U .

For consequently, we have x is a solution of the following problem

(N P )        Maximize f (x) subject to x ∈ U ∀i ∈ {1, ..., s}, g i (x) ≥ 0 ∀j ∈ {1, ..., q}, h j (x) = 0. 5.2.
Proof of (a), (b), (c). We consider the mappings G : U → R s+1 and H : U → R q defined by ∀x ∈ U , G(x) = (f (x), g 1 (x), ..., g s (x)) and H(x) = (h 1 (x), ..., h q (x)). Since (i), (ii) and (iv) we have G and H are Hadamard differentiable at x. Moreover

D H G(x) = (D H f (x), D H g 1 (x)..., D H g s (x)) and D H H(x) = (D H h 1 (x), ..., D H h q (x)). We set C := Im(D H G(x), D H H(x)) + R s+1 -× {0}. C is a convex set of R s+q+1 .
C is not a neighborhood of 0. To prove this, we proceed by contradiction, by assuming that C is a neighborhood of 0. Therefore, there exists r > 0 such that

B • ∞ (0, r) ⊂ C.
We set b = (r, ..., r) ∈ R s+1 . Since, for all j ∈ {1, ..., q}, (b, re q,j ) ∈ C and (b, -re q,j ) ∈ C, there exists u j ∈ E and z j = (z 0,j , ..., z s,j

) ∈ R s+1 - such that D H G(x)u j + z j = b and D H H(x)u j = re q,j (5.1)
and there exists ũj ∈ E and zj = (z 0,j , ..., zs,j ) ∈ R s+1 -such that D H G(x)ũ j + zj = b and D H H(x)ũ j = -re q,j .

(5.2)

We set K := { q j=1 a j u j + q j=1 ãj ũj : ∀j ∈ {1, ..., q}, a j ≥ 0, ãj ≥ 0 and q j=1 a j + q j=1 ãj = 1}. By using (5.1), we have 0 / ∈ K. We remark that K is a convex and compact set of E. Since G and H are Hadamard differentiable at x and K is a compact set of E, we have

∃δ 1 > 0 ∀t ∈]0, δ 1 ], ∀k ∈ K, G(x + tk) -G(x) -tD H G(x)k ∞ < rt (5.3) ∃δ 2 > 0 ∀t ∈]0, δ 2 ], ∀k ∈ K, H(x + tk) -H(x) -tD H H(x)k ∞ < r q t. (5.4)
Since U is a neighborhood of x, we have there exists r 0 > 0 such that B(x, r 0 ) ⊂ U . we set α := min{δ 1 , δ 2 , r0 sup k∈K k }. Therefore, by using (5.3) and (5.4) with t = α, we have

∀k ∈ K, |f (x + αk) -f (x) -αD H f (x)k| < rα (5.5) ∀k ∈ K, ∀i ∈ {1, ..., s}, |g i (x + αk) -αD H g i (x)k| < rα (5.6)
∀k ∈ K, ∀j ∈ {1, ..., q}, |h j (x + αk) -αD H h j (x)k| < r q α.

(5.7)

We set for all j ∈ {1, ..., q}, for all k ∈ K, w j (k) = 1 α h j (x + αk) -D H h j (x)k. We note that for all j ∈ {1, ..., q}, w j ∈ C 0 (K, R) because h j ∈ C 0 (K, R) and for all j ∈ {1, ..., q}, for all k ∈ K, |w j (k)| < r q (by (5.7)). We consider the mapping Φ : K → E defined by Φ(k) := q j=1 φ j (k)u j + q j=1 φj (k)ũ j where for all j ∈ {1, ..., q}, for all k ∈ K, φ j (k) = 1 2q -1 2r w j (k) and φj (k) = 1 2q + 1 2r w j (k). For all k ∈ K, we have for all j ∈ {1, ..., q}, φ j (k) ≥ 0, φj (k) ≥ 0 and q j=1 φ j (k) + q j=1 φj (k) = 1 therefore we have Φ(K) ⊂ K. Since for all j ∈ {1, ..., q}, φ j and φj belong to C 0 (K, R), we have Φ ∈ C 0 (K, K). Therefore, by using Theorem 3.2, we obtain there exists k ∈ K such that Φ( k) = k. Since

D H H(x) k = D H H(x)Φ( k) = q j=1 ( 1 2q -1 2r w j ( k))D H H(x)u j + q j=1 ( 1 2q + 1 2r w j ( k))D H H(x)ũ j = - q j=1 w j ( k)e q,j .
Therefore, for all j ∈ {1, ..., q}, D H h

j (x) k = -w j ( k) = -( 1 α h j (x+α k)-D H h j (x) k) which implies that h j (x + α k) = 0. Since k ∈ K there exists (a j , ãj ) 1≤j≤q ∈ R 2q
+ with q j=1 a j + q j=1 ãj = 1 such that k = q j=1 a j u j + q j=1 ãj ũj . For consequently, we have

D H f (x) k = q j=1 a j D H f (x)u j + q j=1 ãj D H f (x)ũ j = q
j=1 a j (rz 0,j ) + q j=1 ãj (r -z0,j ) (from (5.1) and (5.2))

which implies that

D H f (x) k ≥ r. (5.8)
By the same reasoning, we have also ∀i ∈ {1, ..., s}, D H g i (x) k ≥ r.

(5.9) By using (5.8), (5.9), (5.5) and (5.6) with t = k, we have f (x + α k) > f (x) and for all i ∈ {1, ..., s}, we have g i (x+α k) > 0. Since x+α k ∈ U verify for all i ∈ {1, ..., s}, g i (x + α k) > 0, for all j ∈ {1, ..., q}, h j (x + α k) = 0 and f (x + α k) > f (x), we have x is not a solution of (N P). This is a contradiction. Since 0 ∈ C and C is not a neighborhood of 0, we have 0 ∈ bdC. Since C is a convex of R 1+s+q and 0 ∈ bdC, by using Theorem 3.1 there exists v = (λ 0 , ..., λ s , µ 1 , ..., µ q ) ∈ R 1+s+q \ {0} such that for all x ∈ C, v, x ≤ 0. Therefore, we have

∀u ∈ E, ∀z = (z 0 , ..., z s ) ∈ R 1+s - λ 0 (D H f (x)u + z 0 ) + s i=1 λ i (D H g i (x)u + z i ) + q j=1 µ j D H h j (x)u ≤ 0 (5.10)
We set for all i ∈ {s + 1, ..., p} λ i = 0. Since (λ 0 , ..., λ s , µ 1 , ..., µ q ) = 0, we have (λ 0 , ..., λ p , µ 1 , ..., µ q ) = 0. Let i ∈ {0, ..., s}, by using (5.10) with u = 0 and z = -e s+1,i+1 , we have -λ i ≤ 0 which implies that λ i ≥ 0. We have also for all i ∈ {1, ..., p}, λ i g i (x) = 0. By using (5.10), with z = 0, we have ∀u ∈ E, λ 0 D H f (x)u + s i=1 λ i D H g i (x)u + q j=1 µ j D H h j (x)u ≤ 0 which implies that λ 0 D H f (x) + s i=1 λ i D H g i (x) + q j=1 µ j D H h j (x) = 0. Since, for all i ∈ {1, ..., s}, D G g i (x) = D H g i (x), we have λ 0 D H f (x)u + s i=1 λ i D G g i (x)u + q j=1 µ j D H h j (x)u = 0.

(5.11) Therefore λ 0 D H f (x)u + p i=1 λ i D G g i (x)u + q j=1 µ j D H h j (x)u = 0. We proved (a), (b) and (c).

Proof of (d).

We assume (i), (ii), (iii) and (iv). We proceed by contradiction by assuming that (λ 0 , ..., λ p ) = (0, ..., 0). Therefore, according to (5.11), q j=1 µ j D H h j (x)u = 0. Since (iv), we have (µ 1 , ..., µ q ) = 0. For consequently, we have (λ 0 , ..., λ p , µ 1 , ..., µ q ) = (0, ..., 0) this a contradiction with (a). We proved (d).

5.4. Proof of (e). We assume (i), (ii), (iii), (iv) and (v). Thanks to our previous proof we know that there exist λ 0 , ..., λ p ∈ R + and µ 1 , ..., µ q ∈ R which verify (a), (b), (c) and (d). We have λ 0 = 0, we proceed by contradiction by assuming that λ 0 = 0. Since (d) and (b), we have (λ 1 , ..., λ s ) = 0. Since (v) and (λ 1 , ..., λ s ) ∈ R s + \ {0}, we have s i=1 λ i D G g i (x)w > 0. By using (5.11), we have s i=1 λ i D G g i (x)w = 0. This a contradiction. Since, λ 0 = 0, by taking for all i ∈ {0, ..., p}, λ ′ i = λi λ0 , we proved (e).

Theorem 3 . 1 .

 31 Let n ∈ N * . Let C be a nonempty convex subset of R n and z ∈ bdC. Then there exist v ∈ R n \ {0} and γ ∈ R such that v, z = γ and for all x ∈ C, v, x ≤ γ.

Acknowledgements The author thanks Joël Blot for his encouragement.


Maxim Kolomeets
email: kolomeec@comsec.spb.ru

Didier Amira Benachour
email: abenachour@laas.fr

El Baz
email: elbaz@laas.fr

Andrey Chechulin
email: chechulin@comsec.spb.ru

Martin Strecker
email: martin.strecker@irit.fr

Igor Kotenko
email: kotenko@comsec.spb.ru

Didier El Baz

Reference architecture for social networks graph analysis tool

Keywords: Social networks, graph analysis, big data, parallel computing, GPU, graph databases, data visualization, real-world networks

Introduction

Social networks can give rise to various graph structures. They can be graphs of friends, subscribers, repost trees, trees of comments, dependency graphs of content and other. At the same time, big graphs often appear when analyzing even small amounts of source data. For example, if one is analyzing a small community, it is necessary to take into account friends and maybe friends of friends. As we will show in subsection ??, if one will collect information about a community with 2000 participants and their friends, the graph can grow up to 770.000 vertices. And it can grow up much more if one needs information about friends of friends, relation to content or other information.

An investigation of big graphs implies many difficulties that are associated with the storage, processing and visualization of data -big graphs are at the core of the big data problematic. At the same time there are a lot of effective systems that are using big data for the analysis. Besides analysis systems for social networks there are many analysis software products for computer networks, mesh networks of Internet of Things, structures of algorithms, economic and political relationships, etc. The key moment is that big graph analysis is different from big data analysis -in graphs, an important component is the topology of the structure, which can make a significant contribution to the understanding of the data is analyzed. In current analysis systems of social networks are usually analyzing content and not considering analysis of structures.

A lot of other information sources also can be represented as a graph. The graphs that model these structures are often of great size and complexity. These occur in many domains like social simulation, e.g., road networks (US road network: 58,000,000 edges), social networks, e.g., big graph simulation (Twitter fellowship: 1,470,000,000 edges) and brain science, e.g., EU Brain project (Neural networks: 100,000,000,000 edges, 89 billion nodes). There are solutions for specific use-cases in the scientific literature and commercial software, but there is a lack of the general approach which will be able to combine various algorithms of graph preparation, processing and analysis.

This paper presents the concept of a tool for the analysis of big graphs of social networks that concentrates on the static structure analysis. The novelty of this work lies in generalization of the existing approaches for the various modules of the graph processing algorithms into one pipeline which includes all of the features. The scientific contribution of this work is the reference architecture for analysis of big graphs of social networks, which demonstrates the integration of various approaches into a single tool. Analysis methods include: graph analysis via graph algorithms, technologies for storing big graphs, graph visualization and graph processing based on parallel computing.

This article is a continuation of the previous paper [START_REF] Kolomeets | Social networks analysis by graph algorithms on the example of the VKontakte social network[END_REF] where we proposed an approach for creating the hierarchical graphs schemas of social networks.

The paper is organized as follows. In Section 2 we speak about the state of the art -the review of a systems that are using big graphs for the analysis and a review of areas where such systems are used. Section 3 is dedicated to the concept of analysis pipeline -a description of the proposed concept for big graph analysis and its parts. Section 4 describes the implementation -the "proof of concept" software prototype with the experiments based on the calculation of betweenness centrality measure for graphs of social networks. Section 5 is the discussion -evaluation of the concept and analysis of its utility. The last Section 6 concludes with the description of the results and plans for future work.

State of the art

Graphs can give valuable information about processes where the most important attribute is dependence of elements. Graph analysis objectives include but are not limited to analysis of streams and paths, structures that are formed by elements, elements' significance in relation to other elements and others. There are many areas where big graphs are necessary for the analysis.

For example transactions flows are used for detection of fraud in different systems from online commerce platforms [START_REF] Chen | Big data based fraud risk management at Alibaba[END_REF] and banks [START_REF] Sadowski | Fraud detection: Discovering connections with graph databases[END_REF] to cryptocurrency such as Bitcoin [START_REF] Di Battista | Bitconeview: visualization of flows in the bitcoin transaction graph[END_REF]. Using graphs it is possible to find the money flows and ultimate beneficiary of the transaction.

Dependency graphs are important for calculation of measures for specific users, that are later used in different recommendation services. For example, dependency graphs are used by such big companies as IMDB [START_REF] Angelova | Graph-based text classification: learn from your neighbors[END_REF] and Netflix [START_REF] Elahi | Mlconf seattle 2015, Spark and GraphX in the Netflix recommender system[END_REF].

Journalists and police can use graphs for their investigation of fraud that is based on dependence between criminal and/or analyzed persons. For example International Consortium of Investigative Journalists (ICIJ) helped to reveal many tax evasion cases by building interactive graph visualization that showed dependence between offshore assets and dignitaries of different countries [START_REF] Dominguez | Mapping the global offshoring network through the panama papers[END_REF].

Also graphs can be used in smart transportation for evaluation and management of transport systems [START_REF] Rathore | Exploiting real-time big data to empower smart transportation using big graphs[END_REF].

At the same time there are a lot of systems for social networks analysis. Social networks are classical targets for graph analysis that are used by companies that own social networks for advertising [START_REF] Li | On modeling product advertisement in large-scale online social networks[END_REF] and protection [START_REF] Kotenko | Monitoring and counteraction to malicious influences in the information space of social networks[END_REF] of their reputation: for example, for detection of hate speech, prevention of artificial influence on society (for example, like cheating), detection of extremists, terrorists communities and bot farms. The Avalance Online [START_REF]Avalance online software[END_REF] complex monitors media and social networks with the possibility of classifying the collected information, compiling a "dossier" for individuals using open data and determining the emotional coloring of messages. The features of this complex include the ability to build a graph of user connections, information for which is drawn from open sources. Another successful product that monitors user information on the Internet is Palantir [21]. This tool enables an analyst to analyze data from both open and closed sources, and the relationships between them. One of the specialized software for analyzing social networks is the "Oktopus" and "Zveroboi", which are used by experts in the Investigative Committee of the Russian Federation to investigate crimes [START_REF]Baltinfocom company[END_REF]. VISR company provides service for child safety by analyzing with whom the child speaks in social networks [START_REF]Visr company[END_REF]. For sociology social networks is also good environment for experiments and research. For example in [START_REF] Branitskiy | Determination of young generation's sensitivity to the destructive stimuli based on the information in social networks[END_REF] sociologists use machine learning for prediction of Destructive Stimuli based on the Ammon test and content analysis from social networks. Also, big companies that are own social networks such as Facebook, Instagram, Twitter, Reddit, VKontakte and others use information from their users for advertising.

Most social networks analysis tools are using content analysis with bound of machine learning and statistical methods. In that paper we concentrate on analysis of structures by graph algorithms.

Graph algorithms are distinguished in Network Science branch. That algorithm includes the calculation of centrality measures, finding the structures and clustering. At the same time it is complex to implement such algorithms on big graphs. Systems that analyse them using Network Science approaches need powerful subsystems that help to extract subgraphs, speed up calculations and visualize results. These subsystems form a pipeline, the concept of which we present in the next section.

Concept of analysis pipeline

The analysis of big graphs includes the tasks of both processing and storage of large volumes of data, and the tasks of analyzing the graph topology. For effective analysis of social networks, it is necessary to provide the following features:

1. Collection of data from social network.

2. Storage of a big graph that supports graph transformation.

3. Graph topology analysis using graph algorithms.

4. Parallel data processing that obtains results of analysis at an acceptable time.

5.

Graph visualization that allows one to visually explore the results of the analysis. Thus, to analyze big graphs one should use a set of technologies for collecting, gathering, storing, filtering, processing and visualizing data. On a high level they all can be united into a tool that looks like a "data pipeline". The concept of "pipeline" is presented in the Figure 1 and on the most abstract level it includes next main modules: data collection module, graph storage module, graph analysis module and visualization module. Also, each module includes smaller submodules.

Graph collection

Data collection can be carried out by a public or specialized method. A public method involves accessing HTML pages, parsing HTML markup, and extracting meaningful information. A specialized method use an API to access data.

Extracting data by parsing HTML pages can be an alternative to accessing the API functions in cases where the functions themselves are missing or when the social network imposes restrictions on the returned result (for example, "Twitter" limits the search for "tweets" for keywords to a 7-day interval). For automated loading of dynamic HTML pages and retrieving information, it is necessary to use libraries for HTML parsing. Today, more and more social networks provide access to stored information through calls to Application Programming Interface (API) functions (including such big companies as Facebook, Instagram, Twitter, VKontakte, etc.). Access to source data using the API is legal, as the information providers already limit access to data that may legally be retrieved. The legality of the information collection can be also restricted according to the aim of data collection (usually it is allowed only for a personal usage and scientific purposes) and personal data protection laws (usually it can be solved through the usage of anonymization algorithms).

Scanners are used for data collection via making a request to the social network via an API. However, increasing the speed can trigger a block of scanner since social networks set a limit on the frequency of requests. For a high speed of data collection, a large number of simultaneously working scanners is required. Each scanner runs in its own virtual space -the thread of execution. So increasing the speed comes down to increasing the number of scanners that works in parallel.

Graph storage

A key component of graph storage is the ability to execute requests to retrieve parts of a graph. For example, the task of finding the friends of several people comes down to obtaining a subgraph based on topology -the possibility of finding the set of adjacent vertices (traversal function). The best storage implementation that takes into account topology is provided by graph databases. Also, the following properties of graph databases can be distinguished:

1. horizontal scaling -the ability to increase the number of operations per second due to the distribution of database resources on multiple devices;

2. multi-modal -the ability to store relationships between different types of data (including unstructured data that are common for social networks), such as documents;

3. schema -the possibility of implementing a case-dependent scheme (if one uses the modeling terminology -"meta model"), which is expressed in defining new types of vertices and edges of the graph. In addition, when storing big graphs, it becomes necessary to provide a flexible scheme -when adding new types of vertices and edges does not lead to changes in old records (it can happen in relational databases). The schema is necessary not only for retrieving new graphs, but also for retrieving graphs with structures that fit for analysis by algorithms and visualization (see Figure 1).

Such requirements help to filter and aggregate graphs faster and more easily. In general, aggregation and filtering is needed because it helps with solving the problem of graph transformation. Transformation can be reduced to:

1. bringing data to the structure of the database (data to schema); 2. combining several graphs into a single structure or creating representations that reflect only part of the original more complex graph (schema to schema).

"Data to schema" transformation means parsing of data to the database. During parsing one can aggregate and filter data for fitting data to a schema. It is pretty common for every database at the level of database filling and not unique.

"Schema to schema" transformations are more complex and unite different tasks of analysis:

1. graph filtering by:

• the parameter of node or edge -for example, by "weight" of the vertex or edge (age of user, length of text and other);

• schema class of node or edge -for example, by specific class of the vertex or edge (user, post, comment and so on);

• by topology -for example, querying graph from some adjacent vertices of the vertices subset (retrieving friends, commentators, who liked and so on);

graph aggregation by

• the parameter of node or edge -for example, by some categorical parameter of the vertex or edge;

• schema class of vertex or edge -for example, by superclass of vertex or edge;

• by topology -for example, by some path or specific sequences of traversal queries;

3. graph mapping to another schema -for example, by adding or removing the parameters, classes and superclasses.

Some of the graph transformations were considered in our previous paper [START_REF] Kolomeets | Social networks analysis by graph algorithms on the example of the VKontakte social network[END_REF], including aggregation by superclasses, aggregation by topological path that creates "virtual graphs" and filtering by class. Such transformation operations provide the ability to create new graphs.

As we said, graph transformations "data to schema" and "schema to schema" are different. The conversion of "data to schema" occurs at the stage of loading data into the database and should be provided using the appropriate API of DB that is based on the simple parsing of data.

A "schema to schema" conversion can occur in two ways. The first way is to use filtering, aggregating and mapping possibilities of the database itself using the database syntax or built-in functions as showed in [START_REF] Kolomeets | Social networks analysis by graph algorithms on the example of the VKontakte social network[END_REF]. The second way is to use graph algorithms, for example, graph algorithms can calculate some weights for the vertices after which can be performed filtering by weight. In this case, the task of transforming the "schema to schema" is partly transferred to the analysis module.

Graph analysis

The third element is a data analysis module that implements parallel graph processing. As we said, the key element of a graph is its topology. Thus, finding structures and determining the significance of the graph vertices can provide fundamentally new information about the analyzed data. There are many algorithms that can be distinguished: centrality, clustering, similarity, algorithms for finding the topological, potential-based algorithms in Laplace matrices and others.

Many centrality measures exist for quantifying the importance of a node in a network, utilizing both local and global information. Local measures as degree centrality and closeness centrality have linear time complexity, but are limited in their usefulness. Global measures such as betweenness centrality are of a much higher time complexity but are very useful.

We focused on the group of the algorithms that are based on the "Shortest Path Search", especially on the betweenness centrality measure.

Betweenness centrality is used to distinguish the most influential vertices in a graph. It is the ratio of shortest paths passing through a certain vertex v to the total number of shortest paths between all pairs of vertices. Let σ st denote the number of shortest paths from a vertex s ∈ V to a vertex t ∈ V . σ st (v) denotes the number of shortest paths from s to t that go through v. The betweenness centrality index of a vertex v is given by:

BC(v) = ∑ s =v =t∈V σ st (v) σ st (1)
In social networks, it determines the individuals who influence the flow in the network. We consider a parallel betweenness centrality implementations based on Brandes' algorithm [START_REF] Brandes | A faster algorithm for betweenness centrality[END_REF].

The key concept of Brandes's approach is the dependency δ of a vertex v with respect to a given source vertex s. We define S(v) as the set of successor vertices of v.

δ s (v) = ∑ w∈S(v) σ sv σ sw (1 + δ s (w)), (2)
where σ sv is the number of shortest paths between nodes s and v and δ s (w) is the dependency of vertex w with respect to s. The recursive relationship between the dependency of a vertex and the dependency of its successors allows a more efficient calculation of the betweenness centrality. Brandes's algorithm splits the betweenness centrality calculation into two major steps:

1. Find the number of shortest paths between each pair of vertices 2. Sum the dependencies for each vertex Thus, BC measures are redefined as follow:

BC(v) = ∑ s =v δ s (v) (3)

Graph Visualization

The third element is a visualization module that normalizes and maps the results into graphic primitives (color, size, transparency, etc.) and renders the image. The final result is visualization. For example, the graph with weights that have been calculated by the graph analysis module, can be presented as a 3D graph where the vertex weight will be expressed as the color of the vertex. The basic submodules of visualization are:

1. normalization -includes the selection of the right scale; 2. mapping -is bringing the values to visual, for example, bringing number to color or volume; 3. layout calculation -is calculation of the positions of nodes depending on the layout (tree, circular, force-layout, etc.).

Normalization is necessary because data produced by centrality algorithm can be distributed differently. For example, a large number of nodes can have small centrality measure while a small number of nodes can have large centrality value. Without normalization, the difference between extremal values is so small that an analyst will not see any difference. For normalization are usually used scales that depends on the the distribution of values: linear scale, pow scale, log scale and others.

Mapping is the process when numerical or categorial values transforms to visual values. The visual values can be: size, shape, color, hue, saturation, opacity, texture, scaling speed, movement speed and rotation speed. For example vertex can be a cube and its rotation speed can express the centrality. For scaling speed, movement speed and rotation speed and opacity mapping is normalization from 0 to 1, because speed and opacity can be expressed as percentage from minimum for maximum. Shape and mapping can be defined only for categorial values, so mapping is the setting of specific shape or texture for each category. For color, hue and saturation mapping is the normalization of numerical value to RGB (red, green and blue value), where minimum value is setting as one color and maximum value as other color. For size it is important to take into account the shape. For example if cube is defined through length of side, so size should be calculated using the formula of dependence of side length on volume. It is important to note that the rotation speed also depends on the shape, and it can not be applied to sphere.

Layouts calculation is the calculation of the position of nodes in order to make a graph more easily to perceive. There are many layout methods [START_REF] Hu | Algorithms for visualizing large networks[END_REF] but the biggest part of them is based on the force model. For force layout it is necessary to set the charge for vertex (analog of electron -define the force with which the vertices of the graph will be repelled from each other) and length of edge (analog of springdefines the spring's ability to stretch).

Having the visual values and coordinates of the vertices one can render a graph to the image that will be the result of processing.

Implementation

We implemented the proposed concept and made experiments with the analysis of the betweenness centrality of graphs. In the implementation we considered 5 datasets of different sizes and edge density. The goal is to find the leaders of the community and evaluate how many friends they have. It is also interesting to find the sub-communities and evaluate their size. Th implementation of the pipeline includes 4 main modules -collection of data, graph storage, analysis with GPU and visualization.

Data collection

As data source we select the social network VKontakte, because it has an open API [START_REF]Vkontakte -api methods -developers[END_REF] for collection of public data.

In VK users can make their profiles private, so it is impossible to get any information about such accounts.

We collect data about users of one group "Go SlackLine Team" -a community of fans of walking on a sling [START_REF]Go slackline team community in vk[END_REF]. The community includes only 2104 users, but when we scan their friends we got 779020 users (around 370 friends per user in average). The collection took 112 minutes with 3 scanners that worked in parallel. This dataset contains many private profiles that will be filtered later.

Another, random data set, contains 402.000 users with open profiles who have at least 2 friends or subscribers. The collection took 215 minutes with 3 scanners that worked in parallel. It is important to note, that the second dataset was loaded more slowly than the first one because in the second case we loaded only open profiles with more data, while the first dataset includes many private profiles.

Graph storage

As a storage we select the graph database OrientDB [START_REF]Orientdb -graph database -multi-model database[END_REF], as it provides all required functionality and using SQL like syntax for querying. Also, OrientDB includes built in traversal function, web server that helps to implement necessary API and can be scaled to multiple servers for performance increase. As a database schema we select a schema that was described in our previous paper: it is the hierarchical schema for social networks that can aggregate or filter using classes and superclasses of the scheme hierarchy [START_REF] Kolomeets | Social networks analysis by graph algorithms on the example of the VKontakte social network[END_REF].

So, the data pipeline in graph storage module is organized as follows.

The "Data to schema" submodule is implemented on Node.js with the help of the OriendDB APIit is getting data from VKontakte API and brings graph to the schema of database. Using the built in functions, database syntax and Node.js we implement the "schema to schema" submodule that supports the and filtering of edges and vertices of the graph by property, class and superclass. It is also possible to traverse set of vertices. Using "schema to schema" submodule we are bringing data to the schema that is necessary for GPU analysis and for visualization.

For both the "Go SlackLine Team" and "Random data" graphs we aggregate "friend" and "subscribers" edges by one to get the relations between users.

Also for the first graph we made filtering by property "number of friend": we create 4 new graphs, where where deleted users who have less than 5, 4, 3 and 2 users. This was done because the first graph contains many users with only one "friend" edge -it happened because of the many private profiles. Vertices with one edge form a star structures that is not useful for the analysis, so filtering removes them. That's why we also collect another graph that has a higher edge density and less star structures to test performance on highly connected graph.

As the result we got the graphs that are presented in a table 1.

Graph analysis 4.3.1 Parallel processing using GPU

Meaningful information concerning graphs may be difficult to extract without applying specific graph algorithms. However, it is important to obtain results within acceptable times. For that purpose it can be interesting to consider parallel processing on GPU devices. A GPU consists of many individual Streaming Multiprocessors (SMs), each of which executes in parallel with the others. Each SM contains a set of cores, called Stream Processors (SPs) that share control logics and instruction caches.

The GPU includes a large amount of device memory with high bandwidth. Each SM has a low latency shared memory and is also attached with a read-only texture and constant caches. On each SM, there are also compiler-managed registers used as a local storage for each thread.

To best support graphics processors NVIDIA Corporation introduced Compute Unified Device Architecture (CUDA) a platform for a parallel computing.

In the CUDA programming model, a program consists of multiple phases that are executed on either the CPU or the GPU. Parallel functions executed on the GPU are called Kernels. When launched, a CUDA kernel is executed N times in parallel by N different CUDA threads. These threads are organized into a three-level hierarchy. All threads generated by the kernel are collectively called a grid, which is an array of thread blocks.

Due to such massive amounts of parallelism, GPUs are attractive platforms to accelerate computations for many applications (see [START_REF] Boyer | Solving knapsack problems on GPU[END_REF], [START_REF] Luo | GPU based parallel genetic algorithm for solving an energy efficient dynamic flexible flow shop scheduling problem[END_REF], [START_REF] Bastien Plazolles | Simd monte-carlo numerical simulations accelerated on GPU and xeon phi[END_REF]) and in particular graph processing [START_REF] Dabah | Hybrid multi-core CPU and GPU-based b&b approaches for the blocking job shop scheduling problem[END_REF].

Graph visualization

For graph visualization we used D3.js library [START_REF] Bostock | D3.js -data-driven documents[END_REF]. Betweenness centrality measure is expressed by color and size of the vertex -double expression helps to percept value more accurately. For size we use power scale non-normalized betweenness centrality. As the size of the vertices in D3 is defined by radius of the sphere, we map volume V (that is equal to centrality) into radius r by next formula

r = 3 3V 4π . (4)
For color we use linear scale no normalize betweenness centrality. The color value was mapped into RGB value from blue to red (Figure 3). As the layout we took 3D force layout algorithm that is based on the charge of vertices (the force with which the vertices of the graph repel) and strength of edges (edge stretching ratio). For force layout we calculate values of charge and strength individually for every vertex and edge based on the betweenness centrality and degree of each vertex (number of ingoing and outgoing edges for each vertex) as presented in [START_REF] Kalameyets | The technique of structuring social network graphs for visual analysis of user groups to counter inappropriate, dubious and harmful information[END_REF]. We set values according to the following rules:

1. For vertices that have only one edge and for that edge: (a) to set small charge value for vertex;

(b) to set maximum strength value of 1 for edge (the edge cannot be stretched); (c) to set a small edge length.

2. For vertices that have the biggest betweenness centrality (top 5%) and for edges between these vertices:

(a) to set a big charge value for vertex;

(b) to set maximum strength value of 1 (the edge cannot be stretched) for edges between these vertices (having the largest number of edges).

(c) to set a big edge length.

3. For all other vertices and edges:

(a) to set an average charge value for vertex;

(b) to set value of 0.1 for edge (the edge can be strongly stretched);

(c) to set an average edge length.

As a result, vertices with highest betweenness centrality will be far from each other and will form a "skeleton" of the graph. The vertices with only one edge will be grouped into clouds. Other vertices will be between the most central vertices.

The visualization of datasets from table 1 is presented in the pictures 4 and 5 and via the link [START_REF]Graphs visualization[END_REF]. For dataset with random users we filter graph to 7000 nodes with biggest centrality.

The big red nodes indicate the leaders of the community. Highlighting by color and size helps to manually select these users if needed. It is also possible to identify sub-communities that are formed around the most central nodes.

Discussion

As we see, analysis of structure in social networks require different solutions for every stage of analysis. They can be united in a single pipeline that can make such analysis automatic.

The biggest challenge is increasing the speed of each part of data pipeline to get results in acceptable time. The decisions based on scalable graph databases and usage of GPUs for data processing can significantly reduce time of analysis.

Modern graph storages can perform basic manipulations with graphs by their own, including graph transformations to the specific schemas. Such an approach helps to reduce the needs of data transferring between modules of storage and analysis for simple operations, such as filtering and aggregation. From Table 1, we note that computing accelerators GPUs permit one to reduce computing time when the graphs are sufficiently large, e.g., remove 2 dataset and random dataset. In the particular case of remove 2 dataset we observe that we obtain a speed up equal to 2.84x. In the case of random dataset the speed up is more important and we have stopped the computations on the CPU after 24H. This is due to the fact that thread occupancy on GPU is more important for these two graphs.

Graph visualization is the result of the analysis. Perception is increased by metrics expression. For example, on small graph 4d it is possible to locate central nodes by graph topology even without coloring by centrality. But when graph is growing up to the structure as in Figure 4a, it is becomes complicated to do that without the help of node coloring.

Conclusion

In the paper we present the reference architecture based on the data pipeline for the analysis of the graphs of social networks. Based on this pipeline it is possible to develop a tool that is able to filter, aggregate and process big graphs of social networks, and at the same time takes into account its structure. We present data collection, graph storage, graph analysis by GPU and graph visualization modules for that pipeline. We implement that pipeline and conducted experiments based on the calculation of betweenness centrality of the graphs in real-world social network.

Possible applications of the proposed architecture are not only the analysis of social networks; it can also be used for analyzing big and unstructured graphs in other areas. In future work we plan to extend the current implementation of the pipeline architecture so as to take into account other centrality measures. We also will investigate the possibilities of speed up the calculations for centrality measures, make

Figure 1 :

 1 Figure 1: Proposed reference architecture in form of pipeline

Figure 2 :Algorithm 1 : 3 if v = s then 4 σ8

 2134 Figure 2: GPU memory architecture

Figure 3 :

 3 Figure 3: Color mapping that was used for betweenness centrality

  (a) remove 2 dataset -users who have at least 2 friends (b) remove 3 dataset -users who have at least 3 friends (c) remove 4 dataset -users who have at least 4 friends (d) remove 5 dataset -users who have at least 5 friends

Figure 4 :

 4 Figure 4: Visualisation of "Go SlackLine Team" community with betweenness centrality expressed by size of the vertex, color of vertex and and force-layout parameters. Big red nodes have big values of betweenness centrality, while small blue nodes have small values.

Figure 5 :

 5 Figure 5: Dataset of 402916 users that was reduced to 7000 users with biggest centrality measure

Table 1 .

 1

	Dataset	Nodes	Edges	Time CPU (msec) Time GPU (msec)
	remove 2	9842	61438	80373	28296
	remove 3	4919	32020	14967	13983
	remove 4	3038	17060	3886	7764
	remove 5	2187	8706	1021	5325
	random 402916 9850186	+24H	5765261

Table 1 :

 1 Execution times

Acknowledgment

Parts of this study (Sections 3.3 and 4.3) has been made possible by a funding of PHC Tassili Bigreen 40160QB -Algorithms of large data graphs on distributed memory architecture. Parts related to the social networks (Sections 2, 3.1, 3.4, 4.1 and 4.4) was supported by the grant of RSF #18-71-10094 in SPIIRAS. Parts related to the big data storage (Sections 3.2 and 4.2) are carried out with support of Ministry of Education and Science of the Russian Federation as part of Agreement No. 05.607.21.0322 (identifier RFMEFI60719X0322).