Samet Atdağ

Vincent Labatut

A Comparison of Named Entity Recognition Tools Applied to Biographical Texts

Named entity recognition (NER) is a popular domain of natural language processing. For this reason, many tools exist to perform this task. Amongst other points, they differ in the processing method they rely upon, the entity types they can detect, the nature of the text they can handle, and their input/output formats. This makes it difficult for a user to select an appropriate NER tool for a specific situation. In this article, we try to answer this question in the context of biographic texts. For this matter, we first constitute a new corpus by annotating 𝟐𝟒𝟕 Wikipedia articles. We then select 𝟒 publicly available, well known and free for research NER tools for comparison: Stanford NER, Illinois NET, OpenCalais NER WS and Alias-i LingPipe. We apply them to our corpus, assess their performances and compare them. When considering overall performances, a clear hierarchy emerges: Stanford has the best results, followed by LingPipe, Illionois and OpenCalais. However, a more detailed evaluation performed relatively to entity types and article categories highlights the fact their performances are diversely influenced by those factors. This complementarity opens an interesting perspective regarding the combination of these individual tools in order to improve performance.

I. INTRODUCTION

Identifying and categorizing strings of text into different classes is a process defined as named entity recognition (NER) [START_REF] Nadeau | Semi-Supervised Named Entity Recognition: Learning to Recognize 100 Entity Types with Little Supervision[END_REF]. Strictly speaking, a named entity is a group of consecutive words found in a sentence, and representing concepts such as persons, locations, organizations, objects, etc. For instance, in the sentence "Martin Schulz of Germany has been the president of the European Parliament since January 2012", "Martin Schulz", "Germany" and "European Parliament" are person, location and organization entities, respectively. Note there is no real consensus on the various types of entities. Although those are not exactly named entities, NER tools sometimes also handle numeric entities such as amounts of money, distances, or percentages, and hybrid entities such as dates (e.g. "January 2012" in the previous sentence).

Recognizing and extracting such data is a fundamental task and a core process of the natural language processing field (NLP), mainly for two reasons. First, NER is used directly in many applied research domains [START_REF] Nadeau | Semi-Supervised Named Entity Recognition: Learning to Recognize 100 Entity Types with Little Supervision[END_REF]. For instance, proteins and genes can be considered as named entities, and many works in medicine focus on the analysis of scientific articles to find out hidden relationships between them, and drive experimental research [START_REF] Tanabe | GENETAG: a tagged corpus for gene/protein named entity recognition[END_REF]. But NER is also used as a preprocessing step by more advanced NLP tools, such as relationship or information extraction [START_REF] Bach | A Review of Relation Extraction[END_REF]. As a result, a number of tools have been developed to perform NER. S. Atdag and V. Labatut are with the Department of Computer Science of the Galatasaray University, Istanbul, 34349, Turkey (e-mail: samet2@gmail.com, vlabatut@gsu.edu.tr).

NER tools differ in many ways. First, the methods they rely upon range from completely manually specified systems (e.g. grammar rules) to fully automatic machine-learning processes, not to mention hybrids approaches combining both. Second, they do not necessarily handle the same classes of entities. Third, some are generic and can be applied to any type of text [START_REF] Ratinov | Design challenges and misconceptions in named entity recognition[END_REF][START_REF] Landsbergen | Named Entity Work in IMPACT[END_REF][START_REF] Finkel | Incorporating Non-local Information into Information Extraction Systems by Gibbs Sampling[END_REF], when others focus only on a specific domain such as biomedicine [START_REF] Leaman | BANNER: an executable survey of advances in biomedical named entity recognition[END_REF] or geography [START_REF] Martins | Assigning geographical scopes to Web pages[END_REF]. Fourth, some are implemented as libraries [START_REF] Finkel | Incorporating Non-local Information into Information Extraction Systems by Gibbs Sampling[END_REF], and some take various other forms such as Web services [START_REF]Calais Web Service[END_REF]. Fifth, the data outputted by NER tools can take various forms, usually programmatic objects for libraries and text files for the others. There is no standard for files containing NERprocessed text, so output files can vary a lot from one tool to the other. Sixth, tools reach different levels of performance. Moreover, their accuracy can vary depending on the considered type of entity, class of text, etc.

Because of all these differences, comparing existing NER tools in order to identify the more suitable to a specific application is a very difficult task. And it is made even harder by two other factors. First, most tools require the user to specify certain configuration settings, like choosing a dictionary. This leads to a large number of possible combinations, each one potentially corresponding to very different behaviors and performances. Second, in order to perform a reliable assessment, one needs an appropriate corpus of annotated texts. This directly depends on the nature of the application domain, and on the types of entities targeted by the user. It is not always possible to find such a dataset, and if none exist, then it must be designed manually, which is a long and difficult operation.

The work we present here constitutes a preliminary step in a larger research project, consisting in extracting spatiotemporal events from biographical texts. For this purpose, we need first to select an efficient NER tool. As mentioned earlier, there is no entity-annotated corpus for this usage, and the comparison of NER tools is difficult. To solve this problem, we constituted an appropriate corpus based on a selection of Wikipedia pages and developed a platform automating the comparison of NER tools. It includes a variant of classic performance measures we proposed to best fit our needs. Both the corpus and tool are publicly available under open licenses 1 . We then used our platform to compare the most popular free NER tools, and discuss their results.

The rest of this article is organized as follows. In the next section, we briefly review the selected NER tools. In section III we present the methods we used to evaluate their performance. We propose a new set of measures allowing to take partial matches into account. In section IV, we describe the corpus we created for this work and compare it to the 1 http://bit.gsu.edu.tr/compnet

A Comparison of Named Entity Recognition Tools Applied to Biographical Texts

Samet Atdağ and Vincent Labatut existing ones. We then present and discuss, in section V, the performances obtained by the NER tools on these data. We conclude by highlighting the main points of our work, and discuss how it can be extended.

II. EXISTING NER TOOLS

As mentioned before, many methods and tools were designed for named entity recognition. It is not possible to list them all here, but one can distinguish three main families [START_REF] Mansouri | Named Entity Recognition Approaches[END_REF]: hand-made rule-based methods, machine learning-based methods, and hybrid methods. The first use manually constructed finite state patterns [START_REF] Zhou | Named entity recognition using an HMMbased chunk tagger[END_REF]; the second treat NER as a classification process [START_REF] Mansouri | Named Entity Recognition Approaches[END_REF], and the third are a mix of those two approaches. We used three criteria for selecting appropriate NER tools. First, it must be publicly and freely available. Second, we favor proven tools, already wellestablished in the NER community. Last, due to our goal of finally identifying spatiotemporal events, we focused on tools able to handle at least Person, Location and Organization entities.

In the end, we selected four different tools. Stanford Named Entity Recognizer (SNER) [START_REF] Finkel | Incorporating Non-local Information into Information Extraction Systems by Gibbs Sampling[END_REF] is based on linear chain conditional random fields. Illinois Named Entity Tagger (INET) [START_REF] Ratinov | Design challenges and misconceptions in named entity recognition[END_REF] relies on several supervised learning methods: hidden Markov models, multilayered neural networks and other statistical methods. Alias-i LingPipe (LIPI) [START_REF] Alias-I | [END_REF] uses 𝑛gram character language models, trained through hidden Markov models and conditional random field methods. Several pre-trained models for the English language are provided with these three tools. Moreover, they all take the form of Java applications. The last selected tool differs in this point, since OpenCalais (OCWS) [START_REF]Calais Web Service[END_REF] is a Web service. Both LingPipe and OpenCalais are general tools, able to handle various other NLP tasks besides NRE. Moreover, both are commercial tools, but free licenses are available for academic use.

III. EVALUATION METHODS

For a given text, the output of a NER tool is a list of entities and their associated types, and the ground truth takes the exact same form. In order to assess the tool performance, one basically wants to compare both lists. Different approaches can be used for this purpose, depending on the goal and context [START_REF] Nadeau | Semi-Supervised Named Entity Recognition: Learning to Recognize 100 Entity Types with Little Supervision[END_REF]. In this section, we first review the traditional approach, and then propose a variant adapted to our own context.

