Anne-Caroline Genix
email: anne-caroline.genix@umontpellier.fr

Julian Oberdisse

Determination of the local density of polydisperse nanoparticle assemblies

Quantitative characterization of the average structure of dense nanoparticle assemblies and aggregates is a common problem in nanoscience. Small-angle scattering is a suitable technique, but it is usually limited to not too big assemblies due to the limited experimental range, low concentrations to avoid interactions, and monodispersity to keep calculations tractable. In the present paper, a straightforward analysis of the generally available scattered intensityeven for large assemblies, at high concentrationsis detailed, providing information on the local volume fraction of polydisperse particles with hard sphere interactions. It is based on the identical local structure of infinite homogeneous nanoparticle assemblies and their subsets forming finite-sized clusters. The approach is extended to polydispersity, using Monte-Carlo simulations of hard and moderately sticky hard spheres.

As a result, a simple relationship between the observed structure factor minimumtermed the correlation holeand the local volume fraction  on the scale of neighboring particles is proposed and validated through independent aggregate simulations. The relationship shall be useful as an efficient tool for the structural analysis of arbitrary aggregated colloidal systems.

Introduction

Nanoparticle (NP) assemblies are formed under many different circumstances, for instance in suspensions due to lack of colloidal stability 1 , in polymer matrices 2,3 , or upon drying of suspensions 4 . Some of these NP assemblies have important industrial applications, like e.g. reinforcing filler aggregates in car tires, 5 or the formation of porous membrane structures from NPs for electrocatalytical applications 6 . Knowing details of such structures allows understanding of transport properties related to connectivity, like conductivity 7 , or mechanical reinforcement associated with force transmission [START_REF] Klüppel | Filler-Reinforced Elastomers/Sanning Force Microscopy[END_REF] . Other studies pursue fundamental goals, like understanding the influence of physico-chemical properties of the environment on interparticle interactions governing NP assemblies.

Such interactions may be temperature-dependent, as in hybrid functional polymer-NP systems aiming at a control of optical properties via aggregation, [START_REF] Jones | [END_REF] or dominated by biologically relevant ions in systems mimicking NP assembly in cells 10 . Particular interactions may lead to specific aggregates, like the formation of NP chains which has been related to the combined presence of hydrogen bonding and dipolar interactions. 11 In polymer-composites, the effect of the polymer-mediated interactions, in particular via polymer grafts, on final aggregate structure has been investigated. 12,13 On the other extreme, the dynamics of polymer surrounding well-dispersed NPs due to favorable polymer-particle interactions have attracted considerable interest. [14][15][16] The structure of such assemblies is usually studied by electron microscopy 6,11,17,18 , or alternatively by scattering techniques 19,20 , in particular small-angle scattering suitable for NPs. Direct imaging techniques are attractive as they produce results which can be intuitively understood; unfortunately, they often suffer from limited representativity due to lack of statistics. Moreover, both sample preparationlike slicing for transmission electron microscopy (TEM)and artefacts like particle superposition leading to miscounts may alter the results, even if impressive progress has been made with tomographic methods 21 . Note that some groups use the complementarity of scattering and electron microscopy to overcome the shortcomings of both methods. 13,[22][23][24] On the other hand, scattering techniques are quite outstanding as they provide average information on three dimensional NP arrangements on the nanoscale. Well-dispersed NPs in solutions or polymer matrices have been analyzed by SAXS. 13,25 When NPs assemble, the low-q intensity increases due to the growth of the zones containing NPs with correlated positions. 19 This low-q upturn may follow a power law 26 , and then a fractal dimension can be extracted from the data with a power law fit, or literature expressions [26][27][28][29] . In some cases, in particular for small aggregates with scattering entering the experimentally accessible q-range completely, average aggregation numbers and radii of gyration can be determined directly. In this context, the unified law by Beaucage 27,30 has been applied successfully, also for multi-level structures [START_REF] Beaucage | Hybrid Organic-Inorganic Composites[END_REF][START_REF] Beaucage | Polymer Science: A Comprehensive Reference[END_REF] . Note that this is usually not possible for bigger assemblies, or interacting aggregates. In the case of sufficiently monodisperse NPs, crystallization leads to the emergence of well-defined scattering peaks allowing the resolution of both local orderand thus distances and densities-, and average crystallite size [START_REF] Langford | [END_REF] . Most NPs, however, are polydisperse in particle size (and sometimes shape, here we focus on spherical shapes), 34 polydispersity being typically in the range of 5 to 40%, depending on the synthesis protocol and the particle size. In practice, this leads to a large number of partial structure factors, which can sometimes be reduced by regrouping them (binning), but which are not easily measured independently, e.g., using deuteration or fluorination 35,36 . In general, an experimental (sometimes called 'apparent') structure factor representing a weighted average of all partial structure factors is thus measured.

Since the pioneering calculations of D'Aguanno et al 37 , it is well known that polydispersity makes the experimental structure factor peaks shrink until they possibly disappear completely. It is thus difficult to extract structural information from such low intensity signals. On the contrary, the depression of the structure factor at wave vectors just below the NP-NP interaction peak (or whatever remains of it) is a strong signature of the repulsive interactions between NPs. We call this low-q depression the correlation hole 38 , in analogy with the excluded volume correlation hole in the direct-space pair correlation function, g(r). In particular, as already shown by D'Aguanno 37 , polydispersity induces an increase of the low-q intensity. Rather involved theoretical integral-equation approaches based on solutions of the Ornstein-Zernike equation for polydisperse hard spheres (HS) and sticky hard spheres have been used, see also refs. [39][40][41][42][43][44][45][46] A similar method will be used as cross check in this article. [39][40][41] In the most complex cases, including both stickiness and polydispersity, equations have to be solved numerically 42 . Available analytical results will be used as a reference for our simulations, which are preferred here due to the homogeneity of a single-method approach, possibly uncontrolled analytical approximations as shown later in the text, a higher degree of freedom in the choice of the interactions, the availability of real-space representations, and the simplicity of the final formula proposed by us and applicable to scattering of any aggregate or particle assembly.

We have recently recognized the depth of the correlation hole as an experimental observable to follow the structure of filler aggregates in industrial 17,22,47 and model nanocomposites 23,48 . In the present article, we have chosen a simulation approach to provide a universal tool for a large range of experiments: first, (log-normal) polydisperse hard sphere particles are created, and both "infinite" and finite NP assemblies representing aggregates of known particle density generated. Then, all partial interaction terms are summed, and the experimental structure factor is determined. The correlation hole at scattering wave vector q = 0 for "infinite" assemblies, and at finite q for aggregates is then mapped onto the local density. Finally, this mapping is explicitly shown to allow the determination of the local particle volume fraction in independently generated aggregates without further numerical work.

Simulation method and scattering analysis

Simulation details: configurations of systems of polydisperse spherical particles with hard sphere interactions are explored by randomly placing N = 8000 particles in a cubic simulation box of dimension Lbox, with periodic boundary conditions, followed by an equilibration procedure of random displacements. The absence of finite-size effects has been checked and an example is shown in the ESI. The particles obey a log-normal size distribution function with parameters R0 and σ, see 49 , the latter polydispersity parameter being varied between 0 and 45% in this article, while R0 is arbitrarily fixed to 10 nm in order to obtain scattering functions directly in the wave vector range usually probed by small-angle scattering from experimental NP systems. The only remaining parameter is the global volume fraction κ of the system defined by the ratio of total NP and box volume. For homogeneous systems, the global volume fraction is identical to the average local one (also termed 'compacity' in previous work) associated with the environment of individual particles on the scale of nearest neighbors, where the average is performed over all particles. The determination of κ from the scattering function is the objective of this article. In practice, high volume fractions are created by starting with smaller particle sizes giving lower volume fractions, and increasing the particle sizes progressively to their nominal values, during equilibration. Note that we work at a fixed number of particles, which implies that the box size Lbox decreases for higher volume fractions. This is reflected by changes in qmin = 2π/Lbox. After equilibration, structure factors (see below) representative of "infinite" systems are determined as averages over different configurations of the entire box, generating typically 50-100 independent systems, each being first equilibrated, and then 100 statistically independent structure factors are calculated by letting the system evolve in timetypically 100 steps per particle between each S(q). By performing multiple calculations, we have checked that the accuracy of this averaging procedure for S(q) is of the order of 1%. For finite-sized aggregates of know density (identical to the global one), an equivalent number of spherical subsets of Nagg particles is cut out of the central region of the equilibrated and evolving systems.

The study of local correlations between moderately sticky hard spheres at a fixed global volume fraction κ was done following a geometrical rather than thermodynamic approach of Baxter 50 or Gazzillo 42,43 , in order to maintain system homogeneity. Simulations are restrained to moderate stickiness because our mapping procedure is based on the equality of global and local volume fractions, which is only true for systems which are not destabilized by attractive interactions yielding phase separation. NP configurations (N = 8000) in a simulation box were first generated and equilibrated with only hard sphere interactions, as before. Then, spheres were made sticky, and each particle continues moving until hitting another one, i.e., a center-to-center distance equal to the sum of the radii. These two particles form a (heavier) group, which was considered immobile in order to avoid the collapse of the system and thus preserve homogeneity. Such groups conserve stickiness and can grow further via subsequent collisions with free particles. The procedure was repeated until a majority of 80% of all NPs was stuck onto others, leaving thus a small part individually dispersed.

