Bubonic Plague Outbreak Investigation in the Endemic District of Tsiroanomandidy -Madagascar, October 2014

Keywords: BHCS: Basic Health Center, CDC: Control and prevention Diseases Center, DHS: District Bubonic Plague, Outbreak, Environmental Factors, Reservoirs, Vectors

Plague is a zoonotic disease caused by the bacillus Yersinia pestis, rodents are reservoirs and the disease is transmitted by infected fleas or by direct exposure. Symptoms associate high fever with painful bubo, chills, headache, malaise, prostration, hemoptysis and pneumonia. The clinical forms are bubonic, septicemia or pneumonia. Bubonic plague is treated by a combination of injected streptomycin and oral sulfamethoxazole trimethoprim [START_REF] Butler | Plague Gives Surprises in the First Decade of the 21st Century in the United States and Worldwide[END_REF][2][START_REF]Atlas de la peste à Madagascar Groupe d'Etudes sur la Peste[END_REF].

In the world, 3248 cases of plague in humans were reported from 2010 to 2015, resulting in 584 deaths [4].

Madagascar is the most seriously affected country in the world with 74% of the total cases in the world [4]. Plague is endemic in Madagascar with the number of reported human cases ranging from 312 to 648 per year between 2010 and 2014 [4]. Plague season usually starts in September and ends in April. It primarily affects the central highlands, with an elevation over 800 m [START_REF] Handschumacher | The resurgence of the plague in Madagascar: a 100-year-old disease with history and ecology [La résurgence de la peste à Madagascar : une maladie centenaire à l' épreuve de l'histoire et de l' écologie[END_REF][START_REF] Kannapel | On the paths of plague in Madagascar, Mémoire DEA 2005 [Sur les chemins de la peste a Madagascar[END_REF]. Plague is a mandatory notification disease with an individual form provided by the Ministry of health National plague control program [START_REF]Ministry of Health The National Policy for the Fight Against Plague[END_REF]. Human infections occur in households during an epizootic among rats living in or near human dwellings and animal facilities.

Tsiroanomandidy is a plague-endemic district located 212 km from the capital Antananarivo in the Midwest of Madagascar. During this period: August 1 st (beginning of the plague season in Madagascar) to October 12 th (end of the investigation), plaguecases were reported in 7 out of 17 municipalities of the district. The district has 1 reference hospital and 30 basic health centers (BHCS). In Madagascar, plague epidemics occur from August to April, with peaks in December and January corresponding to the maximum of precipitation.

According to the data base of Pasteur Institute Madagascar, from 2008 to 2014, the five municipalities that recorded a total number of plague cases over 40 cases were: Tsiroanomandidy fihaonana, Miandrarivo, Ankadinondry sakay, Tsinjoarivo Imanga and Ambatolampy. The total number of plague cases in the district of Tsiroanomandidy was almost constant during the previous three years, from 2011 to 2013.

Confronted with the notification of suspected plague cases and deaths reported by the local health authority of Tsiroanomandidy district in late September 2014 and according to the District Health Service (DHS) register, from August 1 st (the beginning of the 2014-2015 plague season) to October 9 th 2014 (week 32 to week 41), 27 out of 30 (90%) plague cases were notified in two out of 17 municipalities, namely Tsinjoarivo Imanga and Ambatolampy.

A team from the Pasteur Institute de Madagascar (IPM) was sent to perform rodent capture and a disinfestation campaign while a team of epidemiologists conducted a plague outbreak investigation from October 10 th to 14 th . The joint investigation team consisted of epidemiologists, rodentologists and entomologists technicians.

The objectives of our investigation were i) to conduct active cases and contacts finding; ii) to describe all cases; iii) to raise hypotheses about exposure factors and finally; iv) to strengthen the local health team in order to block the spread of this epidemic and prevent new outbreaks.

Methods

Case definition according to the National Plague program

We conducted an investigation and descriptive analysis study A suspected bubonic plague case was defined as any person with uncorrected axillary temperature above 37 o 5 Celsius associated with bubo(es) in a favorable epidemiological context (contact with a case or residence or travel in endemic areas or observed/ reported prior rat mortality or evidence of flea bite from September 27 th 2014).

A probable case was defined as a suspected case with positive F1 antigen dipstick rapid test. The detection of F1 antigen in the diagnosis of plague during the acute phase of the disease is quite relevant in both human and rodents [START_REF] Chanteau | Early diagnosis of bubonic plague using F1 antigen capture ELISA assay and rapid immunogold dipstick[END_REF]. Confirmed case was defined as any suspected or probable case of plague with a positive Yersinia pestis culture.

Case finding

We examined the outpatients' registers of the BHCS and all individual notification forms issued by the DHS.

New cases detected during our mission were identified by consulting the registers of the BHCS and by conducting active research. All cases that occurred until September 27 th and new cases reported during our investigation period were included. Active research consist in conducting an interview and medical examination of persons who have been in contact with a case, the aim was to identify new suspected cases among families and their neighbors.

Data collection

We interviewed each identified case and/or their relatives using a standardized questionnaire. The form included demographic information as well as data regarding the clinical details of the disease, residence or visit in an endemic area within the 10 days before the onset of symptoms, contact with a suspected plague case or deceased, rat mortality in or around households or in the fields. The identified contacts were given sulfamethoxazole trimethoprim (STX TMP) as chemoprophylaxis, free of charge. New cases detected were treated by injectable streptomycin and all treated patients responded favorably to antibiotic therapy.

An environmental survey was conducted among heads of family cases, neighbors and community workers to identify risk factors for the disease including the possible mortality or proliferation of rodents and fleas, the practice of bush fires, the unsafe environment. Tsiroanomandidy the site of study is located in 18 o 4 South to 46 o 3 East.

Rodents have been trapped in 5 hamlets where human cases have occurred. Forty live traps were distributed randomly in 20 houses and indoor for each hamlet. Body weight as well as length measurements of rodents were recorder in order to identify the species and their age. Rodent spleen samples were collected from rodent captured following the Pasteur Institute guidelines [9] in order to detect Yersinia pestis by culture on median agar. Rodent fleas were collected to calculate flea index (number of flea per animal).

To reduce density of rodent-fleas vectors, the insecticide fenithrothion was used by using bait box kartman and Matabi sprayer. Free fleas were collected by using light traps.

The first goal was to calculate the rodent density in the area (number of rodents per species per hamlets) and the flea index (total number of fleas collected, divided by the total number of rodents captured). The second goal was to perform rat spleen sampling for subsequent isolation of Y.pestis.

Results

The insecticide used was fenitrothion™ using Matabi™ sprayer. We used candle flea traps to test the effectiveness of the pesticide, consisting of a plate filled with water or salt or detergent and a lit candle and in its middle to attract fleas.

The outbreak started on week 32 and finished on week 41, there were peaks in week 37, 39 and 41. Over an 11 week period, we identified 30 cases of bubonic plague of which 18 confirmed cases, 6 probable cases and 6 suspect cases. Cases were distributed along 9 weeks while the 13 deaths occurred within 6 weeks (Week 36 to Week 41) (Table 1). There were 10 deaths among confirmed cases and 3 deaths among probable cases given a total of 13 deaths (case fatality rate of 41.9%) linked to plague in the district of Tsiroanomandidy.

New suspected cases were detected among families and neighbors of cases: 2 cases in the municipality of Ambatolampy and then 3 death cases in the municipalities of Tsinjoarivo Imanga, these two municipalities are well known as plague endemics foci (Table 2).

Data analysis

Means and medians were used as measures of central tendency and statistical analysis was implemented using Epi info 7.1.5.0 (CDC Atlanta). Statistical test used is the Chi 2 test for comparison of proportions or Fisher exact for small cell numbers. We used a 95% confidence interval and considered a p-value below 0.05 as significant.

