Emmanuel Frénod

Sever A Hirstoaga

Mathieu Lutz

Long time simulation of a highly oscillatory Vlasov equation with an exponential integrator

We change a previous time-stepping algorithm for solving a multi-scale Vlasov-Poisson system within a Particle-In-Cell method, in order to do accurate long time simulations. As an exponential integrator, the new scheme allows to use large time steps compared to the size of oscillations in the solution.

Introduction

In this paper, we improve the time numerical scheme introduced in [START_REF] Frénod | An exponential integrator for a highly oscillatory Vlasov equation[END_REF], in order to make long time simulation of the following Vlasov equation

   ∂f ε ∂t + v ε ∂f ε ∂r + - r ε + E ε (r, t) ∂f ε ∂v = 0, f ε (0, r, v) = f 0 (r, v) , (1.1)
where 0 < ε ≪ 1, r ∈ R is the position variable, v ∈ R the velocity variable, f ε = f ε (r, v, t) is the distribution function, f 0 is given, andr ε + E ε (r, t) corresponds to the electric field. The difficulty in the numerical solution of this equation lies mainly in the multi-scale aspect due to the small parameter ε.

The main application will be the case when the electric field E ε is obtained by solving the Poisson equation. We will thus have to solve the following nonlinear system of equations

           ∂f ε ∂t + v ε ∂f ε ∂r + - r ε + E ε (r, t) ∂f ε ∂v = 0, ∂ ∂r rE ε = ρ ε (t, r) , ρ ε (t, r) = R f ε (t, r, v) dv, f ε (0, r, v) = f 0 (r, v) . (1.2)
This simplified model of the full Vlasov-Maxwell system is particularly adapted to the study of long and thin beams of charged particles within the paraxial approximation assuming that the beam is axisymmetric (see [START_REF] Frénod | Long time simulation of a beam in a periodic focusing channel via a two-scale PIC-method[END_REF] and the references therein).

We will also test our scheme when E ε (r, t) = -r 3 .

(1.3)

As in [START_REF] Frénod | An exponential integrator for a highly oscillatory Vlasov equation[END_REF], we solve numerically the Vlasov equation by a particle method, which consists in approximating the distribution function by a finite number of macroparticles (see [START_REF] Birdsall | Plasma Physics via Computer Simulation[END_REF]). The trajectories of these particles are computed from the characteristic curves of the Vlasov equation, whereas the term E ε is computed, when obtained from the Poisson equation, on a mesh in the physical space. The contribution of this work is to improve the time numerical scheme proposed in [START_REF] Frénod | An exponential integrator for a highly oscillatory Vlasov equation[END_REF], for solving in long times the stiff characteristics associated to equation (1.1)

     dR dt = V ε , dV dt = - R ε + E ε (R, t), (1.4)
provided with the initial conditions R(0) = r, V (0) = v. We note that when E ε is given by (1.3), solving (1.4) reduces to solve the undamped and undriven Duffing equation

R ′′ (t) + R(t) ε 2 + R 3 (t) ε = 0 (1.5) with initial conditions R(0) = r, R ′ (0) = v/ε.
The solution of (1.1) is represented by a beam of particles in phase space moving along the characteristics curves (1.4). When the electric field E ε is zero the beam rotate around the origin with period 2πε. Otherwise, the dynamical system (1.4) can be viewed as a perturbation of the system obtained when the electric field is zero (see [START_REF] Lutz | Application of Lie Transform Techniques for simulation of a charged particle beam[END_REF]). When the electric field E ε is obtained by solving the Poisson equation or if it is given by (1.3), the beam evolves by rotating around the origin in the phase space, and in long times a bunch forms around the center of the beam from which filaments of particles are going out. Classical explicit numerical methods require very small time step in order to capture the fast rotation. Consequently, long time simulations are very tedious.

In [START_REF] Frénod | An exponential integrator for a highly oscillatory Vlasov equation[END_REF] the authors introduced a new explicit scheme based on Exponential Time Differencing (ETD) integrators (see [START_REF] Cox | Exponential time differencing for stiff systems[END_REF] and [START_REF] Hochbrück | Exponential integrators[END_REF]). The idea of the algorithm was the following: first, for each macroparticle as initial condition, we solve the ODE in (1.4) over some fast (i.e. of order ε) time by using a 4th order Runge-Kutta solver. The fast time is the same for all the macroparticles. Then, by means of the variation-of-constants formula we compute an approximation of the solution over a large whole number of fast times. Thus, this scheme (recalled in Algorithm 2.1) allows to take time steps ∆t varying from 0.1 to 1 and therefore, when ε varies from 10 -5 to 10 -2 , the numerical gain increases from 3 to 10 5 when compare the scheme to a reference solution. In addition, for short time simulation (t = 3.5) the results are quite precise (the numerical error is about 10 -3 knowing that the beam is of size 1). For time of simulation less than 30, this ETD method still gives good qualitative behaviors. Nevertheless, it fails to capture precisely the filamentation phenomena leading even to unstable simulation in long times.

In this paper we improve the time-stepping method following a simple idea. The fast time in the above description of the algorithm was chosen in [START_REF] Frénod | An exponential integrator for a highly oscillatory Vlasov equation[END_REF] to be the mean of all the numerically computed periods for the particle trajectories. The authors remarked that this choice gives better results than using 2πε. The algorithm that we propose now is to not use a fixed value for the fast time, but to push each particle with its period. This means that the first step should consist in solving the ODE starting from each particle over different fast times (the particles computed periods). However, implementing this simple idea turns out to be not so easy and in addition asks for changing the order of the steps in the algorithm. We detail this problem in Section 3. Our simulations show that using precise periods for each particle and at each macroscopic time step results in a more accurate ETD scheme in long times. In addition, by following the proof lines in [START_REF] Frénod | An exponential integrator for a highly oscillatory Vlasov equation[END_REF], we show formally that the algorithm is still an approximation when using any value for the fast time. We recall that in [START_REF] Frénod | An exponential integrator for a highly oscillatory Vlasov equation[END_REF], the authors justified the algorithm when using only 2πε as fast time. From now on we will use the incorrect term of period to indicate the time that a particle takes to do a complete tour in the phase space.

The remainder of the paper is organized as follows. In Section 2 we briefly recall the ETD scheme introduced in [3] and we do long time simulation. Then, Section 3 is devoted to the improvement of the method. Eventually, in Section 4, we implement and test the new algorithm on the Vlasov equation in the two cases of electric field.

Long time simulation of the exponential integrator

We first recall the exponential integrator introduced in [START_REF] Frénod | An exponential integrator for a highly oscillatory Vlasov equation[END_REF] for solving efficiently in short times the Vlasov equation. Then, we discuss the long time simulations done with this algorithm in the case of E ε given by (1.3), in Section 2.2 and in the Vlasov-Poisson case in Section 2.3.

The previous exponential integrator for the Particle-In-Cell method

The time-stepping scheme that we describe in this section for solving the Vlasov equation (1.1) is proposed in the framework of a Particle-In-Cell method (PIC). A PIC method (see [START_REF] Birdsall | Plasma Physics via Computer Simulation[END_REF]) consists in approximating the distribution function f ε , solution of (1.1), by a cloud of macroparticles (R i , V i ) i∈{1,...,Np} (each one of them stands for a set of physical particles) of weight ω i advanced along the characteristics curves (1.4). In other words we will approach the distribution function by a sum of Dirac masses centered at the macroparticles positions and velocities

f ε (r, v, t) ≈ Np i=1 ω i δ (r -R i (t)) δ (v -V i (t)) .
(2.1)

The weights are chosen such that

Np i=1 ω i = R 2 f 0 (r, v) drdv, (2.2)
and the particles are initialized according to the probability density associated with f 0 . The aim of the exponential integrator introduced in [START_REF] Frénod | An exponential integrator for a highly oscillatory Vlasov equation[END_REF] is to solve (1.4) by using big time steps with respect to the typical period of oscillation, which is about 2πε. Now, we recall the main ideas of this algorithm. For simplicity we denote by y the characteristics, i.e.

y = R V . (2.3)
Under the assumption for all

n tn+N •2πε tn R(τ ) 0 E ε (τ, R(τ )) dτ ≈ N • tn+2πε tn R(τ ) 0 E ε (τ, R(τ )) dτ, (2.4
) where R is some 2πε-periodic rotation in the phase space, the authors derived the following scheme. Fix a time step ∆t ≫ 2πε and determine the unique integer N and the unique real o such that

∆t = N • 2πε + o, 0 ≤ o < 2πε.
(2.5)

For each macroparticle y i (denoted by y for simplicity) apply Algorithm 2.1. Assume that y n the solution of (1.4) at time t n is given.

1. Compute y (t n + 2πε) by using a fine Runge-Kutta solver with initial condition y n .

2. Compute y (t n + N • 2πε) by the rule

y (t n + N • 2πε) = y n + N y (t n + 2πε) -y n (2.6)
3. Compute y at time t n+1 by using a fine Runge-Kutta solver with initial condition y(t n + N • 2πε), obtained at the previous step.

Remark 2.2. Hypothesis (2.4) is satisfied if the time to make one rapid complete tour (in the phase space) is quasi constant and close to 2πε and if τ → E ε (τ, y(τ )) is about 2πε-periodic.

