Vincent Labatut
email: vlabatut@gsu.edu.tr

Jean-Michel Balasque
email: jmbalasque@gsu.edu.tr

Business-oriented Analysis of a Social Network of University Students Informative value of individual and relational data compared through group detection

Keywords: Social Networks, Business Science, Cluster Analysis, Community Detection, Community Comparison, Individual Data, Relational Data I

Despites the great interest caused by social networks in Business Science, their analysis is rarely performed both in a global and systematic way in this field: most authors focus on parts of the studied network, or on a few nodes considered individually. This could be explained by the fact that practical extraction of social networks is a difficult and costly task, since the specific relational data it requires are often difficult to access and thereby expensive. One may ask if equivalent information could be extracted from less expensive individual data, i.e. data concerning single individuals instead of several ones. In this work, we try to tackle this problem through group detection. We gather both types of data from a population of students, and estimate groups separately using individual and relational data, leading to sets of clusters and communities, respectively. We found out there is no strong overlapping between them, meaning both types of data do not convey the same information in this specific context, and can therefore be considered as complementary. However, a link, even if weak, exists and appears when we identify the most discriminant attributes relatively to the communities. Implications in Business Science include community prediction using individual data.

INTRODUCTION

Bringing new insights in decision-making analysis, social networks have raised a great interest in the scientific community. In Marketing Science, and more generally in all the fields of Business Science, the concept strength can be seen at different levels [START_REF] Baret | Management et réseaux sociaux: Jeux d'ombres et de lumières sur les organisations[END_REF]. First, locally, by taking into account the interaction between a person and his precise relational context, it constitutes a good tool to better understand individual decisions. Second, at the level of a whole system, it provides a meaningful analysis basis and offers the necessary information to improve both global organization and individual activities management. In Business sciences, the main point in both research and practice has been the possible benefits a person or a firm can get from social networks. Consequently, their analysis has been considered primarily in a utilitarian perspective, with a particular emphasis on their impact on the nature and efficiency of information dissemination. Their role was noticeably studied in the context of competitiveness in the construction sector [START_REF] Comet | Productivité et réseaux sociaux: Le cas des entreprises du bâtiment[END_REF], firm innovativeness [START_REF] Simon | Créativité et réseaux sociaux dans l'organisation ambidextre[END_REF], investors attraction for venture capital [START_REF] Ferrary | Apprentissage Collaboratif et réseaux d'investisseurs en capital-risque[END_REF], effective use of their social capital [START_REF] Ranie-Didice | Capital social des dirigeants et performance des entreprises[END_REF] in the labor market [START_REF] Fondeur | Réseaux sociaux numériques et marché du travail[END_REF], and administrative boards decision [START_REF] Guieu | Conseils d'administrations et réseaux d'administration en Europe[END_REF], among others. In Marketing Science, the focus has been put more on speed of information diffusion, with a major interest in word-of-mouth [START_REF] Dwyer | Measuring the value of electronic word of mouth and its impact in consumer communities[END_REF], changes of opinions and adoption of innovations inside groups of people (mainly consumers and potential consumers) [START_REF] Goldenberg | The role of hubs in the adoption process[END_REF][START_REF] Steyer | Modélisation de la structure sociale de groupes de discussion sur Internet: implications pour le contrôle du marketing viral[END_REF][START_REF] Van Der Merwe | Finding and utilising opinion leaders: socail networks and the power of relationships[END_REF] or diffusion of specific products [START_REF] Hyunsook | Comparing fashion process networks and friendship networks in small groups of adolescents[END_REF].

In most of these studies, the analysis is centered on a single or a few persons, and consists in studying their most immediate connections in much detail. Even if the investigation concerns a whole social system (group or firm), the focus remains local. Some works study the role these individuals of interest have in the network. Other works analyze the possible effects of the social network on these individuals, and generalize the resulting observations to the rest of the network, or to some subgroups of persons. This approach can be criticized in several ways. First, influence processes within social networks vary considerably depending on the nature, structure and strength of the links that connect the considered persons. For instance, Steyer et al. [START_REF] Steyer | Modélisation de la structure sociale de groupes de discussion sur Internet: implications pour le contrôle du marketing viral[END_REF] showed the efficiency of information dissemination processes, used for viral marketing, depends on the whole network structure. Van der Merwe [START_REF] Van Der Merwe | Finding and utilising opinion leaders: socail networks and the power of relationships[END_REF] described its effect on the role of opinion leaders. According to various authors [START_REF] Hartmann | Modeling social interactions : identification, empirical methods and policy implications[END_REF][START_REF] Watts | Influentials, networks and public opinion formation[END_REF], both opinion spreading and speed of innovation adoption depend on the considered network structure and density. Second, the interest of adopting a nonlocal approach is backed by several Marketing studies like [START_REF] Iacobucci | Modeling dyadic interactions and networks in marketing[END_REF], which, following a stream of Sociology studies, emphasized the necessity of taking sub-networks or cliques into account. These structures diffuse information faster: people belonging to them are more quickly and more deeply influenced, they rapidly adopt new products. So, from a managerial point of view, they are of higher interest. In the context of complex networks, this naturally leads to the notion of community, i.e. a group of nodes with denser relationships, compared to the rest of the network.

Burt [START_REF] Burt | Structural Holes and Good Ideas[END_REF] and Perry-Smith [START_REF] Perry-Smith | Social yet creative: The role of social relationships in facilitating individual creativity[END_REF] showed structural holes improve the emergence of new ideas. In their analysis of firm innovativeness, Simon and Tellier [START_REF] Simon | Créativité et réseaux sociaux dans l'organisation ambidextre[END_REF] differentiated two kinds of innovativeness: exploitation and exploration. They showed groups with denser inner-connections were more efficient to diffuse ideas, but rupture innovations were less likely to happen in those parts of the firm. These denser groups can also be seen by people as stressful areas which constrain them too much, preventing any behavior opposed to the dominant one. In this context, people sometimes rely on persons not belonging to their community [START_REF] Rose | La constitution de liens faibles: une passerelle pour l'adaptation des immigrantes centroamericaines mères de jeunes enfants a Montréal[END_REF] or weakly connected [START_REF] Granovetter | The Impact of Social Structure on Economic Outcomes[END_REF]. Then, detecting communities can also, by contrast, reveal the zones of lower link density, or structural holes. It additionally allows a deeper study of the network structure by performing a centrality analysis. Indeed, people located in-between communities often play specific roles because of their central position [START_REF] Sureh | Viral distribution potential based on active node identification for ad distribution in viral networks[END_REF]. Interestingly, this last point brings us back to the local approach, illustrating how complementary they are: a global approach can be used to locate persons of interest, which can then be studied more attentively.

