INRIA Yue Huang
email: yue.huang@inria.fr

Jacques Levy-Vehel

3D Characterization of Underfoliage Targets Using L-band Tomographic SAR Data and A Wavelet-Based Approach

SAR imaging of underfoliage targets has to face a complex mixture of diverse scattering mechanisms. To characterize this complex scattering environment, nonparametric tomographic estimators are more robust to focusing artefacts but limited in resolution. Parametric tomographic estimators provide better vertical resolution but fail to adequately characterize continuously distributed volumetric scatterers such as forest canopies. To overcome these limitations, this paper addresses a new wavelet-based approach for 3D characterization of underfoliage targets. The effectiveness of this new approach is demonstrated by using L-band Multi-Baseline PolInSAR Data over Dornstetten, Germany.

Introduction

Hybrid environments refer to a scenario of objects embedded in a host natural environment (e.g. forests). Their scattering patterns consist of a complex mixture of diverse scattering mechanisms, like the volume scattering from the canopy, double bounce reflection between the ground and under-foliage objects as well as between an object and trunks, surface scattering from the underlying ground, etc. The resulting SAR information is characterized by a strong complexity, which makes SAR image analysis difficult by means of PolInSAR data (due to the single-baseline configuration). Multi-baseline PolIn-SAR techniques can be applied to reconstruct the associated scattering responses and polarimetric patterns. In [START_REF] Nannini | Imaging of targets beneath foliage with sar tomography[END_REF], using single polarization tomograms, the forest profile and truck shape were both extracted using Capon's spectral estimation approach. However, due to the limited spectral resolution and sidelobe suppression of such an approach, parametric and fully polarimetric tomographic approaches are expected to show significantly improved features of under-foliage objects and forests as it has been shown in [START_REF] Huang | Polarimetric sar tomography of tropical forests at p and lband[END_REF]. In [START_REF] Nannini | Imaging of targets beneath foliage with sar tomography[END_REF][START_REF] Huang | Polarimetric sar tomography of tropical forests at p and lband[END_REF], the applied spectral estimation methods are either nonparametric or parametric. It is known that nonparametric approaches are in general more robust to focusing artefacts, whereas parametric approaches are characterized by a better vertical resolution. It has been shown [START_REF] Stoica | Performance study of conditional and unconditional direction-of-arrival estimation[END_REF][START_REF] Huang | Building height estimation using multibaseline l-band sar data and polarimetric weighted subspace fitting methods[END_REF] that the performance of these spectral analysis approaches is conditioned by the nature of the scattering response of the observed objects. The scattering power from forest canopy in elevation can be characterized by continuous spectrum, since volumic scatterers are continuously distributed in vertical. Scattering responses from the objects or ground are considered to be localized discretely in the vertical direction. The under-foliage object with a deterministic scattering response embedded in the surrounding distributed environments, should be characterized by a mixed spectrum. Considering Conventional tomographic estimators, either nonparametric methods(e.g.Capon, Beamforming) or parametric methods (e.g. Maximum likelihood)are limited to one type of spectrum or the other, due to the lack of adaptation to the mixed spectrum. Semiparametric methods like sparse estimation methods, have been used for compressive sensing over urban areas in [START_REF] Zhu | Tomographic sar inversion by l1 -norm regularization-the compressive sensing approach[END_REF] and over forested areas in [START_REF] Aguilera | Waveletbased compressed sensing for sar tomography of forested areas[END_REF]. However for this scenario of complex mixed scattering environment, a new waveletbased approach is proposed, adapted to characterize the hybrid nature of the observed environment. The effectiveness of the proposed method is demonstrated by using the L-band multibaseline InSAR data acquired over the test site of Dornstetten, Germany.

Tomographic Signal Model

The MB-InSAR configuration consists of M acquisition positions, each pair of which are separated by a baseline. Considering an azimuth-range resolution cell that contains K backscattering contributions from scatterers located at different heights z = [z 1 , . . . , z K ], the received data vector, y ∈ C M ×1 , can be formulated as follows:

y(l) = K i=1 a(z i )s i (l) + n(l) (1)
where l = 1, . . . , L indicates one of the L independent realizations of the signal acquisition. The complex additive noise n ∈ C M is assumed to be Gaussianly distributed with zero mean and variance σ 2 n and to be white in time and space. The steering vector a(z) contains the interferometric phase information associated to a source located at the elevation position z above the reference focusing plane and is given by:

a(z) = [1, exp(jk z2 z), . . . , exp(jk z M z)] T (2)
where

k zj = 4π λ B ⊥ j
r1 sin θ is the two-way vertical wavenumber between the master and the jth acquisition tracks.

The carrier wavelength is represented by λ, whereas θ stands for the incidence angle and r 1 is the slant range distance between the master track and the scatterer. As k zj is calculated from acquisition system parameters, a(.) is a known function but the source elevation z is unknown. The source signal vector, s = [s 1 . . . s K ] ∈ C K , contains the unknown complex backscattering coefficients of the K source scatterers. We are interested in recovering the power distribution in elevation (i.e. tomographic profile),

x = [|s 1 | 2 , . . . , |s K | 2 ] ∈ R K ,
from the observed data [y(1), . . . y(L)] ∈ C M ×L . Conventionally, K < M scatterers are assumed to be located within one resolution cell. However, the forest canopy consists of a large number of elementary scatterers continuously distributed in the vertical direction. To characterize the object embedded in a forest environment, it is reasonable to assume K >> M . In order to solve this underdetermined problem, a wavelet-based sparse estimation method is proposed in the following section.

Tomographic Estimation

In the frame of urban remote sensing, the l 1 norm regularization has been used for tomographic SAR inversion by [START_REF] Zhu | Tomographic sar inversion by l1 -norm regularization-the compressive sensing approach[END_REF]. This compressive approach can efficiently localize the point-like scatterers in the vertical direction, but can not directly deal with volumic media because the volumic scatterers are not distributed sparsely in the vertical domain. In [START_REF] Aguilera | Waveletbased compressed sensing for sar tomography of forested areas[END_REF], a wavelet-based compressed sensing technique has been developed for SAR tomography of forested areas and it provided undeniable performance for forest characterization. However this approach lacks high resolution to characterize the objects beneath the canopy. For this purpose, a criterion is proposed and compactly written in a standard format of l 1 norm minimization with quadratic constraints

min x ||Bx|| 1 subject to ||AΛ x A † -R|| F ≤ (3)
where

• x = x 1 x 2 ∈ R K : scattering power distribution in elevation.
x 1 ∈ R p and x 2 ∈ R q represent respectively scattering power distribution for the objects and canopy in elevation (N = p + q).

• Bx = I (p×p) 0 0 Ψ x = x 1 Ψx 2 ∈ R K : sparse signal.
x 1 ∈ R p is sparse as the scattering responses of an object may be described with a few scatterers discretely localized in elevation. -Ψx 2 ∈ R q represents the projection of canopy power distribution x 2 onto an orthonormal wavelet basis Ψ ∈ R q×q . The power distribution of canopy in elevation, x 2 , depicts continuous regular signal behaviors, so its projection onto wavelet basis, Ψx 2 , is sparse.

• Λ x = diag(x) ∈ R N ×N . • R = 1 L L
1 y(l)y † (l) ∈ R M ×M : sample covariance matrix of observed data.

• : tolerance parameter to control model mismatch and signal sparsity.