This simple algorithm was formally proved in [START_REF] Frénod | An exponential integrator for a highly oscillatory Vlasov equation[END_REF] to provide an approximation of the solution under the assumption in (2.4). The capability of the scheme relies on the following. When the solution is periodic, say y(t n + 2πε) = y n , the second step of the algorithm reduces to an exact statement. Otherwise, it can happen that y(t) 2 = R(t) 2 + V (t) 2 vary slowly in time, typically when the electric field is given by the Poisson equation (see [START_REF] Lutz | Application of Lie Transform Techniques for simulation of a charged particle beam[END_REF]). In this case, the scheme allows to capture the small variations of the amplitude of y since it solves them during the first step. Nevertheless, it should be noted that the algorithm works provided that these variations do not change considerably during the second step.

Therefore, our aim now is to improve the algorithm in order to be able to capture also the small variations of the period. This viewpoint was outlined in [START_REF] Frénod | An exponential integrator for a highly oscillatory Vlasov equation[END_REF]. More precisely, the authors noticed that the results are much better, especially in the Vlasov-Poisson case, when replacing 2πε in Algorithm 2.1 by the mean of the particles times to make the first complete tour. The so-obtained scheme was called the modified ETD algorithm. However, as we will see in the next two sections, this scheme still needs to be improved in order to do accurate long time simulations. The idea is that using a more accurate period when pushing particles leads to better results.

Application to long time simulation of the undamped and undriven

Duffing equation In this section we consider the Vlasov equation (1.1) provided with the electric field given by (1.3) and with the initial condition (see [START_REF] Frénod | Long time simulation of a beam in a periodic focusing channel via a two-scale PIC-method[END_REF])

f 0 (r, v) = n 0 √ 2πv th exp - v 2 2v 2 th χ [-0.75,0.75] (r), (2.7)
where the thermal velocity is v th = 0.0727518214392 and χ [-0.75,0.75] (r) = 1 if r ∈ [-0.75, 0.75] and 0 otherwise. In the particle approximation, we implement this distribution function with N p = 20000 macroparticles and equal weights w i = 1/N p . Moreover, this initial condition will be used all along this work. In this case, the characteristics equation or equivalently the Duffing equation (1.5) has periodic solutions in time (see the appendix). Thus, the time to make one rapid complete tour in the phase space depends only on the initial condition. It is actually constant in time and it corresponds to the period of the trajectory. The repartition of the periods with respect to the initial condition in (2.7) is given in Fig. 1. These values are computed with a fine RK4 solver and they are in accordance with formula (A.8) in the appendix. Notice that the periods are very close to 2πε, they belong to (2πε -1.5ε 2 , 2πε). Now we compare the modified ETD scheme with a reference solution, obtained by solving (1.4) with explicit 4th order Runge-Kutta scheme with small time step. The solution in the phase space (R, V ) at different large times, obtained with ε = 0.01, is illustrated in Fig. 2. We notice that beyond t = 30 the errors become significant. Next, we explain the reasons. Imagining a position (or velocity) trajectory in time being sinusoid-like, it is easy to see that a particle for which the period is underestimated (by the mean period) will drift inward in the phase space when applying the second step of the algorithm. When the period is overestimated, the particle will clearly drift outward. In addition, with the same approximation of the periods, larger is the amplitude of the sinusoid, bigger is the error made by the third step of the modified ETD scheme (see Fig. 3). Consequently, all the particles close to (0, 0) in the phase space are well treated by the algorithm, while the particles far from the center of the beam accumulate significant error in time. This behaviour was noticed in reference [START_REF] Frénod | An exponential integrator for a highly oscillatory Vlasov equation[END_REF] in short time simulation, in terms of errors for particles off or on the slow manifold.

Figure 3: In green : the amplitude of the exact solution is 0.5 and the period is 2πε. In blue the solution obtained with the ETD Scheme with a period 2πε -15ε 2 . In orange : the amplitude of the exact solution is 1.5 and the period is 2πε. In purple the solution obtained with the ETD Scheme with a period 2πε -15ε 2 .

Application to long time simulation of the Vlasov-Poisson test case

In this section we consider the Vlasov-Poisson equation (1.2) provided with the initial condition (2.7). The calculus done in the appendix for computing periods is now difficult to achieve. Therefore, in this case, we compute the time to make one fast tour by using a fine RK4 solver. The Poisson equation is simply solved by means of the trapezoidal formula for the integral in r, with 256 cells. As in the previous section, the fast time depends on the initial condition but in addition, it changes slowly in time. The same happens for the amplitude y (t) 2 = R(t) 2 + V (t) 2 , see Figs. 5 and6.

The comparison between the modified ETD scheme and a reference solution obtained with explicit 4th order Runge-Kutta scheme with small time step is summarized in Fig. 7. We see from Figs. 2 and7 that the dynamics and/or the filamentation in the Vlasov-Poisson case is slower than that in the case of E ε given by (1.3). Certainly, this is because of bigger particle periods (compare Figs. 1 and4)

Now, we can recall the discussion from the previous section about the consequences of using approximated period within the second and the third steps of the algorithm. However, in this Vlasov-Poisson case, the periods distribution is more complicated and thus, it seems more difficult to clearly state how the approximation influences long time simulation. We only remark the following. The error done for particles at the extremities of the beam is less significant than in the previous Vlasov case. The reason is that the mean of the initial periods is very close to the periods of the particles far from the center of the beam (see Figs. 4 and5). As for those close to the center (0, 0), we can see in Fig. 7 that particles slightly drifting both outward and inward are present, as expected from Fig. 4.

Therefore, in the next section we will compute at each time step the period of each particle, in order to take into account this slow evolution of the periods distribution. We recall that the slow evolution of the amplitudes is considered when applying the first step of the algorithm.

The new time-stepping scheme

In this section, we change Algorithm 2.1 by improving the approximation of each particle's time to make one rapid complete tour. More precisely, within the first step, instead of solving the ODE (1.4) during some fixed fast time for all the particles, we will push each particle with its own fast time. Unfortunately, implementing this idea in Algorithm 2.1 will not work in the Vlasov-Poisson case. The reason is the following. Suppose that we have the particles (y i ) i∈{1,...,Np} and their computed periods (T i ) i∈{1,...,Np} at time t n . First, we finely solve the ODE with each particle as initial condition, during different times (the T i s), paying attention to push enough in time (the maximum period) all the particles in order to calculate the correct self-consistent electric field. Then, applying the second step of Algorithm 2.1 with the corresponding N i will lead to particles at different times t n + N i T i . Now, it is impossible to apply the third step of the algorithm, because the particles arrived at the minimum of t n + N i T i i∈{1,...,Np} can not be pushed with the right electric field since all the particles are not available at that time. This problem is solved by changing the steps of the algorithm, as it is described below, in Algorithm 3.4.

Firstly, note that dynamical system (1.4) can be rewritten as

y ′ (t) = 1 ε M y (t) + L ε (t, y (t)) , (3.1)
where y is defined by (2.3) and M and L ε are given by Let T be a positive real number which is intended to be close to 2π and let r (τ ) be the matrix defined by

M = 0 1 -1 0 and L ε = 0 E ε . (3.2)
r (τ ) = cos 2π T τ sin 2π T τ -sin 2π T τ cos 2π T τ , (3.3)
which is a T -periodic function. Then we compute

d dτ r - τ ε y (τ ) = 2π εT r - τ ε M y (τ ) + r - τ ε 1 ε M y (t) + L ε (τ, y (τ )) = r - τ ε L ε (τ, y (τ )) + 1 - 2π T 1 ε r - τ ε M y (τ ) = r - τ ε β ε (τ, y (τ )) , (3.4)
where

β ε (τ, y (τ )) = L ε (τ, y (τ )) + 1 - 2π T 1 ε M y (τ ) . (3.5)
Integrating (3.4) between s and t with s < t thus leads to Now we establish the time-stepping scheme. We write equation (3.6) with s = t n and t = t n+1 = t n + ∆t in order to specify how the solution is computed at time t n+1 from its known value at time t n . Thus, for each particle of the beam we are faced with the numerical computation of the integral from t n to t n+1 involved in the right hand side of (3.6). Subsequently, we denote by y i the particle satisfying equation (3.1) provided with the initial condition y n i . We denote by T n i the time to make the first rapid complete tour starting at t n . This time is computed numerically.

y (t) = r t -s ε y (s) + r t -s ε t s r s -τ ε β ε (τ, y (τ )) dτ. (3.6)
Since we want to build a scheme with a time step ∆t much larger than the fast oscillation, we first need to find the unique positive integers N n i and the unique reals

o n i ∈ [0, T n i ) such that ∆t = N n i T n i + o n i . (3.7)
The derivation of the scheme, Algorithm 3.4, is based on the following approximation.

Approximation 3.1. We have for any i ∈ {1, . . . , N p }

t+N n i T n i t r n i t -τ ε β ε (τ, y i (τ )) dτ ≈ N n i t+T n i t r n i t -τ ε β ε (τ, y i (τ )) dτ (3.8)
where t = t n + o n i and r n i corresponds to the matrix in (3.3) with T = T n i /ε. Remark 3.2. Approximation 3.1 is valid if we make the assumptions that the times for all particles to do the first rapid tour starting from t evolve slowly in time and that the particle and the electric field evaluated at the particle position are quasi-periodic in time (with a period close to the time to make the first rapid complete tour).

