Alexandre Cohen

Nathalie Fraysse

Jean Rajchenbach

Médéric Argentina

Yann Bouret

Christophe Raufaste

Inertial mass transport and capillary hydraulic jump in a liquid foam microchannel

teaching and research institutions in France or abroad, or from public or private research centers.

The rheological behavior of liquids in unbounded geometries (i.e. without rigid boundary conditions) is not well understood. Examples are jets, films, and liquid foams, the dynamics of which is driven either by gravity or geometrical inhomogeneities (capillary suction). The drainage of soap foams under gravity has in particular been investigated [1][2][3][4][5]. In such media, the liquid is assumed to flow through the network of channels called "Plateau borders" (PBs). The most controlled experiment, called forced drainage, consists in pouring liquid at constant flow rate on top of a foam column: a swollen region of constant liquid fraction is observed to develop from the top and travel downward at constant velocity [3]. Macroscopic measurements at the scale of the foam sample have been satisfactorily accounted for by effective-medium models of flow through porous media, assuming a low Reynolds number. The so-called drainage equation is used [1,2,5]. Capillary suction can be neglected within the swollen region, which displays a homogeneous liquid fraction [1,2,5], however it can no longer be disregarded for determining the exact profile of the front zone [3,6,7] where capillary effects become important, as evidenced by the few microgravity experiments [8]. Generally speaking, few experiments have been devoted to the study of the local flow at the scale of one elementary cell (i.e. one bubble), and all of them dealt with steady regimes [1,9].

The present study investigates transient flows through a Plateau border with capillarity as the only driving force. This is achieved experimentally by injecting a droplet into a single Plateau border which is maintained horizontally to eliminate gravity effects.

We use a straight, 15 mm-long Plateau border created by dipping a triangular-prism frame into a soapy solution. The frame is positioned so that the cross-section of the three films that hold the PB adopts the Y-shape shown in Fig. 1a. The setup geometry is analogous to the one used by Piroird and Lorenceau to study oil imbibition inside an aqueous foam [10]. The cross-section in Fig. 1b is typical of Plateau borders in foams. The radius of curvature of the PB is controlled by continuously injecting liquid at one upper-corner of the frame. Two kinds of surfactant solutions are probed in the experiments: Solution A was obtained from a commercial dishwashing liquid, Solutions B were obtained by dissolving TTAB (Tetradecyl trimethyl ammonium bromide) into de-ionized water and adding various amounts of glycerol in order to vary the viscosity. Solutions A and B are characterized by tangential stress-free interfaces (high surface mobility limit) [9,11]. We inject extra liquid into the PB by releasing from above a small spherical droplet of the same surfactant solution. After release, the droplet rebounds on the PB, stabilizes and finally coalesces with the PB. In these experiments, the droplet radius ranges from r = 0.2 mm to 1.8 mm, while the initial radius of curvature of the PB ranges from R i = 0.1 to 1.3 mm. The relaxation of the PB-with-drop is visualized by means of a fast camera.

There are two different dynamical regimes. A viscous regime is observed for large bulk viscosities or small radii of curvature of the Plateau border: the bulge corresponding to the fluid in excess spreads with time and the liquid is slowly evacuated into the PB (Fig. 1c). The PB thickness profile is smooth (Fig. 1f) and presents a diffusivelike spreading dynamics (data not shown). In contrast, an inertial regime is observed for small solution viscosities and regular or large radii of curvature of the Plateau border. The liquid in excess does not spread smoothly, but is evacuated by dilating the initial PB in a front-like manner (Fig. 1d,e). A sharp traveling jump (Fig. 1g,h) separates the dilated part of the PB, which has a uniform and constant radius of curvature R j , from the notyet-perturbed part characterized by the initial radius of curvature R i . This jump travels with a constant and substantial velocity (∼ 0.1 -1 m/s).

We now turn to the transition between the two dynamical regimes described above, as well as the reason for referring to them as "viscous" versus "capillary-inertial". Five parameters, namely ρ, η, γ, r and R i , are relevant in the system, which yields only two independent dimensionless numbers. The first one is the ratio of the droplet At rest, the cross-section is well approximated by the tangential contact of three arcs of circles of same radius equal to Ri. ei is the apparent thickness of the PB and is proportional to its radius of curvature Ri. c-e) Three sets of snapshots of the longitudinal view of the PB that illustrate the different behaviors observed. ∆t = 2.5 ms between consecutive images (5 ms between the last two images of each series). c) Viscous regime for a high viscosity TTAB solution. d) Inertial regime for the less viscous TTAB solution. c l (cr) holds for the velocity of the front that travels toward the left (right). Red dashed lines are guides to the eyes to follow the front position. e) Same as d) but for a thicker initial PB. f-h) Enlargement of the edge of the perturbed part of the PB. The enlarged zones are pinpointed by the blue boxes drawn on the penultimate images of the snapshot series in c-e).

size to the PB size, r/R i . The second one is the socalled Ohnesorge number -often used to deal with freeinterface problems in fluid mechanics [12]. This number can be defined as the ratio of a capillary-inertial velocity c 0 = γ/ρR i to a capillary-viscous velocity γ/η:

Oh = η √ ργR i . (1)
The Ohnesorge number is actually the inverse of the Reynolds number Re based on c 0 . The experiments re- ported in Fig. 2 show a well-defined transition between the two regimes, for a critical value Oh = 0.05, or equivalently Re = 20, independently of r/R i . For Oh larger than 0.05 (Re < 20), viscosity is observed to dominate, whereas for Oh smaller than 0.05 (Re > 20), a capillaryinertial regime is observed. We emphasize that this transition is droplet-size-independent. This new capillary-inertial dynamics needs to be investigated because all current foam drainage models consider viscous flows only. In the rest of this paper, we concentrate on this regime and its relevance for foam drainage dynamics.

Experimental results obtained in the inertial regime are reported in Fig. 3 for Solution A and for the less viscous Solution B. The front velocity (computed as the average over the right and left swelling fronts velocities, see Fig. 1d) strongly decreases when the initial radius of curvature of the PB increases (Fig. 3a); a power law interpolation gives exponents of -0.51±0.05 and -0.50±0.02 for the two solutions, respectively. The radius of curvature R j upstream of the jump increases linearly with the initial radius of curvature R i ; the best linear fits are R j = (1.9 ± 0.1)R i and R j = (1.5 ± 0.1)R i for the two solutions, respectively (Fig. 3b). All the experiments in the inertial regime show similar behavior: the properties of the traveling jump are determined by the properties of the initial PB and do not depend on the amplitude of the perturbation. Within our experimental range, the initial radius of the droplet does not appear to play a significant role neither on the front velocity nor on the radius of curvature of the perturbed region of the PB. This is true as long as the droplet acts as a liquid reservoir that can sustain the jump geometry.

We propose a model based on two assumptions. First, the Reynolds number based on the front velocity (∼ 0.2 m/s) and on the PB size (∼ 0.5 mm) is of order 100. Therefore we will consider the flow as inertia-dominated. Secondly, we assume a plug-flow inside the PB, at least far from the front zone, because of the high mobility of the surfactants at the interfaces [11]. The geometry of the jump zone is analogous to the one of a hydraulic jump triggered by gravity [START_REF] Rayleigh | Proc. R. Soc. Lond. A[END_REF] if considered in the reference frame of the moving front R f .

A sketch of this geometry is displayed in Fig. 4, together with the notations used. Balance equations relate to R f . We assume that the liquid is initially at rest in the reference frame of the lab, R, thus V i = c, where c is the velocity of the traveling front in R. The mass balance equation applied on both sides of the jump gives:

R 2 i c = R 2 j V j (2)
The momentum difference rate accross the jump thus is:

∆p/∆t = ρS i c 2 -ρS j V 2 j = ρS i c 2 (R i /R j ) 2 -1 , (3)
where

S k = ( √ 3 -π/2)R 2
k is the BP cross-section area (Fig. 4). This negative rate must be balanced by the net capillary force F j -F i that applies on the capillary jump. Three contributions to the capillary force have to be taken into account (ordered as such in the following formula): (1) capillary pressure force on the PB crosssection, (2) line tension on the PB contour and (3) line tension on the three holding films (note that each film has two liquid-gas interfaces):

F j -F i γ = S j R j - S i R i + π(R j -R i ) -6(h j -h i ) (4)
which reduces to

