Corinne Parat
email: corinne.parat@univ-pau.fr

Laurent Authier

Alain Castetbon

David Aguilar

Encarna Companys

Jaume Puy

Josep Galceran

Martine Potin-Gautier

Free Zn 2+ determination in natural freshwaters of the Pyrenees: towards on-site measurements with AGNES

Keywords: FIAM, geochemical model, heavy metals, screen-printed electrodes, speciation

Environmental context

Introduction

The free Zn 2+ ion concentration in environmental aqueous systems is an important factor in determining Zn deficiency or toxicity to organisms as the element in this form is directly bioavailable. Many analytical techniques like ion exchange methods [START_REF] Schneider | Adaptation of the ion exchange method for the determination of the free ionic fraction of cadmium in solution[END_REF] , Donnan Membrane Technique (DMT) [START_REF] Temminghoff | Determination of the chemical speciation of trace metals in aqueous systems by the Wageningen Donnan Membrane Technique[END_REF][START_REF] Weng | Strategies in the application of the Donnan membrane technique[END_REF] or Permeation Liquid Membrane (PLM) [START_REF] Gramlich | The use of permeation liquid membranes for free zinc measurements in aqueous solution[END_REF] have been developed to determine the free metal ion concentrations in natural samples. These methods agree well with speciation models (WHAM or MINTEQ), [START_REF] Allison | MINTEQA2/PRODEFA2, A geochemichal assessment model for environmental systems: version 3.0 user's manual[END_REF][START_REF] Gustafsson | Modeling Salt-Dependent Proton Binding by Organic Soils with the NICA-Donnan and Stockholm Humic Models[END_REF][START_REF] Cornu | Cadmium speciation assessed by voltammetry, ion exchange and geochemical calculation in soil solutions collected after soil rewetting[END_REF][START_REF] Mueller | Trace metal speciation predictions in natural aquatic systems: incorporation of dissolved organic matter (DOM) spectroscopic quality[END_REF] but require complementary equipment which cannot be moved into the field for on-site measurements. Commercial ion selective electrodes (ISE) are of particular relevance for trace metal studies, [START_REF] Bakker | Carrier-Based Ion-Selective Electrodes and Bulk Optodes. 1. General Characteristics[END_REF][START_REF] Bakker | Peer Reviewed: The New Wave of Ion-Selective Electrodes[END_REF] but their commercial versions lack the required sensitivity and cannot measure Zn. During the last few years, an electroanalytical technique called Absence of Gradients and Nernstian Equilibrium Stripping (AGNES) [START_REF] Galceran | AGNES: a new electroanalytical technique for measuring free metal ion concentration[END_REF] has been developed to determine free Zn 2+ concentration [START_REF] Companys | Humic acid complexation to Zn and Cd determined with the new electroanalytical technique AGNES[END_REF][START_REF] Galceran | AGNES: A technique for determining the concentration of free metal ions. The case of Zn(II) in coastal Mediterranean seawater[END_REF][START_REF] Zavarise | Application of the new electroanalytical technique AGNES for the determination of free Zn concentration in river water[END_REF][START_REF] Chito | Determination of free Zn2+ concentration in synthetic and natural samples with AGNES (Absence of Gradients and Nernstian Equilibrium Stripping) and DMT (Donnan Membrane Technique)[END_REF] . Typically, it has been implemented with the hanging mercury drop electrode (HMDE) and has been used, amongst other applications, to determine free Zn 2+ or Pb 2+ concentrations in sea [START_REF] Galceran | AGNES: A technique for determining the concentration of free metal ions. The case of Zn(II) in coastal Mediterranean seawater[END_REF][START_REF] Díaz-De-Alba | Lead electrochemical speciation analysis in seawater media by using AGNES and SSCP techniques[END_REF] and river [START_REF] Zavarise | Application of the new electroanalytical technique AGNES for the determination of free Zn concentration in river water[END_REF][START_REF] Chito | Determination of free Zn2+ concentration in synthetic and natural samples with AGNES (Absence of Gradients and Nernstian Equilibrium Stripping) and DMT (Donnan Membrane Technique)[END_REF] waters. Recent developments of AGNES [START_REF] Aguilar | Non-purged voltammetry explored with AGNES[END_REF][START_REF] Aguilar | Determination of free metal ion concentrations with AGNES in low ionic strength media[END_REF][START_REF] Parat | Direct determination of free metal concentration by implementing stripping chronopotentiometry as the second stage of AGNES[END_REF] are making the possibility of on-site measurements realistic which would avoid numerous problems that can potentially occur during sampling and sample handling of natural solutions (contamination, changes in pH and temperature, loss by adsorption, etc). Obviously, the HMDE is poorly adapted for on-site studies. Consequently, the application of AGNES has been undertaken with thin film mercury screenprinted electrodes (SPE) which represent an ideal alternative to the use of the HMDE. [START_REF] Parat | Direct determination of free metal concentration by implementing stripping chronopotentiometry as the second stage of AGNES[END_REF][START_REF] Parat | Determination of free metal concentrations using screen-printed electrodes and AGNES with the charge as response function[END_REF] These sensors have a very small size (9.6 mm 2 ) and use a thin mercury film thickness (200 nm), which make them easy to deploy on-site. Unlike the HMDE, SPEs do not need any N 2 pressure and, thus, the transport of N 2 bottles to the field, which could be very problematic, is avoided. A recent work has demonstrated the feasibility of measuring free Zn 2+ and Cd 2+ in non-deaerated synthetic solutions provided that the changes in speciation, due to the reduction of the dissolved oxygen, is similar in the calibration and sample solutions [START_REF] Aguilar | Non-purged voltammetry explored with AGNES[END_REF] . Another challenge presented by on-site analysis is measurements made in freshwaters of low ionic strength. The analytical signal obtained using AGNES is affected by low ionic strength media [START_REF] Aguilar | Determination of free metal ion concentrations with AGNES in low ionic strength media[END_REF] . Finally, the last variant of AGNES, called AGNES-SCP, where the reoxidation stage consists of stripping chronopotentiometry (SCP) (also called potentiometric stripping analysis (PSA)), has shown an important improvement as metal interferences can be avoided [START_REF] Parat | Direct determination of free metal concentration by implementing stripping chronopotentiometry as the second stage of AGNES[END_REF][START_REF] Parat | Determination of free metal concentrations using screen-printed electrodes and AGNES with the charge as response function[END_REF] . The objective of this work was to determine free Zn 2+ concentration in natural freshwaters from some rivers of the Pyrenees (Garonne, Gave de Cauterets and Gave de Pau) by developing a new analytical strategy using AGNES-SCP. In this work, two aspects limiting the on-site applicability of electrochemical techniques to freshwater samples are tackled: the low ionic strength of the media, and the presence of dissolved oxygen. For the first time using AGNES, the developed methodology has been applied on-site in a highly contaminated natural freshwater sample of the Gave de Cauterets. This strategy has been validated by comparing results with measurements performed on the same samples by applying the purged classical AGNES methodology in the laboratory. The laboratory results have been corroborated with theoretical estimations carried out with Visual Minteq modelling software [START_REF] Gustafsson | Visual Minteq, version 3.0[END_REF] .

Experimental

Reagents

Zn 1000 mg L -1 stock solution was obtained from Merck. KNO 3 (Trace Select), HNO 3 (69-70%, Baker Instra-Analysed for trace metal analysis), NaOH (Baker Analysed), HCl (Baker Instra-Analysed for trace metal analysis) were purchased from Sigma Aldrich. Ultrapure milli-Q water (resistivity 18.2 MΩ cm) was employed in all the experiments. Purified watersaturated nitrogen N 2 (50) was used for deaeration and blanketing of solutions. Synthetic river water was prepared from sodium hydrogen carbonate (Scharlau), magnesium sulphate (Merck, Pro Analysis), calcium chloride (Merck, Pro analysis) and potassium nitrate (Sigma Aldrich, Trace Select). A stock solution of synthetic river water was prepared as follows: 10 -2 mol L -1 NaHCO 3 , 10 -3 mol L -1 MgSO 4 •7H 2 O, 2×10 -3 mol L -1 CaCl 2 •2H 2 O and 5×10 -4 mol L -1 KNO 3 , which corresponds to an ionic strength of 0.0192 mol L -1 . For each experiment with synthetic river water, the stock solution was diluted to obtain a solution having a composition close to the river sample (Erreur ! Source du renvoi introuvable.). To avoid voltammetric problems derived from the low ionic strengths of the samples [START_REF] Aguilar | Determination of free metal ion concentrations with AGNES in low ionic strength media[END_REF] , the solutions (both synthetic and freshwater) were spiked with KNO 3 up to 0.01 mol L -1 , to give a conductivity close to 1500 µS cm -1 . At this ionic strength, no problems derived from low supporting electrolyte are expected. Using Visual Minteq, it has been observed that this addition does not alter the speciation of the river samples. The pH was adjusted with 0.01 mol L -1 NaOH or 0.01 mol L -1 HNO 3 to reach the pH of the natural river sample. Water samples were filtered on-site with 0.45 µm acetate cellulose filters by using Nalgene polysulfone, a reusable complete filter unit (from VWR) and a Mityvac hand vacuum pump (model MV8010).

Equipment

Major cation concentrations were obtained with an Inductively Coupled Plasma Atomic Emission Spectrometer (ICP-AES) (Horiba Jobin Yvon, Activa-M). Trace elements were obtained with an Inductively Coupled Plasma Mass Spectrometer (ICP-MS) (Agilent 7500ce). Major anions were measured with an ion chromatograph (Dionex DX-120). Dissolved organic carbon (DOC) was obtained with a Total Organic Carbon Analyzer (Shimadzu TOC-V CSN). Dissolved oxygen was measured with a multi-parameter analyser Consort C535. Temperature, pH and conductivity were measured with a multi-parameter analyser WTW 340i. Voltammetric measurements were performed with an Eco Chemie µ-Autolab III potentiostat attached to a Metrohm 663 VA Stand and to a computer by means of the GPES 4.9 (Eco Chemie) software package. The auxiliary electrode was a glassy carbon electrode. The reference electrode was a DRIREF-5 (3 mol L -1 KCl) purchased from World Precision Instrument. All potentials were given versus this reference electrode. Glass jacketed cells, provided by Metrohm, were used to maintain the temperature constant (generally at 20°C). SPE were prepared using a commercial ink electrodag PF-407A (Acheson Colloids). The electrodes were screen-printed on 1 mm-thick polystyrene support for serigraphy (Sericol) (Figure 1). After a drying step (1 hour at room temperature) and a curing step (1 hour at 60°C), an insulating layer was spread manually over the conductive track, leaving a working disk area of 9.6 mm 2 [START_REF] Parat | Determination of labile cadmium using a screen-printed electrode modified by a microwell[END_REF] . A thin layer of mercury was deposited onto the electrode surface for trace metal detection. The mercury deposition on the SPE was carried out using an acetate buffer solution (0.2 mol L -1 , pH = 4.6) prepared from acetic acid (Trace select), sodium acetate trihydrate (Trace select) and 0.83 mmol L -1 Hg(NO 3 ) 2 (all obtained from J.T. Baker). First, the working surface of the electrode was conditioned by applying 4 cycles of cyclic voltammetry (CV) using the following conditions: potential range from -0.1 V to +0.8 V, scan rate 100 mV/s, step potential 2.4 mV. The Hg film was then deposited at -1.0 V, with stirring until the charge associated with the deposited mercury (Q Hg ) reached 25 mC.

Sampling and on-site analyses

