Xavier D 'hérouville

Claude Gaudeau De Gerlicz

Aurore Caulier

Charles Margot Jack

Paul Pieter

Biometry applied to facial recognition of four portraits presumed to be of Leonardo da Vinci

ARTICLES __________________________________

Biometry applied to facial recognition of four portraits presumed to be of Leonardo da Vinci Xavier d'Hérouville 1* , Claude Gaudeau de Gerlicz 2* and Aurore Caulier 3* Our original aim for this project was to use artificial-intelligence tolls to measure objectively similarities observed subjectively by human eye between faces in graphic works using different pictorial techniques. We submit images that are presumed to be portraits of Leonardo da Vinci for identification by facial-recognition software. Algorithmic identification allowed us to compare each portrait to the whole database, pair by pair. However, our experimental method led us to reverse our approach. In the end we had to authenticate the results from facial-recognition technology using 'one-to-one' visual comparison. So that we double-checked by submitting the portraits to a panel of nonexpert volunteers, thus verifying our hypothesis. We proved that artificial intelligence is an invaluable addition to the toolkit of today's art expert. Reinforced by the natural abilities of the human eye, it will be essential to recognizing and verifying the identity of subjects in works of art.

Biometry (shortened from anthropobiometry, the study of 'the measurement of the living human body') is the 'automatic recognition of a person using distinctive features' 1 . Physical features are automatically measurable and so unique that they can be used to identify individuals or to verify their alleged identity 2 . Other properties of biometric characteristics are that they are universal and unique. That is, they are present in everyone and no one has exactly the same characteristics as anyone else. They also are permanent, meaning that they do not change over time or they change very little 3 . Humans have a natural ability, more or less developed according to the individual, to identify faces. The most discerning are called 'physiognomists' ('spotters' in the vernacular). In the art world, such experts are said to have an 'absolute eye' in much the same way as we speak of the 'absolute ear' ('perfect pitch' in the vernacular) of virtuoso musicians.

A computerized system of facial recognition

This ability to recognize faces does not exist naturally, of course, in the information technology (IT) of a computer. Hence, the need to simulate recognition by means of autonomous intelligent systems. Just as our brain stores images of faces we have seen and observed throughout our lives, facial-recognition computer software requires the prior establishment of a database of well-known faces. A facial recognition system must be able to automatically identify faces within a picture or a video. The image of the face to be recognized is normalized before being sent to the recognition system that will process it, using an algorithm to extract a signature. A classifier then compares this signature with the rest of the signatures in the database, in order to identify the face to be recognized 1 (Fig. 1).

Figure 1 | The different phases of facial recognition tools using artificial-

intelligence system 1 .

The biometric system can operate in these following two modes 2, 4 : -Verification (authentication), where the user inputs the image of a face alleged to be that of Person X, and the biometric system tries to answer the question: 'Is this Person X?' Using the characteristic data of the face in the image, the system formulates a mathematical signature for the face and searches the database for signature that corresponds to the alleged identity. This is a 'one-to-one' comparison, (1:1). The system verifies that the two faces match, and that this is indeed Person X. This procedure is commonly used in applications such as access control, border security and in payment authentication.

-Identification, where the biometric system is used to establish _________________________________________________________________________________ 1 PhD, Art expertise consultant, Editech, Florence, Italie.

2 PhD, Scientific director, Bioespas international, Tours, France.

3 PhD, Scientific director, Richelieu museum, France.

the identity of a person from a database and tries to answer the question : 'Who is Person X?' This time, the system compares the signature obtained from the input information with all others signatures in its database. This is a 'one-to-all' comparison, (1:N). The system gives each pair of images a score based on their degree of resemblance and ranks all the images in the database according to the paired scores obtained by these N 'one-toone' comparisons, (1:1) x N. This procedure is commonly use in commercial applications to identify regulars customers and VIP or shoplifters and fraudsters, but also in forensic investigations to identify criminals and even corpses. 5 .

Problems specific to the facial recognition of portraits

In the art domain, identification by an expert eye of the drawn or painted face is in fact synonymous with authentication. The scope of assessment of the portrait to be identified will be differ, depending on whether or not the artist is known:

-If the author of the portrait is known, the expert eye will give a name to the depicted subject based on the similarities between his face and other identified portraits done by the same artist.

-However, if the author is unknown, but the work relatively well dated, the expert eye will give priority to attributing the portrait to a specific artist. The similarities in the rendering will enable the expert eye to attribute the portrait to a particular known artist. The search for the subject's name moves down the priority list. At this stage, it was certainly tempting to use facial-recognition algorithms originally developed for forensic investigations to identify criminals and now often used in commercial applications. But we had reservations about applying such technology to the expert evaluation of pictures of faces 6 . If the identification is based on facial recognition that 'crystallizes the individual identity' 7 , the problem of recognizing a drawn or painted face is based on the rendering differential specific to each artist: the pictorial technique (sketch, drawing or painting), the style (the artist's 'creative hand' and the coarseness or fineness of its 'touch' ) and the format used, with its pictorial constraints. Indeed, regarding the fineness of the features and the processing details, consider the obvious rendering differences between a subject's face pictured in a miniature work done under a magnifying glass, and the same subject's face pictured in a giant mural or fresco work.

Some responses provided by early studies

Several scientific studies had already broached the topic seriously. One that should be mentioned is the biometric study conducted in 2005 by Raoul Perrot, director of the Anthropology and Anatomical Paleopathology Laboratory at the Claude Bernard University of Lyon 1, on behalf of the Design Department of the Cosimo Di Medici Laboratory of Paris 6 . Perrot used mathematical facial-recognition tools to assess the degree of resemblance between three painted or carved faces presumed to be of Benvenuto Cellini. The known and authenticated face of the Benvenuto Cellini 's portrait by Giorgio Vasari served as a reference. In the end, two of the three faces to be recognized were identified as Benvenuto Cellini's self-portraits. In 2012, a team of art historians from the California State University of Riverside led by Conrad Rudolph began work on a research project entitled a project entitled 'Faces, Art and Computerized Evaluation Systems' (FACES) 8 . The known and authenticated face of the three-dimensional Laurenzo di Medici 's death mask served as a reference. They began to develop a facial-recognition software that could identify his two-dimensional face in drawn or painted works of artists that were his contemporaries. One member of the team, Amit Roy-Chowdhury, has since used the software he helped to develop to identify Anne Boleyn, second and hapless wife of Henry VIII, in a portrait which until then had been considered that of Henri VIII's next wife, Jane Seymour. The same study enable him to unmask a falsely alleged portrait of Anne Boleyn exhibited at the National Portrait Gallery of London.

The implemented double experimental system

Faced with this delicate conundrum, we decided to approach it from two angles : The artificial-intelligence of the NeoFace © Watch algorithm, complemented by the discernment of the human ocular and cerebral neural network. Regarding facial recognition by means of software, scores established by comparing faces with those of a database are only numerical values based on confidence level and must be considered as such. The higher the score, the more the two faces are alike. Usually, a score around 0.550 for a pair of 'real faces' (photographed) would indicate that the two faces are potentially alike. In our particular case, namely the recognition of 'interpreted faces' (drawn or painted), we considered a score around 0.450 significant. However, we had to keep in mind that this score did not represent a probability coefficient. Computerized facial-recognition systems are not foolproof magic tools and final verification by the human eye will always be an invaluable adjunct. Moreover, in addition to the score value set by the software, it is also interesting to consider the comparative ranking images as selected by the database. Faces sorted by descending score up to rank 10 should be considered potentially similar, leaving the human eye ultimately exercise its critical and discriminatory potential. Hence the interest in this study to propose to a 85-person panel the subjective assessment of the degree of resemblance between the images of faces we submitted in parallel to the software NeoFace © Watch. Usually, a visually set score around 0.650 for a pair of 'real faces' (photographed) would indicate that the two faces are potentially alike. In our particular case, namely the recognition of 'interpreted faces' (drawn or painted) by a nonexpert panel, we also considered a score around 0.450 significant. Four faces with apparent features and extracted from separate graphic works (made of different pictorial techniques and realized in different formats) were the subject of the present study (Fig. 2). The first one [1] in Figure 2, is a portrait drawn with red chalk commonly attributed to Leonardo da Vinci (kept at the Turin Royal Library) ; this three-quarters face, about fifteen centimetres high, is generally presented as being that of Leonardo da Vinci, about sixty years old.

The second one [START_REF] Woodward | Biometrics : Look at Facial Recognition[END_REF], is extracted from a painting on a large canvas representing the 'Last Supper' (kept in a Luxembourg private collection); this three-quarters face, also about fifteen centimetres high, is that of the Apostle Thaddeus, whose fea-tures are presumed to be those of Leonardo da Vinci in his prime, i.e., about fifty years old (in terms of the 'Last Supper' fresco in Milan). The third one [START_REF] Ababsa | Authentification d'individus par reconnaissance de caractéristiques biométriques liées aux visages 2D/3D[END_REF], is extracted from a painting on a small panel of wood representing the 'Temptation of Saint Anthony', in the alchemical mode of the 'Great Work' (kept in a French private collection) ; this front face, only a few millimetres high, represents Saint-Anthony, 'the Great', alias 'the Egyptian'. Finally, the fourth one [START_REF] Liu | A practical guide to biometric security technology[END_REF], is extracted from a catalogue at the Windsor Castle Royal Library (RL 12300v ref.

). This three-quarters face, only a few centimetres high, is a pencil-and-ink drawing generally presented as being that of Leonardo da Vinci, about fifty years old, most likely executed by one of his studio students.