By minimizing the criterion (3), the solution x is obtained that reconstructs the vertical power distribution of underfoliage objects. In practice, the problem in ( 3) is under SOCP formulation and can be solved by any convex optimization solver proposed in the field of sparse recovery estimation. In this paper, the CVX solver is implemented to solve this standard l 1 norm minimization, due to its implementation facility and compactness. The parameter is selected based on noise variance σ 2 n , so according the (3), should be ∝ √ M σ 2 n , e.g. for our applied data sets, we choose =4 √ M σ 2 n . For the sparse estimation controlled by the user-selected parameter, the drawback is the source signal power leaks into the neighboring sampling intervals. This fact may be due to the inappropriate choice for the parameter . If is chosen too small, then the measured data will be overfitted and the mainlobe of the source signal power spectrum may be splitted in several peaks, especially in the low SNR case. The other reason may be due to the off-grids effects and basis mismatch [START_REF] Tan | Joint-sparse recovery in compressed sensing with dictionary mismatch[END_REF], [START_REF] Xing | Polarimetric sar tomography using l2,1 mixed norm sparse reconstruction method[END_REF]. This type of leakage happens more often to the estimated signal associated to the I basis, i.e. x 1 in our criterion [START_REF] Stoica | Performance study of conditional and unconditional direction-of-arrival estimation[END_REF] . To solve this issue, a merging processing based on linear interpolation is used here, similar as in [START_REF] Tan | Joint-sparse recovery in compressed sensing with dictionary mismatch[END_REF]. Candidate peaks with amplitude > max(| x 1 |)/10 can be selected from estimated reflectivity x 1 for underfoliage objects or ground reflection. Taking a window with width ∆ and centering at each peak location z i , the neighboring peaks [z i1 , . . . , z i d ] located within [z i -∆/2, z i + ∆/2] are merged in such a way:

z m = z ic + d k=1 x 1 (z i )(z i k -z ic )/ d k=1 x 1 (z i ) with z ic = (z i1 + • • • + z i d )/d.
This method effectively merges splitted peaks within a filtering window ∆ into one peak.

Experimental Results

The tomographic analysis of a volumetric forested area and sub-canopy objects is led using polarimetic L-band airborne data acquired by the DLR's E-SAR system over the Dornstetten test site, Germany. The acquisition geometry consists of 23 flight tracks, three of which are located very close to each other (quasi-null spatial baseline) in order to estimate the temporal decorrelation. Thus 21 tracks are effectively used for the tomographic analysis. The horizontal baselines form a quasi-uniform linear array with an average baseline close to 20 m and the geometric vertical resolution is about 2 m. This quasi-regular distribution provides 3D features with reduced sidelobe levels and hence facilitates the tomographic analysis. The test zone for underfoliage objects is shown in Fig. 1.

Vertical reflectivity profiles

The wavelet basis Φ should be selected based on the criterion that the coherence between the measurement matrix A and wavelet basis Φ should be as small as possible. More details of the wavelet basis selection have been provided in [START_REF] Aguilera | Waveletbased compressed sensing for sar tomography of forested areas[END_REF]. The sym4 wavelet with 3-level decomposition has been used to form Φ in [START_REF] Aguilera | Waveletbased compressed sensing for sar tomography of forested areas[END_REF] which shows excellent performances for the reflectivity recovery of forests in vertical direction. Due to the same test data set used in this paper, we keep the same choice for wavelet basis Φ.

Considering firstly the simple scenarios in this test areas, the recovered scattering profiles from HH channel are shown in Fig. 2(a)-(c). The reflectivity profile, x, directly estimated from (3) (in blue) may produce splitted peaks, e.g. over the bare soil in Fig. 2(a). The reflectivity profile after merging is shown in black. Clearly depicted in Fig. 2(a), the merging processing effectively merges the closely-spaced neighboring peaks into a single one and its interpolated location coincides with Beamforming or Capon estimation.

Tomograms of the test line

The entire test line is estimated by diverse tomographic estimators and the resulting reflectivity tomograms are given in Fig. 3. The Capon tomogram depicts trucks with a poor vertical resolution due to the nature of continuous spectrum (Fig. 3(a)), although it can well charcterize the forest canopy. Using n s estimated by diagonal loading MOS technique in [START_REF] Huang | Underfoliage object imaging using sar tomography and polarimetric spectral estimators[END_REF], the MUSIC tomogram characterizes the uncovered truck with strong sidelobes in the vertical direction and the forests with a limited number of scatterers (Fig. 3(b)). Moreover, the underfoliage trucks are not visibly shown in the above two tomograms. Applying now the proposed wavelet-based method and merging process, the resulting tomogram demonstrates the continuous spectrum for the canopy and the high-resolution discrete spectrum for the ground and underfoliage object as shown in Fig. 3(c). Also using the proposed method, the ground and underfoliage scattering power can be separated from the distributed scattering of canopy and their tomograms can be respectively shown in Fig. 3(d) and (e).

Figure 1 :

 1 Figure 1: Pauli image for test area where trucks are set

Figure 2 :

 2 Figure 2: Normalized scattering power distribution in elevation for underfoliage truck using different polarimetric data sets. Horizontal axis: height z(m). Vertical axis: normalized scattering power.

  Proposed method with merging (d) Ground and underfoliage scattering (x 1 ) estimated by proposed method with merging (e) Canopy power (x 2 ) estimated by proposed method with merging (f) dB

Figure 3 :

 3 Figure 3: Reflectivity tomograms estimated by the proposed method with merging processing using HH data set. (Gray background:zero reflectivity).


Hakim Amara

Christophe Bichara

François Ducastelle

A Tight-Binding Grand Canonical Monte Carlo Study of the Catalytic Growth of Carbon Nanotubes

Keywords: numbers: 68.55.Ac, 61.46.Fg, 82.65.+r

1

Accurately controlling the location, diameter, chirality and length of single wall carbon nanotubes elaborated by chemical vapor deposition (CVD) is one of the critical issues for an effective use of the unique properties of these nanoobjects in many applications such as electronic devices [START_REF]Carbon Nanotubes: Synthesis, Structure, Properties and Applications[END_REF] . According to Nasibulin et al. [START_REF] Nasibulin | [END_REF] and Bachilo et al., 3 the diameter of the tubes produced by CVD is related to the diameter of the catalyst particle from which they originate. One important step is therefore to control the size distribution and the location of the catalyst particle. Chirality may result from either thermodynamic stability differences between the initial tube caps 4 or from difference in the growth kinetics. 5 The tube length can be limited by the poisoning of the catalyst resulting from uncontrolled growth parameters.

The very large number of parameters controlling the CVD reaction makes it necessary to rationalize the approach by an understanding of nucleation and growth mechanisms at the atomic level. Experimental investigations at this level are usually done by Transmission Electron Microscopy (TEM) performed post mortem outside the CVD reactor.

Remarkable progress has recently been made in the in situ observation of the growth of nanotubes, 6,7,8 but the atomic resolution is not obtained under the actual growth conditions.

Computer simulation techniques are an alternative way to gain an insight at the atomic level. However, they have to face the very difficult challenge of requiring an accurate description of the interatomic interactions, as typically provided by first principles calculations, and to address the size and time scales relevant to the experimental situation.

Efficient catalyst particles for CVD reactions are in the 1-10 nm diameter range (some thousands of atoms) and, according to Lin et al., 9 the time scale for the nucleation and growth of tubes is in the 10-100 seconds range. Such scales are largely beyond the capabilities of Molecular Dynamics (MD) techniques, even with the most simple interatomic interaction models. This means that only some elementary steps can be studied, or that the growth conditions imposed in the simulations are orders of magnitude too fast, resulting in very defective structures as compared to the almost perfect tubes obtained experimentally.

Static ab initio calculations have been used to calculate the total energies of atomic configurations considered as representative of the nucleation of carbon caps on a catalyst. 10 Hofmann et al. 11 proposed a schematic growth model and calculated the relevant activation barriers. Abild-Pedersen et al. 12 showed that carbon surface or subsurface diffusion on Ni correspond to almost equal diffusion barriers. First principles Molecular Dynamics simulations were used to study the root incorporation of C atoms on a Co catalyst 13 and the nucleation of a carbon cap on a Fe droplet was described by Raty et al.. 14 As argued by these latter authors the absence of diffusion inside the Fe particle is due to its very small size (55 atoms). This is at odds with the findings of Ding and Bolton 15 who argued that highly supersaturated carbon concentrations are required for nucleating carbon islands on the Fe particle surface. This difference might be due to the FeC interaction (empirical versus ab initio) model used or to the very short physical time of the first principles simulations. The same group studied the roles of the particle size and of a possible temperature gradient on the nanotube growth. 16 Based on their empirical MD simulations, Shibuta and Maruyama 17 found hexagonal carbon networks formed within a small Ni cluster of 108 atoms, in complete contradiction with the ab initio calculations of Zhang et al. 18 showing that, at 0 K, the most stable position for one C atom on a small Ni 38 hexagonal cluster is adsorbed on the surface rather than in the central interstitial site.

