Olivier Berder

Philippe Rostaing
email: philippe.rostaing@univ-brest.fr

Ludovic Collin
email: collin@ecole-navale.f

Gilles Burel

Gilles Burel Minimum

Minimum BER Diagonal precoder for MIMO systems

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

I INTRODUCTION

Multi-Input Multi-Output (MIMO) digital transmission systems currently retain more and more attention due to the very high spectral efficiencies they can achieve. Most existing systems such as spatial multiplexing [START_REF] Foschini | Layered space-time architecture for wireless communication in a fading environment when using multi-element antennas[END_REF] or space-time coding [START_REF] Tarokh | Space-time codes for high data rate wireless communication: Performance criterion and code construction[END_REF] assume no channel knowledge at the transmitter. However, in many wireless applications, feedback does exist (e.g., symmetric or asymmetric duplex transmissions), and channel information can be made available at the transmitter. Indeed, only a very small data rate is used to provide channel information to the transmitter. The question, then, is how to take profit of this information to globally optimize the transmission system. Performances can be improved either by antenna selection [START_REF] Heath | Antenna selection for spatial multiplexing systems based on minimum error rate[END_REF] or precoders design in order to allocate power among the transmit antennas. In [START_REF] Sampath | Joint transmit and receive optimization for high data rate wireless communications using multiple antennas[END_REF] and [START_REF] Sampath | Optimum precoder and equalizer designs for fixed rate MIMO systems[END_REF] Sampath et al have globally optimized the transmission scheme by designing optimum precoder and decoder using the minimum mean square error (MMSE) criterion. An interesting property of their work is the diagonality of their equivalent channel after optimization. This diagonality can also be obtained by the singular value decomposition (SVD) method, especially used to maximize the channel capacity, which leads to the well-known water-filling (WF) solution [START_REF] Boixadera Espax | Capacity considerations for wireless multiple-input multipleoutput channels[END_REF][START_REF] Holter | On the capacity of the MIMO channel -a tutorial introduction[END_REF]. In this paper, a similar technique is employed to provide a simplified diagonalized MIMO system which can be easily optimized by any criterion (not only the channel capacity maximization). In addition, this diagonality results in an interesting complexity reduction, which enables one to use a maximum-likelihood (ML) receiver.

As the bit error rate (BER) can then be expressed in a quite simple way, we propose a new precoder based on the minimum BER (MBER) criterion. By comparisons with other criteria such as MMSE or the WF solution, we show that the use of the MBER criterion increases the system performances in term of error rate and achieved capacity for a given constellation. We also present an approximation of the MBER precoder (AMBER), whose results remain very close and which is faster because it does not need any optimization.

II SIMPLIFIED MIMO SYSTEM MODEL

Let us consider a MIMO system with n R receive and n T transmit antennas over which we want to achieve b independent data streams. Including a precoder matrix F and a decoder matrix G, the basic system model is (Fig. 1):

y = GHFs + Gν ( 1
)
where H is the (n R × n T ) channel matrix, F is the (n T × b) precoder matrix, G is the b × n R decoder matrix , s is the (b × 1) transmitted vector and ν is the (n R × 1) noise vector. We assume :

E {ss * } = I b , E {νν * } = R and E {sν * } = 0.
Furthermore, if the available transmission power is noted p 0 , the constraint below must be fulfilled:

trace {FF * } = p 0 .
Our first objective is to obtain a diagonal channel and a whitened noise in order to facilitate both the system analysis and the determination of the optimal precoder. We decompose the matrices

F = F v F d and G = G d G v
, where the virtual precoder and decoder matrices F v and G v are designed to reach this first objective, such that the determination of precoder F d and decoder G d with respect to any criterion is greatly facilitated. They are obtained after successive matrix manipulations and transformations, such as the singular value decomposition (SVD), and are decomposed as follows:

F v = F 1 F 2 F 3 and G v = G 3 G 2 G 1 .
The three different steps necessary to get F v and G v are resumed in Table 1.

step i method F i G i noise whitening 1 EVD: R = QΛQ * F 1 = I n T G 1 = Λ -1 2 Q * channel diagonalization 2 SVD: G 1 HF 1 = AΣB * F 2 = B G 2 = A * dimensionality reduction 3 F v = F 1 F 2 F 3 G v = G 3 G 2 G 1 F 3 = I b 0 G 3 = I b 0 Table 1:
Steps to obtain the diagonal MIMO system in case of CSI at the transmitter.

In this new representation the model becomes:

y = G d H v F d s + G d ν v (2)
where

H v = G v HF v is the virtual diagonal channel and ν v = G v ν is the virtual noise, whose correlation matrix R v = G v RG * v = I b .
H v entries are linked to the singular values of the channel H and can be expressed as H v = diag(σ 1 , ..., σ b ) with positive elements ranked in the decreasing order.

III PRECODER DESIGNS

The matrices F d and G d are still to be determined, according to a given criterion. Since the channel is diagonal and the noise white, we restrict our search to diagonal matrices

F d = diag{f i } b i=1 and G d = diag{g i } b i=1
. Hence, the system can be seen as a set of b independent and parallel subchannels. ML detection can be then performed efficiently even for large values of b and important constellations.

The values of these matrices depend on the criterion to be optimized as illustrated hereafter. Our approach provides a fast way to find many results already available in the literature as well as new ones for the MBER precoder and its approximation.

III.1 Classical criteria

The most popular criterion for MIMO systems optimization aims at maximizing the information rate of the transmission and is known as the water-filling (WF) solution.

Reminding the basic hypothesis, the equivalent model (2) leads to the following capacity [START_REF] Telatar | Capacity of multi-antenna gaussian channels[END_REF]:

C = b i=1 log 2 (1 + f 2 i σ 2 i ) (3)
Using Lagrange multiplier µ, the criterion to be optimized under the constraint on total transmit power is then:

C W F = b i=1 log 2 (1 + f 2 i σ 2 i ) + µ b i=1 f 2 i -p 0 (4)
Cancellation of ∂CW F ∂fi provides the precoder elements expression:

f 2 i = p 0 + bΨ k=1 1/σ 2 k b ψ - 1 σ 2 i + (5)
where (s) + = s if s > 0 and (s) + = 0 if s ≤ 0, and b Ψ represents the integer until which this positivity condition remains true.

The minimization of the mean square error (MMSE) is another optimization method, especialy appreciated for its robustness and low complexity. We introduce here the weigthed MMSE criterion, that allows to get information on each eigen mode and to act on it, leading to various applications such as the quality of services or the equal-error transmission.

Thanks to the diagonal representation, the weighted mean square error is expressed as:

b i=1 E[w i |(g i σ i f i -1)s i + g i ν vi | 2 ] (6)
where w i for i = 1, . . . , b are positive weighting coefficient.

That leads to the following criterion to be minimized:

C M SE = b i=1 w i (g 2 i σ 2 i f 2 i -2g i σ i f i + g 2 i + 1) + µ[( b i=1 f 2 i ) -p 0 ] (7)
Cancellations of ∂CMSE ∂fi and ∂CMSE ∂gi provide the precoder and decoder expressions:

f 2 i = w i (p 0 + bΨ k=1 1/σ 2 k ) σ i bΨ k=1 w k /σ 2 k - 1 σ 2 i + and g i = σ i f i (σ i f i ) 2 + 1 (8)
The presence of w i in this expression allows to act on each mode. The expression of the precoder based on the classical (unweighted) MMSE criterion can be easily recovered taking the weighting coefficients w i = 1 for i = 1, . . . , b. Some constant data rate communication systems need a very secure transmission and same SNR ρ on each way, i.e. ρ = ρ i = σ 2 i f 2 i for i = 1, . . . , b. This particular configuration leads to the following precoder expression:

f 2 i = p 0 σ 2 i b k=1 1/σ 2 k (9)
This equal-error precoder can be obtained from another point of view, considering the criterion which aims at maximizing the minimum eigenvalue of the post-processing SN R(F, G) matrix (see [START_REF] Scaglione | Optimal designs for spacetime linear precoders and decoders[END_REF]). This criterion provides a lower bound for the minimum distance of the received symbol vector [START_REF] Scaglione | Optimal designs for spacetime linear precoders and decoders[END_REF].

Same results as ( 5), ( 8) and ( 9) can be found in the literature [START_REF] Sampath | Joint transmit and receive optimization for high data rate wireless communications using multiple antennas[END_REF][START_REF] Sampath | Optimum precoder and equalizer designs for fixed rate MIMO systems[END_REF][START_REF] Scaglione | Optimal designs for spacetime linear precoders and decoders[END_REF] but are obtained here by a simple way since a diagonalization of the MIMO system is performed in a previous step.

III.2 MBER criterion

As the performance of practical systems depends strongly on the bit error rate and achieved capacities, we propose a new precoder based directly on the minimum BER, whose efficiency has been proved in [START_REF] Rostaing | Minimum ber diagonal precoder for mimo digital transmissions[END_REF] for another configuration. As an ML receiver is used, G d has no impact on the minimization of the BER, so we choose for simplicity

G d = I b .
The signal to noise ratio for each sub-channel is:

ρ i = σ 2 i f 2 i ( 10
)
For a square M -QAM constellation (M = 2 2n ), the BER is P e = 1 b b i=1 P e,i where the BER in sub-channel i is [START_REF] Proakis | Digital communications[END_REF]:

P e,i = α M × erf c β M × ρ i with α M = 2 log 2 M (1 - 1 √ M ) and β M = 3 2(M -1) (11)
Using Lagrange multiplier µ, we can express the precoder elements f i as follows:

f 2 i = 1 2β M σ 2 i W 0 2σ 4 i α 2 M β 2 M µ 2 πb 2 (12)
where W 0 stands for Lambert's W function of index 0 [START_REF] Corless | On the Lambert W Function[END_REF]. The parameter µ can be iteratively computed by using the constraint of the total transmit power.

A simplified solution of the MBER design can be performed by approximating the Lambert's W function of index 0 by: W 0 (x) log(x) -log(log(x)) for x 1

By using this approximation in [START_REF] Telatar | Capacity of multi-antenna gaussian channels[END_REF] and the constraint power we directly obtain the approximated MBER (AMBER) solution:

f 2 i = a i (1 -k A k ) + A i k a k k a k for i = 1, . . . , b (14)
where:

a i = 1 2β M σ 2 i (15) A i = a i (log(b i ) -log(log(b i ))) with b i = 2σ 4 i α 2 M β 2 M πb 2 (16)
One should note here that, in the low SNR case, the approximation (13) does not hold any more; log(b i ) may be smaller than 1 and (16) can not be computed. The AMBER method then neglects the weakest subchannel, just as MMSE or WF solutions, and ( 14) is computed over the remaining modes.

This AMBER method is the fastest one among those presented in this paper, because it needs neither optimization nor µ search.

IV SIMULATION RESULTS

The efficiency of the MBER precoder is illustrated by Fig. 2 which represents the BER and achieved capacity of MIMO systems with different precoders with respect to the SNR. We here consider n T = 5 transmitters, n R = 5 receivers; using a QPSK constellation, we transmit 4 independent data streams over the system.

For each SNR, 100 000 4-symbol vectors are transmitted during the Monte-Carlo simulations. For each transmitted vector, a new H and a new R are randomly chosen in order to obtain results that depend neither on a particular channel, nor on particular noise statistics. Entries of H are i.i.d. zero-mean unit-variance complex Gaussian random variables. Matrices R are obtained by R = T T * (where entries of T are i.i.d. zero-mean unit-variance complex Gaussian random variables) and then scaled according to the desired SNR. The SNR is defined as the ratio of the total transmitted power p 0 to the total received noise power.

In order to compute the achieved capacity, we consider a binary symmetric channel (BSC) [START_REF] Proakis | Digital communications[END_REF] because we use an optimal receiver (ML) and the input and the output of the system can be seen as binary data streams. In the MIMO case with b independent data streams and a QPSK constellation (2 bits per symbol), the BER and the achieved capacity are then related by the following expression:

C QP SK = 2b×(1+BER×log 2 (BER)+(1-BER)×log 2 (1-BER)) (bits / transmitted vector) (17) Fig. 2 shows that the best precoder is the MBER, followed by the MMSE. In the MMSE solution, the performances of our equivalent model are exactly the same as in [START_REF] Sampath | Optimum precoder and equalizer designs for fixed rate MIMO systems[END_REF]. In opposition with the expected capacity, the WF is the worst one (the SNR gain of the MBER is about 5 dB). Intermediate results are obtained by the equal-error precoder. Finally, the performances of the very simple AMBER are close to the optimal MBER and even equivalent as the SNR is increasing.

Figure 1 :

 1 Figure 1: MIMO System with linear precoder and decoder

  Bit-error-rate

Figure 2 :

 2 Figure 2: Experimental results for a QPSK with n T = 5, n R = 5, and b = 4

The diagonality the global optimized system allows independent parallel subchannels and an easy ML reception. Nevertheless, it would be interesting to study the design of non-diagonal precoders and their performance under the same conditions. Futhermore, this kind of transmission scheme is directly applicable to narrowband wireless channels, in which channel information can be made available at the transmitter. As a matter of fact, future research will include applications to broadband MIMO channels, with the help of multicarrier modulations.

V CONCLUSION

In this paper, we proposed a simplified representation of MIMO channels along with an optimization of the global transmission scheme. Thanks to simple matrices manipulations, i.e. an eigen value decomposition and a singular value decomposition, we respectively whitened the noise and diagonalized the channel. The diagonality of the obtained global system allowed us to design a diagonal precoder based on the Minimum Bit Error Rate criterion. By comparisons precoders based on other criteria, such as the maximum information rate or the minimum mean square error, it was shown that the MBER precoder was far more efficient, both in achieved capacity and BER terms. The best compromise between performance and complexity is certainly obtained by the AMBER precoder. Its performances are very close to the optimal MBER one with a minimum of complexity.


archive ouverte pluridisciplinaire HAL, est destinée au dépôt

In-depth theoretical understanding of the chemical interaction of aromatic compounds with a gold nanoparticle

Gold Nanoparticles (GNPs), owing to their unique properties and versatile preparation strategy, have been demonstrated to exhibit promising applications in diverse fields, which includes bio-sensors, catalysts, nanomedicines, radiotherapy. Yet, the nature of the interfacial interaction of GNPs with their chemical environment remains elusive. Experimental vibrational spectroscopy can reveal different interactions of aromatic biological molecules absorbed on GNPs, that may result from changes in the orientation of the molecule. However, the presence of multiple functional groups and the aqueous solvent introduces competition, and complexifies the spectral interpretations. Therefore, our objective is to theoretically investigate the adsorption of aromatic molecules containing various functional groups on the surface of GNP to comparatively study their preferred adsorption modes. The interaction between Au 32 , as a model of GNP, and a series of substituted aromatic compounds that includes benzene, aniline, phenol, toluene, benzoic acid, acetophenone, methyl benzoate, and thiophenol, is investigated. Our computed interaction energies highlight the preference of the aromatic ring to lie flat on the surface. The orientations of the molecules can be distinguished using infrared spectroscopy along with strong changes in intensity and significant shifts of some vibrational modes when the molecule interacts with GNP. The interaction energy and the electron transfer between the nanoparticle and the aromatic molecule are not found to correlate, possibly because of significant back donation of electrons from GNP to organic molecules as revealed by charge decomposition analysis. A thorough quantum topological analysis identifies multiple non-covalent interactions and assigns the nature of the interaction mostly to dative interactions between the aromatic ring and GNP as well as dispersive interaction. Finally, energy decomposition analyses point out the role of the charge transfer energy contribution in the subtle balance of the different physical components.