Lemma 3.3. Under Approximation 3.1 we obtain for any i ∈ {1, . . . , N p } and any time t n

y i (t n+1 ) ≈ y i (t n + o n i ) + N n i y i (t n + o n i + T n i ) -y i (t n + o n i ) , (3.9)
where y i is the solution to equation (3.1) with a given initial condition y i (t n ) = y n i . Proof. Writing the variation-of-constants formula from s = t n + o n i to t = t n+1 and recalling (3.7) we obtain the following exact scheme

y i (t n+1 ) = y i (t n + o n i ) + t n+1 tn+o n i r n i t n + o n i -τ ε β ε (τ, y i (τ )) dτ (3.10) since r n i (N n i T n i /ε
) is the identity matrix. Then, under Approximation 3.1 we obtain Remark 3.5. As in [START_REF] Frénod | An exponential integrator for a highly oscillatory Vlasov equation[END_REF], the way to compute the (T n i ) i from (y n i ) i is the following. First, we solve the characteristics of equation (1.4) with a time step (∆t) RK = 2πε/100, for all initial conditions y n i until all the particles reach their trajectory's third extremum. The criterion for finding these extrema is the velocity's change of sign. We then state that each particle's period is the time interval between the first and the third extremum.

y i (t n+1 ) ≈ y i (t n + o n i ) + N n i tn+o n i +T n i tn+o n i r n i t n + o n i -τ ε β ε (τ, y i (τ )) dτ. ( 3
Remark 3.6. The time step (∆t) RK chosen in the third step of the algorithm is 2πε/100. It is easy to see that the reals (t n + o n i ) i and (t n + o n i + T n i ) i are located on a few cells of length (∆t) RK . Thus, we approximate the values y i (t n + o n i ) and y i (t n + o n i + T n i ) by quadratic interpolations.

Figure 1 :

 1 Figure 1: In red the computed periods with respect to the initial positions (at left) and to the initial velocities (at right). The case of E ε = -r 3 with ε = 0.01. In blue the mean of the periods, in green the 2πε value.

Figure 2 :

 2 Figure 2: The case of E ε = -r 3 with ε = 0.01. In green: the reference solution obtained with a Runge-Kutta algorithm with time step ∆t = 2πε/100. In red: the result of the modified ETD scheme with time step ∆t = 0.5. The final times are, from left to right and from top to bottom t = 10, 20, 30 and 40.

Figure 4 :

 4 Figure 4: In blue the computed periods with respect to the initial positions, in the Vlasov-Poisson case with ε = 0.01. In red the mean of the periods, in green the 2πε value.

Figure 5 :

 5 Figure 5: The periods distribution with respect to the initial periods (in blue) at times t = 5, 10, 15, and 20. The Vlasov-Poisson case with ε = 0.01.

Figure 6 :

 6 Figure 6: The modulus (R (t) , V (t)) 2 with respect to the initial modulus (in blue) at times t = 5, 10, 15, and 20. The Vlasov-Poisson case with ε = 0.01.

Figure 7 :

 7 Figure 7: Vlasov-Poisson test case with ε = 0.01. In red: the reference solution obtained with a Runge-Kutta algorithm with time step ∆t = 2πε/100. In green: the result of the modified ETD scheme with time step ∆t = 0.5. The final times are, from left to right and from top to bottom: t = 5, 10, 30 and 60.

Figure 8 :

 8 Figure8: The case of E ε = -r 3 with ε = 0.001. In green: the reference solution. In red: the solution obtained with the modified ETD scheme (left) and with the improved ETD scheme (right). From top to bottom : t = 10, t = 20, t = 30 and t = 37. The time step used for the ETD schemes is ∆t = 0.5.16

Figure 9 :

 9 Figure9: Vlasov-Poisson test case with ε = 0.001. In red: the reference solution. In green: the solution obtained with the modified ETD scheme (left) and with the improved ETD scheme (right). From top to bottom : t = 15, t = 30, t = 45 and t = 60. The time step used for the ETD schemes is ∆t = 0.5. 17

Figure 10 :

 10 Figure 10: The cases of Vlasov-Poisson (left) and of Vlasov with E ε = -r 3 (right), when ε = 0.0001. In red: the reference solution. In green: the solution obtained with improved ETD scheme. From top to bottom : t = 10, t = 30, t = 60 and t = 90. The time step for the ETD scheme is ∆t = 0.5. 18

  Assume that for each i ∈ {1, . . . , N p }, y n i , the value of a solution of (3.1) at time t n , is given. 1. Compute from (y n i ) i∈{1,...,Np} the periods (T n i ) i∈{1,...,Np} at time t n . 2. For each i ∈ {1, . . . , N p } compute the unique positive integers N n i and the unique reals For each i ∈ {1, . . . , N p } compute y i (t n + o n i ) and y i (t n + o n i + T n i ) by using a fine Runge-Kutta solver with initial condition y n i . 4. For each i ∈ {1, . . . , N p } compute an approximation of y i (t n+1 ) thanks to

	Applying now formula (3.6) with s = t n + o n i , t = t n + o n i + T n i and r = r n i yields
	y i (t n + o n i + T n i ) -y i (t n + o n i ) =	tn+o n i +T n i tn+o n i	r n i	t n + o n i -τ ε	β ε (τ, y i (τ )) dτ (3.12)
	since r n i (T n i /ε) is the identity matrix. Thus, injecting (3.12) in (3.11) leads to (3.9).
	Using Lemma 3.3, we deduce the following algorithm to compute y n+1 i	from y n i .
	Algorithm 3.4. o n i ∈ [0, T n i ) such that	∆t = N n i T n i + o n i .		(3.13)
	3. y n+1
						.11)

i = y i (t n + o n i ) + N i y i (t n + o n i + T n i )y i (t n + o n i ) .

(3.14)

Numerical simulations

We now do long time simulations with the improved ETD scheme (Algorithm 3.4) in the two cases of Vlasov equation. The results show that the new scheme works in long times while the modified ETD scheme becomes unstable. We can observe the idea underlined from the begining of the paper: using all along the simulation accurate approximations of each particle period leads to very accurate solutions. Thus, we note that the numerical solutions in the first case (Section 4.1) are very good since very precise values for the periods are available and in addition they do not change in time. On the contrary, in the Vlasov-Poisson case the periods are numerically approximated at several levels and therefore the scheme does not perform as well as in the first case.

Long time simulation of the undamped and undriven Duffing equation

In this section we consider the Vlasov equation (1.1) provided with the electric field given by (1.3) and with the initial condition (2.7). We recall that we use 20000 macroparticles with equal weights. Note that the first step of Algorithm 3.4 is executed only initially, since the particle periods are constant in time.

The results obtained with ε = 0.001 are summarized in Fig. 8 and with ε = 0.0001 in Fig. 10 at right: we compare the outcome of the algorithm with a macroscopic time step ∆t = 0.5 to a reference solution computed with a small time step, 2πε/100. As already mentioned in Section 2.2 (see also the appendix), the particles moving according to (1.4) with given E ε , have periodic trajectories and thus, the periods depend only on the initial conditions. We observe on Figs. 8 and 10 that both the filamentation phenomena and the fast rotation are well treated in long times by the improved ETD scheme (the old scheme is unstable at these times). Notice also that when ε = 0.0001, the integers N n i are about 800, meaning that the ETD scheme is about 800 times faster than the reference solution.

Long time simulation of the Vlasov-Poisson test case

In this section we consider the Vlasov-Poisson equation (1.2) provided with the initial condition (2.7). The Poisson equation is solved as mentioned in Section 2.3. The results obtained with ε = 0.001 and the same time steps as above are summarized in Fig. 9. The case of ε = 0.0001 is illustrated in Fig. 10 at left. Again, one can see the slower filamentation of the Vlasov-Poisson case in comparison with the given electric field case. The time to make one rapid complete tour evolves slowly in time (see Section 2.3). Therefore, the approximations made in Algorithm 3.4 lead to accurate results. In particular the particle filaments are well treated by the improved ETD scheme. Note again that the new algorithm is about 80 times faster (when ε = 0.001) than the reference solution.

Concluding, the scheme is able to produce quite accurate numerical solutions for stiff Vlasov type equations for different small values of ε with the same computational cost, which is rather close to that of a reduced model.

A Appendix: Periods calculus for an undamped and undriven Duffing equation

Let ε > 0 be some small parameter. The solution to the following Duffing-type equation

can be written by using Jacobi elliptic functions. In this appendix we obtain by elementary calculus (see [START_REF] Hale | Ordinary differential equations[END_REF]), an approximated value of order 3 in ε for the period of the solution. In particular, we obtain explicitly how the period T depend on the initial condition (r 0 , v 0 ). The orbits of the solutions are level curves of the Hamiltonian function

where V stands for R ′ . As in Chapter V of reference [START_REF] Hale | Ordinary differential equations[END_REF], we denote the restoring force associated to the hard spring described by equation (A.1) by

and by

the potential energy. Since the function G has an absolute minimum in (0, 0) and no other critical point, all orbits are periodic. In addition, the closed orbit of a periodic solution is symmetric with respect to the R-axis and intersect it at two points, (a, 0) and (b, 0), with a < b. Taking into account that the function g is odd, we have a = -b and finally, we can determine an implicit formula for the period of the solution whose orbit intersect the R-axis in (b, 0):