A. Traditional Evaluation

The traditional evaluation relies on a set of counts classically used in classification: True Positive (TP), False Positive (FP) and False Negative (FN) counts. Those are used to process two distinct measures: Precision and Recall [START_REF] Sang | Introduction to the CoNLL-2002 shared task: language-independent named entity recognition[END_REF]. Precision is defined as the ratio 𝑇𝑃 (𝑇𝑃 + 𝐹𝑃) ⁄ . It corresponds to the proportion of detected entities which are correct. Recall is defined as 𝑇𝑃 (𝑇𝑃 + 𝐹𝑁) ⁄ . It is the proportion of real entities which were correctly detected. Both measures are complementary, in the sense they are related to type I (false alarm) and type II (miss) errors, respectively.

Comparing the estimated and actual lists of entities can be performed according to two distinct axes: spatial (position of the entities in the text) and typical (types of the entities). In terms of spatial performance, a TP is an actual entity whose position was correctly identified by the tool. A FP refers to an expression considered by the tool as an entity, but which does not appear as such in the ground truth. A FN is an actual entity the tool was not able to detect. Figure 1 presents an example of text extracted from Wikipedia and annotated. It contains 10 actual entities represented in boxes, and 9 estimated ones characterized by wavy underlines. In terms of exact matches, there are 5 TP (Victor Charles Goldbloom, Montreal, Selwyn House, McGill University, New York), 4 FP (Canada, MD, Dr.Goldbloom, Medical Center) and 5 FN (Alton Goldbloom, Annie Ballon, Lower Canada College, Goldbloom, Columbia Presbyterian Medical Center). This leads to a Precision of 0.56 and a Recall of 0.50. The interpretation of the counts is different when assessing the typical performance. TP correspond to entities whose type was correctly estimated. Due to the NER process, they consequently also correspond to entities whose position was identified at least partially correctly. FP are expressions considered by the tool as entities, but whose type was incorrectly selected, or which are not actual entities. FN are actual entities for which the tool selected the wrong type, or no type at all [START_REF] Nadeau | Semi-Supervised Named Entity Recognition: Learning to Recognize 100 Entity Types with Little Supervision[END_REF]. As an example, Table I contains the types of the entities from Figure 1. We count 7 TP (rows 1, 2, 5, 7, 9, 10 and 11 in Table I), 2 FP (rows 6 and 8) and 3 FN (rows 3, 4 and 6). Based on these counts, we get a Precision of 0.78 ands a Recall of 0.70. Recall and Precision can then be combined, for example using the F-Measure, in order to get a single score. Some authors even combine spatial and typical performances to get a single overall, somewhat easier to interpret, value. One of our goals with this work is to characterize the behavior of NER tools on biographical texts. To our opinion, combining the various aspects of the tool performance will result in a loss of very relevant information. To avoid this, we want to keep separated measures for space and types. For types, we decided to process Precision and Recall independently for each type. This allows assessing if the performance of a tool varies depending on the entity type. For instance, let us focus on Person entities from Table I. We count 2 TP (rows 1 and 9), 1 FP (row 8) and 2 FN (rows 3 and 4). For this specific type, we therefore get a Precision of 0.67 and a Recall of 0.50. For the spatial performance, we want to clearly distinguish partial and full matches. For this matter, in the next subsection we define variants of the traditional measures.

B. Considering Partial Matches

The traditional approach used to assess spatial performance requires a complete match in order to count a TP: the boundaries of the estimated and actual entities must be exactly the same. However, in practice it is also possible to obtain partial matches [START_REF] Nadeau | Semi-Supervised Named Entity Recognition: Learning to Recognize 100 Entity Types with Little Supervision[END_REF], i.e. an estimated entity which intersects with an actual entity, but whose boundaries do not perfectly match. For example, in Figure 1 Lower Canada College is an actual entity, but the estimation only includes the word Canada. A partial match represents a significant piece of information: the NER tool detected something, even if it was not exactly the expected entity. Completely ignoring this fact seems a bit too strict to us. Moreover, in a later stage of our project, we will aim at developing a method to efficiently combine the findings of several NER tools, in order to improve the overall performance. From this perspective, it is important to consider the information represented by partial matches, and this is why we present an extension of the existing measures.

For this purpose, we propose alternative counts one can substitute to the previously presented ones. First, we need to count the Partial Matches (PM), i.e. the cases where the estimated entity contains only a part of the actual one. We consequently also need to consider the cases where the NER tool totally ignores the actual entity: we call this a Complete Miss (CM). The sum of PM and CM is equal to what was previously called FN. Another situation arises when the detected entities corresponds to no actual entity at all. We call this a Wrong Hit (WH). The sum of PM and WM is equal to FP. Finally, the last relevant case happens when we have a Full Match (FM). It exactly corresponds to a FP, but we decided to use a different name to define a consistent terminology. In the example from Figure 1, we have 5 FM (the entities previously considered as TP), 3 PM (Lower Canada College, Dr.Goldbloom, Columbia Presbyterian Medical Center), 1 WH (MD) and 2 CM (Alton Goldbloom and Annie Ballon).

We use our new counts to adapt the Precision and Recall measures. Regarding the numerator, we now have two different possibilities: FM or PM (instead of TP). For the Precision denominator, we need the total number of estimated entities, which amounts to 𝐹𝑀 + 𝑃𝑀 + 𝑊𝐻 (and not 𝑇𝑃 + 𝐹𝑃 anymore). For the Recall denominator, we use the total number of actual entities, which is 𝐹𝑀 + 𝑃𝑀 + 𝐶𝑀 (and not 𝑇𝑃 + 𝐹𝑁 anymore). We therefore obtain two kinds of Precision ). Additionally, a Total Precision (resp. Recall) can be obtained by summing Full and Partial Precisions (resp. Recalls). In the example of Figure 1, we get 𝑃𝑟𝑒 𝐹 = 0.56 and 𝑃𝑟𝑒 𝑃 = 0.33, so the Total Precision is 0.89. For the Recall, we have 𝑅𝑒𝑐 𝐹 = 0.50 and 𝑅𝑒𝑐 𝑃 = 0.30, resulting in a Total Recall of 0.80.

IV. DESCRIPTION OF THE CORPUS

NER requires big amounts of data for both training and testing the tools. Most studies use some standard corpora generally designed for conferences or competitions, whereas some commercial tools are provided with their own data [START_REF] Alias-I | [END_REF]. The New York Times Annotated Corpus [START_REF] Sandhaus | The New York Times Annotated Corpus[END_REF] is a popular resource, constituted of manually annotated articles published in this journal. However, the access is conditional to the payment of a fee, and we decided to focus on freely available tools in this work. The Message Understanding Conference [START_REF] Grishman | Message Understanding Conference-6: a brief history[END_REF] proposed various corpora for NER. However, not all of them are freely available, and those which are focus on texts very different from biographies (terrorist reports, airplane crashes, etc.). The National Institute of Standards and Technology designed a NER corpus based on newswires [START_REF] Doddington | The Automatic Content Extraction (ACE) Program: Tasks, Data, and Evaluation[END_REF], but it is not accessible from the web anymore. The Conference on Computational Natural Language Learning constituted NER corpora in 2002 and 2003, the latter in English [START_REF] Sang | Introduction to the CoNLL-2003 shared task: language-independent named entity recognition[END_REF]. However, all the articles are related to news, not biographies, and their access is commercial. In [START_REF] Minkov | Extracting personal names from email: applying named entity recognition to informal text[END_REF], four different corpora were constituted from emails, for the purpose of NER assessment. However, only Person entities were annotated. The Automatic Content Extraction corpora [START_REF]Automatic Content Extraction[END_REF] are based on newswires, and their access requires to pay a fee. Due to the absence of a corpus meeting our needs and purpose, we designed a new one, specifically to assess NER tools on biographical texts. We first extracted more than 300 biographical articles from Wikipedia. We then cleaned and annotated 247 of them by hand. The corpus contains a total of 21364 annotated Person, Location, Organization and Date entities, as detailed in Table II. The texts concern people from six categories of interest: Politics, Science, Military, Art, Sports, and other activities (medicine, law, etc.). The distribution of articles over categories is given in Table III. Note there are more politicians (from the 19 th and 20 th centuries) because the final goal of our spatiotemporal event extraction project primarily concerns this population.