The number of general population used as a denominator data was drawn from the data base of National Institute of Statistics of Madagascar (INSTAT. 2014) and the Demographic and Health Surveys Madagascar (EDSM IV. 2009) [START_REF]Demographic and Health Survey Madagascar[END_REF]. Median age of the cases was 13.5 years (range: 5 to 45 years) and 56.6% (17/30) of cases were under 15 years. There were no significant differences between the proportions of cases in the age group below 15 years old (56.6%) compared to the general population (44.9%) (p=0. [START_REF] Rahalison | Murine surveillance mission report of the Pasteur Institute of Madagascar in the fokontany plague center of the district of Antsirabe II [Rapport de mission de surveillance murine de l'Institut Pasteur de Madagascar dans les fokontany foyer de peste du district d' Antsirabe II[END_REF]).

Case identification

Total W41 W40 W39 W38 W37 W36 W35 W34 W33 W32 Week/lab & status 6 - 1 2 - 1 2 - - - - Alive Suspect - - - - - - - - - - - Deceased 3 - 1 - - 1 - - - - 1 Alive Probable 3 2 - - - - - 1 - - - Deceased 7 2 - 2 1 - 1 - 1 - - Alive Confirmed
The proportion of males among the cases (80%) is significantly higher than the general population (49.8) (P <0.001).

Ninety percent (27/30) of cases occurred in two municipalities (Tsinjoarivo and Ambatolampy) (Figure 1). Table 1 shows the distribution of all cases in each municipality. The outbreak started on week 32 in the municipality of Tsinjoarivo, and the peak was in week 37. During this period, 7 out of the 17 municipalities of Tsiroanomandidy reported cases of plague (Figure 2).

Five new cases among which three deceased were reported in the two municipalities of Tsinjoarivo and Ambatolampy during the term of our investigation.

Cohabitation with animals and generalized poor sanitation were commonly observed in the 5 hamlets visited. Bushfires exist every year, especially during the summer season (September to November)

Reservoirs and vectors

There were 4 positive in Yersinia pestis isolation among the 48 Rattus rattus dissected. The flea index was 2.3. Journal of Case Reports and Studies Forty-five fleas were collected by a flee trap set 6 hours after insecticide spraying in the house of deceased of plague cases in the municipality of Ambatolampy.

Discussion

Tsiroanomandidy is known as a plague endemic district even if not all of its municipalities are affected. During our investigation, seven out of the 17 municipalities of Tsiroanomandidy reported cases of plague and these four municipalities were ranked among the areas with a total number over 40 plague cases for the last six years (2008)(2009)(2010)(2011)(2012)(2013)(2014). Two municipalities (Tsinjoarivo Imanga and Ambatolampy) accounted for 90% of registered cases.

The distribution of case (Table 1) suggests that there is no specific cluster of cases by locality, and cases have been distributed over several weeks in each. Nearly half of the cases deceased (13 /30, i.e. 42%), this high case fatality in the three hamlets may be related to late detection of cases and poor healthcare systems, particularly in remote areas with limited access of care. Population uses primarily traditional healers [START_REF] Ratsitorahina | Recrudescence and spread of plague in Madagascar from 1980 to[END_REF][START_REF] Ratsifasoamanana | Plague, a re-emerging disease in Madagascar [La peste : maladie réémergence à Madagascar[END_REF]. The documented case fatality for bubonic plague is 5 to 10% [START_REF] Rakotoarisoa | Plague: the factors of endemisation of the endemic in the district of Antsirabe II [Peste: les facteurs de pérennisation de l' endémie dans le district d' Antsirabe II[END_REF][START_REF] Chanteau | Current epidemiology of human plague in Madagascar[END_REF]. All cases died at home and did not seek treatment at the health center.

In this outbreak the majority of cases were young men, with a median age of 15 years, and children. Sex ratio (M / F) was 4: 1, in the rural area, boys used to keep the cattle in the fields and men often leave home to work in the fields or even in other regions with high exposure to wild rodents [START_REF] Ratsitorahina | Recrudescence and spread of plague in Madagascar from 1980 to[END_REF][START_REF] Rakotoarisoa | Plague: the factors of endemisation of the endemic in the district of Antsirabe II [Peste: les facteurs de pérennisation de l' endémie dans le district d' Antsirabe II[END_REF][START_REF] Migliani | Epidemiological trends for human plague in Madagascar during the second half of the 20th century: a survey of 20,900 notified cases[END_REF].

The scarcity of rodents captured suggests probable epizootics that occurred before the beginning of the human plague. The presence of positive rodents to the rapid plague test (F1 dipstick assay) during the investigation showed that epizootics were still active in these municipalities. The flea index greater than 2.3 is potentially a condition increasing the risk of plague transmission to humans [START_REF]Atlas de la peste à Madagascar Groupe d'Etudes sur la Peste[END_REF][START_REF] Duplantier | From rural plague without a wild reservoir to urban plague without rodents: the Malagasy paradox [De la peste rurale sans réservoir sauvage à la peste urbaine sans rongeurs : le paradoxe Malagache[END_REF][START_REF] Brossolet | Pourquoi la peste? le rat, la puce, et le bubon[END_REF]. Consequently, it requires particular monitoring and control measures of rodents and vectors.

Insecticides used appeared to be inefficient, which may be attributed to the insecticide flea resistance or an inaccuracy of spreading technique but also a possible deterioration of the product due to poor conservation. This may be the cause of the increase number of cases in some districts [START_REF] Chanteau | Plague, a reemerging disease in Madagascar[END_REF][START_REF] Rahalison | Murine surveillance mission report of the Pasteur Institute of Madagascar in the fokontany plague center of the district of Antsirabe II [Rapport de mission de surveillance murine de l'Institut Pasteur de Madagascar dans les fokontany foyer de peste du district d' Antsirabe II[END_REF][START_REF] Tollenaere | Génétique et évolution du rat noir, Rattus rattus, réservoir de la peste à Madagascar[END_REF][START_REF]Expert Committee on plague[END_REF]. Consequently, tests to determine sensitivity of flea population to insecticides must be conducted periodically and staff that makes the spreading should be trained periodically and provided with adequate equipment. Moreover insecticides must be protected from light and moisture.

Limitations of this study are the potential false negative due to sampling technique on the field, impacting in biological results because the technique of handling the rapid test and the puncture of the bubo might be difficult for non-trained personnel.

Conclusion

The presence of infected flea and rodent during the investigation confirmed that Yersinia pestis was still circulating in this area and the high flea index is a potentially condition to increase the risk of plague transmission to humans. Information concerning the reservoirs and vectors are of great utility to the plague control measures. In this investigation we were able to localize villages or hamlets with active plague focus, but also problems on the effectiveness of insecticides using information obtained about the reservoirs and vectors investigations.

We suggest to systematically performing rodents and vectors elimination in all plague endemic districts before the beginning of plague season especially in August. Controlled use of insecticides and also the periodical training of spraying agents are necessary.

Positioning of antibiotic stocks in remote areas would shorten the delay of treatment administration.

The population should be sensitized on symptoms of plague and educated about procedures in case of plague suspicion by the local health staff in collaboration with the community leaders in the village.

Establishment of surveillance in each village involving community focal point would allow early detection and reporting of rat mortality and suspicious deaths. The focal point could meanwhile ensure that all patients come to the health center immediately at the beginning of the symptoms.

Figure 1 :Figure 2 :

 12 Figure 1: Plague cases by locality according to week of onset in the district of Tsiroanomandidy, August 1st until October 12th, 2014 (week 32 to week 41) (n = 30)

Table 1 :

 1 Plague cases and deaths in the district of Tsiroanomandidy, August 1st until October 12th, 2014 (week 32 to week 41) (n = 30)

	Deceased	-	-	-	1	0	5	0	2	1	2	11
	Total	1	0	1	2	3	7	1	6	3	6	30
							Number	Total	%	P value
	<15 years	Cases General population (EDSM 2009)		17 36 748	30 81 867	56.6 44.9	P=0.19
	Male	Cases General population (EDSM 2009)		24 40 779	30 81 867	80 49.8	P=0.0009
		Plague case distribution according to the age group and sex

Table 2 :

 2 Distribution of plague cases according to age group and sex

Journal of Case Reports and Studies

Dennis DT, Gage KL (1999) Manual of plague: epidemiology, distribution, surveillance and struggle [Manuel de la peste Epidémiologie, répartition, surveillance et lutte], USA.

Acknowledgment

We are deeply indebted to the Malagasy Ministry of Public Health as well as the staff located at the district of Tsiroanomandidy. Epidemiological and laboratory data collection were made possible through dedicated work from staffs from the plague control department of MOH and Plague laboratory Pasteur Institute of Madagascar. This publication was supported by the internal fund of Pasteur Institute of Madagascar and the Ministry of Health of Madagascar.


Aurélien Gautreau

Alain Barrat

Marc Barthélemy

Arrival Time Statistics in Global Disease Spread

Keywords: numbers: 89.75.-k, -87.23.Ge, 05.40.-a

Metapopulation models describing cities with different populations coupled by the travel of individuals are of great importance in the understanding of disease spread on a large scale. An important example is the Rvachev-Longini model [Math. Biosci. 75, 3-22 (1985)] which is widely used in computational epidemiology. Few analytical results are however available and in particular little is known about paths followed by epidemics and disease arrival times. We study the arrival time of a disease in a city as a function of the starting seed of the epidemics. We propose an analytical Ansatz, test it in the case of a spreading on the world wide air transportation network, and show that it predicts accurately the arrival order of a disease in world-wide cities.

In modern societies, individuals can easily travel over a wide range of spatial and temporal scales. The interconnections of areas and populations through various means of transport have important effects on the geographical spread of epidemics. In particular, the structure and the different complexity levels of the air-transportation network are responsible for the heterogeneous and seemingly erratic outbreak patterns observed in the worldwide propagation of diseases [START_REF] Colizza | Proc. Natl. Acad. Sci. (USA)[END_REF] as recently documented for SARS [2,[START_REF] Hufnagel | Proc. Natl. Acad. Sci[END_REF]. In order to describe such a complex phenomenon and to obtain powerful numerical forecasting tools, different levels of description are possible, ranging from a simple global mean-field to detailed agent-based simulations [START_REF] Anderson | Infectious diseases in humans[END_REF][START_REF] Hethcote | [END_REF]6,7,8,9,10] that recreate entire populations and their dynamics at the scale of the single individual [10].

At large scale, such as the world-wide level, a very important class of models in modern epidemiology are the so-called metapopulation models which use a description at two levels by dividing the global population into interconnected subpopulations. Within each subpopulation, a mean-field like model of epidemic spreading is used, while the spread from one subpopulation to another is due to the travel of individuals. Agents of each subpopulation can be in various states (healthy, infectious, recovered...), change state by contact with other agents, and diffuse on the transportation network between subpopulations. Metapopulation models can thus be considered as reaction-diffusion processes, which opens very interesting perspectives and issues [11] within the global framework of dynamical phenomena occurring on complex networks [12,[START_REF] Dorogovtsev | Evolution of networks: From biological nets to the Internet and WWW[END_REF][START_REF] Pastor-Satorras | Evolution and structure of the Internet: A statistical physics approach[END_REF][START_REF] Boccaletti | [END_REF]. For the description of worldwide epidemic spreading, the subpopulations are cities connected by a transportation network in which links correspond to the existence of passenger flows described by the worldwide air-transportation network (WAN). The WAN represents a major channel for the worldwide spread of infectious diseases [START_REF] Colizza | Proc. Natl. Acad. Sci. (USA)[END_REF][START_REF] Hufnagel | Proc. Natl. Acad. Sci[END_REF] and its complex, heterogeneous features at various levels (degree distribution, traffic, populations) have recently been characterized [START_REF] Barrat | Proc. Natl. Acad. Sci[END_REF][START_REF] Guimerà | [END_REF].

In this Letter, we focus, in the framework of such metapopulation models, on the issue of the arrival time in a city of the first infectious individual. In particular, we study how this time depends on the origin of the disease and on the network characteristics. This problem is more complex than the one of random walks on complex networks [18], since the number of infectious individuals diffusing on the network is constantly evolving due to the inner-city epidemic dynamics. We also note that references [19,20] were also concerned with the arrival time problem for an epidemic spreading on a complex network, but in a different framework: each network node was an individual (susceptible or infectious), while in our case each node represents a whole subpopulation. After the precise definition of the model, we will first consider the simple case of a one-dimensional topology for the transportation network in order to gain analytical insights into this problem. This will allow us to propose an analytical form for the arrival time in arbitrary networks. We then test this form in the case of the WAN, by simulating numerically a stochastic spreading phenomenon on the network, and show that we can indeed predict with a good accuracy the spreading phenomenon and the arrival order of a disease in various cities at a world-wide level.

While the precise model describing the epidemic spreading at the subpopulation level could be refined at will in order to describe a particular disease, we are here interested in generic and fundamental aspects of the metapopulation modeling approach. We therefore restrict our study to a simple SI disease model in which individuals are either healthy (susceptible, S) or can become infectious (I) if in contact with an infectious individual. The Rvachev-Longini SI model [21] describes the evolution of the number of infectious I i (t) individuals (and also of S i (t)) in each city i through

∂ t I i = K({X i }) + Ω({I j }) , (1)
where the first term K of the right hand side describes the (epidemic) reaction process inside each subpopulation (city), due to the interaction of individuals in the various possible states. In our case X ∈ {S, I} (we have checked that more involved models, such as SIS or SIR, give consistent results [22]) and the standard homogeneous mixing assumption in each city gives [START_REF] Anderson | Infectious diseases in humans[END_REF]:

K({X i }) = λI i (N i -I i )/N i ,
where N i is the population of city i and λ the spreading rate. The second term Ω represents the evolution due to the arrival or departure of infectious individuals from or to other cities and is determined by passenger flows on the transportation network. This model therefore considers a simplified mechanistic approach with a widely used markovian assumption in which individuals are not labeled according to their original subpopulation, and at each time step the same traveling probability applies to all individuals in the subpopulation, without memory of their origin [START_REF] Colizza | Proc. Natl. Acad. Sci. (USA)[END_REF][START_REF] Hufnagel | Proc. Natl. Acad. Sci[END_REF]21]. Denoting by w ij the average number of passengers traveling from i to j per unit of time (w ij = 0 if there is no direct connection), the probability per unit time that an individual travels from city i to city j is then given by w ij /N i .

The full metapopulation model is therefore described by

∂ t I i = λI i (t) N i -I i (t) N i + j w ji N j I j - j w ij N i I i . (2)
This original formulation considers only expectation values, which can take continuous values, so that "fractions" of infectious individuals can travel and infect neighboring cities arbitrarily fast [START_REF]A numerical integration of (2) leads to an infection of all cities at time 0 +[END_REF]. To investigate arrival times, one therefore needs to take into account the inherent stochasticity of the spreading. We thus consider in all our numerical simulations the stochastic generalization described in [START_REF] Colizza | Proc. Natl. Acad. Sci. (USA)[END_REF][START_REF] Hufnagel | Proc. Natl. Acad. Sci[END_REF] where the number of individuals traveling on each connection is an integer variable randomly extracted at each time step of length ∆t, with average ∆tw ij I i /N i (in the numerical simulations we will use ∆t = 1 day); for simplicity we keep the endogenous growth deterministic since we are mainly concerned with the effect of travel, but we have checked that inclusion of stochastic effects as in [START_REF] Colizza | Proc. Natl. Acad. Sci. (USA)[END_REF] do not change our results [22]. Note that in real cases such as the WAN, most weights are symmetric (w ij = w ji ) [START_REF] Barrat | Proc. Natl. Acad. Sci[END_REF] but the probabilities of travel from one city to another are not since they depend on the populations of the various cities: the travel effectively occurs as a random diffusion with non-symmetric rates on the transportation network. The topological distance thus does not contain all the information needed to characterize such a process. Moreover, since most transportation networks are small-world networks, many cities lie at the same topological distance from a given seed, but will potentially be reached at very different times. Before turning to numerical simulations of the described model, we present an analytical approach to the determination of arrival times. Let us first consider the simple case of two cities (0 and 1), with populations N 0 , N 1 which are connected by a passenger flux w 01 = w. We assume that at t = 0, there are I 0 = 1 infectious people in the city 0. Let us first consider that the travel events occur as instantaneous jumps of probability p = w N0 ∆t, at discretized times, in units of ∆t. The probability that the time of arrival t 1 of the epidemic in the city 1 is equal to t = n∆t is then

P d (t 1 = n∆t) = 1 -(1 -p) I 0 (n∆t) n-1 i=1 (1 -p) I 0 (i∆t) .
(3) In order to obtain the density probability P (t) of the arrival time in the city 1 we consider the limit ∆t → 0, using the following assumptions: (i) I 0 (t) ≪ N , which is realistic for usual diseases, in which only small fractions of the population are infectious; (ii) the continuous limit for I 0 (t) can be used which reads 1 λ ≪ t 1 . Within these assumptions, we obtain

P (t)dt = w N 0 e λt-w N 0 λ e λt dt (4)
(the last assumption then reads 1 ≪ ln( N0λ w )). We recognize in (4) a Gumbel distribution with average

t 1 = 1 λ [ln( N0λ w ) -γ],
where γ is the Euler constant. The variance is V ar(t 1 ) = π √ 6λ and does not depend of w N0 (the non physical contribution of the negative values of t in the distribution has to be negligible which is satisfied if 0 -∞ P (t)dt = w N0λ ≪ 1). Within these assumptions, we obtain a good agreement between results of numerical simulations using discretized travel events [START_REF] Colizza | Proc. Natl. Acad. Sci. (USA)[END_REF] and the theory which uses continuous approximations (see Fig. 1). We now consider the case of a one-dimensional line of cities connected by passenger fluxes of random intensity. We assume that the spreading process starts at city 0 and we denote by t n the arrival time in the city n. The quantities having the same unit as t n are 1/λ and N i /w i , where w i is the number of passengers traveling from i to i + 1 per unit time. Dimensional analysis then implies that the probability distribution of the adimensional quantity λt n must be a function of the other adimensional quantities which are the w i /(lambdaN i ):

P (λt n ) = G n (λt n , { wi Niλ })
, where G n is an unknown function. One can write t n as a sum of random variables, ∆ i = t i -t i-1 which are however correlated since each local infection process depends on the history of the epidemics in all previously infected cities. While a complete study of P (λt n ) is left for future work [22], numerical simulations of the spreading show (Fig. 2) that it obeys important invariance properties. For heterogeneous populations and travels (w i and N i are distributed uniformly in [10,2000] and [10 5 , 2.10 7 ], respectively), the whole distribution is invariant when one replaces (i) all the random weights by their geometrical mean w = ( n-1 i=0 w i ) 1/n ; (ii) all the random populations by their geometrical mean N = ( n-1 i=0 N i ) 1/n ; (iii) all weights by w and all populations by N . The ratios of the average times for these different sets stay very close to 1, with deviations at most of the order of 5%.

The average arrival time can thus be written as λ t n = F ({ wi Niλ }) where F (x 1 , . . . , x n ) is a symmetric function of its variables which depends only on the product x i , and such that t 1 is the average of the Gumbel distribution (4). This leads to the following Ansatz (C) uniform populations Ni = N and weights wi = w. We use a small value of n since most real complex networks are small-world: any node lies at a small distance from the seed.

λ t n ≈ χ(n) ≡ ln n-1 i=0 N i λe -γ w i . ( 5
Figure 3 shows that the average arrival time in a city is indeed determined by χ to a very good extent (while the arrival time at a given topological distance from the seed can vary a lot). More quantitatively, χ is approximately proportional to λ t , which it slightly overestimates since we neglect the flow of infectious individuals from n -2 to n -1 with respect to the endogenous increase of We now consider a generic transportation network between the cities. The quantity (5) can easily be computed on any path of length n on the network. While the spread can a priori follow multiple paths from one city to another, we can reasonably assume that the most probable path is the one which minimizes the value of χ computed on it, leading to the smallest arrival time possible (a more refined Ansatz taking into account multiple paths does not lead to strong differences in the final results [22]). We thus obtain the following Ansatz for the arrival time at a city t of a disease starting at node s χ(s, t) = min

I n-1 during [t n-1 ; t n ] [22].
{Pst} (k,l)∈Pst ln N k λ w kl -γ (6)
where {P sj } is the set of all possible paths connecting s to t, and the sum is over the links (k, l) on the paths. In other terms, we have introduced a new (non symmetric) weight ln(N i λ/w ij ) -γ on each oriented link (i, j) of the network.

We have simulated, using the model developed in [START_REF] Colizza | Proc. Natl. Acad. Sci. (USA)[END_REF], and summarized above, a spreading phenomenon on a subnetwork of the WAN, composed of the 2, 400 nodes for which the populations are larger than 10, 000 inhabitants and which corresponds to 98% of the total traffic [START_REF]Similar results are obtained for simulations on various network models[END_REF]. The arrival times are computed by solving numerically the equations of the Rvachev-Longini model with discretized random travel events, and averaging over 1, 000 realizations of the spreading with the same seed (one infectious individual in a given city). Figure 4 shows the obtained values of λ t versus χ for various initial seeds. We observe that the average arrival time is indeed determined by the value of χ in a given city: various cities with the same χ are reached at the same time by the disease propagation. While χ quantitatively overestimates the arrival time, the two quantities are correlated strongly enough, in order to obtain with a good confidence the order of arrival of the disease in different cities. More precisely, if we denote ∆χ(i, j) =| χ(j) -χ(i) |, we show in Fig. 5 the probability f c (∆χ) that the arrival times in one realization of the spread t (i) and t (j) follow the same order as given by χ(i) and χ(j) [ie.

(t (i) -t (j) )(χ(i) -χ(j)) > 0]. In other words, f c is the probability that the disease arrival rank for the two cities i and j is correctly predicted by χ. If ∆χ(i, j) is equal to 0, no prediction is possible and we indeed obtain f c (0) = 0.5. For ∆χ > 10, almost all node couples are correctly ranked. This result has however to be weighted by the number of couples with such a large ∆χ. We thus plot on the same figure the cumulative distribution p > (∆χ) of the number of couples of nodes with a given value of ∆χ. We see for example that approximately 80% of the couples of cities have a ∆χ > 2 and more than 70% of these couples are correctly sorted (instead of just 50% on average if no information is available). From a theoretical point of view, metapopulation models go far beyond classical random walks and deserve many further theoretical investigations. In this Letter, we have proposed an Ansatz for the arrival time of a disease in a city, knowing the starting point of the spread. This Ansatz is a good approximation and predicts with accuracy the arrival order of the disease in the different cities, even if they are at the same topological distance from the seed [22]. Containment strategies could use such information to target the cities most at risk of rapid infection, and therefore deploy limited supplies of vaccine or antivirals in an efficient way. Further developments could include more sophisticated compartmental or metapopulation models, and the systematic investigation of various structures of complex networks [22]. Finally, it would be interesting to extend this study to other scales, like the urban scale, where nodes are locations such as homes, offices or malls [10].

FIG. 1 :

 1 FIG.1: Two cities model. Arrival time t1 distribution computed by numerical simulation and compared with the result of Eq. (4) for w N 0 λ = 10 -2 (line). Inset: Same for w N 0 λ = 10 -1 .

  FIG.2: (A-C) Arrival time distribution on a line at city #7, from numerical simulations for a fixed random set of populations {Ni} and weights {wi} (Black circles). Red crosses: distributions for (A) uniform travel wi = w, and populations {Ni}; (B) uniform populations Ni = N , and weights {wi}; (C) uniform populations Ni = N and weights wi = w. We use a small value of n since most real complex networks are small-world: any node lies at a small distance from the seed.

FIG. 3 :

 3 FIG.3: λ tn vs. χ(n) for 5 cities connected on a line, with 100 different random sets {wi, Ni}. Each point is an average over 1, 000 epidemics for each realization of the w's.

FIG. 4 :FIG. 5 :

 45 FIG.4: (Color online) λ t versus χ on the WAN for diseases starting in different cities (whose name is specified in each graph). Each red circle corresponds to a city and averages are done over 1, 000 realizations of the spreading. Crosses are an average over cities with the same χ. When the initial seed is a hub, the average arrival time is larger than χ in the first reached cities, due to the multiplicity of possible paths[22].

Acknowledgments. We thank V. Colizza and A. Vespignani for discussions and comments. A.G. and M.B. also thank the School of Informatics, Indiana University where part of this work was performed. We are very grateful to V. Colizza for providing the data on city populations and we thank IATA (http://www.iata.org) for making their database available to us. A.G. and A.B. are partially supported by EU contract 001907 (DELIS).


Sébastien Jansou

Nicolas Ressayre

INVARIANT DEFORMATIONS OF ORBIT CLOSURES IN sl(n)

We study deformations of orbit closures for the action of a connected semisimple group G on its Lie algebra g, especially when G is the special linear group.

The tools we use are on the one hand the invariant Hilbert scheme and on the other hand the sheets of g. We show that when G is the special linear group, the connected components of the invariant Hilbert schemes we get are the geometric quotients of the sheets of g. These quotients were constructed by Katsylo for a general semisimple Lie algebra g; in our case, they happen to be affine spaces.

Introduction

Let G be a complex reductive group, and V be a finite dimensional Gmodule. A fundamental problem is to endow some sets of orbits of G in V with a structure of variety. The geometric invariant theory is the classical answer in this context: the set of closed orbits of G in V has a natural structure of affine variety. We denote by V //G this variety, equipped with a G-invariant quotient map π : V → V //G.

Recently, Alexeev and Brion defined in [AB] a structure of quasiprojective scheme on some sets of G-stable closed affine subscheme of V . A natural question is to wonder what happens when one applies Alexeev-Brion's construction to the orbit closures of G in V . Here, we study this construction in the case of a well known G-module, namely the adjoint representation of a semisimple group G, especially when G is the special linear group SL (n).

From now on, we assume that G is semisimple, and denote by g its Lie algebra endowed with the adjoint action of G. Let us recall that a sheet of g is an irreducible component of the set of points in g whose G-orbit has a fixed dimension. Let us fix a sheet S. We show that the G-module structure on the affine algebra C[G • x] of the orbit closure G • x of x doesn't depend on x in S. This allows us to define a set-theoretical application from S to some Alexeev-Brion's invariant Hilbert scheme of g:

π S : S -→ Hilb G S (g) x -→ G • x.
A unique sheet is open in g: we call it the regular one, and denote it by g reg .

In Section 2 we are interested in Hilb G greg (g). The graph of the quotient map π : g → g//G is a flat family of G-stable closed subschemes of g over g//G. So, this family is the pullback of the universal one by a morphism. We prove that this morphism is an isomorphism by showing that Hilb G greg (g) is smooth and applying Zariski's main theorem. So, we obtain that the application π greg identifies with the restriction of the quotient map π : g → g//G; in particular, it is a morphism.

In Section 3, we study any sheet S for G = SL(n). We explicitly construct a flat family over an affine space whose fibers are the closures in g of the G-orbits in S. Then, we show following the same method as in the case of g reg that this family is universal. Let us denote by π : S → S/ SL(n) the geometric quotient of S, constructed by Katsylo in [Ka]. We show that there is a canonical morphism

θ : S/ SL(n) -→ Hilb SL(n) S (g) SL(n) • x -→ SL(n) • x
which is actually an isomorphism onto a connected component of Hilb SL(n) S (g). Another motivation for this work is to understand examples of invariant Hilbert schemes. Indeed, the construction of Alexeev and Brion is indirect and only few examples are known (see [J], [BC]). Here, the connected components of invariant Hilbert schemes we obtain happen to be affine spaces, as in [J] and [BC]. Note that this answers in the case of SL(n) to a question of Katsylo who asked if the geometric quotient S/G is normal.

Hilbert's sheets

We consider schemes and affine algebraic groups over C. Let G be a connected semisimple group. We choose a Borel subgroup B, and a maximal torus T contained in B. We denote by U the unipotent radical of B; we have B = T U .

We denote by Λ the character group of T . We denote by Λ + the set of elements of Λ that are dominant weights with respect to B. The set Λ + is in bijection with the set of isomorphism classes of simple rational G-modules. If λ is an element of Λ + , we denote by V (λ) a simple G-module associated, that is of highest weight λ.

If V is a rational G-module, we denote by V (λ) its isotypical component of type λ, that is the sum of its submodules isomorphic to V (λ). We have the decomposition

V = λ∈Λ + V (λ) .
In any decomposition of V as a direct sum of simple modules, the multiplicity of the simple module V (λ) is the dimension of V U (λ) . We say that V has finite multiplicities if these multiplicities are finite (for any dominant 2 weight λ).

Let us recall some definitions from [START_REF] Alexeev | Moduli of affine schemes with reductive group action[END_REF]§1]. A family of affine G-schemes over some scheme S is a scheme X equipped with an action of G and with a morphism π : X → S that is affine, of finite type and G-invariant. We have a G-equivariant morphism of O S -modules

π * O X ≃ λ∈Λ + F λ ⊗ C V (λ),
where each

F λ := (π * O X ) U (λ)
is equipped with the trivial action of G. Let h : Λ + → N be a function. The family X is said to be of Hilbert function h if each F λ is an O S -module locally free of rank h(λ). (Then the morphism π is flat.)

Let X be an affine G-scheme, and h : Λ + -→ N a function. A family of G-stable closed subschemes of X over some scheme S is a G-stable closed subscheme X ⊆ S × X. The projection S × X → S induces a family of affine G-schemes X → S. The contravariant functor: (Schemes) • -→ (Sets) that associates to every scheme S the set of families X ⊆ S × X of Hilbert function h is represented by a quasiprojective scheme denoted by

Hilb G h (X) ([AB, §1.2].
The dimension of an affine G-scheme whose affine algebra has finite multiplicities can be read on its Hilbert function: If Y is horospherical, that is ([AB, Lemma 2.4]) if for any dominant weights λ, µ, we have A (λ) • A (µ) ⊆ A (λ+µ) , it is clear that the dimension of Y can be read on its Hilbert function. Indeed, let us denote by θ 0 the linear map from Λ ⊗ Q to Q which associates to any fundamental weight the value 1. We denote by θ the group homomorphism from Λ to Z that is the restriction of θ 0 . We associate to θ a graduation of the algebra A by N: its homogeneous component of degree d is

A d := λ∈Λ + , θ(λ)=d A (λ) .
The dimension of A d is finite, and depends only on h:

dim A d = λ∈Λ + , θ(λ)=d h(λ) dim V (λ).
So the Hilbert polynomial of the graded algebra A depends only on h, and so does the dimension of Y .

We can deduce the proposition. Indeed, Y admits a flat degeneration over a connected scheme to a horospherical G-scheme Y ′ that admits the same Hilbert function (by [START_REF] Alexeev | Moduli of affine schemes with reductive group action[END_REF]Theorem 2.7]). So dim Y = dim Y ′ depends only on h.

We will use the method of "asymptotic cones" of Borho and Kraft ([PV, §5.2]): let V be a finite dimensional rational G-module and F the closure of an orbit in V (or, more generally, any G-stable closed subvariety contained in a fiber of the categorical quotient V → V //G). We embed V into the projective space P(C⊕V ) of vector lines of C⊕V by the inclusion v → [1⊕v]. The closure of F in P(C ⊕ V ) is denoted by F . The affine cone in C ⊕ V over F is the closed cone X generated by F .

The vector space C ⊕ V , equipped with its natural scheme structure, is denoted by A 1 × V . The cone X ⊆ A 1 × V , viewed as a reduced closed subscheme, is a flat family of affine G-schemes. Its fibers over non-zero elements are homothetic to F . Its fiber over 0 is a reduced cone, denoted by F . It is contained in the null-cone of V (that is the fiber of the categorical quotient V → V //G containing 0). Its dimension is the same as F .

We consider the adjoint action of G on its Lie algebra g. If x is an element of g, the affine algebra of the closure of its orbit, viewed as a reduced scheme, has finite multiplicities. Let us denote by h x its Hilbert function; we call it the Hilbert function associated to x. In this paper, we are interested in the connected component denoted Hilb G

x of the scheme Hilb G hx (g) that contains G • x. It gives the G-invariant deformations of G • x embedded in g. We determine it when x is in g reg in §2, and for any x when G is the special linear group in §3.

Let us denote by G x the stabilizer of x in G, and g x its Lie algebra. The coadjoint action of G x is its natural action on the dual vector space g *

x .

Proposition 1.2. Let us assume the orbit closure G • x to be normal. The tangent space T G•x Hilb G x to Hilb G x at the point G • x is canonically isomorphic to the space of invariants of the coadjoint action of G x .

Proof. The tangent space to G • x at the point x is g.x; it is stable under the action of G x . We denote by [g/g.x] Gx the space of invariants under the action of G x on the quotient vector space g/g.x. According to [START_REF] Alexeev | Moduli of affine schemes with reductive group action[END_REF]Proposition 1.15 (iii)], we have a canonical isomorphism

T G•x Hilb G x ∼ = [g/g.x] Gx .
(1) Indeed, the orbit closure G • x is assumed to be normal. Moreover, every orbit in g has even dimension, and has a finite number of orbits in its closure ( [START_REF] Popov | Vinberg Invariant Theory[END_REF]Corollary 3 page 198]), so the codimension of the boundary of G • x in G • x is at least 2, and the proposition of [AB] can be applied.

To transform (1) into the isomorphism of the proposition, we will use the Killing form on g, denoted by κ. As g is semisimple, its Killing form gives an isomorphism

φ : g -→ g * y -→ κ(y, •).
The isomorphism φ is G-equivariant, thus G x -equivariant. It sends g.x onto the space g ⊥

x of linear forms on g that vanish on g x . Indeed, the common zeros of the elements of φ(g.x) are the elements y in g such that

∀z ∈ g, κ([z, x], y) = 0, that is ∀z ∈ g, κ(z, [x, y]) = 0,
and this last condition means that y belongs to g x since κ is non-degenerate.

Thus the short exact sequence of

G x -modules 0 -→ g.x -→ g -→ g/g.x -→ 0 identifies (thanks to φ) with 0 -→ g ⊥ x -→ g * -→ (g x ) * -→ 0,

and the proposition follows from (1).

A sheet of g is a maximal irreducible subset of g consisting of G-orbits of a fixed dimension. Every sheet of g contains a unique nilpotent orbit. A regular element of g is an element of g whose orbit has maximal dimension. The open subset of g whose elements are the regular elements is a sheet denoted by g reg .

Let us call Hilbert's sheet a maximal irreducible subset of g consisting of elements admitting a fixed associated Hilbert function.

Proposition 1.3. The Hilbert's sheets of g coincide with its sheets.

Proof. According to Proposition 1.1, any Hilbert's sheet is contained in some sheet. It just remains to check that two points of some sheet S have the same associated Hilbert function.

Let F be the closure of an orbit in S. We recalled that its asymptotic cone F is a degeneration of F . In particular, it is contained in the closure of S. Moreover, F is contained in the null-cone of g, and its dimension is the same as F . So F is the closure of the nilpotent orbit of S.

The affine algebra of g is the symmetric algebra of g * . Its graduation induces a G-invariant filtration on the affine algebra A of F . The affine algebra of the asymptotic cone F is isomorphic, as an algebra equipped with an action of G, to the graded algebra  associated to the filtered algebra A. In particular, A and  are isomorphic as G-modules, and their multiplicities are equal: the Hilbert function of F is equal to that of F , and the proposition is proved.

Notice that in the case of the regular sheet, Proposition 1.3 is a direct consequence of [START_REF] Kostant | Lie group representations on polynomial rings[END_REF]Theorem 0.9].

Regular case

Let us denote by h reg the Hilbert function associated to the regular elements of g (Proposition 1.3). In this section, we prove that the invariant Hilbert scheme H reg := Hilb G hreg (g) is the categorical quotient g//G, that is an affine space whose dimension is the rank of G.

By [Ko, Theorem 0.1], all schematic fibers of the quotient morphism g → g//G are reduced. This allows us to identify in the following the schematic fibers with the set-theoretical fibers.

2.1 A morphism from g//G to H reg Let X reg be the graph of the canonical projection g → g//G. It is a family of G-stable closed subschemes of g over g//G.

Proposition 2.1. The closed subscheme X reg is a family of G-stable closed subschemes of g with Hilbert function h reg .

Proof. Let us denote by π : X reg → g//G the canonical projection, and by R := π * O Xreg the direct image by π of the structural sheaf of X reg . We have to prove that for any dominant weight λ, we have that R U (λ) is a locally free sheaf on g//G of rank h(λ).

Let us first study the case where λ = 0. The morphism π//G :

X reg //G → g//G induced by π is clearly an isomorphism. So R G = R U (0) is a free module on g//G of rank 1 = h reg (0). Let λ be a dominant weight. It is known (see [AB, Lemma 1.2]) that R U (λ) is a coherent R G -module.
Thus it is a coherent module on g//G. To see that it is locally free, we just have to check that its rank is constant. The fibers of π are those of the canonical projection g → g//G, so they are the orbit closures of the regular elements, and all of them admit h reg as Hilbert function. So the rank of R U (λ) at any closed point of g//G is h(λ), and the proposition is proved. This gives us a canonical morphism

φ reg : g//G -→ H reg .
We will prove in the following of §2 that φ reg is an isomorphism.

Lemma 2.2. The morphism φ reg realizes a bijection from the set of closed points of g//G to the set of closed points of H reg .

Proof. We remark that φ reg is injective. Let us check it is surjective: in other words, that any G-invariant closed subscheme of g of Hilbert function h reg is a fiber of g → g//G.

Let Y be such a subscheme. As h reg (0) = 1, it has to be contained in some fiber F of g → g//G over a reduced closed point. But F already corresponds to a closed point of H reg in the image of φ reg . Moreover, F admits no proper closed subscheme admitting the same Hilbert function, so F = Y , and the lemma is proved.

Let us denote by r the rank of G. The quotient g//G is an affine space of dimension r. A consequence of Lemma 2.2 is:

Corollary 2.3. The dimension of H reg is r.

Tangent space

In this section, we prove:

Proposition 2.4. The scheme H reg is smooth.

Proof. Let Z be a closed point of H reg . We have to prove that the dimension of the tangent space T Z H reg is r. We still denote by Z the closed subscheme of g corresponding to Z. By Lemma 2.2, we know that Z is a fiber of the morphism g → g//G, thus the closure of some regular element x. It is a normal variety. By Proposition 1.2, we have to prove that the dimension of (g * x ) Gx is r, or simply that it is lower or equal to r (by Corollary 2.3).

Let us prove that the dimension of the bigger space

(g * x ) gx
is r, and the proposition will be proved.

A linear form on g x is g x -invariant iff it vanishes on the derived algebra [g x , g x ], so we have to prove that (g x /[g x , g x ]) * is r-dimensional. We will prove that g x is an r-dimensional abelian algebra, and the proposition will be proved. This is true if x is semisimple, because then g x is a Cartan subalgebra of g. If the regular element x is not assumed to be semisimple, the dimension of g x is still r, because this doesn't depend on the regular element x, by definition. Let us check that g x is abelian.

Let us denote by Grass r (g) the grassmannian of r-dimensional subspaces of g, endowed with its projective variety structure. The subset of g reg × Grass r (g):

{(z, h) ∈ g reg × Grass r (g) | h • z = 0 and [h, h] = 0}
is closed, so its image by the natural projection into g reg is closed too. As its image contains the semisimple elements of g reg , it is equal to g reg . Thus g x is abelian for any regular x, and the proposition is proved.

Conclusion

We can now conclude that the family X reg of Proposition 2.1 is the universal family:

Theorem 2.5. The morphism φ reg from g//G to H reg is an isomorphism.

Proof. The morphism φ reg is bijective (Lemma 2.2) and H reg is normal. According to Zariski's main theorem, φ reg is an isomorphism.

Remark 2.6. One knows there is a canonical morphism

ψ reg : H reg -→ g//G
that associates to any closed point F of H reg (viewed as a closed subscheme of g) its categorical quotient F //G (viewed as a closed point of g//G). This morphism is a particular case of morphism

η : Hilb G h (V ) -→ Hilb h(0) (V //G)
defined in [AB, §1.2], because h reg (0) = 1 and thus the punctual Hilbert scheme that parametrizes closed subschemes of length 1 in g//G identifies with g//G itself. The morphism ψ reg is clearly the inverse morphism of φ reg .

Remark 2.7. As pointed to us by M. Brion, Theorem 2.5 admits the following generalization:

Let X be an irreducible affine G-variety such that π : X → X//G is flat. Let h be the Hilbert function of its fibers. Then the graph Γ of π is the universal family; in particular, Hilb G h (X) identifies with X//G.

The idea of his proof is to check that Γ represents the functor. Let X ⊆ X × S be a flat family of Hilbert function h, over some affine scheme S. Since h(0) = 1, the scheme S identifies with X//G and maps on X//G (by the morphism induced by the first projection X × S → X). We obtain the following commutative diagram:

X p 2 -Γ X//G ≃ S ? -X//G. ?
It remains to prove that X is isomorphic (canonically) to the fiber product Γ × X/ /G S. This has only to be verified over the closed points of S. The assertion follows.

The Hilbert schemes we obtain applying the above Brion's result to Gmodules are always affine spaces. The representations V of a simple group G such that V → V //G is flat have been classified by G. Schwarz in [Sch].

Unfortunately, the sheets of sl(n) are not affine in general and Katsylo's quotient cannot be extended to their closure. So, Brion's theorem cannot be applied, whereas the method we used to prove Theorem 2.5 can be used.

Case of sl(n)

We denote by t an indeterminate over C, and I n the identity matrix of size n×n. If x is an element of sl(n) and i = 1 • • • n, we denote by Q x i (t) the monic greatest common divisor (in the ring C[t]) of the (n + 1-i)× (n + 1-i)-sized minors of x -tI n , and Q x n+1 (t) := 1. Then we put

q x i (t) := Q x i (t)/Q x i+1 (t). The polynomials q x 1 (t), • • • , q x n (t)
are the invariant factors of the matrix x -tI n with coefficients in the euclidean ring C[t], ordered in such a way that q x i+1 (t) divides q x i (t).

If x, y are elements of sl(n), then y is in the closure of the orbit SL(n) • x of x if and only if for any i = 1 . . . n, the polynomial Q x i (t) divides Q y i (t). In other words, iff for any i, the polynomial

Q x i (t) divides the (n + 1 -i) × (n + 1 -i)-sized minors of y -tI n .
According to [W], when x is nilpotent, these conditions defines the closure of SL(n)•x as a reduced scheme: to be more precise, when one divides a (n+1-i)×(n+1-i)-sized minor of y -tI n by Q x i (t) using Euclid algorithm, the remainder he gets is a regular function of y. All such functions generate the ideal of the closure of SL(n) • x. We will deduce easily from this difficult result that the same remains true if x is no longer assumed to be nilpotent.

The set of sheets of sl(n) is in bijection with the set of partitions n, that is of sequences σ [START_REF] Bongartz | Schichten von Matrizen sind rationale Varietäten[END_REF]§2.3]). Namely, if σ is a partition of n, the elements of the correspondent sheet S σ are those elements x such that for any i, the polynomial q x i (t) is of degree b i . We denote by σ = (c 1 ≥ c 2 ≥ c 3 ≥ . . . ) the conjugate partition, where c j is the number of i such that b i ≥ j. We denote by h σ the Hilbert function associated to the points of S σ (Proposition 1.3). We denote by Z σ the closure of the nilpotent orbit of S σ . The connected component of Hilb SL(n) hσ (sl(n)) that contains Z σ as a closed point is denoted H σ . We will prove in this section that H σ is an affine space of dimension b 1 -1. The proof is similar to §2.

= (b 1 ≥ b 2 ≥ b 3 ≥ . . . ) of nonnegative integers such that b 1 + b 2 + b 3 + • • • = n (see
We recall that the sheets of sl(n) are smooth ( [Kr]).

3.1 A construction of the geometric quotient of S σ Katsylo showed in [Ka] that any sheet of a semisimple Lie algebra admits a geometric quotient. Although his proof contains an explicit construction, it doesn't make clear the geometric properties of the quotient. Here we present a simple description of the quotient in the case of the Lie algebra sl(n). It takes on the invariant factors theory. We get that the quotient is an affine space.

Lemma 3.1. Given some i, the application S σ -→ A b i that associates to any x the coefficients of

q x i (t) = t b i + λ x b i -1 t b i -1 + • • • + λ x 0 t 0 is regular. Proof.
Up to scalar multiplication, the polynomial q x i (t) is the unique nonzero polynomial of degree less or equal to b i such that dim ker q

x i (x) ≥ N := b i j=1 c j . (2)
Thus the closed subset of S σ × P b i consisting of elements (x, [µ 0 :

• • • : µ b i ]) such that dim ker( b i j=0 µ j x j ) ≥ N
is the graph of the application

ψ : S σ -→ P b i x -→ [λ x 0 : • • • : λ x b i -1 : 1]
According to [START_REF] Harris | Algebraic geometry: a first course[END_REF]Exercise 7.8 p 76], this graph is also the graph of a rational map φ from S σ to P b i . On the open subset Ω of S σ where φ is regular, φ coincides with ψ, so the functions x → λ x j are regular functions from Ω to A 1 . As S σ is smooth, the complementary of Ω in S σ has codimension at least 2 ([Sha, Thm 3 chap II.3.1]). We conclude that the functions extend to regular functions from S σ to A 1 . By continuity, these extensions satisfy (2), so they coincide with the functions x → λ x j on S σ .

Let us define, for any x in S σ , the monic polynomial of degree b i -b i+1 :

p x i (t) := q x i (t)/q x i+1 (t)
(where q x n+1 := 1). It follows from the previous lemma that its coefficients, viewed as functions of x, are regular functions from S σ to A 1 . Given an x, the family (p x 1 (t), . . . , p x n (t)) can be any family of monic polynomials of degrees b i -b i+1 , provided the following relation is satisfied, where S(p x i ) denotes the sum of the roots of p x i , counted with multiplicities (given by its first nondominant coefficient):

n i=1 iS(p x i ) = 0
(this relation simply means that the trace of x is zero). Thus, associating to any x the coefficients of the family (p x 1 (t), . . . , p x n (t)), we get a regular map π from S σ to a linear hyperplane of C b 1 , which we will denote by

A b 1 -1 . Proposition 3.2. The map π : S σ -→ A b 1 -1 is the geometric quotient of S σ .
Proof. This map is surjective, and its fibers are exactly the orbits of S σ under the action of SL(n). Let us denote by S σ / SL(n) the geometric quotient of S σ (whose existence is proved in [Ka]). The map π is the composite of the canonical projection from S σ to S σ / SL(n) with a regular bijection

S σ / SL(n) -→ A b 1 -1 .
This last map is bijective (thus birational), and the space A b 1 -1 is normal. According to Zariski's main theorem, it is an isomorphism.

A morphism from

S σ / SL(n) to H σ If z = (p 1 (t), . . . , p n (t)) is a closed point of A b 1 -1 corresponding to the orbit SL(n) • x in S σ , the polynomial Q x i (t) = p i (t) • (p i+1 (t)) 2 • ... • (p n (t)) n-i+1
only depends on z. Let us denote it by Q z i (t). Its coefficients are regular functions from

A b 1 -1 to A 1 .
Let us consider the closed subscheme X σ of {(z, y) ∈ A b 1 -1 × sl(n)} defined by the vanishing, for i = 1 . . . n, of the remainders we get when we divide the (n + 1 -i) × (n + 1 -i)-minors of y -tI n by Q z i (t). We denote by I σ the ideal generated by these remainders. The underlying set of X σ consists of all the couples (z, y) such that y is in the closure of the orbit corresponding to z.

Proposition 3.3. The closed subscheme X σ is a family of SL(n)-stable closed subschemes of sl(n) with Hilbert function h σ .

Proof. The proof is similar to that of Proposition 2.1. The subscheme X σ is a family of SL(n)-stable closed subschemes of sl(n) over A b 1 -1 . Let us denote by π the morphism X σ -→ A b 1 -1 .

As previously, let us first remark that the morphism

π// SL(n) : X σ // SL(n) -→ A b 1 -1
induced by π is an isomorphism. To do this, let us verify that the comorphism

(π// SL(n)) * : C[A b 1 -1 ] -→ C[A b 1 -1 ] ⊗ C[sl(n)] SL(n) /I SL(n)
σ is an isomorphism. It is injective, as π is surjective. Its surjectivity comes from the relations that define X σ : they give, for i = 1, that Q z 1 (t) divides the determinant of tI n -y, that is the characteristic polynomial of y. As their degrees are equal, Q z 1 (t) and the characteristic polynomial of y are equal. This gives the surjectivity.

We go on as previously: let λ be a dominant weight. The R SL

(n) -module R U (λ) is of finite type ([AB, Lemma 1.2]). Thus (π * O Xσ ) U (λ) is a coherent O A b 1 -1 -module.
To see that it is locally free, we just have to check that its rank is constant. Let us assume that the origin 0 ∈ A b 1 -1 corresponds to the nilpotent orbit in S σ . The fiber of π over 0 is the closure of this orbit, fitted with its structure of reduced scheme. Thus, the rank of (π * O Xσ ) U (λ) at 0 is h σ (λ). If z is any point of A b 1 -1 , the fiber of π over z is as a set the closure in sl(n) of the corresponding orbit. So, by Proposition 1.3 the rank of (π * O Xσ ) U (λ) at z is at least h σ (λ). To conclude, we use the action of the multiplicative group on sl(n) (by homotheties) and the induced action on A b 1 -1 , that makes π equivariant. The orbit of z goes arbitrary close to 0, and the rank of a coherent sheaf is upper semicontinuous, so the rank of (π * O Xσ ) U (λ) is h σ (λ) at z.

Tangent space

In this section, we compute the dimension of the tangent space to H σ at the point Z σ :

Proposition 3.4. The dimension of T Zσ H σ is b 1 -1.
Proof. Let x be an element in the open orbit in Z σ . It is known that Z σ is normal ( [KP]). So by Proposition 1.2, we just have to prove that the dimension of (sl(n) * x ) SL(n)x is b 1 -1. Let us consider SL(n) as a closed subgroup of the general linear group GL(n), and sl(n) as a subalgebra of gl(n). The stabilizer GL(n) x of x in GL(n) is generated by SL(n) x and the center of GL(n). It is clearly equivalent to prove that the dimension of (gl(n) *

x ) GL(n)x is b 1 . The group GL(n) x is connected, so the last space is isomorphic to

(gl(n) * x ) gl(n) x .
A linear form on gl(n) x is gl(n) x -invariant iff it vanishes on the derived algebra [gl(n) x , gl(n) x ], so we have to prove that

(gl(n) x /[gl(n) x , gl(n) x ]) * is b 1 -dimensional.
This fact is the following elementary lemma.

Lemma 3.5. Let E = c 1 i=1 E i be a graded vector space over C, where each E i is b i -dimensional. We denote by h := gl(E) the Lie algebra of endomorphisms of E. Let x be a nilpotent element of h such that each subspace E i is stabilized by x, and the restriction of x to each E i is cyclic.

Let us denote by h x the stabilizer of x in h. Then the codimension of the derived algebra

[h x , h x ] in h x is b 1 .
Proof. The graduation of E induces a graduation on the vector space h:

h = i,j
Hom(E i , E j ).

Let us denote by p i : E -→ E i the natural projections. As they commute with x, the subspace h x of h is homogeneous:

h x = i,j Hom x (E i , E j ),
where Hom x (E i , E j ) denotes the space of homomorphisms that commute with x. Let us choose, for any i, an element e i of E i such that x b i -1 e i = 0. We put n ij := b j -b i if j < i and 0 otherwise. We denote by f ij : E i → E j the unique homomorphism that commutes with x and that sends e i to x n ij e j . Then any homomorphism from E i to E j that commutes with x is the composite of f ij with a polynomial in x:

Hom x (E i , E j ) = C[x] • f ij . We notice that if i = j, then Hom x (E i , E j ) is contained in [h x , h x ]. Indeed, for any u : E i → E j , we have [u, p i ] = u.
So we have to prove that the codimension in i Hom

x (E i , E i ) of [h x , h x ] ∩ i Hom(E i , E i )
is b 1 . The last vector space is generated by its elements of the form

P (x)[f ji , f ij ] = P (x)x |b i -b j | (id E i -id E j ),
where P (x) is a polynomial in x.

One checks easily that a basis of a supplementary in i Hom x (E i , E i ) of this space is given by the family of elements

x k id E i where 0 ≤ k < b i -b i+1
, and the lemma is proved.

Conclusion

In this section, we prove that the family X σ of Proposition 3.3 is the universal family:

Theorem 3.6. The morphism φ σ from S σ / SL(n) to H σ obtained in §3.2 is an isomorphism.

We denote by S σ the closure of S σ in sl(n), equipped with its reduced scheme structure. The invariant Hilbert scheme H ′ σ := Hilb SL(n) hσ (S σ ) which parametrizes the closed subschemes of S σ of Hilbert function h σ is canonically identified with a closed subscheme of Hilb SL(n) hσ (sl(n)). The morphism φ σ factorizes by a morphism ψ σ : S σ / SL(n) → H ′ σ . To prove the theorem, we will get that the morphism ψ σ is an isomorphism from S σ / SL(n) to H ′ σ and that H ′ σ is a connected component of H σ (Corollary 3.10).

Lemma 3.7. The morphism ψ σ induces a bijection from the set of closed points of S σ / SL(n) to the set of closed points of H ′ σ .

Proof. We know that ψ σ is injective. Let us check it is surjective: in other words, that any SL(n)-invariant closed subscheme of S σ with Hilbert function h σ is the closure of some orbit in S σ .

Let X be such a subscheme. As h σ (0) = 1, it has to be contained in some fiber F of the categorical quotient S σ → S σ // SL(n) over a reduced closed point. But F already corresponds to a closed point of H ′ σ in the image of ψ σ . Moreover, F admits no proper closed subscheme admitting the same Hilbert function, so F = X, and the lemma is proved.

Corollary 3.8. The dimension of H ′ σ is b 1 -1.

The action of the multiplicative group G m on sl(n) by homotheties induces canonically an action of G m on H σ , and on H ′ σ (because it stabilizes S σ ). The cone Z σ is a G m -fixed point of H ′ σ . In fact, it is in the closure of the G m -orbit of any point of H ′ σ :

Proposition 3.9. Let F be a closed point of H ′ σ . The morphism η : G m -→ H ′ σ , t -→ t.X extends to a morphism A 1 -→ H ′ σ , 0 -→ Z σ .

Proof. The point F corresponds to a SL(n)-invariant closed subscheme of S σ admitting Hilbert function h σ . We still denote it by F . As h σ (0) = 1, it is contained in the fiber of the categorical quotient sl(n) → sl(n)//SL(n) over some closed point. Thus we can apply to it the method of asymptotic cones: we obtain a flat family over A 1 whose fiber over 0 must be Z σ (as in the proof of Proposition 1.3). It gives a morphism from A 1 to H ′ σ whose restriction outside 0 is η.

From the proposition, we deduce that the dimension of the tangent space to H σ at any point of H ′ σ is lower or equal to that at Z σ , that is b 1 -1. As the dimension of H ′ σ is b 1 -1, we get:

Corollary 3.10.

• The scheme H ′ σ is reduced and smooth.

• It is a connected component of H σ .

The morphism ψ σ is bijective (Lemma 3.7) and H ′ σ is normal. According to Zariski's main theorem, ψ σ is an isomorphism. So Theorem 3.6 is proved, thanks to the second point of Corollary 3.10.

  Proposition 1.1. Let h : Λ + -→ N be a function. Let Y and Z be two affine schemes of Hilbert function h. Then dim Y = dim Z. Proof. Let us denote by A the affine ring of Y .


Armel Fotsoh

Christian Sallaberry

Annig Le Parc-Lacayrelle

Tanguy Moal

A process for business entities extraction on the web

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

Introduction

Building local-based services appears to be a trend these days as it attracts an increasing interest. In fact, local-based services help users to nd local services oers in their neighbourhood or around a specic spatial localization. In that sense, some services are dedicated to businesses and services geolocated search, such as Google My Business 1and "Pages Jaunes" 2 . These services are however mostly supplied with manually recorded data, meaning there is no real time update and some data can be missed. For instance, a search for zinc-work companies in the French council of "Pujols Sur Ciron" on Google Maps does not lead to any result in the targeted council; nor does it have any results in "Pages Jaunes". As a matter of fact, "Ets JEROME BELLIN" is a zinc-work company indeed located in the targeted council of "Pujols Sur Ciron" and has its website 3 up-to-date with the current business information and location. This highlights the limitation of existing services dedicated to local businesses. Some companies' information, such as their registration number, is freely provided by local or national institutions. In addition, an increasing number of companies are referenced on the web. According to "La Tribune" blog 4 , in 2013, about 64% of French companies had an ocial website with the company information. In Europe, the presence rate is actually higher. Based on these observations, we propose an approach to address extraction of companies data on the web such as activity elds, practised jobs, commercialized or manufactured products, postal addresses, emails, phone or fax numbers.

The proposal relies on a model of business entity with two main parts; the rst part is made of company registration data (ocial name, business category, identier, managers) contained in dedicated open data websites. The second part is constituted of extended data extracted from companies' websites. Address extraction is one of the most dicult task in the process, due to the fact that micro data or specic tags are used just by few websites for publishing addresses. Besides, people use many dierent ways to write addresses.

The paper is organised as follow. Section II presents some related work; Section III describes our proposal; Section IV presents the implementation of our approach; Section V is about evaluation of the website ltering module and the information extraction one and Section V is the paper conclusion as well as some prospects.

II. Related Work

Few researchs focus on spatial named entities recognition in text documents. Vaid et al. [START_REF] Vaid | Spatio-textual indexing for geographical search on the web[END_REF] presents, an approach for the extraction and disambiguation of spatial named entities on the web. Their approach also allows the extraction of relative spatial entities introduced by topological expressions like "near of", "in the south of", etc. More specic works focus on the automatic extraction of addresses in textual documents. There are three mains techniques: (i) the rst one is ontology-based. It is used by Borges et al. [START_REF] Karla | Discovering geographic locations in web pages using urban addresses[END_REF] for the recognition, extraction and geocoding of Brazilian addresses in web pages; (ii) the second one relies on machine learning techniques for the extraction of urban addresses. A learning algorithm (CRF: Conditional Random Field) is used in [START_REF] Loos | supporting web-based address extraction with unsupervised tagging[END_REF] for example to extract addresses in web pages; (iii) the last one is a pattern-based technique, it is used by Ahlers and Boll [START_REF] Ahlers | Retrieving address-based locations from the web[END_REF] for the extraction and the validation of German addresses from web pages and it relies on the use of many Gazetteers, one of which contains all German street names. The use of knowledge resources in thematic text annotation is explored by several researchs. In fact, recent development in semantic web allows the structuring of the knowledge of a specic eld in specialized resources like ontologies, thesauri, etc. The contribution described in [START_REF] Soner | An ontology-based retrieval system using semantic indexing[END_REF], presents an approach for textual documents annotation using a Football domain ontology. This formalization of a eld knowledge in a structured organisation like ontologies allows the annotation of concepts [START_REF] Ne²i¢ | Concept-based semantic annotation, indexing and retrieval of oce-like document units[END_REF] and/or relations between them [START_REF] Royer | Extraction automatique de relations sémantiques dénies dans une ontologie[END_REF] in text. Sometimes, knowledge resources do no always contain enough vocabulary for text annotation. Therefore, several techniques have been designed to enrich these resources. Parekh et al. [START_REF] Parekh | Mining domain specic texts and glossaries to evaluate and enrich domain ontologies[END_REF] proposes an approach based on text mining to enrich, in a semi-automatic way, an ontology describing the medical eld. They use medical textual documents and glossaries. The approach presented in [START_REF] Parekh | Mining domain specic texts and glossaries to evaluate and enrich domain ontologies[END_REF] uses matrix decomposition in singular values to build clusters of terms from a selected input corpus. An expert of the domain validates selected terms for each cluster.

Discovering of web pages that describe specic entities on the web, is a eld of research in full development. Rae and Murdock [START_REF] Rae | Mining the web for points of interest[END_REF] propose a technique for bootstrapping points of interest (POIs) data from the web. In fact, their approach uses Wikipedia data, to collect a POI information and use it to nd the most relevant corresponding website. Complementary information about the POI is then extracted from the selected website.

Many services dedicated to business information retrieval are available on the web. Data providers like Factual5 , collect and commercialize business information. Directories like "Pages Jaunes" or Google My Business are used to query business databases while social networks like Yelp6 or Foursquare7 are used in information sharing and reviews about businesses. All these services are supplied mostly by manually recorded data (end-users and employees), partner companies data or open data. Thus, data is not always up to date and some can be missed. Therefore, some works focus on business information extraction on the web. For instance, Alhers [START_REF] Ahlers | Business entity retrieval and data provision for yellow pages by local search[END_REF] proposed a system which analyses web pages content in order to to consolidate and enrich those contained in the Yellow Pages database. The analysed corpus is constituted of websites of companies referenced within Mozilla Directory (DMOZ8 ). Extracted data here are addresses, using the approach details in [START_REF] Ahlers | Retrieving address-based locations from the web[END_REF], phone numbers, emails, commercial and tax information of businesses. Note that, the proportion of existing companies registered in DMOZ is very low, therefore the extracted data remains poor and the wealth of companies information available on the web is only partially exploited.

III. Proposition

The process ow of our service is composed of several main steps: Our approach is dierent from the one used by Ahlers [START_REF] Ahlers | Business entity retrieval and data provision for yellow pages by local search[END_REF] in the way that, websites constituting extraction corpus are ltered directly from the web, using an heuristic similar to the one used in [START_REF] Rae | Mining the web for points of interest[END_REF]. Hence, the number of websites used for the information extraction process is more signicant. Besides contact information and addresses, we also extract companies activities elds, products and practised jobs from the websites using knowledge resources.

• An other step (Figure 1.3) based on the approach detailed in [START_REF] Parekh | Mining domain specic texts and glossaries to evaluate and enrich domain ontologies[END_REF], is used for knowledge resources enrichment.

• Target information is automatically extracted from those websites' contents using patternbased and ontology-based approaches(Figure 1.2).

• Business entities are constructed from registration and extracted data. These constructed entities are then stored in the knowledge graph (Figure 1.6). Our approach is designed for French companies, but it can also be adapted for others countries.

Next sub-sections detail data and resources preprocessing, website ltering, information extraction and business knowledge graph storage.

I. Open data Leverage

Open data seems to be a trend for data publishing. Access to data is more and more generalized with the real revolution brought by the semantic web. Even public administration are not left out. They publish a huge volume of information in open access on the web. "Trade and Companies Register" for example collect, publish and maintain French' companies registration information on an open data platform 9 . That information is structured according to the standard model of the SIRENE repository dened by the French National Statistics Institute INSEE 10 . This registration data is the entry point of our website ltering process. The SIRENE model is also use to represent registration data in a business entity.

INSEE has also dened two hierarchies for organizing companies' activity elds and manufactured or commercialized products. This is respectively the "French Activities Nomenclature" (NAF) and the "French Classication of Products" (CPF). The Open data is used in the process ow stage for ltering companies' websites, building knowledge resources for information extraction task and dening the structure of data. Table 1 presents a simplied model of entities in the business knowledge graph. For each property, we also provide which data source has been used.

II. Website ltering

Registration data coming from datainfogree.fr is used to query the web in order to identify companies' websites. In fact, datainfogree.fr is a platform supplied and maintained by the public administration, thereby, companies name and main activity data we need are reliable. An heuristic based on this registration data is dened to lter companies' websites. Figure 2 details the heuristic. Indeed, several combinations of registration data are tested in order to identify websites from a sample of 300 French ), but it is not mandatory. The algorithm 1 presents our website ltering heuristic. A blacklisted websites list, containing business directories, council websites, people directories, social networks and administration websites is constituted and used in the heuristic to reduce errors.

III. Resources enrichment

For the automatic extraction of activities, jobs and products, we use three knowledge resources. These resources are built by transforming the NAF, ROME, CPF hierarchies as OWL ontologies. The three core hierarchies choice is motivated by their organizational level which is fairly atomic. Each ontology used in our proposal, is a graph of concepts (activity, jobs or products) with hierarchical relations. A set of vocabulary labels is used to describe each concept. The activity ontology built from the NAF hierarchy is poor in vocabulary labels. Therefore, we decided to use the website corpus to enrich it. We propose a semi-automatic text-mining technique similar to the one describes in [START_REF] Parekh | Mining domain specic texts and glossaries to evaluate and enrich domain ontologies[END_REF]. Indeed, registration data of companies contains information about its main activity eld. The idea is to use a learning algorithm to gather phrases in companies' websites of a same activity eld. An expert will validate the selected phrases and they will be added to the core resource. Given the volume of companies' websites available for each activity eld which is quite low, the Latent semantic Allocation (LSA) algorithm does not give good results for such a vocabulary gathering task. However, Latent Dirichlet Allocation (LDA) [START_REF] David M Blei | Latent dirichlet allocation[END_REF], allows us to obtain more acceptable results. Therefore, this last algorithm is used for our clustering purpose. It is also important to mention that phrases can be uni-gram, 2-gram, 3-gram and 4-grams.

For a given activity eld, a corpus of all associated web pages is constituted. In this corpus, there are phrases related to the activity eld vocabulary as well as others latent vocabularies. The goal is to gather web pages phrases into vocabulary clusters. The clustering function takes several parameters :

• n: which is the size of phrases in each vocabulary cluster (1 to 4).

• V: which is the vocabulary of the corpus, it is constituted of all the distinct n-grams.

• M: which is the matrix representing relations between each phrase of the vocabulary and corpus pages. Columns of M are constituted of V elements and lines of web pages. M ij is the weight of the j phrase in the i web page. In our proposal, the weighting is based on an adaptation of the TF-IDF [START_REF] Rousseau | Graph-of-word and tw-idf: New approach to ad hoc ir[END_REF].

• nb_topics: which is the number of phrases' clusters we want to extract from the websites corpus.

• nb_top_words: which is the number of top phrases in each cluster.

As output, we have clusters of phrases corresponding to topics identied in corpus. An expert selected relevant phrases from the cluster corresponding to the activity eld description. These phrases are then added to the associated class in ontology.

IV. Information extraction

Each web page is analysed to annotate targeted information (Figure 1.2). The annotations are extracted from web pages to ll in extended data properties [START_REF] Ahlers | Business entity retrieval and data provision for yellow pages by local search[END_REF] .

Thematic information extraction Extraction of activities, jobs and products relies on an ontologybased approach. We use the three knowledge resources built and enriched in III.III to automatically annotate web pages. These ontologies are processed as follow: vocabulary labels are lemmatized and case normalized for the semantic annotation task. Besides, each web page content is also tokenized, lemmatized and case normalized. Thereby, web page phrases matching an ontology class label are tagged with the corresponding class identier. Regular expressions are used to annotate emails, phone and fax numbers in web pages. Observation of this information in a sample of French companies websites allowed us to write the extraction patterns.

V. Indexation

Annotations are extracted from web pages to construct corresponding extended data. Geocoding of extracted addresses is performed before merging extended data with registration one to construct business entities according to the model dened in III.I. All the business entities so obtained are added to an index representing the business knowledge graph while textual content of webpages is stored in another full text index for the search module.

IV. Process flow implementation

Our prototype deals with the South West region of France (Aquitaine) where about 254,000 companies are registered. We chose 212 INSEE activity elds corresponding to about 115,000 companies: 22,000 of them have a website according to the website ltering heuristic. We use Google Search API14 for executing search queries. Corpus is constituted by crawling all these websites with Apache Nutch Framework15 (we crawl only the home page and the rst level pages for each website). This produces a corpus of about 550,000 web pages. We use the Python library lda16 , which implements the clustering function described in III.III. This process allows the enrichment of the activity ontology with new class phrases. Corpus annotation is performed using GATE17 Platform. In order to deal with French language, we integrate TreeTagger in GATE. We also connect GATE to Apache HADOOP18 framework in order to deal with the large volume of web pages. Thus, the annotation process is scalable and its implementation does not depend on data size. The knowledge graph of business entity is indexed using Elasticsearch 19 .

For the corpus of 550,000 web pages, our annotation process identied about 30,000 addresses, 44,000 activity phrases, 12,500 product phrases and 28,000 job phrases. The business and the full text indexes have a total size of 3 GB.

V. Evaluation

This section details the evaluation of some process ow steps such as website ltering and information extraction.

I. Website Filtering Evaluation

A set of 500 entities are randomly selected from the business knowledge graph for website ltering evaluation. A manual verication is then carried out to analyse each company website in a browser to validate if it is relevant or not. About 30% of the retrieved websites were not relevant. These results can be explained by the fact that some not relevant domain names are not registered in our blacklisted websites list. Moreover, many companies, especially artisans, have a commercial or ocial name which coincide with the founder one. Therefore, the website ltering process brings back no relevant websites, such as magazines, newspapers, universities, institutions etc. as long as the founders rst name or last name appears in these websites.

II. Information Extraction Evaluation

We evaluate both the address and the activity elds extraction processes. There is no evaluation campaign available dedicated for this type of entities (address, activity), therefore, we have dened one.

Our campaign follows the classic TREC process like the one described in [START_REF] Voorhees | TREC: Experiment and Evaluation in Information Retrieval[END_REF]. It contains:

• Categories: each one corresponds to the entity type we want to tag in the corpus (Address or Activity).

• Pages: it is constituted of the information needs in the TREC approach. In our case, each page contains one or more addresses (activities respectively).

• Query relevance judgements (qrels): this is the mapping between each page and the relevant extracted entities. In fact, an expert has annotated in each page all the relevant addresses (and activities respectively).

The evaluation corpus is submitted to the annotator system. Extracted entities and qrels are used to calculate each page precision and recall. Means of these metrics, on all the evaluation corpus, give respectively the global precision and the global recall. The harmonic mean of these global metrics corresponds to the F-measure.

II.1 Address Extraction Evaluation

The evaluation corpus is constituted of 240 web pages containing at least one address. 309 addresses are annotated by the expert, while 286 are selected by our annotator. Among those selected by the annotator, 251 are judged relevant and 13 have been partially selected (some elements are missed). Table 3 presents summary results of address evaluation process. Several selected addresses are not relevant. Many reasons explain this observation: council name is not in the council Gazetteer or it is misspelled, this raises mostly with composed council name ("Bon-Encontre"); the street name contains a council name and the correct council name is not in the council Gazetteer ("Rte de Martillac 40200 Bon-Encontre").

However, some relevant addresses are not selected, due to the fact that they are not covered by our extraction patterns. It is the case when the Zip Code is omitted ("10 Place de la Bourse Bordeaux") and sometimes the council name too ("10 Place de la Bourse").

II.2 Activity Extraction Evaluation

We have constituted a corpus of 100 company websites' home pages. We deal only with activities related to roof (carpentry, covering, etc.). The system annotates 1119 activity phrases while the expert annotates 1131. Only 631 among the 1119 activity phrases selected by our annotator are correct. Table 4 summaries results of the activity evaluation process. About half of the pertinent activities are not annotated. This is mostly due to the poorness of the activity ontology is spite of its enrichment. Moreover, many of the activity labels do not represent all the possible variations of a phrase. Indeed, the expert can annotate a label which is only partially recorded in the ontology. He can identify for example the expression "traditional wood frame", while only "wood traditional frame" is recorded as a label in the ontology. In addition, some errors may be due to misspellings in web pages or even phrases lemmatization problems during the annotation process.

VI. Conclusion

We propose a modular process dedicated to the extraction of business thematic and location information on the web. This process relies on several research areas which are combined in a complementary way to construct business entities. These entities are stored in a business knowledge graph. The proposed approach aims the extraction of addresses in websites in spite of the dierent expression formats, with quite good eectiveness results. Despite the poor results obtained, the enrichment of knowledge resources with learning techniques, contributes to improve thematic information extraction in websites. Our model of business entities is based on the one used by the administration to publish open data combined with those dened by specialized organisations.

Filtering websites, which is a key stage in the process, has to be improved. Therefore, future work will explore how to add a classier in the ltering step in order to automatically detect if a website is a directory or a company one. Other future work will also focus on the semantic disambiguation of activities, products and jobs detected in a company' website. This will help to keep only in the knowledge graph relevant information for each entity. Finally, we will focus on the denition of information retrieval models combining spatial, thematic and full text criteria for business local-based search.

2 Figure 1 :

 21 Figure 1: Processing chain

  French organisation for work Pole Emploi 11 has dened an hierarchy, "Trade and Jobs Operational Register" (ROME) for organizing the dierent socioprofessional categories. These hierarchies are published on their related institution websites in open access. They are used in our proposal for information extraction purpose. Besides, the French governmental laboratory of open data Etalab 12 , denes a consensus model of postal addresses representation. Addresses, according to the dened model, are geocoded and published in open access on a dedicated platform 13 . Our proposal uses this open data platform to geocode detected addresses in websites.

Figure 2 :

 2 Figure 2: Website Filtering

  Address → AS? ((P B SC) | (SC P B) | P B| SC)? SN u? SN a AS? ((P B SC)| (SC P B) | P B| SC)? ((ZC C)| (C ZC)) LN ? D? Co? Legend A? : A can be omitted A | B : A or B A B : A and B

Table 1 :

 1 SIMPLIFIED BUSINESS ENTITY MODEL

	Business Entity Properties	Representation Models	Data Sources
	Registration data	SIRENE (INSEE)	datainfogree.com
	Coordinates
	website	-	web
	Address	Address (Etalab)	company website
	Phone Numbers, emails, fax	-	company website
	extended data
	Jobs	ROME (Pole Emploi)	company website
	Activities	NAF (INSEE)	company website
	Products	CPF (INSEE)	company website

  http://www.insee.fr/fr 11 http://www.pole-emploi.fr 12 http://www.etalab.gouv.fr13 http://adresse.data.gouv.fr/

9

http://datainfogree.fr

10

Table 2 :

 2 ADDRESS COMPONENTS

	Field names	Symbols	Examples
	Address Supplement	AS	Résidence Rigaud
	Postal Box	PB	BP 1167
	Special Course Number SC	CS 2587
	Street Number	SNu	10 ter
	Street Name	SNa	Avenue de l'université
	ZIP Code	ZC	64000
	City Name	C	Pau
	Letter Number	LN	CEDEX 01
	Department	D	Pyrénées-Atlantiques
	Country	Co	France
	Street Introduce	SI	Avenue
	Address information extraction The System
	described in [2], uses a Gazetteer of all German
	streets to extract addresses in web pages. Thus, the
	precision of the system is pretty good. In the French
	context, a Gazetteer with an exhaustive list of street
	names is not available. Therefore, we propose a new
	pattern-based approach for address extraction from
	web pages. Observation of a sample of 160 French
	companies websites allowed us to dene a set of ad-
	dress patterns. The Zip Code is almost always pre-
	sented, thereby, it is the entrance point of the ad-
	dress extraction process. Table 2 details the dier-
	ent components of a French address in its full form.

Each component is identied by dedicated patterns. When an address contains at least ZIP code, council name and street information, the extraction pattern is the one bellow. Other information such as Address Supplement, Postal Box or Special Course Number might be present before or after the street name.

Table 3 :

 3 ADDRESS EVALUATION SUMMARY

	Relevant	Selected	Precision	Recall	F-Measure
	309	286	0.80	0.81	0.80

Table 4 :

 4 ACTIVITY EVALUATION SUMMARY

	Relevant	Selected	Precision	Recall	F-Measure
	1131	1119	0.45	0.52	0.49

http://www.google.com/business/

http://www.pagesjaunes.fr

http://www.charpente-bellin.fr/

http://www.latribune.fr/blogs/strategie-marketingen-1min30/20130515trib000764662/64-des-entreprisesfrancaises-disposent-d-un-site-internet.html

http://www.factual.com,

http://www.yelp.fr/

http://fr.foursquare.com

http://www.dmoz.org

http://developers.google.com/custom-search/jsonapi/v1/overview

15 http://nutch.apache.

org 16 http://pypi.python.org/

pypi/lda 17 http:/

/gate.ac.uk 18 http://

hadoop.apache.org 19 http://www.elastic.co