where h is the value of the Hamiltonian on the solution of system (A.1)

Replacing h in (A.2), we obtain

which by Taylor expansion (recall 0 < ε ≪ 1) results in

Therefore, the parameter α = b 2 ε 2 is small when ε ≪ 1. Thus, by Taylor expanding to second order the function α → 1

for each R, we obtain the following approximation to the period


Pierre Maret
email: pierre.maret@univ-st-etienne.fr

Frédérique Laforest
email: frederique.laforest@univ-st-etienne.fr

Dimitri Lanquetin
email: dimitri.lanquentin@gmail.com

A Semantic Web Model for Ad Hoc Context-Aware Virtual Communities Application to the Smart Place Scenario

Keywords: Communities, Mobility, Services, User, Semantic Web, RDF, Ontology

In this paper, we propose a model for an open framework that allows mobile users to create and to participate to context-aware virtual communities. The model we propose and implement is a generic data model fully compliant with the semantic web data model RDF. This model is suited to let mobile end-users use, create and customize virtual communities. We combine fundamentals for a decentralized semantic web social network with context-aware virtual communities and services. Smart cities scenarios are typically targeted with this approach. It can be implemented in places like metro stations, museums, squares, cinemas, etc. to provide ad hoc context-aware information services to mobile users.

INTRODUCTION

A virtual community (VC) is a computer supported space where information can be shared inbetween stakeholders with common interest or purpose [START_REF] Preece | Sociability and usability in online communities: Determining and measuring success[END_REF][START_REF] Koch | Mobile Communities Extending Online Communities into the Real World[END_REF]. Millions of VCs exist on the Internet and they form what is called the Social Web, where people can join, leave and participate in many VCs [START_REF] Bouras | A web-based virtual community[END_REF]. In this paper, we address the topic of context-aware virtual communities and more specifically we present a data model and its implementation suited to let mobile end-users use but also create and customize VCs. Some community platforms take advantage of the mobile context of their users (GPS coordinates, IDs of close devices) to provide a specific service. Examples are numerous: Personal Smart Spaces [START_REF] Gallacher | Linking between personal smart spaces[END_REF], Group Me [START_REF] Guo | GroupMe : supporting group formation with mobile sensing and social graph mining[END_REF], Meeting Assistant [START_REF] Zenker | Towards meeting assistance: An integrated appointment assistance and group pedestrian navigation system[END_REF][START_REF] Al Ridhawi | Policy-based personalized context dissemination for location-aware services[END_REF]. They use context information to provide guidance, profile matchmaking or recommendations. Each platform provides a specific service. Users willing to use (not even to combine) various services face the so called "silo" problem and they have to register to each platform [START_REF] Yeung | Decentralization: The future of online social networking[END_REF]. Also, these platforms don't let users define the services they need in their communities. The platforms proposing user-defined communities require programming skills. Synthesizing all these remarks, nowadays community platforms are closed platforms that do not allow to take profit to the open world of open data, com-munities are hardly tunable by their creators without computing skills, the sharing of profile information or knowledge between communities and with the open world is hard or even impossible.

In smart cities, users are supposed to move and use various services. So, there is need for a model and an open architecture for users to create the communities they want, with the services they want, and at the location they want (or more generally in the context they want the services to be used).

In this paper, we propose a model and a platform architecture for ad hoc context-aware communities: communities can be created by naive end-users with a selection of pre-defined semantically described services. Users get access to these communities with a single sign-in. Our model makes use of Semantic Web technologies which allows it to provide selfdescribing services and to offer a open door to the open linked data inand out of the virtual communities. The semantic web approach promotes open data model, machine readable data and reasoning, which let the users be supported by personal software agents to manage their personal data and social relations in respect with the chosen policy. Our platforms also uses the multi-agent paradigm to support users' interactions. These interactions take advantage of context information to help services tune their offered functionalities. The multi-agent paradigm emphasizes autonomy and cooperation of communicating entities with goals. Our design typically addresses smart cities scenarios. It can be applied in places like metro stations, museums, public squares, cinemas, park places, etc.

We first present a state of the art related to the main features for communities: contents, user profile and services. Then we make a tour of existing community platforms. In section 3 we present our conceptual framework along the three main features from the state of the art. In section 4 we provide a description of our implementation, and conclude in section 5.

CONTENTS, USER PROFILE AND SERVICES IN VCS

Contents

Contents are information pieces exchanged between users within a community. The underlying data model impacts the sharing of these contents within the community platform and out of the platform: inputs, queries, exports, imports of information can be envisioned differently depending on this model. The model can be either platform dependent or open. Most social networking websites use their own data models, specifically designed for their architecture. Moreover, the data model is rarely publicly available. Platform-dependent data formats make it nearly impossible to import/export contents, profiles and social relations [START_REF] Razmerita | Towards a New Generation of Social Networks: Merging Social Web with Semantic Web[END_REF]. It leads to the well-known isolation of social networks.

Platform independent data models are public. Since community platforms run on the Internet and in a Web environment, norms or standards from these fields are the best candidates to share models. SIOC [START_REF] Breslin | To-wards Semantically-Interlinked Online Communities[END_REF][START_REF] Bojars | Weaving SIOC into the Web of Linked Data[END_REF] has been proposed for the representation of social data. It is founded on the Semantic Web technologies. The Semantic Web approach [START_REF] Berners-Lee | The Semantic Web[END_REF] aims at representing data in terms of RDF 1 triples: (term relation value) or (term1 relation term2). It is a userand machine-readable model. Each item of a triplet can be described anywhere on the Internet (URI, Uniform Resource Identifier). This builds the so-called linked data. Sesame [START_REF] Broekstra | Sesame: A Generic Architecture for Storing and Querying RDF and RDF Schema[END_REF] and Jena are Java frameworks used to store RDF triples. Reasoning processes can be launched to infer facts, especially in conjunction with formal description of domains (ontologies) which are also written with RDF (more specifically using RDF-based languages: OWL and RDFS). SIOC is written in the RDF/OWL language. Its use provides models and techniques for a platform independent data model.

1 http://www.w3.org/RDF/

User Profile

Some platforms [START_REF] Gallacher | Linking between personal smart spaces[END_REF][START_REF] Ganti | Analysis of data from a taxi cab participatory sensor network[END_REF][START_REF] Guo | GroupMe : supporting group formation with mobile sensing and social graph mining[END_REF] propose to enrich dynamically the user profile with context information: physiological parameters, GPS coordinates, nearby devices, etc. The management of several profiles is a complex task for end-users. Some works have proposed to federate different profiles [START_REF] Mitchell-Wong | Opensocial: From social networks to social ecosystem[END_REF]. However, all characteristics cannot be federated and, for average users, keeping profiles safe and up to date quickly becomes an issue. This is crucial because user profiles contain personal information. A complex management of profiles raises privacy issues: users may not adequately control data sharing.

A unique profile used on several community platforms eases its management and allows the user to better control the access rights to personal data. The profile can be stored either on a remote system or on the user's side. Several proposals can be found in the literature [START_REF] Seong | PrPl: A Decentralized Social Networking Infrastructure[END_REF][START_REF] Koch | Community Support and Identity Management[END_REF][START_REF] Grzonkowski | Sharing information across community portals with FOAF-Realm[END_REF]. The most advanced model for profile description is FOAF. It is described as an ontology, also written in the RDF/OWL language.

Services in VCs

A virtual community offers services to its participants to communicate i.e. create, modify, read, share information. It can take the form of forum, blog, chat, private messaging, walls... Services are key components of communities as they can strongly influence participation and adoption. Roles are used to define different rights of users: a forum can have a moderator, members, experts, etc. Other types of services can be found such as services related to the location, to information retrieval, to recommendation, etc.

The services offered on a platform are determined by the developers or the administrators. Also services are by definition not available out of the platform and they are not exportable: they are made for a given custom architecture and data model. Only some VC platforms allow users to create customized communities, but they require programming skills (see 2.4).

When the number of services increases, users should receive recommendations to select the most relevant ones regarding their preferences, social relations, and context [START_REF] Schubert | Collaboration platforms for virtual student communities[END_REF]. In [START_REF] Broens | Context-aware, ontology-based service discovery[END_REF][START_REF] Meyffret | Semantic, Social & Context-Aware Registry for Services[END_REF], ontologies for the descriptions of services, for the user's preferences and for context information are used to improve service discovery and selection. In [START_REF] Sinner | Semantic user profiles and their applications in a mobile environment[END_REF], a framework is used to match semantic user profiles with semantic descriptions of location-based services for recommendation.

Contents, User Profile and Services in Existing VCs Systems

Popular social networking websites such as Facebook use proprietary models. User profiles are stored on the proprietary platform which is based on a centralized architecture. Different approaches have been proposed 2 . Diaspora is a software environment for distributing the components of the social network at the users' sides. Evri has platform-dependent profiles and services, however it uses ontologies for the semantic annotation of contents. dgFOAF [START_REF] Schwagereit | Representing Distributed Groups with dgFOAF[END_REF] proposes users to be registered in a unique community and to launch services from different platforms. Elgg and Liferay allow the development of community platforms. Services can be added as plug-ins (or portlets), making community creation and upgrading customizable. However, they require programming skills.