V. RESULTS AND DISCUSSIONS

We applied the NER tools described in section II on our corpus from section IV, using the measures presented in section III to assess their performance. The values obtained for the measures are displayed in Table IV and Table V, for spatial and typical evaluation, respectively. For NER tools proposing several pretrained models, we present only those having obtained the best performance. In order to study in details the behavior of the tested NER tools, we processed their performance not only for the whole corpus, but also by entity type and by article category.

A. Overall Performance

Let us first consider the overall performances. From a spatial perspective (Table IV), there is a clear hierarchy between the tools. When considering the total measures, i.e. the sum of full and partial measures, SNER comes second for Precision (0.88) and first for Recall (0.93). Moreover, the part of partial matches in these results is very low. LIPI has the third Precision (0.81) and the second Recall (0.89), but the part of partial matches is much higher.

INET is fourth for Precision (0.79) and third for Recall (0.78), and the share of partial matches are even more important (more than one third of the total performance). Note the fact the balance between full and partial matches changes from one tool to the other shows it is a relevant criterion for performance assessment. We manually examined the texts annotated by INET and found out this high level of partial matches has two main causes. First, many organization names include a location or a person name. INET tends to focus on them, rather than on the larger expression corresponding to the organization name. For example, in the expression Toronto's Consulate General of the Netherlands, INET detects the locations (Toronto and Netherlands). Second, INET has trouble detecting person names which include more than two words.

All previous three tools reach very comparable values for both measures. However, this is not the case for OCWS. This tool has the best Precision (0.91) but by far the worst Recall (0.61), with the smallest proportions of partial matches. The unbalance between the two measures means that OCWS is almost always right when detecting an entity, but also that it misses a lot of them.

With regards to the overall typical performances (Table V), the same hierarchy emerges between the tools. SNER has the second Precision (0.89) and the first Recall (0.92). It is followed by LIPI with the third Precision (0.82) and second Recall (0.88). INET reaches the fourth Precision (0.80) and third Recall (0.78). These values mean those tools perform relatively well, and are able to appropriately classify most entities. Moreover, their performances are balanced, which is not the case of OCWS. Exactly like for the spatial evaluation, we see OCWS reach the first Precision (0.91) but the last Recall (0.61). In words, on the one hand most of the entities it recognizes are correctly classified, but on the other hand it fails to correctly classify almost half the reference entities of the corpus.

B. Performance by Entity Type

Let us now comment the performances by entity type. For the spatial assessment, as shown in Table IV, SNER performs above its overall level when dealing with Person and Location entities (especially for the former). However, its performances are under it when it comes to Organizations: full match-based measures decrease, while partial matchbased ones increase. The total measures stay relatively constant, though. An analysis of the annotated texts shows SNER has some difficulties in two cases, which mainly concern organizations. First, it tends to detect a full name followed by its abbreviation, such as in Partido Liberación Nacional (PLN), as a single entity. Second, it sometimes splits names containing many words. For instance, in the phrase Dr. Isaías Álvarez Alfaro, it detects Isaías and Álvarez Alfaro as separate names. Finally, although it is less marked than for INET, SNER also sometimes mistakes person or location names in organization names. Regarding the typical performance, Person and Location entities are also slightly better handled: the former in terms of Precision and the latter in terms of Recall.

Concerning Person entities, the spatial performances of INET are very similar to the overall ones. For locations, the total precision decreases (due to less partial matches), whereas the recall increases (due to more full matches). In other words, INET is better as rejecting incorrect locations. For organizations, the total measures are similar to the overall level, but the share of partial matches is much higher. This means INET does not miss more Organization entities (compared to other types), but it has trouble precisely identifying their limits. In terms of typical performance, INET is clearly better on persons, both in terms of Precision and Recall. For locations, we can make the same observations than for the spatial performance, i.e. lower Precision and higher Recall compared to overall values.

For OCWS, compared to the overall results, we get similar values for locations, whereas those obtained for persons are slightly higher, and slightly lower for organizations. For all types, we observe the behavior already noticed at the overall level: Precision is high, comparable to the best other tools, whereas Recall is extremely low. A manual analysis of the annotated texts revealed OCWS has trouble handling acronyms, which mainly represent organizations in our corpus. In terms of typical performance, Person entities are also more accurately classified, and the tool is slightly better at not misclassifying organizations.

The performance of LIPI is much better on persons than overall, for both Precision and Recall: this is true for both spatial and typical measures. For locations, we observe a decrease in Full Precision and an increase in Full Recall, also for both spatial and typical results. Our interpretation is that LIPI detects more incorrect locations, but misses less correct ones. For organizations, there is a clear decrease, in terms of both Precision and Recall, with a larger part of partial matches. This last observation can be explained by the fact LIPI tends to merge consecutive organizations.

C. Performance by Article Category

Certain article categories have an effect on the performance of certain tools. When considering SNER, there is no effect for the categories Military, Politics and Science. However, Art and Others lead to slightly lower performances, in terms of both space and types. On the contrary, the spatial performance is much higher than the overall level for Sports (and it is also true of the typical performance, at a lesser degree). This appears to be due to the fact the sport-related biographies generally contain a lot of person names, such as team-mates, opponent, coaches, etc. SNER is particularly good at recognizing person names, which is why its performances are higher for this category. Art-related articles contain many titles of artworks, which are generally confusing for NER tools: they often mistake them for organization names.

For INET, we observe a clear spatial performance increase for Art articles, which means it is not concerned by the previous observation. The performance is slightly better for Science and Sports, in the sense the proportion of full matches gets higher for both Precision and Recall (the total performance staying approximately equal). On the contrary, the values are lower for Military, Politics and Sports. One difficulty with military texts is the detection of army units (e.g. 2 nd Stryker Cavalry Regiment) as organizations. In terms of typical performance, the differences are strongly marked only for Art and Others, positively, and for Sport, negatively. So in Art articles, INET is better than usual, not only at identifying the limits of entities, but also at classifying them, whereas it is the opposite for Sport.

In terms of spatial performance, OCWS is not very sensitive to categories: the observed performances are very similar to the overall ones. The Sports category constitutes an exception though: total Precision stays the same, but the full Precision clearly increases, meaning OCWS is able to detect entities limits more accurately. This is certainly due to the presence of more person names, as already stated for SNER: OCWS gets its best performance on this entity type. The typical performances are more contrasted. The tool is clearly better on Science articles, for which its Recall is almost at the level of the other tools (0.63). On the contrary, the Recall is very low for Art, Others and especially Military (0.05). For the latter, it incorrectly classifies (or fail to detect) almost all the actual entities.

Like OCWS, the spatial performance of LIPI is not much affected by the article categories. For the Others category though, we observe a behavior opposite to that of OCWS for Sports: total Precision and Recall stay approximately constant, but the part of partial matches increases. It is difficult to interpret this observation, since this category corresponds to heterogeneous article themes. For the typical categories, we observe small variations. The classification is slightly better on Sports and slightly worse on Art.

D. General Comments

Several interesting conclusions can be drawn from our results and observations. First, even if the overall performances seem to indicate SNER as the best tool, it is difficult to rank them when considering the detailed performances. This puts in relief the fact single measures might be insufficient to properly assess the quality of NER tools and compare them. The different aspects we considered all proved to be useful to characterize the tools in a relevant way: partial matches, entity types, article categories.