Our database was extracted from the basic free image data rights 'Google's license Creative Commons 3.0 Attribution'.

Including 51 drawn or painted faces, selected from almost twenty centuries of profane and sacred art, it broke down as follows:

-12 portraits of diverse and varied men, mostly self-portraits extracted from known profane works and absolutely authenticated as to the author, -23 portraits of men with beards, mainly extracted from sacred iconography, -13 portraits of diverse and varied women extracted from known profane works and absolutely authenticated as to the author.

The two images of 'unrecognized' faces to be identified [START_REF] Woodward | Biometrics : Look at Facial Recognition[END_REF] and [START_REF] Ababsa | Authentification d'individus par reconnaissance de caractéristiques biométriques liées aux visages 2D/3D[END_REF], and the two well-known presumed portraits of Leonardo da Vinci [1] and [START_REF] Liu | A practical guide to biometric security technology[END_REF], were as expected added to complement this database. At each test match, the image to be recognized was of course been removed from the database, except to set an expected score of 1.000. represented Saint-Anthony, 'the Great' alias 'the Egyptian'. The system then ranked in descending order all the paired scores obtained by these 51 'one to one' comparisons, (1:1) x 51 (Fig. 3). The first position was logically occupied by face image [1] of the red-chalk portrait commonly attributed to Leonardo da Vinci (Fig. 3 and5). The score was 0.466. The face image occupying the second position on the grid scored only 0.460. This consolidates face image [1] as the leading candidate to keep. It should also be noted that face image [START_REF] Woodward | Biometrics : Look at Facial Recognition[END_REF], which ranked 5th in the classification (Fig.

3), was a potential candidate too, but to a lesser extent in view of its 0.407 score. Face image [START_REF] Liu | A practical guide to biometric security technology[END_REF] ranked 13th with a 0.373 score even less significant. This result was exactly corroborated by the visual test match. Indeed, when our 85-person panel compared 'one to one' (1: 1) the four apparently similar faces which were the subject of the present study (Fig. 2), the classification set by eye also ranked the [3-1] pair at the first place with a 0.500 median score. The pair came in second, tied at 0.400 median score with the [START_REF] Ababsa | Authentification d'individus par reconnaissance de caractéristiques biométriques liées aux visages 2D/3D[END_REF][START_REF] Liu | A practical guide to biometric security technology[END_REF] pair.

The fourth and last test match carried out with artificial-intelligence software compared to the database (1:51) face image [START_REF] Liu | A practical guide to biometric security technology[END_REF] of the pencil-and-ink portrait generally presented as being that of Leonardo da Vinci. The system ranked in descending order all the paired scores obtained by these 51 'one to one' comparisons, (1:1) x 51. The first position was occupied by face image [1] of the red-chalk portrait commonly attributed to Leonardo da Vinci (Fig. 3). The score was 0.492. The face image occupying the second position on the grid scored only 0.462. This consolidates the face image [1] as the leading candidate to keep. It should also be noted that face image [START_REF] Woodward | Biometrics : Look at Facial Recognition[END_REF], which ranked 9th in the classification (Fig. 3), was a potential candidate too, but to a lesser extent in view of its 0.365 score. Face image [START_REF] Ababsa | Authentification d'individus par reconnaissance de caractéristiques biométriques liées aux visages 2D/3D[END_REF] ranked 16th with a 0.343 score even less significant. This result was not exactly corroborated by the visual test match. Indeed, when our 85-person panel compared 'one to one' (1: 1) the four apparently similar faces which were the subject of the present study (Fig. 2), the classification set by eye ranked this time the pair at the first place with a 0,600 median score. The [4-1] pair came in second, tied at 0.400 median score with the [4-3] pair.

Discussion

The first test match carried out with artificial-intelligence software, comparing to the database (1:51) face image [1] of the red-chalk portrait commonly attributed to Leonardo da Vinci, designates as leading candidate face image [START_REF] Woodward | Biometrics : Look at Facial Recognition[END_REF] of the Apostle Thaddeus painted portrait, whose features are presumed to be those of Leonardo da Vinci (Fig. 3 and4). It is corroborated by

Results of artificial-intelligence and visual test matches

The first test match carried out with artificial-intelligence software compared to the database (1:51) face image [1] of the red-chalk portrait commonly attributed to Leonardo da Vinci (Fig. 3). The biometric system tried to answer to the question: 'Who is represented on the face image [1]?'. This was a 'one-toall' test match (1:51), comparing the signature obtained from the characteristic data input for image [1] with those of the other 51 face images in its database. The system then ranked in descending order all the paired scores obtained by these 51 'one to one' comparisons, (1:1) x 51 (Fig. 3). The first position was occupied by face image [START_REF] Woodward | Biometrics : Look at Facial Recognition[END_REF] of the Apostle Thaddeus painted portrait, whose features are presumed to be those of Leonardo da Vinci (Fig. 3 and4). The score was 0.491. The face image occupying the second position on the grid scored only 0.453. This consolidated the position of face image [START_REF] Woodward | Biometrics : Look at Facial Recognition[END_REF] as the leading candidate to keep. It should also be noted that faces images [START_REF] Liu | A practical guide to biometric security technology[END_REF] and [START_REF] Ababsa | Authentification d'individus par reconnaissance de caractéristiques biométriques liées aux visages 2D/3D[END_REF] respectively ranked 11th and 14th, with 0.392 and 0.375 scores, clearly less significant. This result was exactly corroborated by the visual test match. Indeed, when our 85-person panel compared 'one to one' (1: 1) the four apparently similar faces which were the subject of the present study (Fig. 2), the classification set by eye also ranked the [1-2] pair at the first place, tied at 0.500 median score with the [1-3] pair .The [1-4] pair came in third with its 0.400 median score.

The second test match carried out with artificial-intelligence software compared to the database (1:51 ) face image [START_REF] Woodward | Biometrics : Look at Facial Recognition[END_REF] of the Apostle Thaddeus, whose features are presumed to be those of Leonardo da Vinci. The system ranked in descending order all the paired scores obtained by these 51 'one to one' comparisons, (1:1) x 51. The first position was logically occupied by face image [1] of the red-chalk portrait commonly attributed to Leonardo da Vinci (Fig. 3). The score was 0.488. The face image occupying the second position on the grid scored only 0.479. This consolidated the position of face image [1] as the leading candidate to keep. It should also be noted that face images [START_REF] Ababsa | Authentification d'individus par reconnaissance de caractéristiques biométriques liées aux visages 2D/3D[END_REF] and [START_REF] Liu | A practical guide to biometric security technology[END_REF] respectively ranked 12th and 19th, with 0.402 and 0.366 scores, clearly less significant. This result was not exactly corroborated by the visual test match. Indeed, when our 85-person panel compared 'one to one' (1: 1) the four apparently similar faces which were the subject of the present study (Fig. 2), the classification set by eye ranked this time the [START_REF] Woodward | Biometrics : Look at Facial Recognition[END_REF][START_REF] Ababsa | Authentification d'individus par reconnaissance de caractéristiques biométriques liées aux visages 2D/3D[END_REF][START_REF] Liu | A practical guide to biometric security technology[END_REF] pair at the first place with a 0.600 median score. The [2-1] and [START_REF] Woodward | Biometrics : Look at Facial Recognition[END_REF][START_REF] Ababsa | Authentification d'individus par reconnaissance de caractéristiques biométriques liées aux visages 2D/3D[END_REF] pairs occupied ranks 2 and 3 with respective 0,500 and 0,400 median scores.