Two rivers in the Pyrenees have been studied in this work (Figure 2): the Garonne river, which flows in Spain downstream from a Zn mining area and enters into France, and the Gave de Pau which is supplied by a stream, the Gave de Cauterets, also located downstream from a Zn mining area, and continues until Pau (France). The sampling campaigns were carried out on two different dates: April 2012 with a high water level in the Gave de Pau (due to the plentiful rainfalls during the month of April [23] ) and in May 2012 with a low water level. At all sampling places, temperature, pH, conductivity and dissolved oxygen were measured directly in the river. 250 mL of filtered water samples have been acidified with HNO 3 at 2% and stored at 4°C in new polystyrene bottles to measure the concentrations of major cations and trace metals. 250 mL of filtered water sample has been kept without acidification for carbon analysis, anion analysis and AGNES experiments.

Free Zn 2+ determination

The determination of the free Zn 2+ using AGNES-SCP procedure [START_REF] Parat | Direct determination of free metal concentration by implementing stripping chronopotentiometry as the second stage of AGNES[END_REF] consists of two conceptual stages. Along the first (deposition) stage, the metal ion Zn 2+ from the solution is reduced to Znº until attainment of a special situation of Nernstian equilibrium and absence of gradients in the concentration profiles [START_REF] Galceran | AGNES: a new electroanalytical technique for measuring free metal ion concentration[END_REF] . This equilibrium is achieved by applying a potential E 1 more negative than the standard formal potential of the couple Zn 2+ /Zn 0 , E 0 ', for a sufficiently long time t 1 . These conditions imply that identical analytical signals (in the second stage) are obtained for deposition times longer than a certain minimum t 1 .

The Nernst equation allows the concentration ratio at each side of the mercury electrode, also called gain Y, to be calculated as (Eq. 1):

0 0' 1 M - exp ( ) M n nF Y E E RT + ⎡ ⎤ ⎡ ⎤ ⎣ ⎦ = = - ⎢ ⎥ ⎡ ⎤ ⎣ ⎦ ⎣ ⎦ Eq. 1
where n is the number of exchanged electrons, F is the faraday constant, R the gas constant and T the temperature.

The deposition potential E 1 corresponding to a given gain Y can be determined from the peak potential of a differential pulse polarogram (DPP) [START_REF] Galceran | AGNES: a new electroanalytical technique for measuring free metal ion concentration[END_REF] . The higher the gain Y, the higher the sensitivity of the AGNES measurement. However, higher gains will require longer electrodeposition times to reach Nernstian equilibrium. Consequently, the chosen deposition potential will correspond to the lowest gain that allows obtainment of a well-shaped peak.

The goal of the second stage of AGNES-SCP is to measure the concentration of the reduced metal Mº inside the mercury amalgam, e.g. by applying a constant oxidizing stripping current, generally between 1 and 10 µA [START_REF] Parat | Direct determination of free metal concentration by implementing stripping chronopotentiometry as the second stage of AGNES[END_REF] . The analytical signal is the time taken for the analyte reoxidation (transition time, τ). SCP conditions of full depletion allow measuring the total faradaic charge Q which is proportional to the free metal ion concentration [M 2+ ] according to Eq. 2.

0 2 2 Hg Hg Q M M M Q nFV nFV Y h + + ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ = = = ⎣ ⎦ ⎣ ⎦ ⎣ ⎦ Eq. 2
where V Hg is the volume of deposited mercury and h Q is the slope of the calibration plots.

Speciation models

The geochemical modelling program Visual MINTEQ, version 3.0 [START_REF] Gustafsson | Visual Minteq, version 3.0[END_REF] (using the standard databases) was used to predict metal speciation in the investigated rivers. The following inputs were provided: pH, temperature, and total concentrations for Ca 2+ , Na + , K + , Mg 2+ , Mn 2+ , NO 3 -, SO 4 2-, Cl -, CO 3 2-, total Zn and DOC. The NICA-Donnan model was used to describe the formation of metal-DOM (dissolved organic matter) complexes. It was assumed that the ratio of active DOM to DOC (dissolved organic C) was 1.65 and that 100% of the active DOM was fulvic acids (FA) [START_REF] Sjöstedt | Chemical Equilibrium Modeling of Organic Acids, pH, Aluminum, and Iron in Swedish Surface Waters[END_REF] .

Results and discussion

General physicochemical analyses of river waters

As shown in Table 1, physicochemical properties show little difference between both rivers. The pH of the samples were between 7.25 and 7.77 in the Garonne,with a slight increase observed from upstream in the Gave de Pau (7.35 in Soulom) to downstream (8.16 in Laroin). Dissolved oxygen does not show strong variations with an average concentration of 13 mg L - 1 , except in Pointis de Rivière in the Garonne (6.25 mg L -1 ). This low value can be explained by the presence of stagnant water. Conductivity recorded at the different places appeared relatively low with values between 78 and 226 µS cm -1 . An increase is observed from upstream to downstream related to the simultaneous increase of the concentrations of cations (Ca 2+ , K + , Na + , Mg 2+ ) and anions (Cl -, NO 3 -, SO 4 2-). The DOC concentrations vary from 0.7 to 3.7 mg L -1 except in Baudreix where the value is higher (6.8 mg L -1 ), probably due to human activity in the leisure area. and Liat (73 µg L -1 ) in the Garonne, and Soulom (136 µg L -1 ) in the Gave de Pau. In both rivers, a dilution phenomenon is clearly observed downstream from the mines due to many tributaries. Stable values around 5 µg L -1 are reached in the most downstream places, probably close to the geochemical background concentration.

Garonne

Gave&de& Pau

Optimization of AGNES-SCP experimental conditions for on-site analyses

Since total Cd and Pb concentrations were found to be lower than the LOD, only free Zn 2+ was determined. The optimization of the technique was performed in the laboratory with synthetic river water samples before being applied to natural samples in the laboratory and on-site.

Low ionic strength effects on AGNES

The low ionic strength reflected by the conductivity values found in the river (between 78 and 226 µS cm -1 ) can be problematic when working with electrochemical techniques. As shown in Figure 3, for a common fixed deposition potential (E 1 = -1.08V) applied to the purged solution, analytical signal decreases when increasing the sample conductivity. This can be rationalized from Nernst equation, eqn. 1 written [START_REF] Aguilar | Determination of free metal ion concentrations with AGNES in low ionic strength media[END_REF] as:

2 0 2 0 1 Zn - Zn Zn exp ( ) nF E E RT γ + + ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ = - ⎣ ⎦ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ Eq. 3
where Eº is the standard redox potential (which is constant at a given temperature). When the ionic strength increases, the activity coefficient decreases, so the number of accumulated moles of Znº and the analytical signal decrease. The analysis of low ionic strength by electrochemical techniques can be hindered by the ohmic drop in the solution. At high ionic strength, the application of a potential difference between the electrodes results in this potential drop being spatially localized between the working electrode and the adjacent solution. At low ionic strength, the applied potential accounts for the drop of potential at the electrode interface plus the ohmic drop across the solution due to the non-negligible resistance of the solution. This impacts most electroanalytical techniques, because the potential drop at the electrode interface does not coincide with the nominal applied potential [START_REF] Aguilar | Determination of free metal ion concentrations with AGNES in low ionic strength media[END_REF] . Notice, however, that the ohmic drop at the end of the deposition stage of AGNES in purged solutions is negligible due the low current at equilibrium (arising from the traces of oxygen), but can be important in non-deaerated solutions.

The impact of changing ionic strength (due to changes in the activity coefficients) is pronounced for a KNO 3 concentration lower than 10 -2 mol L -1 which corresponds to a conductivity lower than 1200 µS cm -1 . This means that AGNES-SCP will be particularly sensitive in the river samples where the conductivity measured in the rivers is around 100 µS cm -1 (because the ionic strength is not accurately known). For this reason, the conductivity of the natural freshwater sample has been fixed to avoid voltammetric problems in AGNES-SCP derived from the low ionic strengths. Thus, both solutions, synthetic and natural freshwaters, were spiked with KNO 3 up to 10 -2 mol L -1 where no problems derived from low supporting electrolyte are expected. Simulations made with Visual Minteq and the estimated water composition have shown that the free Zn 2+ concentration was not affected when adding this amount of KNO 3 (data not shown).

Oxygen influence during AGNES deposition step

In non-purged solutions, the pH at the surface of the electrode is higher than that of the bulk solution, due to the important reduction of O 2 [START_REF] Aguilar | Non-purged voltammetry explored with AGNES[END_REF] . The presence of oxygen hinders the standard AGNES application by preventing the achievement of absence of gradients in the solution concentration profiles by the end of the preconcentration step. Instead, a steady-state situation is reached where the metal concentration at the surface of the electrode (due to the speciation at a higher pH) is depleted with respect to the bulk concentration. Thus, the aimed preconcentration gain Y (referred to bulk concentrations) might not be achieved, but rather be far smaller [START_REF] Aguilar | Non-purged voltammetry explored with AGNES[END_REF] . Additionally, the steady-state consumption of O 2 implies an increase of the residual current and a concomitant decrease of the actual applied potential due to ohmic drop. pH effects derived from the oxygen interference can be avoided with an effective buffer that compensates for the OH -production at the electrode surface without any change in the metal speciation. Alternatively, calibration solutions in which the steady-state depletion of the metal is similar to the depletion of the samples may be used. The latter is the strategy followed in this work. A calibration has been performed in a synthetic river solution in which the chemical composition is close to the one of the river sample in terms of pH and geochemical composition. In this way, we ensure that changes in calibration and measuring samples due to the presence of oxygen are similar.

The determination of the required potential for a given gain has been obtained empirically searching for a sufficient analytical signal. Thus, using E 1 -values between -1.165 and -1.190 V, the gain was enough for a reliable measurement of Zn in Pyrenees river samples.

Oxygen influence during stripping step

In SCP, the analytical signal is the time taken for the analyte reoxidation (transition time, τ) while a constant oxidizing stripping current is applied [START_REF] Town | Fundamental features of metal ion determination by stripping chronopotentiometry[END_REF] . However, this current corresponds to the sum of the imposed stripping current (I s ) and the oxidants current (I ox ) due to oxidizing agents (e.g. oxygen) present in the solution [START_REF] Aguilar | Non-purged voltammetry explored with AGNES[END_REF] . In classical analyses with purging, I ox is negligible in front of the I s (10 µA) usually imposed with AGNES-SCP [START_REF] Parat | Direct determination of free metal concentration by implementing stripping chronopotentiometry as the second stage of AGNES[END_REF] . In non-purged solutions, it has been shown that interferences due to oxygen during the stripping stage could be minimized by using specific stripping techniques such as square wave anodic stripping voltammetry (SWASV) with high frequency [START_REF] Tercier | In situ voltammetric measurement of trace elements in lakes and oceans[END_REF] or stripping chronopotentiometry (SCP) with sufficiently high stripping currents [START_REF] Parat | Direct determination of free metal concentration by implementing stripping chronopotentiometry as the second stage of AGNES[END_REF] . However, in AGNES-SCP, a large oxidizing current can induce a fast stripping step which can lead to a truncated signal. To avoid this, a chemical stripping (SCP chem ) was applied where the reoxidation is only performed through oxidants current I ox (mainly due to oxygen) present in the solution without imposing any external current (i.e. I s =0) [START_REF] Jagner | Potentiometric stripping analysis[END_REF][START_REF] Parat | Determination of trace metal speciation parameters by using screen-printed electrodes in stripping chronopotentiometry without deaerating[END_REF] . The accumulated charge Q, in this case, can be computed as (Eq. 3):