Besides this complementary nature and the fact a global approach seems necessary to improve our understanding of social networks and their effects, it is rarely adopted in the fields of Marketing and Business Sciences. Moreover, when it is the case, authors generally do not use a systematic method. For instance, the works cited in the previous paragraphs [START_REF] Simon | Créativité et réseaux sociaux dans l'organisation ambidextre[END_REF][START_REF] Perry-Smith | Social yet creative: The role of social relationships in facilitating individual creativity[END_REF] do not use a precise definition of the concept of community and do not intend to identify all communities present in the studied network. We see two possible reasons for this. First, this kind of analysis is computationally far more demanding than local approaches. It relies on relatively new tools (both theoretically and practically speaking), making intensive use of modern computers. Because of this novelty, they do not have penetrated Business Science deeply yet. Second, and more importantly, practical extraction of social networks is a difficult and costly task [START_REF] Chollet | L'analyse des réseaux personnels dans les organisations : quelles données utiliser ?[END_REF][START_REF] Doyle | The role of social networks in marketing[END_REF], because the information it requires is often difficult to access and thereby expensive.

Let us consider data according to two axes: the cost axis and the individual vs. relational axis. In the latter, individual refers to data describing only one person, whereas relational points out data concerning two (or more) persons. On the first axis, we can distinguish three kinds of data, differing both by the nature of the information they convey and on how difficult and costly they are to obtain. First, factual information is the most easily accessible; it corresponds to acknowledged, generally publicly available, facts. For individual data, we can cite for example social status, gender, age, etc. For relational data, it can take the form of communication streams such as email exchanges, lists of collaborations, etc. Second, what we call behavioral information can either result from observations or be obtained directly by interrogating the persons of interest.

For individual data, it describes how some person reacts to a given situation, whereas for relational data, the concern will be put on interactions between people, for instance by measuring the time workers spend together in a firm. Third, sentimental information is related to feelings and thoughts. It is the most difficult to retrieve, since it cannot be accessed in other way than more or less direct questions. For individual data, it is for instance brands representations, firm image or products preferences. For relational data it corresponds to feelings (friendship, love, hate, admiration…) people have for each other. Sentimental relational data can be recovered through questions of the sociometric form, where each person is asked to list his acquaintances and to quantify the strength and orientation of their relationships. This so-called sociometric approach is considered to be both the most efficient, in terms of quality of the retrieved relationships, and the most difficult to apply [START_REF] Chollet | L'analyse des réseaux personnels dans les organisations : quelles données utiliser ?[END_REF]. Extracting a social network requires relational data, which is globally more difficult and costly to gather than individual data [START_REF] Evrard | MARKET: Etudes et recherches en Marketing[END_REF]. Indeed, most available factual data focus on single persons (resumes, archives, surveys…), observing interactions in a whole population obviously requires more resources than concentrating on a single individual, and making people speak about others is an even more sensitive task than making them reveal personal details.

From this data-related difficulty regarding social networks extraction, a question arises: can the information conveyed by social networks be retrieved by other, less expensive, means? In this work, we try to tackle this issue through the angle of community detection. We analyze data coming from a survey conducted in a population of university students. Its questions targeted both relational data, with a sociometric approach, and individual data, including factual, behavioral and sentimentalcentered questions. From the relational data, we extract a social network, in which we detect communities. In parallel, we apply a classic cluster analysis on individual data, in order to obtain clusters of students. The comparison of individual and relational information is performed through an analysis of similarities and differences between the two kinds of groups. We additionally tackle the problem of community composition by analyzing them in terms of individual data. In this article, we present only the first stage of our work, in which we restrict our analysis to factual individual data only, ignoring behavioral and sentimental individual data for now, for several reasons. First, according to our data typology, it is diametrically opposed to the sociometric approach used to build our social network (inexpensive individual vs. expensive relational data), and should therefore lead to contrasted results. Second, these data do not need any pre-processing and are straightforward to interpret. We hence hope to be able to determine if some attributes are more important than others in the composition of communities. This is important from a managerial perspective, because it is related to the mechanisms leading to the observed communities and would allow predicting community membership without requiring the costly process of relational data collection. This article is organized as follow. In section two, we describe the survey we set to collect data, focusing on the parts used in the present work. We also give a short description of the tools used to analyze them: community detection, cluster analysis, and discriminant analysis. In section three, we present our results and compare the groups estimated on relational and individual data. We propose some arguments to explain how communities are related to individual information, and elaborate a discriminant model for student community membership. In the last section, we highlight the original points of our study, discuss its limitations and explain how it can be continued.

II. METHODS

We conducted two different analyses. The first is a comparison of groups estimated independently from the individual and relational data, resulting in so-called clusters and communities, respectively. The second is a study of the communities composition in terms of individual factual data. In this section, we describe first how we gathered the data, and which part of them was used in this study. We then present the methods used to estimate and compare groups of students. Finally, we briefly describe the discriminant analysis approach applied to study community composition.

A. Data Collection

The Galatasaray University (GSU) is a small Turkish public institution of about 2000 students, located in Istanbul, near the Bosphorus. It offers a wide variety of courses (sociology, economics, international studies, management, philosophy, computer science, engineering, law…) taught mainly in French. In Turkey, students enter universities after having passed a national competitive examination called ÖSS. The ranking they get at this occasion is very important, because it has a direct effect on the set of universities and departments they can choose to study in. The GSU is one of the top universities in several fields, and as such it attracts students with very high rankings. For most students, the name of the university itself is more important than the actual standard of the department they are going to enter. This particular university can also recruit students directly from Turkish French-speaking high schools, thanks to a specific internal examination. Approximately two thirds of the students are undergraduates and will get a Lisans (i.e. License, or BS) diploma, the rest being Master and PhD students. Each department has a promotion of about 30 students per level. Community and cultural life is highly developed; the university counts forty sports clubs or cultural associations. There is a very strong feeling of belonging to a group, enhanced by the fact the name Galatasaray also refers to a prestigious high school, a popular association football club, and various other cultural and sporting structures. After the university, very strong ties remain between GSU alumni, which usually help each other professionally.

In this context, we have conducted a study on the social network of current GSU students. A university can be considered as a relatively close system for students, in the sense most of their friends also belong to it, making it an appropriate field of investigation. Accordingly to the previous description, this seems to be particularly true for the GSU. Our study is based on a survey taking place at several periods, in order to be able to study some of the network dynamics. The results presented here are limited to data obtained during the first phase of the overall research project, which took place during spring 2009 and involved 224 respondents mainly at the Lisans level. We designed a questionnaire focusing on social and personal attributes, social interactions (especially in the daily university environment), purchasing behavior and favorite brands. The questions can be distributed into three different thematic parts, although this separation does not appear in the questionnaire, voluntarily. The first one concerns factual data: age, gender, clubs or associations membership, school situation, previous high-school. The second part focuses on the student's behavior relatively to his friends: nature of the communication means he uses (cell phone, Facebook, Skype...); and also concerning his shopping habits, information sources, buying behavior. The third part concerns his feelings about the university, his vision of his relationships with his friends, his desires, goals and favorite brands. All questions were designed to gather individual data, i.e. information limited to the student himself, except one, which was dedicated to relational data, i.e. data involving two students. We adopted a classic sociometric approach, consisting in asking the student to name the peers he finds the most important in his everyday life, and to quantify these relationships on a scale ranging from -5 (hate) to +5 (love). A website was created to gather the responses. Part of the required information was very personal and sensitive, so a specific procedure was set to guarantee perfect anonymity, replacing all names by meaningless codes.