As a related point, it turns out NER tools are affected by these factors in different ways. This is also why they are difficult to rank: none of them is the best on every type and category. As a consequence, these tools can be considered as complementary. For instance, if we consider types, then SNER is the best at recognizing persons. OCWS can be trusted when it recognizes locations and organizations, however is prone to missing a lot of them. On the contrary, LIPI is very good at not missing locations, but also incorrectly detect a lot of them. The differences are not as obvious for article categories, but this information can still be useful, e.g. SNER is much reliable when processing Sports articles. A set of voting rules could be manually derived to take advantage of these observations, or an automatic approach could be used, such as the training of a standard classifier, in order to combine outputs of individual NER tools, and increase the performance of the overall NER VI. CONCLUSION In this article, we focus on the problem of selecting an appropriate named entity recognition (NER) tool for biographic texts. Many NER tools exist, most of them based on generic approaches able to handle any kind of text. So, their performances on these specific data need to be compared in order to make a choice. However, existing corpora are not constituted of biographies. For this reason, we designed our own one and applied a selection of publicly available NER tools on it: Stanford NER [START_REF] Finkel | Incorporating Non-local Information into Information Extraction Systems by Gibbs Sampling[END_REF], Illinois NET [START_REF] Ratinov | Design challenges and misconceptions in named entity recognition[END_REF], OpenCalais WS [START_REF]Calais Web Service[END_REF] and LingPipe [START_REF] Alias-I | [END_REF]. In order to highlight the importance of partial matches, we evaluated their performance using custom measures allowing to take them into account. Our results show a clear hierarchy between the tested tools: first Stanford NER, then LingPipe, Illinois NET and finally OpenCalais. The latter obtains particularly low Recall scores. When studying the detail of these performances, it turns out they are not uniform over entity types and article categories. Moreover, clear differences exist between tools in this regard. A tool like OpenCalais, which performs apparently much lower than the others (on these data), is still of interest because it can be good on niches, and therefore complete an otherwise better performing tool such as Stanford NER.

Our contribution includes four points. The first one is the constitution of a biographic corpus. It is based on articles of the English version of Wikipedia. We manually annotated 247 texts to explicitly highlight Person, Organization, Location, and Date entities. The second point is the definition of performance measures allowing to take partial matches into account. For this purpose, we modified the Precision, Recall and F-Measure traditionally used in text mining. The third point is the implementation of a platform allowing to benchmark NER tools. It is general enough to be easily extensible to other NER tools, corpora and performance measures. Our corpus and platform are both freely available online. The last point concerns the application of this platform to the comparison of four popular and publicly available NER tools. This work can be extended in several ways. First, the size of the corpus could be increased, in order to get more significant results. This would also allow using a part of the corpus for training, and therefore obtain classifiers possibly more adapted to process biographies than the general ones we used here. However, article annotation is a very difficult and time-costly task. Second, the benchmark could involve more NER tools, so that the results reflect more completely the possible choices of the end user. Finally, the comparison we conducted here showed individual NER tools perform diversely on bibliographic texts. Their results are influenced by factors such as entity types and article categories. Moreover, they are not affected in the same way: some are better at recognizing locations, others at organizations, etc. Those tools can therefore be considered as complementary. Combining their outputs by giving them more or less importance depending on these factors seems like a promising way of improving the global NER performance. This could be achieved by defining a set of voting rules based on the observations we made during this study, or by training a classifier.

Figure 1 .

 1 Figure 1. Example of annotated text

  0.06 0.89 0.07 0.56 0.13 0.67 0.16 0.80 0.08 0.52 0.05 0.58 0.14 0.75 0.18 Organization 0.66 0.19 0.71 0.20 0.48 0.32 0.43 0.29 0.74 0.14 0.54 0.10 0.47 0.29 0.49 0.30 Category Art 0.71 0.12 0.77 0.13 0.63 0.17 0.66 0.18 0.77 0.11 0.51 0.08 0.59 0.19 0.60 0.19 Military 0.75 0.15 0.80 0.16 0.50 0.24 0.47 0.23 0.75 0.16 0.44 0.09 0.64 0.20 0.58 0.18 Politics 0.77 0.12 0.80 0.12 0.47 0.33 0.45 0.32 0.80 0.10 0.45 0.06 0.66 0.18 0.63 0.17 Science 0.77 0.13 0.80 0.13 0.61 0.21 0.57 0.20 0.82 0.12 0.46 0.07 0.63 0.20 0.64 0.20 Sports 0.85 0.07 0.85 0.08 0.46 0.26 0.41 0.23 0.92 0.05 0.44 0.03 0.65 0.24 0.60 0.22 Others 0.73 0.15 0.76 0.15 0.57 0.26 0.55 0.25 0.80 0.12 0.49 0.07 0.56 0.25 0.56 0.25

TABLE I .

 I TYPES OF THE ENTITIES IN FIGURE1

	Reference entity	Reference	Estimation
	Victor Charles Goldbloom	Person	Person
	Montreal	Location	Location
	Alton Goldbloom	Person	-
	Annie Ballon	Person	-
	Selwyn House	Organization	Organization
	(Lower) Canada (College)	Organization	Location
	McGill University	Organization	Organization
	MD	-	Person
	(Dr.) Goldbloom	Person	Person
	(Col. Presb.) Medical Center	Organization	Organization
	New York	Location	Location

  Victor Charles Goldbloom was born in Montreal, the son of Alton Goldbloom and Annie Ballon. He studied at Selwyn House and Lower Canada College. He studied at McGill University receiving his BSc in 1944, his MD in 1945, his DipEd in 1950 and his DLitt in 1992. Dr. Goldbloom was assistant resident at the Columbia Presbyterian Medical Center, in New York.

TABLE II .

 II NUMBER OF ENTITIES BY TYPE

	Person	Location	Organization	Date
	7330	2350	4611	4126

TABLE III .

 III NUMBER OF ARTICLES BY CATEGORY

	Politics	Science	Military	Art	Sports	Others
	94	48	11	34	25	37

TABLE IV .

 IV SPATIAL PERFORMANCE BY ENTITY TYPE AND ARTICLE CATEGORY

TABLE V .

 V TYPICAL PERFORMANCE RESULTS BY ENTITY TYPE AND ARTICLE CATEGORY

	system.
			SNER		INET		OCWS		LIPI
			Precision	Recall	Precision	Recall	Precision	Recall	Precision	Recall
	Overall		0.88	0.93	0.80	0.78	0.91	0.61	0.82	0.88
		Person	0.93	0.95	0.84	0.82	0.94	0.68	0.91	0.94
	Type	Location	0.85	0.97	0.71	0.85	0.88	0.60	0.73	0.94
		Organization	0.85	0.92	0.80	0.74	0.88	0.69	0.76	0.80
		Art	0.83	0.92	0.80	0.86	0.90	0.34	0.78	0.81
		Military	0.91	0.96	0.81	0.78	0.96	0.05	0.85	0.77
	Category	Politics Science	0.89 0.90	0.92 0.93	0.80 0.82	0.77 0.80	0.91 0.94	0.53 0.63	0.84 0.83	0.81 0.85
		Sports	0.93	0.93	0.73	0.64	0.96	0.51	0.89	0.83
		Others	0.87	0.91	0.83	0.81	0.92	0.19	0.81	0.80

ACKNOWLEDGMENT

The first version of our platform was developed by Yasa Akbulut, and the first version of our corpus was constituted by Burcu Küpelioğlu. Both tasks were conducted in our research team.


Burcu Kantarcı

Vincent Labatut

Classification of Complex Networks Based on Topological Properties

Keywords: Complex Networks; Topological Measures, Properties Comparison, Cluster Analysis

Complex networks are a powerful modeling tool, allowing the study of countless real-world systems. They have been used in very different domains such as computer science, biology, sociology, management, etc. Authors have been trying to characterize them using various measures such as degree distribution, transitivity or average distance. Their goal is to detect certain properties such as the small-world or scale-free properties. Previous works have shown some of these properties are present in many different systems, while others are characteristic of certain types of systems only. However, each one of these studies generally focuses on a very small number of topological measures and networks. In this work, we aim at using a more systematic approach. We first constitute a dataset of publicly available networks, spanning over different domains. We then process different topological measures to characterize them in the most possible complete way. Finally, we apply standard data mining tools to analyze these data. A cluster analysis reveals it is possible to obtain two significantly distinct clusters of networks, corresponding roughly to a bisection of the domains modeled by the networks. On these data, the most discriminant measures are density, modularity, average degree and transitivity, and at a lesser extent, closeness and edgebetweenness centralities.

I. INTRODUCTION