Studying the growth of nanotubes on small (Ni 48 and Ni 80 ) clusters by empirical MD, Zhao et al. 19 found almost the same mechanism as in our previous calculations on a semi infinite system (slab geometry) 20 based on a tight binding model. In both studies, four steps can be identified: C dissolution, the formation of C chains on the surface followed by the formation of sp 2 C sites that gradually detach from the catalyst surface.

Summarizing the computer simulations results, it seems that the question of the presence of carbon dissolved in the catalyst remains quite controversial. First principles static or dynamic calculations tend to show that no C is dissolved in the very small particles studied, while empirical simulations tend to find a larger amount of C dissolved. Besides the questions of the accuracy of the interatomic force model and of the time scale of the simulations, another aspect is completely neglected in the MD calculations used. Molecular Dynamics works by construction in a microcanonical or canonical ensemble with a fixed number of particles. Growth sequences are obtained either by adding particles "by hand" or by putting the catalyst particle in a box, with a fixed number of C atoms in a vapor phase. Such a process completely ignores the chemical potential gradient that is the thermodynamic driving force for the growth.

In this paper, using a carefully tested tight binding model we show that the solubility of carbon and the possibility to grow tube embryos at the surface of small Ni cluster critically depend on the carbon chemical potential. Moreover, we show that, at 1000 K, the solubility of carbon also depends on the structure of the small metallic cluster considered : disordered, liquid-like clusters incorporate more C atoms, while they tend to remain adsorbed on the surface of crystalline structures.

The tight binding model we used for C and Ni interactions has already been used by Amara et al. 20 and is described in detail in reference 21. The total energy is taken as a sum of a band structure term and an empirical repulsive term. The s and p electrons of C and d electrons of Ni are included. Calculations are performed in the grand canonical ensemble, with fixed volume, temperature (T), number of Ni atoms and C chemical potential (µ C ). In order to be efficiently implemented in the grand canonical Monte Carlo (GCMC) code, the total energy has to be taken as a sum of local terms, avoiding to recalculate the total energy of the whole box at each step of the Monte Carlo process. This is achieved by calculating local densities of electronic states using the recursion method. [START_REF]The Recursion Method and Its Applications[END_REF] To keep the model as simple and fast to compute as possible, we neglect the Ni s electrons and calculate only the first four moments of the local densities of states. The local energy of each atom therefore depends only on the positions and chemical identities of its first and second neighbors, as defined by a cut off distance set at 3.20 Å for first neighbors.

The GCMC calculations presented here compare the adsorption of carbon atoms on small Ni clusters, either "crystalline", in their face centered cubic equilibrium Wulff shape, with 201, 405, or 807 atoms, or disordered, resulting from the quench of liquid droplets with 50 or 108 atoms. These calculations were done at 1000 K, a typical temperature for the CVD synthesis of single wall nanotubes. We analyze the influence of the carbon chemical potential on the carbon nanostructure grown on the Ni cluster, on the structure of the nickel carbon interface and on the solubility, if any, of carbon in the Ni cluster.

The decomposition reaction of the carbon rich feedstock under specific partial pressure conditions is not taken into account explicitly in our calculations. However, the result of this reaction is to provide atomic carbon with a given chemical potential that is able to adsorb and diffuse on, or in, the nickel surface. As explained in e.g. Lolli et al., 5 this carbon chemical potential is experimentally controlled through the thermochemistry of the decomposition reaction. To achieve this in the computer experiments, we use Monte Carlo simulations in the grand canonical ensemble. [START_REF] Frenkel | Understanding Computer Simulation[END_REF] The grand canonical algorithm used consists in a series of Monte Carlo macrosteps.

Each macrostep randomly alternates displacement moves for Ni or C atoms, attempts to incorporate carbon in a previously defined active zone and attempts to remove existing carbon atoms. Within each macrostep, we systematically performed four times the number of atom attempted displacement steps. To incorporate carbon atoms in the structure, 1000 attempts were made and ended as soon as one successful incorporation has occurred. The number of attempted carbon removal steps was equal to twice the number of C atoms present in the structure. We typically performed up to 5000 macrosteps. We will see below that this number of macrosteps is large enough to reach equilibrium when the chemical potential conditions are such that no carbon nanostructure grows. Of course, under growth conditions, no equilibrium is ever reached and the number of adsorbed C atoms keeps increasing. The maximum amplitude of the attempted displacements of Ni or C atoms is adjusted during the run in order to have a rejection rate around 50%, ensuring an optimal use of the computer resources to sample the configurational space of the system. [START_REF] Frenkel | Understanding Computer Simulation[END_REF] On average, the maximum amplitude of the displacements of Ni atoms turns out to be twice as large as that of C atoms, meaning that the mobility of Ni atoms is larger. In order to mimic the CVD process, the active zone for inserting or extracting carbon atoms is defined as a region of space at less than 3 Å above and 3 Å below the surface of the Ni cluster. Moreover, to avoid the encapsulation of the Ni cluster with carbon and to account for the fact that, in the experiments, the catalytic particles are supported, the active zone is limited to the topmost (60%) part of the cluster. We stress that this is a very crude approximation that neglects the modifications of the cluster structure that can be induced by the substrate. [START_REF] Vervisch | [END_REF] In the case of the largest fcc Wulff-shaped clusters, this zone is smaller: 50% for the 405 atoms cluster and 40% for the 807 atoms cluster. A first reason for this is to limit the CPU time of the calculations, since the fourth moment tight binding model for Ni and C atoms is replaced by a much simpler second moment approximation model for Ni atoms only, as soon as they are far enough from any C atom (i. e.: at a distance larger than 6.4 Å ). A second reason is that these fractions of the clusters volume roughly correspond to the same number of Ni atoms (151 for the 201 atom cluster, 231 for the 405 atoms one and 267 for the 807 atoms one), which will be used to calculate the mole fraction of carbon atoms dissolved in the Ni structure.

To analyze the results of the calculations, we will have to discriminate between carbon atoms that are outside the Ni cluster, generally forming sp (small chains) or sp 2 (layered) structures and individual carbon atoms that are adsorbed on the surface or incorporated in subsurface or bulk. A convenient way to do this is to calculate the distance between the carbon atom of interest and its nearest carbon neighbor. If this distance is smaller than 1.7 Å , the atom is defined as an "outer" C atom, because C-C bond lengths in sp or sp 2 bonding states are smaller than this. If it is longer, the carbon atom is either adsorbed on the Ni surface, with Ni neighbors in the 1.85-1.95 Å distance range, or incorporated in interstitial sites: such carbon atoms are denoted as "inner" carbon atoms in the following. This criterion stems from the analysis of the carbon carbon pair correlation function that clearly shows distinctive features for each type of atoms. It can be easily checked by a visual inspection of the structures formed.