Ox Q I τ = - Eq. 4
I Ox , obtained at the end of the deposition stage with the solution in quiescent conditions, appeared to be stable with time, indicating that a steady state for the entire system, including the transport of O 2 towards the electrode, was reached. It has been shown that either Q or τ were proportional to the free metal concentrations at the electrode surface [START_REF] Parat | Determination of free metal concentrations using screen-printed electrodes and AGNES with the charge as response function[END_REF] .

AGNES-SCP implementation in the present work

When working with non-deaerated solutions, the deposition potential needs to be very negative, because of the decrease in metal concentration at the electrode surface. This is due to the reaction of the free metal with the OH -species formed from the O 2 reduction at the electrode surface [START_REF] Aguilar | Non-purged voltammetry explored with AGNES[END_REF] . Using E 1 -values between -1.165 and -1.190 V, the gain was enough for a reliable measurement of the metal as explained below. Chemical stripping has been used during the second stage of AGNES-SCP to obtain a wellshaped peak. In order to avoid confusion with classical SCP using a constant stripping current, this new method will be called AGNES-SCP chem .

As discussed below, calibration of AGNES was performed using synthetic river waters whose characteristics were close to the ones of the Gave de Pau river samples in terms of pH and geochemical composition. In this way, we ensure that changes in calibration and measuring samples due to the presence of oxygen are similar. A typical calibration curve is presented in Figure 4.

Temperature effect on AGNES-SCP chem method

The influence of temperature on AGNES-SCP chem was evaluated in a non-purged solution (Figure 5). The analytical signal (τ) increased around 3.7 ms with each increase of 1 ºC. This evolution results from: i) the decrease of the dissolved oxygen concentration when temperature increases (Table 1). Lower I Ox values correspond to slower stripping processes, leading to longer τ; ii) the dependence of the E 0 ' potential with temperature. For a fixed deposition potential, the increase in temperature in this system leads to higher accumulations and analytical signals as expected from the endothermic nature of Zn 2+ reduction [START_REF] Harris | Quantitative Chemical Analysis[END_REF] . So, the temperature has to be carefully controlled when performing AGNES with Zn. All the experiments in the laboratory were performed with a thermostated bath at 20 ºC, except the on-site measurements and on-site calibrations, which were performed at the natural river temperature.

Interferences of Cu with Zn

In multicontaminated systems, a high concentration of metals can be accumulated in the mercury amalgam, so that intermetallic compounds may form [START_REF] Town | Stripping chronopotentiometry at scanned deposition potential (SSCP). Part 5. Features of multi-metal systems[END_REF][START_REF] Chito | The Impact of Intermetallic Compounds CuxZn in the Determination of Free Zn2+ Concentration with AGNES[END_REF] . This phenomenon arises when Cu and Zn concentrations are sufficiently high so that the solubility of the intermetallic compounds in mercury is exceeded. Figure 6 shows how the analytical signal was not affected by the presence of Cu in the solution up to a concentration of 2 µg L -1 (well above Cu concentration in the river samples).

Limit of detection and limit of quantification

The limit of detection (LOD) has been statistically determined from the calibration curve obtained from 12 calibration points in a synthetic river solution at pH 7.9 with AGNES-SCP chem without purging according to Eq. 4 [START_REF] Inczédy | Compendium of analytical nomenclature -Definitive rules[END_REF] :

LOD = (b + k S b ) / m Eq. 5
where k = 3, b is the intercept of the regression line, S b is the intercept standard deviation of the regression line and m is the slope of the calibration graph. The quantification limit (LOQ) was calculated with the same equation as for the detection limit, but with k = 10.

For each Zn concentration, three replicates were performed at three different deposition times to be sure that AGNES conditions are fulfilled. Thus, by using a deposition potential of -1.165V, a LOD of 0.6 µg L -1 and a LOQ of 0.9 µg L -1 have been obtained. If necessary, more negative deposition potentials (which require longer deposition times) could be used to detect lower free Zn 2+ concentrations.

In lab determination of free Zn 2+ concentration in freshwaters

The free Zn 2+ concentrations were determined in the laboratory in different samples taken from the Gave de Pau and Garonne rivers in May 2012 following the non-purged methodology previously described. Calibration was performed in a synthetic river water whose characteristics were close to the ones of the considered river sample [START_REF] Aguilar | Non-purged voltammetry explored with AGNES[END_REF] . Table 2 shows the retrieved free Zn 2+ concentrations applying E 1 = -1.165 V, t 1 = 300-400 s at 20ºC. The proportion of free Zn 2+ determined in the river is very high for all the locations, ranging from 72 to 100 %, in comparison to previous studies carried out with river waters [START_REF] Chito | Determination of free Zn2+ concentration in synthetic and natural samples with AGNES (Absence of Gradients and Nernstian Equilibrium Stripping) and DMT (Donnan Membrane Technique)[END_REF][START_REF] Korfali | Speciation of metals in sediment and water in a river underlain by limestone: role of carbonate species for purification capacity of rivers[END_REF][START_REF] Cheng | Comparison of zinc complexation properties of dissolved natural organic matter from different surface waters[END_REF] . These results are consistent with the low levels of dissolved organic matter found (around 3 mg L -1 ) and low pH (pH < 8). Calculations of metal speciation show that as pH and carbonates increase, the concentrations of free ions decrease because of the increased complexation with carbonate species and fulvic acids [START_REF] Tipping | Modelling the chemical speciation of trace metals in the surface waters of the Humber system[END_REF] .

Using the geochemical data measured for each sample, an estimation of the free concentration was performed with Visual Minteq. Figure 7 shows that a good correlation is observed between the experimental results obtained with AGNES-SCP chem and the ones computed from Visual Minteq which validates the AGNES-SCP chem method applied in natural water sample without purging. These results confirm the absence of Cu interferences (consistent with the low Cu concentration, Table 2) and agree well with the low conductivity (<200 µS cm -1 ) and low organic matter contents indicative of low Zn complexation capacity (Table 1).

On-site free Zn 2+ measurements

On-site measurements were performed in the Gave de Cauterets at Soulom (France). In April 2012, the pH of the river was 7.8, T = 6ºC and conductivity 154 µS cm -1 . All the material was deployed in the field and plugged into a portable battery if necessary. The collected sample was filtered on-site at 0.45 µm. An aliquot of the sample was acidified at pH 1.5 for ICP-AES analysis in laboratory. Another fraction of the sample was spiked with KNO 3 up to 0.01 mol L -1 for electrochemical analyses. The resulting free Zn 2+ concentration found on site was 374 ± 54 µg L -1 . In order to corroborate these results, further classical AGNES-SCP were performed in the laboratory, purging with a mixture of N 2 /CO 2 in order to fix the pH in the most natural way possible without altering the speciation of the sample [START_REF] Zavarise | Application of the new electroanalytical technique AGNES for the determination of free Zn concentration in river water[END_REF] . Since there is no interference from oxygen (no pH shift close to the electrode), a more positive potential could be used (E 1 = -1.065 V, t 1 = 300-500 s) and a 10 µA stripping current was applied. The calibration was performed in a KNO 3 0.01 mol L -1 solution at T = 6ºC. Given that, in purged samples, there is no need for the calibration to be at the same pH as the sample, pH 5 was selected to minimize Zn hydrolysis. The free Zn 2+ concentration retrieved was 345 ± 37 µg L - 1 and appeared in good agreement with the previous results obtained on-site.

The results measured in Soulom show huge differences in total Zn concentrations between April 2012 (647 µg L -1 ) and May 2012 (136 µg L -1 ), but also the free Zn 2+ proportion: in May, all Zn was free, whereas only 58 % of the total Zn was free in April 2012. These differences could be explained by the plentiful rainfalls during the month of April [23] which induced a higher water level in the Gave de Pau. These events led to a flooding of the old mines and, thus, to a high release of other components able to complex Zn, such as carbonates and organic matter [START_REF] Tipping | Modelling the chemical speciation of trace metals in the surface waters of the Humber system[END_REF] . This is supported by the highest conductivity being recorded in April (154 µS cm -1 ), relative to that in May (78 µS cm -1 ).

Conclusions

A new methodology has been developed to measure on-site free Zn 2+ in non-purged river samples of the Pyrenees with AGNES-SCP chem . The use of screen-printed electrodes appeared very suitable for this purpose as they could be easily deployed on site. Difficulties related to these measurements were removed by taking some precautions: i) a calibration in a synthetic solution where the composition is similar to the one of the sample; ii) calibration and sample analyses performed in the same conditions of pH and temperature; iii) an ionic strength fixed by an addition of KNO 3 0.01 mol L -1 to avoid anomalous voltammetric responses and ionic strength uncertainties. Free Zn 2+ measurements of samples taken from different locations in the Pyrenees rivers have been performed in the laboratory to check the suitability of the AGNES-SCP chem methodology. Observed free Zn 2+ concentrations appeared well correlated with the estimated ones using Visual Minteq. Finally, AGNES experiments were carried out on-site in the Gave de Cauterets in Soulom (France). The on-site measured free Zn 2+ appear in concordance with further measurements performed in the laboratory using the classical N 2 /CO 2 purge, validating the proposed methodology. This study showed that the total and free Zn concentrations depend on the geographical characteristics of the site (i.e. proximity to mines) and that an increase of the total Zn concentration does not systematically lead to a proportional increase of the free Zn concentration. This kind of approach is therefore of great interest in risk assessments, given the different levels of toxicity of different metal species.

Figure 1 .

 1 Figure 1. Scheme of a screen-printed electrode

Figure 2 .

 2 Figure 2. Map of the studied area: a. Gave de Cauterets and Gave de Pau and b. Garonne river. Sampling sites are indicated with a red circle (•).

Figure 3 .

 3 Figure 3. Zn analytical signals obtained in AGNES-SCP at different ionic strengths with purging (red bullets referred to left axis) for a total Zn concentration of 5×10 -7 mol L -1 . Black squares stand for conductivity (referred to right axis). Deposition time between 300 and 800s at -1.08V, Stripping current I s = 10µA. Error bars of the 2 replicates indicated when larger than the marker symbol.

Figure 4 .

 4 Figure 4. Calibration curve obtained with AGNES-SCP chem in a synthetic river spiked with KNO 3 0.01M, pH 8. Electrochemical conditions: E 1 = -1.165V, t 1 = 400s with stirring, Chemical stripping without stirring.

1 Figure 5 .

 15 Figure 5. Variation of Zn analytical signals in a non-purged solution of KNO 3 0.01 mol L -1 with temperature. Inset: stripping signal at different temperatures: 5°C (▬), 10°C (▬), 15°C (▬) and 20°C (▬). Zn concentration 65 µg L -1 , E 1 = -1.175V, t 1 = 400 and 500s, chemical stripping.

Figure 6 .

 6 Figure 6. Zn analytical signals obtained with AGNES-SCP chem in a synthetic river solution with 10 µg L -1 total Zn concentration spiked with KNO 3 0.01 mol L -1 and increasing Cu concentrations from 0 to 2 µg L -1 . AGNES-SCP chem conditions: E 1 = -1.190 V, t 1 = 300 s and 400 s, chemical stripping.

c

  Cu,T / µg L -1