As stated before, in this work, we focus only on a part of the gathered data. First, the relational data (sociometric question) are used to build the social network, which, in turn, is used to identify communities. In this first study, we chose to analyze a simple network, i.e. containing undirected and unweighted links, for interpretation reasons and because all the well-proven community detection tools are dedicated to this type of networks. For this purpose, we ignored the strength and orientation of the relationships when we extracted the network. In other terms, a bilateral link is present between two network nodes when at least one of the considered students cited the other, or both cited each other. Consequently, the network contains more nodes (552) than we had respondents (224), since some cited persons did not answer during this phase of the survey. Second, factual individual data was used to estimate clusters of students, in order to be subsequently compared to communities. The complete list of factual individual attributes is given in table I. In the rest of the document, we will refer to these data simply as the attributes.

B. Groups Identification

We performed the clustering analysis using the Two-Step tool available in PASW 18 (SPSS Inc.). It is an implementation of a classic algorithm [START_REF] Zhang | BIRCH: An efficient data clustering method for very large databases[END_REF], able of processing both numeric and nominal data, which was our case. This implementation optimizes a probabilistic criterion (AIC or BIC) to reduce the intra-cluster distance and increase the inter-cluster one. Different distance functions are available, log-likelihood or Euclidean distance; the log-likelihood has to be used when applied to nominal data. Unlike many clustering algorithms, this one is not hierarchical, so the clusters estimated at step k are not necessarily contained in those from step k+1 or k-1. This implementation is designed to estimate automatically the optimal number of clusters in terms of the selected probabilistic criterion. We applied Two-Step to all possible combinations of factual individual attributes, in order to get a wide range of partitions and be able to select the optimal one.

To identify network communities, we used a set of recent algorithms. Unlike for cluster analysis, there is no difficulty to select data here, since these algorithms can only be applied to the network extracted from the relational data. We chose to apply several algorithms in order to ensure community stability. Fast Greedy [START_REF] Newman | Finding and evaluating community structure in networks[END_REF] is a hierarchical agglomerative algorithm relying on a greedy approach to optimize a networkspecific criterion called modularity. Walktrap [START_REF] Pons | Computing communities in large networks using random walks[END_REF] is also a hierarchical agglomerative algorithm, but it uses a random walk-based definition of inter-node distance to identify communities. Edge-betweenness [START_REF] Girvan | Community structure in social and biological networks[END_REF] is a hierarchical divisive approach based on a link centrality measure: it iteratively removes the most central links to discover the communities. Spinglass [START_REF] Reichardt | Statistical mechanics of community detection[END_REF] is another method optimizing modularity, relying on an analogy between the statistical mechanics of complex networks and physical spin glass models. Modularity is a measure defined by Newman [START_REF] Newman | Finding and evaluating community structure in networks[END_REF] to estimate the quality of a network partition. Its theoretical maximum value is one, but in practice, it is related to the network structure, and cannot be reached in all networks. When considering real-world networks, partitions whose modularity is at least 0.7 are considered to be very good [START_REF] Tasgin | Community Detection in Complex Networks Using Genetic Algorithms[END_REF][START_REF] Newman | Modularity and community structure in networks[END_REF]. Modularity is also used in Fast Greedy Walktrap and Edge-betweenness to select the best cut in the generated hierarchy of partitions, and therefore determine the optimal number of communities. All four algorithms are available in the iGraph library [START_REF] Csardi | The igraph software package for complex network research[END_REF].

To compare the groups estimated by the previously described approaches, we chose the adjusted Rand index (ARI), which is widely used to measure similarity between partitions of a given dataset. The original Rand index (RI) [START_REF] Rand | Objective Criteria for the Evaluation of Clustering Methods[END_REF] is defined as RI=(a+d)/(a+b+c+d), where a (resp. d) corresponds to the number of pairs whose elements belong to the same (resp. different) group(s) in both partitions, and b (resp. c) to the number of pairs whose elements belong to the same group in the first (resp. second) partition, whereas they belong to different groups in the second (resp. first) one. The adjusted version [START_REF] Hubert | Comparing partitions[END_REF] is defined as ARI=(RI-E)/(1-E), where E is the amount of similarity expected to be due to chance. The upper limit of this measure is 1 (the two partitions are exactly the same). The value 0 indicates a partial overlap, equivalent to what would be observed if both partitions were random (i.e. RI=E). Negative values indicate a strong divergence between the partitions. The ARI was used first to compare the partitions estimated by the various community detection algorithms, and second to compare these same partitions with those resulting from the Two-Step cluster analysis.

The second part of our analysis consisted in elaborating a model of the composition of communities, on the basis of the attributes. We used the classic discriminant analysis algorithm implemented in PASW 18, which builds a predictive model for group membership, under the form of a set of classification functions. Each function is a linear combination of the attributes providing the highest separation between the reference groups. The model is constructed iteratively, by estimating the functions one-by-one. Each additional function is fitted to improve the overall quality of the model. The process ends when the maximal number of functions is reached (it depends on the number of attributes and groups), or when the model allows to successfully classify some proportion of instances. The model quality can be assessed by using it to process the groups for some instance set, and then comparing these estimations to the actual groups. Compared to other approaches, discriminant analysis has the advantage of explicitly highlighting which attributes are the most important to determine the group membership of an instance. As we stated in the introduction, group membership has an effect on decision making, so the predictive abilities of the model obtained from discriminant analysis has an indisputable interest in the field of Marketing and Business Science.

III. RESULTS AND DISCUSSION

A. Groups Analysis and Comparison

Our presentation of the results follows the approach we presented in section two. First, to identify clusters, we applied Two-Step on all possible combinations of attributes. We obtained the best results using the log-likelihood-based distance and the BIC (Bayesian information criterion) optimization criterion. In most cases, the data could not be discriminated and the process ended up with a single cluster as the optimal partition. This means the respondents' distribution in the space of considered attributes was too homogeneous, with no areas of higher or lower density to allow clear separation. In other terms, these attributes were not conveying enough information to allow a proper clustering. In a few cases, significant clusters were identified, though. The best results were obtained using three attributes: Gender, Department, and Class, leading to an optimal number of 4 clusters. The fact the quality of the clusters depends strongly on the selected attributes is important, because it shows attributes are not equivalent, and the mentioned ones carry most of the factual individual information.

Before performing community detection social network extracted from our relational its isolated nodes. This is a classic proce algorithms consider separated compone communities, leading to many meaningless c such nodes are present. We applied Edge-Greedy, Spinglass and Walktrap to the unwe resulting network. The optimal partitio modularity contain 23, 22, 29 and respectively. The first three algorithms le partitions, with ARI values around 0.75. Walk with ARI values around 0.6 when co algorithms. We can conclude we have a g between most algorithms, and the detected rather stable. Consequently, we decided to partition to be compared with the clusters individual data. We chose the partition e Greedy, represented in fig. 1. Its modularity the highest value over all tested algorithms. F the smallest number of partitions and is th comparable to our 4 clusters.