Introduction

The interest in understanding the interaction between gold nanoparticles (GNPs) and their surroundings, which includes surface ligands and solvent, has recently increased significantly, owing to their tunability to allow the design and synthesis of materials with desired physical, chemical, and optical properties. These materials have a broad range of application, such as catalysis, nanomedicine, imaging, biosensors, etc. [1][2][3][4][5][6] The different orientation of ligands on the surface, as spectroscopically identified, depends on various factors such as coverage, surface charge, etc. and can affect significantly their physical and chemical properties. With the development of surface sensitive spectroscopy techniques, such as surface enhanced Raman spectroscopy (SERS), Surface Plasmon Resonance (SPR), attenuated total reflection Fourier transform infrared (ATR-FTIR) and sum frequency generation (SFG), it is now possible to obtain structural information of the compounds interacting at the surface of nanoparticles. [7][8][9][10][11][12][13][14] The spectroscopic signatures provide information on the way biomolecules (proteins, lipids, and others) interact with nanoparticles, revealing whether the structural integrity is maintained or disrupted as they interact. 7,[15][16][17] Nevertheless, interpretation of experimental data is often difficult as illustrated with infrared (IR) spectra that exhibit considerable vibrations along with band broadening. Also, the presence of solvent molecules can additionally induce an important difference between spectra of isolated or adsorbed molecules, making interpretation uncertain.

Also, there is still limited understanding on the underlying forces governing the interaction energy. Several computational studies investigate the interaction at the interface of nanoparticles with various molecules, such as oxygen, carbon monoxide, amino acids, etc. [18][19][20][21][22][23] However, these efforts have faced several challenges that include the complexity of nanoparticles in terms of size and shape, which result in different reactivity sites.

In this context, computational chemistry can provide insights at the atomistic scale. Within the quantum chemistry framework, there is still a size limitation for the systems under evaluation, despite the rapid development in the computational power. To mitigate this limitation, there are different computational methodologies available to enable the simulation of gold nanoparticles, such as the semi-empirical DFTB method [24][25][26] , classical force fields 22,27,28 and coarse grained models 29,30 , with increasing level of approximations introduced respectively. Therefore, these methodologies are generally developed relying on more accurate methods acting as a reference to ensure their reliability. Here, an in-depth DFT level investigation is performed to study the interaction between gold nanoparticles with aromatic organic molecules, including the dominant physical origins of the interaction energies. The achieved understanding might help the development of simplified, empirical methods: the strength and physical origin of the interactions are valuable guides for choosing the most appropriate approaches between (polarized) force fields, tight-binding methods and machine-learning potentials.

Our previous work on the interaction with a series of small organic molecules has indicated that benzene prefers to adopt a flat configuration (with the aromatic plane interacting parallel to the surface of GNP). 31 This could be attributed to the optimized interaction between the HOMO of benzene and LUMO of GNP, as well as the maximization of dispersion interactions. However, previous studies of aromatic containing compounds deposited on metal surfaces have indicated that the aromatic plane does not always adsorbed in parallel configuration. 8,12,13,32 They could adopt either a perpendicular configuration or a tilted orientation with respect to the plane of the surface. Contributing factors include, among others, the presence of functional groups, that either alter the electron density of the aromatic compound, introduces steric effects or leads to stronger "direct" interactions because of high ligand affinity for gold. Considering the extensive presence of aromatic containing systems across diverse fields, i.e. materials science, enzyme design, etc., it is important to understand the interactions between GNP and aromatic compounds, in particular the substituent effect on the preferred adsorption geometries.

In this work, we are systematically investigating the interaction of a series of substituted aromatic compounds, i.e. benzene, benzoic acid, acetophenone, ethyl benzoate, toluene, phenol, aniline, and thiophenol, on Au 32 , which is taken as the GNP model (Figure 1). As the study is performed in gas phase, benzoic acid and thiophenol are protonated whereas aniline is not protonated (NH 2 group). These forms are not the ones usually present in experimental conditions in solution. The icosahedral strucutre of Au 32 has been taken from the literature without further change. 33 Initially, the aromatic compounds are placed in at least two different configurations, called "flat" and "perpendicu- lar" (see Figure 1). The complexes are then optimized without constraints and subsequently, the IR spectra are computed. The effect of the interaction with GNP is studied in detail by examining the modification of the vibrational modes of the aromatic molecule. Finally, different topological and energy decomposition analyses are performed to probe the nature of the interactions. The comparison between the different approaches leads to a more precise description of the equilibrium of the terms that compose the chemical interaction.

Methodology

DFT calculations

DFT calculations have been performed with the GGA/PBE functional associated with the D3 dispersion correction 34 using de-Mon2k, 35,36 unless otherwise mentioned. Gold atoms are described with a relativistic effective core potential (RECP), either with small core (SC), i.e. 60 core electrons, or with large core (LC), i.e. 68 core electrons, and their associated valence basis sets. The organic atoms are described with DZVP basis set. The deMon2k code, which is based on variational fitting of Coulomb potential, uses an auxiliary density to calculate the exchangecorrelation contributions, resulting in significant acceleration in computation time. The criteria for SCF and auxiliary density convergences are set to 1.0.10 -9 a.u and 1.0.10 -7 a.u, respectively. The geometry optimizations of each of the complexes have been performed without constraints, with the convergence criterion for RMS gradient set to be 1.0.10 -5 a.u.. Since the LC-RECP optimized geometry of Au 32 interacting with benzene is similar to the one obtained with SC-RECP, (Au-benzene distance differs by 0.06 Å), the LC-RECP has been used for the optimization of all the other complexes, with a significant reduction in the computational cost.

The interaction energy, E int , was obtained for the optimized geometries via:

E int = Esys -E GN P,sys -Eorg,sys (1)
with Esys the energy of the global system, E GN P,sys the electronic energy of Au 32 , and Eorg,sys the electronic energy of the respective organic molecule at the geometry of the full system. The adsorption energies of the complexes, which take into account the deformation energy, are provided in supplementary information and differ by 3 kcal/mol in average compared to the interaction energies (GNP contributes to 80% of the deformation energy). The charge transfer (CT) was obtained by subtracting the total charge of Au 32 with and without the adsorbate using different population schemes. Vibrational frequencies have been computed analytically for each of the optimized complexes with the LC-RECP/DZVP basis sets to obtain the IR spectra, which have been plotted with a Lorentzian line shape and half-width value of 1 cm -1 . 37 Due to convergence issues in deMon2k, the impact of the basis set superposition error (BSSE) has been estimated with the counterpoise method with Orca package. 38 The Au atom is described by the SC-RECP and its associated valence basis set, while the other atoms are described by def2-SVP or def2-TZVP basis set. The calculated BSSE values are reported in Table S2 and Figure S2 in supplementary information. The calculated BSSE using the TZ basis set is small and regular (∼ 2.5 kcal/mol), so the interaction energies have not been corrected from here onwards. While the impact of the basis set for the adsorbate geometry and the interaction energy is small (DZVP vs. TZVP), the interaction energies computed with LC-RECP are significantly overestimated as compared to SC-RECP, as well as the results from Orca (see Table S2 and Figure 2).

Condensed Fukui analysis of Au 32

Au 32 , as shown in Figure S1, is an icosahedral fullerene-like nanostructure, first computationally predicted to be stable by Johansson et al. 33 Since then, several works have been done with Au 32 as the starting model to study the interaction between GNP with amino acids 20 and small molecules (CO, H 2 , O 2 ). 39,40 To assess the reactivity of Au 32 , the condensed Fukui function has been computed using an analytical approach, as implemented in de-Mon2k. 36 It allows to localize the electrophilic and nucleophilic sites at the surface, and the results are shown in Table S1. 41,42 Due to the high symmetry, this nanoparticle contains 20 sixcoordinated and 12 five-coordinated gold atoms. The condensed Fukui value of all the five-coordinated gold atoms is greater than 0, which means that they are electrophilic sites and susceptible to interact with nucleophilic species. On the other hand, the sixcoordinated gold atoms are mostly nucleophilic sites, susceptible to interact with electrophilic species. This assessment agrees with previous molecular electrostatic potential study by Wang et al. 43