Determination of small-angle scattering: Structure factors are calculated differently for the entire simulation box representing an "infinite" system, and finite subsets. By treating the entire simulation box as the unit cell of an infinite cubic lattice, finite-size effects are avoided: the structure factor of the "infinite" system can be calculated at the reciprocal lattice points of the box, i.e., at certain q-values qp defined below, and in certain directions compatible with the cubic lattice: [51][START_REF] Pedersen | Neutrons, X-ray and Light Scattering[END_REF][START_REF] Pedersen | [END_REF][54][55]

𝑆 𝑚𝑜𝑛𝑜 (𝑞 𝑝 ) = |∑ exp [-𝑖𝑝2𝜋 ℎ𝑥 𝑗 +𝑘𝑦 𝑗 +𝑙𝑧 𝑗 𝐿 𝑏𝑜𝑥 ] 𝑁 𝑗=1 | 2 (1)
where the N (monodisperse) particles are located at positions (xj,yj,zj), and the norm of the scattering vector is given by qp = 𝑝 2𝜋 √ℎ 2 +𝑘 2 +𝑙 2 𝐿 𝑏𝑜𝑥

, with p = 1, 2, 3… . In practice, thirteen directions provide a good average, chosen as Miller indices 100, 110, and 111, and their respective equivalents. This leads to three series of qp, obtained by multiplication of the first one with √2 and √3, which can then be unified in a single function. For polydisperse systems, each particle j is described by the Fourier transform of its scattering length density Δρ, which is called the form factor amplitude. Its prefactors are Δρ and the particle volume Vj, and the function normalized to 1 at low q is termed Fj(q). The square of the non-normalized function (including the volume Vj) is commonly called the form factor Pj(q), and it can be averaged over all particles, giving 𝑃 ̅ (𝑞) . It is straightforward to include polydispersity in the above formalism, eqn (1), by weighting the exponential by the form factor:

𝐼(𝑞 𝑝 ) = |∑ ∆ρ F j (q p )V j exp [-𝑖𝑝2𝜋

where the experimental structure factor S(qp) with its apparent isothermal compressibility is obtained by dividing by the average form factor 𝑃 ̅ (𝑞) in eqn (2b), as done for finite assemblies below.

Configurational averages are then performed on S(qp), simply written S(q) in what follows.

For finite-size assemblies of Nagg monodisperse particles, the structure factor can be calculated more efficiently using directly the isotropic average. For identical spherically symmetric nanoparticles, S(q)

is the Fourier transform of the pair-correlation function of the center-of-mass positions of NPs. Using the Debye formula 56 , it reads:

S(q) = 1 + 2 𝑁 ∑ sin (q(r j -r i )) q(r j -r I ) N i>𝑗 = 1 + 2 𝑁 ∑ S ij (q) N i>𝑗 (3)
where (ri -rj) represents the distance between the centers-of-mass of NPs i and j, and the sinus term is regrouped in Sij expressing the phase difference of waves scattered by particles i and j, its thermodynamic average over all particles of the same sizes being the partial structure factor. The lowq upturn of S(q) contains valuable information on the number of particles, and the spatial extent of the NP assembly. At large q, the interparticle correlation peak is usually found, and just below this qvalue, the correlation hole. As with eqn (2b), the isotropically averaged intensity, i.e., the differential scattering cross section per unit sample volume I(q) can be calculated by the product of the monodisperse NP form factor, P(q) = Δρ 2 V 2 F 2 (q), and the interparticle structure factor, S(q). [START_REF] Pedersen | Neutrons, X-ray and Light Scattering[END_REF] Adding polydispersity in size for the spherical NPs requires to weight properly each contribution to the structure factor Sij by its form factor amplitude Fj(q). The total scattered intensity is given by a weighted average 22 , and one can again calculate the experimental structure factor by dividing by the average form factor:

           i 2 i 2 i j i, ij j i j i q F V q S q F q F V V S(q) (4)
Analysis of small-angle scattering and mapping procedure: It is proposed to extract the local particle volume fraction κ through the following simple mapping procedure. First, the local volume fraction κ experienced by particles in an aggregate (or any other assembly) is determined by comparing its correlation hole structure factor to the low-q limit of S(q) of a "infinite" homogeneous HS fluid of known κ. A straightforward development of the PY equation at low q 57-59 or equivalently the Carnahan-Starling equation [START_REF] Carnahan | [END_REF] gives the following limit for monodisperse particles setting α to one:

    2 4 PY κ α 2 1 κ α - 1 = 0) (q S   (5)
This limit is associated with the isothermal compressibility of the nanoparticle assembly. In eqn (5),

we have introduced the empirical parameter α to allow a generalization to the description of polydisperse spheres, to be given in the results section. As a reference, we use the calculation by Vrij 46 for log-normal polydisperse HS. Using our symbols, it reads:

                          2 2 2 2 2 P olyHS 3σ exp 2κ 1 9κ 2σ exp 2κ 1 6κ 1 κ 1 σ κ, S (6)
In a second time, finite spherical assemblies of spheres are cut out of the homogeneous HS fluid. By construction, they have the same κ as the original system, a feature which is difficult to achieve with arbitrary aggregates or assemblies. Note that such spherical subsets have the lowest surface area, limiting thereby modifications of the signal by particles sitting close to the surface, and thus experiencing locally lower densities. Using eqn (4), the structure factor now resembles finite-sized aggregates: it displays a low-q upturn, and a correlation hole, which can then be mapped onto an experimental one to determine the corresponding average density.

Results

The reference case of "Infinite" NP assemblies: We have undertaken numerical simulations of hard sphere NP assemblies in order to check the influence of concentration and polydispersity. The structure factor is calculated using eqn (1) and its generalization to polydispersity with eqns (2), and results are shown in Fig. 1. For monodisperse systems, one may note that it is numerically more efficient to Fourier transform the pair correlation function. As one can see in the inset of Fig. 1a, the result for monodisperse hard spheres is indistinguishable from the Percus-Yevick (PY) result 57 , down to low q, in spite of the finite box size, for volume fractions ranging from 10 to 30%. Important features of S(q) of infinite assemblies of monodisperse spheres are (i) the low-q limit S(q→0)

describing the isothermal compressibility, (ii) the high-q limit of one, and (iii) the position of the NP-NP correlation peak around π/R, R being the NP radius. Note that the first point (i) expressing a relationship between concentration and low-q scattering is the basis of the method proposed here. In Fig. 1 (a) Log-log plot of the structure factor S(q) as a function of wave vector q for an "infinite" HS ensemble (R0 = 10 nm, volume fraction 20%v), with polydispersity σ ranging from 0 to 45% as given in the legend. Inset: comparison of simulated structure factor for monodisperse (σ = 0) hard spheres with their analytical counterpart (lines, see text for details), for κ = 10, 20, and 30%. (b) Low-q limit S(q→0) as a function of polydispersity σ at different volume fractions к, compared to calculations by Vrij 46 and numerical solutions of Ornstein-Zernike (OZ) 39,40 , see text for details. Solid lines are linear fits of common slope.

The structure factors in Fig. 1a at fixed volume fraction of к = 20% highlight the following features:

first, the structure factor peak around 0.03 Å -1 is clearly due to NP correlations in contact, as qpeak ≈ π/R. Secondly, the correlation hole is well defined even when the peak vanishes. The low-q values S(q→0) are seen to increase with increasing polydispersity at low q, with consequences extending also towards the intermediate q-range. It is thus important to know the particle polydispersity if one wishes to determine aggregate densities from the low-q depression.

In Fig. 1b, we have regrouped all our results for S(q→0) of "infinite" HS assemblies. As observed in Fig. 1a, S(q→0) increases with polydispersity, and this increase is found to be linear, with a slope independent of κ. Naturally, the low-q limit decreases with the density к, as illustrated in the inset of Fig. 1. The comparison with the reference calculation by Vrij, eqn (6), 46 is also shown in Fig. 1b. It illustrates two points: First, our simulations agree nicely with the predictions by Vrij for low and moderate polydispersities. Above some 30%, however, the Vrij-function shows an upward curvature.

While there is no a priori reason why our simulation code should break down for higher polydispersities, in particular at low concentrations, we compared both predictions to an independent calculation based on the simultaneous numerical solution of Ornstein-Zernike integral equations for quasi-continuous size distribution. [39][40][41] The perfect superposition with our simulation results suggests that the latter are trustworthy, while some necessary approximations in the analytical model 46 induce the observed deviations at high polydispersities.

In order to finalize this part on the low-q scattering of HS assemblies, one can analyze vertical cuts in Fig. 1b, for each polydispersity. Examples for monodisperse and polydisperse (σ = 15% and 30%) HS particles are shown in Fig. 2. The fits were made using eqn (5), with the α∞-parameters for these "infinite" systems given in the caption. The quality of the fits is very good. For monodisperse particles, the original Percus-Yevick result (α∞ = 1) is found; then α∞ decreases with polydispersity, which corresponds to the increase in S(q→0) described in Fig. 1a.



Infinite systems

Fig. 2 Low-q structure factor S(q→0) of "infinite" system as a function of volume fraction based on simulations of hard spheres (polydispersity σ = 0, 15%, 30%). Solid lines are fits using eqn (4) with α∞ = 1 (PY), 0.95, and 0.87, for σ = 0, 15, and 30%, respectively.

The description given in Fig. 2 can be performed for all polydispersities, and the result for α is well described by a parabolic function (shown later in the text):

α∞(σ) = 1 -1.13 σ 2 (7)
It is thus possible to predict the outcome S(q→0) of our simulations for any particle polydispersity (below 45%) using eqns ( 5) and (7), and determine к of any NP assembly by comparing to the corresponding correlation hole data. The parabolic shape is related to the observation in Fig. 2 showing that at first, with low polydispersity (σ from 0 to 15%), there is only little change. At higher σ, however, polydispersity becomes important.

One can also conclude on the accuracy of this к-determination, in particular if the polydispersity is not exactly known. For an experimentally measured S(q→0) of 0.2, the uncertainty in volume fraction к is typically from 22±1.5%, if the polydispersity ranges between 0 and 30%; even for S(q→0) = 0.1, the range in kappa is still rather reduced, 31.5±2.5%. This seems an acceptable error given the simplicity of the method. Interestingly, the shape of the curves in Fig. 3 makes the relative range of κ approximately constant, ca. 15%. One may thus conclude that the determination of the local density of the NPs arrangements is rather robust.

Two additional points may deserve discussion. First, while the decrease in S(q→0) observed in Fig. 2 is clearly related to the increase in local density, it is unclear how this translates to finite-sized aggregates. Secondly, real aggregates are formed by attractive interactions, and it is unclear how these affect the local correlations. Both points are addressed in the next sections.

Finite-sized NP assemblies of known density: Spherical assemblies of hard spheres of known average density κ have been generated by equilibrating an "infinite" HS system with periodic boundary conditions, and cutting out a spherical domain in the center of the simulation box, of radius such that the number of selected spheres equals Nagg. This is illustrated in Fig. 3. For practical reasons, it is sufficient to equilibrate HS assemblies with less than N = 8000 particles; most of what follows has been run with N = 2000, and Nagg = 200 central particles were selected. The advantage of this method is that the local density of the spherical aggregate equals the nominal one of the cubic simulation box.

Note that it is sufficient to study individual spherical aggregates, as our analysis will be focused on intermediate-q vectors, which will be unaffected by interactions between aggregates at higher concentrations. Statistical averages are achieved as before, by letting the entire simulation box equilibrate and evolve before calculating structure factors. The structure factors are calculated using eqn (4), and examples are shown in Fig. 3 for two different densities. Their low-q value is essentially given by Nagg, with a small correction due to particle polydispersity, exp(-9σ 2 ), calculated using eqn (4). The low-q decrease is first due to a Guinier regime of finite-sized objects, and one sees that the assembly with higher concentration is smaller (Nagg being fixed), and decreases thus less rapidly. Due to the rather accurate definition of the spherical surface by the particles as illustrated in the inset, the symmetry of the object is high, and the spherical form-factor oscillations around q = 0.005 Å -1 are thus quite pronounced. At high q, finally, an interparticle correlation peak is reached, with a position which is further to the right for the denser system, as expected. In between the form factor oscillations and the correlation peak, the structure factor is depressed. The depth of this correlation hole decreases with the density, offering us the possibility to map its depth on the density, as done with infinite particle assemblies in the previous section. Its position extends over a limited q-range, but it is difficult to locate it exactly due to the multiple maxima and minima. We have drawn a continuous black line as guide to the eye describing the average shape of the correlation hole in Fig. 3. A good compromise for the position of its minimum between the vanishing low-q oscillations and the increase to the correlation peak appears to be the second local minimum starting from low-q, at q0, and of value S0. By performing calculations with different geometries (sphere, cubes, short cylinders, see ESI), we have checked that S0 given by this second local minimum is robust. While the exact value of S0 is affected by the geometry, it is mainly controlled by the local particle density, and it will be shown below that the choice of the sphere allows determining the density of aggregates of arbitrary shapes. Comparisons to fuzzy aggregate structures in the discussion will show the suitability of this estimation.

The next step is to generalize the example given in Fig. 3, and determine the structure factor at the correlation hole, S0, as a function of κ, for different polydispersities, in analogy with Fig. 1 for "infinite" systems. In Fig. 4a, S0 is plotted for volume fractions from 5 to 40%, for the moment at fixed NP polydispersity of 0, 15% and 30%. One immediately sees that these functions are well above the PY limit of infinite fluids, which demonstrates that the correlation hole of the "infinite" system only gives a first approximation for the one of finite-sized aggregates or assemblies. Note that our data are perfectly reproducible: to illustrate this, the κ = 12.5% (σ = 30%) concentration has been run twice, and the two points overlap in Fig. 4a. As in Fig. 2, the influence of polydispersity is to increase S0, at first moderately, and quite markedly for σ = 30%. The fits with eqn (5) are superimposed to the data points in Fig. 4a. The quality of the fit is acceptable, with deviations showing up high concentrations, above 30%. The corresponding α-values (termed αfinite) are reported in the caption. These values are lower than the ones for "infinite" systems, translating the fact that the S0-values are higher than the S(q→0) of the latter. Fig. 4 (a) Low-q structure factor S0 of finite (spherical) system as a function of volume fraction к based on simulations of hard spheres (polydispersity σ = 0, 15, 30%). Solid lines are fits using eqn ( 5) with αfinite = 0.73, 0.69, and 0.57, for σ = 0, 15, and 30%, respectively. The black line is the (infinite) PY prediction. (b) S0 as a function of σ for κ = 10, 20, and 30% (finite systems), respectively. Dotted lines are linear fits of common slope.

The plot of S0 as a function of polydispersity (for different κ) is shown in Fig. 4b. As in Fig. 1b, the functional dependence on σ is found to be linear, with a slope independent of κ. However, the slope is higher than for the "infinite" system. We think that this is related to the different q-range under scrutiny: for infinite systems, we focus on q→0, whereas the finite ones have a correlation hole at finite q. Unlike at very low q, the structure factor in the latter range is more strongly affected by changes in local correlation, as we will see in the discussion section below. By fitting eqn (5) at fixed σ, the αfinite-parameters can be determined, and the result is plotted in Fig. 5a. Moreover, these data are compared to those of "infinite" systems described by eqn (7) in the same figure. Fig. 5 (a) Evolution of fitted αfinite-parameter, as a function of polydispersity σ, for both "infinite" and finite systems. The lines are fits as given in eqns (7,8). (b) Left axis: correlation hole S0 of κ = 20% ( = 15%) spherical subsets as a function of Nagg of subset. The infinite limit for S0 is also shown (broken line). Right: κ deduced from S0, compared to dotted horizontal lines illustrating ±15% error.

αfinite is also a decreasing parabolic function, with a remarkably similar curvature, but shifted vertically to lower α. The result for αfinite(σ) reads:

αfinite(σ) = 0.72 -1.45 σ 2 (8)
With eqn (8), it is possible to determine α for finite HS systems with any log-normal polydispersity σ between 0 and ca. 45%, and then employ eqn (5) to extract the local compacity κ from the experimental scattering data without further numerical work. The combination of eqns ( 5) and ( 8) thus represents the main result of this article. One may note that the values reported in Fig. 5a deviate from our results for HS-systems used in a preliminary calculation, 22 but remain remarkably close (α = 0.72 for σ = 15%), due to a compensation of two effects, the removal of the finite-size box effect obtained using eqn (1), and generation of finite assemblies.

We have shown in Fig. 5a how the effect of local volume fraction on the experimental isothermal compressibility of "infinite" systems S(q→0) translates into an effect on the correlation hole S0 located at finite q-values for finite-sized aggregates characterized by a number of particles Nagg.

Naturally, the choice of Nagg may be questioned. We have performed simulations with Nagg ranging from 25 to 1000 (adapting N for big assemblies, see ESI), and found that the representative depth of the correlation hole as taken at the 2 nd S(q) minimum is robust. The result for κ = 20% (σ = 15%) is shown in Fig. 5b, where S0 is plotted as a function of Nagg. S0 is seen to tend to a plateau for large Nagg, whereas at low Nagg the spherical subsets are so small that they have a comparatively high surface area. Particles located at this surface have neighbors only on one side, thereby decreasing the effective local volume fraction. This induces an increase of S0 towards one. The plateau value indicates also that polydispersity in aggregate size would lead to an average lying on the same level. One can now calculate the κ one would obtain from this S0, using eqns ( 5) and ( 8), and its value is superimposed to the plot. The nominal κ of 20% is found for aggregates having Nagg ≥ 100, within a ±15% error interval illustrated by dotted lines. Finally, S(q→0) of the "infinite" calculation is also shown as a broken horizontal line. One would expect S0 to tend more quickly towards S(q→0), but one should keep in mind that even 1000 particles correspond to only 10 particles along one direction, and which is too small to separate the length scales. This illustrates again that necessity of describing finite-sized systems.

Up to here, we have worked only with assemblies of hard spheres, which might be incompatible with a description of local interactions in, e.g. aggregates made by attractive (sticky) interactions. Our initial working hypothesis was that at high enough concentrations, above a threshold to be defined, the local environment is so crowded that even in absence of stickiness, neighbors are necessarily very close. In the next section, we will first check the validity of this hypothesis by comparing HS to mildly sticky particles, and then evaluate the predictions of our mapping procedure for rigid aggregates as they may be formed by inorganic NPs.

Discussion

The local correlations between NPs depend obviously on their interactions. We have therefore changed the type of interactions from purely hard sphere to mildly attractive, in order to explore the consequences on the depth of the correlation hole. As our mapping procedure relies on the generation of spatially uniform assemblies of spheres being described by a single volume fraction κ, strongly attractive NP systems leading to local phase separations are not suitable here. We have therefore designed the numerical procedure outlined in section 2 in order to produce globally homogeneous systems with locally sticky HS interactions. In Fig. 6a, the experimental structure factors for polydisperse spheres (σ = 15%) of hard and sticky hard spheres are compared at κ = 20%. At the bottom, the S(q) of "infinite" systems are superimposed. As one turns on the sticky interaction, the NP interaction peak moves to the right, but the low-q limit remains essentially unchanged. We interpret this as the confirmation of the global homogeneity in spite of the stickiness. At intermediate q, however, the structure factor of sticky beads shows a slower descent from the peak to the low-q limit, i.e. a higher signal. Together with the peak shift, this is thus the of the stickiness as generated here. This is also the q-region where polydispersity affects local correlations more strongly, as discussed in section 3. For comparison with the finite NP assemblies, their S(q) are shifted vertically in Fig. 6a. They display exactly the same features, from HS to sticky: unchanged low-q behavior, a slight increase at intermediate q, and a shift of the correlation peak. By comparing the depth of the correlation hole, it can be concluded that the structure factor at q0 as defined in Fig. 3 is moderately increased due to stickiness. The structure factor at the correlation hole S0 is plotted as a function of κ in Fig. 6b, for finite systems, for both hard and sticky hard spheres with σ = 15%. The two curves deviate at low volume fractions.

The strong increase of the S0 of the sticky system is probably related to the generation of spatial heterogeneities caused by strong density fluctuations possible at low к. S0 then exceeds 1 as illustrated by the strongly increasing dotted line. At high enough densities, the structure factor S0 of the sticky system progressively approaches the HS one. This confirms our initial hypothesis that at high к, the interaction is dominated by the infinite hard sphere potential, and the system designed to be only moderately sticky is indeed preserved from large-scale heterogeneity. As in section 3, one can estimate the error made by using the HS formalism instead of stickiness by visual inspection of Fig. 6b, and a few percents error on κ are found as long as κ is high enough, say above some 10%. Alternatively, one could parametrize S0 of the sticky interactions, and would obtain estimations even in this low local density range.

Finally, the performance of the combination of eqns ( 5) and ( 8) must be evaluated, in particular for "real" aggregates composed of chemically bound particles, as encountered in typical experimental situations 18 . We therefore apply our mapping procedure to simulated aggregates made of polydisperse NPs mimicking real aggregates. This is a severe test of the hypothesis of dominant hard sphere interactions, as all NPs are glued together irreversibly, without any dynamics, whereas eqns (5,8) are based on simulations subsets of homogeneous hard sphere assemblies. Different construction algorithms based on ref. 18 have been developed in order to produce aggregates of different structure and density, and are outlined in the ESI. We start with the discussion of rather open aggregates. In Fig. 7a the intensity I(q) averaged over several hundred aggregates, the average NP form factor rescaled to the same contrast and concentration, and the average structure factor are plotted, together with a graphical representation of one aggregate (Nagg = 200, R0 = 10 nm, σ = 15%), which appears to be rather fuzzy. Note that there is no control of coordination numbers with this type of construction. S(q)

has the properties and the typical shape described above: a low-q upturn due to aggregation followed by a short, possibly fractal regime (df compatible with 1.5), a contribution below one (correlation hole at q0) due to NP repulsion in the intermediate-q range, and a peak related to the interparticle distance.

This peak is not very prominent due to polydispersity, whereas the correlation hole remains welldefined.

For comparison, the explicit calculation of the experimental structure factor of a finite hard sphere system of the same size distribution (R0 = 10 nm, σ = 15%) for к = 11.5% is also superimposed to the aggregate structure factor in Fig. 7a, where the choice of 11.5% is discussed below. Obviously, the shape is not the same, as it is spherical by definition of the subset, whereas the aggregate is fuzzy: the low-q domain thus differs. In the high-q range, the exact position of the structure factor peak is not reproduced either, as spheres move around some average distance in the hard sphere system, and are not stuck to each other as in the aggregate. Neither of these two features is relevant for the present discussion, which focuses on the average depth of the correlation hole, well reproduced in Fig. 7a. S(q) 0.54 a)