F j -F i γ = -( √ 3 -π/2)(R j -R i ) (5)
It is noteworthy that the film contribution is always negative and is dominant in the capillary net force. It is also remarkable that the expression of the driving force (Eq. 5) is equivalent to the one of a capillary pressure with a negative surface tension -γ [START_REF] Géminard | [END_REF]: this reflects the fact that an increase in the PB radius is energetically favorable as it results in a decrease of the interfacial area of the holding films that prevails over the concomitant increase of the interfacial area of the PB. For that reason, the capillary pressure only (the same holds for the tension force) would never support a capillary hydraulic jump in classical 1D geometries, like jets. Combining Eqs. ( 3) and ( 5) leads to the following intrinsic relation linking geometry and dynamics:

c(R i /R j ) = c 0 1 R i /R j (1 + R i /R j ) , (6)
where c 0 = γ/ρR i is the capillary-inertial velocity previously introduced. We use the value given by the experimental data (Fig. 3b) for the ratio R i /R j in order to compute the velocity predicted by the model (Eq. 6).

The comparison with the front velocity that was measured is shown in Fig. 3c. Despite some dispersion, the agreement is satisfactory since the model comprises no free parameter. Consider now liquid foams. In the dry foam limit, the radius of curvature of the Plateau borders is related to an effective bubble diameter. For instance, the Kelvin structure leads to the approximate relation: Φ ≃ 1.32(R i /D) 2 [START_REF] Weaire | The Physics of Foams[END_REF], where D is the bubble diameter and Φ is the liquid fraction of the foam. The Ohnesorge number thus is:

Oh = 1.07 η ργDΦ 1/2 (7)
This expression yields an estimate of the critical bubble radius D c above which the inertial regime may be observed. Common values for liquid foams (ρ = 1000 kg.m -3 , γ = 30 mN.m -1 , η = 1 mPa.s and Φ = 0.01) lead to D c = 0.15 mm. One has to be cautious when extrapolating data from experiments performed on model foams that have characteristic sizes significantly larger than the ones of usual foams. More importantly, a large set of experiments reported in the literature should exhibit a fast liquid flow along the Plateau borders. This is true for drainage studies [1,8,[START_REF] Saint-Jalmes | [END_REF]17], but also for other liquid redistribution cases such as bubble rearrangements [18]. However, since this process is fast compared to other processes involved (dissipation in vertices for drainage studies, dissipation inside the opening film during bubbles rearrangements), the dynamics of the system is ruled by the latter and capillary suction is not the origin of the limiting time scale. Nevertheless, it should be taken into account in gravity-free environment or to describe the shape of the transition zone in drainage studies. Note that the analysis performed in this study is valid only for tangential stress-free interfaces. Experiments performed with surfactants of low surface mobility reveal other behaviors (data not shown). We have never observed the hydraulic jump geometry in this case.

In summary, we have designed a local scale experiment and shown the occurrence of a fast mass transport regime along Plateau borders in liquid foams. This regime is triggered by capillary suction and is characterized by a capillary-inertial velocity which scales as γ/ρR i , where γ, ρ and R i are the surface tension of the liquid, its den-sity and the radius of curvature of Plateau border, respectively. We have given a phenomenological criterion for this regime to occur in foams, in terms of interfacial properties of the liquid, foam liquid fraction and bubble radius. It will be crucial to look closely at the exact profile of the front zone during forced drainage and to scrutinize the Plateau borders during bubble rearrangements like T1 processes to detect the capillary-inertial regime.

We gratefully acknowledge fruitful discussions with members of the GDR 2983 Mousses et Emulsions (CNRS). Franck Celestini is thanked for insightful comments. This work was supported by a research funding granted by the University of Nice Sophia Antipolis.

  FIG.1. a) Experimental setup: the Plateau border is held by three soap films. A drop is released from above and enters in contact with the Plateau border. b) Cross-section of the initial Plateau border observed through one of its extremity. At rest, the cross-section is well approximated by the tangential contact of three arcs of circles of same radius equal to Ri. ei is the apparent thickness of the PB and is proportional to its radius of curvature Ri. c-e) Three sets of snapshots of the longitudinal view of the PB that illustrate the different behaviors observed. ∆t = 2.5 ms between consecutive images (5 ms between the last two images of each series). c) Viscous regime for a high viscosity TTAB solution. d) Inertial regime for the less viscous TTAB solution. c l (cr) holds for the velocity of the front that travels toward the left (right). Red dashed lines are guides to the eyes to follow the front position. e) Same as d) but for a thicker initial PB. f-h) Enlargement of the edge of the perturbed part of the PB. The enlarged zones are pinpointed by the blue boxes drawn on the penultimate images of the snapshot series in c-e).

2 FIG. 2 .

 22 FIG. 2. Ohnesorge number as function of ratio of droplet size to PB size. Red squares ( ) and blue triangles ( ) stand for the inertial regime and for the viscous regime, respectively. The straight horizontal line (Oh = 0.05) highlights the transition between the two regimes.

FIG. 3 .

 3 fig1.d

FIG. 4 .

 4 FIG. 4. a) Sketch of the cross-section of the PB held by the three liquid films. Geometrical considerations lead to S = ( √ 3 -π/2)R 2 and h = R/ √ 3. b) Representation of the capillary hydraulic jump geometry (based on experimental observations, Fig. 1g,h) in the reference frame of the moving front.

* corresponding author: Alexandre.Cohen@unice.fr


Bako Rajaonah
email: bako.rajaonah@univ-valenciennes.fr

Juan Carlos Castelli

Jean-Bernard Ravenel

Antoine Osmont

Pierre Cabrol

Gwenn Le Fur

Acceptability of security scanners at airports: A French opinion survey

Keywords: Acceptability, Acceptance, Cognitive compromise, Opinion survey, Trust, Security scanner

This paper deals with the passenger screening procedure at airports. A survey on the acceptability of security scanners was conducted in France in July 2012 with a sample of 458 air travellers. Acceptability was operationalized in terms of behavioural intention to undergo scanning if such scanners were implemented at French airports. The great majority of the respondents would choose to pass through a security scanner whatever the representation used by the system to display potential hidden objects (a fuzzy image of the body of the passenger or a generic avatar). Despite their possible lack of knowledge on the efficiency of the technology, most of the respondents trusted security scanners to detect hidden explosives. Finally, the majority of the respondents did not perceive such scanning as a breach of fundamental rights. By way of discussion, a model is proposed which expresses that acceptance would emerge from a cognitive compromise between expected benefits, accepted risks, and tolerated constraints. The compromise would be shaped by trust and perceptions, which would themselves be shaped by knowledge and socially shared affect and values.

Introduction

France, as a Member State of the European Union (EU), the European Civil Aviation Conference (ECAC), and the International Civil Aviation Organization (ICAO), has become involved in strengthening aviation security measures. This paper focuses on a specific ground security measure at airports, namely the passenger body screening.

Indeed, international airports have progressively been equipped with walkthrough body screening scanners based on Xray or millimeter wave technologies. These systems are officially termed "security scanners" in the EU (see European Commission, 2010).

Security scanners are capable of detecting objects under clothes; not only metallic objects such as knives and arms but also non-metallic objects such as plastic and liquid explosives. These imaging technologies provide either images of the body of the person who is scanned or images of a generic avatar that resembles a human outline.

Advanced imaging technology being at the heart of security scanners, these systems are a source of controversy, notably in the form of privacy, health, and performance issues. Public concern about these issues raises the problem of the acceptance of security scanners.