The multi-agent approach has been also used for VCs [START_REF] Gunasekera | Adaptation support for agent based pervasive systems[END_REF][START_REF] Aguero | Developing pervasive systems as serviceoriented multi-agent systems[END_REF]. Koch [START_REF] Koch | Integrating community services-a common infrastructure proposal[END_REF] introduces agencies to separate user profile and community participation (i.e. use of community services). Guidelines are made available for people with programming skills wanting to develop a community platform, with no restriction on contents or services representation. [START_REF] Fahad | Smart places: multi-agent based virtual community management system[END_REF] is a community platform based on the multiagent framework Cartago3 . End-users can create and join communities, and they can delegate these tasks to autonomous agents. The communities are limited to four services: mailbox, forum, information dispatcher and personal box.

Properties of community platforms are summarized in table 1. None of these let end-users create and customize their VCs in selecting services and associating them to context information. Few platforms use open (semantic web) models.

the FOAF model and encompassing also user's context description, (ii) A community model that extends SIOC with communities-related properties, and (iii) A service description model that allows the use of onthe-shelf services.

Platforms

(

User Profile

As we have seen in section 2.2, a unique profile stored at user's side is desirable. We use and extend the FOAF ontology. The model (Fig. 1 In addition, avatars have the property hasContext, which is the capability of the device hosting the avatar to deliver context data (Fig. 1(b)). We define context Context data may relate to location but also to battery state, network connections, user's behavior (through an accelerometer), etc. The property hasContextData is the piece of information describing the state of the device hosting the avatar or a status of the actor (Fig. 2). It contains hasDescriptor (a string describing the information) and hasValue (context data value).

Content and Communities

Contents consist of pieces of information coded in RDF format with the properties hasAuthor, hasTopic, type and value which associates a value of a RDF class defined as a URI (Fig. 3(a)). The sharing of contents happens in the frame of communities. We define the Community ontology as an extension of the SIOC ontology (Fig. 3(b)). It is composed of hasOwner, hasTopic (contents used as subject of the community), hasMember (actors), hasService (see 3.3), hasRole (see 3.4) and hasContent (contents within the community). SIOC also provides the notion of topic with a dedicated property that usually refer to a semantic web resource.

Services

We define a service as a set of operations. For instance, a blackboard is a service, with the operations write, read and delete. Services in our framework are related to the management of contents. They are implemented to create and get contents from communities (hasContent property). As all communities are described using the data model defined above, any service can be used in communities. Services are described using the ontology given in Fig. 4. It contains the name of the service, its description and operations. Properties of an operation are described in Fig. 5(a). Notice that the hasRequiredContext property introduces the context of the avatars (see 3.1). This is used to introduce the context-aware property of operations. The property hasCommand relates to the exchanges of information: Get, Put, Delete or Post; it uses hasInputParameter and hasOutputParameter A parameter (Fig. 5(b)) has a description, a type (RDF class) and constraints applied on its value (RDF triple). The hasMultiProperty is used to indicate multivalued properties.

Goals and Roles

Goals are defined by actors. They are part of their personal data and consist of sets of operations that avatars will execute (Fig. 6(a)). The goal model uses part of the operation's model defined above to ease service discovery and selection. Roles define the rights to execute operations in the frame of a community. A role is composed of a set of actors and a set of operations (Fig. 6(b)). The notion of role also exists in the SIOC ontology with the class Role that can be referenced by a UserAccount.

FRAMEWORK IMPLEMENTATION

In the previous section, we have presented the data model of our framework. It allows users, communities and services modeling, and more specifically context-aware operations within communities. It is based on RDF principles and can be easily extended or adjusted. In this section, we present the implementation of this model and we show how it allows end-users to easily create their customized communities with different services and for dedicated contexts. The compliance with the RDF principles is kept with the framework implementation.

Main Implementation Choices

Our implementation combines the semantic web technologies with the multi-agent approach. Indeed, agents (users, avatars) as well as information and services are distributed in different concrete or virtual (i.e. computer supported) locations. Furthermore agents interact with others and share information in the frame of the communities to achieve user's goals.

We use the multi-agent platform Cartago to implement our system. In Cartago, agents interact with other agents but also with the environment through the artifact abstraction. We implement data store, avatars, communities and services with this abstraction. Through artifacts, agents can write/read data, get context values, create and participate to communities and execute operations. Cartago proposes also the concept of workspace to group artifacts and agents. We use this concept to group communities based on context values (for instance the location). We call Space of Communities (SoC) a set of communities hosted in a same workspace. Distributed communities can also be realized since communication in-between workspaces is possible.

As previously mentioned, we use RDF triples to model contents within communities, users' profiles, and services. This RDF implementation conforms to open linked data models. We use Sesame repositories [START_REF] Broekstra | Sesame: A Generic Architecture for Storing and Querying RDF and RDF Schema[END_REF] within artifacts to store and access these triples. Services are built on top of Web services. Details of the framework architecture are described in the next subsections and summarized in figure 7.

Implementation of Users Profiles

The user profiles are implemented as described in the data model (see 3.1) under the form of RDF triples. Each user's avatar is composed of an artifact (Profile artifact) and 3 agents (Profilor, Space Detector, Participator). The Profile artifact is used for accessing a Sesame repository which contains triples about context information, information topics and friends as defined in 3.1. The Profilor agent lets users manage their profiles. The Space Detector agent is a contextual detector of SoCs. The Participator agent is created when a SoC is detected. It allows the user to join or create communities: the agent filters the information received from the SoCs, depending on the user's topics of interest, context and goals and notifies the user. This process is privacy-aware since no personal data is transmitted to the SoC. Notice that as the user profile is unique, avatars of a single user interact together to merge data and keep up to date.

Implementation of Communities and their Services

As stated before, Cartago artifacts are used to implement communities. Once a community is created, a community artifact allows the access to a Sesame repository. It stores the data of this community: shared contents, roles, services (see 3.2). A dedicated SoC artifact manages the list of communities and the list of services the SoC holds. Services interfaces are also implemented as artifacts. They provide a set of methods for querying (using SPARQL), adding, deleting triples in the community repository. The availability of a given service in a community is decided by the community creator.

Smart City Scenario and Discussion

Our system can be used for the following scenarios. A city has implemented in the most populated quarters the ad hoc context-aware community platform and has settled several spaces of communities with different web services. A ride sharing service and a question/answer service are among these. Operations of the ride sharing service are: declare an offer, search for daily rides, and book for a ride. The question/answer service has two main operations: search a query and get answers; and read a query and give an answer. This second service is implemented at the train station.

As a committed citizen, Alice wants to develop daily ride sharing in her close area. She has learned the existence of the community platform and decides to register and to create her avatar (stored on her device). She creates a community with "ride sharing" as topic, the street name as the context for launching the services, and she selects operations from the ride sharing service. John is searching for "car ride" on the platform. Since he leaves close to Alice (same context), and thanks to the semantic analysis (same content), the platform proposes him to join Alice's community.

Bob and Colin have joined the platform. They often wait in the train station and have learnt that the train company has created a question/answer community. Bob loves winning points every day in answering questions asked by other participants. Colin loves asking questions about subjects he wants to learn about.

The scenarios illustrate the kind of implementations our data model can support for smart city applications. Users can manage their profiles on their mobile devices, their avatars can collect context data, and pieces of information can be gathered or delivered automatically following their goals. Spaces of Communities (with their artifacts, data stores and services) can be hosted by servers in specific places such as museums, cinemas, stores, campus, points of interest... Communities with ad hoc services can be created by users with no specific knowledge in computer science, thanks to the use of the semantic web technologies. Users can join communities and thus receive or deliver information.

Compared to other approaches, our approach proposes a user profile which is unique and which contains context values from the user's avatar. It can be used in all Spaces of Communities. The models for user profile, context and data are open and compliant with the Semantic Web technologies. Knowledge items are RDF triples contained into URIs. This Following such standards also allows to include other value added services ; for example reasoning on data can improve the user's experience with better recommendations. Finally, services can be added into Spaces of Communities and they can be easily included by end-users in the communities they create. No programming skill is required : the use of standards for the semantic description of services allows their inclusion with a high level of interaction with end users. Different types of communities can be created, using different services according to the communities needs. The semantic description of the avatar context also allows the use of such information by services ; they can adapt their behavior to the enduser context of usage.

CONCLUSION

The design of ad hoc context-aware communities typically addresses smart cities scenarios. We have proposed a model and an implementation which rely on the Semantic Web approach. Our approach can be useful in many different places and for many scenarios. Our data model can be easily extended to suit specific needs, and various services can be used by endusers. Cities, shops, malls, museum, cinemas should be interested by the approach. In the near future, our next steps will consist of building a more appropriate and illustrative user interface for end-user, and of de-veloping new services which will illustrate different kinds of communities that could be initiated by users in different places.

  (a)) has the following properties: foaf:interest (a topic about which the actor wants to share, obtain, create information), foaf:friend (another actor known by the user), hasAvatar (a delegate of the actor in the systemhosted by an electronic device of the user), hasGoal (goal to be achieved by the avatar, see 3.4). Properties foaf:friend and foaf:interest are taken from the FOAF ontology. The Actor class refers to both the foaf:Person and the UserAccount class in SIOC. The SIOC:Avatar class has no relationship with our Avatar class.

Figure 1 :

 1 Figure 1: Actor model (a), Avatar model (b)