We first study the effect of the carbon chemical potential on the structures formed outside the particle. Starting with the same Ni 50 disordered droplet, we performed GCMC runs with µ C varying between -6.00 and -4.50 eV/atom, by steps of 0.75 eV/atom. The carbon chemical potential is referred to a fictitious ideal monoatomic gas, explaining its values that are of the order of the cohesive energies of the various carbon phases (e.g.:

-7.41 eV/atom for a graphene layer in our model). Figure 1 shows a series of typical configurations obtained under these conditions. At low chemical potential, no outer carbon structure is formed. Carbon atoms land on the surface and tend to diffuse on the surface or towards subsurface sites. They sometimes form carbon dimers, but no twofold coordinated long chain structure is ever formed. An equilibrium situation is quickly reached, with about 25 C atoms adsorbed. On the contrary, when the chemical potential is much larger (-4.5 eV/atom), a disordered and thick carbon layer is formed outside the cluster. This amorphous layer is formed by carbon atoms with 3 or 4 carbon neighbors. This can be interpreted as the growth of an amorphous carbon fiber. A much more interesting situation, as far as the formation of a carbon nanotube is concerned, is observed at intermediate chemical potential values. At µ C = -5.25 eV/atom and 1000 K, a cap of carbon atoms is formed. It encapsulates the topmost part of the Ni droplet. Figure 2 presents a series of configurations characteristic of the formation of the cap. At the very beginning of the GCMC run, carbon atoms "land" on the available surface of the Ni particle. Then, instead of diffusing towards subsurface sites as observed at lower chemical potentials, they tend to form dimers and short chains at the surface of the droplet. Because µ C is larger, the flux of incoming atoms is larger and C atoms quickly find another C to form a C-C bond that stabilizes it on the surface.

Although no time scale is included in the grand canonical Monte Carlo scheme, we can see that this step is very fast: in less than 50 Monte Carlo macrosteps, carbon chains are already formed on the surface. As observed in our previous calculations on Ni slabs, 20 the chains grow, cross each other to form threefold coordinated sp 2 carbon sites that act as nucleation centers to grow sp 2 layers. These sp 2 carbon atoms interact weakly with the Ni surface and the cap formed can gradually detach from the droplet. The difference with calculations performed on flat surfaces is that the curvature of the Ni droplet induces a curvature of the carbon cap. The cap diameter and curvature are determined by the Ni particle shape at the moment when the cap is formed. However, since Ni atoms are more mobile than C atoms, the shape of the Ni droplet can be modified later in the process. As compared to the almost perfect graphene like layer, mostly formed with hexagons, obtained on a flat Ni surface, the curvature and growth conditions impose a larger number of defects such as pentagons, heptagons, etc. The cap structure shown in figure 1 is formed by 13 pentagons, 28 hexagons, 7 heptagons, 5 octogons and 7 9-membered rings. The cap is very defective as compared to ideal nanotube terminations that require only a small number of pentagons to be formed. 25 The larger number of defects observed here results from the growth conditions: the carbon chemical potential chosen to obtain realistic structures in a reasonable, although long, CPU time is probably too high. Under such conditions, the growth is too fast and the defects formed have a very small probability to be healed.

The GCMC calculations presented above indicate that there is an optimal carbon chemical potential to grow sp 2 carbon caps on a very small Ni droplet. When the carbon chemical potential is large enough, carbon nanostructures are formed outside the Ni droplet, while some carbon atoms remain adsorbed on the surface, in close contact with Ni atoms, or even diffuse inside the particle. The mole fraction of these inner C atoms depends on the carbon chemical potential and on the temperature, as indicated by comparing with our previous calculations at 1500 K. 20 We note here that it also depends on the particle size and on the structural state of the Ni cluster. In order to analyze these latter points, we performed the same calculations on a larger disordered droplet with 108 Ni atoms and on face centered cubic clusters with a truncated octahedron shape that minimizes their total (surface + volume) energy. These so called Wulff-shaped clusters have only ( 111) and (100) facets. Three sizes were considered: 201, 405 and 807 Ni atoms. At 1000 K and µ C = -5.25 eV/atom, the results are qualitatively the same, as far as the cap formation is concerned.

As shown in figure 3, more or less defective carbon layers are formed on the cluster surface.

Their shape is imposed by the cluster geometry. In order to allow them to detach from the surface, much longer runs should be performed, as has been done for the Ni 50 disordered cluster. It is interesting to notice that the crystalline structure of the cluster is preserved, although the Ni atoms on the edges are less stable than the others and can be strongly displaced, as shown on the right hand image in figure 3.

A visual inspection of the structures obtained seems to indicate that the number of dissolved C atoms is smaller in the case of crystalline structures than in the disordered ones. This is confirmed by the analysis of the mole fraction of inner carbon atoms as a function of the number of Monte Carlo macrosteps, plotted in figures 4 and 5. For the disordered structures, the mole fraction of inner C atoms is calculated with respect to the total number of Ni atoms (respectively 50 and 108), because the particles are small and C atoms tend to diffuse in the whole structure. As mentioned above, for the fcc clusters, the mole fraction of inner C atoms is calculated with respect to a smaller number of Ni atoms. These different ways of calculating the mole fractions tend to minimize the differences between the carbon solubilities in crystalline or disordered clusters. At 1000 K and µ C = -6.00 eV/atom (see figure 4), the difference is quite clear, with about 40% C adsorbed on, or dissolved in, the disordered cluster and about 15% C atoms, mostly adsorbed on the surface or subsurface sites of the crystalline clusters. The same holds for the runs at µ C = -5.25 eV/atom. However, a striking difference can be noticed between the two situations. At µ C = -6.00 eV/atom the mole fraction of inner carbon atoms gently rises during the course of the Monte Carlo run to reach an equilibrium value. At µ C = -5.25 eV/atom, the number of carbon atoms adsorbed on the cluster surface increases very rapidly at the beginning of the process, then decreases and rises again. During this process the total number of carbon atoms constantly increases. The sharp peak observed in the inner carbon concentration at the beginning of the adsorption process corresponds to the adsorption of individual C atoms on the cluster surface. As soon as the concentration of surface C atoms is large enough, they tend to form chains and then sp 2 structures that detach from the surface, explaining the depletion of C at the surface. At lower chemical potential, this surface concentration threshold is never reached and the C atoms gradually diffuse towards subsurface or bulk interstitial sites. Summarizing this paper, we study the early stages of the formation of carbon nanostructures on small nickel clusters. The GCMC method used enables us to emphasize the critical role of the carbon chemical potential on the resulting structure. We show that an optimal chemical potential value exists to nucleate nanotube caps. Because of the short time scale spanned by the computer simulations as compared to the hundreds of seconds of the experiments, the cap structures obtained are much more defective than what is assumed for the experimental ones. The coarse sampling of the chemical potential values by steps of 0.75 eV/atom also plays a role: less defective caps could probably be grown with µ C closer to -6.00 eV/atom, but this would require longer simulation times. Under suitable carbon chemical potential and temperature conditions, the early stages of the growth are quite similar to what has been observed on flat surfaces, 20 with the difference that the curvature is imposed by the catalyst particle's size at the moment of the nucleation.

The atomistic growth mechanism is more or less in agreement with most of the previous computer simulation studies. 14,15,16,19 However these authors do not take into account the carbon chemical potential that plays a critical role on the outer nanostructure formed, but also on the surface state of the catalyst. In addition, we show that the presence of carbon in surface, or interstitial subsurface or bulk sites depends on a second parameter that is the structure of the catalyst particle. As in the case of the bulk phase diagram that exhibits a low solubility of carbon in crystalline nickel, but a larger one in the liquid phase, we show that the carbon solubility is larger in disordered clusters. Our study

is not yet complete since we should compare liquid and solid structures with the same number of atoms. This work is in progress. However, this is an important finding because the surface state of the catalyst is of fundamental importance if one wishes to understand the origin of the chiral selectivity that has been reported for instance by Bachilo et al.. 3

FIG. 1 :

 1 FIG. 1: Typical configurations resulting from GCMC simulations of the growth of C on a 50 Ni atom disordered droplet at 1000 K. Left panel, µ C = -6.00eV/atom, central panel µ C = -5.25 eV/atom, right panel µ C = -4.50 eV/atom. 5000, 4000 and 2500 Monte Carlo macrosteps were performed, respectively. Nickel atoms are represented in orange, inner carbon atoms are in green and outer carbon atoms are in grey. See text for the definition of "inner" and "outer" carbon atoms.