The present paper aims to consider the psychological aspects of the acceptability and acceptance of security scanners at airports. Acceptability and acceptance can be operationalized in terms of intentional behaviour (e.g. [START_REF] Ausserer | Intelligent transport systems and serviceschances and risks[END_REF]. When air travellers" intentional behaviour is considered before the deployment of the technology, it is termed acceptability; after the deployment, it is termed acceptance (Schade and Schlag, 2010).

Section 2 deals with three issues that may influence air travellers" acceptability and acceptance of security scanners: the privacy and fundamental rights; the passenger"s health; the systems" performance. Section 3 presents two empirical studies of the literature on the acceptance of security body scanners. The first study was carried out with air travellers in New York City and Tel Aviv, the second one with air travellers in the UK. Section 4 presents and discusses the results of an opinion survey on the acceptability of security scanners carried out in France in July 2012. A model of acceptance that takes into account the results of the three studies is proposed at the end of the paper.

Issues that may influence the acceptance of security scanners

Privacy and fundamental rights issues

The protection of privacy and fundamental rights is recognized by governmental institutions as being a primary issue with the use of security scanners (e.g. [START_REF] Cavoukian | Whole body imaging in airport scanners: Privacy by design[END_REF]; UK Department for Transport, 2010; U.S. Department of Homeland Security, 2011).

About Europe, the following parts of the Charter of Fundamental Rights of the European Union are pertained to the use of security scanners: human dignity; respect for private and family life; freedom of thoughts, conscience, and religion; non-discrimination; the rights of child; ensuring a high level of human health protection; protection of personal data (European Commission, 2010, p. 4).

Whatever the representation displayed on the screen, personal data are processed. According to the European Union, "personal data" means any information relating to an identified or identifiable individual ("data subject"), and "automatic processing" includes the following operations if carried out in whole or in part by automated means: data storage, carrying out logical and/or arithmetical operations on those data, and their alteration, erasure, retrieval or dissemination (Council of Europe, 1981).

From the researchers" point of view, for example, Olga Mironenko from the University of Oslo (Norway), the use of body scanners seriously impacts the rights to privacy and data protection even if it may contribute to maintaining a high level of security, notably regarding terrorism [START_REF] Mironenko | Body scanners versus privacy and data protection[END_REF]. She noticed that the images created by body scanners could be considered personal data and that the use of these data, even not recorded, fell within the definition of processing (i.e. any operation performed upon personal data). Finally, she emphasizes that the storage and retrieval of images is the most controversial point for discussion.

According to Raphael Gellert and Serge Gutwirth from Vrije Universiteit Brussel (Belgium), even though the images produced by body scanners are anonymous, they "must not necessarily be considered as non-personal data" (Geller and Gutwirth, 2013, p. 527).

In view to these conclusions, it would be interesting to know the passengers" opinions on breaches of privacy and fundamental rights regarding the use of security scanners. It would also be interesting to know their trust in airport authorities to protect personal data. Indeed, the points of view of experts and the public may not coincide. It may be that the problem of the acceptability of security scanners in terms of privacy is not a real one for the majority of passengers. An argument for this view is the case of video surveillance. It is possible that the decisions made by institutions to increase aviation safety are seen by citizens as justified because the threats are objectivized [START_REF] Dumoulin | Une petite entreprise qui ne connaît pas la crise. Le succès de la vidéosurveillance au regard de la littérature internationale[END_REF]. Another argument comes from the domain of biometric technologies: people tend to consider being under surveillance as natural [START_REF] Crampton | The biopolitical justification for geosurveillance[END_REF] and adopt a level of social indifference (Van Den Hoogen, 2009).

Therefore, besides investigating the air travellers" views on potential breaches of fundamental rights, it would be interesting to know whether they consider passing through security scanner to be normal and unquestionable regarding the threat of terrorism.

Health issues

Security scanners also raise health concerns because they are based on technologies exposing the passenger to electromagnetic radiation. Two reports about health risks are presented, one based on X-ray backscatter technology and the other on millimeter wave technology.

The Scientific Committee on Emerging and Newly Identified Health Risks (SCENIHR), an advisory structure of scientific committees and experts in the field of consumer safety, public health and the environment, was requested by the European Commission to identify and quantify the health risks related to the use of security body scanners based on X-ray technology. According to the report of the SCENHIR published in 2012, cancer risks cannot be entirely excluded from body scanning technology, but if they exist, their magnitude would be below the baseline cancer risk due to other factors.

A second report issued by the French Agency for Environmental and Occupational Health (AFSSET) in 2010 at the request of the French government focused on acquiring a complete understanding of the use of security body scanners based on active millimeter-wave technology.

The Agency Concerning concluded that no thermal effect on exposed tissue was expected following a security body scan. The agency reported that the power radiated by such a body scanner was much weaker than the power radiated by other sources of radio frequencies used in everyday activities, such as microwave ovens or cell phones.

The conclusion emerging from the two reports is that both backscatter and active millimeter-wave security body scanners are nearly harmless to the health of passengers. However, another interesting conclusion comes from David J. Brenner in his paper of 2011 on X-ray backscatter scanners. According to him, the radiation doses associated with backscatter scanners that are probably safe for most of individuals may have long-term effects on the entire exposed population. Dr. Brenner added that what one could argue is that risk among population would be more than balanced by the benefits of reducing the risk of a terrorism event.

In the light of those conclusions contrasting with the alarmist titles in the mass media (e.g. "Radiation doctor says TSA naked body scanners can cause cancer"; NaturalNews, January 05, 2012), it would be interesting to investigate the passengers" views about the effect of passing through a scanner on their health.

Performance issues

With regard to the performance of security scanners, there are two major issues: the capability to detect metallic and non-metallic objects carried under clothing; the rapidity of the algorithms used to analyze data and provide the results displayed on the screen.

First, the capability to detect hidden objects is a matter of contrast, and explanations of that topic are beyond the scope of this paper (for details see, for example, [START_REF] Appleby | Millimeter-wave and submillimeter-wave imaging for security and surveillance[END_REF]. However, if a potential threat is identified, the passenger is invited to undergo a manual search by a security officer. In addition to being less efficient and more time consuming than scanning, a manual search is presumed to be highly intrusive (e.g. [START_REF] Langerman | News & Views[END_REF]. The benefits gained by using security scanners would be negated if the systems are not reliable. A security scanner can be considered unreliable if the rate of false positives and/or the rate of false negatives are too high. False positives occur when a security scanner highlights objects that do not constitute threats and false negatives when threats are not detected.

Second, the rapidity of data processing will have an impact on passenger flow. Using security scanners is presumed to be faster than performing manual searches: delays are in the terms of seconds for scanning, and of minutes for manual search. Short rapid inspection times would likely account for an enhanced passenger"s acceptance of security body screening as well as it would be a benefit in terms of airport authorities [START_REF] Holguίn-Veras | An assessment of the impacts of inspection times on the airline industry"s market share after September 11th[END_REF].

To recap, the ideal performance of security scanners would be their ability to detect both metallic and non-metallic threats in a few seconds with a high detection rate and low false-alarm rate. That kind of technical acceptance should intersect with the psychological acceptance of security scanners to ensure harmonious and efficient security controls. Hence, it would be interesting to investigate the passengers" views about the performance of security scanners.

The next sections deal with three studies on passengers" views of those technologies. The first study was carried out with air travellers in New York City and Tel Aviv, the second one in the UK. Both studies come from the review of the literature on security body scanners. The presentation of the third study that was carried out in France in 2012 is the primary goal of the present paper.

Two empirical studies in the literature on acceptance of security body scanners

Leo and Lawler's study with air travellers in the USA and Israel

The first study, reported by [START_REF] Leo | A Study of passenger perception and sensitivity to airport backscatter X-ray technologies[END_REF], focuses on the acceptance of backscatter machines. The investigated factors were sensitivity to privacy; perception of a security threat; knowledge of the functionality of screening technologies; knowledge of imaging and information storage by screening technologies and of their usage. The participants were experienced air travellers and they received the instrument survey questionnaire by e-mail. The responses were scored on a 6-point Likert-type scale going from none to very high, and the means (M) were calculated.

The survey conducted in New York shows that the 25 participants were not highly sensitive either to privacy (M = 3.84) or to the severity of the threat of terrorism (M = 3.64). They were less perceptive of the effectiveness of screening technologies (M = 2.68), less knowledgeable about the functioning of screening technologies (M = 1.52), and less knowledgeable about information storage by such technologies (M = 0.84).

The survey conducted in Tel Aviv shows a very high perceived security threat (M = 5.00) and perception of the effectiveness of screening technologies (M = 5.00) despite no knowledge of the data storage, techniques, or usage of the technologies (M = 0.00) and no privacy sensitivity (M = 0.00). The willingness to accept the personal intrusion presented by screening technologies was very high (M = 5.00).

Leo and Lawler concluded that the "culture of security alert, if not fear, and the tangibility of security threats in Israel" (Leo and Lawler, 2007, p. 17) might have made knowledge of screening technology not necessary for the Tel Aviv participants" receptivity of the technology.

The above study is very interesting because it illustrates the relationship between perceived risk and willingness to accept personal intrusion by screening technologies. Leo and Lawler"s study shows also the possible absence of relationship between the knowledge of screening technologies and the acceptance of them. If acceptance of security scanners (i.e. intention to undergo scanning) is considered as the result of a decision-making process, then the acceptance might be influenced by the affect heuristic. The affect heuristic, which is a mental shortcut that relies on salient affective sides of mental imagery, is used in decisionmaking involving judgment of risks and benefits [START_REF] Finucane | The affect heuristic in judgments of risks and benefits[END_REF]Slovic et al., 2004). In other words, the differences between participants" attitudes in New York and Tel Aviv may be explained by the use of a shortcut based on affect (here, fear) which would have biased the responses in Tel Aviv"s study.

Mitchener-Nissen, Bower, and Ketty's study with air travellers in the UK

The second study, reported in [START_REF] Mitchener-Nissen | Public attitudes to airport security: The case of whole body scanners[END_REF], was conducted in July 2010 at Manchester Airport. Two questionnaires were used to investigate the passengers" attitudes towards whole-body scanners: the first questionnaire comprised two central questions on whether being for or against those scanners and the preference between a scan and a pat down; the second questionnaire included 10 opinion statements about the necessity of such scanners with regard to threat of terrorism; their impact on flight safety; issues of dignity and privacy; perception of threat to health.

Regarding the first questionnaire (N = 225), 88 percent of the respondents would choose a scan over a pat-down. The main reasons of their choice are, in order of frequency: less intrusiveness; speed; safety/security. The main criteria for those who preferred the pat-down option were familiarity with pat-down search and health concern about scans.

Regarding the second questionnaire (N = 186), there were two groups: one group was provided detailed information on backscatter whole-body scanners, whereas the control group did not receive any information. The results show that the participants who received information had more positive attitudes towards body scanners than those who did not.

The paper of Mitchener-Nissen et al. ( 2012) is interesting because the preference between scanners and manual searches was investigated in detail; the reasons of the preference were questioned. Their study shows the impact of knowledge on attitudes, whereas having knowledge seems not to have been a major factor in Leo and Lawler"s study. The comparison of the two papers suggests that the culture and society under study have to be taken into account to understand how acceptance is formed.

A French opinion survey on the acceptability of security scanners at airports

The study carried out in France in 2012 aimed at analyzing air travellers" acceptability of security scanners. The term acceptability is chosen because security scanners are not still deployed at French airports. The intention to undergo scanning and other topics reviewed in the previous sections were investigated using a survey questionnaire.

Method

The method consisted of a face-to-face survey conducted by the public poll institute TNS Sofres in July 2012. Outsourcing the survey to a research institute was motivated by a concern of representativeness of the results.

Respondents were interviewed at home. The weighted sample size of those who had flown at least once in the previous 12 months was N = 458 (234 men and 223 women). This was derived from a representative national sample of 2000 people aged 15 and over (quota sampling approach).

The questionnaire contained 14 closed items that were developed from the literature reviewed in the previous section and discussed with TNS Sofres.

Two items were expressed in terms of trust. Indeed, trust can be defined as "a psychological state, resulting from knowledge, beliefs, and assessments related to the decision-making situation, which creates confident expectations" (Rajaonah, Anceaux, and Vienne, 2006, p. 102). Therefore, perceived security scanner technology"s ability to detect hidden threats as well as perceived airport authorities" performance to ensure confidentiality of data provided by the scanner may be investigated through the concept of trust.

Three items were related to the perceived breaches of privacy and fundamental rights posed by security scanning. A YES/NO response format was used according to an implicit assumption that a violation of fundamental rights would not be perceived in degrees.

Two items on the acceptability of security scanners investigated behavioural intention between three alternatives: undergoing scanning, undergoing a hand search, or giving up flying (multi-choice response). The first item focused on security scanners providing a fuzzy image of the body of the passenger, the second on those providing an avatar. The English translations of the items are presented in Table 1.

A brief presentation of the topic was introduced to the participants, with no information concerning advanced imaging technologies. The English translation of the presentation is as follows: "The authorities are examining the possibility of deploying security scanners at French airports. As these scanners are capable of detecting explosives, they are much more than portal metal detector systems. Potential threats are visualized on a screen that displays either a fuzzy image of the body of the passenger or a generic avatar that is identical for all passengers. Only authorized security officers are allowed to examine what is displayed on the screen. Lastly, the data provided by the scanners are not stored".

The questions were asked in a different random order for each interview. Slides of a fuzzy image and of an avatar were shown three times to the participant: at the introduction of the questionnaire and at each of the two questions on acceptability.

Results and Discussion

The results are divided into four subsections:

acceptability; privacy and fundamental rights issues; health issues; and performance issues.

The percentage distributions of responses to the questions on perceptions and trust are presented in Table 2.

Acceptability

The acceptability of security scanners was investigated in terms of behavioural intention to undergo scanning if such systems were implemented at French airports.

More precisely, the respondents had to select one response among three alternatives: undergoing scanning, undergoing a hand search, or giving up flying (multi-choice response).

Two kinds of security scanner were investigated depending on the representation used by the system to display potential hidden objects, either a fuzzy image of the body of the passenger or a generic avatar. The results are shown in Figure 1.

With regard to security scanners providing a fuzzy image of the body of the passenger, most of the respondents (83.3 percent) would undergo scanning, whereas 13.4 percent would prefer a manual search, and two respondents would give up flying. In other words, the percentage of the respondents who were resistant to the scanning procedure, that is to say, those who chose either undergoing a manual search or giving up flying, was of 14 percent. On the other hand, the percentage of the respondents who intended to fly whatever the procedure at security control (either passing through a scanner providing a fuzzy image or undergoing a manual search) was 96.8 percent.

With regard to security scanners providing a generic avatar, the great majority of the respondents (84.6 percent) would undergo scanning, whereas 11.5 percent would prefer a manual search and one respondent would give up flying. The percentage of the respondents who were resistant to the scanning procedure was 11.7 percent, and those who intended to fly whatever the procedure at security control were made up 96.1 percent.

To recap, the great majority of the respondents would undergo scanning whatever the representation. These findings are remarkably similar to those in [START_REF] Mitchener-Nissen | Public attitudes to airport security: The case of whole body scanners[END_REF]. Indeed, their study shows that the great majority of the passengers interviewed were in favour of the use of whole body scanners in airports, and they preferred a scan to a pat-down.

However, cause-effect relationships between perceptions and acceptability of security scanners were not investigated in this French study, whereas they were in Mitchener-Nissen et al."s one. For example, these authors showed that the safety and security issues were the most frequently cited reason for explaining preference for whole body scanners, while the most cited reason for choosing a scan over a pat-down was intrusiveness of pat-down search.

Most of the respondents in France (70.2 percent) agreed with the statement that they felt the threat of terrorism to be present, whereas 27.1 percent disagreed. Furthermore, a very strong majority of the respondents (91.6 percent) agreed with the statement that passing through a security scanner was normal in the fight against insecurity (i.e. insecurity in a general way). It might be hypothesized from the results that perceived threat of terrorism and perceived social norm to undergo scanning had influenced the participants" intention to undergo scanning.

Health issues

With regard to health issues, nearly twothirds of the respondents disagreed with the statement that passing through a security scanner would have an effect on their health (Figure 2 and Table 2). It is important to notice that more than half of the participants who were resistant to scan perceived that passing through a security scanner would have an effect on their health: 59.2 percent of the respondents resistant to the scanner providing a fuzzy image; 62.8 percent for the scanner providing an avatar.

In [START_REF] Mitchener-Nissen | Public attitudes to airport security: The case of whole body scanners[END_REF], only 2.7 percent of the respondents chose the pat-down option because of health concerns. Hence, their results are not fully similar to those of the French study, but it might be that they are not comparable.

Indeed, the cause-effect relationship between resistance to the scanning procedure and health concerns can just be hypothesized in the French study.

Privacy and fundamental rights issues

Results on privacy and fundamental rights issues include three parts: perceived breach of dignity, freedom, and private life; perceived embarrassment due to the visualization of passengers" images by security officers and perceived embarrassment due to manual search; trust in airports" authorities to protect private personal data.

 As in shown in Figure 3, the great majority of the respondents perceived breaches of neither private life nor freedoms or dignity (respectively, 83.3 percent, 81.4 percent, and 79.9 percent of disagreement with the statement of perceived breaches). Nevertheless, comparing the results of the 12.8% of the respondents who seemed to have been resistant to the scanning procedure with those of all the respondents, it seems that the "opponents" might have tended to be a bit more sensitive to breaches of their fundamental rights (Figure 4).  Concerning embarrassment due to scanning, as shown in Table 2, perceived embarrassment tended to occur more frequently with an image of the body of the passenger (20.1 percent) than with an avatar (14 percent). However that may be, most of the respondents disagreed with the statement on embarrassment due to the visualization of image by a security officer (79.5 percent in the case of an image of the passenger; 84.8 percent in the case of a generic avatar).

Opinions on manual search were less clearcut. Indeed, 40.1 percent of the respondents globally agreed with the statement that manual search was embarrassing and 59.1 percent disagreed.

 Concerning data protection, the majority of the respondents (71.3 percent) agreed with the statement that they would trust airport authorities to guarantee the anonymity and confidentiality of the data provided by security scanners (Table 2).

To recap the results, privacy and fundamental rights might have not been a problem for most of the participants. The question is thus whether there is a gap between experts and public"s views of privacy and fundamental rights issues. The response may be that two levels of explanation are involved, namely the psychological and legal levels. The focus of research in the field of psychology is on passenger"s perceptions, while the focus at the legal level is on the protection of the citizens according to the precautionary principle.

Performance

Performance issues were investigated with two items: trust in security scanners to perform required functions and the perceived efficiency of using security scanners to move the passengers through the security system. The responses are shown in Table 2.

A great majority of the respondents (80.9%) agreed to the statement that they would trust security scanners to detect hidden explosives. The statement that the use of security scanners would enhance control procedure times at airports was agreed with by 63.3 percent of the respondents.

Security scanners were thus perceived positively, despite the possible lack of knowledge of the respondents about the efficiency of the technology. Indeed, as mentioned earlier, no information about the functioning of security scanners was provided to the participants.

Recall that the Tel Aviv participants in the Leo and Lawler"s study perceived the highest level of the effectiveness of screening technologies, despite no knowledge of their functioning [START_REF] Leo | A Study of passenger perception and sensitivity to airport backscatter X-ray technologies[END_REF]. Recall also that [START_REF] Mitchener-Nissen | Public attitudes to airport security: The case of whole body scanners[END_REF] showed that providing information to the passengers in the UK enhanced their attitudes toward backscatter scanners. The differences between those two studies plus the results in the French study reinforce the idea that the psychological process of acceptance of security scanners might not be based only on knowledge. How the acceptance of security scanners is formed might also involve specific values and beliefs shared among the members of the society and/or culture under study.

Conclusion

The study presented in this paper aimed to investigate the acceptability of security scanners at French airports. The results show that undergoing scanning would be chosen by the passengers rather than undergoing manual search, whatever the representation used by the system to display potential hidden objects (a fuzzy image of the body of the passenger or a generic avatar). The great majority of the respondents perceived breaches of neither their private life nor their freedoms or human dignity. Lastly, despite their possible lack of knowledge on the efficiency of the technology, most of the respondents trusted security scanners to detect hidden explosives. Acceptability of security scanners at airports

The findings, especially in the light of those of the literature on security scanners, suggest that studying the acceptance of new technologies such as security scanners is more relevant if they are considered within their sociotechnical environment. Indeed, that provides other explanatory factors than perceived performance as traditionally studied in research on the acceptance. That is illustrated on Figure 5.

The hypothesis could be that the passenger"s response to the stimulus of terrorism threat would emerge from the most satisfactory cognitive compromise between expected benefits, accepted risks, and tolerated constraints regarding each alternative (e.g. undergoing scanning, undergoing manual search, or giving up flying). The compromise would be shaped by individual"s trust and perceptions that are themselves shaped by knowledge based on information from the decision-makers as well as by social and cultural values including socially-shared affect and worldviews [START_REF] Peters | The role of affect and worldviews as orienting dispositions in the perceptions and acceptance of nuclear power[END_REF][START_REF] Slovic | Trust, emotion, sex, politics, and science: A risk-assessment battlefield[END_REF].

The socially shared values might be the chief influence on the cognitive compromise that underlies the passengers" acceptance. The first implication of that viewpoint is the importance of taking into account the social and cultural factors for providing information to the citizens, particularly those who may be resistant to the scanning procedure.

The findings have also implication in terms of trust. Indeed, the results show that the respondents might have tended to trust both technology and institutions in the fight against terrorism. Nevertheless, trust is fragile and hard to be restored [START_REF] Muir | Trust in automation. Part II. Experimental studies of trust and human intervention in a process control simulation[END_REF][START_REF] Slovic | Trust, emotion, sex, politics, and science: A risk-assessment battlefield[END_REF]. Therefore, recommendations should include guidelines to ensure public awareness of technologies limitations as well as security costs.

To conclude, the objective of future works is to use the proposed model in studies within sociotechnical environments of security at airports, concerning other technologies of security and/or other actors than passengers.

Qualitative approaches of social sciences will be prioritized through techniques such as face-to-face semi-directed interviews and/or focus-group discussions. Both techniques allow researchers to collect in-depth information, especially responses to such questions of "why" and "how", which would have been very useful to complement the quantitative analysis in the French study.

Figure 1 :

 1 Figure 1: Percentage distribution of responses regarding intentional behaviour at the passenger screening procedure by security scanner type (one providing a fuzzy image and the other an avatar). The respondent had to select only one response from among the three proposed alternatives: undergoing scanning, undergoing a manual search, or giving up flying.

Figure 2 :

 2 Figure 2: Percentage distribution of responses to perceived effects on health of passing through a security scanner (N = 458).

Figure 3 :

 3 Figure 3: Percentages of the respondents who perceived a breach to the right to a private life, freedom, or human dignity.

Figure 4 .

 4 Figure 4. Perceived breaches of fundamental rights: Means of the percentages between responses regarding scanners providing image of the body of the passenger and responses regarding scanners providing a generic avatar: on the right, allthe respondents; on the left, the respondents who were resistant to the scanning procedure.

Figure 5 :

 5 Figure 5: The passenger"s acceptance of security scanners: Taking into account the influence of knowledge based on information from the decision-makers and the socially shared affect and values on the cognitive compromise that underlies acceptance.

Table 1 :

 1 Items of the questionnaire: the studied factors underlying the questions are in the left column, the items of the questionnaire translated from French in the middle, and the response categories in the right column.

	Studied factors	Items of the questionnaire	Response categories
	1. Perceived threat of terrorism	You feel terrorism threat as present
	2. Perceived health risk	Passing through security scanners will have effect on your health
	3. Perceived efficiency of	The use of security scanners would enhance
	using security scanners	control procedure times
	4. Perceived social norm to undergo scanning	Passing through security scanners is normal in the fight against insecurity	4-point scale plus a "No opinion" category:
	5. Trust in the technology	You trust the security scanner technology to detect hidden explosives	"Strongly agree", "Rather agree",
	6. Trust in institutions and organizations	You trust airport authorities to guarantee anonymity and confidentiality of data provided by the scanner	"Rather disagree" "Strongly disagree",
		The visualization of a fuzzy image of your
		body on a screen by a security officer is
		embarrassing
	7. Anticipated experience of embarrassment	The visualization of a representation of your silhouette by a generic avatar is embarrassing
		Manual search on your body by a security
		officer is embarrassing
		Security scanner inspection invades private
		life ("la vie privée" in the French version)
	8. Perceived breaches of fundamental rights	Security scanner inspection invades freedoms ("les libertés")	YES/NO response
		Security scanner inspection invades dignity
		("la dignité humaine")
		If security scanners providing a fuzzy image of	Multiple-choice
		the body of the passenger were installed at	response (one response
		French airports, what would you do?	only):
	9. Acceptability of security scanners	If security scanners providing a generic	-Undergoing scanning -Undergoing a hand
		avatar were installed at French airports, what would you do?	search -Giving up flying

Table 2 :

 2 Percentage distributions of responses to the questions using a 4-point scale.

	Items	Strongly agree	Rather agree	Rather disagree	Strongly disagree	No opinion
	Perceived presence of terrorism threat	28.8%	41.4%	18.7%	8.5%	2.7%
	Perceived effect on health	6.2%	21.2%	28.9%	35.9%	7.8%
	Perceived efficiency of using security scanners	22.1%	41.1%	19.6%	10.1%	7.1%
	Perceived normality to undergo scanning	54.5%	37.1%	5%	2.1%	1.3%
	Trust in security scanners	32.1%	48.8%	11.7%	4.8%	2.5%
	Trust in airport authorities	31.2%	42%	17.3%	6.7%	2.8%
	Embarrassment with a fuzzy image	6.4%	13.7%	31.9%	47.6%	0.3%
	Embarrassment with an avatar	2.1%	11.9%	26.4%	58.4%	1.3%
	Embarrassment with manual search	12.8%	27.3%	26.6%	32.5%	0.8%

Acknowledgments

This work was funded by the French National Research Agency (ANR) within the project SAMOSA of the CSOSG Program (ANR-10-SECU-0011).

The survey was sub-contracted to TNS Sofres (138-avenue Marx Dormoy 92129 Montrouge France). The authors thank Béatrice Guilbert and Séverine Thiriot for their precious advices. For any technical question regarding the survey, please contact Ms. Béatrice Guilbert (beatrice.guilbert@tnssofres.com).

Finally, the authors thank very much the reviewers of the previous versions for their helpul remarks. U.S. Department of Homeland Security. ( 2011


Matthieu Roy

Stefan Schmid

Gilles Tredan

Modeling and Measuring Graph Similarity: The Case for Centrality Distance

Keywords: J.4 [Computer Applications]: Social and Behavioral Sciences Complex Networks, Graph Similarity, Centrality, Dynamics, Link Prediction

The study of the topological structure of complex networks has fascinated researchers for several decades, and today we have a fairly good understanding of the types and reoccurring characteristics of many different complex networks. However, surprisingly little is known today about models to compare complex graphs, and quantitatively measure their similarity.

This paper proposes a natural similarity measure for complex networks: centrality distance, the difference between two graphs with respect to a given node centrality. Centrality distances allow to take into account the specific roles of the different nodes in the network, and have many interesting applications. As a case study, we consider the closeness centrality in more detail, and show that closeness centrality distance can be used to effectively distinguish between randomly generated and actual evolutionary paths of two dynamic social networks.

INTRODUCTION

How similar are two graphs G1 and G2? Surprisingly, today, we do not have good measures to answer this question. In graph theory, the canonical measure to compare two graphs is the Graph Edit Distance (GED) [START_REF] Gao | A survey of graph edit distance[END_REF]: informally, the GED dGED(G1, G2) between two graphs G1 and G2 is defined as the minimal number of graph edit operations that are needed to transform G1 into G2. The specific set of allowed graph edit operations depends on the context, but typically includes some sort of node and link insertions and deletions.

While graph edit distance metrics play an important role in computer graphics and are widely applied to pattern analysis and recognition, we argue that the graph edit distance is not well-suited for measuring similarities between natural and complex networks. The set of graphs at a certain graph edit distance d from a given graph G, are very diverse and seemingly unrelated: the characteristic structure of G is lost.

A good similarity measure can have many important applications. For instance, a similarity measure can be a fundamental tool for the study of dynamic networks, answering questions like: Do these two complex networks have a common ancestor? Or: What is a likely successor network for a given network? While the topological properties of complex networks have fascinated researchers for many decades, (e.g., their connectivity [START_REF] Barabási | Emergence of Scaling in Random Networks[END_REF][START_REF] Newman | Clustering and preferential attachment in growing networks[END_REF], their constituting motifs [START_REF] Milo | Network motifs: Simple building blocks of complex networks[END_REF], their clustering [START_REF] Watts | The small world problem[END_REF] or community patterns [START_REF] Berry | Tolerating the community detection resolution limit with edge weighting[END_REF]), today, we do not have a good understanding of their dynamics over time.

Our Contributions. This paper initiates the study of graph similarity measures for complex networks which go beyond simple graph edit distances. In particular, we introduce the notion of centrality distance dC (G1, G2), a graph similarity measure based on a node centrality C.

We argue that centrality-based distances are attractive similarity measures as they are naturally node-oriented. This stands in contrast to, e.g., classic graph isomorphism based measures which apply only to anonymous graphs; in the context of dynamic complex networks, nodes typically do represent real objects and are not anonymous!

We observe that the classic graph edit distance can be seen as a special case of centrality distance: the graph edit distance is equivalent to the centrality distance where C is simply the degree centrality, henceforth referred to as the degree distance dDC. We then discuss alternative centrality distances and, as a case study, explore the closeness distance dCC (based on closeness centrality) in more detail.

In particular, we show that closeness distance has interesting applications in the domain of dynamic network prediction. As a proof-of-concept, we consider two dynamic social networks: (1) An evolving network representing the human mobility during a cocktail party, and (2) a Facebook-like Online Social Network (OSN) evolving over time. We show that actual evolutionary paths are far from being random from the perspective of closeness centrality distance, in the sense that the distance variation along evolutionary paths is low. This can be exploited to distinguish between fake and actual evolutionary paths with high probability.

Examples. To motivate the need for graph similarity measures, let us consider two simple examples.

Example 1.1 (Local/Global Scenario). We consider three graphs G1, G2, G3 over five nodes {v1, v2, . . . , v5}: G1 is a line, where vi and vi+1 are connected in a modulo manner; G2 is a cycle, i.e., G1 with an additional link {v1, v5}; and G3 is G1 with an additional link {2, 4}.

In this example, we first observe that G2 and G3 have the same graph edit distance to G1: dGED(G1, G2) = dGED(G1, G3) = 1, as they contain one additional edge. However, in a social network context, one would intuitively expect G3 to be closer to G1 than G2. For example, in a friendship network a short-range "triadic closure" [START_REF] Kossinets | Empirical analysis of an evolving social network[END_REF] link may be more likely to emerge than a long-range link: friends of friends may be more likely to become friends themselves in the future. Moreover, more local changes are also expected in mobile environments (e.g., under bounded human mobility and speed). As we will see, the centrality distance concept introduced in this paper can capture such differences.

Example 1.2 (Evolution Scenario). As a second artificial and very simple example, in this paper we will consider two graphs G1 and G2, where G1 is a line topology and G2 is a "shell network", shown in Figure 1. We ask the question: what is the most likely evolutionary path that would lead from the G1 topology to G2?

Note that the graph edit distance does not provide us with any information about the likely evolutionary paths from G1 to G2, i.e., on the order of the edge insertions: there are many possible orders in which the missing links can be added to G1, and these orders do not differ in any way. In reality, however, we often have some expectations on how a graph may have evolved between the two given snapshots G1 and G2. For example, applying the triadic closure principle to our example, we would expect that the missing links are introduced one-by-one, from left to right. A similar evolution may also be predicted by a temporal preferential attachment model [START_REF] Newman | Clustering and preferential attachment in growing networks[END_REF]: the degree of the most highly connected node is likely to grow further in the future.

The situation may look different in a technological, manplanned network. For example, adding links from left to right only slowly improves the "routing efficiency" of the network: after the addition of t edges from left to right, the longest shortest path is n -t hops, for t < n -1. A "better" evolution of the network can be obtained by adding links to the middle of the network, reducing the much faster in the beginning: after t edge insertions, the distance is roughly reduced by a factor t.

MODEL AND BACKGROUND

This paper focuses on named (a.k.a. labeled) graphs G = (V, E): graphs where vertices v ∈ V have unique identifiers and are connected via undirected edges e ∈ E. We focus on node centralities, centralities assigning "importance values" to nodes v ∈ V .

Definition 2.1 (Centrality

). A centrality C is a function C : (G, v) → R + that takes a graph G = (V, E) and a vertex v ∈ V (G) and returns a positive value C(G, v).
The centrality function is defined over all vertices V (G) of a given graph G. Although we here consider named graphs, we require centrality values of vertices to be independent of the vertex's identifier, i.e., centralities are unchanged by a permutation of identifiers: given any permutation

π of V (G), ∀v ∈ V (G), C(π(G), π(v)) = C(G, v), where π(G) = (V (G), {(π(v), π(v ′ )) : (v, v ′ ) ∈ E(G)}.
Centralities are a common way to characterize complex networks and their vertices. Frequently studied centralities include the degree centrality (DC), the betweenness centrality (BC) and the closeness centrality (CC), among many more. A node is DC-central if it has many edges: the degree centrality is simply the node degree; a node is BC-central if it is on many shortest paths: the betweenness centrality is the number of shortest paths going through the node; and a node is CC-central if it is close to many other nodes: the closeness centrality measures the inverse of the distances to all other nodes. Formally:

1. Degree Centrality: For any node v ∈ V (G) of a network G, let Γ(v) be the set of neighbors of node v: Γ(v) = {w ∈ V s.t. {v, w} ∈ E}. The degree centrality DC of a node v ∈ V is defined as: DC(G, v) = |Γ(v)|.
2. Betweenness Centrality: For any pair (v, w) ∈ E(G), let σ(v, w) be the total number of different shortest paths between v and w, and let σx(v, w) be the number of shortest paths between v and w that pass through x ∈ V . The betweenness centrality BC of a node v ∈ V is defined as: BC(G, v) = x,w∈V σv(x, w)/σ(x, w). As a slight variation from the classic definition, we assume that a node is on its own shortest path: ∀v, w ∈ V 2 , σv(v, w)/σ(v, w) = 1. We adopt the convention: ∀v ∈ V, σv(v, v)/σ(v, v) = 0. The reason of this variation will become clear in the next section. w) . By convention, we define the centrality of a node with no edges to be 0. Moreover, throughout this paper, we will define the graph edit distance between two graphs G1 and G2 as the minimum number of operations to transform G1 into G2 (or vice versa), where an operation is one of the following: link insertion, link removal, node insertion, node removal.

Closeness Centrality

: The closeness centrality CC of a node v ∈ V is defined as: CC(G, v) = w∈V \v 2 -d(v,

GRAPH DISTANCES

We now introduce our centrality-based graph similarity measure. We will refer to the set of all possible topologies by G, and we will sometimes think of G being a graph itself: the "graph-of-graphs" which connects graphs with graph edit distance 1. Figure 2 illustrates the concept. Definition 3.1 (Centrality Distance). Given a centrality C, we define the centrality distance dC (G1, G2) between two neighboring graphs as the component-wise difference:

∀(G1, G2) ∈ E(G), dC (G1, G2) = v∈V |C(G1, v) -C(G2, v)|.
This definition extends naturally for non-neighboring graph couples: the distance dC (G1, G2) between G1 and G2 is simply the graph-induced distance.

As we will see, the distance axioms are indeed fulfilled for the major centralities. The resulting structure supports the formal study with existing algorithmic tools. Let us first define the notion of sensitivity.

v 1 v 2 v 3 v 5 G 1 : v 4 v 1 v 2 v 3 v 5 G 2 : v 4 v 1 v 2 v 3 v 5 G 3 : v 4 v 1 v 2 v 3 v n v 1 v 2 v 3 v n G 1 G 2
∀G ∈ G, ∀e ∈ E(G), ∃v ∈ V (G) s.t. C(G, v) = C(G \ {e}, v),
where G \ {e} is the result of removing edge e from G. Lemma 3.3. DC, BC and CC are sensitive centralities.

It is easy to see that also other centralities, such as cluster centralities and Page Rank centralities are sensitive. The distance axioms now follow directly from the graph-induced distance.

Theorem 3.4. For any centrality C, dC is a distance on G iff C is sensitive.

The centrality distance metric of Definition 3.1 however comes with the drawback that it is expensive to compute. Thus, we propose the following approximate version: Definition 3.5 (Approximate Centrality Distance). Given a centrality C, we define the approximate centrality distance dC (G1, G2) between any two graphs as the component-wise difference:

∀(G1, G2), dC (G1, G2) = v∈V |C(G1, v) -C2(G2, v)|.
Note that dC ≤ dC always holds. As we will see, while the approximate distance can be far from the exact one in the worst case, it features some interesting properties.

EXAMPLE: CLOSENESS DISTANCE

To illustrate the concepts, we will follow the example of a topological evolution changing a line graph into a shell graph (depicted in Figure 2

Degree Distance

As a baseline and for comparison with alternative centralities, we will consider the degree distance dDC(G1, G2): the distance between two graphs simply counts the number of different edges. We first make the simple observation that the number of graph edits is equivalent to the differences in the centrality vectors.

Observation 1. The graph edit distance is equivalent to the degree distance, i.e., dGED ≡ dDC. This connection is established by the topological shortest path in the graph-of-graphs G. Let us consider our example from Figure 2 (right): Since all paths from G1 to G2 which do not introduce unnecessary edges have the same cost, the order in which edges are inserted is irrelevant. From a dGED perspective the incremental (left) and the dichotomic (right) paths of Figure 2 (right) are equivalent.

We make the following observation:

Observation 2. The degree distance resp. graph edit distance does not provide much insights into graph evolution paths: essentially all paths have the same costs.

Closeness Distance

Intuitively, a high closeness distance indicates a large difference in the distances of the graph. The closeness distance dCC has some interesting properties. For example, the shortest path in the graph-of-graph is connected the the topological shortest path. In particular, if two graphs are related by inclusion, the shortest closeness path is also a topological shortest path, as shown in the following. Theorem 4.1. Let G1 and G2 two graphs in G such that E(G1) ⊂ E(G2). Then all the topological shortest paths ( i.e. paths that only add edges from G1 to G2) are equivalent for closeness.

The inclusion property is a relevant property in many temporal networks, e.g., where links do not age (e.g. if an edge denotes that u has ever met/traveled/read v).

To give some intuition of the closeness distance, Figure 4 plots the evolution of the distance terms over time. As we can see, in the dichotomic order, first longer links are added, while the first incremental steps are more or less stable.

The dichotomic path has the larger impact on the dynamic graph's shortest path distances. This indicates that the closeness distance could even be used for "greedy routing", in the sense that efficient topological evolutions can be computed by minimizing the distance to a target topology.

EXPERIMENTAL CASE STUDIES

This section studies the power and limitation of closeness distance empirically, in two case studies: the first scenario is based on a data set we collected during a cocktail party and models a human mobility pattern; the second scenario is based on an evolving online social network (OSN) data set which is publicly available.

Datasets. The first case study is based on the SOUK dataset [START_REF] Killijian | SOUK: Social Observation of hUman Kinetics[END_REF]. This dataset captures the social interactions of 45 individuals during a cocktail, see [START_REF] Killijian | SOUK: Social Observation of hUman Kinetics[END_REF] for more details. The dataset consists in 300 discrete timesteps, describing the dynamic interaction graph between the participants, one timesteps every 3 seconds.

The second case study is based on a publicly available dataset FBL [START_REF] Opsahl | Clustering in weighted networks[END_REF], capturing all the messages exchanges reon an online Facebook-like social network between roughly 20k users over 7 months. We discretized the data into a dynamic graph of 187 timesteps representing the daily message exchanges among users. For each of these two graphs series, we compare each graph Gt with the subsequent one: Ga = Gt,G b = Gt+1. First, we generate a set S of 200 samples such that ∀G2 ∈ S, dGED(Ga, G2) = dGED(Ga, G b ). Then we compare the centrality induced distance dC from Ga to the samples of S against dC (Ga, G b ).

Methodology. We study the question whether centrality distances could be used to predict the evolution of a temporally evolving network. To this end, we introduce a simple methodology: We take a graph G1 and a graph G2 following G1 later in time in the given experiment. For these two graphs, the graph edit distance (or "radius") R := dGED(G1, G2) is determined, and we generate alternative graphs Gi at the same graph edit distance R uniformly at random. We investigate the ques-

G i CD=r G 1 GED=R G 2
Figure 4: Illustration of our methodology: Given an initial graph G1, graphs Gi at a given graph edit distance d GED = R are generated uniformly at random. The actual later graph observed in the experiment is denoted by G2. We test the hypothesis that G2 is closer to G1 than other graphs Gi with respect to a certain centrality distance dC .

tion whether closeness centrality distance can help to effectively distinguish G2 from other graphs Gi, in the sense that dCC (G1, G2) ≪ dCC (G1, Gi) for i = 2. Figure 4 illustrates our methodology.

Results. Figure 5 (left) provides a temporal perspective on the evolution of dGED for both the 300 timesteps of the SOUK dynamic graph and the 187 timesteps of the FB dataset. Both datasets exhibit very different dynamics: FB has a high dynamics for the first 50 timestemps, and is then relatively stable, whereas SOUK exhibits a more regular dynamics.

Figure 5 (right) presents the results of our experiment on the SOUK dataset. It represents the closeness distance dCC from each graph Gt to Gt+1 in red. The distribution of dCC values from Gt to the 200 randomly sampled graphs of St+1 is represented as follows: the blue line is the median, while the gray lines represent the 5 and 95 percentiles of the distribution. One can observe that although ∀G2 ∈ St+1, dGED(Gt, G2) = dGED(Gt, Gt+1), most of the time dCC(Gt, Gt+1) ≤ dCC(Gt, G2), ∀G2 ∈ St+1. In other words, most of the times, the measured graph Gt+1 is closer to Gt in closeness distance than the 5% closest randomly sampled graphs. Figure 6 (Left) presents the same results on the FB dataset. Here, although most of the time the measured topology is closer in closeness distance, this is mostly true for the first, most dynamic, time steps.

Figure 6 (right) provides a more aggregate view of this observation: it shows the rank of dC (Gt, Gt+1) in the {dC (Gt, G2), G2 ∈ St+1} distribution for the closeness (CC) centrality distance for both dynamic graphs. Values are sorted increasingly, so rank 0 represents the smallest. This graph shows that out of the 300 timesteps of SOUK, the observed graph is closer than any of the 200 random samples in 298 timesteps for the closeness distance. The same statement holds for 73% of the 187 snapshots of the FB dataset.

The observation one can draw from this plot is that when we measure the raw evolution of topologies (in terms of degree distance) we only grasp a very incomplete, and rather pessimistic view of the dynamics on both datasets. Com- pared to a random evolution that would create the same degree distance difference, actual topology evolution leaves most of nodes importance as connectors (closeness distance) unchanged.

RELATED WORK

To the best of our knowledge, our paper is the first to combine the important concepts of graph distances and centralities. In the following, we will review the related works in the two fields in turn, and subsequently discuss additional literature on dynamic graphs.

Graph distances. Graph edit distances have been used extensively in the context of inexact graph matchings in the field of pattern analysis. Central to this approach is the measurement of the similarity of pairwise graphs. Graph edit distances are attractive for their error-tolerance to noise. We refer the reader to the good survey by Gao et al. [START_REF] Gao | A survey of graph edit distance[END_REF] for more details.

However, we in this paper argue that the graph edit distance fails to capture important semantic differences, and are not well suited to measure similarities between complex networks. Accordingly, we introduce a distance which is based on a parameterizable centrality.

In classic graph theory, notions of similarity often do not take into account the individual nodes. A special case are graph isomorphism problems: The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. While the problem is of practical importance, and has applications in mathematical chemistry, many complex networks and especially social networks are inherently non-anonymous. For example, for the prediction of the topological evolution of a network such as Facebook, or for predicting new topologies based on human mobility, individual nodes should be taken into account. Moreover, fortunately, testing similarity between named graphs is often computationally much more tractable.

Graph characterizations and centralities. Graph structures are often characterized by the frequency of small patterns called motifs [START_REF] Boccaletti | Complex networks: Structure and dynamics[END_REF][START_REF] Milo | Network motifs: Simple building blocks of complex networks[END_REF][START_REF] Wernicke | Efficient detection of network motifs[END_REF][START_REF] Schreiber | Frequency concepts and pattern detection for the analysis of motifs in networks[END_REF], also known as graphlets [START_REF] Przulj | Biological network comparison using graphlet degree distribution[END_REF], or structural signatures [START_REF] Contractor | Testing multitheoretical organizational networks: An analytic framework and empirical example[END_REF]. Another important graph characterization, which is also studied in this paper, are centralities. [START_REF] Brandes | Network Analysis: Methodological Foundations[END_REF] Dozens of different centrality indices have been defined over the last years, and their study is still ongoing, and a unified theory missing. We believe that our centrality distance framework can provide new inputs for this discussion.

Dynamic graphs. Researchers have been fascinated by the topological structure and the mechanisms leading to them for many years. While early works focused on simple and static networks [START_REF] Erdos | On the evolution of random graphs[END_REF], later models, e.g., based on preferential attachment [START_REF] Barabasi | Emergence of scaling in random networks[END_REF], also shed light on how new nodes join the network, resulting in characteristic graphs. Nevertheless, today, only very little is known about the dynamics of social networks. This is also partly due to the lack of good data, which renders it difficult to come up with good methodologies for evaluating, e.g., link prediction algorithms [START_REF] Liben-Nowell | The link prediction problem for social networks[END_REF][START_REF] Yang | Like like alike: joint friendship and interest propagation in social networks[END_REF].

An interesting related work to ours is by Kunegis [START_REF] Kunegis | On the spectral evolution of large networks[END_REF], who also studied the evolution of networks, but from a spectral graph theory perspective. In his thesis, he argues that the graph spectrum describes a network on the global level, whereas eigenvectors describe a network at the local level, and uses these results to devise link prediction algorithms.

CONCLUSION

We believe that our work opens a rich field for future research. In this paper, we mainly focused on closeness distance, and showed that it has interesting properties when applied to the use case of dynamic social networks. However, our early results indicate that other centralities have very interesting properties as well. For instance, it can be seen that using betweenness distance to move from a graph G1 to a smaller graph G2 results in the same graph sequence as Newman's graph clustering algorithms, indicating that betweeness distance can be used to study graph clusterings over time. The properties, opportunities and limitations of alternative centralities will be the main focus of our future work.

Figure 1 :Figure 2 :

 12 Figure 1: Left: Local/Global Scenario: G1 is a line graph, G2 and G3 are obtained from G1 by adding a link. Right: Evolution Scenario: G1 describes a line graph, G2 describes a shell graph.

Figure 3 :

 3 Figure 3: Evolution of closeness centrality distance dCC from GL to GS for n = 40. Dichotomic and incremental paths are depicted in Figure 2 (right). Both order define a different path in G from GL to GS. At each step, the closeness centrality-induced distance between Gi and Gi-1 is computed.

Figure 5 :Figure 6 :

 56 Figure 5: Left: Measured closeness distance dC from Gt to Gt+1 (red ), and to St+1 sampled graphs (blue: median, bars: 5 and 95 percentiles) over time. Right: Temporal representation of the measured closeness distance d CC from Gt to Gt+1 (red) on the SOUK dataset, and to St+1 sampled graphs (blue: median, bars: 5 and 95 percentiles) over time.

Acknowledgments. Stefan Schmid is supported by the DAAD-PHC PROCOPE program, the EIT ICT project Mobile SDN, and is part of the INP visiting professor program. Gilles Tredan is supported by the DAAD-PHC PROCOPE program.

APPENDIX

A. PROOF OF LEMMA 3.3 Let G ∈ G, and e = (u, v) ∈ E(G).

Degree centrality: DC(G, u) = DC(G \ {e}, u) + 1: DC is sensitive.

Betweenness centrality:

Recall our slightly changed definition of betweenness. Now, BC(G, u) =

x,w∈V σu(x, w)/σ(x, w). In G\{e}, all shortest paths are at least as long as in G, and the shortest path between u and v has increased at least one unit: BC is sensitive.

Closeness centrality: CC(G, u) =

w∈V \{u} 2 -d(u,w) . In G\{e}, all distances are greater or equal than in G, and strictly greater for the couple (u, v): CC is sensitive.

B. PROOF OF THEOREM 3.4

We show that dC is a metric on G: Separation ∀G1, G2 ∈ G, dC (G1, G2) ≥ 0 since all summands are non-negative.

Coincidence

For the sake of contradiction, assume C is not sensitive:

and therefore dC (G, G \ {e}) = 0 with G = G \ {e}: dC is not a metric.

Triangle inequality Observe that the neighbor-based dC definition associates each edge of G with a strictly positive weight. The multi-hop distance dC is the weighted shortest path in G given those weights. Since the weighted shortest path obeys the triangle inequality for strictly positive weights, dC does as well.

C. PROOF OF THEOREM 4.1

Let P be a topological shortest paths connecting G1 and G2: |P | = dGED(G1, G2). Since E(G1) ⊂ E(G2), P contains only edge additions to G1, where |P | denotes the path length. Also ∀u, v ∈ V 2 , ∀i,

where P [i] denotes the i-th node on the path. Therefore

Therefore:

The sum of the closeness distances on this path P is the exact closeness distance, for any such path P : all shortest paths are equivalent for dCC in this case.