Fig. 7 (a) Example of average I(q), the average particle form factor   q P , and the resulting S(q) as a function of wave vector q of simulated aggregates of Nagg = 200 polydisperse NPs (R0 = 10 nm, σ = 15%). S(q) is compared to the simulated structure factor of a finite HS system at 11.5% (orange symbols, same parameters). In the inset, a 3D snapshot of one aggregate is shown (polydispersity is not graphically represented). (b) Determination of aggregate volume by discretizing on the scale of the first coordination shell.

The aim of the mapping procedure is to estimate the local volume fraction within the aggregate.

Reading off S0 = 0.54 from Fig. 7a, an average local volume fraction felt by the NPs in the aggregate of к = 11.5% is determined using αfinite(σ) = 0.72 -1.45 σ 2 = 0.69. For comparison, one may estimate the total volume fraction of aggregates like the one shown in Fig. 7a from their total particle volume and the global size given by the circumscribing sphere: one finds an average for κ of about 7.5%. Due to the presence of voids within the aggregate, this must be a lower bound for κ describing local interactions between particles, and a more appropriate method to estimate κ needs to be developed. As illustrated in Fig. 7b, the aggregate volume can be better estimated by discretizing the total volume into small cubes. One may then count the number of cubes being occupied by at least one particle, and estimate the corresponding compacity κagg from the ratio of the known particle volume, and the aggregate volume. The choice of the cube size is crucial, as one wishes to follow local density fluctuations on the scale of 1/q0. The position q0 of the correlation hole being closely related to the correlation peak of particles in contact, the first coordination shell is a suitable candidate for the cube size: it is chosen such that the cube contains the coordination shell, i.e. its linear size is 6R0, see Fig. 7b. Much bigger cubes would include local voids, whereas too small ones would simply identify the bare particle volume. With this choice of the cube size, an average of κagg = 15.7% is found from this geometrical description.

In order to check the general validity of our approach, it has then been applied to a series of more or less dense aggregates generated with different algorithms as outlined in the ESI. Contrarily to the aggregate shown in Fig. 7a, where any number of spheres can touch a given sphere as long as excluded volume is respected, new ensembles of aggregates have been created by varying the allowed number of direct neighbors in the simulation reaching different compacities. Three examples of such aggregates are shown in Fig. 8a, together with the structure factors that have been calculated as averages over hundreds of aggregates. The correlation hole is found to deepen as the geometrically determined compacity agg increases from ca. 18 to 22%. In parallel, the real-space images show that aggregates become less fuzzy and denser, which is also seen in reciprocal space, as the first maximum of the form factor oscillation of spherical aggregate shapes shows up around 0.007 Å -1 . As a result, the compacity κ of these aggregates extracted using eqns ( 5) and ( 8) evolves from 15.3% to 25.7%. The comparison between the compacities determined with the geometrical approach in real space based on cubes (κagg, Fig. 7b), and the one obtained from the correlation hole analysis (κ) is shown in Fig. 8b, for all aggregates generated for this study using the algorithms given in the ESI. This comparison validates our approach: it means that a local density, on the scale of the first coordination shell, is successfully estimated by the correlation hole of the structure factor. We have also extended our calculations to aggregates of different sizes (Nagg = 50 to 800, see ESI), and the results convincingly join the data points on Fig. 8b.

The work by Beaucage and in particular the unified scattering law 27,30 may be used to benchmark the predictions of our model as shown in Figure 8b. The particle density using, e.g., a two-level Beaucage fit can be determined using the ratio of prefactors (giving the aggregation number) together with the radius of gyration or of the equivalent sphere of the upper level. This approach needs more care in presence of particle polydipersity, which changes the ratio of the prefactors. By construction, this method gives the average density, as the radius of gyration does not account for the local density. In a semi-empirical approach, [START_REF] Beaucage | Hybrid Organic-Inorganic Composites[END_REF][START_REF] Beaucage | Polymer Science: A Comprehensive Reference[END_REF] Beaucage proposes to take correlations into account, with two parameters, a correlation length and a local density. In the ESI, we have applied a two-level model with and without correlations to our data in Figure 7a. While the purely fractal law does not describe the correlation hole, the correlation term with a local density of 15% approaches the experimental curve somewhat in the intermediate q-range. Note that alternative choices of up to 25% are possible.