Topological analyses

All of the topological analyses have been carried out within Multiwfn code, 44 except for the quantification of non-covalent interaction (NCI) basins, which has been performed with NCIplot4. 45 Quantum Theories of Atoms in Molecule (QTAIM). The QTAIM approach, developed by Bader and coworkers, 46,47 provides a robust way to study chemical bonding, based on partitioning of electron density in terms of the basins of attractors of the density gradient field. Within this framework, we can search for bond critical points and their associated bond paths, that are representative of the interaction. The characterization of this interaction is then made possible by calculating the local properties, such as electron density, Laplacian of the electron density, and energy density, according to the classification reported by Bianchi and coworkers. 48 Non-Covalent Interaction Analysis With the NCI analysis, developed by Johnson et al., 49 the intermolecular non-covalent interactions can be identified based on the reduced density gradient, while the strength of the interaction is characterized by the multiplication of the sign of the second eigenvalues of the Hessian matrix with the electron density. This analysis results in qualitative visualization of the interaction basins, color coded based on the strength of the interaction. Furthermore, with the recent implementation in NCIplot4, 45 the interaction basins can be further decomposed into different types of interactions, and they are then integrated to produce quantitative results.

Energy and charge decomposition analyses

The energy decomposition analysis (EDA) has been performed based on two different approaches, which are the Block-Localized Wavefunction energy decomposition analysis (BLW-EDA), as implemented in CP2K, 50,51 and Symmetry Adapted Perturbation Theory (SAPT) at HF level with density fitting, as implemented in PSI4 and named SAPT0. [52][53][54] For the sake of simplicity, the SAPT0 results will be referred to as SAPT in the following text.

BLW-EDA is based on the absolutely localized molecular orbitals (ALMO) and defines molecules in terms of "blocks" of basis functions, inhibiting any exchange or sharing of electrons between blocks. The interaction energy calculated with BLW-EDA is defined in the equations 2, and it can be decomposed into polarization (pol), charge transfer (CT), and frozen terms. The sum of frozen and polarization terms is called BLW. E GN P,sys and Eorg,sys correspond to the energy of the GNP and organic fragment in their final geometry adopted in the presence of the other fragment. Eguess is the systems energy obtained by a superposition of the fragment density matrices. E BSSE corresponds to basis set superposition error estimated in the counterpoise procedure.

E IN T = E f rozen + E pol + E CT = E BLW + E CT E f rozen = Eguess -E GN P,sys -Eorg,sys E pol = E BLW -Eguess E CT = Esys -E BLW -E BSSE (2)
Here, we define two blocks, one for the GNP and one for the aromatic adsorbate. Since the polarization of each block in the presence of the other is computed variationally, this method allows rigorous separation between polarization and charge transfer contributions. 50 The frozen terms describes the interaction between isolated fragment densities, which encompasses electrostatic, repulsive, and dispersive contributions. 55 For this calculation, we applied PBE-D3 level of theory, using the MOLOPT-DZVP basis set for valence electrons and Goedecker, Teter, and Hutter (GTH) pseudopotentials. As for Au atoms, the 11 valence electron potential is used. The electron smearing was approximated at 300 K by Fermi-Dirac distribution. Note that this setup closely follows a previous publication, where it has been shown to yield analogous results to plane-wave basis set computations using VASP. 56 SAPT, on the other hand, treats the interaction energy as the perturbation introduced to the Hamiltonian of the isolated monomer, as it interacts in a dimer. The simplest SAPT method, is SAPT0, whose interaction energy can be defined as:

E SAP T 0 int = E (1) elec + E (1) exch + E (2) ind + E (2) disp (3)
This interaction can be decomposed into meaningful physical components, which are electrostatic (E elec ), exchange (E exch ), induction (E ind ) and dispersion (E disp ). In equation 3, (1) and (2) indicate the first and second order terms, respectively. The electrostatic component contains both the interpenetration of the charge clouds and Coulombic interactions. The exchange interaction arises from the overlap of the monomer wave functions and the requirement of a fermionic antisymmetric wave function in the dimer. The induction includes both the polarization response and charge transfer. Dispersion results from the dynamical correlation of electrons between the two monomers. Being the sim-plest method, SAPT0 has the largest mean absolute error as compared to the other SAPT methods. But, considering the relatively low computational cost, this method has been applied. The SAPT analysis has been performed with density fitting, frozen core, and def2-TZVP basis set. Gold atom has been described with SC-RECP and its associated valence basis set.

Lastly, the charge decomposition analysis (CDA), as developed by Dapprich and Frenking and implemented in Multiwfn, 57 constructs the molecular orbital of complexes by linear combination of the fragment orbitals. This approach allows the quantification of charge transfer between donor and acceptor (donation, back donation, and polarization term). Furthermore, it also gives insight into which molecular orbitals of the isolated fragments play significant role in the formation of the complex.

Results and discussion

3.1 Geometry and electronic structure analysis

Flat configuration

The optimized structures of the complexes adopting flat configurations at the DFT level are shown in Figure 3 in the order of increasing interaction energy. In overall, there is an increase of the interaction energy with the addition of functional groups on benzene. An increase of the interaction energy in the dimer of substituted benzene has been previously observed and rationalized. 58,59 Thus, the observed increase for the complexes studied here could similarly be attributed to the additional direct dispersive and electrostatic interactions between the substituent groups and Au 32 . A closer look at the orientation of the aromatic compounds on the surface of Au 32 reveals quite different orientations depending on the substituent groups (see Figure S3). Benzene, phenol, toluene, and aniline are showed to adopt a slightly tilted orientation. Meanwhile, benzoic acid and thiophenol are revealed to adopt a more flat configuration, where the aromatic plane is almost parallel to the surface of Au 32 . This could arise due to the stronger interaction between their respective functional groups (-COOH and -SH) with the gold surface atoms. Acetophenone, on the other hand, is tilted away from the surface of GNP, to favor the interaction between carbonyl group with the gold surface atoms. Ethyl benzoate is planar in gas phase but it rearranges itself in favor of interactions with the -CH 2 -CH 3 group. This rearrangement results in the phenyl group to be tilted away from the surface of GNP. Moreover, other higher-energy conformations have been obtained and are provided in SI (see Figure S4).

The CT has subsequently been obtained from the Atomic dipole moment corrected Hirshfeld (ADCH) population scheme and is provided in Figure 3. In general, there is a net electron transfer from the organic compound to the GNP, which demonstrated the electrophilicity of GNP. However, there seems to be a weak correlation between the interaction energy and CT (R 2 of 0.68, see Figure S5). In particular, the CT calculated for acetophenone and ethyl benzoate are smaller compared to the one for benzoic acid, despite their stronger interaction energy. We have additionally performed population analysis with different schemes for comparison (see Figure S6 and S7 in SI). All schemes produce con- sistent result in regards to the electrophilicity of GNP, but the different schemes result in different amount of CT, in line with the non-uniqueness of the definition of atomic charges. 60 . Reassuringly, regardless of the population schemes a weak correlation is found between the interaction energy and CT.

We have also performed charge decomposition analysis (CDA) to decompose the electron donation and back donation, as well as for the identification of the interacting molecular orbitals (see Table S4 and Figures 4,S8, S9, S10, S11,S12, S13, S14, and S15 in SI). Firstly, the molecular orbitals of the aromatic molecules are in general delocalized throughout the ring and the functional groups. They tend to overlap with the unoccupied molecular orbitals of GNP, leading to a favorable flat orientation (see Figure S8). Secondly, the analysis shows a small contribution of electron back donation the HOMO of GNP to the LUMO of the matic molecule. The synergy between donation and back donation eventually results in stronger interaction energy. However, the interpretation of the charge transfer becomes less straightforward.