FIG. 2 :

 2 FIG. 2: Typical growth sequence during a GCMC simulation of the adsorption of C on a 50 Ni atom disordered droplet at 1000 K and µ C = -5.25 eV/atom. From left to right and top to bottom: 1) carbon atoms or diatoms adsorbed; 2) chains growing; 3 and 4) cap formed; 5 and 6) cap detaches from the Ni droplet. Nickel atoms are represented in orange, inner carbon atoms are in green and outer carbon atoms are in grey. See text for the definition of "inner" and 'outer" carbon atoms.

FIG. 3 :

 3 FIG. 3: Typical configurations resulting from GCMC simulations of the growth of C on nickel fcc Wulff-shaped clusters at 1000 K and µ C = -5.25 eV/atom. Left: 201, center: 405 and right:807 Ni atoms. The active zones for the GCMC calculations were the topmost 60%, 50% and 40% respectively (see text). Nickel atoms are represented in orange, "inner" carbon atoms are in green and "outer" carbon atoms are in grey. See text for the definition of "inner" and "outer" carbon atoms.

10

 10

FIG. 4 :

 4 FIG. 4: Mole fractions of surface and subsurface carbon atoms, "inner" carbon atoms in the text, as a function of the number of outer Monte Carlo loops (macrosteps), calculated at 1000 K and µ C = -6.00 eV/atom. Black circles: Ni 50 liquid droplet. Pink squares: Ni 108 liquid droplet. Red up-pointing triangles: fcc 201 Ni cluster. Green down-pointing triangle: fcc 405 Ni cluster. Blue diamond: fcc 807 Ni cluster.

FIG. 5 :

 5 FIG. 5: Mole fractions of surface and subsurface carbon atoms, "inner" carbon atoms in the text, as a function of the number of outer Monte Carlo loops (macrosteps), calculated at 1000 K and µ C = -5.25 eV/atom. Black circles: Ni 50 liquid droplet. Red up-pointing triangles: fcc 201 Ni cluster. Green down-pointing triangle: fcc 405 Ni cluster. Blue diamond: fcc 807 Ni cluster.

Acknowledgments Part of this work is supported by the Belgian Program on Interuniversity Attraction Poles (PAI6) on "Quantum Effects in Clusters and Nanowires". H. A. acknowledges the use of the Interuniversity Namur Scientific Computing Facility (Namur-ISCF), a common project between FNRS, SUN Microsystems, and Les Facultés Universitaires Notre-Dame de la Paix (FUNDP) and the LEMAITRE computer of UCL.


Rami Belkaroui
email: rami.belkaroui@gmail.com

Rim Faiz
email: rim.faiz@ihec.rnu.tn

Aymen Elkhlifi
email: aymen.elkhlifi@paris4.sorbonne.fr

Using Social Conversational Context For Detecting Users Interactions on Microblogging Sites

In the current era, microblogging services like Twitter, gives people the ability to communicate, interact, collaborate with each other, reply to messages from others and create conversations. These services can be seen as very large information repository containing millions of text messages usually organized into complex networks involving users interacting with each other at specific times. Several works have proposed tools for tweets search focused only to retrieve relevant tweets. Therefore, users are unable to explore the results or retrieve more relevant tweets based on the content, and may get lost or become frustrated by the information overload.

In this paper, we propose a new method to retrieve conversation on microblogging sites particularly Twitter. It's based on content analysis and content enrichment. The goal of our method is to present a more informative result compared to conventional search engine. The proposed method has been implemented and evaluated by comparing it to Google and Twitter Search engines and we obtained very promising results.

Introduction

Last years, People are becoming more communicative through expansion of services and multi-platform applications such as blogs, forums and social networks which establishes social and collaborative backgrounds. This behavior leads to an accumulation of an enormous amount of information. Among these platforms are so-called microblogs. Furthermore, microblogging services [START_REF] Boyd | Tweet, tweet, retweet: Conversational aspects of retweeting on twitter[END_REF] gives people the ability to communicate, interact, collaborate with each other, reply to messages from others and create conversations. While communicating people share different kind of information like common knowledge, opinions, emotions, information resources and their likes or dislikes. The analysis of those communications can be useful for commercial applications such as trends monitoring, reputation management and news broadcasting. In addition, one of main characteristic of microblogging services is that users are not limited to produce contents; they can get involved indirectly in conversations with other by liking and sharing user's posts. Several works have proposed tools for tweets search focused only to retrieve relevant tweets. Therefore, users are unable to explore the results or retrieve more relevant tweets based on the content, and may get lost or become frustrated by the information overload. In addition, finding good results concerning the given subjects needs to consider the entire context. However, context can be derived from user interactions.

This paper proposed a conversation retrieval method which can be used to extract conversation from twitter. Comparing with current methods, the new proposed not only extract directly reply tweets, but also relevant tweets which might be retweets or comments and other possible interactions. The method extract extensive posts beyond conventional conversation. The rest of the document is organized as follows: we begin by presenting related work addressing conversation retrieval on microblogging sites. In section 3, we propose our method allows extracting user's content interactions. The experimentation and evaluation results are detailed in section 4. The final section presents a summary of our work and future dicrections.

Related Work

Conversation retrieval is a new search paradigm for microblogging sites. It results from the intersection of Information Retrieval and Social Network Analysis (SNA). Most of microblogging services provide a way to retrieve relevant information [START_REF] Jabeur | Uprising microblogs: A bayesian network retrieval model for tweet search[END_REF][START_REF] Cherichi | New metric measure for the improvement of search results in microblogs[END_REF], but lack the ability to provide all tweets discussion. There have been few previous researches dealing specifically with conversation detection. In addition, existing conversation retrieval approaches for microblogging sites [START_REF] Cogan | Reconstruction and analysis of twitter conversation graphs[END_REF][START_REF] Magnani | Information propagation analysis in a social network site[END_REF][START_REF] Magnani | Conversation retrieval from twitter[END_REF][START_REF] Magnani | Conversation retrieval for microblogging sites[END_REF] have so far focused on the particular case of a conversation formed by directly replying tweets. [START_REF] Magnani | Conversation retrieval from twitter[END_REF] proposed a user-based tree model for retrieving conversations from microblogs. They considered only tweets that directly respond to other tweets by the use of @sign as a marker of addressivity. The downside is that this method does not consider tweets that do not contain the @sign. Similarly [START_REF] Cogan | Reconstruction and analysis of twitter conversation graphs[END_REF] proposed a method to build conversation graphs, formed by users replying to tweets. In this case, a tweet can only directly reply to other tweet. However, users can get involved indirectly in conversations communities by commenting, liking, sharing user's posts and other possible interactions. In [START_REF] Kumar | Dynamics of conversations[END_REF] the authors concentrated on different microblogging conversations aspects. They proposed a simple model that produces basic conversation structures taking into account the identities of each conversation member. Other related works [START_REF] Huang | Conversational tagging in twitter[END_REF] focusing on different aspects of microblogging conversation, that deal respectively with conversation tagging and topics identification.

Twitter Conversation Detection Method: TCOND

We propose a method which combines a set of conversational features and the directly exchanged text messages in order to extract extensive posts beyond conventional conversation. In addition, we defined a conversation as a set of short text messages posted by a user at specific timestamp on the same topic. These messages can be directly replied to other users by using "@username" or indirectly by liking, retweeting, commenting and other possible interactions. In the next part, we will present more details about our two approach steps. et al.

Step 1: Constructing Direct Conversation

In this step, we aim to collect all tweets in reply directly to other tweets. Obviously, a reply to a user will always begin with "@username". Our goal in this step is to create reply tree. The reply tree construction process consists of two algorithms run in parallel recursive root finder algorithm and iterative search algorithm.

Algorithm 1 Recursive Root Finder (A: twitter)