A complex system is a specific type of real-world system, i.e. a set of interacting elements relatively isolated from their environment, and possessing some emerging properties [START_REF] Costa | Analyzing and modeling real-world phenomena with complex networks: a survey of applications[END_REF]. Such a property is not present at the level of a single element, but appears when considering the system as a whole. Its study consequently requires focusing on the interactions between the system elements. For this purpose, graphs are a very appropriate modeling tool, in which elements and their relations are represented by nodes and links, respectively. And indeed, they have been used as such in a number of domains such as computer science, physics, biology, sociology, etc. [START_REF] Newman | The structure and function of complex networks[END_REF]. The graph representation of a complex system is called a complex network. Such a graph has non-trivial topological properties, due to the specific features of the complex system it represents. Concretely, this means complex networks differ from both regular and random graphs.

Graphs can be characterized by many different measures, each one reflecting some particular traits of the studied structure. One can cite degree, transitivity, distance between nodes, density, etc. Some of these measures have been used to detect certain properties, seemingly very widespread in complex systems. For instance, it is now well known that many complex networks are scale-free, meaning their degree is power-law distributed [START_REF] Newman | The structure and function of complex networks[END_REF]. Many of them also possess the small-world property, i.e. the average distance between their nodes increases only logarithmically with the number of nodes [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF]. Complex networks are also known to have a transitivity several order of magnitude larger than that of random graphs of the same size [START_REF] Newman | The structure and function of complex networks[END_REF]. It is also very common for complex networks to display a hierarchical or a community structure [START_REF] Newman | The structure and function of complex networks[END_REF].

In the past, authors have focused on one or a few properties and studied them on networks representing a range of systems, with the purpose of showing their omnipresence. For example, in [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF], Watts & Strogatz considered the transitivity and average distance in social, electrical and biomolecular networks, and found out they all behave similarly. On the contrary, other studies tried to show some properties are characteristic only of a certain class of networks. For example, in [START_REF] Lancichinetti | Characterizing the Community Structure of Complex Networks[END_REF], Lancichinetti et al. observed different topological traits in community structures, depending on whether the considered data correspond to a biological, social, information, communication or computer network. These works highlight the importance of discovering regularities and discrepancies in complex networks topological properties. Indeed, these properties correspond to functional features. For example, a scale-free network is known to be sensitive to targeted attacks or failures, but resilient to random ones [START_REF] Costa | Analyzing and modeling real-world phenomena with complex networks: a survey of applications[END_REF]. Topologically similar networks are therefore likely to represent systems with functional similarities, whereas network classes with specific topologic properties probably have unique functional features. However, existing works focused on a small number of networks and/or of properties. The network number limitation might be due to the difficulty of accessing data at this time. And regarding the focus on a few properties, this might be because those works were conducted to verify an a priori hypothesis. For example, one goal of Watts & Strogatz was to check if the small-world property was present also in non-social networks [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF].

In this work, we propose to adopt a systematic approach in the study and comparison of the topological properties of complex networks. First, it is now possible to retrieve many publicly available network datasets through the Web, which allows considering a number of different systems. Second, data mining techniques are able to consider a large number of topological measures simultaneously, and to automatically identify the relevant ones. By considering many of them at the same time, we can find how they relate, which is not possible when focusing only on a few of them. We first gathered a dataset of networks spanning several domains, which constitutes our first contribution. We processed the most widespread topological measures for these networks, and used them as feature vectors to characterize them. We then applied standard data mining tools to study them depending on these features. We finally analyzed and interpreted this outcome.

The rest of the article is organized as follows. In the next section, we define the measures we selected to characterize the networks. In section III, we describe the tools we used to analyze the dataset. In section IV, we first present our dataset, before describing and interpreting our results. We conclude with a discussion of our work, its limitations and how these can be solved.

II. TOPOLOGICAL MEASURES

In this section, we briefly describe the topological measures we used in our study. We decided to focus on the most popular ones in the network analysis literature. Here, we distinguish between local and global measures, i.e. those concerned with individual nodes or links, and those describing the network as a whole. In a given network, we note the node set and the link set. The number of nodes is | | and that of links is | |. We note A the adjacency matrix, whose binary element is if there is a link between nodes and , and otherwise.

A. Local Measures

Degree. This nodal measure ( ) corresponds to the number of links attached to a node .. In real-world networks, it often follows a power law, leading to the so-called scale-free property [START_REF] Newman | The structure and function of complex networks[END_REF]. The degree ( ) of a node can be formally defined using the adjacency matrix:

( ) ∑ (1)
Distance. The geodesic distance ( ) between two nodes and corresponds to the length of the shortest path between them. The distance distribution has been especially studied in the context of computer networks such as the Internet. When it increases logarithmically with the size of the network, the system has the so-called small-world property [START_REF] Newman | The structure and function of complex networks[END_REF].

Eccentricity. This nodal measure ( ) corresponds to the largest distance between a node and any other node [START_REF] Freeman | Centrality in Social Networks I: Conceptual Clarification[END_REF].

( ) ( ) (2)
Betweenness centrality. This nodal measure ( ) is the number of shortest paths going through a node . Let us note the total number of shortest paths between nodes and , and

( ) the number of shortest paths between and going through [START_REF] Freeman | Centrality in Social Networks I: Conceptual Clarification[END_REF]. We have:

( ) ∑ ( ) (3)
Closeness centrality. This nodal measure ( ) is the inverse of the sum of distances between the node of interest and all the other nodes . It quantifies how close a node is from the rest of the network, in average.

( ) ∑ ( ) (4)
Edgebetweenness. This measure ( ) represents the number of shortest paths containing the link . Links with high edgebetweenness centrality corresponds to bridge-like connectors between two parts of a network [START_REF] Girvan | Community structure in social and biological networks[END_REF]. In the following formula, ( ) is the number of shortest paths between and containing the link .

( ) ∑ ( ) (5)
Local transitivity. This nodal measure ( ), also called clustering coefficient, corresponds to a ratio: the number of triangles including the node of interest , to the number of possible triangles centered on this node. It can be interpreted as the probability for a link to exist between two randomly picked neighbors of the node of interest [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF]. Let us note ( ) the neighborhood of node , then we have:

( ) | ( )| ( ) ⁄ (6)

B. Global Measures

Density. This global measure noted ( ) corresponds to the ratio of existing to possible links in network . It ranges from (no link at all) to (all nodes are connected). Realworld networks are generally considered to be very sparse, with densities close to .

( ) ( ) (7)
Diameter & radius. The diameter ( ) is the maximum eccentricity over the network, i.e. the maximal distance between two nodes in :

( ) ( ) (8)
On the contrary, the radius ( ) is the minimum eccentricity of the network [START_REF] Dehmer | Structural Analysis of Complex Networks[END_REF], i.e.:

( ) ( ) (9)
Transitivity. This measure, also called clustering coefficient, corresponds to the proportion of triangles in the network [START_REF] Newman | The structure and function of complex networks[END_REF]. As such, it ranges from (no triangles) to (all possible triangles exist). It can be interpreted, when picking randomly a node, as the probability for two of its neighbors to be connected. According to the literature, the transitivity ranges from to in real-world network [START_REF] Newman | The structure and function of complex networks[END_REF]. Let us note ( ) the number of subgraph with links and nodes (i.e. triangles) and ( ) is the number of subgraphs with at least links and nodes (i.e. triangles and incomplete triangles). Then, the global transitivity is:

( ) ( ) ( ) (10)
Modularity. This measure assesses the quality of a community structure. It corresponds to the proportion of links located inside the communities, minus an estimation of the same qua ntity obtained for a null model. Consequently, its upper bound is 1 while 0 means the community structure is equivalent to a random one. Values observed in real-world networks possessing a community structure are relatively high, in general. Let us define the function such that (

) is equal to if nodes and belong to the same community, and otherwise [START_REF] Newman | Finding and evaluating community structure in networks[END_REF]. Then the modularity is:

∑ [ ] ( ) (11)
We note ( ) an estimation of the maximal modularity one can get on network .

Averages. Besides the mentioned measures, which are global by construction, we also consider as global measures the averages of the previously listed local measures: average distance, average local transitivity, etc.