Perpendicular configuration

The optimized geometries of the complexes adopting perpendicular configuration are shown in Figure 5. Most of the compounds relaxed back to the flat orientation during the optimization but some of them have a local minimum with perpendicular orienta- tion. In this adsorption mode, the interactions are formed with the substituents, and not with the phenyl ring. The interaction mode through the phenyl ring, with hydrogen pointing towards the GNP surface, also relaxes back to the flat configuration. In the cases of toluene and acetophenone, the perpendicular mode results in a much weaker interaction compared to the flat counterpart. On the other hand, the interaction between GNP and the -COOH functional group is shown to be more favorable compared to the flat counterpart. This implies the stronger interaction between carboxylic functional groups in comparison to benzene. The amount of CT for this interaction mode is also shown in Figure 5 and is smaller in quantity as compared to that of the flat counterpart, in line with our earlier observation that CT and interaction energy are not correlated.

The charge decomposition analysis shows that the molecular orbital of organic molecule participating in the complex formation is localized on the functional groups (see Figure S9, S10, and S12 in SI). Although electron donation is dominating, back donation also participates to the stabilization of adsorption modes.

Vibrational analysis

Greenler, et al. previously proposed the surface selection rule of molecules adsorbed on small metal particles for IR spectra. 61 Furthermore, Schunke et al. investigated the influence of the adsorp-tion orientation of halobenzene on copper surfaces via infrared spectroscopy experiments. 32 In this work, frequency calculations have been performed to simulate the vibrational IR spectra of the isolated molecules and the complexes, and to investigate how the interaction with GNP affects the IR spectra. This insight would be helpful to structural identification in experimental IR spectra.

Our general observation is that firstly, some IR inactive vibrational modes for the isolated molecule have become active. This can be seen clearly in the IR spectrum of benzene adsorbed on GNP in Figure 6. Due to its high symmetry, only few vibrational modes are IR active in the free molecule. Upon interacting with GNP, several modes between 750 cm -1 to 1000 cm -1 , assigned to C-H aromatic bending modes, have become IR active due to symmetry breaking. Secondly, it is interesting to observe that the intensity of C-H aromatic stretching modes of benzene (at ca. 3100 cm -1 ) have been significantly reduced, as compared to the isolated one (37 km/mol for isolated benzene vs. < 5 km/mol for adsorbed benzene). Such observation has consistently been made for all the aromatic compounds adopting flat configurations. Thirdly, the functional groups that interact closely with GNP, or acting as the anchor, undergo quite significant frequency shifts, as can be seen in the case of most of the complexes under study. In the case of toluene, for example, the -CH 3 moiety interacts closely with GNP, for both flat and perpendicular configurations. As such, the frequency corresponding to the -CH 3 stretching (see Figure 6) has been considerably red shifted, i.e. from 2981 cm -1 in isolated toluene to 2942 cm -1 in the flat complex and 2936 cm -1 in the perpendicular complex. In the case for thiophenol, where -SH interacts strongly with GNP, the frequency corresponding to the -SH stretching mode has red shifted as well, from 2634 cm -1 in isolated to 2627 cm -1 in the complex (see Figure 6). Similar observations have been made for acetophenone and benzoic acid (see Figure S19 and S20 in SI), where the C=O stretching mode has considerably shifted due to its relatively strong interaction with GNP, i.e. from 1694 cm -1 in isolation to 1640 cm -1 in flat complex and 1705 cm -1 in perpendicular complex in acetophenone, and from 1741 cm -1 in isolation to 1678 cm -1 in flat complex and to 1664 cm -1 in perpendicular complex in benzoic acid.

Moreover, a published FTIR experiment on thiophenol functionalized gold nanoparticles found CH stretching vibration modes (the strongest of which was at 3057 cm -1 ) in reasonably well agreement with our unscaled calculated frequencies in the region of 3100-3200 cm -1 . 62 These peaks were not detectable in thiophenol solutions when the gold nanoparticles were absent, hence demonstrating that thiophenol interacts with gold nanoparticles.

Topological analysis

Quantum Theory of Atoms in Molecule

Within the QTAIM framework, bond critical points (BCPs) and their associated bond paths have been identified for each of the optimized complexes. The local properties, i.e. the electron density, the Laplacian, and the energy density, calculated at the respective BCPs, are shown in Figures 4,S16 and S17, and tabu-Fig. 6 IR computed spectra of benzene, toluene and thiophenol isolated (I in blue) and adsorbed on Au 32 (A). "F" (in black) and "P" (in red) stand for flat and perpendicular, respectively. lated in Table S5 in SI.

Flat configuration. When aromatic compounds adopt the flat configuration, multiple BCPs have been found. For benzene, two BCPs are found, one classified as dative and the other as dispersive interactions. The addition of functional groups subsequently results in an increased number of BCPs, associated to stronger interaction energies. This observation is in agreement with general observations of substituent effects on interaction energies and for adsorption energies on metal surfaces, and can be rationalized by the direct interaction between the functional groups and the GNP surface. 58,63 In the cases of toluene, phenol, and aniline, one BCP is found in between the -CH 3 , -OH, and -NH 2 , respectively, and the interaction is classified as dispersion. In the cases of benzoic acid and thiophenol, the -COOH and -SH functional groups both form strong dative interactions with GNP. Meanwhile, in the cases of both acetophenone and ethyl benzoate, as discussed earlier, the aromatic ring does not lie flat on the surface of GNP and only one BCP corresponding to the interaction between aromatic moiety and GNP has been found. The functional groups, on the other hand, form rather strong interaction with the surface, according to the local properties of the BCP. Furthermore, it can be deduced from this analysis that the carbonyl and thiol functional groups form stronger interaction with the surface, as compared to the hydroxyl and amine functional groups.

Perpendicular configuration. For the molecules adsorbed in a perpendicular configuration, only a few BCPs exist. In the cases of toluene and acetophenone, only one BCP has been found, between GNP and -CH 3 and -COCH 3 , respectively. Based on the essentially zero interaction energy and basic chemical principles, they correspond to a very weak dispersion interaction between the adsorbate and the GNP. As for benzoic acid, two BCPs have been found for both C=O and O-H, with the interaction classified as dative with the one formed with C=O being stronger than O-H, an expected result based on the availability of oxygen electron lone-pairs to interact with the GNP.

Non-Covalent Interaction analysis

Since QTAIM analysis has indicated the non-covalent nature of the interactions, NCI analysis 49 is used to obtain a visualization and spatial understanding of these non-covalent interactions. Figure 7 and Figure 8 show the intermolecular NCI results of the optimized complexes, with the basins color-coded to represent the strength and the nature of the interaction (red representing repulsive interactions, green representing dispersion interactions, and blue representing dative interactions). By construction, the position of the basins found in NCI corresponds the calculated BCPs.

Flat configuration. For the complexes adopting a flat configuration, multiple delocalized interaction basins have been found. For benzene, there are two delocalized basins, with one stronger dative interaction and the other a dispersive interaction. Similarly, by adding substituents, these two delocalized basins are still generally present in the flat configuration. In addition to these two delocalized basins, there are additional interactions formed between the functional groups and the GNP. The -OH, -NH 2 , -CH 3 in phenol, aniline and toluene form dispersive interaction with GNP. On the other hand, the -COOH and -SH functional groups in benzoic acid and thiolbenzene form a rather strong dative interaction. As for ethyl benzoate and acetophenone, ester and ketone functional groups form multiple non-covalent interactions that caused the phenyl ring to form only one interaction with the GNP.

Perpendicular configuration. For the perpendicular configuration, and similar to QTAIM analysis, lesser number of interaction basins have been found (see Figure 8). The non-covalent basins are present for the CH 3 moiety for both toluene and acetophenone. For benzoic acid, two interaction basins are found between the carboxylic acid functional groups and the GNP, i.e. one for the C=O and one for -OH.