Let T be a tweet collected from Twitter (ID tweet) while (T i !=root) do Extract T i -1 by matching field "in reply to status id" end while A : twitter = A : twitter -1 Let T0 is the root (first tweet published) of the conversation C and T is a single tweet of the conversation retrieved. Let consider T i the type of tweet T. A tweet can have three types: root, reply or retweet. The goal of the Recursive Root Finder Algorithm is to identify the conversation root T0 given T. Note that when the algorithm starts, T is not known. Once, the conversation root T0 has been established, the Iterative Search Algorithm is used to seek the remainder of conversation C by searching all tweets addressed to T i using matching field "in reply to status id". It is run repeatedly until some conditions, indicating that the conversation has ended, are met.

Step 2: Relevant Indirect Tweets

We define new features that may help to detect tweets related indirectly to a same conversation. The goal is to extract tweets that may be relevant to the conversation without the use of the @symbol. We use the following notations in the sequel:

• t i is a set of tweets present in direct conversation (tweets in reply to other tweets directly).

• t j is a tweet that can be linked indirectly to conversation.

The features we used are:

• Using the same URL:

By sharing an URL, an author would enrichment the information published in his tweet. This feature is applied to collect tweets that share the same URL. P1(t i , t j ) = 1 if t contains the same URL. 0 otherwise.

(1)

• Hashtags Similarity:

The # symbol, called hashtag, is used to mark a topic in a tweet or to follow conversation. Any user can categorize or follow topics with hashtags. We used this feature to collect tweets that share the same hashtags.

i , t j ) = 1 if t contains the same hashtag. 0 otherwise.

(2)

• Tweets Time Difference:

The time difference is highly important feature for detecting tweets linked indirectly to conversation. We use the time attribute to efficiently remove tweets having a large distance in terms of time compared to conversation root.

• Tweets Publication dates:

Date attribute are highly important for detecting conversations. Users tend to post tweets about conversational topic within a short time period. The Euclidean distance has been used to calculate how similar two posts publication dates are.

• Content:

We compute the textual similarity between each element in t j , t i taking the maximum value as the similarity measure between two messages. The similarity between two elements is calculated using the well-known tf-idf cosine similarity, sim(t i , t j ).

• Similarity Function:

Finally, the similarity between tweets indirectly linked to conversation and tweets which are present in the reply tree is calculated by a linear combination between their attributes.

Experiments and Results

The following experiment has been designed to gather some knowledge on the impact of our results on end-users. For this experiment we have selected three events and queried our dataset using Google 1 , Twitter search engine 2 and our method (TCOND). Then, we have asked a set of 100 assessors to rate the top-10 results of every search task with three relevance levels, namely highly relevant (value equal to 2), relevant (value equal to 1) or irrelevant (value equal to 0). In order to measure the results quality, we use the Normalized Discounted Cumulative Gain (NDCG) at 10 for all the judged events. In addition, we used a second metric which is the Precision at top 10.

The dataset has been obtained by monitoring microblogging system Twitter posts over the period of July-August 2013. In particular, we used a sample of about 113 000 posts containing trending topic keywords using Twitter's streaming API. Trending topics have been determined directly by Twitter, and we have selected the most frequent ones during the monitoring period.

Experimental Outcomes and Interpretation Results

We compare our conversation retrieval method with the results returned by Google and by Twitter search engine using two metrics namely the P@10 and the NDCG@10. From this comparison, we obtained the values summarized in Table 1 where we notice that our method overcomes the results given by both of Google and Twitter. The reason of these promising values is the fact that we combine a set of conversational features and direct replies method to retrieve conversation may have a significant impact on the users' evaluation. P@10 (Average%) NDCG (Average%) Focusing on the three messages selections, we observe that all conversations obtained with our method receive higher scores with compared to Google and Twitter's selection. According to the free comments of some users and following the qualitative analysis of the posts in the three selections we can see that Google and twitter received lower scores not because they contained posts judged as less interesting, but because some posts were considered not relevant with regard to the searched topic.

Concentration on the three messages selections we observe that all conversations selections obtained with twitter search has higher scores with respect to Google's selection. These results lead us toward a more general interpretation of the collected data. It appears that the social metrics usage have a significant impact on the users' degree interest in the retrieved posts. In addition, the retrieving conversations process from Social Network differs from traditional Web information retrieval; it involves human communication aspects, like the degree interest in the conversation explicitly or implicitly expressed by the interacting people.

Conclusion

This work explored a new method for detecting conversation on microblogging sites: an information retrieval activity exploiting a set of conversational features in addition to the directly exchanged text messages to retrieve conversation. Our experimental results have highlighted many interesting points. First, including social features and the concept of direct conversation the search function improves the relevance of tweets informativeness and also provides results that are considered more satisfaction with respect to a traditional tweet search task. Future work will further research the conversational aspects by including human communication aspects, like the degree of interest in the conversation and their influence/popularity by gathering data from multiple sources from Social Networks in real time.

  Table of Values for Computing our Worked Example

	Task1
	Google	59.62	56.86
	Twitter	65.73	59.71
	TCOND	73.28	64.52
	Task2
	Google	57.31	56.02
	Twitter	62.78	58.45
	TCOND	67.27	62.73
	Task3
	Google	63.21	66.52
	Twitter	65.88	68.46
	TCOND	77.27	69.33
	TAB. 1 -


Rami Belkaroui
email: rami.belkaroui@gmail.comdh.jemal@gmail.com

Dhouha Jemal

Rim Faiz
email: rim.faiz@ihec.rnu.tn

Exploring Big Data Environment for Conversation Data Analysis and Mining on Microblogs

Keywords: Social Media, Big Data analysis, data mining, conversation retrieval, social networks analytics

Today, social media services and multiplatform applications such as microblogs, forums and social networks gives people the ability to communicate, interact and generate content which establish social and collaborative backgrounds. These services now embodies the leading and biggest repository containing millions of Big social Data that can be useful for many applications such as measure public sentiment, trends monitoring, reputation management and marketing campaigns. But social media data are essentially unstructured that's what makes it so interesting and so hard to analyze. Making sense of it and understanding what it means will require all new technologies and techniques, including the emerging field of big data. In addition, social media is a key model of the velocity and variety which are main characteristics of Big Data.

In this paper, we propose a new approach to retrieve conversation on microblogging sites that combine Big Data environment and social media analytics solutions. The goal of our approach is to present a more informatives result and solve the information overload problem within Big Data environment. The proposed approach has been implemented and evaluated by comparing it with Google and Twitter Search engines and we obtained very promising results.

Introduction

Social media is considered as a part of the Web 2.0 movement, which gave birth to a huge volume of data produced by users called User Generated Content (UGC). This massive explosion of volume and data types' diversity implies the imposition of the Big Date in our technological landscape. Furthermore, many of the most important sources of Big Data are relatively new. The huge amount of information from social networks, are only as old as the networks themselves; for example Facebook was launched in 2004, Twitter in 2006. In addition, the term Big data [START_REF] Smith | Big data privacy issues in public social media[END_REF] has been mainly used in two contexts, firstly as a technological challenge when dealing with dataintensive domains such as high energy physics, astronomy or internet search, and secondly as a sociological problem when data about us is collected and mined by companies such as Facebook, Google, mobile phone companies, retail chains and governments.

In the current era, social media services attract more and more users and tend to become a solid media for simplified collaborative communication due to the ease and the speed of information sharing especially in real time. Thus, social media services have completely changed the manner in which people communicate and share information. They [START_REF] Jabeur | Uprising microblogs: A bayesian network retrieval model for tweet search[END_REF] give people the ability not only to communicate, interact and collaborate with each other, reply to messages from others and create conversations. In addition, social media such as Twitter and Facebook represents an enormous public archive of human thought that captures the ideas, opinions and debates taking place around the world on almost any topic at any moment in time. The analysis of those communications can be useful in various ways such as measuring public sentiment, trend monitoring, reputation management, marketing campaigns, customer behavior and news analysis. Additionally, the analysis of Big social Data has become substantially to help businesses gain a better understanding of their consumers by incorporating social feedback, which should improve decision-making process. Although, according to Salesforce research, 89% of business leaders believe that Big Data will revolutionize business operations in the same way the Internet did, and 83% have pursued Big Data projects in order to seize a competitive edge. 3 As Big Data is becoming a hot topic in many areas where datasets are so large that they can no longer be handled effectively or even completely, it presents an opportunity to analyze expressions and behavioral traces available on social platforms. The question that arises is how to benefit the e-identity and user's opinions shared on social medias.