We thus conclude that our method is compatible with the semi-empirical approach by Beaucage, and possibly more precise.

The comparisons shown in Fig. 8b indicate that our approach is robust for aggregates of different internal structure. Moreover, we have checked that different aggregate masses correspond to aggregates of different structure, each characterized by a different κ. One should not, however, claim exaggerated precision. From all the examples given in this article, an error bar of ±15% on κ seems acceptable. Last but not least, it is recalled that κ is an average quantity characterizing local interactions, not suitable for, e.g., describing the global density, e.g. of very big fractal aggregates, for which it decreases strongly with size. Along the same lines, too small and too 'linear' aggregates are probably not suited for the present analysis. One should also keep in mind that distributions of aggregation numbers, in particular coexistence of isolated nanoparticles, will be described by an average compacity. Averaging is based on the convex shape of eqn ( 5) and thus introduces a peculiar weighting, underestimating к. In any event, the exact value of the local density depends on the scale of observation, due to the intrinsically heterogeneous nature of aggregates. We have shown, however, that a trustworthy and useful estimate can be obtained easily from the scattered intensity.

Conclusion

We have shown in this article that the local volume fraction κ of spherical nanoparticles in dense assemblies or aggregates can be extracted in a robust and straightforward manner from a minimumthe correlation holein the experimentally observed small-angle scattering function, if the particle form factor is known. The simulations have been performed for "infinite" systems of known density first, with parameters given by eqn (7) already providing an acceptable estimate of κ. As finite systems are closer to the application of aggregates, the mapping procedure was further improved with finite subsets of the same density. The main result given by eqns ( 5) and ( 8) works in presence of polydispersity, and at any concentration of aggregates, because it is not based on the low-q intensities, but on a particular experimentally determined wave vector q0. In spite of its simplicity, our method has been shown to deliver trustworthy estimates even in the unfavorable (but common) case where the exact nature of the interactions between NPs is unclear, due to the dominant HS interactions, in particular at higher local densities.

We emphasize that the present simulations have been performed with log-normally distributed polydisperse hard spheres. Real particles may differ, with two consequences: first, due to adsorbed or grafted layers, or intrinsic non-uniform scattering densities, non-spherical shapes, or non log-normal distribution functions, the average scattering of the individual particles may be different. This would result in a different form factor, but as long as particles can be well described as spherically symmetric, the experimental form factor can still be used to extract the apparent structure factor described in this article. On the other hand, the interactions between particles will not be correctly described for strongly facetted NPs, violently polydisperse size distributions like strong bidispersity, or too thick adsorbed polymer layers with interactions impeding hard sphere repulsion. In practice, aggregates must be large enough that it makes sense to speak about their internal structure (typically Nagg > 100, see Figure 5b), and then the local density has been shown to be correctly determined between about 5 to 30%. The lower limit is probably a few percent given by the necessity of connectivity between particles, while we expect the upper limit to be even higher.

For the sake of completeness, it is noted that (possibly more involved) reverse Monte Carlo simulations of NP assemblies may give direct 3D information 61 . The advantage of such simulations is that they may describe entire intensity curves, and propose possible structures and correlation functions of 3D assemblies. However, they usually require additional knowledge like total aggregate masses, either from scattering down to low enough angles, or from other sources like microscopy.

Moreover, depending on density, such techniques may require simulations of very big systems and thus be time-demanding, whereas the mapping proposed here is a straightforward application of eqns (5,8). The same is true with alternative integral equation modeling, which furthermore necessitates knowledge of interaction potentials.

There are applications of the present mapping procedure to about any assembly made of nanoparticles, in any matrix, even micellar aggregates [62][63][64] or mineral particles 65 in water, with attractive interactions mediated by polymer chains. In experimental studies of colloidal gels, the correlation hole was found to be well-defined and unchanged during the gelation process, and could be used to describe the average local particle density. 66 Simulations of attractive particles provide a representative application of our mapping procedure. Del Gado et al. have investigated the structure of a colloidal gel at 5% nominal volume fraction. 67 Applying the infinite HS analysis (eqn ( 7)) to their high-temperature fluid structure factor leads to an average density of about 4%. At low temperature, the structure evolves towards a gel with a low-q upturn and a correlation hole, describable by a finite sub-set (eqn (8)). In this case, the local volume fraction is obtained to be 7%, illustrating the local densification due to sticky interactions. The correlation hole analysis appears thus to be a simple and suitable tool.

Moreover, it can also be used to quantify tendencies of к along variations of experimental or simulation parameters. Our personal perspective is to use it for the analysis of local NP aggregates structure in polymer nanocomposites, as applied by us previously on industrial 22 and model systems 18, 68 , however without detailed knowledge of the background and limits of the mapping procedure. In this context, high filler concentrations are usually of industrial interest, and our method works regardless of interactions between aggregates, as we focus on internal aggregate structure characterized by intermediate-q scattering.

Fig. 1a ,

 1a Fig. 1a, the simulated structure factors are plotted as a function of polydispersity σ for a volume fraction  of 20%, others are shown in the ESI.

Fig. 3

 3 Fig.3Structure factor S(q) of finite spherical HS systems, for two volume fractions, κ = 20 and 40% (σ = 15%). q0 represents the position of the correlation hole, the continuous black line illustrates its average shape. Inset: "Infinite" simulation box with equilibrated HS, and illustration of cutting out a finite spherical aggregate in the box center.