III. ANALYSIS METHODS

In this section, we describe the methods we applied to analyze our dataset. We first explain the method we used to normalize the data, in order to be able to compare the various considered measures. We then describe the clustering tools we selected to detect groups of networks. Finally, we present the measures we used to assess the cluster qualities and compare them.

A. Preprocessing

The first step in our preprocessing is to normalize the values obtained for the selected measures. Then, these normalized data can be used to process the distance between networks.

Normalization. Not all measures are defined on the same range. This can be a problem when performing cluster analysis, because certain algorithms are sensitive to large differences in attribute values, and might give more importance to those with the largest magnitude [START_REF] De Souto | Comparative Study on Normalization Procedures for Cluster Analysis of Gene Expression Datasets[END_REF]. To avoid this, we apply the same Min-Max normalization to all measures. Let ( ) be a vector of values we want to normalize, where is here the number of values. Then, the Min-Max normalization consists in processing ( ) such as:

However, we treat local and global measures differently. For the global ones, each network is described by a single value: we consequently normalize a series of values over the dataset. This way, we can consistently compare networks, knowing the minimal and maximal values a network can reach in our dataset are and , respectively.

For the local measures, we obtain a series of values for each network. Each value corresponds to a node, a link or a pair of nodes. We separately normalize these series, so that and now correspond to the minimal and maximal values one can find for a given network (and not for the whole dataset, like before). Indeed, our goal here is to compare distributions, so relative differences are more important than absolute ones. After this normalization, the distribution is processed under the form of histograms, containing bins with a step of .

Distance Matrix. Once the measures have been normalized, it is possible for us to process the distances. We first calculate a partial distance for each measure taken separately. We then combine all of them to get the overall distance between two networks. Again, we distinguish between global and local measures.

For each global measure, we compare two networks by simply considering the Manhattan distance , i.e. the absolute value of the differences. The result is necessarily a value ranging from to , thanks to our normalization. For the local measures, we process the Earth Mover's (EM) distance [START_REF] Rubner | The Earth Mover's Distance as a Metric for Image Retrieval[END_REF] between both histograms. Because we apply the EM distance to normalized histograms, it ranges from to .

The overall distance is obtained by simply averaging all partial distances. By construction, it will also range from 0 to 1. The overall distance is processed for each pair of networks, in order to build the matrix distance required by the clustering algorithms. Let us note the number of global measures, and the number of local measures. Each normalized global measure is noted ( ) and each normalized local measure is noted ( ). The overall distance between two networks and is:

( ) ∑ ( ( ) ( )) ∑ ( ( ) ( )) (13)

B. Cluster Detection

Cluster analysis consists in empirically forming groups of objects, called clusters, with high intra-cluster similarity and low inter-cluster similarity. One can distinguish various general approaches: partitional, hierarchical and density-based algorithms. We chose to apply one tool of each these families, in order to be able to compare them and obtain consensual clusters.

Partitional approaches. They first split the dataset in several mutually exclusive clusters, and then maximize (resp. minimize) the intra-cluster (resp. inter-cluster) similarity by moving objects from one cluster to another. The most widespread algorithm is -means, however it requires to perform averages objects, which we can since we only have access to the distances. For this reason, we selected a variant of -means called Pam (Partitioning Around Medoids) [START_REF] Reynolds | Clustering rules: A comparison of partitioning and hierarchical clustering algorithms[END_REF]. This approach requires the user to specify the number of desired clusters. When this information is unknown, as it is for us, the classic approach consists in using a broad range of values, and selecting the one leading to the best clusters according to some criterion.

Hierarchical approaches. They build a hierarchy of clusters, called dendrogram. Two different methods exist for this matter: bottom-up or agglomerative, and top-down or divisive. In the former, each object is initially considered as a cluster, and those are iteratively merged until only one cluster containing all objects remains. In the latter, on the contrary, all the objects are in the same unique cluster, which is then repeatedly divided until obtaining only singleton clusters. The choice of the final clusters is made by selecting a level, called cut, in the dendrogram, according to some criterion of interest. We selected two popular algorithms: one agglomerative tool, Agnes (Agglomerative Nesting) [START_REF] Kaufman | Finding Groups in Data: An Introduction to Cluster Analysis[END_REF], and one divisive tool, Diana (Divisive Analysis) [START_REF] Kaufman | Finding Groups in Data: An Introduction to Cluster Analysis[END_REF].

Density-based approaches. Starting from an initial object called seed; a cluster is constituted by iteratively aggregating close objects. The cluster grows as long as some conditions regarding its density still hold. When it is not the case anymore, the cluster is complete (its limits have been reached). Another seed is then picked, in order to constitute a new cluster. We selected the DBscan implementation of this approach [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF]. It requires the user to specify two parameters allowing defining the notion of cluster density: first, a radius defining the neighborhood of an object; second, the minimal number of object required inside this neighborhood, so that it is considered as dense.

C. Cluster Evaluation

Each selected clustering method outputs several partitions of the dataset, either because it is hierarchical (Diana, Agnes) or because some parameters must be tuned (Pam, DBscan). In order to identify the best partitions, we therefore need to be able to quantify their quality. For this matter, we used the average Silhouette width. Moreover, once the best partition has been identified for each tool, we want to compare them from tool to tool, in order to check for agreement. For this purpose, we used the Adjusted Rand Index.

Silhouette. This measure is based on two quantities noted ( ) and ( ) [START_REF] Aranganayagi | Clustering categorical data using silhoutte coefficient as a relocation measure[END_REF]. The former is the average distance between an object of interest and the rest of the objects located in the same cluster. For the latter, we first perform the same operation, but for objects located in a different cluster. ( ) is the minimum of this quantity processed over all other clusters. From ( ) and ( ), we can process the silhouette width for the object of interest:

( ) ( ) ( ) ( ( ) ( )) (14)
The overall value is obtained by averaging ( ) over all objects. Its range is [ ], and higher value means better quality.

Adjusted Rand index. This measure was designed to compare two partitions of the same set [START_REF] Hubert | Comparing partitions[END_REF]. Let us note the number of instances belonging to cluster in the first partition, and to cluster in the second one. We can then note the number of instances belonging to cluster in the first partition, whatever their cluster in the second partition is, and the symmetric quantity: number of instances in cluster , independently from their cluster in the first partition. The Adjusted Rand Index is defined as:

∑ ( ) [∑ ( ) ∑ ( ) ] ( ) [∑ ( ) ∑ ( ) ] [∑ ( ) ∑ ( ) ] ( ) (15)
A value of corresponds to perfect agreement, while means random agreement.

IV. RESULTS AND DISCUSSION

Our dataset consists of a collection of networks, all of them publicly available on the Internet. One of our goals was to study how the type of system represented by the network affects its topology. For this reason, we grouped them in different domains: social interactions, scientific citations, communication, ecological systems, biomolecular interactions, computer networks and transportation systems. Social networks correspond to acquaintances, sexual and trust networks. Scientific citations represent bibliographic references. Communication networks include email and phone networks. Ecological networks are constituted of taxa and their predator-prey relationships. Biomolecular networks include protein, metabolic and genetic interaction networks. Computer networks include various representations of the Internet and the Web. Transportation networks correspond to airport interconnections and road systems. The number of networks for each domain is represented in TABLE I. In this section, we present our analysis of these data, using the methods described in section III.

A. Topological Properties

Let us describe our datasets in terms of the topological measures presented in section II. Those results are summarized in TABLE II, which contains lower and upper bounds, mean ( ) and standard deviations ( ) for the main measures, and for each domain. The notations are the same than in section II, namely: size, density, average degree, global transitivity, average distance, diameter, radius and modularity.

Size. For all domains, the size of the smallest networks is of the same order of magnitude: a few tens of nodes. However, this is not the case for the largest ones. The largest Ecological and Transportation networks contain a few hundred nodes. For Social, Communication and Biomolecular networks, it is several thousand nodes. And Citation and Computer Science networks reach several tens of thousands of nodes. This highlights the fact real-world network sizes are very heterogeneous, spanning orders of magnitude. This is confirmed by the generally large standard deviations.