Our first comparison consisted in consid partitions estimated by Two-Step and Fast G observation, we performed two cing Fast Greedy and Two-Step 22 clusters, respectively. Fast approach, so it is rather 4 communities by selecting a f partitions it outputs. Of course, ower modularity (hence quality) 2 communities). The comparison and the 4 optimal clusters from ower ARI value of 0.001. This ese communities correspond to community. The modularity processed dy managed to identify it well. Isolated merges of the 22 communities considered at first. Two-Step is not hierarchical, so we had to apply the algorithm again, forcing it this time to estimate 22 clusters. Unlike Fast Greedy, there is no reason, from the algorithm perspective, for these clusters to be related to the 4 previous ones. Again, we tested all possible combinations of attributes. It is noteworthy that 22 was never the optimal number of clusters, and the obtained partitions had generally poor quality in the sense they did not reach high BIC values. We then compared these partitions with Fast Greedy optimal partition of 22 communities. Most Two-Step partitions had poor ARI values, sometimes even worse than random partition (i.e. negative values). Nevertheless, four partitions led to ARI values significantly different from zero. Table II sums up the attributes used to estimate these clusters, and the ARI value resulting from their comparison with the communities. These values are intermediary, which seems to indicate the individual attributes used during the clustering process contain a part of the information underlying the network community structure. So on the one hand, we were able to use individual data to identify clusters which are relatively close to (or rather: not significantly different from) the communities estimated from relational data. But on the other hand, the corresponding partitions have very low quality when considering how they separate the space of attributes. Moreover, some of the selected attributes are highly correlated (Category, City and Specialization). This seems to confirm our previous observation regarding the difference in the nature of the information conveyed by the individual and relational data. In summary, the various comparisons we conducted between the groups estimated by the cluster analysis approach and those identified by the community detection algorithms, generally lead to close to zero ARI values, meaning the overlap between the corresponding partitions is very low. However, in some specific cases, appropriate combinations of attributes resulted in ARI values significantly different from 0. Thus, a link, even if a tenuous one, seems to exist between some individual attributes and the communities derived from the relational data. The highest ARI value was obtained by taking into account a great deal of individual factual data, so this link is far from being obvious. The next step in our study consisted in performing a discriminant analysis to assess in which part the repartition of the students in the different communities is determined by their attributes.

B. Composition of the Communities

For the discriminant analysis, we used the communities as reference groups, in order to elaborate a model which would be able to estimate them, based on certain attributes. All attributes were used, since we opted for an exploratory approach. The selected algorithm automatically detects and discards correlated attributes, which are therefore not a problem here. Community sizes were used to compute the prior membership probabilities.

Only three attributes were found to be significantly discriminant. By order of decreasing significance, they are: the class (year of study in the university), the type of entrance examination (national or internal) and the university department. The other attributes did not convey any additional information useful for the prediction of the communities. The three most explicative attributes are only weakly correlated to each other (with values between -0.241 and 0.009). On their basis, the algorithm estimated a system of three functions, constituting the predictive model. For a given student, this model allows processing his membership probability for any community, the most probable one being considered as its estimated community. The overall comparison between estimated and actual communities gave a 37.2% success rate. This rate is very low, but still significantly different from zero, like the intermediate ARI values found in the previous section when comparing clusters and communities.

The fact the Class and Entrance attributes are more discriminant than the department could be explained by a specificity of the GSU. Students integrating this university come from all parts of Turkey; they have very different skills and levels, both from the academic and linguistic perspectives. In particular, some of them have been speaking French since nursery school, whereas others never practiced this language before entering the GSU. For this reason, before starting the actual Lisans degree, they must follow a preparatory class for one or two years, including an intensive French course. Most students recruited via the national examination do not speak French and have to follow the two-year-long preparation. All students which succeeded in the internal examination speak French and are prepared for only one year. During these preparatory years, all departments are mixed, because students do not follow yet specialized classes, but only French, methodological and common-core classes. We suppose this mixing make students develop cross-departmental relationships more easily. Moreover, this takes place during the first university years, and in a very specific context for many students: they are far from home (Turkey is a large country), and family is very important in the Turkish society. For all these reasons, we think these relationships last even after the end of the preparatory program, when students enter specific departments and are separated from most of their preparatory fellows. The class and entrance attributes are directly linked to the composition of the preparatory study groups, and this may be a reason why they are the most discriminant relatively to the observed student communities. The entrance attribute has additional implications, which can be linked to its observed discriminant power. First, due to their better understanding of the French language, students selected via the internal examination tend to stay together in their Lisans years. More importantly, most of them come from a small set of Frenchspeaking high-schools with very strong identities. For instance, the Galatasaray high-school (a centuries-old French-speaking public institution dating back to the Ottoman Empire) has a powerful association of alumni, very tightly bound to the diplomatic, political, industrial and business worlds. Finally, a social factor should also be mentioned, since most of these French-speaking high-schools are private and accessible only to middle and upper classes. Their standards of living, aims and preoccupations can be different from students selected through the national examination, some of which comes from very poor backgrounds. The fact is that students recruited through the two different examinations do not mix so much. The third discriminant attribute (Department) was more predictable, because spending daily hours together, working, interacting and sharing the same classroom make people closer and is favorable to the apparition of strong relationships (be it friendship or enmity). Some factors have surprisingly no influence on the repartition between communities. Gender, which could be supposed to have a central role in student interaction, especially in the case of young persons evolving in a new environment, far from their home and family, does not seem to affect the way communities are formed. In a lesser degree, we expected high-school specialization (mathematics, literature…), and home city to have a noticeable effect. The life in Istanbul is clearly more cosmopolite, liberal, and culturally richer than in most parts of Turkey. For this reason, persons living in Istanbul sometimes have some sort of superior attitude towards people coming from rural environments, which can be aggravated by the differences of social status, and we expected this to appear in the composition of communities.

Of course, the scope of all these comments must be qualified, because they hold only for one third of the students, for which the mentioned discriminant attributes allow correctly predicting the community. For most of the population, we were not able to find a way to match communities and attributes, that is to find a link between the relational and individual data. This goes in the same direction than our results from the group comparisons, i.e. relational and individual data seem to convey different information, at least partially.

IV. CONCLUSION

We gathered data from a population of university students, using a survey. From these data, we retained only the individual factual and relational information, leaving the rest of the individual information for further exploration. We extracted a social network from the relational information, and detected 22 communities thanks to the Fast Greedy algorithm [START_REF] Newman | Finding and evaluating community structure in networks[END_REF]. Each community is characterized by a denser interconnection compared to the rest of the network. In parallel, we applied the Two-Step clustering approach [START_REF] Zhang | BIRCH: An efficient data clustering method for very large databases[END_REF] on the individual data, leading to an optimal partition of 4 clusters for the considered students. Note all combinations of attributes were considered during this process. We compared these partitions using the adjusted Rand index (ARI) [START_REF] Hubert | Comparing partitions[END_REF], and find out there was no significant overlapping between them. To our knowledge, this type of comparison was never performed before, at least in the domain of Business Science. We then extended our study by comparing each optimal partition (clusters and communities) to non-optimal partitions obtained by forcing the number of groups to match the optimal opposite count (4 and 22, respectively). This resulted in close to zero ARI values when the communities were forced to 4, and intermediate values (around 0.3) but essentially poorly separated clusters when these were forced to 22. We concluded that, on these data, the information conveyed by the relational and factual individual data seem to differ significantly, at least in terms of groups of students.

