K Seleznyova

N A Sergeev

M Olszewski

P Stępień

S V Yagupov

M B Strugatsky

J Kliava

Fitting MAS NMR spectra in crystals with local disorder: Czjzek's vs. Maurer's model for 11 B and 71 Ga in polycrystalline gallium borate

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Extracting meaningful physical information from Nuclear Magnetic Resonance (NMR) spectra requires accurate computer simulations. Fitting to experimental NMR spectra usually allows estimating chemi cal shifts and quadrupole parameters [START_REF] Abragam | The Principles of Nuclear Magnetism[END_REF][START_REF] Freude | Quadrupolar Nuclei in Solid-State Nuclear Magnetic Resonance[END_REF]. However, the existence of disorder in the environment of magnetic (with nuclear spin I ≠ 0), in particular, quadrupolar I ( > )

2 nuclei manifests itself in broadening of the spectra. As a consequence, relative amplitudes and widths of spectra features can be satisfactorily fitted to only if local disorder is explicitly taken into account in the simulation code, allowing for statistical distributions of the NMR parameters, in particular of the quadrupole parameters related to components of the electric field gradient (EFG) tensor.

From the viewpoint of the magnetic resonance (both electronic and nuclear) spectroscopist, different degrees of local disorder give rise to more or less broad distributions of relevant spectroscopic parameters. Therefore, in most cases, the degree of disorder can be defined with respect to the ratio distribution width/mean value of the most representative parameters. Typically, low local disorder occurs in high quality crystals possessing low concentrations of structure defects [START_REF] Seleznyova | [END_REF] while high local disorder is observed in non crystalline, in particular glassy solids [4] as well as in crystals with highly flawed structure [5,6]. In what follows, we shall refer to low and high degree of disorder in accordance with the above mentioned criterion.

The issue of the distribution of the quadrupole parameters was first raised by Czjzek in the framework of a random packing model of amorphous materials [7,8]. As far as the quadrupole parameters are related to components of the EFG tensor, Czjzek et al. suggested a joint distribution density (JDD) of these parameters. Later, Le Caër and Brand [9] have provided a more general justification of the Czjzek's JDD; indeed, they have shown that it holds if all components of the EFG (in NMR) or of the quadrupole fine structure (in Electron Paramagnetic Resonance, EPR) tensor are subjected to normal (Gaussian) random distributions. The Czjzek's JDD has been exten sively used in both NMR and EPR studies of non crystalline materials [10 12] and also applied to simulate NMR spectra of some crystals with high degree of local disorder [5]. Yet, the major drawback of this JDD is to completely disregard symmetry and local structure persisting to a certain extent in crystals with low degree of disorder.

With the aim to describe a randomly distorted structure preserving, to a certain extent, local ordering, a more elaborated JDD of the quadrupole parameters has been suggested by Maurer [13] and Le Caër and Brand [9]. For brevity, we refer to this JDD as the Maurer's model, although Le Caër and Brand have provided a more detailed theoretical analysis thereof. Interestingly, a similar model has been put forward to describe the JDD of nanoparticle size and shape distribution [14].