The third test match carried out with artificial-intelligence software compared to the database (1:51 ) the face image [START_REF] Ababsa | Authentification d'individus par reconnaissance de caractéristiques biométriques liées aux visages 2D/3D[END_REF] that was notice that the features of this 'Saint-Anthony-like' face have nothing to do with the emaciated one's we would expect to find on the face of a hermit ; rather, much more with those of the face of a healthy monk, somewhat chubby. It takes more than 20 x magnification to realize, not only the actual account dexterity of the artist and the extreme precision of his touch, but also the resemblance of this face with that of presumed portraits of Leonardo da Vinci. The result of the third test match carried out with artificial-intelligence software, comparing to the database (1:51) to face image [START_REF] Ababsa | Authentification d'individus par reconnaissance de caractéristiques biométriques liées aux visages 2D/3D[END_REF], designates as the leading candidate the face image [1] of the red-chalk portrait commonly attributed to Leonardo da Vinci. It is corroborated by the visual test match (1: 1) that ranks the [3, 1] pair at the first place. If tried that the red-chalk portrait kept at the Turin Royal Library [1] would be a self-portrait of Leonardo da Vinci, this study allows to emit the incredible assumption that Leonardo da Vinci himself would be portrayed in the guise of the famous 'father of hermits' in this painting representing the 'Temptation of Saint Anthony', in the alchemical mode of the 'Great Work'. The hypothesis is also supported by another pictorial detail of that this painting : an 'anthropomorphic landscape' whose profile recalls precisely the features of the same red-chalk portrait [1] commonly attributed to Leonardo da Vinci (Fig. 6). Anyway, the results of the present study significantly shows that face image [START_REF] Ababsa | Authentification d'individus par reconnaissance de caractéristiques biométriques liées aux visages 2D/3D[END_REF] and [1] would be portraits of the same personality. Ultimately, this study was able to affirmatively answer to the original question, namely : 'Using artificial-intelligence tools, is it possible to measure objectively similarities observed subjectively by human eye between faces in graphic works using different pictorial techniques?' The consistency of the test-matches results obtained using the NeoFace © Watch artificial-intelligence software and those obtained using the human ocular and brain neural network can position this software as a necessary tool for facial recognition applied to separate graphic works made of different pictorial techniques. Beyond this scientific aspect, if tried that the red-chalk portrait kept at the Turin Royal Library [1] would be a self-portrait of Leonardo da Vinci, as regards the two 'unrecognized' face images [START_REF] Woodward | Biometrics : Look at Facial Recognition[END_REF][START_REF] Ababsa | Authentification d'individus par reconnaissance de caractéristiques biométriques liées aux visages 2D/3D[END_REF], this study can allow to affirm that they would also be that of Leonardo da Vinci. Anyway, the results of the present study significantly shows that these two face images would be portraits of the same personality as that shown in the red-chalk portrait kept at the the visual test match (1: 1) that ranks the [1, 2] pair at the first place. Finally, it is consolidated by the second test match carried out with artificial-intelligence software, which compared to the database (1:51) face image [START_REF] Woodward | Biometrics : Look at Facial Recognition[END_REF] of the Apostle Thaddeus, that logically designates as leading candidate the above mentioned face image [1] of the red-chalk portrait commonly attributed to Leonardo da Vinci (Fig. 3). The inversion in the classification for 2 and 3 ranks between the artificial-intelligence software and the visual test matches may be explained by a large difference of processing and finishing, which is superimposed that of an age gate of about ten years, between the two face images [1] and [START_REF] Liu | A practical guide to biometric security technology[END_REF]. The nonexpert eye of everyone is not necessarily able to integrate these parameters, unlike the intrinsic performances of the facial-recognition software. If tried that the red-chalk portrait kept at the Turin Royal Library [1] would be a self-portrait of Leonardo da Vinci, this study supports the hypothesis that the face of the Apostle Thaddeus character depicted in this version of the 'Last Supper' would also be that of Leonardo da Vinci. Anyway, it significantly confirms that face image [1] and [START_REF] Woodward | Biometrics : Look at Facial Recognition[END_REF] would be portraits of the same personality. Furthermore, the present study opens the debate on whether the face image [START_REF] Woodward | Biometrics : Look at Facial Recognition[END_REF] of the Apostle Thaddeus extracted from this painting on large canvas representing the 'Last Supper' could be the hand of Leonardo da Vinci himself, or that of one of his studio students, after a lost original of his Florentine master. The fourth test match carried out with software artificial-intelligence, comparing to the database (1:51) face image [START_REF] Liu | A practical guide to biometric security technology[END_REF] of the pencil-and-ink portrait generally presented as being that of Leonardo da Vinci, designates as leading candidate face image [1] of the red-chalk portrait commonly attributed to Leonardo da Vinci. The ranking shift between artificial-intelligence software and visual test matches may again be explained by a large difference of processing and finishing, which is superimposed that of an age gate of about ten years, between the two faces images [1] and [START_REF] Liu | A practical guide to biometric security technology[END_REF]. As mentioned above, everyone nonexpert eye is not necessarily able to integrate these parameters, unlike the intrinsic performances of the facial recognition software. If tried that the red-chalk portrait kept at the Turin Royal Library [1] would be a self-portrait of Leonardo da Vinci, this study confirms the hypothesis that the pencil-and-ink face of the character extracted from a catalogue at the Windsor Castle Royal Library (RL 12300v ref.

) would also be that of Leonardo da Vinci. Anyway, it significantly confirms that face image [1] and [START_REF] Liu | A practical guide to biometric security technology[END_REF] would be portraits of the same personality. The result of the third test match carried out with artificial-intelligence software, comparing to the database (1:51) face image [START_REF] Ababsa | Authentification d'individus par reconnaissance de caractéristiques biométriques liées aux visages 2D/3D[END_REF] of the Saint-Anthony character extracted from a painting representing the 'Temptation of Saint Anthony', is paradoxically not the most surprising, although the perspectives it offers are the most incredible and even more dizzying in their layout and possible reading. Nothing in this painted face, only a few millimetres high, would at first glance let the average viewer glimpse or even imagine any resemblance with that of any presumed portrait of Leonardo da Vinci. Neither at first glance, nor the following. Even the more discerning eye cannot distinguish this 'Saint-Anthony-like' miniature portrait from its archetypal 'father of hermits' representation, as it typically appears in profane or sacred iconography. Only an 'absolute eye' might Turin Royal Library. The result that raised the most questions was undoubtedly one obtained for the face image [START_REF] Ababsa | Authentification d'individus par reconnaissance de caractéristiques biométriques liées aux visages 2D/3D[END_REF] extracted from a painting on a small panel of wood representing the 'Temptation of Saint Anthony', in the alchemical mode of the 'Great Work'. If tried that the red-chalk portrait kept at the Turin Royal Library [1] would be a self-portrait of Leonardo da Vinci, why was the Florentine master this time represented in these amazing appearances and staged in such a theatrical manner? Perhaps, to agree with Giorgio Vasari when he wrote in the first version of his 'Life of painters' that Leonardo da Vinci had 'developed in his mind such an heretical doctrine that he was no longer dependent of any religion, maybe more preferring to be a philosopher rather than a Christian'. Finally, in the case of authentication, who could have created such an explicit esoteric alchemical 'manifesto'? Leonardo da Vinci himself? Or a disciple from his near or distant surroundings? Someone who wanted -through this painted panel of the 'Great Work' -to pay tribute in the form of posterity testimony to Leonardo da Vinci's sacred way for 'insiders', that is a heretical way for the others?

The controversy is reopened.

SUMMARY OF METHOD