The second part of our analysis aimed at identifying the most discriminant attributes relatively to the communities. For this purpose, we performed a discriminant analysis [START_REF] Zhang | BIRCH: An efficient data clustering method for very large databases[END_REF], using the communities as reference groups. We found out the year of study, the type of examination taken to enter the university and the current department were sufficient to correctly predict the community of 37.2% of the respondents. On the one hand, this low rate confirms our observation regarding the limited overlapping between clusters and communities. On the other hand, it can be considered as relatively high, regarding the fact only 3 attributes are used to select one community among 22 possible. Even if it is obvious they do not allow explaining completely how the students are distributed over the communities, we proposed some interpretations regarding why a community can be correctly predicted from these attributes for more than one third of the students. Indeed, being able to predict communities is of utmost interest in the fields of marketing and management. For example, young students are intense consumers of technological products such as mobile phones or MP3 players, or fashion product like clothes, jewels and make-up. Communities are supposed to have a strong effect on the buying process and decision making [START_REF] Hyunsook | Comparing fashion process networks and friendship networks in small groups of adolescents[END_REF]. Consequently, any mean able to provide more information regarding potential client membership is extremely relevant and worthwhile.

We consider this work as a first step in the analysis of our field results. Consequently, it suffers from some limitations we plan to solve quickly in the forthcoming articles. First, we focused on the factual part of the individual information. The next step will consist in talking into account behavioral and/or sentimental individual data: maybe they convey the information necessary to define clusters exhibiting a better overlap with the communities. Second, we extracted the social network by considering only the presence of relationships between pairs of students: we ignored completely their orientation and strength. Consequently, the social network links are neither directed nor weighted. This first approach was partly constrained by the fact most community detection algorithms work only on this kind of network. This information is extremely important though, and could lead to very different communities, worth comparing with clusters. Another interesting point would be to allow a student to belong to several groups at the same time. But even less community detection algorithms allow this [START_REF] Derenyi | Clique percolation in random networks[END_REF], and it also raises difficulties from the cluster analysis perspective.

Our work also suffers structural weaknesses, inherent to the context of the study. First, the survey was conducted in a small institution, with specific characteristics, which makes it difficult to generalize our results to any situation. This problem could be addressed by performing similar studies in other contexts, and for this purpose we are trying to start collaborations with searchers from other universities. Second, and more importantly, the data we analyzed is far from being complete, since it represents a relatively small part of the total number of students in the GSU. This response rate is normal for such a survey, especially considering the fact students participate on their behalf only. To improve this rate, we conducted our survey again, one semester later (it is currently ongoing). This should both provide additional respondents, and add an interesting dynamic dimension to those who participated to both surveys.

Figure 1 .

 1 Figure 1. Communities detected by the Fast Greedy a for this partition is 0.88, i.e. a high value, which has tw

TABLE I

 I

	.	FACTUAL INDIVIDUAL ATTRIBUTES USED FOR BOTH
	CLUSTERING AND DISCRIMINANT ANALYSES
	Attribute	Type	Description
	Gender	binary	Male vs Female
	Department	nominal	The GSU has 12 departments
	Class	ordinal	Current year (Preparatory and Lisans): 6 different levels
	Entrance	binary	Entrance examination: National ÖSS vs Internal French-speaking
	High-School	nominal	High-school name
	Category	nominal	High-school type: 6 different categories
	City	binary	High-school city: Istanbul vs. not Istanbul
	Specialization	nominal High-school specialization: 17 categories
	Clubs	binary	Forty activities inside and outside the GSU

TABLE II .

 II ADJUSTED RAND INDEX VALUES BETWEEN FOUR 22 CLUSTERS PARTITIONS ESTIMATED BY TWO-STEP, AND THE OPTIMAL FAST GREEDY PARTITION (ONLY THE PARTITIONS WITH HIGHEST ARIS ARE REPRESENTED)

	Considered Attributes	ARI
	Gender, Department, Class, Entrance, Category, City, Specialization	0.423
	Category, City, Specialization	0.291
	Department, Class, Entrance	0.320
	Gender, Department, Class, Entrance, Category, City, Specializarion, Clubs	0.286


Günce Keziban Orman
email: keziban.orman@uekae.tubitak.gov.tr

Vincent Labatut
email: vlabatut@gsu.edu.tr

Relative Evaluation of Partition Algorithms for Complex Networks

Complex networks partitioning consists in identifying denser groups of nodes. This popular research topic has applications in many fields such as biology, social sciences and physics. This led to many different partition algorithms, most of them based on Newman's modularity measure, which estimates the quality of a partition. Until now, these algorithms were tested only on a few real networks or unrealistic artificial ones. In this work, we use the more realistic generative model developed by Lancichinetti et al. to compare seven algorithms: Edge-betweenness, Eigenvector, Fast Greedy, Label Propagation, Markov Clustering, Spinglass and Walktrap. We used normalized mutual information (NMI) to assess their performances. Our results show Spinglass and Walktrap are above the others in terms of quality, while Markov Clustering and Edge-Betweenness also achieve good performance. Additionally, we compared NMI and modularity and observed they are not necessarily related: some algorithms produce better partitions while getting lower modularity.

Introduction

Complex networks have recently become very popular to model systems of interacting objects. They have been used in very different application domains, such as physics, biology, computer networks and social science [START_REF] Newman | The structure and function of complex networks[END_REF].

Network partition, also called community detection, consists in looking for subsets of nodes densely interconnected relatively to the rest of the network [START_REF] Newman | Finding and evaluating community structure in networks[END_REF]. It is one of the most active research areas in complex networks. Many different community detection algorithms have been proposed. They are generally based on classical hierarchical clustering principles adapted to graphs, or use optimization methods. Most of them use Newman's modularity measure [START_REF] Newman | Finding and evaluating community structure in networks[END_REF], which estimates the quality of a given network partition relatively to the structure of the considered network.

Authors traditionally test their community detection algorithms on a few real networks [START_REF] Girvan | Community structure in social and biological networks[END_REF][START_REF] Falkowski | DENGRAPH: A Density-based Community Detection Algorithm[END_REF][START_REF] Liu | Email Community Detection Using Artificial Ant Colony Clustering[END_REF][START_REF] Hoff | Latent space approaches to social network analysis[END_REF][START_REF] Newman | Fast algorithm for detecting community structure in networks[END_REF][START_REF] Raghavan | Near linear time algorithm to detect community structures in large-scale networks[END_REF]. But building such networks is a costly and difficult task, and determining reference communities is generally performed manually. This possibly results in small networks, where actual communities are not always defined objectively, or even known. Additionally, it is not possible to control the networks structural parameters such as degree distribution, transitivity or average distance. Consequently, the algorithm is tested on a very specific and limited set of features.

Artificial networks overcome these limitations, by allowing to control the networks structure, to define the communities a priori and to generate many networks randomly. This is the reason why many authors also use them to test their algorithms [START_REF] Newman | Finding and evaluating community structure in networks[END_REF][START_REF] Girvan | Community structure in social and biological networks[END_REF][START_REF] Newman | Fast algorithm for detecting community structure in networks[END_REF][START_REF] Pons | Computing communities in large networks using random walks[END_REF][START_REF] Reichardt | Detecting Fuzzy Community Structures in Complex Networks with a Potts Model[END_REF] But simple and not very realistic generative models such as Newman's [START_REF] Girvan | Community structure in social and biological networks[END_REF] are used, hence the results cannot be trustfully transposed to real networks [START_REF] Danon | The effect of size heterogeneity on community identification in complex networks[END_REF][START_REF] Lancichinetti | Benchmark graphs for testing community detection algorithms[END_REF]. Some recent works introduced more realistic models, able to mimic some of the real networks features. For instance, Lancichinetti et al. [START_REF] Lancichinetti | Benchmark graphs for testing community detection algorithms[END_REF] proposed a model able to generate networks with controlled power-law degree and community size distributions.