Fig. 6 (

 6 Fig. 6 (a) Comparison of sticky to hard sphere structure factor, for "infinite" and finite (multiplied by 2 for clarity) systems (κ = 20%, σ = 15%). (b) Comparison of sticky to hard sphere structure factor minimum S0 as a function of κ (σ = 15%).

Fig. 8 (

 8 Fig. 8 (a) Evolution of S(q) of aggregates (Nagg = 200, same spheres R0 = 10 nm,  = 15%) of various compacities. Snapshots are shown in the insets. (b) Comparison of geometrically determined local density кagg to к deduced from correlation hole analysis. Plain symbols: different construction algorithms with Nagg = 200, empty symbols: Nagg varying from 50 to 800 for a fixed algorithm (see details in ESI).

Acknowledgements:

The authors are thankful for support by the ANR NANODYN project, grant ANR-14-CE22-0001-01 of the French Agence Nationale de la Recherche. J.S. Pedersen (Aarhus) and L. Belloni (Saclay) are warmly thanked for illuminating discussions: in particular, the former for reminding us of the properties of eqn (1), and the second for providing us with a numerical tool implementing a solution of OZ integral equations, allowing the cross check of our results in Fig. 1b. Critical reading and suggestions by L. Cipelletti and W. Kob on a preliminary version are gratefully acknowledged.


Anne-Marie Vercoustre
email: anne-marie.vercoustre@inria.fr

Jovan Pehcevski
email: jovan.pehcevski@inria.fr

James A Thom
email: james.thom@rmit.edu.au

Using Wikipedia Categories and Links in Entity Ranking

This paper describes the participation of the INRIA group in the INEX 2007 XML entity ranking and ad hoc tracks. We developed a system for ranking Wikipedia entities in answer to a query. Our approach utilises the known categories, the link structure of Wikipedia, as well as the link co-occurrences with the examples (when provided) to improve the effectiveness of entity ranking. Our experiments on the training data set demonstrate that the use of categories and the link structure of Wikipedia, together with entity examples, can significantly improve entity retrieval effectiveness. We also use our system for the ad hoc tasks by inferring target categories from the title of the query. The results were worse than when using a full-text search engine, which confirms our hypothesis that ad hoc retrieval and entity retrieval are two different tasks.

Introduction

Entity ranking has recently emerged as a research field that aims at retrieving entities as answers to a query [START_REF] Fissaha Adafre | Entity retrieval[END_REF][START_REF] Pehcevski | Exploiting locality of Wikipedia links in entity ranking[END_REF][START_REF] Thom | Use of Wikipedia categories in entity ranking[END_REF][START_REF] Vercoustre | Entity ranking in Wikipedia[END_REF]. Here, unlike in the related field of entity extraction, the goal is not to tag the names of the entities in documents but rather to get back a list of the relevant entity names. It is a generalisation of the expert search task explored by the TREC Enterprise track [START_REF] Soboroff | Overview of the TREC 2006 Enterprise track[END_REF], except that instead of ranking people who are experts in the given topic, other types of entities such as organizations, countries, or locations can also be retrieved and ranked.

The Initiative for the Evaluation of XML retrieval (INEX) is running a new track on entity ranking in 2007, using Wikipedia as its document collection [START_REF] De Vries | INEX 2007 Entity ranking track guidelines[END_REF]. There are two tasks in the INEX 2007 XML entity ranking (XER) track: entity ranking, which aims at retrieving entities of a given category that satisfy a topic described in natural language text; and list completion, where given a topic text and a small number of entity examples, the aim is to complete this partial list of answers. Two data sets were used by the participants of the INEX and assessed by the track participants. The main purpose of having two data sets is to allow participants to tune the parameters of their entity ranking systems on the training data set, and then use the optimal parameter values on the testing data set.

An example of an INEX 2007 XER topic is shown in Figure 1. Here, the title field contains the plain content only query, the description provides a natural language description of the information need, and the narrative provides a detailed explanation of what makes an entity answer relevant. In addition to these fields, the entities field provides a few of the expected entity answers for the topic (task 2), while the categories field provides the target category of the expected entity answers (task 1).

In this new track, the expected entities correspond to Wikipedia articles that are likely to be referred to by links in other articles. As an example, the query "European countries where I can pay with Euros" [START_REF] De Vries | INEX 2007 Entity ranking track guidelines[END_REF] should return a list of entities (or pages) representing relevant countries, and not a list of entities representing non-relevant (country or other) names found in pages about the Euro and similar currencies.

In this paper, we describe our approach to ranking entities from the Wikipedia XML document collection. Our approach is based on the following principles:

1. A good entity page is a page that answers the query (or a query extended with names of target categories or entity examples).

2. A good entity page is a page associated with a category close to the target category (task 1) or to the categories of the entity examples (task 2). 3. A good entity page is referred to by a page answering the query; this is an adaptation of the HITS [START_REF] Kleinberg | Authoritative sources in hyperlinked environment[END_REF] algorithm to the problem of entity ranking. 4. A good entity page is referred to by contexts with many occurrences of the entity examples (task 2). A broad context could be the full page that contains the entity examples, while smaller and more narrow contexts could be elements such as paragraphs, lists, or tables.

After a short presentation of the INEX Wikipedia XML collection used for entity ranking, we provide a detailed description of our entity ranking approach and the runs we submitted for evaluation to the INEX 2007 XER track. We also report on our run submissions to the INEX 2007 ad hoc track.

INEX Wikipedia XML collection

Wikipedia is a well known web-based, multilingual, free content encyclopedia written collaboratively by contributors from around the world. As it is fast growing and evolving it is not possible to use the actual online Wikipedia for experiments, and so we need a stable collection to do evaluation experiments that can be compared over time. Denoyer and Gallinari [START_REF] Denoyer | The Wikipedia XML corpus[END_REF] have developed an XML-based corpus based on a snapshot of the Wikipedia, which has been used by various INEX tracks in 2006 and 2007. It differs from the real Wikipedia in some respects (size, document format, category tables), but it is a very realistic approximation.

Entities in Wikipedia

The entities have a name (the name of the corresponding page) and a unique ID in the collection. When mentioning such an entity in a new Wikipedia article, authors are encouraged to link every occurrence of the entity name to the page describing this entity. This is an important feature as it allows to easily locate potential entities, which is a major issue in entity extraction from plain text.

However in this collection, not all potential entities have been associated with corresponding pages. For example, if we look for Picasso's artworks, only three paintings ("Les Demoiselles d'Avignon", "Guernica", and "Le garçon à la pipe") get associated pages. If the query was "paintings by Picasso", we would not expect to get more than three entity pages for Picasso's paintings, while for the online Wikipedia there are about thirty entities, yet not that many compared to the actual number of his listed paintings.

The INEX XER topics have been carefully designed to make sure there is a sufficient number of answer entities. For example, in the Euro page (see Fig. 2), all the underlined hypertext links can be seen as occurrences of entities that are each linked to their corresponding pages. In this figure, there are 18 entity references of which 15 are country names; specifically, these countries are all "European Union member states", which brings us to the notion of category in Wikipedia.

"The euro . . . is the official currency of the Eurozone (also known as the Euro Area), which consists of the European states of Austria, Belgium, Finland, France, Germany, Greece, Ireland, Italy, Luxembourg, the Netherlands, Portugal, Slovenia and Spain, and will extend to include Cyprus and Malta from 1 January 2008." Fig. 2. Extract from the Euro Wikipedia page

Categories in Wikipedia

Wikipedia also offers categories that authors can associate with Wikipedia pages. There are 113,483 categories in the INEX Wikipedia XML collection, which are organised in a graph of categories. Each page can be associated with many categories (2.28 as an average).

Wikipedia categories have unique names (e.g. "France", "European Countries", "Countries"). New categories can also be created by authors, although they have to follow Wikipedia recommendations in both creating new categories and associating them with pages. For example, the Spain page is associated with the following categories: "Spain", "European Union member states", "Spanishspeaking countries", "Constitutional monarchies" (and some other Wikipedia administrative categories).

When searching for entities it is natural to take advantage of the Wikipedia categories since they would give a hint on whether the retrieved entities are of the expected type. For example, when looking for entities "authors", pages associated with the category "Novelist" may be more relevant than pages associated with the category "Book".

Our entity ranking approach

Our approach to identifying and ranking entities combines: (1) the full-text similarity of the answer entity page with the query; (2) the similarity of the page's categories with the target categories (task 1) or the categories attached to the entity examples (task 2); and (3) the contexts around entity examples (task 2) found in the top ranked pages returned by a search engine for the query.

We have built a system based on the above ideas, and a framework to tune and evaluate a set of different entity ranking algorithms.

Architecture

The system involves several modules and functions that are used for processing a query, submitting it to the search engine, applying our entity ranking algorithms, and finally returning a ranked list of entities. We use Zettair 3 as our choice for a full-text search engine. Zettair is a full-text information retrieval (IR) system developed by RMIT University, which returns pages ranked by their similarity score to the query. In a recent comparison of open source search engines, Zettair was found to be "one of the most complete engines" [START_REF] Middleton | A comparison of open source search engines[END_REF]. We used the Okapi BM25 similarity measure that has proved to work well on the INEX 2006 Wikipedia test collection [START_REF] Iskandar | Social media retrieval using image features and structured text[END_REF].

Our system involves the following modules and functions:

-the topic module takes an INEX topic as input (as the topic example shown in Fig. 1) and generates the corresponding Zettair query and the list of target categories and entity examples (as an option, the names of target categories or example entities may be added to the query); -the search module sends the query to Zettair and returns a list of ranked Wikipedia pages (typically 1500); -the link extraction module extracts the links from a selected number of highly ranked pages,4 together with the information concerning the paths of the links (using an XPath notation); -the category similarity module calculates a weight for a page based on the similarity of the page categories with target categories or those of the entity examples (see 3.2); -the linkrank module calculates a weight for a page based (among other things) on the number of links to this page (see 3.4); and -the full-text IR module calculates a weight for a page based on its initial Zettair score (see 3.4).

The global score for a page is calculated as a linear combination of three normalised scores coming out of the last three modules (see 3.4).

The architecture provides a general framework for evaluating entity ranking which allows for some modules to be replaced by more advanced modules, or by providing a more efficient implementation of a module. It also uses an evaluation module to assist in tuning the system by varying the parameters and to globally evaluate our entity ranking approach.

The current system was not designed for online entity ranking in Wikipedia. First, because we are not dealing with the online Wikipedia, and second because of performance issues. The major cost in running our system is in extracting the links from the selected number of pages retrieved by the search engine. Although we only extract links once by topic and store them in a database for reuse in later runs, for an online system it would be more efficient to extract and store all the links at indexing time.

Using Wikipedia categories

To make use of the Wikipedia categories in entity ranking, we define similarity functions between:

-the categories of answer entities and the target categories (task 1), or -the categories of answer entities and a set of categories attached to the entity examples (task2).

Similarity measures between concepts of the same ontology, such as treebased similarities [START_REF] Blanchard | A tree-based similarity for evaluating concept proximities in an ontology[END_REF], cannot be applied directly to Wikipedia categories, mostly because the notion of sub-categories in Wikipedia is not a subsumption relationship. Another reason is that categories in Wikipedia do not form a hierarchy (or a set of hierarchies) but a graph with potential cycles [START_REF] Thom | Use of Wikipedia categories in entity ranking[END_REF][START_REF] Yu | Ontology evaluation using Wikipedia categories for browsing[END_REF].

Task 1 We first define a similarity function that computes the ratio of common categories between the set of categories cat(t), associated to an answer entity page t, and the set cat(C) which is the union of the provided target categories C:

S C (t) = |cat(t) ∩ cat(C)| |cat(C)| (1)
The target categories will be generally very broad, so it is to be expected that the answer entities would not be directly attached to these broad categories. Accordingly, we experimented with several extensions of the set of categories, both for the target categories and the categories attached to answer entities.

We first experimented with extensions based on using sub-categories and parent categories in the graph of Wikipedia categories. However, on the training data set, we found that these category extensions overall do not result in an improved performance [START_REF] Thom | Use of Wikipedia categories in entity ranking[END_REF], and so they were not used in our INEX 2007 runs.

Another approach is to use lexical similarity between categories. For example, "european countries" is lexically similar to "countries" since they both contain the word "countries" in their names. We use an information retrieval approach to retrieve similar categories, by indexing with Zettair all the categories, using their names as corresponding documents. By sending both the title of the topic T and the category names C as a query to Zettair, we then retrieve all the categories that are lexically similar to C. We keep the top M ranked categories and add them to C to form the set TCcat(C). On the training data set, we found that the value M=5 is the optimal parameter value used to retrieve the likely relevant categories for this task [START_REF] Thom | Use of Wikipedia categories in entity ranking[END_REF]. We then use the same similarity function as before, where cat(C) is replaced with TCcat(C).

We also experimented with two alternative approaches: by sending the category names C as a query to Zettair (denoted as Ccat(C)); and by sending the title of the topic T as a query to Zettair (denoted as Tcat(C)). On the training data set we found that these two approaches were less effective than the TCcat(C) approach [START_REF] Thom | Use of Wikipedia categories in entity ranking[END_REF]. However, we used the Tcat(C) category set in the ad-hoc runs where the target category is not provided.

Task 2 Here, the categories attached to entity examples are likely to correspond to very specific categories, just like those attached to the answer entities. We define a similarity function that computes the ratio of common categories between the set of categories attached to an answer entity page cat(t) and the set of the union of the categories attached to entity examples cat(E):

S C (t) = |cat(t) ∩ cat(E)| |cat(E)| (2)

Exploiting locality of links

For task 2, exploiting locality of links around entity examples can significantly improve the effectiveness of entity ranking [START_REF] Pehcevski | Exploiting locality of Wikipedia links in entity ranking[END_REF]. The idea is that entity references (links) that are located in close proximity to the entity examples, especially in list-like elements, are likely to refer to more relevant entities than those referred to by links in other parts of the page. Here, the very notion of list involves grouping together objects of the same (or similar) nature. We are therefore looking for links that co-occur with links to entity examples in such list-like elements.

Consider the example of the Euro page shown in Fig. 2, where France, Germany and Spain are the three entity examples (as shown in Fig. 1). We see that the 15 countries that are members of the Eurozone are all listed in the same paragraph with the three entity examples. In fact, there are other contexts in this page where those 15 countries also co-occur together. By contrast, although there are a few references to the United Kingdom in the Euro page, it does not occur in the same context as the three examples (except for the page itself).

We have identified in the Wikipedia collections three types of elements that correspond to the notion of lists: paragraphs (tag p); lists (tags normallist, numberlist, and definitionlist); and tables (tag table). We use an algorithm for identifying the (static) element contexts on the basis of the leftmost occurrence of any of the pre-defined tags in the absolute XPaths of entity examples. The resulting list of element contexts is sorted in a descending order according to the number of distinct entity examples contained by the element. If two elements contain the same number of distinct entity examples, the one that has a longer XPath length is ranked higher. Finally, starting from the highest ranked element, we filter all the elements in the list that either contain or are contained by that element. We end up with a final list of (one or more) non-overlapping elements that represent the statically defined contexts for the page. 5Consider Table 1, where the links to entity examples are identified by their absolute XPath notations. The three static contexts that will be identified by the above algorithm are the elements p [START_REF] Iskandar | Social media retrieval using image features and structured text[END_REF], normallist [START_REF] Iskandar | Social media retrieval using image features and structured text[END_REF] and p [START_REF] De Vries | INEX 2007 Entity ranking track guidelines[END_REF]. The first two element contexts contain the three (distinct) examples, while the last one contains only one entity example.

The drawback of this approach is that it requires a predefined list of static elements that is completely dependent on the collection. The advantage is that Table 1. List of links referring to entity examples (France, Germany, and Spain), extracted from the page 9272.html, for the INEX 2007 XER topic shown in Fig. 1.

the contexts are fast to identify. We have also experimented with an alternative algorithm that dynamically identifies the link contexts by utilising the underlying XML document structure. On the training data set, we found that this algorithm does not significantly improve the entity ranking performance compared to the algorithm that uses the static contexts [START_REF] Pehcevski | Exploiting locality of Wikipedia links in entity ranking[END_REF].

Score Functions and parameters

The core of our entity ranking approach is based on combining different scoring functions for an answer entity page, which we now describe in more detail.

LinkRank score The linkrank function calculates a score for a page, based on the number of links to this page, from the first N pages returned by the search engine in response to the query. The number N has been kept to a relatively small value mainly for performance issues, since Wikipedia pages contain many links that would need to be extracted. We carried out some experiments with different values of N and found that N=20 was a good compromise between performance and discovering more potentially good entities.

The linkrank function can be implemented in a variety of ways. We have implemented a linkrank function that, for an answer entity page t, takes into account the Zettair score of the referring page z(p), the number of distinct entity examples in the referring page #ent(p), and the locality of links around the entity examples:

S L (t) = N r=1   z(p r ) • g(#ent(p r )) • lt∈L(pr,t) f (l t , c r |c r ∈ C(p r ))   (3)
where g(x) = x + 0.5 (we use 0.5 to allow for cases where there are no entity examples in the referring page); l t is a link that belongs to the set of links L(p r , t) that point from the page p r to the answer entity t; c r belongs to the set of contexts C(p r ) around entity examples found for the page p r ; and f (l t , c r ) represents the weight associated to the link l t that belongs to the context c r . The weighting function f (l r , c r ) is represented as follows:

f (l r , c r ) =      1 if c r = p r (the context is the full page) 1 + #ent(c r ) if c r = e r (the context is an XML element)
A simple way of defining the context of a link is to use its full embedding page [START_REF] Vercoustre | Entity ranking in Wikipedia[END_REF]. In this work we use smaller contexts using predefined types of elements such as paragraphs, lists and tables (as described in sub-section 3.3).

Category similarity score As described in sub-section 3.2, the category score S C (t) for the two tasks is calculated as follows:

task 1

S C (t) = |cat(t) ∩ cat(C)| |cat(C)| (4)
For task 1, we consider variations on the category score S C (t) based on lexical similarities of category names (see sub-section 3.2), by replacing cat(C) with TCcat(C).

task 2

S C (t) = |cat(t) ∩ cat(E)| |cat(E)| (5)
On the training data set, we found that extending the set of categories attached to both entity examples and answer entities did not increase the entity ranking performance [START_REF] Thom | Use of Wikipedia categories in entity ranking[END_REF], and so for task 2 we do not use any category extensions.

Z score The Z score assigns the initial Zettair score to an answer entity page. If the answer page does not appear among the initial ranked list of pages returned by Zettair, then its Z score is zero:

S Z (t) =      z(t) if page t was returned by Zettair 0 otherwise (6)
Global score The global score S(t) for an answer entity page is calculated as a linear combination of three normalised scores, the linkrank score S L (t), the category similarity score S C (t), and the Z score S Z (t):

S(t) = αS L (t) + βS C (t) + (1 -α -β)S Z (t) (7)
where α and β are two parameters that can be tuned differently depending on the entity retrieval task. We consider some special cases that allow us to evaluate the effectiveness of each module in our system: α = 1, β = 0, which uses only the linkrank score; α = 0, β = 1, which uses only the category score; and α = 0, β = 0, which uses only the Z score. 6 More combinations for the two parameters are explored in the training phase of our system. The optimal combination is then used on the testing data set.

Experimental results

In this section, we present results that investigate the effectiveness of our entity ranking approach when applied to both the INEX 2007 XER and ad hoc tracks.

We first tune the system parameters using the training collection, and then we apply the optimal values on the test collection. We submitted three runs for task 1 and three runs for task 2. For this track, we aim at investigating the impact of using various category and linkrank similarity techniques on the entity ranking performance. We also compare the performances of our entity ranking runs to that achieved by a full-text retrieval run. For the ad hoc track, we submitted three entity ranking runs that correspond to the three individual modules of our system and compare it with the full text Zettair run submitted by RMIT. For this track, we aim at investigating the impact of using our entity ranking approach on the ad hoc retrieval performance.

XER training data set (28 topics)

The XER training data set was developed by our participating group. It is based on a selection of topics from the INEX 2006 ad hoc track. We chose 27 topics that we considered were of an "entity ranking" nature, where for each page that had been assessed as containing relevant information, we reassessed whether or not it was an entity answer, and whether it loosely belonged to a category of entity we had loosely identified as being the target of the topic. If there were entity examples mentioned in the original topic these were used as entity examples in the entity topic. Otherwise, a selected number (typically 2 or 3) of entity examples were chosen somewhat arbitrarily from the relevance assessments. We also added the Euro topic example (shown in Fig. 1) from the original INEX description of the XER track [START_REF] De Vries | INEX 2007 Entity ranking track guidelines[END_REF], resulting in total of 28 entity ranking topics. We use mean average precision (MAP) as our primary method of evaluation, but also report results using several alternative measures that are typically used to evaluate the retrieval performance: mean of P [START_REF] Fissaha Adafre | Entity retrieval[END_REF] and P [START_REF] Thom | Use of Wikipedia categories in entity ranking[END_REF] (mean precision at top 5 or 10 entities returned), and mean R-precision (R-precision for a topic is the P[R], where R is the number of entities that have been judged relevant for the topic). For task 1 all the relevant entities in the relevance assessments are used to generate the scores, while for task 2 we remove the entity examples both from the list of returned answers and from the relevance assessments, as the task is to find entities other than the provided examples.

Task 1 Table 2 shows the performance scores on the training data set for task 1, obtained for Zettair and our three submitted XER runs. Runs 1 and 2 use only the category module (α = 0.0, β = 1.0) while run 3 uses a combination of linkrank, category, and Z scores (α = 0.1, β = 0.8). Runs 2 and 3 use lexical similarity for extending the target categories.

We observe that the three entity ranking runs outperform the plain Zettair run, which suggests that using full-text retrieval alone is not an effective entity ranking strategy. The differences in performance between each of the three runs and Zettair are statistically significant (p < 0.05) only for the two entity ranking runs that use lexical similarity between categories (runs 2 and run 3 in Table 2).

When comparing the performances of the runs that use only the category module, we observe that run 2 that uses lexical similarity between category names (TCcat(C)) is more effective than the run that uses the target categories only (cat(C)). With MAP, the difference in performance between the two runs is statistically significant (p < 0.05). We also observe that the third run, which uses combined scores coming out from the three modules, performs the best among the three. To find the optimal values for the two combining parameters for this run, we calculated MAP over the 28 topics in the training data set as we varied α from 0 to 1 in steps of 0.1. For each value of α, we also varied β from 0 to (1α) in steps of 0.1. We found that the highest MAP score (0.287) is achieved for α = 0.1 and β = 0.8 [START_REF] Thom | Use of Wikipedia categories in entity ranking[END_REF]. This is a 19% relative performance improvement over the best score achieved by using only the category module (α0.0-β1.0). This performance improvement is statistically significant (p < 0.05). Task2 Table 3 shows the performance scores on the training data set for task 2, obtained for Zettair and our three submitted XER runs. As with task 1, we again observe that the three entity ranking runs outperform the plain Zettair run. With the first two runs, we want to compare two entity ranking approaches: the first that uses scores coming out from the linkrank module (run 1), and the second that uses scores coming out from the category module (run 2). We observe that using categories is substantially more effective than using the linkrank scores. With MAP, the difference in performance between the two runs is statistically significant (p < 0.05).

Run 3 combines the scores coming out from the three modules. To find the optimal values for the two combining parameters for this run, we again varied the values for parameters α and β and we found that the highest MAP score (0.377) was achieved for α = 0.2 and β = 0.6 [START_REF] Pehcevski | Exploiting locality of Wikipedia links in entity ranking[END_REF]. This is a 19% relative performance improvement over the best score achieved by using only the category module. This performance improvement is statistically significant (p < 0.05).

XER testing data set (73 topics)

Runs description Table 4 lists the six XER and four ad hoc runs that we submitted for evaluation in the INEX 2007 XER and ad hoc tracks, respectively. With the exception of the plain Zettair run, all the runs were created by using our entity ranking system. However, as seen in the table the runs use various parameters whose values are mainly dependent on the task. Specifically, runs differ depending on whether (or which) Zettair category index is used, which of the two types of link contexts is used, whether categories or example entities are used from the topic, and which combination of values is assigned to the α and β parameters.

For example, the run "run 3", which was submitted for evaluation in task 1 of the INEX 2007 XER track, can be interpreted as follows. The Wikipedia fulltext Zettair index is used to extract the top 20 ranked Wikipedia pages, using the title from the INEX topic as a query. After extracting all links to potential answer entities from these 20 pages, the Zettair index of category names is used Table 4. List of six XER and four ad hoc runs submitted for evaluation in the INEX 2007 XER and ad hoc tracks, respectively. "Cat-sim" stands for category similarity, "Ctx" for context, "Cat" for categories, "Ent" for entities, "T" for title, "TC" for title and categories, "C" for category names, "CE" for category and entity names, "FC" for full page context, and "EC" for element context. to extract the top five ranked categories, using both the title and the category names (TC) from the INEX topic as a query. This set of five categories is used as an input set of target categories by the category module. The full page context (FC) is used to calculate the scores in the linkrank module. The final scores for answer entities are calculated by combining the scores coming out of the three modules (α = 0.1, β = 0.8).

Category index

Results Results for XER task 1 and task 2 on the testing data set will be reported when they become available. The results obtained for our runs will also be compared with the results obtained for runs submitted by other track participants.

Ad hoc data set (99 topics)

There are no target categories and example entities provided for the ad hoc task. However, we wanted to apply our algorithm to test 1) whether some indication of the page categories would improve the retrieval performance, and 2) whether extracting new entities from the pages returned by Zettair would be beneficial for ad hoc retrieval. We submitted four runs for the INEX 2007 ad hoc track: Zettair, representing a full-text retrieval run, and three entity ranking runs. As shown in Table 4, run 1 uses only the Z module for ranking the answer entities, run 2 uses only the linkrank module, while run3 uses only the category module. For each INEX 2007 ad hoc topic, we create the set of target categories by sending the title T of the query to the Zettair index of categories that has been created by using the names of the categories and the names of all their attached entities as corresponding documents.

Table 5 shows the performance scores on INEX 2007 the ad hoc data set, obtained for Zettair and our three submitted entity ranking runs. Two retrieval scenarios are distinguished in the table: a document retrieval scenario (the first four result columns in Table 5), where we compare how well the runs retrieve relevant documents; and a focused retrieval scenario (the last three result columns in Table 5), where we compare how well the runs retrieve relevant information within documents.

For the document retrieval scenario, we observe that Zettair outperforms the other three XER runs. The differences in performance between Zettair and any of these three runs are statistically significant (p < 0.05). Among the three XER runs, the run that only uses the Z scores performs significantly better than the other two, followed by the run that only uses the category scores which in turn performs significantly better than the worst performing run that only uses the linkrank scores.

The same trend among the four runs is observed across the three sub-tasks of the focused retrieval scenario, where again Zettair is able to better identify and retrieve the relevant information compared to the other three XER runs.

The obvious conclusion of our our ad hoc experiments is that Zettair, which is especially designed for ad hoc retrieval, performs better than our entity ranking system specifically designed for entity retrieval.

Conclusion and future work

We have presented our entity ranking system for the INEX Wikipedia XML document collection which is based on exploiting the interesting structural and semantic properties of the collection. On the training data, we have shown that our system outperforms the full text search engine in the task of ranking entities.

On the other hand, using our entity ranking system for ad-hoc retrieval did not result in any improvement over the full-text search engine. This confirms our hypothesis that that tasks of ad hoc retrieval and entity ranking are very different. Once the official results for the INEX 2007 XML entity ranking track are available, we will make further analysis and compare the effectiveness of our entity ranking system to those achieved by other participating systems.

  2007 XER track: a training data set, comprising 28 XER topics which were adapted from the INEX 2006 ad hoc topics and proposed by our INRIA participating group; and a testing data set, comprising 73 XER topics most of which were proposed

	<inex_topic>
	<title>
	European countries where I can pay with Euros
	</title>
	<description>
	I want a list of European countries where I can pay with Euros.
	</description>
	<narrative>
	Each answer should be the article about a specific European country
	that uses the Euro as currency.
	</narrative>
	<entities>
	<entity ID="10581">France</entity>
	<entity ID="11867">Germany</entity>
	<entity ID="26667">Spain</entity>
	</entities>
	<categories>
	<category ID="185">european countries<category>
	</categories>
	</inex_topic>
	Fig. 1. Example INEX 2007 XML entity ranking topic

Table 2 .

 2 Performance scores for Zettair and our three XER submitted runs on the training data set (28 topics), obtained for task 1 with different evaluation measures. For each measure, the best performing score is shown in bold.

	P[r]

Table 3 .

 3 Performance scores for Zettair and our three XER submitted runs on the training data set (28 topics), obtained for task 2 with different evaluation measures. For each measure, the best performing score is shown in bold.

				P[r]
	Run	cat-sim	α β	5	10 R-prec MAP
	Zettair	-	--0.229 0.232 0.208 0.172
	run 1 cat(E)-cat(t) 1.0 0.0 0.214 0.225 0.229 0.190
	run 2 cat(E)-cat(t) 0.0 1.0 0.371 0.325 0.319 0.318
	run 3 cat(E)-cat(t) 0.2 0.6 0.500 0.404 0.397 0.377

Table 5 .

 5 Performance scores for Zettair and our three XER submitted runs on the ad hoc data set (99 topics), obtained with different evaluation measures. For each measure, the best performing score is shown in bold.

			P[r]	Foc	RiC BiC
	Run	α β	5	10 R-prec MAP iP[0.01R] MAgP MAgP
	Zettair --0.513 0.469 0.326 0.292 0.379 0.088 0.195
	run 1 0.0 0.0 0.513 0.469 0.303 0.247 0.379	0.075 0.165
	run 2 1.0 0.0 0.339 0.289 0.170 0.121 0.235	0.031 0.070
	run 3 0.0 1.0 0.406 0.368 0.208 0.157 0.287	0.050 0.115

http://www.seg.rmit.edu.au/zettair/

We discarded external links and some internal collection links that do not refer to existing pages in the INEX Wikipedia collection.

In the case when there are no occurrences of the pre-defined tags in the XPath of an entity example, the document element (article[START_REF] Iskandar | Social media retrieval using image features and structured text[END_REF]) is chosen to represent the element context.

This is not the same as the plain Zettair score, as apart from answer entities corresponding to the highest N pages returned by Zettair, the remaining entity answers are all generated by extracting links from these pages, which may or may not correspond to the initial 1500 pages retrieved by Zettair.

Acknowledgements

Part of this work was completed while James Thom was visiting INRIA in 2007.