Figure 2 :

 2 Figure 2: Context model

Figure 4 :

 4 Figure 4: Service model

Figure 6 :

 6 Figure 6: Goal model (a) and Role model (b)

Figure 3 :

 3 Figure 3: Content (a) and Community (b) models

Figure 7 :

 7 Figure 7: Framework architecture

A DATA MODEL FOR AD-HOC CONTEXT-AWARE VIRTUAL COMMUNITIESIn this section, we propose our data model to develop the framework for ad hoc context-aware communities. The model relies on RDF, and consists of three main elements: (i) A user profile based on 2 http://diasporaproject.org/, http://www.evri.com/, http://elgg.org/, http://liferay.com/ 3 http://cartago.sourceforge.net


Julien Subercaze

Christophe Gravier

Frédérique Laforest

Towards an expressive and scalable Twitter profile hash for users recommendation

Microblogging websites such as Twitter produce tremendous amounts of data each second. Identifying people to follow is a heavy task that cannot be completely done by users. Consequently, real time recommendation systems require very efficient algorithm to quickly process this massive amount of data, so as to recommend users having similar interests. In this paper we present a tractable algorithm to build user profiles out of their tweets. We propose a scalable and extensible way of building content-based users profiles in real time. Scalability refers to the relative complexity of algorithms involved in building the users profiles with respect to state of the art solutions. Extensibility considers avoiding to recompute the model for newcomers. Our model is a graph of terms co-occurency, driven by the fact that users sharing similar interests will share similar terms. We show how this model can be encoded as a binary footprint, hence boosting comparison of profiles. We provide an empirical study to measure how the distance between users in the hash space differs from distance between users using standard Information Retrieval techniques. This experiment is based on a Twitter dataset we crawled, and represents 25K users and 1 million tweets. Our approach is driven by real time analysis requirements and is thus oriented on a trade-off between expressivity and efficiency. Experimental results shows that our approach outperforms vector space model by three orders of magnitude, with a precision of 58%.

I. Introduction

Microblogging websites such as Twitter produce tremendous amount of data each second. For instance, Twitter was known to publish an average of 140 millions tweets per day as of march 2011 1 . In a single year, this number has increased up to 340 millions tweets 2 . In this context, we address the problem of building a "good" user profile model, in order to later exploit it in application such as recommending users to users. We expect a "good" user profile model that maximizes the following characteristics :

• Distance-preserving : The distance between users in the user profile space should preserve the proximity perceived by users with their peers as much as possible.

• Extensibility : The set of users and their interests evolves with time. However, it should be possible to update the model without having to rebuild it.

• Scalability : Algorithms to compute and compare user profiles should present a complexity as low as possible.

• Parallellization : These algorithms should also be easily parallelized, to take advantage of the advent of Map/Reduce [START_REF] Dean | Mapreduce: simplified data processing on large clusters[END_REF] and related paradigms.

• Explainability : Recommender systems should be able to produce human-understandable justifications of a recommendation.

In this paper we present a new approach to create and compare profiles of social network users. The solution exploits user-generated contents. In this model, we generate a binary footprint of the user profile that preserves the distance between users profiles in the binary space. Using a binary footprint provides both scalability and parallellization for computing and comparing hashed user profiles. Computing Hamming distance between two hashes is a very fast operation that is computed at the processor level3 on commodity machines. Moreover, computing newcomers profiles does not require to recompute others' profiles. The paper is organized as follows. Section II presents related works on building user profiles. Section III describes the core of our proposition, which is a complete processing of user-generated contents resulting in building and comparing user profiles. Details on how we deal with finding representative data structures in the user profile is provided in section III-A. We apply this approach on a Twitter dataset that we crawled, and compete with other content-based techniques, taken from the field of Information Retrieval. Experimental results validate the quality and the real-time property of our approach in section IV. Section V concludes and provides hints for further investigations.

II. On building social user profiles

Twitter analysis has been applied for folksonomies homogenisation [START_REF] Zangerle | Using tag recommendations to homogenize folksonomies in microblogging environments[END_REF], tag recommendation [START_REF] Song | Real-time automatic tag recommendation[END_REF], [START_REF] Wu | Automatic generation of personalized annotation tags for twitter users[END_REF] or as a corpus for opinion mining and sentiment analysis [START_REF] Pak | Twitter as a corpus for sentiment analysis and opinion mining[END_REF], [START_REF] Go | Twitter sentiment analysis[END_REF]. It is often used as a datasource for recommender systems. Among these systems a distinction is done between user recommendations and user-generated content recommendations. User-generated content recommendations concern tweets or external content sources suggestions to users whereas users recommender systems suggest users to follow as an output. Both rely on a digital representation of each user's features, which is usually called the user's profile. The field of recommender systems blossomed with the advent of Web-scale data analysis, especially with applications in Web search and social networks. While it has grown so as to be now considered as a new data science by itself, we tried to cover how building user's profile is performed in the myriad of existing works. Exhaustive literature reviews with better coverage can be found in [START_REF] Adomavicius | Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions[END_REF], [START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF], and [START_REF] Lops | Content-based Recommender Systems: State of the Art and Trends Recommender Systems Handbook[END_REF]. To our knowledge, user recommender systems fall in the following schools of thought: Social Network Analysis, Collaborative Filtering, Semantic-based models, and Content-based models. They can also combine these approach for building hybrid recommender systems. Our proposal (see Section III) falls into the content-based model category.

A. Social Graphs

A possible approach to build user profiles is to consider information from the social network of the user. The assumption is that the proximity of users in a social graph conveys the distance between users' interests, hence the user recommendation scheme. The proximity between users mainly relies on concepts such as graph density and centrality in order to identify key users in the social graph. In these works, the problem is not taken as ranking all possible friends to a given user. Instead, it most frequently aims at finding clusters of users (sometimes referred as communities) in the social graph. Recommended users are then picked within the user's cluster. For instance, in [?], the authors introduced a users segmentations method using the Gaussian Mixture Model (GMM). In [START_REF] Java | Why we twitter: understanding microblogging usage and communities[END_REF], the authors look for hubs and authorities in the network and then identify possible overlapping and dense communities in the network.

The major issues with Social Network were stressed by Social Network Analysis studies [START_REF] Wilson | User interactions in social networks and their implications[END_REF]. They demonstrate that content and user interactivity prevail over the social graph of the user. Moreover, note that most of the algorithms applied to social graph are NP-hard problems, and even applying heuristics or approximations are at best in polynomial time.

B. Collaborative Filtering

Collaborative Filtering is a very popular research area for recommender systems. It builds recommendations based on past item-user interactions, previous ratings of items by users. It is primarily used in item recommender systems [START_REF] Schafer | The adaptive web[END_REF], as competitions are organized around large publicly available datasets, like the Netflix dataset [START_REF] Bennett | The netflix prize[END_REF]. They can also be used for user to user and item to item recommender systems. State of the art implementations rely on Matrix Factorization methods [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF].

Collaborative filtering methods are known to provide good results given enough data. They suffer from the infamous sparse data and cold start problems. Computation is also at stake when the matrix is in a order of magnitude of billions of lines and columns. However, given both users and items are projected in a feature space, they can provide some justifications for the recommendation they made, for instance by illustrating the recommendation with close users-items interactions in the feature space [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF].

C. Semantic-based models

Semantic-based models exploit external databases in order to enrich user profiles, especially linked data. In [START_REF] Mika | Flink: Semantic web technology for the extraction and analysis of social networks[END_REF], the authors presents Flink, a system that builds user profiles out of users web pages, emails, and even FOAF profiles. FOAF profiles is a cornerstone for these approaches, since it is the de facto standard for modeling user profile in the Semantic Web. This category of user profiles usually complement Collaborative Filtering, as they address the cold start. Nonetheless, they do not scale well, because reasoning over logic fragments involved in the Semantic Web is, even for minimalist fragments like [START_REF] Muñoz | Minimal deductive systems for rdf[END_REF] in polynomial time, and at worst NEXPTIME [START_REF] Horst | Completeness, decidability and complexity of entailment for rdf schema and a semantic extension involving the owl vocabulary[END_REF]. Regarding the user recommendation process that follows user profile construction, [START_REF] Stan | Semantic user interaction profiles for better people recommendation[END_REF] proposed the use of semantic technologies for better people recommendation in a system called Social Adviser. The authors introduced linked data (DBPedia, a semantized version of Wikipedia) in the content extraction process. They have also defined specific scores to measure expertise). Even if no performance analysis is provided, [START_REF] Hartig | Executing sparql queries over the web of linked data[END_REF] showed that executing SPARQL queries over the Web of data takes at least 20 seconds even with all data locally retrieved in advance, which discards de facto such an approach for real-time purpose.

D. Content-based models

Content-based models aim at modeling users with predefined features. For instance, users can present geolocation, gender, age. . . while items could have features such as metadata, topics, hashtags, etc. There are many possible features and ways to combine them, thus leading to as many different models. For instance, [START_REF] Au Yeung | A study of user profile generation from folksonomies[END_REF] builds user profiles out of folksonomies. From the user personomy, a bipartite graph is built and greedy algorithm looks for clusters of tags, and most frequent tags in the cluster serve as a signature of this cluster.