In this work we used this model to generate a set of artificial networks with various sizes and properties, and applied seven different community detection algorithms on them. The normalized mutual information measure [START_REF] Fred | Robust Data Clustering[END_REF][START_REF] Danon | Comparing community structure identification[END_REF] allowed us to assess the quality of the results and compare the considered algorithms. Additionally, we studied the behavior of the modularity measure in function of the algorithms performances.

In section 2, we describe the general mechanisms of community detection, define the modularity measure, and present the algorithms we chose to compare. In section 3, we explain how we generated our test set of artificial networks, and describe the normalized mutual information measure. In section 4, we present and discuss our results concerning the compared algorithms performances and modularity levels.

Community detection

General principle

Early solutions in community detection are based on hierarchical approaches whose result is a tree of communities called dendrogram. On the one hand, agglomerative approaches [START_REF] Newman | Fast algorithm for detecting community structure in networks[END_REF][START_REF] Pons | Computing communities in large networks using random walks[END_REF][START_REF] Clauset | Finding community structure in very large networks[END_REF] start with as many communities as nodes, each node having its own community, and iteratively merge them until only one giant community remains. On the other hand, divisive approaches [START_REF] Girvan | Community structure in social and biological networks[END_REF] start with one community containing all nodes, and iteratively split the communities until each node constitute one community. The merged or split communities are chosen accordingly to some distance or similarity function that allows detecting which communities are the most similar (agglomerative approach) or different (divisive approach). What distinguishes algorithms is mainly the nature of the distance or similarity function.

Some other approaches are optimization-based and use a heuristic function to estimate the quality of a network partition [START_REF] Newman | Finding community structure in networks using the eigenvectors of matrices[END_REF][START_REF] Reichardt | Statistical mechanics of community detection[END_REF][START_REF] Van Dongen | Graph clustering by flow simulation[END_REF]. The general algorithm consists in first processing several partitions of the network (randomly or by following a fitting function) and second keeping the best one according to the estimated quality. This partition can then be refined in order to improve its quality.

The remaining approaches do not follow any common principle. For instance, some are inspired by other classical clustering approaches like densitybased clustering [START_REF] Falkowski | DENGRAPH: A Density-based Community Detection Algorithm[END_REF]; some are agent-based [START_REF] Liu | Email Community Detection Using Artificial Ant Colony Clustering[END_REF]; some allows finding overlapping communities (one node can be a part of several communities at once) [START_REF] Derenyi | Clique percolation in random networks[END_REF]; some use a latent space approach to process the probability for a node to belong to a community [START_REF] Hoff | Latent space approaches to social network analysis[END_REF].

Modularity

Many community detection algorithms rely on Newman's modularity [START_REF] Newman | Finding and evaluating community structure in networks[END_REF]. Some use it internally at each iteration, for instance as an optimization criterion. Some use it after the processing, for instance to select the best cut in a dendrogram built by a hierarchical approach. It is a costly measure to process, hence the numerous algorithms defined for its optimization [START_REF] Newman | Finding community structure in networks using the eigenvectors of matrices[END_REF].

Modularity was presented by Newman and Girvan [START_REF] Newman | Finding and evaluating community structure in networks[END_REF] to assess the quality of a network partition. They first define what could be called a community contingency matrix, whose elements represent the total fraction of links from a node in community towards a node in community . We are considering undirected networks, so and this matrix is symmetric. The sum on row or column is noted ∑ and represents the fraction of links with at least one node in community .

The modularity measure is then defined as the difference between the observed and expected fractions of links inside a community, summed over all communities:

The term corresponds to the observed fraction of links inside a community , and is an estimation of this value under the hypothesis of uniformly randomly distributed links.

When the communities are not better than a random partition, or when the network does not exhibit any community structure, is negative or null. Its superior limit is 1, which can be approached only if the network has a strong community structure and if the communities have been perfectly detected [START_REF] Newman | Finding and evaluating community structure in networks[END_REF].

Selected algorithms

Because we had many generated networks to process, we decided to focus first on fast and simple algorithms. When the result of the partition was a dendrogram, we used modularity to estimate its best cut.

Newman et al.'s Fast Greedy (FG) [START_REF] Newman | Fast algorithm for detecting community structure in networks[END_REF][START_REF] Clauset | Finding community structure in very large networks[END_REF] is modularity-based and relies on a hierarchical agglomerative approach. Its name is due to the use of a standard greedy method, making it relatively faster than earlier algorithms, and allowing it to process large networks.

Pons and Latapy's Walktrap (WT) [START_REF] Pons | Computing communities in large networks using random walks[END_REF] uses a hierarchical agglomerative method, where the distance between two nodes is defined in terms of random walk process. The random walks length must be specified through a parameter.

Girvan and Newman's Edge-betweenness (EB) [START_REF] Girvan | Community structure in social and biological networks[END_REF] uses a hierarchical divisive method based on a link centrality measure. At each step it removes the most central links, creating a hierarchy of communities.

Newman's Eigenvector (EV) [START_REF] Newman | Finding community structure in networks using the eigenvectors of matrices[END_REF] is a modularitybased optimization method inspired by graph partitioning techniques. It relies on the eigenvectors of a so-called modularity matrix, instead of the graph Laplacian used in classic graph partitioning.

Van Dongen's Markov Clustering (MC) [START_REF] Van Dongen | Graph clustering by flow simulation[END_REF] also uses random walks, but this time to perform optimization through a bootstrapping procedure. An inflation parameter allows controlling the granularity of the resulting communities: the higher this parameter, the smaller the communities.

Reichardt and Bornholdt's Spinglass (SG) [START_REF] Reichardt | Statistical mechanics of community detection[END_REF] is an optimization method relying on an analogy between the statistical mechanics of complex networks and physical spin models. A spin parameter represents the maximum number of communities the algorithm is allowed to find. [START_REF] Raghavan | Near linear time algorithm to detect community structures in large-scale networks[END_REF] uses the concept of node neighborhood and the diffusion of information in a network. Initially, each node is labeled with a unique value, representing its community. Then an iterative process takes place, where a node is given the label the most spread in its neighborhood.

Raghavan et al.'s Label Propagation (PG)

Method

Network generation