The four apparently similar faces extracted from separate graphic works which were the subject of the present study, were submitted to the identification test (1:N) of the NeoFace © Watch facial-recognition software developed by NEC corporation. Performing at a rate of only 4.1% failure for facial recognition in a database of 1.6 million images, this software is currently considered the most accurate of its type on the market, especially for its success with low-quality images. The facial-recognition software NeoFace © Watch is based on a generalized learning vector quantization (GLVQ) algorithm type 5 . We established a database of 51 drawn or painted faces, selected from almost twenty centuries of profane and sacred art (extracted from the basic free image data rights 'Google's license Creative Commons 3.0 Attribution'), to enable the biometric system to identify (1:N) the four apparently similar faces which were the subject of the present study. For drawn or painted portraits (these being 'interpreted faces', opposed to -strictly speaking -'real faces' of photographed portraits), a score of about 0.450 can be considered significant. To validate the results of these identification tests (1:51), we submitted the same four faces in parallel to control tests (1:1) by an 85-person panel. For drawn or painted portraits (these being 'interpreted faces', opposed to -strictly speaking -'real faces' of photographed portraits), moreover being identified by nonexpert eyes, a score around 0.450 was also considered significant.

Figure 2 |

 2 Figure 2 | The four apparently similar faces which were the subject of the present study. 1, Presumed 'Self-portrait of Leonardo da Vinci' (Turin -Italy). 2, The Apostle Thaddeus from the 'Last Supper' (Luxembourg). 3, Saint-Anthony from the 'Temptation of Saint Anthony' (France). 4, Presumed 'Portrait of Leonardo da Vinci' (Winsor Castle -UK).

Figure 3 |

 3 Figure 3 | The four grids of test matches results (1:51) ranked in descending order of scores, from up to bottom and from left to right, by NeoFace © Watch software. On the light blue sidelines, top and right of each of the four grids, the face to be recognized. In the top left of each grid, the leading candidate of the test match ranked by the software.

Figure 5 |

 5 Figure 5 | Result of the third artificial-intelligence test match (Fig. 3), comparing face image [3] to the rest of the database (1:51). On the right, the leading candidate [1] ranked by the NeoFace © Watch software.

Figure 4 |

 4 Figure 4 | Result of the first artificial-intelligence test match (Fig. 3), comparing face image [1] to the rest of the database (1:51). On the right, the leading candidate [2] ranked by the NeoFace © Watch software.

Figure 6 |

 6 Figure 6 | Anthropomorphic landscape : On the right, the 'Leonardo-like' profile of the 'Temptation of Saint Anthony', from which is also extracted face image [3] of this study (Fig. 2). On the left, the red-shark portrait commonly attributed to Leonardo da Vinci [1].

  1. Boujellal S. 'Détection et identification de personnes par méthode biométrique', mémoire de Magister en Électronique, option Télédétection. Faculté de génie électrique et d'informatique, Université Mouloud Mammeri de Tizi-Ouzou (RADP, 2015).


Steve Lawford
email: steve.lawford@enac.fr.

Yll Mehmeti

Cliques and a New Measure of Clustering: with Application to U.S. Domestic Airlines *

Keywords: Airline network, Clique, Clustering, Graph theory, Subgraph

We propose a natural generalization of the well-known clustering coefficient for triples C(3) to any number of nodes. We give analytic formulae for the special cases of three, four, and five nodes and show, using data on U.S. airline networks, that they have very fast runtime performance. We discuss some theoretical properties and inherent limitations of the new measure, and use it to provide insight into changes in network structure over time.

Introduction

Networks are ubiquitous in social and economic settings. Recent examples of their empirical application include Banerjee et al. [START_REF] Banerjee | The diffusion of microfinance[END_REF], Faris and Felmlee [START_REF] Faris | Status struggles: Network centrality and gender segregation in same-and cross-gender aggression[END_REF], Jackson [START_REF] Jackson | Networks in the understanding of economic behaviors[END_REF] (social networks), Akbas et al. [START_REF] Akbas | Director networks and informed traders[END_REF], Cohen-Cole et al. [START_REF] Cohen-Cole | Trading networks and liquidity provision[END_REF], El-Khatib et al. [START_REF] El-Khatib | CEO network centrality and merger performance[END_REF], Hochberg et al. [START_REF] Hochberg | Whom you know matters: Venture capital networks and investment performance[END_REF], Robinson and Stuart [START_REF] Robinson | Network effects in the governance of strategic alliances[END_REF] (financial networks), and Aguirregabiria and Ho [START_REF] Aguirregabiria | A dynamic oligopoly game of the US airline industry: Estimation and policy experiments[END_REF], Baumgarten et al. [START_REF] Baumgarten | The impact of hubbing concentration on flight delays within airline networks: An empirical analysis of the US domestic market[END_REF], Guimerà et al. [START_REF] Guimerà | The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles[END_REF], Lin and Ban [START_REF] Lin | The evolving network structure of US airline system during 1990-2010[END_REF], Lordan et al. [START_REF] Lordan | Study of the topology and robustness of airline route networks from the complex network approach: a survey and research agenda[END_REF], Ryczkowski et al. [START_REF] Ryczkowski | How transfer flights shape the structure of the airline network[END_REF], Verma et al. [START_REF] Verma | Revealing the structure of the world airline network[END_REF] and Wuellner et al. [START_REF] Wuellner | Resilience and rewiring of the passenger airline networks in the United States[END_REF] (transportation networks). These papers formalize real-world interactions -such as information transfer links between firms, or physical air travel routes between airports -using the tools of graph theory. Typically, they report a selection of summary statistics to capture particular global or local aspects of the network, including its density, distribution of node centrality, and clustering. These measures can provide insight into network structure and dynamics, that would not be available from using other methods. Clustering is especially important in economic and social networks, and captures the extent to which an individual's contacts are themselves linked. There is evidence that a high level of clustering is related to cooperative social behaviour and beneficial information and reputation transfer, and that many real-world networks exhibit higher clustering than if links were formed at random (e.g. Newman [START_REF] Newman | The structure and function of complex networks[END_REF], Jackson [START_REF] Jackson | Social and Economic Networks[END_REF][START_REF] Jackson | Networks in the understanding of economic behaviors[END_REF] and references therein).

One widely used measure of clustering in a network (graph) is the overall clustering coefficient which is defined in Newman [21, equation (3.3)] as, in our notation,

C(3) =
3 × number of triangles in the network number of connected triples of vertices ,

where a connected triple is a set of three distinct nodes u, v and w, such that at least two of the possible edges between them exist. In other words, how often are an individual's friends also friends with one another, on average, across the entire network? Since C(3) is based upon connected triples of nodes, it is natural to ask whether a similar measure can be derived for any number of nodes. In this paper, we make the following specific contributions:

• We propose a new generalized clustering coefficient C(b), based upon connected groups of b nodes, which nests the standard clustering coefficient C(3). We develop a very fast analytic implementation for connected groups of three, four and five nodes, that we show to be up to 2,000 times faster than a naïve nested loop algorithm, for some small dense graphs.

• We examine some theoretical properties of C(b) and show that it will become prohibitively difficult to compute C(b) efficiently as b increases, even using analytic formulae, since these will become too cumbersome to derive. Using data on U.S. airline networks over time, we also show that C(b) can be highly correlated across b, and with network density, which may reduce its practical benefits on some datasets of interest. It is not yet known whether this high correlation holds generally for large classes of networks.

All analytic formulae that we use, and several proofs, are collected in Appendix A, and a supporting table of correlation coefficients and additional figures are reported in Appendix B.

Graph Theory and Clustering

We briefly review some relevant tools of graph theory. Important monographs include Diestel [START_REF] Diestel | Graph Theory[END_REF] (mathematics), Jackson [START_REF] Jackson | Social and Economic Networks[END_REF] (economics of social networks) and Jungnickel [START_REF] Jungnickel | Graphs, Networks and Algorithms[END_REF] (algorithms). A graph is an ordered pair G = (V, E) where V and E denote the sets of nodes and edges of G, respectively. We use n = |V | and m = |E| to represent the numbers of nodes and edges of G. A graph has an associated n × n adjacency matrix g, with representative element (g) i j that takes value one when an edge is present between nodes i and j, and zero otherwise. We also use (i, j) ∈ E to denote an edge between nodes i and j, and say that they are directly-connected. A graph is simple and unweighted if (g) ii = 0 (no self-links) and (g) i j ∈ {0, 1} (no pair of nodes is linked by more than one edge, or by an edge with a weight that is different from one). A graph is undirected if (g) i j = (g) ji . A walk between nodes i and j is a sequence of edges {(i r , i r+1 )} r=1,...,R such that i 1 = i and i R+1 = j, and a path is a walk with distinct nodes. A graph is connected if there is a path between any pair of nodes i and j. In this paper, we consider simple, unweighted, undirected and connected graphs. The degree k i = ∑ j (g) i j is the number of nodes that are directly-connected to node i, and the (1-degree) neighbourhood of node i in G, denoted by Γ G (i) = { j : (i, j) ∈ E}, is the set of all nodes that are directly-connected to i. The density d(G) = 2m/n(n -1) is the number of edges in G relative to the maximum possible number of edges in a graph with n nodes. A graph

G = (V , E ) is a subgraph of G if V ⊆ V and E ⊆ E where (i, j) ∈ E implies that i, j ∈ V .
A spanning tree on G is a connected subgraph with nodes V and the minimum possible number of edges m = n -1. A complete graph on n nodes, K n , has all possible edges, and a complete subgraph on b nodes is called a b-clique. A maximal clique is a clique that cannot be made larger by the addition of another node in G with its associated edges, while preserving the complete-connectivity of the clique. A maximum clique is a (maximal) clique of the largest possible size in G, and the clique number w(G) of the graph G is the number of nodes in a maximum clique in G. Let G(n, p) be an Erdős-Rényi random graph with nodes V = {1, . . . , n} and edges that arise independently with constant probability p. Using the notation of Agasse-Duval and Lawford [START_REF] Agasse-Duval | Subgraphs and motifs in a dynamic airline network[END_REF], we refer to particular topological subgraphs by

M (b)
a , where b is the number of nodes in the subgraph, and a is the decimal representation of the smallest binary number derived from a row-by-row reading of the upper triangles of each adjacency matrix g from the set of all topologically-identical subgraphs on the same b nodes.

Analytic formulae for a generalized clustering coefficient

The clustering coefficient C(3) is bounded by 0 ≤ C(3) ≤ 1, attaining the minimum when there are no triangles in the graph, and taking the maximum value for a complete graph K n . Since each triangle contains three triples of nodes, a factor of three appears in the numerator of [START_REF] Agasse-Duval | Subgraphs and motifs in a dynamic airline network[END_REF]. A naïve algorithm based on nested loops, that considers every distinct triple of nodes in G, will run in O(n 3 ) time. However, it is easy to write down an analytic version of C(3), using the nested subgraph enumeration formulae in Agasse-Duval and Lawford [1, equations ( 1) and ( 2)]:

C(3) = 3 |M (3) 7 | |M (3) 3 | = tr(g 3 ) ∑ i k i (k i -1) , (2)
and where C(3) makes explicit the definition of clustering in terms of triples M

(3)

3 and triangles M

(3)

7 . If we instead interpret (2) as the average probability that any three connected nodes in a graph are also completelyconnected, then a natural generalization follows to any number b of nodes, such that 3 ≤ b ≤ n. We define the generalized clustering coefficient as follows: A naïve algorithm for (3), based on nested loops, will run in O(n b ) time. For example, the denominator of (3) can be calculated by considering every distinct set of b nodes in G, and counting the number of spanning trees on each subgraph. This will be excessively slow. If we instead think of C(b) as a measure of the prevalence of b-cliques relative to all connected groups of b nodes, then it is clear that we can use analytic subgraph enumeration for counting the cliques and the spanning trees for the special cases C(4) and C(5), in the same way as for (2):

C(b) = a(b) × number of b-cliques in G number of b-spanning trees in G , (3)
C(4) = 16 |M (4) 63 | |M (4) 11 | + |M (4) 13 | = 4 ∑ i tr(g 3 -i ) ∑ i k i (k i -1)(k i -2) + 6 ∑ (i, j)∈E (k i -1)(k j -1) -3 tr(g 3 )
.

(4)

C(5) = 125 |M (5) 1023 | |M (5) 75 | + |M (5) 77 | + |M (5) 86 | = 25 ∑ i ∑ j∈Γ G (i) tr(((g -i ) -j ) 3 ) ∑ i k i (k i -1){(k i -2)(k i -15) -24} + 12 ∑ (i, j)∈E (k i -1)(k i + k j -8)(k j -1) -48 ∑ k i >2 (g 3 ) ii (k i -2) + 12 ∑ i = j (g 4 ) i j -12 tr(g 3 )
.

(

) 5
The numerator terms |M 86 |), which are illustrated in Figures 1 and2. Since there are sixteen possible spanning trees on any given four nodes in the graph, all of which will occur in K 4 , the factor a(4) equals 16. Similarly, counting the distinct 5-spanning trees in K 5 gives a(5) equal to 125. However, while this approach seems promising, it will rapidly become too cumbersome to derive analytic formulae for larger values of b, because the number of denominator terms explodes. Essentially, we would need to find a formula for every non-isomorphic tree on b nodes. For example, C(6) would require evaluation of six denominator terms (Figure 3). Numerical values are given as series A000055 in the Online Encyclopedia of Integer Sequences ( http://oeis.org/A000055 ). For example, C(7) has 11 denominator terms, C(8) has 23 denominator terms, and C(36) has more than 6.2 × 10 12 terms! This creates an intrinsic bound on the general applicability of analytic formulae for C(b): we can reasonably expect to use them for C(3), C(4), C(5) and perhaps C(6), but not beyond. 1 3 Data and Results

To illustrate the behaviour of C(b), we construct quarterly networks for eight airline carriers over the period 1999Q1 to 2013Q4, using publicly-available data from the U.S. Department of Transportation's DB1B Airline Origin and Destination survey and T-100 Domestic Segment (All Carriers) census. 2 The DB1B is a 10% random sample of quarterly ticket-level itineraries, collected from reporting carriers. The T-100 is a monthly 100% census on domestic nonstop flight segments, including number of enplaned passengers and available capacity. Both datasets have been widely used in empirical work in economics e.g. Aguirregabiria and Ho [START_REF] Aguirregabiria | A dynamic oligopoly game of the US airline industry: Estimation and policy experiments[END_REF], Ciliberto and Tamer [START_REF] Ciliberto | Market structure and multiple equilibria in airline markets[END_REF], Dai et al. [START_REF] Dai | Is the effect of competition on price dispersion non-monotonic? Evidence from the U.S. airline industry[END_REF]. We do not observe the actual date of flight or purchase, ticket restrictions, or the buyer's characteristics. We merge the DB1B and T-100, retaining all scheduled nonstop round-trip tickets, for domestic carriers, between airports in the continental U.S. We do not keep tickets that were sold under a codesharing agreement, that have unusually high or low fares, or that are considered unreliable by the data provider. Some carriers (e.g. JetBlue Airways and Southwest Airlines) report large numbers of business and first class tickets. We only use coach class tickets, unless more than 75% of a carrier's tickets are listed as business or first class, in which case we keep all tickets for that carrier. Individual tickets are then aggregated to non-directional route-carrier observations. We omit route-carriers with an especially low number of passengers, that do not have a constant number of passengers on each segment, or that are not present over the full sample period. In building the route networks, a node is an airport that was served as a route origin or destination, and an edge is present if some passengers travelled on a direct route between two nodes, for a given carrier-quarter. Our eight empirical networks are connected in every quarter of the sample. Further details of the data treatment are available from the authors.

Since C(b) is intimately related to the relative number of cliques, we start by using the Bron-Kerbosch algorithm to identify all cliques in a given network. Figure 4 displays the 2013Q4 network of Southwest Airlines, and highlights one maximal 4-clique, between Albuquerque, Dallas, Houston, and Kansas City. It is interesting to see how many maximal cliques of any given size there are in a network, and whether this distribution is stable over time. We illustrate using Southwest's network, in Figure 5, which shows that the distribution is more spread out, and that more larger cliques appear, over time. There is a maximum clique size of eleven, which corresponds to 12.5% of all of the airports served by Southwest in 2013Q4. This might seem surprising, given that Southwest's network is relatively sparse, with a density d(G) equal to 15% in that quarter. Since every airport in the maximum clique has at least 11 connections, we can think of it as a group of "important" airports, that are also very highly connected among themselves. 3 An operational reason for developing such groups could be to enable the opening of a large number of new indirect routes between airport pairs, at relatively low cost, with the addition of a few well-chosen direct routes. It seems likely that Southwest, through its network expansion, has focused both on increasing the size and connectivity of a moderate number of "core" airports while also creating links from non-core airports into the core. are given in A161680 of the OEIS ( http://oeis.org/A161680 ). 2 The carriers are American Airlines (AA), Alaska Airlines (AS), Delta Air Lines (DL), AirTran Airways (FL), Spirit Airlines (NK), United Airlines (UA), US Airways (US), and Southwest Airlines (WN). 3 We find evidence that nodes that belong to maximal cliques in Southwest's network are more connected, on average, than nodes that are not in maximal cliques, and that the average degree of nodes in maximal cliques increases in the order of the clique (Figure B.2). 4 Not all networks evolve in this way e.g. the distribution of maximal cliques for American (AA) is far more stable over time (Figure B.3). Since there are a substantial number of cliques with more than three nodes, we examine how C(3), C(4) and C(5) vary across carriers, and over time (Figure 8). We make the following remarks:

• There is considerable heterogeneity across carriers. For instance, Southwest has quite a stable C(3) over 1999Q1 to 2013Q4, despite its significant expansion in terms of airports and routes. On the other hand, United has far more clustering (in triangles) from 2009 onwards, while Alaska has progressively less.

• Generalized clustering C(b) is highly positively correlated across b, for some networks e.g. Delta, and is also positively correlated with network density (see Table 1 in Appendix B). Some of this follows by construction e.g. for every newly formed 4-clique in a network, there will be between two and four new 3-cliques, while every newly formed 5-clique will create between two and five new 4-cliques and between three and ten new 3-cliques. High correlation reduces the information-content of C(4) and C( 5), but it is unclear whether this result holds for most classes of network, or if airline networks are in fact a special case. In order to control for this correlation, we might consider performing the following regressions: C(4) = constant + β C(3) + error and C(5) = constant + β C(3) + γ C(4) + error, and using the residuals rather than C(4) and C(5) themselves. 5• There is some evidence that C(3) > C(4) > C(5), and we might think that this holds for all graphs. However, we were able to construct a series of (pathological) counterexamples.

The general rule behind the construction is as follows: we create a complete K b subgraph and then build a "chain" of nb nodes attached to one of the nodes in K b . As n increases, the number of complete subgraphs of order no more than b does not change (for instance, there are four triangles and one 4-complete subgraph in Figure 6). Furthermore, increasing n after a certain point will only add paths of length b to the denominator of C(b), and no other spanning trees (e.g. b-stars). It is easy to show that

C(3) = 12 n + 10 ; n ≥ 5; C(4) = 16 n + 22 ; n ≥ 6, (6)
from which C(3) ≥ C(4) as n ≤ 26, with equality when C(3) = C(4) = 1 3 . In Figure 7, the number of 4-complete and 5-complete subgraphs is constant as n increases. Beyond a certain point, only 4-paths and 5-paths are added to the denominators of C(4) and C(5) and no further 4-stars or 5-stars or 5-arrows are created. We can show that To end, we simulated the actual runtimes of the analytic formulae for C(b) for b = 3, 4, 5, on dense Erdős-Rényi graphs G(n, 0.9), and compared these with the runtimes of a simple nested loop implementation. We are able to show that the theoretical asymptotic runtime of each of the analytic clustering formulae is lower than that of the nested loops. 6 However, the small-sample runtime is much lower when analytics are used (Figure 9): the analytic algorithm is roughly 2,000 times faster for C(3) and more than 500 times faster for C(4) and C(5) for the dense G(n, p). While analytic runtime gains are lower for sparse G(n, p), they remain very substantial, and this contributes to making these generalized clustering coefficients a practical tool.

C(4) = 80 n + 95 ; n ≥ 7; C(5) = 125 n + 203 ; n ≥ 8, (7)

Conclusions

We have examined the nature and dynamics of topological cliques in real-world airline networks. We propose a fast generalized clustering coefficient C(b), that can be readily implemented for b = 3, 4, 5. Despite some apparent drawbacks, including the difficulty of deriving higher order C(b), and high correlation across different values of b, the new measure can potentially provide insight regarding larger (than triangle) groups of completely-connected nodes in a network. More generally, analytic formulae for subgraph enumeration might have application to other statistics that are commonly used in applied graph theory. Future work linking graphs and econometrics should also lead to a better understanding of the economic, strategic and spatial factors that drive dynamic clustering in real-world networks. Proof of Proposition 2.1. We consider the "if" and "only if" parts separately:

• (if) Let G be

where

  Cayley's formula a(b) = b b-2 gives the number of spanning trees in K b , and ensures that 0 ≤ C(b) ≤ 1. Clearly, C(b) nests C(3), and equals zero if and only if there are no b-cliques in the graph. Moreover, we show: Proposition 2.1. Let G be a connected graph with at least b nodes (b ≥ 3). Then C(b) = 1 if and only if G is complete.

( 4 )

 4 63 | and |M(5) 1023 | are the number of 4-cliques and 5-cliques respectively. The denominator terms are the counts of the 4-star (|M (4) 11 |), the 4-path (|M (4) 13 |), the 5-star (|M (5) 75 |), the 5-arrow (|M (5) 77 |), and the 5-path (|M (5)

Figure 1 :

 1 Figure 1: The sixteen spanning trees on four labelled nodes: four 4-stars M (4) 11 and twelve 4-paths M (4) 13 .

Figure 2 :

 2 Figure 2: A selection of 5-node undirected connected subgraphs.

Figure 3 :

 3 Figure 3: The six non-isomorphic trees on six nodes.

4

 4

1

  In the special case of G(n, p), it follows directly from (3) that C(b) = p (b-1)(b-2)/2 in expectation, since there are n b p ( b 2 ) b-cliques and b b-2 n b p b-1 b-spanning trees in G(n, p). Numerical values of b-1 2

Figure 4 :

 4 Figure 4: The Albuquerque-Dallas-Houston-Kansas City maximal 4-clique in Southwest's network.

Figure 5 :

 5 Figure 5: The distribution of maximal k-cliques in Southwest's network, in 1999Q1, 2004Q2, 2009Q3 and 2013Q4.

Figure 6 :

 6 Figure 6: Counterexample for C(3) ≥ C(4).

Figure 7 :

 7 Figure 7: Counterexample for C(4) ≥ C(5).

( a )

 a Southwest Airlines. (b) American Airlines. (c) US Airways. (d) United Airlines.(e) Spirit Airlines.(f) AirTran Airways.(g) Alaska Airlines.(h) Delta Air Lines.

Figure 8 :

 8 Figure 8: The dynamic behaviour of C(3), C(4), C(5) and density from 1999Q1 to 2013Q4.

  (a) C(3).(b) C(4).

  (c) C(5).

Figure 9 :

 9 Figure 9: Runtimes, in seconds, of C(3), C(4) and C(5) analytic and nested loop algorithms, computed over 100 (or 20 for C(4) and C(5)) replications of dense Erdős-Rényi graphs G(n, 0.9), where we only retain connected graphs.

  complete. Hence, each set of b nodes of G forms a b-clique and G contains exactly n b b-cliques. The number of b-spanning trees of G is equal to the number of b-spanning trees enclosed in any b-clique which is, using Cayley's formula: b b-2 × n b , from which (3) gives C(b) = 1. • (only if) We prove this part by contrapositive. Suppose that G is not complete. Since G has at least b nodes, we can find a connected subgraph G of G with b nodes such that G is not a b-clique, and we can extract a b-spanning tree from G by removing any cycles. Hence, there is at least one b-spanning tree in G which is not enclosed in a b-clique. It follows that: number of b-spanning trees in G ≥ number of b-spanning trees enclosed in a b-clique + 1 > number of b-spanning trees enclosed in a b-clique = b b-2 × number of b-cliques in G, and so C(b) < 1 from (3), which proves the proposition.

Figure B. 1 :

 1 Figure B.1: Regression of C(4) on a constant and C(3) , where the star notation indicates that both coefficients have been corrected so that they are difference and trend stationary, before performing the regression (see footnote 5).

Figure B. 2 :

 2 Figure B.2: The mean (black line), median (green line), minimum (blue circle) and maximum (red triangle) degree of nodes that belong to maximal cliques of order k, in Southwest's 2013Q4 network. For comparison, we plot the mean (black dashed line) and median (green dashed line) degree of all nodes in the network. Values in parentheses are the total number of maximal cliques of order k in the network.

Figure B. 3 :

 3 Figure B.3: The distribution of maximal k-cliques in American's network, in 1999Q1, 2004Q2, 2009Q3 and 2013Q4.

We illustrate the C(4) procedure in FigureB.1, for US Airways and Southwest (WN). Since C(3) and C(4) display evidence of a unit root (US) and a unit root and trend (WN), we first run regressions of the form ∆C(b) t = α + δ t + u(b) t , for b = 3, 4. We then regress the difference and trend stationary u(4) on a constant and u(3), and find that 76% (US) and 89% (WN) of the variation in C(4) is "explained" by C(3). In this sense, C(4) is moderately informative once C(3) has been accounted for. It is unclear if other networks will give similar results.

The worst-case theoretical runtime of a nested loop implementation of C(b) is O(n b ), since there are b nested loops. In a very sparse graph, the actual runtime of nested loops can be much faster, and coding shortcuts can take advantage of the fact that not every b-tuple needs to be considered. Directly from (2), (4) and (5), we can see that the numerator will dominate the asymptotic runtime of the analytic formulae. We find that C(3) is O(n ω ), C(4) is O(n ω+1 ), and C(5) is O(n ω+2 ), where ω is the exponent of matrix multiplication, for which current implementations give 2.38 ≤ ω ≤ 3. The very fast matrix multiplication algorithms due to Coppersmith and Winograd[START_REF] Coppersmith | Matrix multiplication via arithmetic progressions[END_REF] and Vassilevska Williams[START_REF] Williams | Multiplying matrices in O(n 2.373 ) time[END_REF] both have ω ≈ 2.38, the well-known algorithm due to Strassen[START_REF] Strassen | Gaussian elimination is not optimal[END_REF] has ω ≈ 2.81, and a naïve algorithm has ω = 3.

A Proofs

Derivations for the 3-star M For completeness, we repeat the results here, without proof, in Proposition A.1. We also include the three spanning trees on five nodes: the 5-star M [START_REF] Baumgarten | The impact of hubbing concentration on flight delays within airline networks: An empirical analysis of the US domestic market[END_REF] 75 , the 5-arrow M [START_REF] Baumgarten | The impact of hubbing concentration on flight delays within airline networks: An empirical analysis of the US domestic market[END_REF] 77 and the 5-path M [START_REF] Baumgarten | The impact of hubbing concentration on flight delays within airline networks: An empirical analysis of the US domestic market[END_REF] 86 , as well as the 5-complete M [START_REF] Baumgarten | The impact of hubbing concentration on flight delays within airline networks: An empirical analysis of the US domestic market[END_REF] 1023 , all with their corresponding proofs. Proposition A.1 (Analytic formulae for nested subgraph enumeration).

|M

(3)

|M

(3)

|M (4)

|M

(4)

|M

(4)

|M

(5)

|M

(5)

|M

(5)

|M

(5)

Remark A.1. In (13), g -i is the adjacency matrix corresponding to the subgraph induced by the neighbourhood Γ G (i) of i, which we denote by

), and we use [START_REF] Dai | Is the effect of competition on price dispersion non-monotonic? Evidence from the U.S. airline industry[END_REF] to count the number of triangles.

Remark A.2. In [START_REF] Jackson | Social and Economic Networks[END_REF], ∑ (i, j) * ∈E denotes summation over all edges in E, in both directions (i, j) and ( j, i).

Remark A.3. In ( 17), (g -i ) -j is the adjacency matrix corresponding to the subgraph induced by the neighbourhood Γ G-i ( j) of j, which we denote by

), and we use [START_REF] Guimerà | The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles[END_REF] to count the number of 4-cliques. 13 | in Agasse-Duval and Lawford [START_REF] Agasse-Duval | Subgraphs and motifs in a dynamic airline network[END_REF]. Consider any edge (i, j) ∈ E, as the central edge in a 5-arrow. Let i and j have degrees three and two respectively, and let node i be directly-connected to nodes x and z, and let node j be directly-connected to node y. Node i has k i -1 possible neighbours (for nodes x and z) and node j has k j -1 possible neighbours (for node y). There are 1 2 (k i -1)(k i -2)(k j -1) ways in which two neighbours of i can be paired with a neighbour of j, which gives a total of ∑ (i, j) ∈E k i -1 2 (k j -1) across all possible central edges, in both directions (we use (i, j) to denote "(i, j) and ( j, i)"). This sum includes the unwanted cases x = y and x = z, both of which form a tadpole. Since two of the four edges of the tadpole can be a candidate central edge (i, j) of a 5-arrow, we subtract 2 |M 86 |: A very similar but less transparent proof can be found in Movarraei and Shikare [START_REF] Movarraei | On the number of paths of lengths 3 and 4 in a graph[END_REF]. A 5-path is a walk of length 4 with no repeated nodes. Note that 1 2 ∑ i = j (g 4 ) i j gives the number of walks of length 4 from i to j, which does not only include 5-paths. There are five subgraphs in which we can find walks of length 4 that are not 5-paths: 63 comprised of nodes j, k, l and m. Let each node be in the neighbourhood Γ G (i) of some node i such that i = j = k = l = m. Hence, the five nodes i, j, k, l and m, and the edges between them, form a 5-complete subgraph M [START_REF] Baumgarten | The impact of hubbing concentration on flight delays within airline networks: An empirical analysis of the US domestic market[END_REF] 1023 . The quantity |M [START_REF] Banerjee | The diffusion of microfinance[END_REF] 63 (g -i )| gives the number of 5-complete subgraphs that contain node i, where g -i is the adjacency matrix corresponding to the subgraph induced by Γ G (i). By symmetry, summing across all nodes i will give five times the total count of 5-complete subgraphs in the graph, and so we divide the sum by five to give result [START_REF] Jungnickel | Graphs, Networks and Algorithms[END_REF], which can be simplified further by using [START_REF] Guimerà | The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles[END_REF] to count 4-complete subgraphs in each subgraph G -i .

Proof of Proposition

B Additional Figures and Tables


Krastanka Bozhinova

Enhancing Multilingual Learning Practices in a University Context

Learning L3 French

Multilingual approaches to language learning today attempt to take into account the learners' own resources, namely their multilingualism which can trigger effective strategies conducive to language development (Cenoz / Gorter 2015, [START_REF] Jessner | Linguistic Awareness in Multilinguals[END_REF]. On the other hand, the use of digital resources possesses a significant potential to encourage innovative multilingual approaches in the university context (Borg et al. 2016, iii).

The aim of this paper is to emphasize the value of considering language learning, in this particular casethe French language, in close association with learners' pre-acquired knowledge in other languages and their learning strategies. In the last two decades, teachers of French, at least in Bulgaria, often regret that students choose to learn English as a first L2 after their L1. However, we shouldn't forget that teaching and learning French as an additional language (or L3) is also a frequent case that deserves to be examined in order to identify positive effects on the learning practices.

The paper will first examine the characteristics of the Integrated Language Didactics1 , which is part of the pluralistic approaches developed in the recent decades [START_REF] Candelier | Approches plurielles, didactiques du plurilinguisme : le même et l'autre[END_REF]. It will also consider some research findings in the field of Third Language Acquisition (Aronin / Hufeisen 2009) and multilingual education (Cenoz / Gorter 2015). It will then present examples from empirical studies on multilingual learning practices based on the use of digital resources, which have been conducted since 2013 with learners of French in a university context.

Psycholinguistic foundations of L3 learning and teaching

Integrated language teaching

The foundations of the integrated language teaching originate from the work of the Council of Europe, which in the 1970s encouraged educational leaders to foster the integration of similarities between languages rather than focus on differences (Cavalli 2005, 194-195).

According to the principle of anticipation, each teacher of L1 or L2 prepares the consecutive or parallel teaching of other languages. The acquisition of an additional language exerts also a retroactive effect on the already acquired linguistic knowledge and its restructuring (Moore 2006, 201).

Psycholinguistic models of multilingualism

In the last two decades, the linear psycholinguistic models developed in the research on bilingualism shifted to dynamic models which reflect the complex phenomena involved in language acquisition and production. For example, Herdina and Jessner's Dynamic Model of Multilingualism (DMM) (2002) represents the development of the multilingual system as evolving in time, non linear, reversible and complex. Multilingual competence is characterized mainly by the dynamic interactions between psycholinguistic systems, crosslinguistic interaction and multilingualism as a factor which reflects the particular qualities of the multilingual speaker/learner.

Williams and Hammarberg's model of language roles or functions distinguishes between "instrumental role" when other languages are activated to manage the communicative situation (for example to insert a comment, a question, an explanation, to translate, etc.), and "supplier role" when they are activated as material for speaking in another language (Hammarberg 2006, 2). These authors have observed that usually one language in the multilingual speaker's repertoire functions as a default external supplier language.

Partial activation of another language

Phenomena that emerge from the contact between languages are often referred to as "transfer", "cross-linguistic influence" or "interaction" as encompassing and interchangeable concepts. (De Angelis 2007, 19) The term "partial activation of another language" (Narcy-Combes 2012) seems to be more precise since it reflects the cognitive activity of the multilingual learner or speaker. According to its definition in linguistics, activation is a "process by which an entire languageor some elements of itare stimulated and accessed during the execution of a receptive or productive task". (De Angelis 2007, 70-71) Occurrences of activation represent traces of the presence of multiple languages in the speaker's verbal repertoire and refer to the "macrocompetence" which allows the multilingual subject to handle the available codes and to switch between them if necessary [START_REF] Moore | Plurilinguismes et école[END_REF].

The concept of translanguaging is currently used to name the multilingual practices based on the free use of different languages as resources in the learning process (Cenoz / Gorter 2015).

The aim is to create links between the known languages as a pedagogical strategy and to introduce specific activities that promote metalinguistic awareness.

The L3 learners' characteristics

The learning process is also influenced by the L3 learners' characteristics such as their aptitude, strategies and representations, which function as a cognitive and affective filter in the learning process. In the studies on multilingualism, linguistic aptitude is closely associated to metalinguistic awareness in the acquisition of multiple languages. For this reason, in the DMM, the acronym MLA is used to designate both "multilanguage aptitude" and "metalinguistic awareness" (Herdina et Jessner 2002, 138).

Metalinguistic awareness is related also to the monitoring hypothesis (Jessner 2006, 26) integrated in most of the psycholinguistic models of multilingualism. Regarding the DMM, the psycholinguistic system of the multilingual speaker possesses an "enhanced multilingual monitor" which facilitates the mobilization of compensatory strategies based on all available linguistic resources. At the same time, it can deactivate linguistic items which do not correspond to the communicative setting.

Research has also shown that the multilingual learners' strategies are more varied and less dependent on individual factors comparing to the learners of a first L2. Production strategies used by multilingual learners are also called "multilingual compensatory strategies" [START_REF] Jessner | Linguistic Awareness in Multilinguals[END_REF]). According to some empirical studies, the process of partial activation of another language occurs either as a conscious strategy or unconsciously, by leaving few or no traces in the speech. Researchers who have studied activation of other languages in L3 written production usually find that activation of L2 occurs most often at the lexical level while morpho-syntactic items are not activated frequently2 .

In the fields of didactics and language acquisition, representations are defined as a structuring element of the acquisition process since they trigger specific learning strategies depending on the perceived distance between the two linguistic systems involved (Castellotti / Moore 2002, 9). Representations are simultaneously static and dynamic. On the one hand, part of them are memorized and function as a reference and on the other hand, others are evolving because they are constructed in the interactions (ibid, 10).

L2 English in support of learning L3 French

Research questions and hypotheses

Three empirical studies were conducted in the context of French language courses, taught to international university students fluent in English. The impact of their multilingual repertoires and experience as learners of other languages on the French learning process was examined.

The exploratory study realized in 2013 aimed at observing the multilingual learners' behavior and, in particular, how they mobilize their plurilingual potential to perform a communicative task in French.

The two intervention studies carried out in 2014-2015 and 2017 were designed to experiment an approach to language teaching that recognizes the multilingual learners' needs and relies on digital tools and mediation to facilitate their writing activity.

The initial hypothesis of the exploratory study was that L2 English, used as the language of instruction in this educational context, plays an important facilitative role in learning French as an L3.

The intervention studies, aimed at answering the question how to optimize the pedagogical activities designed to develop the multilingual learners' written production in French. It was suggested that the plurilingual approach could lead to positive effects if it was applied through a dynamic blended learning system. The blended environment design was largely inspired by the Model of Didactic Ergonomics which Narcy-Combes and his team proposed, drawing upon emergentist and socioconstructivist theories [START_REF] Narcy-Combes | Interrogations didactiques à l'heure de la connaissance située et distribuée[END_REF]). The most important conditions for effective learning in this context were:

 the combination of reading and writing;  basing speech production on both rules and chunks;  providing forms of scaffolding that correspond to the recurrent nature of writing;

 the use of digital multilingual tools that could reinforce the effect of tasks.