A large spectrum of works tries to leverage the textual information that were produced or rated by the user. Our proposal that follows in Section III falls in this category. Early popular approaches rely on Vector Space Models (VSM) [START_REF] Salton | A vector space model for automatic indexing[END_REF]. VSM uses frequency measures in text corpus in order to leverage semantic information.

Frequencies encompass [START_REF] Turney | From frequency to meaning: vector space models of semantics[END_REF] :

• frequencies of terms in documents, for modeling user interests based on their choice of words.

• frequencies of terms in the context of a given term for word sense disambiguation.

• frequencies of word pairs with other word pairs, in order to model latent word pairs semantic relatedness.

Distance-Preserving Extensibility Scalability Parallelizable Explanations

Social Graphs

- + -- - + Collaborative Filtering + - + ++ + Semantic-based + - -- - + Content-based + - -- ++ - Hybrid ++ -- -- + --
TABLE I: Pro/cons of differents schools of trends for building user profiles as an input to recommender systems.

Most of these techniques use bags of words to characterize users or documents [START_REF] Phelan | Using twitter to recommend real-time topical news[END_REF], [START_REF] Hannon | Recommending twitter users to follow using content and collaborative filtering approaches[END_REF]. As the bag of words approach has shown its limitations, machine learning techniques have been developed to go beyond this representation. The most popular are continuous Conditional Random Fields (CRF) [START_REF] Lafferty | Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data[END_REF] and Latent Dirichlet Allocation algorithm [START_REF] Blei | Latent dirichlet allocation[END_REF] (LDA). Both techniques have been used to represent documents [START_REF] Wallach | Topic modeling: beyond bag-of-words[END_REF], [START_REF] Peng | Information extraction from research papers using conditional random fields[END_REF] and LDA has also been used for topic modeling in social network [START_REF] Pennacchiotti | Investigating topic models for social media user recommendation[END_REF]. The main drawback of these machine learning techniques is the learning part, which is prohibitively extensive for real-time processing.

Wallach [START_REF] Wallach | Topic modeling: beyond bag-of-words[END_REF] provides mean execution time for LDA. Results show that each iteration (around 200 are required) takes between 2 and 15 seconds. Although presenting computational issue, these approaches extract knowledge automatically, thus avoiding the hurdle to create ad hoc ontologies like in semantic-based approaches.

E. Hybrid methods

Several works tried to combine usually the aforementioned approaches. For instance, [?] combines Social graph with Collaborative Filtering. They propose Referral Web, a Web-scale system for searching social networks for users and items at both coarse and fine grain. In [START_REF] Debnath | Feature weighting in content based recommendation system using social network analysis[END_REF], the authors propose a combination of collaborative filtering and content-based methods for item recommendation. Another combinaison is Content-based mixed with Collaborative Filtering as proposed by [START_REF] Melville | Content-boosted collaborative filtering for improved recommendations[END_REF] for improved recommendations. In [START_REF] Hannon | Recommending twitter users to follow using content and collaborative filtering approaches[END_REF], twitter users are recommended some followers using content and Collaborative Filtering approaches. Hybrid systems are gaining momentum since they have proven to beat single approach baseline in large and popular dataset. In lessons learnt from the Netflix prize in [START_REF] Bell | Lessons from the netflix prize challenge[END_REF], the authors stress the importance of using a variety of models that complement the shortcomings of each others. This is however beyond the scope of this paper. We focus on a proposal falling into the Contentbased category, and expect that improving one of these categories would improve the overall performance of hybrid recommender systems. We provide a synoptic view of the different schools of trends on building user profile in Tab I, in the light of the criteria presented in Section I that we want to maximise when building a user profile.

As a conclusion, the real time processing of textual data cannot be handled efficiently with the use of external data sources or with machine learning techniques.

In this paper we developed a document centric approach, with the use of statistics and graph techniques. Given shortcoming stressed in this section and gathered in Table I, the aim is to keep the advantages of Content-based approaches but provide them extensibility and scalability using heuristics and hash functions. This approach is described in the next section.

III. Binary user profiles

Our approach is inspired by the paper of Matsuo & Ishizuka [START_REF] Matsuo | Keyword extraction from a single document using word co-occurrence statistical information[END_REF] on keyword extraction. In this article the authors present a method to extract keywords from a single document using statistical information. In a first step their algorithm computes the co-occurency matrix of the terms in each sentence of the document. Then they apply the following procedure "Co-occurrences of a term and frequent terms are counted. If a term appears selectively with a particular subset of frequent terms, the term is likely to have an important meaning. The degree of bias of the co-occurrence distribution is given by the χ 2 -measure."

We adapt the approach of Matsuo & Ishizuka for user profile extraction on twitter. Documents are built from users' tweets contents. The χ 2 -measure is later used in their algorithm to extract relevant keywords or keyphrases, the other words of interest being discarded. In our approach we aim at keeping all relevant words in the users' profiles, with corresponding weights.

The main steps for user recommendation using our HashGraph approach are the following:

1) Grab text from user tweets so as to build a document representing the user 2) Preprocess the document 3) Build the graph of terms 4) Compute the hash of the profile 5) Identify the top-k closest users and recommend them Figure 1 (inspired by [START_REF] Zesch | Approximate matching for evaluating keyphrase extraction[END_REF] to compare keyword extraction processes) summarizes this process. This process must be computable in a real time fashion, so as to react "instantaneously" to the evolution of users tweets topics. Some of these steps do not deserve much attention. In the following we focus on two main actions in these steps. The first action is to transform a document containing a sequence of short text messages into a graph of terms. We present the method for this transformation in section III-A. Since we focus on a real time algorithm, we discuss the complexity of the algorithms used. The second action concerns hashing user profiles and computing a distance between hashed profiles. It is the object of section III-B.

We define an undirected weighted graph of terms G =< V, E > where V is the set of vertices (i.e. the terms) and E is the set of edges. E is an application from V to V . To each e ∈ E, a weight w is associated :w ∈ ℜ, where w is the proximity between the two terms.

A. User profile as graphs of terms

We process the tweets using standard text analysis steps. Instead of sentences split, our algorithm consider a tweet as a sentence, i.e. all the words in a tweet are cooccurring, even if they belong to two different sentences in the same tweet. The idea being to consider a tweet as a unity in terms of performative speech act. The terms are then stemmed using a standard Porter-stemming algorithm. From the set of terms, we restrict the set of candidate terms for building the graphs to the lemmatized tokens and extracted n-grams minus the stopwords. Part of speech tagging is used to extract only nouns, verbs and adjectives from the tweets. Afterwards we build the cooccurrence matrix of the terms based on a tweet (and not a sentence) split. Table II presents an example of a cooccurrence matrix.

Once the co-occurrence matrix is built, we transform it into a graph representation. Several approaches are possible. The naive approach would consider the co-occurrence matrix as an adjacency matrix of the graph. We have decided to consider rows of the matrix as an occurence probability distribution and to compare distributions of terms using statistical divergence measure.

TABLE II: Co-Occurrence matrix example

If we normalize the values of each row in the matrix so that the sum is equal to one and assuming that terms are independently occurring, we can consider the rows of the co-occurrence matrix to be a distribution probability. This means that for row of term a, each cell represents the probability that terms a co-occur with an other one. Table III presents the normalized values for the first row.

TABLE III: Co-occurence frequency and probability for the term a

For instance probability of co-occurrence of a and c is 0.4. To determine wether two terms belong to a same topic, it is possible to evaluate the distance of their co-occurrence probability distribution. Several statistical measures provide either divergence or metrics, we used the square root of the Jensen-Shannon divergence.

Very different terms have a low Jensen-Shannon divergence. They are not of interest in our approach, thus we set a threshold to select the interesting value. A commonly [START_REF] Matsuo | Keyword extraction from a single document using word co-occurrence statistical information[END_REF]. We ran several tests on our dataset and agreed with this value. We then build the graph of the terms using the selected values. The results for the co-occurrence matrix of our example are depicted in figure 2.

Fig. 2: Graph of terms example using table II co-occurrence matrix

Computing the divergence between two discrete probability distributions of N events requires N ×(N -1) 2 operations for comparison between rows times N -1 comparisons between each p i and q i . This complexity seems prohibitive but in fact co-occurrence matrices are very sparse; consequently the number of operations is drastically reduced. Analysis from the dataset are presented in Table IV. In the average only 7.5% of the values are defined in the matrix. This seems logical since few terms co-occur with other terms. We observe that users with few tweets (≤ 25) have more dense matrix than users that have much more tweeted. This means that when the matrices are dense, their size is very small, thus the total computation time remains low. We also noticed that users that tweet very much (≥ 400) and that have abnormal small and dense matrices are users that generate automatically their content such as services providing regularly news from their website using a few templates to generate their tweets. For example a web dictionary that would tweet "'The word FOO has been defined, check out http://mydict/FOO"' each time a new word is defined, it would be affected a small and dense matrix. Consequently one could use the deviation to the average of the co-occurrence matrix in order to detect spam and automatic generated content.

Optimization: To speed-up the graph computation, it is possible to take advantage of the fact that the square root of the JS divergence is a metric. Considering geometrically the relations between three points a, b, c where the distance between a and b and between b and c are known, it is possible to obtain an upper bound for the distance between a and c. Since the square root of Jensen-Shannon is a metric, it verifies the triangle inequality i.e. |a, c| ≤ |a, b| + |b, c|. Considering the fact that we discard distances inferior to a given threshold, we can use the upper bound from the triangle inequality to know without You may want to follow : @user1 Tweets Follow ! @user2 Tweets Follow ! @userk Tweets Follow ! ....