In many community detection works [START_REF] Newman | Finding and evaluating community structure in networks[END_REF][START_REF] Girvan | Community structure in social and biological networks[END_REF][START_REF] Newman | Fast algorithm for detecting community structure in networks[END_REF][START_REF] Reichardt | Detecting Fuzzy Community Structures in Complex Networks with a Potts Model[END_REF], artificial networks with a community structure are generated by using models comparable to Newman and Girvan's one [START_REF] Girvan | Community structure in social and biological networks[END_REF][START_REF] Newman | Fast algorithm for detecting community structure in networks[END_REF]. It relies on the principle of the Erdős-Rényi model [START_REF] Erdos | On random graphs[END_REF], and produce networks with a degree following a Poisson distribution. Yet, it is well known that in most real networks, the degree follows a power-law distribution [START_REF] Newman | The structure and function of complex networks[END_REF]. Networks with this property are called scale-free, because their degree distribution does not depend on their size (some other properties may, though). Moreover, in Newman and Girvan's approach, all the communities have the same size, whereas in real networks, community size is supposed to follow a power-law distribution too.

If we want our comparison to hold when the algorithms are applied on real networks, our artificial networks properties must be the most similar possible to those of real networks. For this reason, we chose to use a more recent generative model defined by Lancichinetti et al. [START_REF] Lancichinetti | Benchmark graphs for testing community detection algorithms[END_REF]. It allows generating random networks with a community structure and a power-law degree distribution. Moreover, the size of the resulting communities also follows a power-law distribution.

The model needs the following compulsory parameters: the number of nodes n, the desired average and maximum degrees, the exponent for the degree distribution, the exponent for the community size distribution, and a value called the mixing coefficient. The latter represents the average proportion of links between a node and other nodes located outside its community, 1 consequently being the proportion of links with other nodes located in the same community.

The generation is performed in three steps. First, the well-known configuration model [START_REF] Molloy | A critical point for random graphs with a given degree sequence[END_REF] is used to generate a scale-free network corresponding to the specified parameter. Second, the community sizes are drawn in accordance with the parameter, and each node is randomly affected to a compatible community. Compatible means here that the community size must be greater or equal to the node internal degree. Some specific mechanisms ensure the convergence of the processing, see [START_REF] Lancichinetti | Benchmark graphs for testing community detection algorithms[END_REF] for more details. Third, some links are rewired in order to respect the mixing coefficient. For a given node, the degree is not modified, but the ratio of internal and external links is changed so that the resulting proportion approximately respects .

For some of these parameters, we used values estimated from measurements on real networks. Experimental studies show that the coefficient usually ranges from 2 to 3 [START_REF] Newman | The structure and function of complex networks[END_REF][START_REF] Barabasi | Statistical mechanics of complex networks[END_REF]. The average and maximal degrees generally depend on the number of nodes in the network. For a scale-free network, it is estimated to be ~ [START_REF] Barabasi | Statistical mechanics of complex networks[END_REF] and ~ ⁄ [START_REF] Newman | The structure and function of complex networks[END_REF], respectively. The power-law parameter for the community size distribution is known to range from 1 to 2 [START_REF] Clauset | Finding community structure in very large networks[END_REF].

For n, the number of nodes, we could not afford using a realistic value because of computational constraints, so we limited the network size to 100 and 500 nodes. The parameter is of utmost importance, because it represents the community sharpness. For this reason, we generated networks with values in 0.05; 0.95 with a 0.05 step.

For each set of parameters, we generated 10 networks in order to deal with possible discrepancies in the networks properties due to the random nature of the generation process. In rare occasions, we observed networks with a few disconnected components. Some algorithms like Walktrap cannot be applied on such networks, so we decided to connect them uniformly randomly.

Performance assessment

Another important point is the assessment of the results quality, which must be reliable in order to compare efficiently the communities detected by the tested algorithms.

As we stated before, the modularity measure is a standard for assessing the quality of a network partition. But it was designed to be used as an estimation function to guide community detection algorithms when the actual communities are unknown. The computed value for a given situation depends on both the quality of the detected communities and of the nature of the network community structure.

This dependence to the network structure prevents from using modularity to compare algorithm performances on different networks. Furthermore, we will use artificial networks, whose communities are known a priori. In this context, modularity is not an appropriate measure, because it does not make use of this important information. For interpretation purposes, we nevertheless processed modularity for each partition.

In place of the modularity, we used the normalized mutual information measure (NMI). It has been used in the context of classical clustering to compare two different partitions of a data set [START_REF] Fred | Robust Data Clustering[END_REF]. It was shown to be an efficient way to assess the quality of estimated network communities by Danon et al. [START_REF] Danon | Comparing community structure identification[END_REF].

The measure is derived from a confusion matrix whose element represents the number of nodes put in community by the considered algorithm, when they actually belong to community . This matrix is usually rectangular, because the algorithm does not necessarily find the correct number of communities.

2 ∑ ∑ log ⁄ ∑ log ⁄ ∑ log ⁄
The terms and represent the sums of the row and column elements, respectively. If the estimated communities correspond perfectly to reality, the measure takes the value 1, whereas it is 0 when the estimated communities are independent from the actual ones.

Results and discussion