Density.

Similarly to what can be observed in the literature, most of our networks are very sparse, as seen in the average density and standard deviation of all domains. For some of them, the density is even as low as . However, the average density of Social and Transportation networks is clearly higher (roughly the double of the others). Moreover, some networks are remarkably dense in the Social, Communication and Biomolecular domains, as highlighted by their upper bounds.

Degree. According to the Kolomogorov-Simirnov tests we performed, all the studied networks have a power-lawdistributed degree, a prominent feature in complex networks literature. For most domains, degree bounds have the same order of magnitude: a few units for the lower bound, several tens for the upper bound. The exceptions are Transportation, Communication and Citation networks, whose upper bounds reach several hundreds. For the Citation domain, this can be explained by the fact the networks are larger (in terms of nodes), compared to other domains, while they are as dense. For the Transportation and Communication domains, the networks are small but dense, which can explain these high upper bounds.

Transitivity. The literature highlights the fact real-world networks generally have a high transitivity. It does not seem to be the case so much when looking at the average values obtained on our dataset, which range from to . A look at the bounds shows us the smallest values are almost zero, and the highest ones are not so large (around ), with the exception of Social and Transportation networks ( and , respectively). The relatively large standard deviations highlight the heterogeneity of the networks in terms of transitivity. However, when comparing with values expected for ER networks with the same size and density, it turns out the networks of our dataset are more transitive.

Distance. The order of magnitude of the average distance and both distance bounds are roughly the same for all domains: the lower bounds are close to , the upper bounds are close to , and the average distances lie in between. All networks consequently have a very small average distance, when compared to their size in terms of nodes. Larger networks have a higher distance, but the increase is marginal. The observed average distances are higher than those expected for ER random networks of same size and density. This means the observed values alone are not sufficient to decide if the networks are small-world.

Eccentricity. For most networks, we observe a bimodal distribution of eccentricity, most of the nodes having very low or very high values. In terms of diameter, the order of magnitude of the diameter is the same for most domains, independently from the network size: it ranges from a few hops to a few tens. However, this is not true for the Social and Ecological networks, since the upper bound is tens of thousands of hops for them. This means that, even if the average distance is of the same order of magnitude than in other domains, it is possible for nodes to be much farther from the network center in Social and Ecological networks. Interestingly, the same observation does not hold for the radius, which is roughly similar for most domains. Computer networks stand out though, with a radius of hundreds of hops, instead of tens for the other domains.

Centrality. For most networks, the betweenness and edgebetweenness centralities are homogeneous, following a normal-like distribution. This means that, in a given network, most nodes and links lie on the same number of shortest paths, and only a few have extreme values. The presence of only a few central links supports the assumption the networks are modular: those links are known to connect communities. On the contrary, the closeness centrality distribution is bimodal. Both modes are extreme values like for the eccentricity.

Modularity. The modularity ranges from close to zero, or even slightly negative values, to as high as . Most networks have a clearly non-zero modularity, though. The most modular networks belong to the Citation domain. Most domains have a relatively high average ( ). However, this is not the case of the Transportation and Ecological domains, whose average modularity values are for the former and almost zero for the later. Thus, modularity seems to be exceptional for those domains, whereas it is the norm for the

B. Correlation Study

We now examine the correlations between the topological measures studied in the previous subsection. As mentioned before, we distinguish two types of measures: global and local ones. To ease the interpretation of our results, we split the correlation study in three parts: global vs. global, local vs. local and global vs. local. III shows the correlation between global measures only. Most of the values are close to zero, indicating no linear relationships between the measures. However, a few strong positive and negative correlations are also observed. The highest ( ) one is measured between the density and transitivity, which can be explained by the fact that when a network becomes denser, the possibility to find triangles increases, too. The average distance and radius are also highly correlated (

Global vs. global. TABLE

). This is certainly due to the fact both measures reflect how compact the network is.

Density and transitivity are both negatively correlated to average distance ( and , respectively). When the network becomes denser, the average distance automatically decreases: because of the additional links, the shortest paths become even shorter. When the average distance is large, the probability for direct connections decreases, impacting the number of triangles.

Modularity is positively correlated with average distance (

), and like this measure, it is negatively correlated with both density and transitivity ( and respectively). Indeed, the presence of a community structure requires links to be concentrated in communities. So, the network must be relatively sparse: if it is too dense, then the community structure cannot exist. The presence of a community structure increases the average distance: the sparsity of direct connections between nodes from different communities makes shortest paths longer, in average. Local vs. local. Local measures take the form of distributions, so it is not possible to compare them directly using Pearson's coefficient. Instead, we considered two series constituted of the distances between these distributions, for each pair of networks in our dataset. So, we insist on the fact we do not consider the direct correlation between two measures here, but rather the correlation of the distances based on these measures. In other words, a strong correlation value means that if both measure are distributed similarly (resp. differently) in one network, they will also be distributed similarly (resp. differently) in the other. These results are presented in TABLE IV, using the same notation than in section II, namely: degree, local transitivity, eccentricity, betweenness, closeness and edgebetweenness. Some measures are not correlated with any other: it is the case for edgebetweenness. On the contrary, we observe a relatively strong correlation between the remaining measures. This is particularly true of degree and local transitivity ( ), which indicates their distributions change similarly from one network to another. This does not necessarily mean degree and transitivity are directly linearly dependent, but rather that when two networks have a similar degree distribution, they also have a similar transitivity distribution, and vice-versa. Betweenness centrality is strongly (eccentricity) or at least significantly (degree, transitivity, closeness) correlated with all other measures except edgebetweenness. More generally, the correlation between all measures but the edgebetweenness is never smaller than . This indicates there is a certain redundancy in the information conveyed by these measures.

Global vs. local.

To study the correlation between global and local measures, we also used the distances. Here again, it is important to be cautious with our interpretation: a strong correlation means that when two networks are similar in terms of some global measure, they are also similar regarding the distribution of the considered local measure. TABLE V shows the results we obtained.

Most of the measures are not correlated. However, we observe a relatively strong positive correlation for some of them. The highest is observed for density and eccentricity (1.00). This means that, when two networks have the same density, they tend to have the same eccentricity distribution (and vice-versa). At a much lesser extent, the same remark can be made for the closeness and betweenness centrality. Average degree, radius, average distance and modularity are correlated with no local measure. Average degree is not even correlated with degree distribution, and neither are radius and average distance with distance distribution. This observation is valuable, since it means those local measures are not summarized by the corresponding global measures, contrary to what one could a priori assume. For degree, this is consistent with our knowledge though: since it is power-lawsdistributed, we know the average is not a characteristic value.

C. Domain Comparison

The domains constitute the natural partition of our dataset. In order to understand what makes them different, we performed an ANOVA. This analysis aims at identifying which global measures allow discriminating domains. The ANOVA reveals measures are significantly different in at least one domain: average distance (

), density ( ), modularity (

) and transitivity ( ). We performed Tukey's post-hoc test to identify which domains have different average values for these measures. In the end, a clear separation appears between two groups of domains. The first contains Biomolecular, Citation and Computer networks, and the other includes Ecology, Transportation, Social and Communication networks. The question is now to know if this separation, based on a subset of the global measures only, is confirmed when considering the whole available information, thanks to the cluster analysis.

D. Network Clusters

As mentioned in section III, we have applied all 4 selected clustering algorithms (Agnes, Diana, DBscan and PAM) over the whole dataset; using the Silhouette measure to identify the best partitions, and the Adjusted Rand Index (ARI) to compare them. All methods reach their maximal Silhouette value for clusters. Diana has the highest Silhouette with , Pam being a close second with , followed by DBscan ( ) and Agnes (

). These values are not very high (the Silhouette upper bound being 1), but they still show there is a non-random separation between two groups of networks, as the lower bound of Silhouette is .

The clusters found by Diana and Agnes have largely similar structures, with an ARI of . After them, Pam and Agnes