Context and collected data

43 students from the American University in Bulgaria took part in the exploratory study.

Their levels in French were from A2 to B2. Written productions were collected at two points during the semester, as well as their language biographies and introspective questionnaires. 76 students participated in the main intervention study. Their levels in French were from A1 to B2. In this study, the proposed tasks integrated collaboration with peers and Frenchspeaking partners, as well as the use of digital tools. The indirect feedback of the teacher was integrated as an intermediate stage in the written production. In addition to their texts, introspective data were collected by audio recording of semi-structured interviews, a research journal, and with a more innovative tool: real time dynamic screen capturing of the students' writing activity3 .

The most recent study was a bilingual telecollaborative project between 12 learners of French from AUBG and 24 older learners of English from the University of Bordeaux. The collected data include writings produced after three synchronous telecollaborative sessions, which were annotated by the partners through email exchange, as well as entries in the students' reflexive journals.

Data analysis

The most important results of the three studies are summarized in this paper. The adopted mixed method combined quantitative and qualitative analysis. Quantitative analysis was mostly applied to the study of linguistic data in order to measure the frequency of:

-the activation of other languages and the proportion between its different forms, for example activation of L2 English versus L1 and activation of lexical items versus morpho-syntactic items;

-the traces of the various forms of scaffolding in order to determine their effect on the development of written production, such as the impact of teacher's and peers' feedback and the work with digital tools; -instances of metalinguistic reflection and the use of different types of strategies while working with digital tools.