We analyzed the algorithms performances in function of the parameters used to generate the networks. The results were very similar for 100 and 500, so we will just discuss the latter here. It was found that and do not seem to significantly affect any of the algorithms: their (Pearson's) correlation to the results is always less than 0.06. On the contrary, has a strong effect (correlations below 0.5) and the average and maximum degrees exhibit non-trivial correlations (above 0.35). The left part of Fig. 1 shows the results for all seven algorithms, expressed in terms of NMI in function of . The plots take the form of reversed sigmoid functions. In other terms, for all algorithms, the performances stay high when is small, then start to decrease when reaches a certain value corresponding to an inflection point, and finally stabilize again at a lowest value. Indeed, an increase in makes the community structure vanish (the proportion of links directed outside the community gets bigger), and thus harder to be identified. Performances are close, but some differences exist however: the slope and the location of the inflection point vary according to the considered algorithm. FG and EV performances decrease almost linearly with , with an inflection point around 0.5. LP has the strongest slope, with an inflection point also around 0.5. For WT and SG, the slope is gentler and the inflection point is shifted towards 0.7. Finally, MC and EB have an even gentler slope, with an inflection point around 0.5; 0.6, and their minimal performances stay significantly above other algorithms results after the inflection point. Dispersion is not shown on the graph, because EV and LP performances can vary a lot (especially during the performance drop), making the plots difficult to read. Each point represents an average over 10 results, and this may not be enough to obtain stable values. The other algorithms do show very small dispersion, though.

The right part of Fig. 1 shows the same results, but this time assessed through Newman's modularity. For each algorithm, we observe an almost linear decrease until reaches 0.5; 0.6, and then stabilization around a lowest value. An interesting question is whether the relative order of the algorithms is the same when we consider NMI and modularity values. Indeed, modularity is known to have some flaws, for example it is sensitive to community size [START_REF] Danon | The effect of size heterogeneity on community identification in complex networks[END_REF] and it is possible to find partitions of Poisson random networks with relatively high modularity values, even though they have no community structure [START_REF] Guimerà | Modularity from fluctuations in random graphs and complex networks[END_REF]. A preserved order relatively to NMI would show that modularity constitutes a good estimation of the partition quality, since NMI uses the actual partition to assess the algorithms performances. When is below 0.5, we observe roughly the same relative order between NMI and modularity. There are a few exceptions though, like with 5, 3, 2: for a close to 0.5, MC is first for the NMI value but penultimate for the modularity. When is above 0.5, the order is not preserved at all. In the same example, when gets close to 1, the relative positions are different not only for MC, but for almost every algorithm.

Beside , the maximum and average degrees also have a significant effect on the observed performances. As Lancichinetti et al. also noticed for two other algorithms [START_REF] Lancichinetti | Benchmark graphs for testing community detection algorithms[END_REF], a higher degree makes the performances better. This is actually true only when is small enough. But when is above 0.5; 0.6, an 0 . 2 0 . 4 0 . 6 0 . 8 0. 0 0 .2 0 .4 0 .6 0. 8 1 .0

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 0.2 0.4 0.6 0.8 0. 0 0 .2 0 .4 0 .6 0. 8 1 .0 • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 0 . 2 0 . 4 0 . 6 0 . 8 0.0 0.2 0.4 0.6 0.8 1.0 • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 0.2 0.4 0.6 0.8 0.0 0.2 0.4 0.6 0.8 1.0 • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • Fast Greedy Eigenvector Normalized Mutual Information Modularity Walktrap Mixing Coefficient Mixing Coefficient

Spinglass

Label Propagation Markov Clustering

Edge-betweenness increase in the degree causes the performances to drop rapidly. The 0.5 value is very important, because when is above this threshold, each node has more links outside its community than inside. In other terms, the communities cannot be described anymore as "subsets of nodes densely interconnected relatively to the rest of the network". All the tested algorithms rely on this definition of the community concept, so it makes sense to observe a performance drop when it does not hold anymore. This is also true for the modularity measure, which relies on the same definition to estimate a partition quality. This explain the clear differences noticed between modularity and NMI when 0.5. It also explains why a degree increase has a positive effect when 0.5, whereas it is negative otherwise. Indeed, below 0.5, each link represents pertinent information in terms of discovering the community structure. A higher degree means more information, hence better performances. On the contrary, when 0.5, the links do not correspond to the community structure, therefore they are noise. A higher degree means more noise, making the community structure harder to find, and leading to lower performances.

What is extremely surprising in the presented results is EB and MC good performances for very high values. For instance, MC almost reaches a 0.8 NMI for 0.95 (

, which means it can nearly find the exact communities when the community structure does not actually exist. The only hypothesis we can advance to explain this observation is that NMI seems to be sensitive to the number of estimated communities, which may unrealistically increase the measured performances for algorithms tending to create many communities.

Since the definition of community holds only when 0.5, it makes no sense to compare the algorithms for higher values. Under these conditions, the criterion to select the best algorithm is to have the highest values on the 0,0.5 interval, which translate in a high initial value (i.e. for a small ), a strong slope and an inflection point located far on the right (high ). For a low average degree, MC has the best results, because it stays on top even when the communities are not clearly defined ( close to 0.5). LP, SP and WT are very close to MC; and EB, EV and FG performances are clearly below. When the average degree is higher, it is more difficult to discriminate the algorithms. EB, MC, SG and WT are excellent (close to the maximum until 0.5), with an advantage to SG and WT, whose performances start declining later. FG and LP have almost the same performances than for the lower degree, and they even decrease for EV, which means they are below the other algorithms.

Conclusion

In this paper, we compared seven different community detection algorithms, namely: Edgebetweenness (EB) [START_REF] Girvan | Community structure in social and biological networks[END_REF], Eigenvector (EV) [START_REF] Newman | Finding community structure in networks using the eigenvectors of matrices[END_REF], Fast Greedy (FG) [START_REF] Newman | Fast algorithm for detecting community structure in networks[END_REF][START_REF] Clauset | Finding community structure in very large networks[END_REF], Label Propagation (LP) [START_REF] Raghavan | Near linear time algorithm to detect community structures in large-scale networks[END_REF], Markov Clustering (MC) [START_REF] Van Dongen | Graph clustering by flow simulation[END_REF], Spinglass (SP) [START_REF] Reichardt | Statistical mechanics of community detection[END_REF] and Walktrap (WT) [START_REF] Pons | Computing communities in large networks using random walks[END_REF]. We used a set of artificial networks generated with the model defined by Lancichinetti et al. [START_REF] Lancichinetti | Benchmark graphs for testing community detection algorithms[END_REF], which allows randomly producing networks with a community structure and power-law degree and community size distributions. This model uses a parameter to control the communities sharpness, and we clearly stated that comparing algorithms was relevent only for 0.5. We used the normalized mutual information measure [START_REF] Fred | Robust Data Clustering[END_REF][START_REF] Danon | Comparing community structure identification[END_REF] to assess the algorithms performances.

For a low average degree, all algorithms perform relatively well, with MC clearly standing out, and EB, EV and FG performing below the other algorithms. For a higher average degree, EV and FG clearly have poor results relatively to the other algorithms, whose performances are so excellent it is difficult to discriminate them, especially EB, MC, SG and WT. WT and SG performs slightly better though, because their performance drop starts after the 0.5 threshold. To expose more important differences amongst the algorithms performances, it may be necessary to perform some further experiments with larger networks. Moreover, other factors than performance are also important for algorithms comparison, like for instance memory and time complexities. Here, for a comparable partition quality, WT and MC are much faster than EB and SG.

Of course, there are some limitations to our results. The generative model we used is more realistic than earlier ones, but it is based on the configuration model [START_REF] Molloy | A critical point for random graphs with a given degree sequence[END_REF], which is known to produce networks with no degree correlation and whose transitivity tends to zero for some parameters [START_REF] Newman | The structure and function of complex networks[END_REF]. On the contrary, real networks show non-null degree correlation (positive or negative), and their transitivity is high [START_REF] Newman | The structure and function of complex networks[END_REF]. Maybe this could be corrected by using another model instead, such as preferential attachment [START_REF] Barabási | Emergence of Scaling in Random Networks[END_REF] (or one of its variations), able to generate networks with more realistic properties. Of course there is no certainty about whether or not these properties would resist the modifications performed on the initial network by Lancichinetti et al's. [START_REF] Lancichinetti | Benchmark graphs for testing community detection algorithms[END_REF] generation process, when the community structure is created. Moreover, real networks properties are usually described commonly, but there may be strong differences between the various types of real networks such as social networks, biological networks, information networks, etc. [START_REF] Newman | The structure and function of complex networks[END_REF]. In that case, a proper test should compare algorithms on different types of corresponding artificial networks.

We compared the algorithms on networks containing 100 and 500 nodes only. Real networks are generally much bigger, in the order of tens of thousands or millions of nodes. For more significance, the algorithms should be tested on this type of networks, but this raises two problems: 1) processing community detection on such huge networks is significantly more time expensive, and 2) determining realistic values for the average and maximal degrees is difficult because of the heterogeneity observed in real networks for these properties. The second point is important, since we observed the performances vary strongly in function of these sole properties. We also limited this comparison to the fastest algorithms, again for computability and time reasons. A proper exhaustive test should consider more expensive algorithms (see [START_REF] Danon | Comparing community structure identification[END_REF]).

Fig. 1 . 2 and 3 .

 123 Fig. 1. Comparison of the seven algorithms results for 500, 2 and 3. On the first row, the average and maximum degrees are 5 and 15, and on the second row they are 30 and 90, respectively. Performance is expressed in terms of normalized mutual information on the left column, and modularity on the right one, in function of . Each point corresponds to an average over 10 generated networks.