Quantification of NCI basins. The NCI basins have been integrated for quantitative analysis and tabulated in Table S6 in SI. Figure 9 shows the integrated volumes based on the decomposition terms: dative interaction (in blue), dispersive interaction (in green), and repulsive interaction (in red) for each system. Based on this analysis, the total interaction is a subtle interplay between the three terms. Since Figure 9 shows largest volume integral for the dispersive basins, the interaction between aromatic sys-tem and Au 32 is driven by dispersive interactions. Additionally, the dative interaction is increasing for all of the substituted benzene, as compared to that of benzene. In some cases, it can be attributed to the additional blue basins formed by the functional groups (i.e. -C=O of benzoic acid, -C=O of acetophenone, -CH 3 of ethylbenzoate, and -SH of thiophenol) as seen in Figure 7. In the cases of toluene, phenol, and aniline, however, the dative interaction is only observed for the interaction with the phenyl ring. This can then be related to the electron donating nature of these functional groups, that result in increased electron density of the phenyl ring, leading to an increase of dative interaction.

The integrated total volume of NCI basins (summation of the volumes of all constituting basins), which could represent the strength of the interaction energy, is found to be moderately correlated with the interaction energy calculated above (see Figure S23, R 2 = 0.60). In particular, the total volumes of NCI basins for benzoic acid in flat and perpendicular configurations (102.70 and 24.78, respectively) clearly do not reflect the change in the interaction energy (-9.8 vs -11.1 kcal/mol). This qualitative disagreement might be due to an inaccurate description of the electrostatic interactions by the NCI basins. Interestingly, a strong correlation is, however, found between the volumes of the NCI basins and the CT (obtained with the ADCH scheme, see Figure S23 in SI, R 2 = 0.91). This can be rationalized by the general observation of the distance dependence of charge transfer: the more contact there is between the two fragments at the equilibrium distance, the higher the charge transfer is expected to be, with the volumes of the NCI basins being a convenient measure for the contact volume. This is further corroborated by the correlation between the repulsive NCI basin volumes with the total NCI basin volumes (R 2 >0.9, see Figure S24), even though it is the smallest component (the volume corresponding to dispersion interactions are about twice as large).

Energy Decomposition Analysis (EDA)

To further understand the underlying contributing factors to the interaction from an energetic point of view, EDA has also been performed using two different approaches, i.e. BLW-EDA and SAPT. The total energies from BLW-EDA and SAPT correlate well with the interaction energy obtained previously (R 2 =0.96 and 0.81, see Figure 10). BLW-EDA. Figure 11 shows the contributing energy terms calculated with the BLW-EDA approach, i.e. frozen, polarization,and charge transfer, for each system. The frozen term is positive highlighting the dominant role of the Pauli repulsion contribution compared to electrostatic and dispersion contributions. This term is nearly constant across the series and, therefore, uncorrelated to the total interaction energy (see Figure 11, R 2 =0.54). This repulsive energy is only partially compensated by the favorable polarization and it is the charge transfer term that provides the actual stabilization. The functional groups generally increase the weight of polarization in the interaction, with -CO functional groups leading to the highest polarization as shown in the case of acetophenone and benzoic acid in a perpendicular configuration (see Figure S26). Similarly, the functional groups also affect the Fig. 10 The correlation between the total interaction energy obtained with SAPT (top), BLW-EDA (bottom) with the interaction energy obtained with molecular approach. charge transfer energy, taking benzene as the reference. Except for -SH functional group, the effect is similar to that observed for polarization energy. Sulfur has a high tendency to form bonds with Au, 64 which rationalizes that the charge transfer contribution of the interaction between thiophenol and GNP is found to be the strongest.

According to Figure 11 and Figure S28, and in contrast to our observations for water add-layers, 56 the polarization energy is neither sufficiently strong to off-set the Pauli repulsion, nor to induce a significant correlation between FRZ+POL (called BLW interaction energy) and the total interaction energy (R 2 =0.14). For the GNP-aromatics interaction, it is the correlation between the charge transfer energy and the BLW-EDA energy that is found to be strong (R 2 = 0.89, see Figure 11). This demonstrates the relative importance of charge transfer energy term as compared to polarization term for these systems. This is reminiscent of the correlation between the interaction energy and the ADCH analysis and indeed the two completely independent measures for CT are well correlated (R 2 =0.80, see Figure S27). In contrast, the correlation between CT and the dative NCI basins, which should describe a similar physics, is weak (R 2 =0.41, see Figure S29).

SAPT. Figure 11 shows the energy terms calculated with SAPT approach, i.e. exchange energy, electrostatic energy, dispersion energy, and induction energy. As compared to DFT, the interaction energy obtained with SAPT is significantly (factor 2.85) more stabilizing. Our hypothesis is that the perturbative treatment of the dispersion energy is to blame for this overestimation: for metallic systems (small band-gap) low-order perturbation theory can be expected to lead to overestimations. The exchange energy represents the repulsion contribution, which is necessarily positive. According to SAPT both electrostatic and dispersion energies give a significant contribution to the total interaction energy, while induction energy is smaller in magnitude. As could have been expected, the sum of electrostatic and exchange energies from SAPT is well correlated with the frozen term of BLW-EDA (R 2 =0.87, see Figure S29), even though the later also includes the dispersion-correction components of the DFT interaction energy. Given that all SAPT components correlate well (R 2 >0.8) with the total interaction energy, it is difficult to distinguish which physical effects lead to increased interaction energy. Based on the above analysis (ADCH, BLW), one could have expected induction to be dominating, but according to the slopes with respect to the total interaction energy, dispersion is found to be much more sig- nificant. However, this has to be taken with caution, as the total interaction energy obtained with SAPT is significantly overestimated compared to the DFT results. This later originates probably in the perturbative treatment of dispersion. Note that in contrast to dispersion, the induction energy contains an "infinite order" correction terms, δ HF , which leads to a near perfect (R 2 =0.98) correlation with the sum of polarization and charge-transfer interactions as obtained by BLW-EDA. According to Figure S29 in SI, the correlation between the repulsion energy from SAPT and the corresponding NCI basins is strong (R 2 =0.80), while the agreement for the dispersive interaction energies is significantly lower (R 2 =0.66). This highlights the difficulty to capture dispersion interactions solely based on the (reduced) density (gradient).

Conclusion

We have systematically and quantitatively investigated the chemical interaction between substituted aromatic compounds and Au 32 as a model of gold nanoparticles. These interactions mainly consist of multiple non-covalent interactions, with dative, dispersive, and repulsive nature. In general, the substituted aromatic compounds prefer to adopt a relatively flat configuration, where the aromatic ring lies almost parallel to the surface of Au 32 , except for benzoic acid, where the interaction with the -COOH group is stronger than the interaction with the phenyl ring, re-sulting in a favorable perpendicular orientation. These flat and perpendicular orientations can be distinguished using vibrational spectroscopy, where the CH aromatic stretching modes are less IR active for the flat configuration. The interactions have further been quantitatively decomposed using NCI, BLW-EDA and SAPT analyses. Though these three methods adopt different approaches in the energy decomposition, we found strong agreement among them, and the results of this analysis could help in designing accurate force fields for gold nanoparticles based materials. In particular our analysis has evidenced the importance of charge transfer, both in terms of interaction energy and in terms of transferred electrons, which impacts the medium-range electrostatic interactions with the environment (e.g., solvent).

  Tandiana, Cécile Sicard-Roselli, Nguyen-Thi Van-Oanh, Stephan Steinmann, Carine Clavaguéra To cite this version: Rika Tandiana, Cécile Sicard-Roselli, Nguyen-Thi Van-Oanh, Stephan Steinmann, Carine Clavaguéra. In-depth theoretical understanding of the chemical interaction of aromatic compounds with a gold nanoparticle. Physical Chemistry Chemical Physics, 2022, 24, pp.25327. 10.1039/d2cp02654f. hal-J o u r n a l Na me In-depth theoretical understanding of the chemical interaction of aromatic compounds with a gold nanoparticle Rika Tandiana a , Cécile Sicard-Roselli a , Nguyen-Thi Van-Oanh a , Stephan Steinmann b , Carine Clavaguéra, * a