Qualitative analysis was applied to the study of:

-the different instances of elements activation belonging to other languages; -the characteristics of the various forms of scaffolding; -the students' attitudes, representations, and perceptions in regards to learning French, their multilingual practices, and the proposed learning environment.

Results and discussion

Activation of other languages

In the exploratory study, it was found that L2 English and other known languages often play a facilitative role in the form of compensatory plurilingual and learning strategies. The hypothesis about the most frequent activation of L2 English was confirmed (80 % of all cases), especially due to the combination of four factors (Fig. 1):

-the status of English as language of instruction in the given context; -psychotypology, that is the perceived typological proximity between French and English;

-the active and most recent use comparing to other L2; -the advanced level of competence in this language.

Fig. 1 Frequency of the activation of other languages in French written production.

An interesting finding, comparing to previous studies (Lindqvist 2010, 136), is that romance languages as L2 play a very weak role in comparison with other known languages. This could be explained with the fact that they correspond to a lower number of factors which usually condition the supplier role of a language [START_REF] Hammarberg | Activation de L1 et L2 lors de la production orale en L3[END_REF]).

The analysis based on the linguistic typology of the activated items from other languages showed that the partial activation at the lexical level was more frequent than the activation at the morpho-syntactic level. More than two thirds of the lexical occurrences are due to the perceived typological proximity between French and another language. In contrast with other studies with a focus on English learners [START_REF] Bouvy | Towards the construction of a theory of Cross-linguistic transfer[END_REF], the rate of the morpho-syntactic occurrences turned out to be much more significant (42 %). It is also important to note that a large amount of errors due to the application of an external rule come exclusively from English, not from the L1 as it was found in other studies (Ringbom 2001). It is possible to state that the weight of the factors related to the use of other languages plays an important role when it comes to their selection and partial activation in this learning context.