WI attendee

Querying using in-house API

Step 1

Step 2 Fig. 1: Successive steps of the algorithm. We propose with the paper an online demonstration to WI 2013 attendees. calculating if the distance will be sufficient. If the upper bound is smaller than the threshold, then calculating the distance would be superfluous. In the worst case, if all the distances are over the threshold then the gain is null. In the best case, the two third of the distances helped to avoid the computation of the last third. Thus the maximum reduction is of N/3 operations. In practice, observed a gain around 8%, which is not to be neglected when dealing with large amount of data.

B. Hashing user profiles and distance between profiles

Using the technique presented before, each user can have his/her profile modeled as an undirected weighted graph, whose vertices are terms extracted from the user's tweets. We then require to compute a compact footprint of this graph, that can be used for both storage and comparison. We have investigated different options to encode a graph as a bit array, so that the Hamming distance could be used as a similarity metric between user profiles, and can also be highly prone to be inserted in a Map/Reduce implementation [START_REF] Dean | Mapreduce: simplified data processing on large clusters[END_REF].

We found a representative hash function of our user profile modeled as a graph of terms. An important review and some approaches on hashing graphs can be found in [START_REF] Papadimitriou | Web graph similarity for anomaly detection[END_REF]. [START_REF] Charikar | Greedy approximation algorithms for finding dense components in a graph[END_REF] proposed SimHash, a hash function for generating a footprint out of a graph. SimHash can be applied to any kind of resource (document, images . . . ), and in our case a graph.

In SimHash, the resource, usually a document, is splitted into token, possibly weighted. Each token is then represented as its hash value, as the result of a traditional cryptographic function applied to the token, which is originally a string. Then, a vector V, of length of the desired hash size, is initialized to 0. For each hash value for the set of tokens, the i th element of V is decreased by the corresponding token's weight if the i th bit of the hash value is 0. Otherwise, the i th element of V is increased by the corresponding token's weight. SimHash works well even for small fingerprints [START_REF] Charikar | Greedy approximation algorithms for finding dense components in a graph[END_REF], and was historically applied to the detection of near-duplicates of web crawl graphs.

We use SimHash to compute binary user profiles by hashing graph of terms with the following settings:

• As SimHash features : the set of edges and vertices of the graph of terms.

• As Simhash edges weights : the normalized Jensen-Shannon divergence values, which is the edge's weight.

Nodes and edges must be manipulated as a bit array in SimHash. The hash values, depending on the hash function used are very compact. For example, with the MD5 algorithm, user profiles are 128 bits long, thus allowing to store 64 millions profiles in 1GB. Using MD5, it allows us to manage 820 billions profiles with a collision probability around 10 -15 . We tested several hash functions, as presented in our evaluation in the next section.

Finding users to recommend is thus solved as getting the top-k closest hashed profiles using a Hamming distance, which has the property to be rapidly computed and easily parallelizable.

IV. Experimental results

A. Building dataset

Twitter users share messages called tweets that are limited to 140 characters. Using the public API of Twitter it is possible to retrieve tweets of any user that has not set its profile private (which is in practice very rare). A users's sequence of tweets is commonly called the user's timeline. To create a user's profile, one could choose either to retrieve all the tweets from the timeline or to select a subset from this timeline. A common intuition is that all the tweets, especially the very old ones may not be of great interest, then selecting a subset would be appropriate. To ensure our choice, and in order to determine the most interesting subset, we conducted some tests on our dataset. In case of analyzing a subset, we then have to determine how to limit this subset : should it be time limited or bounded by a number of tweets.

We first crawled up to 1K tweets for 5K users. We then analyzed how many tweets users actually wrote, and their distribution among time. Distribution over time is biased by numbers of accounts that produced a few tweets at account creation and later remain unused. However the distribution over time is not a very precise indicator. There is a very broad range of usage patterns. One may tweet regularly whereas one other may tweet once in a while. Therefore it is very difficult to setup a relevant time window.

The average tweets number per user is surprisingly low on the sample, however the standard deviation being higher than the mean is an indicator of high volatility of the measure.

The volatility of the results shows that once again it is hard to decide wether we should limit the subset on a temporal or on a numerical basis. Since a decision had to be made, our choice went to a numerical basis, for the simplicity and stability of data harvest. From the cumulative results, we were able to select the number of tweets per user to extract, in order to cover the largest set of users. Requests to the Twitter API are limited and timecostly. Since the gain between 600 and 800 is less than 1%, we decided to set the limit at 600 tweets per user, which seemed to us to be an acceptable trade-off.

We then gathered about 1 million tweets for around 25K users. The tweets are stored on a three machines Cassandra-cluster 4 . Due to the current Twitter's terms of services we are unfortunately not able to publicly provide this dataset.

B. Runtime and Quality

We compared our approach against standard Vector Space Model approach. For this purpose, we implemented our solution in Java without any particular optimisation. As a baseline we used the Lucene5 based TF/IDF vectors with the cosine similarity.

Although containing only 25K Twitter users, our dataset contain more than one million terms in the Lucene index, therefore the curse of dimension would have disastrous consequence on cosine similarity computation with such high dimensional vectors. Therefore, we precomputed TF/IDF vectors for various number of frequent terms, we also precomputed hashes using our approach with three cryptographic hash methods : MD5, SHA-256 and SHA-512. Precomputation time are depicted in figure 4. The difference of precomputation time for 25K users between TF/IDF and our approach HashGraph (20 seconds vs 110 seconds) could be overcome by implementation optimisation. One should not forget that we compare an optimized, in-production solution (Lucene) with a research prototype. This difference should not obscure that the average time required to precompute a binary user profile is only 5 milliseconds.

The running times for the four methods are shown in figure 3. The x axis shows the number of distance comparisons performed. The slight decrease at the beginning of the HashGraph curves is counter-intuitive and is to our opinion, to be attributed to the Java JIT compiler warm up phenomenon.

The HashGraph algorithm clearly outperforms the cosine similarity by three orders of magnitude. For instance, to compute 10 millions comparisons between profiles, the cosine similarity requires 150 seconds, while HashGraphM D5 requires only 253 milliseconds. As one would expect from simple complexity analysis, the running time grows linearly in the number of comparison for both methods.

To determine the quality of our approach against the baseline, we use the standard root-mean-square error (RMSE) on pairwise distances between users on the dataset. The distance between two users u i , u j in the baseline is the standard cosine similarity denoted cos(u i , u j ). Let v i , v j being two TF/IDF vectors representing users u i and u j . The similarity is defined as follows :

sim(u i , u j ) = v i × v j ||v i ||.||v j || (1)
The distance between two hashes is the normalized version of the standard hamming distance. (sim(u i , u j ) -hamming(u i , u j )) 2 (2)

The obtained RMSE, regardless of the number of frequent terms used in the cosine similarity distance is greater than 0.5. It also appears that the choice of hash function in simhash doesn't have much influence on the RMSE. Since MD5 provides the most compact representation with 128 bits, it will be our method of choice.

V. Conclusion

In this paper we have proposed a novel technique for designing very compact and scalable user profile based on the content generated by users. Our approach generates a graph of terms from the content, this graph is finally hashed using the HashGraph algorithm. The experimental results demonstrate the computational efficiency of the approach as well as its quality using Vector Space Model as a baseline.

However, Vector Space Model is no golden standard. The computed precision in this paper allows us to conclude that the results obtained with HashGraph are coherent with state of the art content based user profile. Therefore further research will aim to determine the perceived quality of recommandation through user evaluation, as well as enhancing the descriptive power of our approach by focusing on the design of a dedicated family of hash functions.

Demontration

If this paper is accepted, an interactive online demonstration will be available for WI2013 participants.

  .................... 01101111 0100100010111...................... 11000000 0000011110100...................... 00101011 (result of Simhash() applied to values of a,b,c)

Fig. 3 :

 3 Fig. 3: Running time of TF/IDF 1K vs HashGraphMD5.

Fig. 4 :

 4 Fig. 4: Precomputation time

Fig. 5 :

 5 Fig. 5: Precision (1-RMSE) of the different HashGraph functions against TD/IDF with various frequent terms

TABLE IV :

 IV Sparsity of the co-occurrence matrix -Based on the tweets dataset adopted threshold is 0.95 × log[START_REF] Zangerle | Using tag recommendations to homogenize folksonomies in microblogging environments[END_REF]

  Table V presents some basic analysis of the collected dataset.

	Average tweets per user	≈ 120
	Standard deviation of tweets per user	≈ 212
	Average interval between two tweets	≈ 6 days
	Standard deviation between two tweets	≈ 240 days

TABLE V :

 V Tweets distribution

  Technically the Twitter API provides 200 tweets per page. Splitted into interval of 200 tweets, we present the distribution in table VI.

	Limits	Percentage of users
	200	81,6%
	400	92,48%
	600	95,43%
	800	96,25%

TABLE VI :

 VI Percentage of users having less than a given number of tweets

Recent processors with the SSE4 instruction set allow the computation of hamming distance in two operations, XOR and POPCNT

http://cassandra.apache.org/

http://lucene.apache.org/