In this paper, we propose a new approach to retrieve conversation on microblogging sites that combine Big Data environment and social media analytics solutions. The proposed approach can be used to extract conversation from social media in order to provide relevant results correspondig to user's information needs based on their interactions analysis. In particular, the novelty of our approach is the ability to provide an informative relevant data to satisfy any information need in a large social Big Data. The remainder of this paper is organized as follows. In section 2, we give an overview of related work addressing the domains used in our work: Big Data analysis and social media analytics solutions. In section 3, we present our proposed approach for conversation retrieval, then in section 4 we discuss the obtained results. Finally, section 5 concludes this paper and outlines our future work.

Related Work

Basically, our work lies at the intersection of two main domains: Big Data analysis and social media retrieval. This section is devoted to presenting these latter.

Big Data Analysis

Currently, a strong interest towards the term Big Data is arising in the literature. Several research works have focused on this actual research trend in this field. In this context, Sagiroglu et al [START_REF] Sagiroglu | Big data: A review[END_REF] presented an overview of big data's content, scope, samples, methods, advantages and challenges, detail Big Data its main components and discuss privacy concern. In [START_REF] Smith | Big data privacy issues in public social media[END_REF], the authors have performed analysis on Flickr, Facebook and Google+ social media sites. Based on this analysis, they have discussed the privacy implications and also geo-tagged social media; an emerging trend in social media sites. The proposed concept in this paper helps users to get informed about the data relevant to them in such large social Big Data. In [START_REF] Cuzzocrea | Analytics over large-scale multidimensional data: The big data revolution![END_REF], open problems and actual research trends are highlighted with the aim of providing an overview of state of the art research issues and achievements in the eld of analytics over Big Data, and extend the discussion to analytics over big multidimensional data. This work presented several novel research directions a rising in this field, which plays a leading role in next-generation Data analysis.

According to [START_REF] Manovich | Trending: the promises and the challenges of big social data[END_REF], the expressions and behavioral traces from large numbers of individuals or groups on social platforms constitute Big Data. The authors proposed to analyze this data as an opportunity to provide valuable insights into the arrays of meaning and practice that emerge and manifest social platforms users online.

In [START_REF] Boyd | Six Provocations for Big Data[END_REF], authors presented the problem of misleading claims to objectivity and accuracy for Big Data. They supposed that in the case of social media data, there is a 'data cleaning' process: making decisions about what attributes and variables will be counted, and which will be ignored. They described this process as inherently subjective. In addition to this question, there is the issue of data errors. Authors considered the large data sets from Internet sources as unreliable, prone to outages and losses, and these errors and gaps are magnified when multiple data sets are used together. For this purpose, [START_REF] Bollier | The promise and peril of big data[END_REF] explains that as a large mass of raw information, Big Data is not self-explanatory. The authors wonder if the data can represent an 'objective truth' or is any interpretation necessarily biased by some subjective filter or the way that data is 'cleaned?'

Social Media Retrieval and Analysis

Extracting information from Social media Sites is one of the critical problems which have already been addressed over the past years due to its theoretical and practical signifiance. Social media have become a digital place where users can discuss public issues, share critical information during natural disasters and it will be possible to comment TV shows they are following. Users examine social media sites for answers, timely information (e.g., news, events), people information and topical information [START_REF] Efron | Questions are content: A taxonomy of questions in a microblogging environment[END_REF][START_REF] Teevan | #twittersearch: A comparison of microblog search and web search[END_REF]. However, search functionality provided by those sites is limited to keyword based retrieval to return the most recent posts. However, users are able neither to explore the results nor retrieve more relevant information based on the content [START_REF] Belkaroui | Towards events tweet contextualization using social influence model and users conversations[END_REF], and may get lost or become frustrated by the information overload [START_REF] Bernstein | A torrent of tweets: Managing information overload in online social streams[END_REF].

Recently, various researches have focused on these phenomena with a closer perspective [START_REF] Bruns | #Ausvotes: how twitter covered the 2010 australian federal election[END_REF][START_REF] Magnani | Information propagation analysis in a social network site[END_REF][START_REF] Magnani | Conversation retrieval for microblogging sites[END_REF]. In [START_REF] Magnani | Conversation retrieval from twitter[END_REF] the authors proposed a user-based tree model for retrieving conversations from microblogs. They only considered tweets that directly respond to other tweets by using the "@username" as a marker of addressivity. The advantage of this method is having a coherent conversation based on the direct links between users. The downside of this method is the fact of neglecting the tweet that does not contain the "@sign". Nevertheless, we can have tweets that are related to the conversation even though they are not directly linked with other tweets. In [START_REF] Cogan | Reconstruction and analysis of twitter conversation graphs[END_REF], the authors proposed a method to build conversation graphs. The authors focused on the particular case of a conversation formed by users replying to tweets. In this case, a tweet can only reply to one other tweet and a retweet are ignored, but users can get involved in conversations with other by commenting, liking and sharing other user's posts. Other related works concentrated on different aspects of microblogging conversations are [START_REF] Huang | Conversational tagging in twitter[END_REF][START_REF] Song | A spatio-temporal framework for related topic search in microblogging[END_REF], the deal respectively with the tagging of conversations and the identification of topics. Kumar et al [START_REF] Kumar | Dynamics of conversations[END_REF], in their work has proposed a simple mathematical model that produces basic conversation structures taking into account the identities of each member of the conversation.

Besides, some recent studies aimed to identify how information flow depends on the structural properties of user interactions [START_REF] Cha | A measurement-driven analysis of information propagation in the flickr social network[END_REF][START_REF] Kwak | What is twitter, a social network or a news media?[END_REF]. Moreover, modeling the interaction among users plays a crucial role in order to understand how the information is disseminated in the network [START_REF] Wang | Information spreading in context[END_REF][START_REF] Gómez | Modeling the structure and evolution of discussion cascades[END_REF] and how to maximize its spread [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF][START_REF] Chen | Efficient influence maximization in social networks[END_REF]. In [START_REF] Kwak | What is twitter, a social network or a news media?[END_REF], the authors proposed the first large scale analysis of both topological and temporal structures of retweets in order to catch users' popularity of, trending topics and temporal patterns describing the propagation of information in the network. The temporal dimension of the information spread plays an important role in characterizing users' retweets and identifying influential as well [START_REF] Lee | Finding influentials based on the temporal order of information adoption in twitter[END_REF][START_REF] Yang | Patterns of temporal variation in online media[END_REF]. Eventually, we have to mention that in dynamic interactions, social cascades have also been used to reveal that, different from static properties, the user's geographic locality is a key factor to characterize the way how the information circulates in the network [START_REF] Scellato | Track globally, deliver locally: Improving content delivery networks by tracking geographic social cascades[END_REF].

In summary, retrieving information from social media sites represented always a challenge given its volume, inconsistent writing and noise. Most existing systems focus on term-based approach, but retrieving the relevant information is often neglected, leading to less satisfactory results while searching information.

Conversations Extraction Approach on Big Twitter Data

In recent years, conversations generated by Big Data environments (Twitter, Facebook, blogs, etc.) have flooded the web. Big Social Data have transformed the scale of exploratory analysis on the web and offered new means of performing tasks that were not feasible before. This highlighted how Big Data research has become central to this growth of knowledge. Conversations have become an essential feature of contents generated by most social media platforms. Particularly, on Twitter, many users post tweets freely in order to express what they are thinking about any event, topic, followed by some comments, retweet or favorite. People uses conversations to express their interests, feelings, and experiences about virtually any topic. Thus, the users' interactions essentially reflect the importance of different topics and can be used to improve the conversation retrieval task quality.