The use of digital tools and translation

The analysis of the video recorded writing activity with the help of online tools in real time allowed identifying five types of strategies learners used to produce more complex texts, closer to the norms of French language. These strategies are classified according to the mobilized cognitive resources, starting from the one that retained the least of the writer's attention:

-Simple translation: cases when the learners translate words or short phrases with the automatic translator or a contextual dictionary, such as Reverso Context4 or Linguee5 .

-Spelling and grammar checking: most often learners do this by right click in Word, which is very fast and requires little attention. In some cases additional tools are used, such as verb conjungators, search engines, or bilingual online dictionaries.

-Checking a hypothesis on partially known lexical items, when students begin to write or pronounce the word or expression in French but want to make sure that their hypothesis is correct by checking the item either in a contextual or bilingual dictionary, or in the automatic translator.

-Adaptation of a translated item to the context, that occurs when a translated item needs to be adapted to socio-pragmatic conventions depending on the context, for example, taking into account the status of the speaker and the recipient, their relationship and the textual genre (transformation of a personal pronoun, gender, verb tense, possessives, etc.).

-Translation using advanced tool options: this strategy corresponds to a search for alternative translations (synonyms, reformulation, segmentation of sentences, inverse translation of the result, cross-checking with different tools, etc.).

It was found that beginners used more often tools for quick translation and correction, while higher-level learners exploited more frequently sophisticated tools or a combination of several resources (Fig. 2). Working with tools, which are often based on translation, is likely to lead gradually to the development of learners' autonomy and creativity. However, the intuitive manipulation of the tools increases the time of writing. As a whole, the discourse of the L3 French learners is getting closer to the norms of French for the respective textual genres. At the lower levels, the production mode is closer to the trilingual pole, while the production mode of the B2-level students is closer to the monolingual pole.