Figure 7 . 1 [

 71 Figure 7. Comparison of [Zn 2+ ] determined from AGNES-SCP chem with [Zn 2+ ] computed from Visual Minteq in the natural freshwater samples collected in Garonne, Gave de Pau and Gave de Cauterets. Electrochemical conditions were E 1 = -1.165V, t 1 = 300s with stirring, T = 20°C, chemical stripping without stirring

Table 1 .

 1 Geochemical characteristics of rivers Garonne and Gave de Pau

* not determined

Table 2

 2

presents the total dissolved trace metal concentrations measured in acidified samples from both rivers. Total dissolved Pb and Cd concentrations are lower than 0.1 µg L -1 except for Cd in Victoria, which is the most contaminated site. Total dissolved Cu concentrations are relatively low at all sampling sites, without obvious impact from human activity, suggesting these values correspond to the natural geochemical concentrations. Regarding Zn, the highest total dissolved concentrations are observed in places near a mining area: Victoria (549 µg L -1 )

Table 2 .

 2 Total dissolved metal, and free metal ion analysis results of rivers Garonne and Gave de Pau

			pH	T Conductivity	O 2	Cl 1	NO 3	1	SO 4	21	CO 3	21	DOC	Ca 2+	K +	Na +:	Mg 2+
				!!°C	µS!cm (1							mg!L (1
		Liat	7.25	8.6	111	12.05	0.42	0.86	9.05	45.1	2	21.44	0.14	0.63	0.21
		Vielha	7.77	11	142	13.15	nd*	nd*		nd*	nd*	nd*	23.93	0.44	1.18	2.48
		Victoria	7.68	12	226	11.1	1.2	1.08	40.82 74.1	2.7	39.61	1.15	1.96	1.83
	Garonne	Les	7.44	10	116	12.85	2.24	0.91	6.86	46.2	2.4	19.94	0.3	1.73	1.58
		Fronsac	7.51	12	122	11.65	2.09	1.21	7.95	47.5	3	20.49	0.4	0.95	1.63
		Pointis:de:rivière	7.55	14	136	6.25	2.15	1.46	8.83	55.5	2.5	23.3	0.42	1.17	1.57
		Soulom	7.35	8.8	78	14.15	0.67	1.78	4.95	29.2	3.7	14.05	0.19	0.26	0.72
		Villelongue	7.66	8	125	13.35	0.65	1.15	6.82	56.6	0.7	23.1	0.22	0.97	0.69
		Beaucens	7.66	9.1	125	13.4	0.72	1.38	6.78	57.2	2	23.07	0.25	0.9	0.74
	Gave:de: Pau	Lourdes:amont Lourdes:aval Baudreix	7.67 7.69 8.08	11 11 12	137 142 152	13.65 12.5 12.9	1.06 1.1 1.32	1.58 1.45 1.65	7.68 7.51 8.31	61.9 66.6 69.5	3.2 2.9 6.8	25.06 27.13 27.39	0.26 0.27 0.31	1.16 1.18 1.65	0.85 0.94 1.07
		Stade:	8.05	14	166	13.25	1.67	2.35	8.57	77.2	2.8	29.68	0.38	1.83	1.24
		Laroin	8.16	14	185	12.5	2.55	2.84	8.8	87.1	1	34.11	0.53	1.95	1.76

* Limit of detection; ** not determined

Acknowledgements

English language editing by Holly Pearson is acknowledged. The authors acknowledge support of this research from the Communauté d'Agglomération de Pau Pyrénées (CDAPP), from the Spanish Ministerio de Ciencia e Innovación (CTM2012-39183 and CTM2013-48967), from the European Community EFA15/08 (PyrMet) and from the Comissionat d'Universitats i Recerca de la Generalitat de Catalunya (2014SGR1132).


Antoine Vacavant
email: antoine.vacavant@uca.fr

Bertrand Kerautret
email: bertrand.kerautret@univ-lorraine.fr

Tristan Roussillon
email: tristan.roussillon@liris.cnrs.fr

Fabien Feschet

Reconstructions of Noisy Digital Contours with Maximal Primitives Based on Multi-Scale/Irregular Geometric Representation and Generalized Linear Programming

Keywords: Digital shape analysis, Irregular isothetic grids, Multi-scale analysis, Decomposition into maximal arcs, Decomposition into maximal segments

The reconstruction of noisy digital shapes is a complex question and a lot of contributions have been proposed to address this problem, including blurred segment decomposition or adaptive tangential covering for instance. In this article, we propose a novel approach combining multi-scale and irregular isothetic representations of the input contour, as an extension of a previous work [Vacavant et al., A Combined Multi-Scale/Irregular Algorithm for the Vectorization of Noisy Digital Contours, CVIU 2013]. Our new algorithm improves the representation of the contour by 1-D intervals, and achieves afterwards the decomposition of the contour into maximal arcs or segments. Our experiments with synthetic and real images show that our contribution can be employed as a relevant option for noisy shape reconstruction.

Introduction

The representation of digital contours is an important task in image analysis applications, since binary shapes obtained by image processing algorithms (preprocessing and segmentation) may be altered by noise. A lot of efforts have been made on these algorithms to produce smooth contours, by developing sophisticated deblurring and denoising algorithms [START_REF] Lebrun | Secrets of Image Denoising Cuisine[END_REF], or by integrating regularization terms in segmentation process for instance [START_REF] Wirjadi | Survey of 3d Image Segmentation Methods[END_REF]. However, these approaches significantly raise the computational complexity of the complete image analysis pipeline, and include other input-noise-dependent parameters to be tediously set for any new specific applications.

Hence, another approach consists in obtaining a faithful geometrical representation directly from any noisy digital contours. A lot of research works have addressed this question by fitting parametric curves (e.g. B-splines, rational Gaussian curves) to the input points [START_REF] Bo | A Graph-Based Method for Fitting Planar B-Spline Curves with Intersections[END_REF][START_REF] Goshtasby | Fitting Parametric Curves to Dense and Noisy Points[END_REF][START_REF] Karasalo | Contour Reconstruction Using Recursive Smoothing Splines -Algorithms and Experimental Validation[END_REF]. These approaches require a parameter depending on input noise scale, in order to fit the objective function at best. In general, they do not use the fact that digital points belong to Z 2 , as this is always the case in the image plane. In the digital geometry community, an important literature has been dedicated to this problem since the 80's, by representing contours with several kinds of primitives (segments, arcs of circle). Thanks to theoretical concepts designed in digital geometry, these approaches extend the scheme of vectorization, wellknown in document analysis [START_REF] Baird | Structured Document Image Analysis[END_REF], consisting in converting pixels to line segments. In particular, some publications tackle the issue of fitting both straight segments and circular arcs to digital contours at the same time. The famous approach of Rosin and West [START_REF] Rosin | Nonparametric Segmentation of Curves into Various Representations[END_REF] relies on least square fitting and is non parametric. Another parametric technique has been designed by Hilaire and Tombre [START_REF] Hilaire | Robust and Accurate Vectorization of Line Drawings[END_REF], based on the notions of fuzzy digital segments and fuzzy digital arcs, and Faure and Feschet [START_REF] Faure | Multi-primitive Analysis of Digital Curves[END_REF] by using α-thick decomposition and combinatorial optimization. All of them are robust and accurate whilst the former two suffer from a high time complexity and are restricted to one pixel wide digital curves. Since multi-primitives decomposition can be viewed as a competition between primitives, the complexity can be tackled with an efficient and unified representation of the multiple decompositions with all individuals primitives. Relying on the work of Feschet and Tougne [START_REF] Feschet | On the Min DSS Problem of Closed Discrete Curves[END_REF], each decomposition can be represented by a circular arc-graph in linear-time. Decomposition into several primitives can be solved in O(qn) where q is the minimum number of intersecting primitives in the graph [START_REF] Atallah | An Optimal Algorithm for Shortest Paths on Weighted Interval and Circular-Arc Graphs[END_REF]. Other recent methods from state-of-the-art opt for different strategies, such as the adaptation of tangential cover [START_REF] Ngo | Adaptive Tangential Cover for Noisy Digital Contours[END_REF] or the detection of dominant points [START_REF] Nguyen | Decomposition of a Curve into Arcs and Line Segments Based on Dominant Point Detection[END_REF].

In this article, we propose a novel unsupervised approach for reconstructing noisy digital contours by combining multi-scale and irregular isothetic representations as presented in Fig. 1. The complete pipeline of our approach works as follows. From an input (supposedly noisy) closed contour obtained from any image (first column), we first extract a multi-scale object, containing overlapping boxes, with an unsupervised geometric noise detector (second column). We then represent this structure by irregular isothetic objects that is with cells without any overlapping (third column). This is done by following two directions (X and Y axes) simultaneously. Then these two X and Y axis aligned boxes are represented as lists of 1-D intervals between irregular cells (fourth column). Then, we combine both intervals to achieve a faithful geometric structure of the input contour using both X and Y oriented segments (fifth column) in a unified representation of the contour. At the end (sixth column) we compute maximal primitives within this last representation using the same Generalized Linear Programming approach for segments and arcs allowing us to produce decomposition of the contour into maximal straight line segments or circular arcs.

The article is organized as follows. In Section 2, we present the first step of our approach, aiming at representing the input contour as a multi-scale set of bounding boxes. These are then analyzed and converted into irregular isothetic structures, exposed in Section 3. Then, we describe the way to obtain decompositions into maximal primitives (Section 4), and experimental results with real and synthetic contours (Section 5) before concluding this article in Section 6.

Multi-Scale Noise Detection

The noise level detection on a digital contour is an important problem, which can influence the quality of geometric estimators or contour representation algorithms. From the digital geometry domain, a method was proposed to automatically detect the amount of noise present on a digital structure [START_REF] Kerautret | Meaningful Scales Detection along Digital Contours for Unsupervised Local Noise Estimation[END_REF]. This detection is based on the meaningful scale detection computed from asymptotic properties of the maximal segments. In particular, it is based on a theorem describing the evolution of the lengths of the maximal segments computed on the border of a shape on finer and finer grid sizes [START_REF] Lachaud | Espaces Non-Euclidiens et Analyse d'Image : Modèles Déformables Riemanniens et Discrets, Topologie et Géométrie Discrète[END_REF]. From such a multiscale analysis, the proposed algorithm consists in constructing, for each contour points C, a multiscale profile (P(C)) defined by the segment length of all segments covering P for larger and larger grid sizes h (see graph of Fig. 2 second row). From each profile, the noise level is determined by the first scale (nu) minus one for which the slope of P is decreasing and follows the awaited theoretical bounds between h -1 2 and h -1 3 if C is on a non null curvature area and near h -1 on flat part. On the examples of Fig. 2, the noise levels of points A are 0 since P(A) is always decreasing and B for the circle (resp. flower) has a noise level of 3 (resp. 3) since P(B) is increasing until scale 4 (resp. 3). This uncertainty can be represented as boxes and as exposed in Fig. 2 first row, a high noise in the contour will lead to a large box, and vice-versa. The algorithm can be tested on-line from any digital contour given by a netizen [START_REF] Kerautret | Meaningful Scales Detection: an Unsupervised Noise Detection Algorithm for Digital Contours[END_REF].

Irregular Isothetic Cyclic Representation

In this section, we first recall the I-grid (Irregular Isothetic grid) model [START_REF] Vacavant | Topological and Geometrical Reconstruction of Complex Objects on Irregular Isothetic Grids[END_REF]:

Definition 1 (2-D I-grid). Let R be a closed rectangular subset of R 2 . A 2-D I-grid G is a tiling of R
with closed rectangular cells whose edges are parallel to the X and Y axes, and whose interiors have a pairwise empty intersection. The position of each cell R is given by its center point (x R , y R ) ∈ R 2 and its length along X and Y axes by

(l x R , l y R ) ∈ R * + 2 .
This model permits to generalize many irregular image representations such as quad-trees, kd-trees, run-length encodings, and the geometry of frames encoded within video coding standards like MPEG, H.264, etc. For the rest of the article, we consider the following definitions for I-grids.

Definition 2 (ve-adjacency and e-adjacency). Let R 1 and R 2 be two cells. R 1 and R 2 are ve-adjacent (vertex and edge adjacent) if :

or    |x R1 -x R2 | = l x R 1 +l x R 2 2 and |y R1 -y R2 | ≤ l y R 1 +l y R 2 2 |y R1 -y R2 | = l y R 1 +l y R 2 2 and |x R1 -x R2 | ≤ l x R 1 +l x R 2 2
R 1 and R 2 are e-adjacent (edge adjacent) if we consider an exclusive "or" and strict inequalities in the above ve-adjacency definition. The letter k may be interpreted as e or ve in the following definitions.

A k-path from R to R is a sequence of cells (R i ) 1≤i≤n with R = R 1 and R = R n such that for any i, 2 ≤ i < n, R i is k-adjacent to R i-1 and R i+1 .
Definition 3 (k-curve). Let A = (R i ) 1≤i≤n be a k-path from R 1 to R n . Then A is a k-curve iff each cell R i has exactly two k-adjacent cells in A.
As shown in Fig. 2, the meaningful boxes (denoted afterwards by the set M) overlap and thus cannot be viewed as an irregular isothetic object directly (Definition 1). However each one contains a given number of pixels (at the initial resolution) so that the set of boxes M covers a subset of the input image. This subset P, which is an irregular isothetic object, is transformed into k-arcs, i.e. open k-curves, and the respective adjacencies relations between arcs is represented by a Reeb graph structure [START_REF] Vacavant | Topological and Geometrical Reconstruction of Complex Objects on Irregular Isothetic Grids[END_REF], as illustrated in Fig. 3a [START_REF] Toutant | Arc Recognition on Irregular Isothetic Grids and its Application to Reconstruction of Noisy Digital Contour[END_REF][START_REF] Vacavant | A Combined Multi-Scale/Irregular Algorithm for the Vectorization of Noisy Digital Contours[END_REF]. In that graph, each edge is associated to an irregular k-arc reconstructed. This process is driven by considering a given order relation, along X or Y axis (in this figure, X axis has been chosen). With the support of the Reeb graph, we are then able to produce a cyclic representation of the contour by parsing k-arcs in a given order (e.g. clock-wise from the top-most element). We also remove extra branches of the graph, i.e. edges corresponding to k-arcs not belonging to the cycle (associated to red parts in Fig. 3a). In particular, graph edges comporting a node of degree 1 are removed. At the end of this process, we obtain a single k-curve (Fig. 3b), associated to a cyclic graph, and we consider the interface (Euclidean segment shared) between two consecutive cells in the k-curve, i.e. 1-D intervals.

By combining the intervals computed from both X and Y axes, we have thus two lists of segments representing the input contour, denoted by S X and S Y , as shown in Fig. 4a. We set the internal and external points of these straight segments (black and white points in Fig. 4b) by considering the barycenter of the global shape as we did in [START_REF] Toutant | Arc Recognition on Irregular Isothetic Grids and its Application to Reconstruction of Noisy Digital Contour[END_REF]. We then build a single list of intervals S XY = {S XY [i]} 1≤i≤n with X-and Yaligned elements by first removing segments from S Y intersecting one or several ones in S X (see again Fig. 4a andb). The converse choice can done (i.e. removing segments from S X overlapping some of S Y ), nevertheless, our option leads to a faithful representation of the input contour, as exposed later in experiments.

Then, we simultaneously parse the sets S X and S Y to construct this list by a linear and incremental approach, according to the size of these two lists. At an iteration of this process, consider the last segment added in S XY , denoted by s, and the next segments to be added from S X and S Y , denoted by s x and s y respectively. We add in S XY the closest interval from s. As an illustration, in Fig. 4c, we add s y , and in Fig. 4d,s x .

During this process, adding segments of S X and S Y in

S XY is realized in in O(|S X | + |S Y |).
We can observe that we build a valid list of segments in S XY , since two successive segments in the final list (not sharing the same end point) respect this condition:

----→ S XY [i].
--------------→ S XY (i + 1)mod n ≥ 0, ∀i = 1, . . . , n,

wherein each segment is considered as a vector with the orientation given by internal and external endpoints. For instance, in Fig. 4c, -→ s . -→ s y = 0 and are added successively in S XY , in Fig. 4d, -→ s . -→ s x = 0, and any two consecutive parallel segments S XY [i] and S XY [i+1] will respect a strict positive dot product in Eq. 1. The validity of the list S XY also means that the list of internal points are ordered in the clockwise order, and follow the curvilinear abscissa of the input contour (and this is the same for the list of external points).

Recognition of Straight Segments and Circular Arcs

Even if the arrangement of straight segments in S XY is not completely random, it lacks regularity. For instance, the X-coordinates of the endpoints do not necessarily increase and for this reason, we cannot use the algorithm of O'Rourke [START_REF] O'rourke | An On-Line Algorithm for Fitting Straight Lines Between Data Ranges Com[END_REF] for the recognition of straight segments.

In this work, you use a general algorithm for the recognition of both straight segments and circular arcs, formulated as two instances of a Generalized Linear Programming (GLP) problem [START_REF] Amenta | Helly-Type Theorems and Generalized Linear Programming[END_REF].

Our notations and definitions follow [START_REF] Amenta | Helly-Type Theorems and Generalized Linear Programming[END_REF]. A GLP problem is a family H of constraints and an objective function ω from subfamilies of H to some totally ordered set S. In addition, H and ω must be such that:

(C1) Monotonicity: ∀F ⊆ G ⊆ H, ω(F ) ≤ ω(G), (C2) Locality: ∀F ⊆ G ⊆ H s.t. ω(F ) = ω(G) and for each h ∈ H: ω(F ∪ h) > ω(F ) iff ω(G ∪ h) > ω(G).
Note that the set S must contain a special maximal element Ω so that G ⊆ H is unfeasible if ω(G) = Ω and feasible otherwise.

In our framework, the constraint set H is given by the endpoints of the set of the n straight segments of S XY , with n ≥ 1. Each straight segment has two endpoints: one with label "white", the other with label "black", as depicted in Fig. 4b. Let us denote the set of white (resp. black) endpoints by P

• := {p • i } i=1...n (resp. P • := {p • i } i=1...n ).
Let P (resp. D) be the set of all possible half-planes (resp. disks). For a given X ∈ {P, D}, we want to find a shape X ∈ X that contains one point set, e.g. P • , but not the other. In other words, we want to find X ∈ X under the constraint set

H := {h 2i-1 , h 2i } i=1...n , where ∀i = 1, . . . , n, h 2i-1 := p • i ∈ X, h 2i := p • i / ∈ X. (2)
The problem is unfeasible if it does not exist such a X, but feasible otherwise.

In the latter case, we search for X minimizing a given objective function.

For any X ∈ {P, D}, there exists an objective function ω X so that (C1) and (C2) are true, which means that the above problem reduces to a GLP problem.

The objective function ω D is chosen to either return Ω if the problem is unfeasible or the radius of a smallest separating disk for H otherwise. By definition, the pair (H, ω D ) satisfies the monotonicity condition (C1), which coarsely says that the larger the constraint set is, the larger the smallest separating disk for this set is. In addition, since n ≥ 1, the smallest separating disk, if it exists, is unique, which implies locality (C2).

The objective function ω P returns Ω if the problem is unfeasible. Otherwise, the convex hulls of the point set to enclose and the point set to not enclose are well-defined because n ≥ 1 and do not intersect. In this case, ω P returns the inverse of the minimal distance between the two convex hulls. The inverse is taken so that adding a non-redundant constraint makes the objective function increase. Again, the pair (H, ω P ) satisfies conditions (C1) and (C2). As a result, depending on ω X , we have to solve two different kinds of GLP problem.

There exists an easy-to-implement and randomized algorithm that solves these two kinds of GLP problem in expected linear-time [START_REF] Sharir | A Combinatorial Bound for Linear Programming and Related Problems[END_REF]. It comes from the well-known randomized algorithm for the smallest enclosing circle problem [START_REF] Welzl | Smallest Enclosing Disks (Balls and Ellipsoids)[END_REF]. It takes a pair (H, ω X ) and returns a basis, ie. a minimal subfamily B ∈ H such that ω X (B) = ω X (H). The combinatorial dimension d of the problem is the maximum size of any basis for any feasible family. For instance, d = 3 for ω D (resp. ω P ) because at most three constraints uniquely define a disk (resp. the width between two convex polygons).

The algorithm is incremental and recursive. It may be coarsely described as follows. We iteratively add constraints. For each constraint, we check whether the new constraint violates the current basis or not. If yes, then we try to update the basis from the new constraint by recursively calling the same algorithm with all the previous constraints.

It is useful to have an on-line algorithm in order to compute the whole set of maximal segments [START_REF] Feschet | Optimal Time Computation of the Tangent of a Discrete Curve: Application to the Curvature[END_REF] or arcs [START_REF] Roussillon | Accurate Curvature Estimation along Digital Contours with Maximal Digital Circular Arcs[END_REF]. Since the original algorithm [START_REF] Sharir | A Combinatorial Bound for Linear Programming and Related Problems[END_REF] is incremental, adding the constraints in order straightforwardly leads to an on-line algorithm. The drawback is that the random order can be used only in the recursive calls but not during the constraint discovery, which results to an increase of the expected time-complexity from linear to quadratic. However, we experimentally observe short running times. The next section shows results of our pipeline, employing this on-line algorithm for the reconstruction of maximal segments or arcs.

Experimental Results

We first present in Fig. 5 the whole set of maximal segments and arcs for the Flower image. Contrary to the previous work dedicated to pure vectorization [START_REF] Vacavant | A Combined Multi-Scale/Irregular Algorithm for the Vectorization of Noisy Digital Contours[END_REF], we do not calculate a unique polyline from a complex structure of k-arcs. Thanks to the cyclic irregular representation of the input contour, we are capable of reconstructing maximal primitives, bounded by 1-D intervals, whose lengths only depend on local input noise. Without any parameter, we obtain faithful representations of noisy shapes. Moreover, the results do not depend on any starting point, as it could be the case for other methodologies employing In this article, we have proposed a novel approach combining multi-scale and irregular isothetic representations for the geometrical reconstruction of digital noisy contours. Our algorithm calculates a set of 1-D bounding intervals of the input shape, which permits to apply an on-line and recognition algorithm. Our contribution has been successfully applied on synthetic and real images, encouraging us to exploit it in concrete image analysis contexts, and to investigate several lines of research.

Our first concern will consists in adapting the tangential cover approach [START_REF] Feschet | On the Min DSS Problem of Closed Discrete Curves[END_REF] to our cyclic irregular representation. This will enable the calculation of a structure containing successive primitives, instead of overlapping maximal segments or arcs. Second, we would like to compare our contribution with other methods selected from state-of-the-art, e.g. [START_REF] Ngo | Adaptive Tangential Cover for Noisy Digital Contours[END_REF][START_REF] Nguyen | Decomposition of a Curve into Arcs and Line Segments Based on Dominant Point Detection[END_REF], and to test their robustness [START_REF] Vacavant | A Novel Definition of Robustness for Image Processing Algorithms[END_REF] with challenging data-sets of binary shapes, such as KIMIA. As a longer term, we plan to investigate the more general question of reconstructing digital shapes with other geometrical primitives, like B-splines and other parametric curves, with a similar framework we have presented herein.

Fig. 1 .

 1 Fig. 1. Global pipeline of our approach. Input: a noisy contour. Output: maximal geometric primitives. Stages are: 1-Extraction of a multi-scale representation (unsupervised geometric noise detector); 2-Irregular isothetic representation (non overlapping cells) in X and Y directions; 3-1-D intervals representation; 4-Fusion of the two directions to achieve a faithful geometric structure of the input contour.

Fig. 2 .

 2 Fig. 2. Conversion of two noisy digital contours into meaningful scales (first row) and illustration of the multicale profiles for two points A and B (second row)

Fig. 3 .

 3 Fig. 3. From the meaningful scales of the Circle sample, we reconstruct a set of k-arcs converted to a k-curve thanks to the underlying graph (b). (c) presents a part of the cells obtained with intervals (red)

Fig. 4 .

 4 Fig.4. A part of the two sets SX (black) and SY (red) intervals from the Flower sample (a), and converted into a single set of intervals SXY (b). Internal points are dotted in white, external ones in black. We also illustrate some cases of our process, with specific examples of segments s, sx and sy (see text) in (c) and (d). In the images, red intervals are already in place in SXY and green ones are to be processed from SX , SY

Fig. 5 .Fig. 7 .

 57 Fig. 5. Top: Decomposition into maximal segments (a) and maximal arcs (b) in a part of the Flower sample (green primitives), superimposed on input intervals (presented as in Fig. 4). Center and bottom: The maximal primitives are shown over original digital contour of Flower and Circle

greedy algorithms. Even in the case of an high amount of local noise, our algorithm successfully reconstructs sets of primitives, as illustrated in Fig. 5 (bottom) wherein the input digital contour is significantly corrupted and contains large discontinuities and holes (top-right of the shape). As in [START_REF] Toutant | Arc Recognition on Irregular Isothetic Grids and its Application to Reconstruction of Noisy Digital Contour[END_REF], we can also obtain the circle passing through the contour, by choosing maximal arcs (Fig. 5b).

We finally present the meaningful representation, and sets of maximal straight segments and circular arcs obtained with our algorithm, for two real images, in Fig. 6 (one contour) and Fig. 7 (two contours). The Char image leads to a noisy contour (Fig. 6b), which is accurately represented thanks to our algorithm. Maximal primitives (Fig. 6e,f) represent the complete contour, while one of our previous contributions (d) [START_REF] Vacavant | A Combined Multi-Scale/Irregular Algorithm for the Vectorization of Noisy Digital Contours[END_REF], an accurate vectorization by MLP (or Minimum Length Polyline), misses a part of the object, and produces abrupt angles in round parts. The Sign image (350×350 pixels) allows us to test the scalability of our method. The contours we have extracted generate a high number of meaningful boxes (1,364 boxes for external part, 1,234 for internal part) that we have processed without any extra effort.


B Bouchard

E Gobet

Editors OPTIMAL CONNECTIVITY FOR A LARGE FINANCIAL NETWORK * B Jourdain

Rui Chen
email: rui.a.chen@inria.fr

Andreea Minca

Agnès Sulem
email: agnes.sulem@inria.fr

We investigate network formation for a set of financial institutions represented as nodes.

Linkages are source of income, and at the same time they bear the risk of contagion. The optimal connectivity of the nodes results from a game, in which the risk of contagion depends on the choices of all nodes in the system. Our financial network model can be interpreted as a set of banks connected through funding relations, in which a node's threshold to contagion is represented by its external funding capacity. A second interpretation is that of a set of insurers connected through reinsurance contracts, in which the threshold to contagion is represented by their capital. Our results show that when the threshold distribution across the nodes has higher variance, then, in equilibrium, the average connectivity is in general increasing, but the link failure probability decreases. This suggests that financial stability is best described in terms of the mechanism of network formation than in terms of simple statistics of the network topology like the average connectivity.

Résumé. On étudie la formation d'un réseau financier dont les noeuds représentent des institutions financières. Les liens sont sources de revenus mais également de risque de contagion de défaut. La connectivité optimale du réseau résulte d'un jeu, dans lequel le risque de contagion dépend de tous les noeuds du système. Notre réseau peut être interprété comme un ensemble de banques connectées entre elles par des relations de financement, le seuil de contagion de défaut pour une banque représentant ici sa capacité de financement extérieur. On peut aussi appliquer notre modèle à l'étude d'un réseau d'assureurs connectés par des contrats de réassurance, pour lesquels le seuil de contagion de chaque noeud est son capital. Nos résultats montrent que lorsque la distribution du seuil de contagion de défaut sur l'ensemble des noeuds a une grande variance, la connectivité moyenne croit, alors que la probabilité de défaut décroit. Cela suggère que l'étude de la stabilité financière d'un réseau financier doit prendre en compte le mécanisme de formation du réseau et pas seulement sa connectivité moyenne.

Introduction

Interconnected systems are subject to contagion in time of distress. Recent effort has been dedicated to understanding the relation between network topology and the scope of distress propagation, see e.g., [START_REF] Amini | Resilience to contagion in financial networks[END_REF][START_REF] Amini | Inhomogeneous financial networks and contagious links[END_REF][START_REF] Blume | Network formation in the presence of contagious risk[END_REF][START_REF] Roukny | Default cascades in complex networks: Topology and systemic risk[END_REF] and the references therein. It is critical to recognize that connectivity is a result of an optimization problem of agents, who derive benefits from connections and view the associated contagion risk as a cost. In the context of financial systems, this benefit-cost view of connections is first presented in [START_REF] Blume | Network formation in the presence of contagious risk[END_REF], who analyze socially optimal network topologies.

A threshold model of contagion for heterogenous graphs is proposed in [START_REF] Amini | Resilience to contagion in financial networks[END_REF]. Each node represents a bank, insurance company or institution, and is endowed with a threshold to contagion. A set of nodes fail exogenously and any node in the system can fail due to contagion when its threshold is surpassed by the number of connected nodes that fail. The availability of asymptotic results on the fraction of nodes that fail at the end of the contagion process allows us to estimate the failure probability for a network with given connectivity. In this paper, we take a step further and find the equilibrium choice of connectivity. The banks' payoff is impacted by their own choice of connectivity, which governs both the benefits from linkages as well as the exposure to the risk of contagion in the network. The risk of contagion in turn depends on all the banks' connectivity choices.

The fundamentals in the model are represented by the thresholds. Under full information, the distribution of the thresholds across banks is common knowledge. Once a node chooses its connectivity, the network is generated using the configuration model. This is a random graph chosen uniformly over all graphs with the given connectivity sequence across nodes. For this random graph, a law of large numbers gives the limit probability that a randomly chosen link fails, i.e. it links to a failed node. This probability depends on the join distribution of the connectivity and thresholds. Our equilibrium concept is a rational expectations equilibrium. For an anticipated link failure probability, nodes choose their optimal connectivity as a function of their threshold. We then ensure that the anticipated link failure probability is equal to the failure probability in the network with the chosen connectivity.

Our equilibrium model is quite different from past literature. In [START_REF] Blume | Network formation in the presence of contagious risk[END_REF] the authors use the notion of pairwise Nash stability and a contagion mechanism in which nodes fail with an exogenous probability when a neighbor fails. The notion of pairwise Nash stability is also used in [START_REF] Erol | Network formation and systemic risk[END_REF]. Here we exploit the asymptotic results for contagion scope in our particular choice of random graph, where connectivity is optimized but the actual neighbors are randomly chosen. We are interested in the optimal connectivity as a function of fundamentals, namely the thresholds. Our notion of equilibrium can be seen as a Nash equilibrium with a continuum of players, classified according to their thresholds and we obtain a unique such equilibrium.

For the asymptotic case, our results allow us to understand how the degree of heterogeneity in the fundamentals translates into failure risk in the network with endogenous connectivity. Nodes adjust their connectivity to the degree of heterogeneity in the fundamentals. When the fundamentals are more homogenous, then the average connectivity is lower, but the failure probability is higher than in the case when there is more dispersion in the fundamentals. The network payoff is defined as the average number of links times the survival probability. For different fundamentals, the network connectivity is adjusted in equilibrium to yield the same network payoffs. However, these networks are not equivalent from the point of view of systemic risk. To obtain lower default probability and systemic risk, more dispersion in fundamentals is preferable. In this case, nodes with large thresholds would act as stabilizers in time of distress. Our results are in line with [START_REF] Erol | Network formation and systemic risk[END_REF], who obtain in a different model that economies that are fundamentally "safer", in the sense that they are subject to less volatile shocks, generate higher interconnectedness. Here, it is the homogeneity of the thresholds, or otherwise said their lesser variance, that generates more connectivity.

Our paper is complementary to the line of research on the control of contagion, e.g., [START_REF] Amini | Control of interbank contagion under partial information[END_REF][START_REF] Minca | Optimal control of interbank contagion under complete information[END_REF][START_REF] Rogers | Failure and rescue in an interbank network[END_REF]. In these works, a central party, for example a regulator or government, seeks to minimize contagion. In [START_REF] Erol | Network hazard and bailouts[END_REF] the author explores the effect of moral hazard on network topology, as the network is formed with the anticipation of government bailouts in case of distress. Parallel to the development of network models for systemic risk, a recent series of works [START_REF] Carmona | Mean field games and systemic risk[END_REF][START_REF] Fouque | Stability in a model of interbank lending[END_REF][START_REF] Garnier | Diversification in financial networks may increase systemic risk[END_REF][START_REF] Garnier | Large deviations for a mean field model of systemic risk[END_REF][START_REF] Garnier | Large deviations for a mean field model of systemic risk[END_REF] introduced a reduced form approach to systemic risk analysis, based on mean field interaction models. In these works, the trajectories of the banks are modeled as a set of coupled diffusions, which may be controlled by a central party that specifies the parameters of the interaction. Here in contrast, the financial institutions themselves are the decision makers, and their decision is made before the shock, with a rational expectation on the way the cascade will evolve following the shock.

While most of the work on contagion in financial networks refers to banking networks, a recent literature [4, 13] considers insurance-reinsurance networks. Contagion proceeds similarly in such networks, as failed reinsurers cannot honor contracts to other institutions, and such failures can propagate via chains of reinsurance contracts. Our work offers thus guidance on the formation of such networks and their inherent risk.

The paper is organized as follows. In section 1 we present the model of contagion and the nodes' optimization criteria. In section 2 we investigate the existence and uniqueness of the optimal connectivity, under an anticipated link failure probability. In Section 3 we analyze the equilibrium connectivity. Finally, in Section 4 we study numerically the equilibrium choice as a function of fundamentals.

Node performance under linkage benefits and contagion risk

We represent a financial system by n institutions (nodes), endowed with a sequence of thresholds (θ(i)) i∈ [n] . We can interpret the nodes as banks, in which case the thresholds represent the funding that these banks can raise from external lenders. Banks loan to other banks, and thus choose their connectivity and form funding linkages. Alternatively, we can interpret the nodes as insurance companies. Their threshold represents their capital. They can reinsure other insurance companies, and to do so they choose their connectivity and form reinsurance linkages.

Given a connectivity λ(i), i ∈ [n] , nodes form links according to the random matching from the configuration model. In the configuration model with given degree sequence λ(i), i ∈ [n], each node i is assigned λ(i) incoming half edges and λ(i) outgoing half edges. The (multi)graph results from uniform matching of the in-coming half edges and the outgoing half edges. As n → ∞, self loops and parallel edges become rare, and the graph is simple with positive probability [START_REF] Janson | The probability that a random multigraph is simple[END_REF]. This means that any property that holds with high probability on the configuration model, also holds with high probability conditional on this random graph being simple. This graph is denoted by G and we write (i, j) ∈ G for the event that there's a link between i and j. We let µ n (λ, θ) be the fraction of nodes with degree λ and threshold θ,

µ n (λ, θ) := {i ∈ [n] | θ(i) = θ, λ(i) = λ} n .
We assume the following regularity conditions µ n (λ, θ) → µ(λ, θ), as n tends to ∞. We let the fraction of nodes with threshold θ, be defined as

µ(θ) := λ µ(λ, θ).
This network is subject to contagion risk. After the network is formed, a shock occurs and a set D 0 , representing a fraction of the entire system, switches its threshold to zero. If the financial network represents a network of funding relations among banks, the initial shock has the meaning that the debt capacity of certain banks becomes zero, i.e., no party lends to them, so they exogenously become illiquid. If the financial network represents a network of reinsurance contracts among insurance companies, then the initial shock is to be interpreted that the capital of certain insurers becomes zero following an extreme event. Under both of these representations, the thresholds becoming zero is equivalent to the failure of the node. This initial set of failures triggers a cascade of failures, as we assume that failed nodes cut linkages from the nodes connected to them. Banks that fail after becoming illiquid cut loans from other banks in the system. These banks in turn also fail if their debt capacity is smaller than the amount of funding that was cut by failed banks. Insurers that fail after their capital becomes zero cut the reinsurance of other insurers. These other insurers in turn also fail if their capital is smaller than the amount of reinsurance that was cut by failed insurers. In sum, whenever a the node's threshold is smaller than the number of linkages that are cut from it, then it fails due to contagion.

We have

D 1 := {j ∈ D c 0 | θ(j) < i∈D0 1 1 (i,j)∈G }, with c denoting set complement. The cascade progresses according to D n := {j ∈ D c n-1 | θ(j) < i∈Dn-1 1 1 (i,j
)∈G }, and it stops after at most n steps. We let D f be the set of failures at the end of contagion process. We have the following theorem, which characterizes the set of failures.

Theorem 1 ([1]

). Let p * be the smallest fixed point of the map J in [0, 1], where

J(p) := θ,λ λµ(θ, λ) θ,λ λµ(θ, λ) • B(θ, λ, p), with B(θ, λ, p) := P(Bin(λ, p) ≥ θ) = λ l≥θ λ l p l (1 -p) λ-l .
Here Bin denotes a random variable with binomial distribution with parameters λ and p.

(i) If p * = 1, i.e., if J(p) > p for all p ∈ [0, 1), then asymptotically (when n → ∞) almost all nodes fail during the cascade. (ii) If p * < 1 and p * is a stable fixed point of J, i.e., J (p * ) < 1, then the final fraction of failures

|D f | n
converges in probability to λ,θ µ(λ, θ) j θ=0 B(θ, λ, p * ). The asymptotic fraction of surviving nodes with degree λ and threshold θ at the end of the contagion is given (in the limit) by

s θ,λ = µ(θ, λ)(1 -B(θ, λ, p * )).
Remark 2. Consider the fixed point equation p * = J(p * ) and multiply both sides with n θ,λ λµ(θ, λ), which represents the total number of links in the network. Then p * n θ,λ λµ(θ, λ) represents the number of failed links (links from failed nodes) present in the system. This must be equal at the end of the cascade to θ,λ λnµ(θ, λ)B(θ, λ, p * ), which gives the sum across nodes with different θ of their failed links. In other words, all failed links have been "accounted for" in terms of the nodes which are the counterparties. This result is established by describing the contagion process using a Markov chain of lower dimension than the initial system, in which we aggregate nodes according to their connectivity, threshold, and number of failed counterparties. From the point of view of the evolution of the cascade, the nodes in the same class are indistinguishable. We then show that, as the network size increases, the Markov chain rescaled by network size converges in probability to a limit described by a system of ordinary differential equations, which can be solved in closed form. This readily gives us the asymptotic fraction of surviving nodes (in each class of connectivity and threshold) at the end of the cascade, namely s θ,j .

It is clear that any node in the network is exposed to global failure risk captured by p * . We refer to p * as the global failure probability of a link. The failure probability of a node with degree λ and threshold θ is B(θ, λ, p * ). As nodes add more connectivity, they increase the risk of contagion. Of course, nodes add connectivity because they derive benefits from their linkages. We capture these benefits in a simple way, by assuming that there exists a numéraire and that surviving nodes with connectivity λ receive λ (units of the numéraire) at the end of the cascade. They receive no benefit from their linkages if they fail.

Remark 3. Note that the ability to define a global failure probability depends on our choice of the configuration model as an underlying network. The configuration model is a flexible setting as it gives the possibility to use any degree distribution, but it carries the implicit assumption that a linkage default probability is independent of the end node in equilibrium. It remains an open problem to extend the equilibrium analysis below to other types of random graphs, e.g. inhomogeneous random graphs, and for case when the global failure probability is replaced by a failure probability matrix (with the default probability of a link depending on the types of its end nodes).

We are now ready to define the nodes' performance measure. Definition 4 (Nodes' performance). We define the performance criterion for a node with degree j and threshold θ as the expected benefit of linkages, and it is given in the asymptotic limit by λ 1 -B(θ, λ, p * ) , with p * given in Theorem 1.

Note that the global failure probability of a link p * depends on the connectivity choice of all nodes. Therefore, the optimal connectivity is an outcome of an equilibrium. We proceed in two steps to determine this equilibrium. In the first step, we let the nodes choose their connectivity according to an expected failure probability p of a link, i.e., a node with threshold θ chooses a connectivity

λ * (θ, p) ∈ arg max λ λ 1 -B(θ, λ, p) . (1)
In the second step, detailed in Section 3, we will impose an equilibrium condition that the expected failure probability of a link coincides with the actual failure probability of a link, under the optimal connectivity. Before we proceed, we note that the banks maximize an expected payoff which is equal to the connectivity if the bank doesn't fail and 0 if it does. One could argue that in the performance criterion banks should only count the profit from the surviving linkages. In fact, whether we should use the expected benefit from all linkages or the expected benefit from the surviving links depends on the model interpretation. It can be of interest to use the expected benefit and not the expected benefit from the surviving links when surviving banks replace the defaulted links with new funding from outside creditors to maintain their business. In such case the replaced linkages have the same function as the original ones.

One could also assume that failed links do not provide any benefit and maximize the product of the probability of survival 1 -B(θ, λ, p) and the expectation of non-failed links λ(1 -p). The next remark shows that for fixed failure probability p of a link, the banks' choice remains the same. This in turn implies the equilibrium and its stability properties remain the same.

Remark 5 (Robustness to the performance criterion). We can also define our performance criterion as the expected benefit from the survived links. There are two possible criteria. For fixed θ and p,

• V 1 (λ) := (1 -p)λ 1 -B(θ, λ, p) . In this case the optimizer remains the same as above since

max λ V 1 (λ) = (1 -p) max λ λ 1 -B(θ, λ, p) . Thus arg max λ V 1 (λ) = arg max λ λ 1 -B(θ, λ, p) . • V 2 (λ) := l<θ (λ -l) λ l p l (1 -p) λ-l . Straightforward computation shows that V 2 (λ) = l<θ λ λ -1 l p l (1 -p) λ-l = (1 -p)λ 1 -B(θ, λ -1, p) . Thus arg max λ V 2 (λ) = arg max λ λ 1 -B(θ, λ -1, p) ,
which shares the same structure as the original criterion and will lead to similar results.

Which criterion is more suitable depends on the contagion model. When the direction of link is the same as the direction of contagion (i.e. i loans to j and there is contagion from i to j and the link (i, j) fails when i withdraws funding from j) then V 1 represents the expected benefit of the non-failed links of the surviving banks.

When the direction of the link is inverse to the direction of contagion (i.e. i loans to j and there is contagion from j to i and the link (i, j) fails because j is insolvent or cannot pay the loan) then V 2 represents the expected benefit of the non-failed links of the surviving banks.

Nodes' optimal connectivity choice

In this section we investigate existence and uniqueness of the node's optimal connectivity. We begin by noting that the node's optimization problem carries a tradeoff. We recognize here that 1 -B(θ, λ, p) is equal to the Incomplete beta function I 1-p (λ -θ + 1, θ). We recall that

I x (a + 1, b) = I x (a, b) -x a (1-x) b aB(a,b) , where B(a, b) = 1 0 x a-1 (1 -x) b-1 dx. We have I 1-p (λ -θ + 2, θ) = I 1-p (λ -θ + 1, θ) -(1-p) λ-θ+1 p θ (λ-θ)B(λ-θ+1,θ)
and thus 1 -B(θ, λ + 1, p) < 1 -B(θ, λ, p), which means that the survival probability decreases in λ.

The node's performance as a function of connectivity can now be written as

V (λ) := λ • I 1-p (λ -θ + 1, θ).
It is easy to see that this performance balances more benefits from connectivity (via the factor λ) against more risk, via the decreasing surviving probability I 1-p (λ -θ + 1, θ).

Proposition 6 (Existence). The optimization problem admits a finite optimizer λ * (θ, p) which lies in the

interval 1-p p ∨ θ, θ-2p+ √ (θ-2p) 2 +4(1-p)p 2p
.

Proof. We will show that the node's performance V (λ) is decreasing in λ for λ > θ-2p+

√ (θ-2p) 2 +4(1-p)p 2p
and is

increasing for λ < 1-p p ∨ θ. Recall that λ+1 l = λ+1 λ+1-l λ l = 1 1-l/(λ+1) λ l . We have V (λ + 1) -V (λ) = l≤θ-1 [(λ + 1) 1 -p 1 -l/(λ + 1) -λ] λ l (1 -p) λ-l p l . Now if λ > -(2-θ)+2(1-p)+ √ (2-θ-2+2p) 2 +4(1-p)p 2p = θ-2p+ √ (θ-2p) 2 +4(1-p)p 2p
, then we have (λ + 1)

1-p 1-(θ-1)/(λ+1)λ < 0. This gives (λ + 1) 1-p 1-l/(λ+1) -λ < 0, for all l ≤ θ -1 since (λ + 1) 1-p 1-l/(λ+1) -λ is increasing in l. This leads to (λ + 1)

2 (1 -p) < λ(λ + 2 -θ). Thus λ > -(2-θ)+2(1-p)+ √ (2-θ-2+2p) 2 +4(1-p)p 2p = θ-2p+ √ (θ-2p) 2 +4(1-p)p 2p . Therefore if λ > θ-2p+ √ (θ-2p) 2 +4(1-p)p 2p
, then V (λ + 1) -V (λ) < 0. Thus the optimal λ * should lie in the interval [0,

θ-2p+ √ (θ-2p) 2 +4(1-p)p 2p
]. Similarly if λ < 1-p p , then (λ + 1)(1 -p) -λ > 0 and thus we have (λ + 1) 1-p 1-l/(λ+1) -λ > 0 for all l ≤ θ -1, again by the monotonicity in l. This gives that V (λ + 1) -V (λ) > 0 which means the optimal λ * should be greater than 1-p p . Also it is obvious to choose λ * ≥ θ for players with threshold θ. We conclude that the optimal λ * should lie in the interval 1-p p ∨ θ,

θ-2p+ √ (θ-2p) 2 +4(1-p)p 2p
.

Corollary 7. The optimal connectivity lies in

[ 1-p p ∨ θ, θ p -1].
Proof. This follows from Proposition 6 and the fact that

θ-2p+ √ (θ-2p) 2 +4(1-p)p 2p < θ p -1.
Remark 8. The same results hold for the performance criterion V 2 . We mirror the proof of the existence result, Proposition 6. We have

V 2 (λ + 1) -V 2 (λ) = l≤θ-1 [(λ + 1) 1 -p 1 -l/λ -λ] λ -1 l (1 -p) λ-1-l p l .
If λ > θ-p p , then we have (λ + 1) 1-p 1-(θ-1)/λ -λ < 0. This gives (λ + 1)

1-p 1-l/λ -λ < 0, for all l ≤ θ -1 since (λ + 1) 1-p 1-l/λ -λ is increasing in l. This leads to (λ + 1)(1 -p) < λ + 1 -θ. Thus λ > θ-p p . Therefore if λ > θ-p p , then V 2 (λ + 1) -V 2 (λ) < 0. Thus the optimal λ * should lie in the interval [0, θ p -1]. Similarly if λ < 1-p
p , then (λ + 1)(1 -p) -λ > 0 and thus we have (λ + 1) 1-p 1-l/λ -λ > 0 for all l ≤ θ -1, again by the monotonicity in l. This gives that V 2 (λ + 1) -V 2 (λ) > 0 which means the optimal λ * should be greater than 1-p p . Also it is obvious to choose λ * ≥ θ for players with threshold θ. We conclude that the optimal λ * lies in the interval 1-p p ∨ θ, θ p -1 .

Equilibrium

We now impose the equilibrium condition, that the failure probability given by Theorem 1 with nodes at their optimal connectivity coincides with the anticipated failure probability. Definition 9. We call (p * , (λ * (θ), θ ≥ 0)) an standard equilibrium if

• Given p * , λ * (θ) ∈ arg max λ λ 1 -B(θ, λ, p * ) , for each θ; (2)
• p * is the smallest solution of the fixed point equation :

p * = θ λ * (θ)µ(θ) θ λ * (θ)µ(θ) • B(θ, λ * (θ), p * ). (3)
The fixed point equation in the equilibrium definition is derived from the fixed point equation in Theorem 1, where the connectivity is set to λ * (θ) and we note that µ(θ) = µ(θ, λ * (θ)).

Combining the two conditions above, we see that in equilibrium the failure probability of a link p * is the smallest fixed point of the map

φ(p) := θ λ * (θ, p)µ(θ) θ λ * (θ, p)µ(θ) • B(θ, λ * (θ, p), p). (4)
Now we study the existence of the equilibrium.

Proposition 10 (Existence of equilibrium). When λ * (θ, p) is continuous in p ∈ [0, 1), the function φ admits at least one fixed point p * . When λ * (θ, p) is not continuous in p, the map φ admits a "relaxed" fixed point p defined as p := min{p, φ(p) ≤ p, p ∈ [0, 1)}. For both cases, we let λ * (θ) = λ * (θ, p * ).

Proof. The proof is immediate: when λ * (θ, p) is continuous in p ∈ [0, 1) then the function φ is continuous in [0, 1). It thus admits at least one fixed point since lim p→1 φ(p) ≤ θ µ(θ) λ * (θ,p) θ λ * (θ,p)µ(θ) = 1 and lim p→0 φ(0) ≥ 0. When λ * (θ, p) is not continuous, the relaxed fixed point always exists since φ(0) ≥ 0 and φ(1) ≤ 1.

Remark 11. The continuity of λ * (θ, p) in p is guaranteed by the uniqueness of the optimal connectivity λ * (θ, p). However, this uniqueness is difficult to show for problem [START_REF] Amini | Resilience to contagion in financial networks[END_REF]. We provide below a uniqueness result for an approximated problem obtained by approximating the binomial distribution in (1) by the Poisson distribution P ois(λp) when λ is large enough and p is small :

λ * (θ, p) ∈ arg max λ λ 1 -P ois(θ, λ, p) , (5)
where 1 -P ois(θ, λ, p) = ). Thus

d[λ(1 -P ois(θ, λ, p))] dλ = θ-1 k=0 (λp) k e -λp k! -λpe -λp + λ θ-1 k=1 p( (λp) k-1 e -λp (k -1)! - (λp) k e -λp k! ) = θ-1 k=0 (λp) k e -λp k! -λp • (λp) θ-1 e -λp (θ -1)! .
The optimal λ * should satisfy

θ-1 k=0 (λp) k k! = (λp) θ (θ -1)! . We note that if λ ≥ θ+1 p , then (λp) k+1 (k+1)! > (λp) k k! , for k = 0, 1, . . . θ -1. Thus, θ-1 k=0 (λp) k k! < θ (λp) θ θ! = (λp) θ (θ -1)! .
So we must have λ * < θ+1 p . It follows that

d 2 [λ(1 -P ois(θ, λ, p))] dλ 2 = -p • (λp) θ-1 e -λp (θ -1)! -p(θ) (λp) θ-1 e -λp (θ -1)! + p (λp) θ e -λp (θ -1)! < 0.
Thus λ(1 -P ois(θ, λ, p)) is concave in λ and uniqueness of the optimizer follows.

Remark 13. Relation to the Nash equilibrium We can relate the equilibrium of Definition 9 to a Nash equilibrium of the following game. Any player with threshold θ 0 , given the connectivity {λ(θ)} θ =θ 0 of the other players, computes its optimal connectivity λ * (θ 0 , p) ∈ arg max

λ λ 1 -B(θ 0 , λ, p) ,
under the constraint that

θ =θ 0 µ(θ) λ(θ) θ =θ 0 µ(θ)λ(θ) + µ(θ 0 )λ * (θ 0 ) B(θ, λ(θ), p) + µ(θ 0 ) λ * (θ 0 ) θ =θ 0 µ(θ)λ(θ) + µ(θ 0 )λ * (θ 0 ) B(θ 0 , j, p) = p.
We can rewrite the above constraint p = G(λ * (θ) θ =θ 0 , λ) for some function G. Thus, the optimization criterion can be rewritten as :

λ * (θ) ∈ arg max λ λ[1 -B(λ, θ 0 , G(λ * (θ) θ =θ 0 , λ))].
In this sense, (λ * (θ), θ ≥ 0) is a Nash equilibrium.

Analysis of the equilibrium

Case 1: The system is perfectly observable to all the nodes, i.e. all the θ and their distribution µ(θ) are common knowledge. Then all the nodes will simultaneously choose their connectivity in the equilibrium state by rational expectations and the system simultaneously reaches the equilibrium (λ * (θ), θ ≥ 0), by virtue of Proposition 10.

Case 2: The system is only partially observed by the players, for example each player only knows his own threshold θ. All the players optimally choose their linkage λ * (θ, p 0 ) according to some anticipated link failure probability p 0 (this could be the failure probability estimated from the current environment). Then the link failure probability p 1 in the next stage is determined by the fixed point of the map p → F (p 0 , p), where

F (p 0 , p) := θ µ(θ) λ * (θ, p 0 ) θ µ(θ)λ * (θ, p 0 ) [1 -B(θ, λ * (θ, p 0 ), p)]. (6)
Then all nodes adjust their expectation of link failure probability from p 0 to p 1 and choose connectivity λ * (θ, p 1 ) corresponding to p 1 . This will be further updated to a series of link failure probabilities {p 0 , p 1 ...p n }.

We conjecture that the sequence {p 0 , p 1 ...p n } will not convergence to the equilibrium states p * , since the following map H is divergent near the equilibrium state

H : p 0 → p 1 = min{p| θ µ(θ) λ * (θ, p 0 ) θ µ(θ)λ * (θ, p 0 ) [1 -B(θ, λ * (θ, p 0 ), p)] = p}. (7)
This means that the equilibrium is not stable in the sense that starting from the neighborhood of the equilibrium state, the above update of the rational expectations on the failure probability will not converge to the equilibrium.

Our numerical results give the examples of this instability phenomenon for different initial distributions:

(i) Uniform initial distribution of θ on the interval [0, 30] (Figure 1); (ii) Gaussian initial distribution of θ on the interval [0, 30] with mean 15 and standard deviation 1.8 (Figure 2); (iii) Two-sided distribution with µ(0) = 0.3, µ(30) = 0.7 and µ(θ) = 0 for θ / ∈ {0, 30} (Figure 3); (iv) Gaussian initial distribution of θ on the interval [0, 200] with mean 100 and standard deviation 40.6 (Figure 4);

Numerical results

In this section we discuss how the link failure probability in equilibrium changes with respect to the initial distribution. More precisely, we consider different initial distributions on some range of the capacity θ. All distributions have the same mean but different variances. We choose θ in the interval [0, 30] and we consider a Gaussian distribution on this range with mean 15 and standard deviation γ. We vary γ from 1 to 6, and we find that the link failure probability in equilibrium drops from 0.14072 to 0.13748. This shows that relatively less concentration in the initial distribution leads to less failure probability in equilibrium, see Figure 5. Moreover, the increase of the standard deviation in the initial distribution of θ leads to larger average connectivities in equilibrium. This is consistent with the results in [START_REF] Amini | Resilience to contagion in financial networks[END_REF] that the average connectivity is a too simple statistics of network topology, see Figure 6.

Conclusion

In this paper, we considered the optimal choice of connectivities by nodes in a large network. The nodes balance the benefits of connectivity with the risk of the contagion, which is endogenous and depends on the strategies of all nodes. We have studied the existence of an equilibrium in the system and the stability properties. Under full information, the equilibrium is reached simultaneously by all nodes, whereas under partial information, we show numerically that the equilibrium is unstable in the sense that a sequence of anticipated link failure probabilities does not converge. Our numerical results demonstrate that more concentrated distributions of threshold lead to equilibria with smaller average connectivity but higher failure probability. This suggests new directions of research on the relation between failure and connectivity in endogenous networks especially with dynamic feature.

Proposition 12 (

 12 Uniqueness). The approximated optimization problem (5) admits an unique solution λ * . Proof. Recall that ( (λp) k e -λp k! ) = p( (λp) k-1 e -λp (k-1)! -(λp) k e -λp k!

Figure 1 .

 1 Figure 1. Divergence near the equilibrium state for uniform initial distribution of θ on [0, 30]. The map H has slope > 1 near the equilibrium state.

Figure 2 .

 2 Figure 2. Divergence near the equilibrium state for Gaussian initial distribution of θ on [0, 30] (with standard deviation 2). The map H has a slope > 1 near the equilibrium state.

Figure 3 .

 3 Figure 3. Divergence near the equilibrium state for two-sided distribution with µ(0) = 0.3, µ(30) = 0.7 ). The map H has a slope > 1 near the equilibrium state.

Figure 4 .

 4 Figure 4. Divergence near the equilibrium state for Gaussian initial distribution of θ on [0, 200] (with standard deviation 30). The map H has a slope > 1 near the equilibrium state.

Figure 5 .

 5 Figure 5. Failure probability in equilibrium with different initial distribution of θ on [0, 30]. As the standard deviation parameter γ increases from 1 to 6, the failure probability in equilibrium drops from 0.14072 to 0.13748.

Figure 6 .

 6 Figure 6. The average connectivities of the system in the equilibrium with different initial distribution of θ on [0,30]. As the standard deviation parameter γ increases from 1 to 6, the average connectivity firstly increases from 79.295 to 81.029 then drops to 80.989 .

* This work was partially founded by a research grant from the Europlace Institute of Finance. * * Andreea Minca is partially funded under NSF grant CMMI 1638230. * * * Rui Chen is funded by a grant from Fondation Sciences Mathématiques de Paris.