In this paper, we explore the Big Data environment to propose an information retrieval approach for microblogging sites. Particularly, we focused on Twitter based conversation retrieval task (figure 1). Our approach combines direct and indirect conversation aspects in order to extract extensive posts beyond conventional conversation. In addition, we defined a conversation as a set of short text messages posted by a user at specific timestamp on the same topic. These messages can be directly replied to other users by using "@username" or indirectly by liking, retweeting, commenting and other possible interactions.

For this purpose, we opted for a Big Data solution. Due to the huge amount of data, structure diversity and specially the task complexity, a Big Data solution can provide best performance and efficiency. Thus, MapReduce is presented as one of the most efficient Big Data solutions. The MapReduce programming model has been successfully used for many different purposes. Hence, the remedy of the user defined function, which is one of the main strength feature of the MapReduce model. While conducting our exploratory detection and analysis of the tweeter's conversation, we came across large conversations' features. Our approach is bases on the direct and indirect conversations and consist in 2 steps:

-Step 1: Constructing the direct reply tree using all tweets in reply directly to other tweets.

-Step 2: Detecting the relevant tweets related indirectly to a same reply tree which might be retweets, comments or other possible interactions in order to extract extensive posts beyond conventional conversation.

Twitter Conversations Construction Using MapReduce

In this phase, we aim to collect all tweets in reply directly to other tweets. Obviously, a reply to a user will always begin with "@username". Our goal in this step is to create reply tree. The reply tree construction process consists of two algorithms: recursive root finder and iterative search algorithm.

For this purpose, we implement the two MapReduce phases: The map phase is implemented with a recursive algorithm to find T0 the root (first tweet published) of the conversation and H0 the hashtag used in the selected conversation. Thus, while the type of a given tweet is a reply or a retweet, the recursive algorithm boots until identifying the root. The iterative algorithm runs in parallel to seek the reminder of the conversation and extracting the used hashtag. The established conversations and the used hashtags, will be the input of the reduce phase of the MapReduce process. The goal of this phase is to classify conversations based on identical hashtags, using a grouping conversations algorithm.

Indirect Reply Structure Using Conversational Features

To the best of our knowledge, there has not been previous work on the structure of reply-based on indirectly conversation. In this step, we also used the MapReduce model to enrich conversations established during the first step. The goal of this step is to extract tweets that may be relevant to the conversation without the use of the @symbol. The conversations classification based on hashtags will facilitate the selection of the candidate tweets for each conversations cluster. Therefore, we define new features that may help to detect tweets related indirectly to a same conversation. The features are used during the MapReduce process. The Map phase is designed to calculate a score for each tweet relative to each conversation. The conversations are the output of the first step of our proposed approach. The features we used are:

-URLs-based selection:

Twitter allows users to include URLs as supplement information to their tweets. URLs that are contained in tweets can be considered as indicators for news related tweets. By sharing an URLs, an author would enrichment the information published in his tweet. In particular, if a tweet contains a URL that points to an external news resource, there is a very high possibility that this tweet is closely related to the linked resource. This feature is applied to collect tweets that share the same URL.

-Hashtag-based selection:

The # symbol, called hashtag, is used to mark a topic in a tweet or to follow conversation. Hashtag is meant to be identifier for conversations that rotate around the same topic. By including hashtag in a message(tweet), users indicate to which conversations their message is related to. We used this feature to collect tweets that share the same hashtags.

-Time Difference and Publication dates:

The time difference is highly important feature for detecting tweets linked indirectly to the conversation. We use the time attribute to efficiently remove tweets having a large distance in terms of time compared to conversation root. Date attribute are highly important for detecting conversations. Users tend to post tweets about conversational topic within a short time period. The euclidean distance has been used to calculate how similar two posts publication dates are.

-Content-based Similarity :

The criterion content refers to the thematic relevance traditionally calculated by IR systems standards. We compute the textual similarity between each element in t i , t j taking the maximum value as the similarity measure between two messages. The similarity between two elements is calculated using the well-known tf-idf cosine similarity, sim(t i , t j ).

After calculating the tweets' scores, a tweet sort relative to each conversation will be established during the reduce phase. Then, for each conversation, we suggest to select the five ranked tweet. The final output will be a conversation set, with an identified root for each one, and enriched by five extra tweets.

Experimentations and Results

The following experiment has been designed to gather some knowledge on the impact of our results on end-users. For this experiment, we have selected three events and queried our dataset using Google, Twitter search engine and our approach. Then, we have asked a set of assessors to rate the top-10 results of every search task, to compare these approaches.

Evaluation Metrics

In order to measure the results quality, we use the Normalized Discounted Cumulative Gain (NDCG) at 10 for all the judged events. In addition, we used a second metric which is the Precision at top 10. In the following, we first describe the experimental setting, then we present the results and we provide an interpretation of the data.

Experimental Settings

The dataset has been obtained by monitoring microblogging system Twitter posts over the period of March-May 2015. In particular, we used a sample of about 313 000 posts consisted of 1TB of data containing trending topic keywords using Twitter's streaming API. Trending topics (the most famous topic on twitter) have been determined directly by Twitter, and we have selected the most frequent ones during the monitoring period. To evaluate our search tasks' results, we have used a set of 100 assessors with three relevance levels, namely highly relevant (value equal to 2), relevant (value equal to 1) or irrelevant (value equal to 0). Every user was informed of three events happened during the sampling period. For each event we performed three searches using: 1. Google. 2. Twitter Search. 3. Our approach.

The evaluators were not aware from which system the results were retrieved. Every user for each search task was presented with three conversations selections, one for each of the previous options with the corresponding top-10 results.

Results Interpretation

We compare our conversation retrieval approach with the results returned by Google and by Twitter search engine using two metrics namely the P@10 and the NDCG@10. From this comparison, we obtained the values presented in figure 2 and figure 3 where we notice that our approach overcomes the results given by both of Google and Twitter.

The reason of these promising values is the fact that we combine a set of social conversational features and big data environment characteristics to retrieve conversation may have a significant impact on the users' evaluation. Focusing on the three messages selections, we observe that all conversations obtained with our approach receive higher scores with compared to Google and Twitter's selection. According to the free comments of some users and following the analysis of the posts in the three selections we can see that Google and twitter received lower scores not because they contained posts judged as less interesting, but because some posts were considered not relevant with regard to the searched topic. Concentration on the three messages selections we observe that all conversations selections obtained with twitter search has higher scores with respect to Google's selection. These results lead us toward a more general interpretation of the collected data. It appears that the social metrics usage have a significant impact on the users' degree interest in the retrieved posts. In addition, the retrieving conversations process from Social Network differs from traditional Web information retrieval; it involves human communication aspects, like the degree interest in the conversation explicitly or implicitly expressed by the interacting people.

Conclusion

Only Big Data applications can enable users to manage social conversations. In addition, Big Data is usually associated to having volume, velocity, variety, variability and complexity which are also features of Social Media Analytics. That is why social media should be explored to make sense of what all the available data means to satisfy users' information needs. This work proposed a new approach to retrieve conversation on microblogging sites that combine Big Data environment and social media analytics solutions. Our experimental results have highlighted many interesting points. First, combining social media features and the concept of direct conversation on Big data environment improves the relevance and informativeness of information search task and also provides results that are considered more satisfaction with respect to

Fig. 1 .

 1 Fig. 1. Exploring Big Data environment for Twitter conversations extraction approach

Fig. 2 .

 2 Fig.2. P@10 Average scores of human evaluation for each approach.

Fig. 3 .

 3 Fig. 3. NDCG Average scores of human evaluation for each approach.

http://www.forbes.com/sites/louiscolumbus/2015/05/25/roundup-of-analytics-big-data-businessintelligence-forecasts-and-market-estimates-2015/

a traditional information retrieval approach. Future work will further research the conversational aspects by including human communication aspects, like the degree of interest in the conversation and their influence/popularity by gathering data from multiple sources from Social Networks.