As far as metalinguistic reflection is concerned, A2 level learners rarely produce comments of this type. On the other hand, the majority of the B1-level students seem to develop a flexible control system, while using both their own language resources and writing aids. The metalinguistic reflection episodes are most frequent in the case of B2-level students. These findings support Jessner's study (2006) on metalinguistic awareness and plurilingual compensatory strategies used by advanced multilingual learners of English.

However, the manipulation of the advanced tool options is sometimes so complex that the learners are unable to notice the errors. Although higher level learners are generally very sensitive to the correctness of their writing, they still need additional training how to check the quality of the resource they use.

The effect of telecollaboration

In the bilingual telecollaborative experience, conversations were carried out via Skype in English and French consecutively. This resulted in drafting texts in the target language, which needed to be improved through exchange of emails with the partners. It was recommended to provide feedback mostly indirectly so that the learners could reflect on their mistakes and try to revise their texts.

Most frequently (in 65% of the interventions) the partners proposed the correct form and at the same time tried to facilitate noticing the gaps: they used highlighting, different colors, italics, or comments with the proposed corrections. This corrective move is more elaborate in 20 % of the interventions where the partners also added explanations of the error. For example, one French partner underlined the word "voyage", replaced it with "transport", and explained the difference between the two words in English in this way: "Voyage is used for long travel. To mean the time to go to our job we use transport."

Most of the explanations are related to lexical, semantic or morpho-syntactic problems (42 out of the 53 explanatory comments). When the error is not complicated, the learners manage to correct it on their own, as in the case of feminine and plural adjectives. Sometimes, the partners reword the sentences to encourage the use of more complex phrases.

Translanguaging is used often to facilitate the interaction and to draw attention to the analogies and contrasts between French and English. For example one partner explained that the conjunction "et" is used for "and", while "est" is a form of the verb "to be". Another one explains that the word order with "aussi" (also) is different in French compared to English.

Students' attitudes and perceptions on their multilingual learning practices

The majority of the students show positive attitude towards the role of other languages in learning French. For instance, 76 % of the participants in the main study perceive the knowledge of other languages as an asset, particularly because of their similarities with French. Known languages seem to play a facilitative role for the introduction to the new code thanks to the lexical and, sometimes, morpho-syntactic proximity, and in general, in terms of learning strategies.

Students who regard some of the languages in their repertoires as an obstacle (19 % of the respondents) refer mostly to their confusion due to the parallel learning of two languages and their typological proximity. Objective linguistic proximity does not automatically lead to partial code activation as learners make a personal judgment about similarities and differences (De Angelis 2007, 23-24).

The training tasks with the contextual dictionaries Linguee and Reverso Context were highly appreciated by the learners at all levels. They found particularly useful the possibility to observe and select out of numerous parallel translations of phrases in their context.

In regards to the evaluation of the telecollaborative experience, it led to contradictory reactions. Some students appreciated the possibility to support each other in learning French and English, to understand better their cultures, as well as to create friendships. Among the difficulties and limitations of this experience were the technical problems with synchronous communication and the slow responsiveness of some partners in the asynchronous part. As far as age difference was concerned, several students perceived it as a communication barrier.

Others were surprised at the beginning but either were not embarrassed or considered this experience as valuable.

Conclusions and perspectives

Multilingual learners' language behavior is dependent on a variety of factors. The French learners' written production may benefit from knowing other languages, provided that favorable conditions are created. Organizing the teaching and learning activities in a blended environment appears suitable for the case of L3 French studied in a university context where L2 English is used as a language of instruction. Such environments are found to be effective when they are based on a dynamic view of the learning process and incorporate digital tools and mediation in a systematic way. The development of appropriate forms of scaffolding is necessary to encourage the multilingual learners' monitoring system (Jessner 2006, 26), since it favors not only the mobilization of the available linguistic resources, but also the deactivation of inadequate linguistic elements. Multilingual digital resources and intercultural telecollaboration seem to be particularly favorable to the development of the linguistic and intercultural competence when the learners are supported in their efforts to achieve their goals.

Fig 2

 2 Fig 2 Frequency of written production strategies using online tools at levels A2, B1 and B2.

In French, Didactique intégrée des langues (DIL).

For example,[START_REF] Bouvy | Towards the construction of a theory of Cross-linguistic transfer[END_REF] records only 8% of occurrences of morpho-syntactic errors in the written production of beginner students of L3 English.Ringbom (2001) insists that at the morpho-syntactic level activation is felt mainly from L1.

The professional version of Microsoft Expression Encoder

4.0 was used to capture the student's activity on the screen and his/her voice comments were recorded with a microphone.

http://context.reverso.net

http://www.linguee.fr