Fig. 1

 1 Fig. 1 (a) Schematic representation of aromatic compounds adsorbed on Au 32 adopting flat configuration "F" (left) or perpendicular configuration "P" (right). (b) Aromatic molecules and their abbreviations.

Fig. 2

 2 Fig.2Uncorrected interaction energy calculated with LC-RECP/DZVP, SC-RECP/DZVP, and SC-RECP/TZVP for the various organic compounds. "P" stands for perpendicular.

Fig. 3

 3 Fig.3Interaction of substituted aromatic compounds with Au 32 adopting a flat configuration of the aromatic ring, along with the interaction energy (in kcal/mol, black color) and the charge transfer with ADCH scheme (in e -, blue color).

Fig. 4

 4 Fig. 4 BCPs calculated within the QTAIM framework, along with the values of local properties, for flat configuration of phenol (left). The interacting molecular orbitals of phenol and GNP, as obtained within CDA framework (right).

Fig. 5

 5 Fig. 5 Interaction of substituted aromatic compounds with Au 32 adopting perpendicular configuration of the aromatic ring, along with the interaction energy (in kcal/mol, black color) and the charge transfer with ADCH scheme (in e -, blue color).

Fig. 7

 7 Fig. 7 NCI analysis of the aromatic molecules adsorbed on Au 32 in a flat configuration, and the associated color code: from left to right, benzene, benzoic acid, acetophenone, ethylbenzoate, toluene, phenol, aniline, and thiophenol.

Fig. 8 Fig. 9

 89 Fig.8NCI analysis of the aromatic molecules adsorbed on Au 32 in a perpendicular configuration, see figure7for the color code: toluene, acetophenone, and benzoic acid

Fig. 11

 11 Fig. 11 The correlation of the respective energy decomposition terms with respect to the total energy for the various complexes: (top) BLW-EDA, and (bottom) SAPT.

Acknowledgements

We thank Dr. Dominik Domin for his valuable technical assistance. This collaborative work was supported by GDR 2035 Sol-vATE, funded by CNRS. This work was performed using HPC resources from the GENCI (CINES/IDRIS, Grant No. 2021-A0100806830).

L'

Supplementary Information

Detailed results for Fukui calculations, BSSE effects, interaction energies, geometries, charge transfer from different populations schemes, CDA and QTAIM analysis, IR calculated spectra, NCI analysis, and SAPT and BLW energy decomposition analysis are provided in Supplementary Information. Separate files for the coordinates of the entire series of compounds are also available.

Conflicts of interest

There are no conflicts to declare.


Nacira Abbas
email: nacira.abbas@inria.fr

Alexandre Bazin
email: alexandre.bazin@umontpellier.fr

Jérôme David
email: jerome.david@inria.fr

Amedeo Napoli
email: amedeo.napoli@loria.fr

Contributions to Link Key Discovery in RDF Datasets

Keywords: Linked Data, RDF, Link Key, Formal Concept Analysis, Pattern Structures

A link key between two RDF datasets D1 and D2 is a set of pairs of properties allowing to identify pairs of individuals, say x1 in D1 and x2 in D2, which can be materialized as a x1 owl:sameAs x2 identity link. There exist several ways to mine such link keys but no one takes into account the fact that owl:sameAs is an equivalence relation, which leads to the discovery of non-redundant link keys. Accordingly, in this paper, we present the link key discovery based on Pattern Structures (PS). PS output a pattern concept lattice where every concept has an extent representing a set of pairs of individuals and an intent representing the related link key candidate. Then, we discuss the equivalence relation induced by a link key and we introduce the notion of non-redundant link key candidate.

Introduction

In this position paper we are interested in data interlinking which goal is to discover identity links across two RDF datasets over the web of data [START_REF] Ferrara | Data Linking for the Semantic Web[END_REF][START_REF] Nentwig | A survey of current Link Discovery frameworks[END_REF]. The same real world entity can be represented in two RDF datasets by different subjects in RDF triples (subject,property,value) (instead of "object" usually used in RDF data we will use "value"). It is important to be able to detect such identities, for example using rules expressing sufficient conditions for two subjects to be identical. A link key takes the form of two sets of pairs of properties associated with a pair of classes. The pairs of properties express sufficient conditions for two subjects, from the associated pair of classes, to be the same. An example of a link key is ({(designation,title)},{(designation,title),(creator,author)},(Book,Novel)) which states that whenever an instance a of the class Book has the same (non empty) values for the property designation as an instance b of the class Novel for the property title (universal quantification), and that a and b share at least one value for the properties creator and author (existential quantification), then a and b denote the same entity, i.e., an owl:sameAs relation can be established between a and b.

A link key can be understood as a "closed set" in the sense that it is maximal w.r.t. the set of pairs of individuals to which it applies. This was firstly discussed in [START_REF] Atencia | Data interlinking through robust linkkey extraction[END_REF] and then extended in [START_REF] Atencia | Link key candidate extraction with relational concept analysis[END_REF]. Hence the question of relying on Formal Concept Analysis (FCA [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]) to discover link keys is straightforward as FCA is based on a closure operator. Then, given two RDF datasets, FCA is applied in [START_REF] Atencia | Link key candidate extraction with relational concept analysis[END_REF] to a binary table where rows correspond to pairs of individuals and columns to pairs of properties. The intent of a concept is a link key candidate which should be validated thanks to suitable quality measures. The extent of the concept is the set of identity links between individuals. Furthermore, a generalization of the former approach proposed in [START_REF] Abbas | Discovery of Link Keys in RDF Data Based on Pattern Structures: Preliminary Steps[END_REF] is based on pattern structures [START_REF] Ganter | Pattern Structures and Their Projections[END_REF] and takes into account different pairs of classes at the same time in the discovery of link keys.

Link key candidates over two RDF datasets have to generate different and maximal link sets. However it appears that two different link key candidates may generate the same link set. This means that there exists some redundancy between the two link key candidates, that they should be considered as equivalent and merged. This can be achieved by looking at owl:sameAs which is an equivalence relation stating that two individual should be identified. The owl:sameAs relation generates partitions among pairs of individuals that can be used to detect redundant link key candidates and thus reduce their number, i.e., two candidates relying on the same partition are declared as redundant and thus merged.

Here after we present the discovery of link key candidates within the framework of pattern structure. Then, we introduce the notion of non-redundant link key candidate based on the equivalence relation induced by a link key candidate. Finally, we discuss how these candidates can be merged to reduce the search space of link keys. This position paper is based on the two publications [START_REF] Abbas | Discovery of Link Keys in RDF Data Based on Pattern Structures: Preliminary Steps[END_REF][START_REF] Abbas | A Study of the Discovery and Redundancy of Link Keys Between Two RDF Datasets Based on Partition Pattern Structures[END_REF] where all details regarding the present approach are available.

Basics and Notations

RDF data Definition 1 (RDF dataset).

Let U be a set of IRIs (Internationalized Resource Identifier), B a set of blank nodes and L a set of literals. An RDF dataset is a set of triples

(s, p, v) ∈ (U ∪ B) × U × (U ∪ B ∪ L).
Given an RDF dataset D, we have the following particular sets: (i) For all (p, q) ∈ Eq, p(a) = q(b) and p(a) = ∅, (ii) for all (p, q) ∈ In \ Eq, p(a) ∩ q(b) = ∅. A link key expression k 1 = (Eq 1 , In 1 , (c 1 , c 2 )) is a "link key candidate" if:

I(D) = {s | ∃p, v (s, p, v) ∈ D} the set of individual identifiers, P (D) = {p | ∃s, v (s, p, v) ∈ D}
(iii) L(k 1 ) = ∅, (iv) k 1 is maximal i.e. there does not exist another link key expression k 2 = (Eq 2 , In 2 , (c 1 , c 2 )) such that Eq 1 ⊂ Eq 2 , In 1 ⊂ In 2 , and L(k 1 ) = L(k 2 ).

The number of link key expressions may be exponential w.r.t. the number of properties. Then link key discovery algorithms only consider link key candidates which are link key expressions generating at least one link and that are maximal w.r.t. the set of links they generate.

Link Key Discovery

Here after we assume that all link key expressions are defined on the same pair of datasets D 1 and D 2 w.r.t. one pair of classes, yielding link key expressions of the form k = (Eq, In, (c 1 , c 2 )). We show how link keys can be discovered within the formalism of pattern structures and then we discuss the notion of non-redundant link keys.

Example 1. Let us consider the pattern structure (G, (E, ), δ) displayed in Table 1. The details for building this table and the related PS lattice are given in [START_REF] Abbas | Discovery of Link Keys in RDF Data Based on Pattern Structures: Preliminary Steps[END_REF].

The rows termed "PS objects" correspond to the set of objects G of the pattern structure and include pairs of related instances. The set of descriptions (E, ) includes all possible pairs of properties preceded either by ∀ or ∃. The mapping δ relates a pair of instances (a, b) ∈ I(c 1 ) × I(c 2 ) to a description as follows: (i) δ(a, b) includes ∀(p, q) whenever p(a) = q(b) and p(a) = ∅, (ii) δ(a, b) includes ∃(p, q) whenever p(a) ∩ q(b) = ∅. Then the descriptions correspond to link key expressions (Eq, In) w.r.t. the pairs of classes (c 1 , c 2 ). It should be noticed that it is possible to simultaneously work with several pairs of classes as explained in [START_REF] Abbas | Discovery of Link Keys in RDF Data Based on Pattern Structures: Preliminary Steps[END_REF].

We have that δ(a 1 , b 1 ) = {∃(p 1 , q 1 ), ∃(p 2 , q 2 )} because p 1 (a 1 ) ∩ q 1 (b 1 ) = ∅ and p 2 (a 1 ) ∩ q 2 (b 1 ) = ∅ while δ(a 2 , b 1 ) = {∃(p 1 , q 1 )} because p 1 (a 2 ) ∩ q 1 (b 1 ) = ∅. Then δ(a 1 , b 1 ) δ(a 2 , b 1 ) = {∃(p 1 , q 1 )} and thus δ(a 2 , b 1 ) δ(a 1 , b 1 ). This can be read in the pattern concept lattice where the pattern concept pc 5 is subsumed by the pattern concept pc 4 , i.e., the extent of pc 5 {(a 1 , b 1 ), (a 2 , b 2 ), (a 3 , b 3 )} is included in the extent of pc 4 {(a 1 , b 1 ), (a 2 , b 1 ), (a 2 , b 2 ), (a 3 , b 3 )}, while the intent {∃(p 1 , q 1 )} of pc 4 is included in the intent of pc 5 , {∃(p 1 , q 1 ), ∃(p 2 , q 2 )}.

The set of all pattern concepts is organized within the pattern concept lattice called lkps-lattice and displayed in Fig. 2. Moreover, all potential link key candidates are lying in the intents of the pattern concepts in the lattice. The corresponding set of link key candidates is denoted by lkc.

Let us consider the lkps-lattice and pc = (L(k), k) a pattern concept, where the extent L(k) corresponds to the set of links generated by k, and the intent k corresponds to a link key candidate. Let I denotes the set of instances I = I(c 1 ) ∪ I(c 2 ) and the binary relation

k ⊆ I × I such as (a, b) ∈ L(k) → a k b.
The interpretation of a k b is: "k states that there exists a owl:sameAs relation between a and b". Actually k is an equivalence relation based on the fact that owl:sameAs itself is an equivalence relation. We say that k induces the equivalence relation k over I. Moreover k forms a partition over I where each element of this partition is an equivalence class. In fact the k equivalence relation will PS objects (g) descriptions (δ(g)) (a1, b1) {∃(p1, q1), ∃(p2, q2)} (a1, b2) {∃(p2, q2)} (a2, b1) {∃(p1, q1)} (a2, b2) {∃(p1, q1), ∃(p2, q2)} (a3, b3) {∀(p1, q1), ∃(p1, q1), ∃(p2, q2)} (a4, b4) {∀(p3, q3), ∃(p3, q3)} (a4, b5) {∀(p4, q4), ∃(p4, q4)} (a5, b4) {∀(p4, q4), ∃(p4, q4)} (a5, b5) {∀(p3, q3), ∃(p3, q3)} Table 1. The pattern structure related to link key discovery over c1 and c2 introduced in Fig. 1. help us to build more concise set of link key candidates since it allows to identify non-redundant link key candidates termed nr-lkc. A link key candidate k 1 is a nr-lkc in lkc if there is no other candidate k 2 in lkc such that k1 and k2 form the same partition. Otherwise, k 1 is redundant. In Fig. 2, it can be observed that k3 and k4 form the same partition, namely {(a 1 , b 1 , a 2 , b 2 ), (a 3 , b 3 )} (it should be noticed that singletons are omitted for the sake of readability). Then the link key candidates k 3 and k 4 are redundant. By contrast, k 1 is a nr-lkc because there is no other candidate k in lkc such that k1 and k form the same partition.

Let us briefly explain how k3 and k4 are inducing the same partition, namely {(a ). The same thing applies when we consider k 4 instead of k 3 . This intuitively shows how k3 and k4 are inducing the same partition.

One main straightforward application of identifying nr-lkc is the ability to reduce the search space of link keys since the set of nr-lkc is included in lkc. Indeed, this can be seen as a refinement where redundant link key candidates inducing the same partition are merged. For example, since k3 and k4 form the same partition, then, k 3 and k 4 can be merged into a nr-lkc k 34 = {k 3 , k 4 }. Among the perspectives is to consolidate the theory and practice of link key discovery based on partition pattern structures initially introduced for mining functional dependencies in [START_REF] Baixeries | Characterizing functional dependencies in formal concept analysis with pattern structures[END_REF].

  the set of property identifiers, C(D) = {c | ∃s (s, rdf:type, c) ∈ D} the set of class identifiers, where a triple (s, rdf:type, c) means that the subject s is an instance of the class c. I(c) = {s | (s, rdf:type, c) ∈ D} the set of instances of c ∈ C(D), p(s) = {v | (s, p, v) ∈ D} is the set of values related to s through p.

Fig. 1 .

 1 Fig. 1. On the left, dataset D1 includes instances of class c1 while on the right dataset D2 includes instances of class c2.

I(c 1 ) 1 { 3 { 4 {(a 1 5 {(a 3 , b 3 )} k 6 = 6 ∅P (D 1 ) 7 Fig. 2 .

 113415366172 Fig.2. The pattern concept intents in the pattern concept lattice lkps-lattice include the complete set of link key candidates.

  1 , b 1 , a 2 , b 2 ), (a 3 , b 3 )}. The extent of k 3 in lkps-lattice is given by {(a 1 , b 1 ), (a 1 , b 2 ), (a 2 , b 2 ), (a 3 , b 3 )}. By transitivity and symmetry of owl:sameAs, we have that (a 1 , b 2 ) and (b 2 , a 2 ) yields (a 1 , a 2 ), then (a 2 , a 1 ) and (a 1 , b 1 ) yields (a 2 , b 1 ), and finally (b 1 , a 2 ) and (a 2 , b 2 ) yields (b 1 , b 2 ) and the complete graph between (a 1 , a 2 , b 1 , b 2