show the second highest similarity with a ARI, and Diana and PAM reach the value 0.41. On the contrary, the clusters found by DBscan are very different, since the ARI is almost zero when compared with all three other methods. Because of the nature of this algorithm, it certainly means it found nonconvex clusters. Those are worth exploring, however in the rest of this work, we decided to focus on the clusters identified by Pam, because it is highly similar to both hierarchical algorithms, and it is very close to Diana in terms of Silhouette. Therefore, we aimed at making a trade-off between the cluster quality and agreement between algorithms. Interestingly, these clusters confirm the partition we previously inferred from the ANOVA conducted over the domains, using the global measures alone. However, the bisection is finer, since it is performed at the level of networks, and not at that of the domains. This allows highlighting the fact a small minority networks do not have topological features typical of their own domain, and therefore constitute outliers worth studying in further details. In order to identify the discriminant topological measures for our clusters, and compare them with those previously obtained for the domains, we conducted another ANOVA. It indicates not less than measures differ significantly between the clusters. For global measures, we have transitivity ( ) diameter ( ), modularity ( ) average distance ( ), density ( ) and average degree (

). For local measures, it is closeness ( ), local transitivity ( ) and edgebetweenness (

).

Amongst the discriminant global measures, we find the 4 ones already identified when studying the domains: modularity,

- - - - 𝑄 Transportation - - - - - Social - - - - - - 𝛿 Communication - - - - - - -
transitivity, density and average distance. The additional global measures are diameter and average degree, which means the only global measures considered as not discriminant are the radius, average centralities and average eccentricity. Out of the selected local measures, only the mentioned above are considered discriminant, the remaining ones being betweenness, degree, distance and eccentricity. Interestingly, closeness and edgebetweenness are considered as not discriminant when averaged, but they are discriminant when handled as distributions. It would be interesting to investigate why averaging them results in an information loss.

V. CONCLUSION

In recent works, specific topological properties have been identified as present in most complex networks, independently from the modeled system, or on the contrary, specific only to certain types of systems. In this work, we tried to extend this kind of work, by adopting a systematic approach. For this purpose, we constituted a dataset of real-world complex networks, distributed over 7 applicative domains; and analyzed it using data mining tools. We first processed widespread topological measures for each networks, including local and global ones. We then compared them relatively to the domains. Some measures, such as density, average degree and transitivity are very heterogeneous, even when considering a single domain. On the contrary, other measures such as average distance and modularity are ether generally more homogeneous, or at least homogeneous when considering domains independently. A correlation study showed strong positive relations between certain global measures: density and transitivity, average distance and modularity; and a strong negative relation between density and modularity. In terms of local measures, there are strong relations between degree and transitivity, and between eccentricity and betweenness. On the contrary, edgebetweenness is not related to any other local measure, but it is strongly related to density.

An additional ANOVA performed on global measures, relatively to the domains, showed transitivity, modularity, average distance and density were the only significantly measures. These differences are clear enough to allow distinguishing two groups of domains: Biomolecular, Citation and Computer networks on one side, and Ecology, Transportation, Social and Communication networks on the other. This dichotomy was confirmed by a cluster analysis based on both global and local measures, although it also allowed performing a finer separation of the networks, highlighting outliers amongst most domains. Moreover, the cluster analysis used additional topological measures to discriminate networks: diameter and average degree for global measures, and closeness centrality, local transitivity and edgebetweenness for local ones.

The first contribution of our work was to tackle the problem of identifying discriminant topological measures by using a systematic approach, in terms of amount of data, topological measures and analysis tools. By opposition, previous works focused only on one or two measures, and on a small number of networks and analysis tools. Our second contribution is the constitution of a real-world complex network dataset. Our third contribution is the analysis of this dataset, mainly based on correlation study, ANOVA and cluster analysis. However, we are aware of certain limitations, too. First, the dataset is relatively small. We are currently still working on it, in order to considerably increase its size. Second, in this first work, we wanted to focus on the most widespread topological measures, but it is possible to consider many others, such as network centralization [START_REF] Freeman | Centrality in Social Networks I: Conceptual Clarification[END_REF], fractal dimension [START_REF] Song | Self similarity complex of networks[END_REF], node roles [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF], assortativity measures [START_REF] Newman | Assortative Mixing in Networks[END_REF], etc. Third, more advanced tools can be used to study the relations between topological measures, and also to interpret the cluster analysis results. For example, discriminant analysis [START_REF] Klecka | Discriminant analysis[END_REF] would allow distinguishing topological measures in terms of discriminant power.

TABLE I .

 I DISTRIBUTION OF NETWORKS OVER DOMAINS

	Domain	Number of Networks
	Social	25
	Citation	20
	Communication	28
	Ecology	20
	Biomolecular	32
	Computer	21
	Transportation	5

TABLE II .

 II OVERVIEW OF TOPOLOGICAL MEASURES RELATIVELY TO DOMAINS

	other ones.
	𝒏	𝜹	𝒌	𝑪	𝒅	𝑫	𝑹	𝑸
	Social

TABLE III

 III

		. CORRELATION BETWEEN GLOBAL MEASURES
	-	0.16	0.76	-0.45	0.02	-0.14	-0.71
	-	-	0.12	-0.16	-0.01	0.00	-0.13
	-	-	-	-0.43	0.04	-0.09	-0.51
	-	-	-	-	-0.09	0.59	0.60
	-	-	-	-	-	-0.03	-0.12
	-	-	-	-	-	-	0.16
	-	-	-	-	-	-	-

TABLE IV

 IV

	. CORRELATION BETWEEN LOCAL MEASURE DISTANCES
	( )		( )	( )	( )	( )	( )
	( )	-	1.00	0.34	0.55	0.24	0.10
	( )	-	-	0.23	0.43	0.33	0.01
	( )	-	-	-	0.79	0.40	-0.01
	( )	-	-	-	-	0.45	0.01
	( )	-	-	-	-	-	-0.01
	( )	-	-	-	-	-	-

TABLE V .

 V CORRELATION BETWEEN GLOBAL AND LOCAL MEASURE DISTANCES

	( )	0.10	-0.09	0.25	0.13	0.01	0.00	0.00
	( )	0.43	-0.09	0.23	0.00	0.01	0.00	0.00
	( )	0.44	0.01	0.18	0.04	-0.04	0.00	0.00
	( )	0.31	-0.06	0.33	0.02	0.01	0.00	0.00
	( )	0.24	-0.25	0.04	-0.01	-0.01	0.00	0.00
	( )	1.00	-0.12	0.43	-0.01	0.07	0.00	0.00

  TABLE VI displays the significantly different measures by pair of domains. All four measures are significantly different between Biomolecular and Computer networks on one side, and Ecology and Social networks on the other side. One the contrary, Biomolecular and Computer networks are not significantly different, and neither are Ecology and Social networks. Although it is not as marked, Transportation networks are also different from both Biomolecular and Computer networks, but not from Ecology and Social networks. Finally, Citation networks lie somewhere in between, since they differ in one measure from all domains but Computer.

TABLE

  VII represents the distribution of networks of different domains over the two clusters detected by Pam. While Biomolecular, Citation and Computer networks are largely grouped in the first cluster, Ecological, Transport, Social and Communication networks are mostly grouped in the second cluster. The first cluster is dominated by Biological networks, whereas Social and Communication clusters dominate the second one.

TABLE VII .

 VII DISTRIBUTION OF DOMAINS OVER CLUSTERS

		Cluster 1	Cluster 2
	Biomolecular	29	3
	Citation	16	4
	Computer	19	2
	Ecology	1	19
	Transportation	0	5
	Social	5	20
	Communication	5	23

TABLE VI .

 VI SIGNIFICANT MEASURES FOR NETWORK DOMAINS

		Biomolecular	Citation	Computer	Ecology	Transportation	Social	Communication
	Biomolecular	-	𝐶		𝐶, 𝑄, 𝑑 , 𝛿	𝐶, 𝑄, 𝑑	𝛿 𝐶, 𝑄, 𝑑	𝐶, 𝑑
	Citation	-	-		𝑑	𝛿	𝑄	𝛿
	Computer	-	-	-	𝐶, 𝑄, 𝑑 , 𝛿	𝑄	𝛿, 𝐶, 𝑑 , 𝑄	𝑑
	Ecology