The aim of the present work is to evaluate the applicability of the Czjzek's and Maurer's JDDs to NMR studies of only slightly disordered crystals. As an example, we have treated the NMR Magic Angle Spinning (MAS) spectra of 11 B and 71 Ga nuclei in GaBO 3 crystals. A special computer simulation code has been put forward in order to test different JDDs. Indeed, the available NMR simulation programs, e.g., GAMMA, SIMPSON, Winfit, STARS, Wsolids, QUASAR, QuadFit and DMFit, either do not at all take into account the distributions of the NMR parameters or, at best, allow calculations only with "standard" JDDs (e.g. Gauss in DMfit and QuadFit or Czjzek's in QuadFit) [ 15 23].

2. Comparative analysis of Czjzek's and Maurer's models

General characteristics

The EFG is described by a second rank tensor V with principal components

V V V , a n d x y z
subjected to the restriction that V V V + + = 0 x y z [START_REF] Abragam | The Principles of Nuclear Magnetism[END_REF]. In choosing the principal axes of V , the convention

V V V ⩾ ⩾ z y
x is usually applied. The "asymmetry parameter" η is defined as [START_REF] Abragam | The Principles of Nuclear Magnetism[END_REF].

η V V V = - , x y z (1)
so that η remains confined within the range η 0 ⩽ ⩽ 1. For η = 0, i.e. V V = x y , one deals with axial distortion, while for η = 1, i.e. V V V = 0 and = -

x y z , the absolute deviation from cubic symmetry is the same along two principal axes of V (the maximum rhombic distortion).

In a disordered solid, all components of V are expected to be statistically distributed. In order to satisfy the requirements of diagonal symmetry and tracelessness, as well as of rotational invariance of V , these components are calculated as linear combinations of five normally distributed random quantities U i , = 1, …, 5 i , with zero mean values and equal standard deviations σ 1 2 [7,9,24]. (Here the 1 2 factor has been introduced in order that the subsequent formulae could be expressed in their habitual form [7 9,13,24].) Thus, we get:

V U U U U U U U U U U U = 3 - + - - . 1 3 1 5 4 2 4 1 3 1 5 3 2 3 2 3 1 ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ (2)
Note that with this definition σ represents the standard deviation of V zz .

With these assumptions, the Czjzek's JDD takes the form [7,9]:

P V η V σ η η e ( , ) = (1 - ) z π z V σ η 1 2 4 5 1 9 2 - 1 + z 1 2 2 2 1 3 2 ⎛ ⎝ ⎜ ⎞ ⎠ ⎟ (3)
with marginal distributions, respectively, for V -∞ < < ∞ z and η 0 ⩽ ⩽ 1:

P V π σ V σ e V σ e P η η η η ( ) = 2 1 -1 - -1 ; ( ) = 3 1 - (1 + ) . m z z V σ z V σ m 3 2 2 2 - 4 3 2 2 - 1 9 2 1 3 2 5/2 z z 1 2 2 2 2 3 2 2 ⎡ ⎣ ⎢ ⎢ ⎛ ⎝ ⎜ ⎞ ⎠ ⎟ ⎛ ⎝ ⎜ ⎞ ⎠ ⎟ ⎤ ⎦ ⎥ ⎥ (4)
Alternatively, instead of V η and z the following parameters can be introduced [8]:

Δ V η = 1+ ² z 1 3 (5)
and

ψ π η V π η V = -arctan for > 0 - + arctan for < 0 . z z 1 6 1 3 1 6 1 3 ⎧ ⎨ ⎪ ⎩ ⎪ (6)
The advantage of the latter representation is that, as a difference of the former one it assures the continuity of the region of non zero probability density of distributed quadrupole parameters, cf. Figs. 1 and 3 in the Czjzek's paper [8]. One can see that Δ ⩾ 0 and ψ -⩽ ⩽ π π 6 6 , ψ = ± π 6 and ψ = 0 corresponding, respectively, to η = 0 (axial distor tion) and η = 1 (maximum rhombic distortion).

For the corresponding form of the Czjzek's JDD one gets [8]:

P Δ ψ Δ σ ψe ( , ) = cos 3 , π Δ σ 1 2 4 5 -1 2 2 2 (7)
and the marginal distributions, for Δ 0 ⩽ < ∞ and ψ -⩽ ⩽ π π 6 6 , respec tively, are:

P Δ π Δ σ e P ψ ψ ( ) = 2 ; ( )= c o s3 . m Δ σ m 1 3 4 5 - 3 2 1 2 2 2 (8)
In the Maurer's and Le Caër's et al. approach [9,13,24], the EFG tensor is represented as a sum of two tensors, V V + 0 where V is the random tensor defined above, and V 0 is a fixed traceless tensor describing a "perfect crystal" and characterized by parameters V η and z0 0 . In the coordinate frame where V 0 is diagonal,

V V η η = ( -1) 0 0 0 -( + 1) 0 0 0 1 z 0 0 1 2 0 1 2 0 ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ (9)
where

η V V V = - . x y z 0 0 0 0 (10)
The parameters Δ 0 and ψ 0 are introduced by means of Eqs. ( 5) and ( 6), respectively, replacing in the latter V V η η by and by z z 0 0 . (Note that in the Maurer's approach all components of the V tensor are assumed to be normally distributed with zero mean values and equal standard deviations [13]. However, such an assumption does not satisfy the above mentioned requirements for this tensor.)

We have put forward a simulation code implementing the above model. 1 This code i. generates the normal random quantities U i , = 1, …, 5 i , vide supra;

i. using Eqs. ( 2) and ( 9) computes and diagonalizes the V V + 0 tensor; ii. for each set of main values of the latter calculates Δ and ψ , respecting the above mentioned convention V V V ⩾ ⩾ z y

x and using Eqs. (1), ( 5) and ( 6

For Δ ≠ 0 0 and different values of ψ 0 , Δ tends to Δ 0 when σ tends to 0 and asymptotically reaches the trend given by Eq. ( 11) for σ Δ ≫ 0 . From Fig. 1 (right) one can see that ψ tends to ψ 0 when σ tends to 0 and tends to zero for σ Δ ≫ 0 . If ψ = 0 0 , ψ is always zero, including the case Δ = 0 0 corresponding to the Czjzek's JDD. With an increase of σ, both σ Δ and σ ψ increase, see Fig. 2. For Δ = 0 0 one can readily show that 1 Available on request from the authors.

2 σ σ σ = 45 - ≈ 1.3754 . Δ π 2 3 128 ( 12
)
For Δ ≠ 0 0 the relationship between σ Δ and σ becomes non linear, and the trend given by Eq. ( 12) is reached asymptotically for σ Δ ≫ 0 . In the latter case, as shown in Fig. 2 (right), σ ψ tends to its limiting value, corresponding to that of the Czjzek's JDD. Using the marginal distribution P ψ ( ) m , see Eq.( 8), one gets:

σ π lim = -8 ≈ 0.2279. σ ψ →∞ 1 6 2 (13)
Fig. 5 in the Maurer's paper [13] suggests that the correlation between Δ and ψ tends to decrease with increasing the departure from axial symmetry (viz., increasing η 0 ) and with lowering the degree of disorder (viz., increasing the Δ σ / 0 ratio). However, Fig. 3 below shows that this is only a part of a more general trend: indeed, ρ vanishes for any degree of disorder if ψ = 0 0 as well as in the limits of both low and high disorder. The absolute value of ρ attains a maximal value of ca. 0.21 for ψ = ± π 0 6 (i.e., for axial symmetry) at intermediate degree of disorder. The corresponding value of σ , σ max , is proportional to Δ 0 ; numerical calculations yield the following relationship between these parameters: 12) and ( 13), respectively. Δ 0 , σ and σ Δ are in arbitrary units.

Analytical Maurer's JDD

Besides, Maurer [13] has introduced an empirical analytical JDD by associating the marginal distribution of δ Δ σ = / , derived from a non central χ 2 distribution with five degrees of freedom, with a semi heuristic marginal distribution of ψ and allowing for a certain correla tion between both random variables.

Here we prefer using σ Δ instead of σ; indeed, such a choice seems more appropriate for a bivariate JDD P Δ ψ ( , ). After amending for a clerical error (in the third term inside the brackets of the exponent in Eq. ( 10) of the Maurer's paper [13], ρ should be replaced by ρ -2 ), this JDD becomes:

P Δ ψ Δ σ g x ψ e ( , ) ∝ ( )cos 3 ² Δ ρ Δ Δ σ ψ ψ σ ρ Δ Δ ψ ψ σ σ - 1 1- ( -) + ( -) -2 ( -)( -) Δ ψ Δ ψ 1 2 0 2 2 0 2 2 0 0 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ (15)
where g x x x e x ΔΔ σ ( ) = -1 + ( + 1) and = .

x

Δ -2 0 2 (16)
Of course, the use of an analytical JDD considerably simplifies the analysis of the experimental results; yet, the limits of its applicability should be carefully evaluated. With this aim in view, we have examined the relations between the "input" parameters Δ ψ ρ σ , , and Δ 0 0 occur ring in Eq. ( 15) and the corresponding "output" parameters and ρ = 0.1 [25], and for 71 Ga, δ = -6.9 , the "input" and "output" parameters are in good agreement; however, at higher disorder, e.g., already at Δ σ / ≈ 10 Δ 0 , these parameters considerably differ from each other. In Figs. 4 and the discrepancy between the "input" and "output" parameters becomes more pro nounced, but in any case we are outside the limits of applicability of the analytical Maurer's JDD. measured with a Bruker Avance 400 NMR spectrometer. The measure ments of 11 B spectra have been described in our previous paper [25]. The measurements of 71 Ga spectra have been carried out at the corresponding resonance frequency, 122.0564 MHz, with 4 mm rotors at the spinning rate of 14 kHz. The absorption signal was recorded using classical direct acquisition by single pulse free induction decay (FID) excitation with accumulation of 1000 pulse signals repeated with 2.4 μs radiofrequency pulse length. The NMR spectra were obtained by a Fourier transform of the FID signals.

Experimental results and discussion

The 11 B and 71 Ga NMR spectra were computer simulated using laboratory developed codes. Computer generated spectra have been acquired by integrating over distributed values of the spin Hamiltonian parameters and random orientations of crystallites.

Fig. 6 shows the experimental spectra for 11 B (left) [25] and 71 Ga (right) together with corresponding best fit computer generated spec tra for the Maurer's JDD. The simulation procedure for 71 Ga spectra has been similar to that for 11 B [25]; however, in order to obtain closer fittings, a normal distribution of δ iso with a standard deviation σ δ has also been assumed.

One can see that the Maurer's JDD provides satisfactory fits to the experimental MAS NMR spectra using fairly reasonable parameter values. The remaining discrepancy between the computer generated and experimental spectra for 71 Ga can be caused by an ill resolved superimposed resonance, probably arising from 71 Ga nuclei in more disordered environment and/or by a superposed contribution from non central NMR transitions.

The best fit simulation parameters for 71 Ga NMR spectra are consistent with sixfold coordinated gallium sites [26]. FeBO 3 crystals have calcite structure where each iron is surrounded by six oxygens forming a nearly perfect octahedron [START_REF] Diehl | Current Topics in Materials Science[END_REF]. As far as Fe x Ga 1-x BO 3 are isomorphous to FeBO 3 [START_REF] Yagupov | [END_REF], it can be reasonably assumed that Ga ions are also sixfold coordinated, and this is confirmed by the NMR results.

One might wonder if adequate fitting to the above experimental spectra can be achieved with the Czjzek's JDD. Obviously, in this case one should be able by varying the only adjustable parameter σ to simultaneously obtain in the simulations the mean parameter values Δ and ψ close, respectively, to Δ 0 and ψ 0 obtained with the Maurer's JDD and similar distribution widths of these parameters. Fig. 7 shows the three dimensional JDD for the Maurer's model, and Figs. 8 and9 show the corresponding marginal distributions of Δ and ψ . In the latter two figures we have also shown for the Czjzek's model the marginal distributions of Δ ψ and yielding the required mean values of these parameters for the Maurer's model. One can see that in order to obtain Δ values close to Δ 0 we need very high σ values, resp., unrealistically broad distributions of Δ, cf. Fig. 8 (a andc). On the other hand, taking the same distribution widths of Δ as those determined with the Maurer's JDD (σ Δ ), in the case of the Czjzek's JDD would result in very low mean Δ values, 0.08 and 0.04 MHz for 11 B and 71 Ga, respectively, cf. Fig. 8 (b andd).

Moreover, the Czjzek's JDD, as expected from Eq. ( 8), regardless of the σ value, always gives one and the same, extremely broad marginal distribution of ψ , see Fig. 9. Obviously, such a distribution is incompatible with only slightly perturbed axial site symmetry in the crystal. In contrast, the Maurer's JDD can produce quite narrow marginal distributions of ψ , describing weak random distortions from the perfect structure. Fig. 10 compares the experimental NMR spectra for 11 B and 71 Ga with computer generated spectra using the Czjzek's JDD with the same σ values as in Fig. 8. Obviously, in contrast to the Maurer's model, the Czjzek's model flagrantly fails to describe the experimental results. This result is not surprising; indeed, as we have seen above, the Czjzek's JDD, in principle, contains no information on the crystal structure. In contrast, the Maurer's JDD includes mean values Δ 0 , ψ 0 and separate distribution widths of both random variables Δ and ψ , as well the correlation coefficient ρ between them, thus preserving to a certain extent the information on intrinsic symmetry and ordering in crystals with low local disorder.

Conclusions

We have carried out comparative analysis of Czjzek's and Maurer's models of the JDD of the NMR quadrupole parameters. In the case of the Maurer's model, we have considered both the numerical and the analytical JDD of the random parameters Δ and ψ , and we have put forward a computer code allowing to obtain the dependences of the corresponding mean values Δ ψ , , standard deviations σ σ , Δ ψ and correlation coefficient ρ on the input value of σ, proportional to the degree of local disorder. The obtained relationships have allowed to determine the limits of applicability of the analytical Maurer's JDD. The Czjzek's JDD is relatively well adapted to the case of heavily disordered solids; meanwhile it contains only one adjustable para meter, describing the degree of local disorder and does not include the characteristics of local structure, partially preserved in the presence of a low degree of disorder. As a result, the marginal distribution of the parameter ψ , describing the local symmetry, becomes extremely broad, which is incompatible with the existence of short range ordering. In contrast, the Maurer's JDD has no these drawbacks, therefore it is expected to provide satisfactory fits to experimental NMR spectra in crystals with low local disorder. The above considerations have been corroborated by applying the Czjzek's and Maurer's models to computer simulations of MAS NMR spectra of 11 B and 71 Ga isotopes in gallium borate. With the former distribution no adequate description can be obtained while the latter has provided quite satisfactory fits.

The present study shows that the Czjzek's model should not be used in computer assisted analysis of NMR spectra of materials with low degree of local disorder. On the other hand, the Maurer's model, conceptually well adapted to this situation, can provide quite satisfac tory fits to the experimental NMR spectra.

  Figs. 1 3 illustrate variations of the latter parameters with σ for different Δ 0 and ψ . 0The graph of Δ vs. σ is shown in Fig.1(left). In the case of Δ = 0 0 , corresponding to the Czjzek's JDD (obviously, in this case ψ = 0 0 as well), the increase of Δ with the increase of σ is strictly linear; indeed, the marginal distribution P Δ ( ) m , see Eq. (8), yields:

Fig. 1 .

 1 Fig. 1. Dependences on σ of Δ (left) and ψ (right) for different Δ 0 and ψ 0 . The dashed line in the left part of the figure corresponds to Eq. (11). Δ 0 , σ and Δ are in arbitrary units.

Fig. 2 .

 2 Fig. 2. Dependences on σ of σ Δ (left) and σ ψ (right) for different Δ 0 and ψ 0 . The dashed lines in the left and right parts correspond to Eqs. (12) and (13), respectively. Δ 0 , σ and σ Δ are in

Fig. 3 .

 3 Fig. 3. Relationships between ρ and σ for different Δ 0 (in arbitrary units) and ψ 0 .

Fig. 4 .,

 4 Fig. 4. Relationships between Δ σ / Δ 0 and Δ σ / Δ 0 cal cal for ψ = 0.5 0

Fig. 5 .Fig. 6 .

 56 Fig. 5. Relationships between ψ 0 and ψ 0 cal for Δ = 3.0 0

Fig. 7 .

 7 Fig. 7. Maurer's JDD calculated with the parameters of the computer-generated spectrum shown in Fig. 6 for 71 Ga. The JDD for 11 B has a qualitatively similar shape.

5 0

 5 5 we show the results only for ψ = 0.5 0 , as far as in the low disorder case those for ψ = 0 0 and ψ = -0.are almost the same. For higher disorder, the results for ψ = ± 0.5 0 are still very close to each other. For ψ = 0 0

11 B

 11 and 71 Ga MAS NMR spectra of GaBO 3 , ground to powder were

Fig. 8 .Fig. 9 .

 89 Fig. 8. Marginal distributions of Δ for 11 B (a and b) and 71 Ga (c and d) obtained for the Maurer's (points, green online) and Czjzek's (squares, red online) models. The parameters of the Maurer's distribution correspond to the best-fit shown in Fig. 6. For the Czjzek's distribution, for 11 B σ = 1.42 (a) and σ = 0.04MHz (b), and for 71 Ga σ = 2.4 (c) and σ = 0.02MHz(d). (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)

Fig. 10 .

 10 Fig.10. Experimental (solid, blue online) for 11 B (left) and 71 Ga (right) and corresponding computer-generated NMR spectra for the Czjzek's JDD. The simulation parameters are: for 11 B, σ = 1.42 (dotted, red online) and σ = 0.04 MHz (dashed-dotted, green online), and for 71 Ga, σ = 2.4 (dotted, red online) and σ = 0.02 MHz (dashed-dotted, green online). (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)

Acknowledgements

This work was partially supported by the Russian Foundation for Basic Research and the Ministry of Education, Science and Youth of the Republic of Crimea, in the framework of scientific project Grant No. 15 42 01008 "р юг а".


Etienne Papegnies

Vincent Labatut

- Richard Dufour

- Georges Linarès

Detection of abusive messages in an on-line community

Keywords: Détection d'abus, Communautés en ligne, Modération, Traitement du langage naturel Abuse Detection, On-line Communities, Moderation, Natural Language Processing

La modération du contenu posté par les utilisateurs de communautés en ligne est majoritairement effectuée manuellement. De par la taille des données à traiter, les méthodes automatiques ont un intérêt certain pour réduire la charge de travail. Actuellement, l'industrie utilise des approches basiques à base de recherche de mots, comme par exemple le filtrage des messages contenant certains mots interdits. Nous nous intéressons dans cet article à une tâche de classification permettant de déterminer si un message est abusif ou non. Ceci est complexe, car les messages sont écrits dans un langage naturel non standardisé. Nous proposons ici une approche originale de modération automatique appliquée au français, s'appuyant à la fois sur des outils classiques et un nouveau descripteur fondé sur la modélisation du comportement utilisateur face à un message abusif. Les résultats obtenus lors de cette étude préliminaire montrent le potentiel de notre méthode, pour l'alerte automatique ou le support à la décision.

ABSTRACT. Moderating user content in online communities is mainly performed manually, and reducing the workload through automatic methods is of great interest. The industry mainly uses basic approaches such as bad words filtering. In this article, we consider the task of automatically determining whether a message is abusive or not. This task is complex, because messages are written in a non-standardized natural language. We propose an original automatic moderation method applied to French, which is based on both traditional tools and a newly proposed context-based feature relying on the modeling of user behavior when reacting to a message. The results obtained during this preliminary study show the potential of the proposed method, in a context of automatic processing or decision support.

Introduction

The Internet has revolutionized the way we communicate, by connecting communities of users and allowing them to exchange through various means, such as text messages, videos, on-line voice calls, social networks, etc. In the context of textual communications, exchanges can be made through instant messaging (chat for example), on messages boards through Internet forums, by commenting news articles, and other ways.

As more and more people get access to the Internet, the size of these on-line communities is rapidly increasing. Maybe because of this success, on-line exchange platforms are inevitably confronted to abusive behaviors from users. The term abusive is originally defined for real-life situations, but most types of abusive behavior can be transposed to on-line exchanges, provided they do not require any physical interaction : verbal aggression, coercion or control, destruction, disruption, harassment, intimidation, isolation or emission of threats. On-line abuse is a widespread issue, impacting various types of communities, that may take different forms : unsolicited messages (spam), provocative messages (such as trolls), racist messages, etc.

Such abuses are generally perceived as harmful to the quality of the service provided by on-line platforms : abused users tend to leave them and look for more comfortable communication means. More importantly, some forms of abuse are also simply considered as illegal in certain countries, e.g. homophobic or racists comments in France. In addition, in the past few years, specific laws have been passed in many countries to explicitly hold the infrastructure maintainers responsible for the content hosted on their platforms, even if such content is submitted under the cover of anonymity. For these reasons, the administrators of on-line platforms started defining behaving rules, often enforced by so-called moderators. However, due to the increasing size of on-line communities, performing this task manually becomes more and more difficult and expensive.

In this paper, we try to partially automate this task. We focus on on-line abuses appearing in text messaging communications, and consider the detection of abusive messages as a supervised classification problem. We evaluate the use of different classic features extracted from textual content (average word length, number of bad words, message length...), and also propose a new feature, based on the detection of significant changes in user behavior. Our assumption is that, when confronted to an abusive situation, a user does not behave like he usually does. To model the user's regular behavior, we build a word n-gram Markov chain using messages known to have been published in a non-abusive situation. To assess and compare the discriminant power of all these features, we use textual messages obtained from the official communication platform of the massively multiplayer on-line game (MMO) SpaceOrigin. We consider two communication means : in-game messages, which could be compared to e-mails, and chat messages, e.g. instant messages. This paper is organized as follows. In Section 2, we quickly review the main works related to abuse detection and automatic moderation. In Section 3, we describe the fea-tures we use to automatically detect abusive messages, including both classic features and the one we propose, based on the modeling of the user's behavior. In Section 4, we present our dataset, describe the experimental protocol we followed, and discuss the results we obtained. Finally, we summarize the main points of our work in Section 5, and show how it could be extended.

Related Work

Several solutions have been proposed to automatically detect abusive messages in on-line communities. While most of the works are evaluated on English datasets, a vast majority of the methods used are language-and community-independent, and can therefore be applied to any on-line text messaging community, which makes them relevant to us. In this review, we first focus on the preprocessing step, because the considered medium exhibits particular linguistic characteristics (ungrammaticality, community-specific linguistic traits, misspelling...), and requires a specific preparation in order not to impact negatively the performance of the methods applied subsequently (Subsection 2.1). Then, we distinguish two types of approaches, depending on the type of information they use to detect abusive messages : content-vs. contextbased methods. In the former case, the classification is performed based only on the textual content of the considered message, whereas in the latter, it takes advantage of additional data : structure of the conversation, user metadata, etc. (Subsection 2.2). The best performance is globally reached with approaches taking advantage of the information described in this review (preprocessing step, content messages, and contextual information).

Preprocessing step

Preprocessing is usually a simple but important step when dealing with messages posted on-line. The Internet medium introduces specific difficulties : disregard of syntax and grammar rules, out-of-vocabulary words, heavy use of abbreviations, typos, presence of URLs... The Denoising and Deobfuscation tasks both consist in mapping an unknown word back into a dictionary of known words. In the first case, a word is out of the vocabulary for unintentional reasons such as typos, e.g. "I uess so" for "I guess so". In the second case, it is due to a more deliberate attempt to conceal the word, e.g. "F8ck3r" for "fucker". Globally, mapping the word back into the dictionary increases the performance of probabilistic learning methods, since these methods need the cleanest possible text to achieve their maximum performance.

In [START_REF] Sood | Using Crowdsourcing to Improve Profanity Detection[END_REF], the Levenshtein distance (also called Edit Distance) is used in an attempt to match unknown words against words in a crowd-sourced list of manually annotated messages containing profanity. The Levenshtein distance [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertions and reversals[END_REF] measures the number of insertions, deletions and replacements needed to convert a string into another (e.g. The Levenshtein distance between "@ss" and "ass" is 1). Computing the Levenshtein distance between two words of length n and m is computationally expensive : the runtime is O(n • m), and for this specific task each word has to be matched against each word in the dictionary, which is huge. We base some of our features on the Levenshtein Distance.

Other works, such as [START_REF] Brill | An improved error model for noisy channel spelling correction[END_REF], proposed to improve on simple Levenshtein distance based denoising (for the purpose of spell checking) by considering the context of the string edition in a word (where the edited character is) and in a sentence (does the edit maps the word into a high n-gram probability ?). However, this approach is based on the assumption that out-of-vocabulary words are mainly due to unintentional spelling mistakes and is therefore not applicable to deobfuscation.

In [START_REF] Lee | Spam Deobfuscation using a Hidden Markov Model[END_REF], the authors use a Hidden Markov Model customized with dictionary and context awareness for the purpose of deobfuscating spam messages. Those types of messages often include deliberately misspelled words in an attempt to bypass filters. Their model showed impressive results with the ability to correct both unintentional misspellings as well as deliberate obfuscation using weird characters or digits and could even map segmented words back into complete words. (ie : "ree movee" -> remove). This process is nonetheless also computationally intensive and it requires curated data such as examples of word obfuscation in the given language, therefore we will not use it in this paper, but will come back to it in future works.

Preprocessing is an important step in an automated abuse detection framework, but it should be applied with caution. The goal of preprocessing is to increase the amount of relevant information in a message, but it can have the opposite effect. For example, the tendency of a user to misspell words can be viewed as an important feature to describe this user, but blind preprocessing would hide that. In order to prevent this, in this paper we use the preprocessing only when it is consistent with the considered feature, and we use the raw text otherwise.

Text messaging classification

In this section we review existing classification approaches that consider the content of the messages to detect abusive messages, and then the context of the exchanged messages.

Content-based approaches [START_REF] Spertus | Smokey : Automatic recognition of hostile messages[END_REF] was one of the first work to automate detection of hostility in messages. While hostility does not imply abuse, abuse often contains hostility. The paper defined a number of rules to identify certain characteristics of the messages, such as Imperative Statement, Profanity, Condescension, Insult, Politeness and Praise. A Decision Tree classifier was then used to categorize messages into Hostile and Non-hostile classes. The setup showed good results but was limited when dealing with sarcasm, noise or innuendo. This approach is interesting but highly tuned for the grammar rules, semantics and idioms of a specific language.

In [START_REF] Chen | Detecting offensive language in social media to protect adolescent online safety[END_REF], the authors note that the mere presence of an offensive word in a message is not a strong enough indication that the message itself is offensive, ie "You are stupid." is way more offensive than "This is stupid.". This is an important observation and the authors showed that the lack of context can be mitigated by looking at word n-grams instead of unigrams.

Another work by [START_REF] Dinakar | Modeling the detection of Textual Cyberbullying[END_REF] used features computed from tf -idf weights, a list of words reflecting negative sentiment and widely used sentences containing verbal abuse to detect cyberbullying in comments associated with Youtube videos. Their model showed good results for instances of verbal abuse and profanity, but was limited with regard to sarcasm and euphemism.

Finally, the work by [START_REF] Chavan | Machine learning approach for detection of cyber-aggressive comments by peers on social media network[END_REF] reviewed machine learning approaches for the classification of aggressive messages in On-line Social Networks, described a full pipeline for achieving classification of raw comments and introduced two new features : Pronoun Occurrence and Skip-Gram features. They allow for the detection of targeted phrases such as "He sucks" or "You can go die", and for the identification of long distance relationship between words, respectively.

Content-based text classification performs relatively well as a starting point. The computational cost to implement these approaches is usually reasonable. Nonetheless, these approaches have severe limitations. For instance, abuse can cross message boundaries, and therefore a message can be abusive only because of the presence of an earlier message. In other cases, messages can be abusive because they reference a shared history between two users. Therefore, studying the context of a message, its recipient, and its author might also be important.

Context-based approaches

To go beyond the limitations of content-based approaches, authors proposed to take into account the context of messages, usually in addition to the textual content itself. Some works explore the use of the content neighboring the targeted message. In [START_REF] Yin | Detection of harassment on Web 2.0[END_REF], authors used a supervised classifier working on n-gram features, sentence-level regular expression patterns and the features derived from the neighboring phrases of a given message to detect abuse on the Web. Their approach focused on detecting derivations in the context of a discussion around a given topic and their context features significantly improved the performance of their system. For this reason, we want to adopt a similar approach for our own method, but by focusing on derivations of users themselves from their usual patterns.

Other works have focused on modeling the users' behaviors by introducing higherlevel features than the textual context. A comprehensive study of antisocial behavior in on-line discussion communities has been proposed by [START_REF] Cheng | Antisocial behavior in online discussion communities[END_REF]. Their exploratory work reinforced the weight of classic features used to classify messages such as misspellings and length of words, and provided insight into the devolution of users over time in a community, regarding both the quality of their contributions and their reactions towards other members of the community. This analysis is a good step towards modeling abusive behavior. One of the essential results of the analysis is that instances of antisocial messages tend to generate a bigger response from the commu-nity compared to benign messages. The number of respondents to a given message is a feature we use in this work.

A selection of contextual features aiming at detecting abuse in on-line game communities has also been investigated in [START_REF] Balci | Automatic analysis and identification of verbal aggression and abusive behaviors for online social games[END_REF]. These features form a model of the users of the game by including information such as their gender, number of friends, investment in the platform, avatars, and general rankings. The goal was to help human moderators dealing with abuse reports, and the approach yielded sufficiently good results to achieve this goal. The work was however limited in applicability because of the specifics of that given community, and of the raw amount of data needed to perform similar experiments in other games.

When quantifying controversy in social media [START_REF] Garimella | Quantifying controversy in social media[END_REF], the structure of the community network is exploited to identify topics that are likely to trigger strong disagreements between users. The approach relies on a network whose nodes are Twitter users and links represent communications between them. It is interesting, however hardly applicable to our case, since we cannot infer the exact network structure from our dataset unless we restrict the network to private conversations between two users. As per the game's terms of use, the content of these conversations is only available to moderators when an abuse case is reported.

Features for abusive message detection

In this work, we propose to use a selection of features to characterize an abusive message, including one newly proposed by us. In this section, we describe according to their type : low-level morphological features (Subsection 3.1), higher level language features (Subsection 3.2), and user-related features (Subsection 3.3).

Morphological Features

Message length. This feature corresponds to the length of a message, expressed in number of characters, before any pre-processing such as normalization. The intuition is that abusive messages are usually either kept short (e.g. "Go die."), or extremely long, which is symptomatic of a massive copy/paste.

We also consider the length expressed in terms of words. In conjunction with the character count, it can match certain overly emphasized messages (e.g. : "Shuuuuuuuuuuuuuuuuuuuuuuut uuuuuuuuuuuuuuuuuuuup !").

Character classes. We split characters into 5 classes : Letters, Digits, Punctuation, Spaces and Others. We keep track of the number of characters in those classes and the ratio of those classes in the message. This is done before any preprocessing on the raw message.

We selected these features based on several observations we made on the abusive messages. First, some of them have an unusual number of charac-ters in the "Other" class, e.g. : "8==================D". Second, some use digits to obfuscate their meaning, in violation of the game rules. For instance, "01000111011011110010000001100100011010010110010100101110" and "476F206469652E" are obfuscated versions of the text "Go die." : the first one is coded in binary, and the second in hexadecimal.

Abusive users also commonly "yell" insults using capital letters, which is why we keep track of both the number of caps and the corresponding ratio of caps in the message.

Compression ratio. This feature is defined as the ratio of the length of the compressed message to that of the original message, both expressed in characters. It is based on the observation that certain users tend to repeat exactly and many times the same text in their abusive messages. We use the Lempel-Ziv-Welch (LZW) compression algorithm [START_REF] Batista | Texture classification using the Lempel-Ziv-Welch algorithm[END_REF], and the features therefore directly relates to the number of copy/pastes made in the same message.

Unique characters. By counting the number of distinct characters in the message, we can detect the use of binary or hexadecimal obfuscation, as well as the overuse of punctuation. For instance, for the message "01000111011011110010000001100100011010010110010100101110", this feature has only a value of 2. This value is also computed before any preprocessing.

Collapsed characters. This feature is processed after normalization, and more particularly after the removal of consecutive characters. When three or more identical consecutive characters are found in the message, they are collapsed down to two characters. For instance, "looooooool" would be collapsed to "lool". The feature is the difference between the length of the original message and that of the collapsed one. This preprocessing step has been widely used in the classification of Tweets, for instance in [START_REF] Roy | A lexicon based algorithm for noisy text normalization as pre processing for sentiment analysis[END_REF].

Language Features

Word length. This feature is a component of the Automated Readability Index (ARI) [START_REF] Senter | Automated readability index[END_REF]. It measures how proficient someone is at creating text documents. While abusive messages are sometimes surprisingly well written, this remains rare.

Unique words. We consider the number of unique words in the message. The intuition is that messages with more words are likely to be more constructive in terms of their content.

tf -idf Scores. Those features are the sums of the tf -idf scores of each individual word in the message. We use two distinct scores : the so-called non-abuse score is processed relatively to the non-abuse class, whereas the abuse score is processed over the abuse class.

If the considered word is unknown, in the sense it does not appear in the training set, we process an approximation of these scores. For this purpose, we first search for known words located within a given Levenshtein distance from the word of interest, and average their own scores.

Computing the full Levenshtein Distance between two words is computationally expensive. For this reason, solutions proposed in this paper never compute the full Levenshtein Distance between two words. Instead, a specialized tree-based index datastructure with a search function that yields all words in the tree within a given maximum edit distance is used. We use 2 as the maximum edit distance. This is considerably faster because branches of the tree are pruned as soon as we reach a state where the maximum edit distance is exceeded. It is still the most computationally intensive operation in our experiments.

Sentiment Scores. These features are numeric values derived from the number of words in the message that have a sentiment weight. It is based on the sentiment corpus presented in [START_REF] Chen | Building Sentiment Lexicons for All Major Languages[END_REF], which was automatically generated for the French language and we augmented it manually by selecting words from a large list of insults.

Bad Words. This feature corresponds to the number of words in the message that appear in a manually crafted list of bad words. The list of words was created from a list of insults in French and then augmented with common Internet shorthand and symbolism. (e.g : 'connard', 'fdp', 'stfu' but also '..|..', '8==D' etc) When we cannot match the considered word to any of the bad words in our list, we try to perform a fuzzy match using the Levenshtein distance. This is supposed to allow us picking up some obfuscated bad words.

We also perform the same tests using the collapsed version of the message (as described for the Collapsed characters feature).

User Behavior Features

Number of respondents. Given a fixed size window after a target message, this feature tracks how many distinct users replied to this message. This feature is relevant because it has been shown that abusive comments tend to trigger a higher number of responses from the community [START_REF] Cheng | Antisocial behavior in online discussion communities[END_REF].

Probability of n-gram emission. We investigate if the abusiveness of a user's message can be detected by considering the effect it has on the other users participating to the same conversation. To do this, we compare the writing behavior of these other users before and after the apparition of the targeted message. We model this behavior through a user-specific Markov chain, which we use to compute how likely some text is to have been generated by the considered user. We first sort the messages in chronological order. For each participant other than the user who wrote the targeted message, we build a word n-gram Markov chain using all but the last W n-grams in the messages posted before the target message.

The Markov chain is a convenient way to store the transition probabilities for all couples of n-grams in a participant's history. We compute two values : the average emission probabilities of the n-grams in the W -length window before and after the target message, as represented in Figure 1.

Let P i,i+1 be the emission probability of a transition between the i th and i + 1 th n-grams in the window of length W . Then we define the average emission probability S over the set of W n-grams as :

S = W -1 i=0 P i,i+1 W [1]
We note S B (u) and S A (u), respectively, the average probabilities processed before and after the targeted message, for the same user u. The final score S(u) for user u corresponds to their difference :

S(u) = S A (u) -S B (u) [2]
This score is processed for every respondent to a message in a window of fixed length after the message. We then compute our feature by averaging this score over all the responding users.

Experiments

In this section we will describe the data used in our experiments (Subsection 4.1), the experimental protocol we applied to the data (Subsection 4.2), and finally discuss the results obtained with our proposed system (Subsection 4.3).

Dataset

We have access to a database of user in-game interactions for the SpaceOrigin MMO. This user-generated content was manually verified, in the sense the game users had the ability to flag parts of the content as inappropriate (i.e. abusive). There are many types of reportable contents, but, in this paper, we focus on two of them : ingame-messages and chat-messages, collectively referred to as messages.

Ingame-messages are on-line messages with a clearly defined reach. They are the equivalent of e-mails and can be sent to specific users or groups of users. They can be edited a posteriori by moderators when an abuse case is reported. The reach of chat-messages is loosely defined because it is limited to users currently active in a chatroom. However, there is no way to determine which user has actually seen a specific chat-message based on the available data. Users are fed recent scroll history for a chatroom upon joining, but it is not possible to reliably determine who has joined when from the chat logs. Chat-messages cannot be edited by moderators afterwards.

The database contains 474, 599 in-game messages and 3, 554, 744 chat-messages. We extract 779 abusive messages (0.02%), which constitute what we call the Positive Class (Class 1) of messages. These messages were first flagged by the game users using a built-in reporting tool, and then confirmed as being abuse cases by the game community moderators. Of these 779 abusive messages, 14% are ingame-messages, and the rest are chat-messages. We then extract non-abuse messages from the database, in order to constitute the so-called Negative Class (Class 0). They are chosen at random from a pool of messages written by users which have never been flagged by a confirmed abuse report. For each message, we also gather context data : a window of messages occurring before and after each message.

We run the experiments with different versions of the corpus : in-game messages only (iM), chat-messages only (cM) and messages of both types combined (iM+cM). Since the non-abuse class of message is chosen automatically at random from the database, we also experiment with different number of messages in that class. We run experiments with balanced classes (noted B), where the number of "abuse" messages equals that of "non-abuse" ones ; and with unbalanced classes (noted U) where the number of "non-abuse" messages is twice that of "abuse" ones. Those numbers are listed in Table 1.

Experiment Abusive Messages

Experimental Setup

Our experiment is designed as a multi-stage classifier pipeline, as described in Figure 2 (each box corresponds to a stage). The first stage (Raw Messages) consists in building the corpus. Messages from both the Abuse and Non-abuse classes are extracted from the database as explained in Subsection 4.1. The corpus is then split into a Train set containing 70% of the messages, and a Test set containing the remaining 30%.

In the second stage (Bag of Words Features), messages are normalized, tokenized and converted into Bags of Words (BoW). In the third stage (Naive Bayes Classifier), the BoW representations of the Train messages are used to build a Naive Bayes classifier. This classifier is then used to generate predictions for the class of the Test messages. The output of this classifier is fetched as a feature to the SVM classifier, described below.

In the fourth stage (Feature Extraction), we extract the features described in Section 3 from the messages. As explained also in Section 3, some of these features are derived from the messages before any normalization or preprocessing, whereas some features require a specific preprocessing. We then use another classifier, a Support Vector Machine (SVM). We could directly feed the BoW to the SVM. However, given the size of the vocabulary in our experiments, this would lead to a dimensionality issue, with a number of features greatly exceeding the number of instances in the corpus. Therefore, we prefer to consider the decision from the Naive Bayes classifier (third stage) as an additional feature given to the SVM. All the features, including the Naive Bayes decision, are gathered into an array.

The fifth stage (SVM Classifier) is the final classification : the feature arrays from the Train set are fetched to an SVM classifier, and the resulting model is then used to generate class predictions for the Test set.

Results

We evaluate the performance of our proposed abusive message detection system in terms of the traditional Recall, Precision and F -Measure, defined below :

Recall = T P T P + F N [3] P recision = T P T P + F P [4] F measure = 2 • P recision • Recall P recision + Recall [5]
where T P , F P and F N are the numbers of True Positives (number of abusive messages correctly classified as abusive), False Positives (number of non-abusive messages incorrectly classified as abusive), and False Negatives (number of abusive messages incorrectly classified as non-abusive), respectively.

Given the relatively low number of abusive samples of the targeted corpus, the whole dataset was split into 10 parts and every result given in this section is the average value over a 10-fold cross validation. We use the notations defined in Table 1, i.e. : U for unbalanced classes, B for balanced ones, iM for ingame-messages only, cM for chat-messages only and iM+cM for all messages at once. Table 2 and 3 present the results obtained when using only our content-based features, with the Naive Bayes classifier and the SVM, respectively. Table 4 displays the results obtained with the SVM when considering both content and context-based features. We could not process all the possible cases because of the high computational cost of this approach.

The behavior observed in Tables 2 and3 We now focus on the effect of the message type (only on balanced classes). In the case of Naive Bayes, the Recall is better for ingame-messages, whereas the precision is better for chat-message. For the SVM, we observe that the Recall is about the same, whereas the Precision is better for chat-messages. So, the type of message does appear to affect the performance. When combining both types of messages (iM+cM), the resulting performance is similar to that of the chat-messages only so it seems like there is not downside to grouping the types. Finally, the disappointment comes from the performances obtained when incorporating our context-based features (Table 4). Indeed, no improvement in terms of performance has been observed. It would seem that the features linked to the context, in the way that we made it, do not incorporate information in addition to the content ones.

Data

Recall Precision F -Measure iM+cMU 0.701 0.663 0.681 Tableau 4 : Classification results using both content and context features.

Let us now compare both classifiers. When considering the Recall, the SVM is always at least as good, and generally better, as Naive Bayes. The difference is es- Previous experiments showed that, even if acceptable results could be obtained with our abusive message detection system (best F -measure of more than 70%), performance is still not good enough to be directly used as a fully automatic system that replaces human moderation. Nonetheless, we think that this system could be useful to help moderators to focus on messages considered has potentially abusive, instead of having to analyze all messages. In this context, Figure 3 presents the curve obtained (in terms of precision and recall) using our proposed combined content-context approach, by varying a threshold on the posterior probability of the SVM classifier on the abusive message class. For example, a threshold of 0.8 means that if the classifier associates a posterior probability greater than 0.8 to a message for the abusive class, then the abusive class is chosen (otherwise, the message is considered as a non-abusive one). This posterior probability is obtained using SKlearn's Platt Scalling implementation [START_REF] Platt | Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods[END_REF].

As expected, we can see that the posterior probability is an interesting information to take into consideration depending on the targeted application. Indeed, if the targeted application requires to be very precise in the decision to take (i.e. be sure that the message is abusive), such as a fully automatic system, then a higher threshold should be used, with a loss in terms of retrieved abusive messages (i.e. lower recall). On the contrary, if the targeted application wants to recover as many abusive messages as possible, such as a moderator helper, then a lower threshold should be used, which will have the effect of having a higher recall (more abusive messages are retrieved) associated to a lower precision (more non-abusive messages will be wrongly considered by the automatic system as abusive).

Conclusion

In this paper we developed a system to classify abusive messages from an on-line community. It is developed on top of a first-stage Naive Bayes classifier and relies on multiple types of features : morphological features, language features and context features, that have proven useful in previous research. We added several features that we derived directly from observations of our corpus, and developed a context feature that aims to capture abnormal reactions from users caused by an abusive message. This preliminary work shows that abusive messages, in their particular form, have characteristics that can be caught by an automatic system, our proposed system achieving a recall of 70% with a precision of 66% on our dataset, with a false positive rate 10%. While the performance of the system is not yet good enough to be deployed as an automated moderation tool, this can already help moderators to focus on messages being identified as abusive, with then a manual verification. However, because some features used in the system are specific to the community in which it is meant to operate, care must be taken when adapting the system to work on a different dataset.

We now plan to pursue our work in several ways. First, we will experiment with computationally more demanding preprocessing methods, and evaluate their contribution to the classifier performance. One such approach is the HMM-based preprocessor. [START_REF] Lee | Spam Deobfuscation using a Hidden Markov Model[END_REF] Second, we want to derive variants of our Markov chain-based feature, and assess which one is the most appropriate in our situation. More generally, we want to propose other context-based features, especially ones based on the network of user interactions.

Figure 1 :

 1 Figure 1 : A sequence of messages broken down into n-grams. Each square represents an n-gram : red for the targeted message from user1, blue for the surrounding messages written by user2.

Figure 2 :

 2 Figure 2 : The full experimental setup

Figure 3 :

 3 Figure 3 : Precision and Recall by varying a threshold on the posterior probability of the SVM classifier on the abusive message class.

  is quite similar. The results are clearly better for balanced classes than for unbalanced ones, be it for cM, iM or cM+iM, with both Naive Bayes and the SVM. It is particularly strong for the precision obtained So our first observation is that the performances are clearly better when we process a balanced dataset, even if this amounts to using less data. In the rest of our discussion, we consequently focus on the results obtained on balanced classes.

	Data	Recall Precision F -Measure
	iM+cMU	0.656	0.650	0.653
	iM+cMB	0.674	0.761	0.715
	iMU	0.585	0.433	0.498
	iMB	0.718	0.739	0.724
	cMU	0.590	0.737	0.656
	cMB	0.645	0.785	0.708
	Tableau 2 : Classification results with a Naive Bayes classifier using BoW features
	(Baseline).
	on iM. Data	Recall Precision F -Measure
	iM+cMU	0.696	0.662	0.679
	iM+cMB	0.731	0.765	0.748
	iMU	0.625	0.458	0.529
	iMB	0.697	0.718	0.707
	cMU	0.658	0.747	0.700
	cMB	0.705	0.793	0.747
	Tableau 3 : Classification results with a SVM classifier using content features only.


Mandimby N Ranaivo Rakotondravelona
email: mandimby.ranaivo@univ-reunion.fr

Fanilo Harivelo
email: fanilo.harivelo@univ-reunion.fr

Pascal Anelli
email: pascal.anelli@univ-reunion.fr

Hierarchical area-based address autoconfiguration protocol for self-organized networks

Keywords: self-organized, ad-hoc, wireless, distributed protocol, address autoconfiguration

Node autoconfiguration is one of the main issues in selforganized networks. One class of approaches relies on hierarchical organization of nodes. This kind of structuration aims to deal with scalability issues, especially for wireless networks. But building and maintaining a hierarchy is generally expensive for these resource-limited networks. We propose a low-cost distributed, hierarchical, location-based address autoconfiguration protocol. Each node infers its address from those of its one-hop neighbors and from its relative position to them. In this way we obtain a globally-consistent organization resulting from local interactions only. This reduces the latency and the overhead generated during address configuration. Moreover this scheme is the first step towards the design of a scalable routing protocol taking advantages of the proposed hierarchical addressing.

Introduction

Self-organized networks consist of hosts that rely neither on a central infrastructure, nor on an external intervention to perform necessary configurations of members. Wireless Sensor Networks (WSN), Wireless Mesh Networks (WMN) and Mobile Ad-hoc Networks (MANET) are typical examples. Internet of things, smart cities, disaster recovery emergency communication systems are possible fields of application of such networks. But to be useful and widely adopted in the real world, they need to scale well. By good scaling capability we mean: bounded configuration time, limited traffic overhead . . . in other words, good performance despite an increased size of the network.

In self-organized networks, address autoconfiguration is a major issue as it is one of the fundamental prerequisites for communication between hosts. Address assignment takes place before any routing protocol execution. The routing protocol will gain from a suitable organization of nodes obtained by the addressing mechanism. Many address autoconfiguration protocols have been proposed but those using hierarchical approaches give the better results in term of scalability as they provide benefits to hierarchical routing protocol [START_REF] Hong | Scalable routing protocols for mobile ad hoc networks[END_REF].

Some mechanisms of existing hierarchical approaches rely on the election of special nodes known as cluster heads. These nodes have more responsibility, such as maintaining the hierarchy, than the rest of the network. For this task, they have to maintain more information, for instance addresses of the nodes in their clusters. Thus their failure is difficult to handle. Other approaches use particular address structure, most of the time, an address tree. The trees are constructed in a top-down approach. But with this way, when the address length is fixed, it is difficult to extend the network with larger addresses. This could lead to rapid address exhaustion. Moreover, in high density networks, granularity problems can occur, again because of the top-down construction. In fact, an a priori distribution of addresses is difficult since the topology of the network is unpredictable. A bottom-up approach doesn't suffer from these drawbacks because it is by nature flexible. For instance, in the granularity problem, the top level of the hierarchy would raise instead of address exhaustion. In this paper, we focus on how to get hierarchical organization without having the cumbersome tasks in maintaining the hierarchy.

We propose a hierarchical addressing scheme for self-organized networks. The nodes are treated equally. Each of them runs the same algorithm: local interactions between nodes result in a hierarchical organization of the network. In other terms we obtain a hierarchy from a bottom-up construction. Moreover address acquired by a node not only indicates the hierarchy branch to which it belongs but also reflects its position in the network. To achieve all of this, we designed an address pattern that is naturally followed by the nodes as they run the proposed protocol. We choose to make a distinction between the identifier and the address as in [START_REF] Eriksson | DART: Dynamic address routing for scalable ad hoc and mesh networks[END_REF]. The identifier is unique and remains unchanged during the node's lifetime. The address gives only information on node's location.

Our two main contributions are:

-A hierarchical subdivision and labeling of space. This is a geographic subdivision of the space. Each smallest area is locally labeled with a binary number following a simple rule. A number of those areas form a bigger area that is locally labeled in its turn and so on. The result is a hierarchy of areas with several levels. The global label of an area is a concatenation of its local label and those of the bigger areas it is member of. Another interesting property of the subdivision is that areas sharing a part of their labels (e.g. same n most significant bits) are geographically close to each other. The details are discussed in Section 3. -A distributed address autoconfiguration protocol. From the previous space partitioning, an address plan is created. In a few words, the labels i.e. the binary numbers representing an area are used as addresses for the nodes. This assignment can be achieved using either the absolute geographic locations of the nodes or their relative positions to each other. In the latter case, only onehop communications are necessary to determine the address of a new host. By applying the particular labeling of the space to node addressing, we are able to construct an address hierarchy in a bottom-up way. This protocol is detailed in Section 4.

Performance of the address assignment scheme is evaluated qualitatively and through a simulation realized on ns-3 [START_REF]ns-3 : a discrete event simulator[END_REF] as described in Section 5. Results show that in the worst case (all the nodes starting at the same time in a connected topology network) the convergence delay, i.e. the time needed for all nodes to get valid addresses, is O(log(n)) where n is the number of nodes. The number of configuration packets generated during this process is O(n). The results demonstrate the scalability of the protocol.

Related work

Numerous address autoconfiguration protocols for self-organized networks, mostly for MANETs have been proposed in the literature. They can be classified as stateless, stateful or hybrid. In stateless protocols, nodes have no knowledge about the already used addresses in the network [START_REF] Perkins | IP address autoconfiguration for ad-hoc networks[END_REF][START_REF] Fazio | AIPAC: Automatic IP address configuration in mobile ad-hoc networks[END_REF][START_REF] Nesargi | MANETconf: Configuration of hosts in a mobile ad hoc network[END_REF]. The address given to a new node is usually selected randomly from the available set of addresses. Therefore it is necessary to check if the new address is already used. This process is called duplicate address detection (DAD). Because nodes don't retain all the used addresses, DAD implies the flooding of the entire network generating high traffic overhead, leading to poor scalability. AROD [START_REF] Kim | AROD: An address autoconfiguration with address reservation and optimistic duplicated address detection for mobile ad hoc networks[END_REF] tries to limit DAD procedures by performing DAD on multiple addresses but broadcast is still necessary.

Stateful schemes tend to be more scalable because there is no need for network-wide DAD. Configured nodes store a state from which addresses for new joining nodes are derived. Usually the protocols rely on some mathematical properties to generate unique sequences of addresses. For instance, Prophet [START_REF] Zhou | Prophet address allocation for large scale MANETs[END_REF] uses a function which generates distinct sequences of addresses according to the seed, each new node receiving a new seed. In [START_REF] Hsu | Prime DHCP: a prime numbering address allocation mechanism for MANETs[END_REF], properties of prime numbers are used. Other approaches consist in sharing disjoint address pools between configured nodes [START_REF] Zimmermann | IP address assignment in wireless mesh networks[END_REF] [START_REF] Sheu | A distributed IP address assignment scheme in ad hoc networks[END_REF].

The above mentioned addressing protocols produce a flat addressing scheme. Yet according to Hong et al. comparative study [START_REF] Hong | Scalable routing protocols for mobile ad hoc networks[END_REF], hierarchical and geographic routing protocols offer better scalability. And these two approaches are efficient with non flat address structure. Hierarchical addressing can be obtained by clustering the network. Some nodes act as cluster heads like in [START_REF] Iwata | Scalable routing strategies for ad hoc wireless networks[END_REF]. A node's address is the sequence of addresses of all its higher levels cluster heads addresses. An adaptation of the IPv6 stateless address autoconfiguration with a hierarchical approach is proposed in [START_REF] Weniger | IPv6 autoconfiguration in large scale mobile ad-hoc networks[END_REF]. One of the drawbacks of these schemes is that these special nodes potentially become bottlenecks because they have to deal with traffic from lower nodes in the hierarchy. In [START_REF] Eriksson | DART: Dynamic address routing for scalable ad hoc and mesh networks[END_REF], a hierarchical addressing without clustering is proposed. The link made between positions of the nodes and the branch of the hierarchy to which they belong inspired us. But in this approach, the hierarchy is constructed in a top-down way. So if there are regions with high node density, some nodes can potentially not obtain an address.

With the availability of geographic location information, another way to obtain hierarchical addressing reflecting the positions of the nodes is to partition the network space with structured areas and use the identifiers of these areas as addresses [START_REF] Li | A scalable location service for geographic ad hoc routing[END_REF]. We propose a similar scheme with elastic partition shape and size depending on the topology and the dynamic of the network.

Finally we want to point out the study in [START_REF] Eriksson | DART: Dynamic address routing for scalable ad hoc and mesh networks[END_REF] showing that scalability problem in MANETs and in self-organized networks results mainly from the use of the node's address as its identifier at the same time. The authors propose a dynamic addressing in which node's identifier remains unchanged during its lifetime; node's address is only intended for location and routing purposes.

Hierarchical areas organization

This section deals with how we can partition the two-dimensional space into labeled areas in order to get a hierarchical organization. This structure constitutes the address plan used to configure nodes as seen later in Section 4.

Hierarchy of areas

(d) Hierarchy

Fig. 1: Area hierarchy From now on, we consider the two-dimensional space. Let's delimit a square and define it as an elementary area. Then we give it a label. A label is a binary number of 2 bits, for instance, 00 (Figure 1(a)). This area is a level-1 area. The remaining available labels are 01, 10 and 11. Let's assign them to the 3 areas of the same size next to the first in a way that the whole forms a larger square area (Figure 1(b)). The latter is in turn labeled with a 2-bits number and constitutes a level-2 area. Again, 4 larger areas are grouped together resulting in a much larger area labeled with a 2-bits number (Figure 1(c)) and so on. The process can be repeated indefinitely. The hierarchy is highlighted on Figure 1(d). The elementary areas are uniquely identified by the concatenation of the labels of every larger areas to which they belong. To sum up, a level-n area has a 2-bits label appended to a global label resulting from the concatenation of the labels of level-N to level-n + 1 areas having it as "child" where N is the level of the largest area.

How about the hierarchy? Each 4 siblings of areas belongs to a particular level of the hierarchy. One area of level n is composed of 4 areas of level n-1 and so on. The equation [START_REF]ns-3 : a discrete event simulator[END_REF] gives the global labels of any 4 siblings of the space with the desired number of levels of hierarchy represented by n. The two-dimensional space can be considered as covered by a numerical matrix (M (n)) whose elements correspond to the global labels of each area.

M (n) = (10 -n%4)||M (n -1) (01 -n%4)||M (n -1) (01 -n%4)||M (n -1) (00 -n%4)||M (n -1) (1)
With M (0) = ()

Example. On Figures 1(c)(d)
we have a hierarchy with n = 3 levels. Let's consider the area colored in gray. It is labeled with 11. The larger area to which it belongs is labeled with 10 that is itself part of the largest area 00. Therefore the complete global label of the considered area is the concatenation of these labels from top to down (indicated by arrows on (c)). The result is 001011.

Properties

The area hierarchy described above has some interesting properties for the design of the address configuration mechanism:

-Unlimited. Theoretically, with equation ( 1), we can partition the entire twodimensional space with an infinite number of levels of hierarchy. -Quasi-isotropic. If we calculate values of equation ( 1) with great n, and if we draw the path from label 00 to the highest value, we would get a spiral. In other words, the construction of the structure tends to grow equally towards all directions. Moreover, as there is no privileged direction, the lengths of the labels of two opposite areas with respect to the center of the considered space tend to be the same. -Geographic and hierarchical property. One of the most important property of this area organization is the relation between the geographic location of an area and its hierarchical position. In fact areas with the same parent belong to the same level of hierarchy but are also close to each other. For instance, if we have a look at Figures 1(c) (d), the areas 001011 (the gray one) and 001010 (on "top" of the gray one in (c), on its "left" in (d) ) share the same parent level-2 area 0010 but are also geographically in the level-2 area corresponding to this label. In other words, the more bits two areas share (from the high-order bit), the more they are geographically close to each other. -Easy neighboring identification. From equation (1) we know how global labels are geographically distributed to all areas. Hence for a given area, it is easy to find the labels of the surrounding areas (from the elements of M (n) in ( 1)).

Address autoconfiguration protocol

In this section we give details about the address autoconfiguration protocol that we designed based on the previous two-dimensional space subdivision. The main idea is to use the labels of areas as addresses for nodes. In other words, the previous labels distribution serves as an address plan. This way, the address assignment scheme inherits the above mentioned properties:

-The maximum number of addressable nodes depends only on the maximum supported address length. It is possible to start with a small address length and increase it as the network grows in scale. -The more bits two addresses share (from the high-order bit), the more geographically close the hosts are. -Neighbors addresses of a given node can be calculated from its own address.

Inversely, a node's address can be deduced from those of its neighbors, provided the information about its relative position to them.

As stated before, we make a distinction between the identifier (ID) and the address of a node. The ID uniquely identifies the node and the address gives an information about its geographic position. This scheme is interesting for networks of mobile nodes. As a matter of fact it is not easy to keep track of a node whose ID is changing frequently. Hence it is better to keep the ID unchanged. But the ID has then to be resolved into an address. To achieve that, distributed lookup service exists [START_REF] Eriksson | DART: Dynamic address routing for scalable ad hoc and mesh networks[END_REF] [START_REF] Li | A scalable location service for geographic ad hoc routing[END_REF]. ID-address separation allows also the assignation of the same address to two or more nodes in the same limited geographic location. This helps to solve granularity problem (case of very high number of nodes in the same location) and spares the address space.

Basic idea

We propose a mechanism that assigns addresses to nodes depending on their geographic position in the network. There are two cases:

-If the nodes know their absolute geographic position (using GPS), the entire region where they are located is mapped with our address plan. This leads to a grid partitionning of the space. The size of the elementary squares is chosen to be close to the radio range of the nodes. Each node chooses as address the label of the region where it is located using its absolute coordinates. -If the nodes have only access to their relative geographic position [START_REF] Zekavat | Wireless Positioning Systems: Operation, Application, and Comparison[END_REF], the address assignement needs communication between nodes. From now on, we will focus on this second case.

A new arriving node gets its address from an already configured node. By configured we mean having a valid address. Thanks to a distributed algorithm, nodes acquire addresses according to the address plan. After the configuration of all nodes in the network, the distribution of the addresses looks like the distribution of the labels of areas as seen previously.

There are two types of configured nodes :

-A standard node doesn't respond to address requests from new joining nodes.

-An Address Agent (AA) node responds to address requests of incoming nodes with its own address.

It is important to notice that AA nodes aren't elected. They become AA in order to satisfy unconfigured nodes with no AA in their vicinity.

Conventions and assumptions

From now on, we will consider a wireless ad-hoc network. The neighborhood of a node is the set of nodes within its communication range. In other terms, the neighborhood is formed by all nodes reachable within one hop. The relative position of a node to one of its neighbor must be taken in a geographic sense and can be obtained using techniques similar to those surveyed in [START_REF] Zekavat | Wireless Positioning Systems: Operation, Application, and Comparison[END_REF]. We call prefix at level n the two bits corresponding to the label of an area of level n.

The address of a particular node is then the concatenation of all prefixes of all levels. For example, given the address 1011, the prefix of level 1 is 11 and that of level 2 is 10.

The following assumptions are made and are necessary for the protocol to work properly:

-A node is uniquely identified with a separate identifier than the address (the MAC address, the EUI-64 identifier, . . .) -A node is aware of its neighborhood. Nodes exchange "hello" messages periodically with the neighbors. -The nodes are aware of their relative position to their neighborhood.

-Each connected group of nodes (or one isolated node) is identified by a network ID.

Address allocation

New node. To join a network, a new node sends an address request. If present, existing AA in the neighborhood provide the node an address. If this is the first node in the network, it assigns itself the address 00 and then becomes an AA while a random network ID is generated.

Becoming an AA. When it "hears" repeated address requests from a new joining node indicating that there is no response, a standard node becomes AA to satisfy the address solicitation. For this purpose, it takes the addresses of all AA in its neighborhood and calculates a new address in accordance with the address plan. This new address will be used to configure incoming nodes.

Example. On Figure 2(a), a node A starts. It sends address requests but receives no reply. So it assigns itself the address 00 and becomes an AA. Later (Figure 2(b)), node B arrives, wants to join and sends address requests. A replies so B is configured as standard node with the same address as A. Then comes node C (Figure 2(c)). We suppose that it is out of the range of A. It sends address requests. B "hears" but doesn't reply as it is not AA. C continues to send requests. B assumes that C has no AA in its vicinity. So B configures itself as AA and uses A's address and its relative position to infer the address 11 (see Figure 1(b)). Finally B responds to C. Mobility. From the moving node point of view, when it reaches a new position, it acts like a new node: it requests new address whether it was a standard node or an AA. From the neighborhood perspective, there is no action to take. A node is aware of its moves (or those of its neighbors) by observing changes in its neighbors table.

Merging. Merging of networks can be detected when nodes with different network IDs are in contact. One solution makes the node with lower (or higher) network ID reach the other network by requesting for new address just like a new node. An optimized solution would compare the size of the two networks: the nodes from the smaller join the bigger. Estimating the size can be done in a distributed way [START_REF] Merrer | Peer to peer size estimation in large and dynamic networks: A comparative study[END_REF]. In any case, the merging process goes gradually, node per node, avoiding a potential explosion of traffic in the network. At the end, the nodes form a single network with the same network ID.

Partitioning. Partitioning of networks doesn't affect the validity of addresses in the resulting partitions. In fact, every partition corresponds to a part of the address plan. Therefore, there is no action to take. And the address space is not reduced because nodes arriving at the previously used partition will use the same addresses as the previous holders.

Evaluation

Qualitative analysis

To evaluate the quality of an address autoconfiguration protocol, common metrics are considered [START_REF] Wangi | Address autoconfiguration in wireless ad hoc networks: protocols and techniques[END_REF]:

Uniqueness. It used to be the most important criteria for address assignment in ad-hoc networks: two or more nodes aren't allowed to share an address. This is only relevant in the case where addresses serve also as identifiers. In our proposition, addresses are only intended to give location information for routing purpose. The nodes which are located in a nearby area are allowed to share the same address. It is analog to people living in the same house who share the same postal address. This contributes to the savings of address space. It solves also the granularity problem which happens when a level-n of the hierarchy is saturated and can't take more level-n -1. It happens when all possible addresses within a given area are allocated and a new node starts.

Protocol overhead. How much bandwidth is consumed during configuration processes? As we have seen previously, all the protocol's operations require local communication only. This reduces traffic overhead compared to other mechanisms with multi-hop broadcast communications. But our protocol needs neighboring discovery, so, hello packets are advertised periodically. The bandwidth consumed by these packets increases linearly with the number of nodes in the network. Nevertheless hello protocols can be improved [START_REF] Giruka | Hello protocols for ad-hoc networks: overhead and accuracy tradeoffs[END_REF], generating less overhead. Comparing to stateful approaches our solution generates fairly the same amount of traffic as these protocols need also periodic updates.

Latency. Latency is the time between the joining of an unconfigured node and when it is fully configured with a valid address. The notion of AA reduces latency. If there is an AA in the neighborhood of a new node, the configuration process ends after the exchange of only two messages (assuming a reliable radio connection). If there is no AA, the latency is increased with the time needed for one of the one-hop neighbors to become an AA. This shows that latency increases as much as the distance to the closest AA. Because all configured nodes had an AA in their vicinity prior their address assignation, the probability to not find an AA is equivalent to the probability that every AA in a given region crashes at the same time. It decreases with the size of the region. Hence the probability to not find an AA decreases with distance (again assuming a reliable radio connection). Therefore latency is bounded at least in a reliable network.

Integration with routing protocol. The efficiency of routing process can be improved with a well designed address assignation mechanism. In our scheme, addresses have a hierarchical structure giving advantages for hierarchical routing protocols which are known to scale well [START_REF] Hong | Scalable routing protocols for mobile ad hoc networks[END_REF]. Another property of the address structure is the relation between addresses and geographic position. Therefore, our protocol can be used along with geographic routing protocols that consume fewer bandwidth [START_REF] Hong | Scalable routing protocols for mobile ad hoc networks[END_REF]. A hybrid approach can also be chosen, combining the hierarchical and geographic aspects.

Scalability.

Local communication means lower communication overhead and shorter latency leading to good scalability.

Comparison with similar approach. Compared to [START_REF] Eriksson | DART: Dynamic address routing for scalable ad hoc and mesh networks[END_REF] the traffic overhead is merely on the same order. But in our solution, nodes don't have to maintain any address range. [START_REF] Li | A scalable location service for geographic ad hoc routing[END_REF] assigns addresses to nodes with only geographic position, hence without bandwidth cost. Author make the assumption that every node is aware of the global partitioning of the world, what we don't.

Compatibility with IP applications. Our approach needs some adaptations in order to run IP applications. This can be done by using nodes identifiers as "IP addresses". This way the autoconfiguration of the nodes addresses (in the sense of our protocol) and the routing through them is hidden to the application layer. Another approach consists in using our addressing scheme for geocasting, i.e, multicasting with groups composed with nodes geographically close to each other. These adaptations are necessary for our protocol to be compatible with IP-based trending protocol stack like 6LowPan.

Simulation

In this subsection we focus on a quantitative study of the scalability of the proposed protocol. The simulation was done on ns-3 [START_REF]ns-3 : a discrete event simulator[END_REF] (ns-3.22 release).

Scenario and metrics. We consider the worst case scenario for the protocol, consisting in unconfigured nodes starting at the same time in a topology connected network. In fact, joining nodes receive addresses quickly when there are already configured nodes in the network. In the case of concurrent starts, address requests are unsatisfied due to unconfigured neighbors. Each node "thinks" that it is alone then assigns itself the 00 address and chooses a random network ID while becoming an AA. After this first configuration, high number of merges occur as each node receives hello packets from different network IDs. At the end of this transient state, the entire network should share the same network ID and addresses should respect the address plan.

To study the scalability of the protocol in this worst case, we chose two metrics and observed their behavior with different network sizes:

-The convergence delay which is the amount of time between when the nodes start and when the last node acquires a valid address with respect to the address plan. In other words, it shows the maximum latency for acquiring a network-wide valid address in a concurrent start case. -The number of configuration packets which is exchanged from the start till the end of the configuration of the last node with a valid address. These packets include address requests, address offers etc. The hello packets are not considered because they are periodically exchanged in any situation.

Simulation parameters. The above metrics are measured with increasing nodes number from 100 to 1000. The nodes are randomly distributed in a square region with a density of 0.375 node per unit × unit, each node having a communication range of 3 units. These values ensure a global connected topology network. The density is kept constant for all simulations. The nodes are also kept in static positions. From the point of view of the protocol, mobility is a crash followed by a start because, as a node moves, it must acquire a new address reflecting its new location. Therefore very high mobility can be considered as a massive concurrent start as studied here. The ns-3 wifi model is 802.11b with non-Qos MAC, disabled rate control and set to ad-hoc mode. UDP is chosen as transport protocol. All the means in the data are presented with their respective 95% confidence interval.

Results. Figure 3 shows the evolution of the average convergence delay for different simulations, each with different number of nodes n. Here n varies from 100 to 1000 nodes. One finds that for a given density, the delay is proportional to log(n). The reason is that each configured node can in turn configure all its neighbors. Thus the number of "configurable" nodes grows exponentially with the number of already configured nodes. In other words, the number of configured nodes grows exponentially in time even if "slowed" by the merges implying reconfigurations.

In Figure 4 we see that the average total number of configuration packets grows linearly with n. In fact, the more we have unconfigured nodes, the more configured packets are sent. This linearity shows that for a single node, the average necessary number of configuration packets it has to exchange doesn't depend on the total number of nodes in the network.

To resume, in the worst case of massive concurrent starts in a global connected topology network, the average convergence delay is proportional to log(n) and the average number of configuration packets to n. These values can be considered as bounds for other less constraining scenarios, showing the scalability of our approach in terms of configuration delay and traffic overhead.

Conclusion and future work

We propose a hierarchical addressing protocol for self-organized networks. A node's address reflects both the branch of the hierarchy to which it belongs and its geographic position in the network. Address assignment needs only local information from one-hop neighborhood. Qualitative performance evaluation and simulations results show the scalability of the scheme. In the worst case, the average convergence delay which is the time needed for all nodes to acquire a valid address is O(log(n)) and the average total number of configuration packets exchanged is O(n).

The addressing scheme has been thought to allow the future design of a scalable routing protocol taking advantages from the hierarchical and geographic addresses. A distributed location service will be also necessary in order to follow the identifier-address separation paradigm. Regarding the addressing scheme, further research will be conducted to adapt the pattern to the three-dimensional space.

Fig. 2 :

 2 Fig. 2: Joining nodes

Fig. 4 :

 4 Fig. 3: Average convergence delay

Acknowledgments

Mandimby N. Ranaivo Rakotondravelona's PhD study is supported by Région Réunion and European Union (ERDF).


The evaluation of the crystallization point of fuels can be only accessed from the thermodynamic properties knowledge of the higher n-alkanes which compose them, and if any, whose crystalline structures have been solved. An equimolecular binary mixture n-octacosane / n-hexacosane should be a good model for the study of the complex paraffinic deposits which form in the oily fluids. To this end, it is essential to have at one's disposal, the highest purity material. The commercial products contain, as main impurities, branched-chain and/or linear chains of closely related homologues which are extremely difficult to eliminate.

The purpose of this work deals with the synthesis of one component of the binary mixture (n-octacosane) and its supercritical carbon dioxide purification. The purity of n-octacosane obtained was tested by several ways (melting point, gas chromatography, calorimetric analysis, X ray diffraction) and compared with the commercial product.

INTRODUCTION CHEMICAL SYNTHESIS

Blaise-ketone synthesis structural analysis (at room temperature) X-ray diffraction experiment (counter diffractometer, copper radiation  K  Cu) shows that the structure of the two samples (extract and commercial) are identical. The average interplanar distance for the extract is in good agreement (3.37 nm) with that indicates in the litterature (3.34 nm).

[6] GERSON, ROBERTS, SHERWOOD, Acta Cryst., B47, 1991 extract = n-octacosane The good purity of the extract was established by gas chromatographic, thermal and structural analysis, and compared with the commercial product. The purity of our n-octacosane is comparable to the Aldrich one's (99 %), and our product is free from branched-chains and homologues.

Future prospects :

We try to optimize the chemical synthesis in order to improve the yield. We also try to optimize the withdrawn of the solute in order to improve the mass balance. Finaly, the structural analysis at different temperatures is in progress.

  Laboratoire de Thermodynamique des Séparations, E.A. 22870 -E.N.S.I.C. -1, rue Grandville -BP451 -54001 NANCY (France)* barth@ensic.u-nancy.fr -fax :33.3.83.35.08.11 McHUGH, SECKER, YOGANT -J. Ind. Eng.Chem. Fundam. -vol. 17 -n°1 -1984 [3] GRISCIK, ROUSSEAU, TEJA -J. of CrystalGrowth -vol.155 -1995 [4] SMITH, CAMBPELL, ROBERTS, SHERWOOD -J.Mater. Chem. -vol.4 -n°6 -1994