Vincent Labatut

Nicolas Dugué

Anthony Perez

Identifying the Community Roles of Social Capitalists in the Twitter Network

In the context of Twitter, social capitalists are specific users trying to increase their number of followers and interactions by any means. These users are not healthy for the Twitter network since they flaw notions of influence and visibility. Indeed, it has recently been observed that they are real and active users that can help malicious users such as spammers gaining influence. Studying their behavior and understanding their position in Twitter is thus of important interest. A recent work provided an efficient way to detect social capitalists using two simple topological measures. Based on this detection method, we study how social capitalists are distributed over Twitter's friendto-follower network. We are especially interested in analyzing how they are organized, and how their links spread across the network. Answering these questions allows to know whether the social capitalism methods increase the actual visibility on the service. To that aim, we study the position of social capitalists on Twitter w.r.t. the community structure of the network. We base our work on the concept of community role of a node, which describes its position in a network depending on its connectivity at the community level. The topological measures originally defined to characterize these roles consider only some aspects of community-related connectivity and rely on a set of empirically fixed thresholds. We first show the limitations of such measures and then extend and generalize them by considering new aspects of the community-related connectivity. Moreover, we use an unsupervised approach to distinguish the roles, in order to provide more flexibility relatively to the studied system. We then apply our method to the case of social capitalists and show that they are highly visible on Twitter, due to the specific roles they occupy.

I. INTRODUCTION

Context. The last decade has been marked by an increase in both the number of online social networking services and the number of users of such services. This observation is particularly relevant when considering Twitter, which had 200 millions accounts in April 2011 [START_REF] Bosker | Twitter: We now have over 200 million accounts[END_REF] and reached 500 millions accounts in October 2012 [START_REF] Holt | Twitter in numbers[END_REF]. Twitter is mostly used to share, seek and debate about information, or to let the world know about daily events [START_REF] Java | Why we twitter: understanding microblogging usage and communities[END_REF]. The amount of information shared on Twitter is considerable: there are about 1 billion tweets posted every two and a half days [START_REF] Rodgers | Behind the numbers: how to understand big moments on Twitter[END_REF]. While focusing on microblogging, Twitter can be considered as a social networking service, since it includes social features. Indeed, to see the messages of other users, a Twitter user has to follow them (i.e. make a subscription). Furthermore, a user can retweet [START_REF] Suh | Want to be retweeted? large scale analytics on factors impacting retweet in twitter network[END_REF] other users' tweets, for instance when he finds them interesting and wants to share them with their followers. Besides, users can mention other users to draw their attention by adding @UserName in their message. Some Twitter users are trying to use these particular properties to spread efficiently some information [START_REF] Ghosh | Understanding and combating link farming in the twitter social network[END_REF]. One of the simplest way to reach this objective is to gain as many followers as possible, since this gives a higher visibility to the user's tweets when using the network search engines [START_REF] Ghosh | Understanding and combating link farming in the twitter social network[END_REF].

Social capitalists. These specific users are called social capitalists. They have been recently observed and studied by Ghosh et al. [START_REF] Ghosh | Understanding and combating link farming in the twitter social network[END_REF] in a study related to link-farming in Twitter. They noticed in particular that users responding the most to the solicitation of spammers are in fact real, active users. To increase their number of followers, social capitalists use several techniques [START_REF] Ghosh | Understanding and combating link farming in the twitter social network[END_REF], [START_REF] Dugué | Social capitalists on Twitter: detection, evolution and behavioral analysis[END_REF], the most common one being to follow a lot of users regardless of their content, just hoping to be followed back. Because of this lack of interest in the content produced by the users they follow, social capitalists are not healthy for a service such as Twitter. Indeed, this behavior helps spammers gaining influence [START_REF] Ghosh | Understanding and combating link farming in the twitter social network[END_REF], and more generally makes the task of finding relevant information harder for regular users. Studying their behavior and understanding their position in Twitter is therefore a very important task to improve the service, since it can allow designing better search engines or functioning rules. In a recent work, Dugué and Perez [START_REF] Dugué | Social capitalists on Twitter: detection, evolution and behavioral analysis[END_REF] have shown that social capitalists can be efficiently detected and classified using two purely topological measures, called overlap [START_REF] Simpson | Mammals and the nature of continents[END_REF] and ratio indices. They provide useful information regarding the interaction between the set of friends and the set of followers1 of a user, which are supposed to have a large intersection whenever a user applies social capitalism techniques. In this work, we rely on this detection method to characterize the behavior of social capitalists. To better understand how they are organized, how really visible they are and how their links spread across the network, we study the positions that social capitalists occupy in Twitter w.r.t. the community structure of the network.

Community roles. In its simplest form, the community structure of a complex network can be defined as a partition of its node set, each part corresponding to a community. Community detection methods generally try to perform this partition in order to obtain densely connected groups of nodes, relatively to the rest of the network [START_REF] Newman | Finding and evaluating community structure in networks[END_REF]. Hundreds of such algorithms have been defined in the last ten years, see [START_REF] Fortunato | Community detection in graphs[END_REF] for a very detailed review of the domain. The notion of community structure is particularly interesting because it allows studying the network at an intermediate level, compared to the more classic global (whole network) and local (node neighborhood) approaches.

The concept of community role is a good illustration of this characteristic. It consists in describing a node depending on the position it holds in its own community 2 . Community roles were initially introduced by Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF] to study metabolic networks. After having applied a standard community detection method, they characterize each node according to two ad hoc measures, each one describing a specific aspect of the community-related connectivity. The node role is then selected amongst 7 predefined ones by comparing the two values to some empirically fixed thresholds. Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF] showed certain systems possess a role invariance property: when several instances of the system are considered, nodes are different but roles are similarly distributed. Scripps et al. [START_REF] Scripps | Node roles and community structure in networks[END_REF], apparently unaware of this previous work, later adopted a similar approach, but this time for influence maximization and link-based classification purposes. They also use two measures: first the degree, to assess the intensity of the general node connectivity, and second an ad hoc measure, to reflect the number of communities to which it is connected. They then use arbitrary thresholds to define 4 distinct roles.

Our contribution. In this paper, we study the community roles of social capitalists within a freely-available Twitter network provided by Cha et al. [START_REF] Cha | Measuring user influence in twitter: The million follower fallacy[END_REF]. We focus on the concept of community role as described by Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF], because it relies more heavily on the community structure. In a first place, we highlight two important limitations of this community role approach. We show that the existing measures do not take into account all aspects of the community-related external connectivity of a node. Moreover, we object the assumption of universality of the thresholds applied to the measures in order to distinguish the different node roles. The dataset we use constitutes a counter-example showing the original thresholds are not relevant for all systems. We then explain how to tackle these limitations. We first introduce three new measures to characterize the external connectivity of a node in a more complete and detailed way. We then describe an unsupervised approach aiming at identifying the node roles without using fixed thresholds. Finally, we apply our method on the Twitter network to determine the position of social capitalists, and show they occupy specific roles in the network. In particular, most of them are well connected to their community, and overall a large part of them spread their links outside their community very efficiently. This gives meaningful insights regarding the actual visibility of these users. They thus seem to occupy roles leading to a high visibility in Twitter.

Outline. We first present the concept of social capitalists in Twitter in more details (Section II). Next, we describe the method proposed by Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF] to identify the community roles of nodes (Section III-A) and provide some elements towards its limitation (Section III-B). We then describe the solutions we propose to tackle these limitations (Section III-C) and finally apply our method to study the roles of social capitalists in Twitter (Section IV).

II. SOCIAL CAPITALISTS IN TWITTER

Social capitalists have first been highlighted by Ghosh et al. [START_REF] Ghosh | Understanding and combating link farming in the twitter social network[END_REF] during a study focused on link-farming and spammers in Twitter. These specific Twitter users try to increase their number of followers by any means. To achieve this goal, they exploit two relatively straightforward principles based on the reciprocation of the follow link:

-FMIFY (Follow Me and I Follow You): the user ensures his potential followers that he will follow them back if they follow him first;

-IFYFM (I Follow You, Follow Me): on the contrary, the user systematically follows other users, hoping to be followed back.

In their work, Ghosh et al. [START_REF] Ghosh | Understanding and combating link farming in the twitter social network[END_REF] noticed that users responding the most to the solicitations of spammers are real (i.e. neither bots nor fake accounts), active and even sometimes popular users, that they called social capitalists. Using this observation, they constituted a list of 100, 000 social capitalists -namely the most responsive ones to the solicitations of spammers. Social capitalists are not healthy for a social networking service, since their methods to gain visibility and influence are not based on the production of relevant content and on getting a higher credibility. From this point of view, their high number of followers can be considered as undeserved, and biases all services based on the assumption that visible users produce or fetch interesting content (e.g. search or recommendation engines).

Using two purely topological measures (and therefore without considering any content), Dugué and Perez [START_REF] Dugué | Social capitalists on Twitter: detection, evolution and behavioral analysis[END_REF] designed a method to detect and classify efficiently these users. These measures are based on neighborhood comparisons, namely between the sets of followers N -(u) (incoming neighbors) and friends N + (u) (outgoing neighbors) of a user of interest u. The first is called the overlap index [START_REF] Simpson | Mammals and the nature of continents[END_REF], and is used to detect social capitalists:

O(u) = |N -(u) ∩ N + (u)| min {|N -(u)|, |N + (u)|} (1)
Its value ranges from 0 (regular user) to 1 (social capitalist).

The second is the ratio r, and is used to distinguish between social capitalists using the FMIFY (r ≤ 1) and IFYFM (r > 1) techniques:

r(u) = |N + (u)| |N -(u)| (2)
Dugué and Perez [START_REF] Dugué | Social capitalists on Twitter: detection, evolution and behavioral analysis[END_REF] also use a third criterion, the number of followers, which corresponds to the incoming degree of the considered node, noted d in (u). They define low in-degree social capitalists as social capitalists having less between 500 10, 000 followers, and high in-degree social capitalists as the remaining set of social capitalists. The latter users are considered as successful social capitalists, while the former ones are more popular. It is interesting to notice that in the network we consider, most users with more than 10, 000 followers are social capitalists (70%). Moreover, users with such a number of followers constitute less than 0.1% of the network, which justifies their popularity.

In the experimental part of this article, we decide to use this method to identify the social capitalists in the studied data, instead of the list manually curated by [START_REF] Ghosh | Understanding and combating link farming in the twitter social network[END_REF]. The reason for this is that the latter seems less exhaustive since it excludes users who do not follow spammers, and does not contain spammers nor bots. Furthermore, some of them have only a few followers, or only a few reciprocate followers-friends links. Finally, the method proposed by Dugué and Perez [START_REF] Dugué | Social capitalists on Twitter: detection, evolution and behavioral analysis[END_REF] achieved a greater than 80% accuracy when comparing the social capitalists it detected with those from the list.

III. IDENTIFYING COMMUNITY ROLES

In order to characterize the roles of nodes in communities, Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF] defined two complementary measures which allow them to place each node on a 2D role space. Then, they proposed various thresholds to discretize this space, each resulting subspace corresponding to a specific role. We first present this method, then highlight its limitations, and finally propose some solutions to these problems.

A. Original approach

Measures. The two measures are related to the internal and external connectivity of the node with respect to its community. In other words, they respectively deal with how a node is connected with other nodes inside and outside of its own community. The first measure, called within-module degree, is based on the notion of z-score. Since the z-score will be used again afterwards, we define it in a generic manner. Let f (u) be any function defined on the nodes, that is f associates a numerical value to any node u of the considered graph. The z-score Z f (u) w.r.t. the community of u is defined by:

Z f (u) = f (u) -µ i (f ) σ i (f ) , u ∈ C i (3)
where C i stands for a community, and µ i (f ) and σ i (f ) respectively denote the mean and the standard deviation of f over the nodes belonging to community C i . Now, let d int (u) be the internal degree of a node u, i.e. the number of links u has with nodes belonging to its own community. Then, the within-module degree of a node u, denoted z(u) by Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF], corresponds to the z-score of its internal degree. Note that z evaluates the connectivity of a node towards its community with respect to that of the other nodes of the same community.

The second measure, called participation coefficient, is defined as follows:

P (u) = 1 - i d i (u) d(u) 2 (4)
where d(u) denotes the degree of the node (i.e. the number of links it has towards other nodes), and d i (u) the community degree of u (i.e. the number of links it has towards nodes of community C i ). Note that when C i corresponds to the community of u, then d i (u) = d int (u). Roughly speaking, the participation coefficient evaluates the connectivity of a node to the communities. If it is close to 0, then the node is connected to one community only (likely its own). On the contrary, if it is close to 1, then the node is uniformly linked to a large number of communities.

Community Roles. Both measures are used to characterize the role of a node within its community. Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF] defined 7 different roles by discretizing the 2D space formed by z and P . They first used a threshold on the within-module degree, which allowed them to distinguish hubs (that is, nodes with z 2.5) from other nodes (called non-hubs). Such hubs are considered as highly linked to their community, when compared to other nodes of the same community. Those two categories are subdivided thanks to several thresholds defined on the participation coefficient (by order of increasing P ), as shown in Table I. Directed Variants. Many networks representing real-world systems, such as the Twitter network we study here, are directed. Of course, it is possible to analyze them through the undirected method, but this would result in a loss of information.

Yet, extending these measures is quite straightforward: the standard way of proceeding consists in distinguishing incoming and outgoing links. In our case, this results in using 4 measures instead of 2: in-and out-versions of both the within-module degree and participation coefficient. Let us note d in the in-degree of a node, i.e. the number of incoming links connected to the node. Then one can consider the internal indegree of a node, noted d in int , corresponding to the number of incoming links the node has inside its community. By processing the z-score of this value, one can derive the withinmodule in-degree, noted z in . Let us note d in i the community in-degree, i.e. the number of incoming links a node has from nodes in community C i . We can now define the incoming participation coefficient, noted P in , by substituting d in to d and d in i to d i in Equation ( 4). We similarly define z out and P out , using the outgoing counterparts d out , d out int and d out i . In the rest of the article, we call this set of measures the directed variants, by opposition to the original measures of Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF].

B. Limitations of this approach

As mentioned before, we identify two limitations in the approach of Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF]. The first concerns the way the participation coefficient represents the nodes external connectivity, whereas the second is related to the thresholds used for the within-module degree.

External Connectivity. We claim that the external connectivity of a given node, i.e. the way it is connected to communities other than its own, can be precisely described in three ways: first, by considering its diversity, i.e. the number of concerned communities ; second, in terms of intensity, i.e. the number of external links ; third relatively to its heterogeneity, i.e. the distribution of external links over communities. The participation coefficient combines several of these aspects, mainly focusing on heterogeneity, which lowers its discriminant power. This is illustrated in Figure 1: the external connectivity of the central node is very different in each one of the presented situations. However, P is the same in all cases. In order to be more illustrative, let us consider two users from our data, which have the same community role according to the original measures. We select two nodes both having a z greater than 2.5 and a P close to 0.25. So according to Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF] (see Table I), they both are provincial hubs, and should have a similar behavior w.r.t. the community structure of the network. However, let us now point out that the first user is connected to 50 nodes outside its community, whereas the second one has 200, 000 connections. This means they actually play different roles in the community structure, either because the second one is connected to much more communities than the first one, or because its number of links towards external communities is much larger than for the first user. Similar observations can be made for the directed variants of the participation coefficient. The measures used to define the external connectivity should take this difference into account and assign different roles to these nodes. Fixed Thresholds. As indicated in the supplementary discussion of Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF], the thresholds originally used to identify the roles were obtained empirically. They first processed P and z for different types of data: metabolic, proteome, transportation, collaboration, computer and random networks. Then, they detected basins of attraction, corresponding to regularities observed over all the studied networks. Each role mentioned earlier corresponds to one of these basins, and the thresholds were obtained by estimating their boundaries.

Implicitly, these thresholds are supposed to be universal, but this can be criticized. First, Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF] used only one community detection method. A different community detection method can lead to a different community structure, and therefore possibly different basins of attraction. Furthermore, z is not normalized, in the sense it has no fixed boundaries. There is no guarantee the threshold originally defined for this measure will stay meaningful on other networks. The values obtained for z in our experiments are far higher for some nodes than the ones observed by Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF]. We also observe that the proportion of nodes considered as hubs (i.e. z ≥ 2.5) by Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF] is much smaller in our network than in the networks they consider: 0.35% in ours versus 2% in theirs. These thresholds seem to be at least sensitive either to the size of the data, the structure of the network, or to the community detection method.

It is therefore necessary to process new thresholds, more appropriate to the considered data. However, the method used by Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF] itself is difficult to apply, because it requires a lot of data. We now present how to overcome these limitations.

C. Proposed Approach

Generalized Measures. In place of the single participation coefficient, we propose 3 new measures aiming at representing separately the aspects of external connectivity: diversity, intensity and heterogeneity. Moreover, a fourth measure is used to describe the internal connectivity.

Because we deal with directed links, each one of these measures exists in two versions: incoming and outgoing (as explained in section III-A), resulting in 8 effective measures. However, for simplicity matters, we ignore link directions when presenting them in the rest of this section.

All our measures are expressed as z-scores. We know community sizes are generally power-law distributed, as described in [START_REF] Lancichinetti | Characterizing the community structure of complex networks[END_REF], which means their sizes are heterogeneous. Our community-based z-scores (cf. Equation ( 3)) allows to normalize the measures relatively to the community size, and therefore to take this heterogeneity into account.

Diversity. The diversity D(u) evaluates the number of communities to which a node u is connected (other than its own), w.r.t. the other nodes of its community. This measure does not take into account the number of links u has to each community. Let ǫ(u) be the number of external communities to which u is connected. The diversity is defined as the z-score of ǫ w.r.t. the community of u. It is thus obtained by substituting ǫ to f in Equation ( 3).

External intensity. The external intensity I ext (u) of a node u measures the amount of links u has towards communities other than its own, w.r.t. the other nodes of its community. Let d ext (u) be the external degree of u, that is the number of links u has with nodes belonging to another community than its own. The external intensity is defined as the z-score of the external degree, i.e. we obtain it by substituting d ext to f in Equation (3).

Heterogeneity. The heterogeneity H(u) of a node u measures the variation of the number of links a node u has, from one community to another. To that aim, we compute the standard deviation of the number of links u has to each community. We denote this value by δ(u). The heterogeneity is thus the z-score of δ w.r.t. the community of u. As previously, it can be obtained by substituting δ to f in Equation (3).

Internal intensity. In order to represent the internal connectivity of the node u, we use the z measure of Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF]. Indeed, it is based on the notion of z-score, and is thus consistent with our other measures. Moreover, we do not need to add measures such as diversity or heterogeneity, since we consider one node can belong only to one community. Due to the symmetry of this measure with the external intensity, we refer to z as the internal intensity, and denote it by I int (u).

Unsupervised Role Identification. Our second modification concerns the way roles are defined. As mentioned before, the thresholds defined by Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF] are not necessarily valid for all data. Moreover, our generalization of the measures invalidates the existing thresholds, since we have now 8 distinct measures, all different from the original ones. We could try estimating more appropriate thresholds, but as explained in section III-B, the method originally used by Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF] to estimate their thresholds is impractical. The fact our measures are all z-scores also weakens the possibility to get thresholds applicable to all systems, which means the estimation process should potentially be performed again for each studied system.

To overcome these problems, we propose to apply an automatic method instead, by using unsupervised classification. First, we process all the measures for the considered data. Then, a cluster analysis method is applied. Each one of the clusters identified in the measure space is considered as a community role. This method is not affected by the number of measures used, and amounts to adjusting thresholds to the studied system. If the number of roles is known in advance, for instance because of some properties of the studied system, then one can use an appropriate clustering method such as kmeans, which allows specifying the number k of clusters to find. Otherwise, it is possible to use cluster quality measures to determine which k is the most appropriate ; or to apply directly a method able to estimate at the same time the optimal number of clusters and the clusters themselves.

IV. COMMUNITY ROLES OF SOCIAL CAPITALISTS

A. Data and Tools

We analyze a freely-available anonymized Twitter network, collected in 2009 by Cha et al. [START_REF] Cha | Measuring user influence in twitter: The million follower fallacy[END_REF]. It contains about 55 million nodes representing Twitter users, and almost 2 billion directed links corresponding to friend-to-follower relationships. We had to consider the size of these data when selecting our analysis tools. For community detection, we selected the Louvain method [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF], because it is widespread and proved to be very efficient when dealing with large networks. We retrieved the C++ source code published by its authors, and adapted it in order to optimize the directed version of the modularity measure, as defined by Leicht and Newman [START_REF] Leicht | Community structure in directed networks[END_REF]. All the role measures, that is Guimerà and Amaral's original measures, their directed variants (section III-A) and our new measures (section III-C), were computed using the community structure detected through this means. We also implemented them in C++, using the same sparse matrix data structure than the one used in the Louvain method.

All resulting values were normalized, in order to avoid scale difference problems when conducting the cluster analysis. Since we do not know the expected number of roles, the clustering was performed using an open source implementation of a distributed version of k-means [START_REF] Liao | Parallel k-means data clustering[END_REF]. Indeed, centralized versions are based on a unique distance matrix, and turned out to be too demanding in terms of memory. We applied this algorithm for k ranging from 2 to 15, and selected the best partition in terms of Davies-Bouldin index [START_REF] Davies | A cluster separation measure[END_REF]. We selected this index because it is a good compromise between the reliability of the estimated quality of the clusters, and the computing time it requires. All pre-and post-processing scripts related to the cluster analysis were implemented in R. The whole source code is available at the following address: https://github.com/CompNet/Orleans

B. Roles Expected for Social Capitalists

We expect the degree of social capitalists to play an important role considering their position (see Section II). High indegree social capitalists (namely greater than 10, 000) should be well connected to their communities -hubs-or to the other communities -connectors, or both. Being connectors would indicate they obtained a high visibility on the whole network and not only in their own communities. Furthermore, because we take the direction of links into account in our measures, we expect social capitalists to be discriminated according to their ratio, i.e. the number of outgoing links divided by the number of incoming links. We especially expect high in-degree social capitalists with a small ratio (so-called passive social capitalists according to [START_REF] Dugué | Social capitalists on Twitter: detection, evolution and behavioral analysis[END_REF]) to be highly connected to their communities and to the rest of the graph. Considering low degree social capitalists, it is not possible to predict their roles without any further information. The study will thus be of great interest to characterize their visibility.

C. Detected Roles

For the sake of completeness, we first used the original undirected measures of Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF]. We obtained only 2 roles, each one concerning too many nodes to bring up any valuable information regarding the studied system. Since this might be due to the fact these measures ignore link directions, we then worked with their directed variants (section III-A), and then with our generalized measures (section III-C).

In both cases we used the unsupervised role identification method we proposed (section III-C).

Directed Variants. A correlation study shows z out and z in are slightly correlated (with a correlation coefficient ρ < 0.3), whereas the correlation is zero for all other pairs of measures. This seems to confirm the interest of considering link directions in the role measures. When doing the cluster analysis, the most separated clusters are obtained for k = 6. An ANOVA followed by post hoc tests (t-test with Bonferroni's correction) showed significant differences exist between all clusters and for all measures.

An analysis of the distribution of high in-degree social capitalists in these clusters shows that a few of these users occupy a connector hub role. This is quite expected as said in IV-B. However, most of the high degree social capitalists are considered as non-hubs and peripheral or ultra-peripheral nodes. More than 60% of the users with a high ratio are classified as ultra-peripheral nodes for both incoming and outgoing directions, which is rather surprising since they have a really high degree. However, they are classified in a cluster with low z and P (both in-and out-versions). The low z indicates these users are not much connected to their community (relatively to the other nodes of the same community), and must thus be more connected to other communities. Still, P does not highlight this aspect of their community-related connectivity, and they appear as peripheral. This inconsistency of the detected roles confirms the limitations of P described in section III-B.

Generalized Measures. Most generalized measures are slightly correlated, with values ranging from almost 0 to 0.4. In particular, both versions of the same measure (incoming vs. outgoing) are only slightly correlated, which is another confirmation of the interest of considering link directions. Only three measures are strongly correlated: internal and external intensities and heterogeneity (ρ ranging from 0.78 to 0.92). The relation between both intensities seems to indicate that variations on the total degree globally affect similarly internal and external degrees. The very strong correlation observed between heterogeneity and intensity means only nodes with low intensity are homogeneously connected to external communities, whereas nodes with many links are connected heterogeneously.

Similarly to the directed measures, the most separated clusters are obtained with k = 6. These 6 clusters are given in Table II with their sizes and roles. However, the correspondance with the original nomenclature is rougher, since these measures are farther from the original ones. The average of each measure per cluster is showed in Table III. Like before, ANOVA and post hoc tests showed significant differences between all clusters and for all measures. We now conduct a detailed analysis of the different roles we obtain. Cluster 1. Because both internal intensity versions (equivalent to z) are negative, nodes in this cluster cannot be hubs. The negative external measures indicate these nodes are not connectors either. We can thus consider them as ultra-peripheral non-hubs. This cluster is the largest one, with 47% of the network nodes. This confirms the matching with this role, whose nodes constitute generally most of the network.

Clusters 4 and 5. Cluster 4 is very similar to Cluster 1. However, its incoming diversity is 0.69. These nodes are again peripheral, because the external intensity is negative. Still, incoming links come from a larger number of communities. Cluster 5 is also similar to Cluster 1. However, both versions of diversity are positive for this cluster, with an outgoing diversity of 0.60. External links are thus connected to a larger number of communities. Clusters 4 and 5 are the second (23%) and third (21%) largest ones, respectively. By gathering all the peripheral and ultra-peripheral nodes, we obtain 91% nodes of the network.

Cluster 6. The internal intensity is still close to 0 but positive. Thus, these nodes are non-hubs, even if they are more connected to their community than those of the previous clusters.

Like the other external measures, the external intensity is low but still positive. These nodes are relatively well-connected to other communities, and we can therefore consider them as connectors. Both versions of the diversity are relatively high, which indicates these nodes are not only more connected to their community as well as others, but also to a larger number of distinct communities.

Cluster 3. The high internal intensity allows us to state that these nodes are hubs. Furthermore, the high external measures indicate these nodes are connected to a high number of nodes from a lot of other communities, and thus are connector hubs. Notice outgoing measures are higher. This cluster represents only 0.6% of the network, meaning this role is very uncommon.

Cluster 2. This observation is even more valid for Cluster 2, which represents much less than 1% of the nodes. For this cluster, all measures are really high. The incoming versions are always higher than their outgoing counterparts. We call these users kinless hubs according to Guimerà and Amaral's nomenclature. It is worth noticing that, whatever the considered measures, some of the roles defined by Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF] are not represented in the studied network. This is consistent with the remarks previously made for other data by Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF], and confirms the necessity of having an unsupervised approach to define roles in function of measures. It is also consistent with the strong correlation observed between internal and external intensities: missing roles would be nodes possessing a high internal intensity but a low external one, or vice-versa. However, those are very infrequent in our network.

Cluster I out int I in int D out D in 1 -0.

D. Relations between clusters

We now discuss how the nodes are connected depending on the role they hold. Figure 2 is a simplified representation of this interconnection pattern.

The outgoing links of ultra-peripheral (Cluster 1) and peripheral (Clusters 4 and 5) nodes target mainly kinless hubs (Cluster 2) and connectors (Clusters 3 and 6), representing 74% (Cluster 1), 82% (Cluster 4), and 74% (Cluster 5) of their connections. These (ultra-)peripheral nodes, which are the most frequent in the network, thus mainly follow very connected users, probably the most influent and relevant ones. This seems consistant: they follow only a few users, and so choose the most visible ones.

Connector nodes (Clusters 3 and 6) are mainly linked to other connectors nodes. They have the tightest connection, since their arcs amounts to a total of 43% of the network links. This is worth noticing, because these clusters are far from being the largest ones. They are also largely connected to the rest of the clusters too, especially with outgoing links. Connectors follow massively users of all clusters, so we suppose they constitute the backbone of the network.

(4 1 % ) 1 0 % (2 9 % ) C1 C2 C3 C4 C5 C6 ( 2 0 % ) 1 % ( 5 % ) (1 1 % ) 1 % (5 % ) (16 %) 1% (2% ) ( 2 0 % ) < 1 % ( 1 % ) ( 22
Kinless hubs (Cluster 2) are massively followed by nonhubs, representing 38% (Cluster 1), 43% (Cluster 4), 19% (Cluster 5) and 8% (Cluster 6) of their outgoing links. And interestingly, the links coming from kinless hubs target the same clusters: 9% go to Cluster 1, 20% to Cluster 4, 22% to Cluster 5 and 41% to Cluster 6. This means the most visible and popular nodes of the network mostly follow and are followed by much less popular users. One could have expected the network to be hierarchically organized around roles, with more peripheral nodes connected to less peripheral nodes. But this is clearly not the case. First, (ultra-)peripheral nodes are marginally connected to other nodes holding the same role, they prefer to follow connectors and/or hubs. Second, kinless and connector hubs, although well connected to connector nonhubs, do not have direct links, i.e. these users do not follow each other.

E. Position of Social Capitalists

As stated previously, we use a list of approximately 160, 000 social capitalists as detected by Dugué and Perez [START_REF] Dugué | Social capitalists on Twitter: detection, evolution and behavioral analysis[END_REF].

In the following, we analyze how social capitalists are distributed amongst the detected roles. As explained section II, we split social capitalists according to their in-degree (number of followers). Recall that low in-degree social capitalists have an in-degree between 500 and 10, 000, and high in-degree social capitalists an in-degree greater than 10, 000. These social capitalists are known for having especially well succeeded in their goal of gaining visibility.

The tables in this section describe how the various types of social capitalists are distributed over the clusters. In each cell, the first row is the proportion of social capitalists belonging to the corresponding cluster, and the second one is the proportion of cluster nodes which are social capitalists. Values of interest are indicated in bold and discussed in the text.

Low in-degree social capitalists. Low in-degree social capitalists are mostly assigned to three clusters: 3, 5 and 6 (see Table IV). Most of them belong to Cluster 6, which contains nonhub connector nodes. These nodes, which have only slightly more external connections than the others, are nevertheless connected to far more communities. Social capitalists in this cluster seem to have applied a specific strategy consisting in creating links with many communities. This strategy is still not completely working, though, as shown by the relatively low external incoming intensity (meaning they do not have that many followers).

Nodes from Cluster 3 are connector hubs, who follow more users than the others. Because IFYFM social capitalists have a ratio greater than 1 and thus more friends than followers, it is quite intuitive to observe that they are twice as many than the other users in this cluster. The high outgoing diversity of Cluster 3 tells us that these social capitalists follow users from a large variety of communities, not only theirs (to which they are well connected). The high external outgoing intensity show that these users massively engage in the IFYFM process, but did not yet receive a lot of following back, as shown by their low external incoming intensity. Finally, roughly 20% of social capitalists with ratio r < 1 belong to Cluster 5, which contains non-hub peripheral nodes. This shows that a non-neglictible share of social capitalists are isolated relatively to both their community and the other ones. These observations show that most of these users are deeply engaged in a process of soliciting users from other communities, not only theirs. Some of them are even massively following users from a wide diversity of communities. This tends to show that these users may obtain an actual visibility across many communities of the network by spreading their links efficiently.

High in-degree social capitalists. Most of the high in-degree social capitalists are gathered in Cluster 3 (see Table V), corresponding to connector hubs. This is consistent with the fact these users have a high degree. Users of Cluster 3 have a high outgoing diversity and a high outgoing external intensity: this shows they practice the IFYFM strategy actively, by following a lot of users from a wide range of communities. The rest of these users is contained in Cluster 2. Nodes in these clusters are kinless hubs and thus can be considered as successful users. Indeed, they are massively followed by a very high number of users from an extremely large variety of communities. Only high-degree social capitalists with a ratio smaller than 0.7 and a few with a ratio smaller than 1 are classified in this cluster. This is consistent with the roles one could expect for social capitalists (section II). These observations mean that most of these users are well connected in their communities but also with the rest of the network. This shows the efficiency of these users strategies. Indeed, most of the users are linked to a wide range of communities, and thus reach a high visibility in a large part of the network.

Ratio

V. CONCLUSION

In this article, our goal is to characterize the position of social capitalists in Twitter. For this purpose, we propose an extension of the method defined by Guimerà and Amaral [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF] to characterize the community role of nodes in complex networks. We first define directed variants of the original measures, and extend them further in order to take into account the different aspects of node connectivity. Then, we propose an unsupervised method to determine roles based on these measures. It has the advantage of being independant from the studied system. Finally, we apply our tools to a friendto-follower Twitter network. We find out the different kinds of social capitalists occupy very specific roles. Those of low in-degree are mostly connectors non-hubs. This shows they are engaged in a process of spreading links across the whole network, and not only their own community. Those of high indegree are classified as kinless or connectors hubs, depending on their ratio r. This shows the efficiency of their strategies, which lead to a high visibility for a vast part of the network, not only for their own community.

The most direct perspective for our work is to assess its robustness. In particular, it is important to know how the stability of the detected communities and clusters affects the identified roles. In this study, the very large size of the data prevented us to do so: first, it was a strong constraint when selecting the tools we used for community detection and cluster analysis, and second it was not possible to repeat these processing many times to evaluate the stability of their results.

We plan to work on this point by using smaller datasets. On a related note, we want to apply our method to other systems, in order to check for its general relevance. The method itself can also be extended in two ways. First, it would be relatively straightforward to take link weights into account (although this was not needed for this work). Second, and more interestingly, it is also possible to adapt it to overlapping communities (by opposition to the mutually exclusive communities considered in this work) in a very natural way, by introducing additional internal measures symmetrical to the existing external ones. This could be a very useful modification when studying social networks, since those are supposed to possess this kind of community structures, in which a node can belong to several communities at once [START_REF] Arora | Finding overlapping communities in social networks: Toward a rigorous approach[END_REF].

Fig. 1 .

 1 Fig.1. Each pattern represents a community. In each case, the participation of the central node is 0.58.

TABLE II .

 II

CLUSTERS DETECTED WITH THE GENERALIZED MEASURES: SIZES IN TERMS OF NODE COUNT AND PROPORTION OF THE WHOLE NETWORK, AND ROLES ACCORDING TO THE GUIMER À AND

AMARAL

[START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF]

NOMENCLATURE.

TABLE III .

 III AVERAGE GENERALIZED MEASURES OBTAINED FOR THE 6 DETECTED CLUSTERS .

  Fig.2. Interconnection between clusters. A vertex i corresponds to Cluster i from TableII. An arc (i, j) represents the set of links connecting nodes from Cluster i to nodes from Cluster j. It is labeled with 3 values, each one describing which proportion of links the arc represents, relatively to 3 distinct sets: first relatively to all links starting from Cluster i, second relatively to all links in the whole network, and third relatively to all links ending in Cluster j. The arc thickness is proportional to the second value. For matters of readability, arcs representing less than 1% of the network links are not displayed.

			( 1 7 % (1 1 % ) 2 % (1 3 % )
	(38%) 2% (16%)	(1 1% ) 3% (5 1% )	%) <1 % (1% ) ( 1 6 % ) 4 % ( 3 5 % ) ) 2 % ( 4 % ) (4 % ) 2% (3 3% ) (41%) <1% (<1%) (1 6% ) 4% (3 1% ) (2 2% ) 2% (1 0% ) (19 %) 3% (22 %) ( 4 3 % ) 4 % ( 3 1 % ) (2 3 % ) 1 0 % (4 9 % ) (8 % ) 4 % (2 9 % ) ( 4 5 % ) ( 1 3 % ) 6 % (12%) 5% (44%)	(25 %) 4% (17 %)	(11%) 2% (13%) (30%) 4% (13%) (40%) 18% (51%)
			(15%) 4% (19%)

TABLE V .

 V DISTRIBUTION OF HIGH IN-DEGREE SOCIAL CAPITALISTSOVER CLUSTERS OBTAINED FROM THE GENERALIZED MEASURES.

For a given user, friends denote the set of users he follows, and followers the set of users that follow him, as per the official Twitter terminology.

Note that the notion of role also appears in works related to block modeling, but it is not defined in terms of position in a community[START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF].


Vincent Labatut
email: vlabatut@gsu.edu.tr

Marc Plantevit
email: marc.plantevit@liris.cnrs.fr

Jean-François Boulicaut
email: jean-francois.boulicaut@insa-lyon.fr

A Method for Characterizing Communities in Dynamic Attributed Complex Networks

Keywords: Dynamic Networks, Nodal Attributes, Community Detection, Community Interpretation, Topological Measures, Emerging Sequence Mining

Many methods have beenproposed to detect communities, not only in plain, but also in attributed, directed or even dynamic complex networks. In its simplest form, a community structure takes the form of apartition of the node set. From the modeling point of view, to be of some utility, this partition must then be characterized relatively to the properties of the studied system. However, if most of the existing works focus on defining methods for the detection of communities, only very few try to tackle this interpretation problem. Moreover, the existing approaches are limited either in the type of data they handle, or by the nature of the results they output. In this work, we propose a method to efficiently support such a characterization task. We first define a sequence-based representation of networks, combining temporal information, topological measures, and nodal attributes. We then describe how to identify the most emerging sequential patterns of this dataset, and use them to characterize the communities. We also show how to detect unusual behavior in a community, and highlight outliers. Finally, as an illustration, we apply our method to a network of scientific collaborations.

I. INTRODUCTION

Complex networks have become very popular as amodeling tool during the last decade, because they help to better understand the intrinsic lawsand dynamics of complex systems. A typical plain network contains only nodes and links between them, but it is possible to enrich it with different types of data: link orientation and/or weight, temporal dimension, attributes describingthe nodes or links, etc. This flexibility allowed to use complex networks to study realworld systems in many fields: sociology, physics, genetics, computer, etc. [START_REF] Newman | The Structure and Function of Complex Networks[END_REF].

The complex nature of the modeled systems leads to the presence of non-trivial topological properties in the corresponding networks. Among them, the community structure is one of the most common and most studied. Intuitively, we can define a community as a group of nodes which is densely interconnected relatively to the rest of the network [START_REF] Girvan | Community structure in social and biological networks[END_REF].However, in the literature, this notion is formalized in many different ways [START_REF] Fortunato | Community detection in graphs[END_REF]. There are actually hundreds of algorithms for detecting community structures, characterized by the use of different formal definitions of what a community is, and/or relying on different processes. Among the principles these approaches are based upon, one can cite: modularityoptimization, similarity matrix clustering, data compression, statistical significance, information diffusion, clique percolation, etc. (c.f. [START_REF] Fortunato | Community detection in graphs[END_REF]for a detailed review). Most of the existing methods deal with plain complex networks, but new methods were gradually introduced to handle richer networks: first link directions and weights, then time, and more recently node attributes [START_REF] Tian | Efficient aggregation for graph summarization[END_REF][START_REF] Zhou | Graph clustering based on structural/attribute similarities[END_REF][START_REF] Sese | Mining networks with shared items[END_REF][START_REF] Silva | Mining attribute-structure correlated patterns in large attributed graphs[END_REF][START_REF] Ruan | Efficient community detection in large networks using content and links[END_REF].

Although the algorithms differ in terms of nature of the detected communities, algorithmic complexity, result quality and other aspects [START_REF] Fortunato | Community detection in graphs[END_REF], their output can always be basically described as a list of node groups. More specifically, in the case of mutually exclusive communities, it is a partition of the set of nodes. From an applicative point of view, the question is then to make sense of these groups relatively to the studied system. In other terms, for the community structure to be useful, it is necessary to interpret the detected communities.This problem is extremely important from the end user's perspective. And yet, almost all works in the field of community detection concern the definition of detection tools, and their evaluation in terms of performance. Only a very few works try to tackle the problem of characterizing and interpreting the communities.

Authors historically interpreted their data manually [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF][START_REF] Newman | Fast algorithm for detecting community structure in networks[END_REF]but this somewhat subjective approach does not scale well on large networks. More recently, several authors used topological measures to characterize community structures. In [START_REF] Lancichinetti | Characterizing the Community Structure of Complex Networks[END_REF],Lancichinettiet al. visually examine the distribution of some community-based topological measures,both at local and intermediary levels. Their goal is to understand the general shape of communities belonging to networks modeling various types of real-world systems. In [START_REF] Leskovec | Statistical Properties of Community Structure in Large Social and Information Networks[END_REF], Leskovecet. alpropose to study the community structure as a whole, by considering it at various scales, thanks to a global measure called conductance. These two studies are interesting, because they try to describe the community structure of plain networks. However, it should be noted the resulting observations are quite general, in the sense communities are studied and characterized collectively, to identify trends in a network [START_REF] Leskovec | Statistical Properties of Community Structure in Large Social and Information Networks[END_REF], or even a collection of networks [START_REF] Lancichinetti | Characterizing the Community Structure of Complex Networks[END_REF].

In order to characterize each community individually, some authors take advantage of the information conveyed by nodal attribute, when it is available. In [START_REF] Tumminello | Community characterization of heterogeneous complex systems[END_REF], the authors propose a statistical method to characterize the communities in terms of the over-expressed attributes found in the elements of the community. In [START_REF] Labatut | Detection and Interpretation of Communities in Complex Networks: Practical Methods and Application[END_REF], authors interpret the communities of a social attributed network. They use statistical regression and discriminant correspondence analysis to identify the most characteristic attributes of each community.Both studies are valuable, however they do not take advantage of the available topological measures to enhance the interpretation process.

As mentioned before, there are methods taking advantage of both relational (structure) and individual (attributes) information to detect communities. It seems natural to suppose the results they output can be used for interpretation purposes. For example, in [START_REF] Zhou | Graph clustering based on structural/attribute similarities[END_REF], the authors interpret the communities in terms of the attributes used during the detection process; and in [START_REF] Yang | Community Detection in Networks with Node Attributes[END_REF], the authors identify the top attributes for each identified community. However, the problem with these community detection-based method is that the notion of community is often defined procedurally, i.e. simply as the output of the detection method, without any further formalization. It is consequently not clear how structure and attributes affect the detection, and hence the interpretation process. All these methods additionally rely on the implicit assumption of community homophily. In other words, communities are supposed to be groups of nodes both densely interconnected and similar in terms of attributes. To our knowledge, no study has ever shown this feature was present in all systems, or even in all the communities of a given network. It is therefore doubtful those methods are general enough to be applied to any type of network.

In this work, we seethe interpretation problem as independent from the approach used for community detection, and we try to propose a method allowing to tackle the limitations of the existing approaches. Based on the observation that attributes allow to improve the interpretation of communities, we propose to enhance it further by considering temporal information, in addition to structure and attributes. Moreover, to obtain intelligible results, we want to explicitly identify which parts of the structural information are relevant to the interpretation process. For this matter, we detect common changes in topological features and attribute values over time periods, in dynamic attributed networks. More precisely, we aim at finding the most representative emerging sequential patterns for each community. These patterns can then be used for both characterizing the community, and identify outliers, i.e. node with non-standard behavior. The emergingpatterns represent the general trend of nodes in the considered community, whereas the outliers can correspond to nodes with a specific role in the community, or node located at itsfringe. We illustrate our proposal on a dynamic co-authorship network extracted from DBLP.

Our first contribution is to consider community characterization as a specific problem, distinct from community detection. In particular, it should be independent from the method used to detect communities, rely on an easily replicable systematic approach, and be as automated as possible. Our second contribution is the introduction of a new representation of dynamic attributed networks. It takes the form of a database containing sequences of node topological measures, attributes and community information, for several time slices. Such sequences were used for the representation of natural data before [START_REF] Mabroukeh | A taxonomy of sequential pattern mining algorithms[END_REF], but not for the networks. Our third contribution is the definition of a method taking advantage of this representation to extract sequential patterns able to characterize the communities. Finally, our last contribution is to illustrate our method by applying it to a real-world network.

The rest of this article is organized as follows. In section II, we give the preliminary definitions needed to describe our method. In section III, we specify the problem and explain in detail our interpretation method. In section IV, we present our experimental results obtained on the DBLP data. Section V discuss our work and presents its possible extensions.

II. PRELIMINARY DEFINITIONS

In this section, we first define different network-related concepts needed to introduce our method. We also describe the topological measures we use in our experiment.

A. Network and Community Structure

We define a dynamicnetwork = 1 , … , as a sequence of chronologically ordered time slices. Each time slice corresponds to a separated subnetwork ( 1), which represents the connections between the nodes for a given time interval. Moreover, the networks we consider areattributed, meaning their nodes are described by some individual attributes. We therefore note a time slice = , , , where is the set of nodes, ⊆ × is the set of links and is the set of node attributes. In what we call adynamicattributed network, the node and attribute sets are the same at each time slice, whereas the link repartition and attribute values can change. We note = the number of nodes.We only deal with undirected graphs,so we consider all pairs , to be unordered. We also define the following adjacency function :

, = 1 , 0 , (1)
where , directly depends on the presence (value 1) or absence (value 0) of a link between nodes and at time .

We define the global weighted network = , ℰ associated to a dynamic network as its integration over time. The link set of contains all links appearing through time ℰ = =1 , whereas the node set is the same than for , since it is fixed. We define a weight function summing over time: the weight of a link , fromℰ is defined as:

, = , 1 (2)
A community structure of a network is a partition of its node set, and each part of this partition is called a community. Here, we work with a static community structure of , so a partition of , and we note the communities ( 1), for distinct communities. Moreover, we define , the function associating a node to its community in . The community size of a given community is , i.e. the number of nodes it contains.

B. Topological Measures

A topological measure quantifies the structural properties of the network or its components. Here, we focus on five nodal measures: internal degree, local transitivity, within module degree, participation coefficient and embeddedness. We process each of these measures for each node, and at each time slice. The degree and local transitivity are both local measures, whereasthe othersare community-related.

We first note = : , the neighborhood of node at time , i.e. the set of nodes connected to in . The degree = of a node is the cardinality of its neighborhood, i.e. its number of neighbors, at time slice .

We define the internal neighborhood of a node at time as the subset of its neighborhood located in its community: = ∩ . The internal degree = is defined similarly to the degree, as the cardinality of the internal neighborhood, i.e. the number of neighbors the node has in its community at time .

The local transitivitycorresponds to the ratio of existing to possible triangles containing in :

= , : ∧ -1 2 (3)
In thisratio, the numerator corresponds to the observed number of links between the neighbors of , whereas the denominator is the maximum possible number of such links.

The within module degree and participation coefficient are two measures proposed by Amaral&Guimerà [START_REF] Guimerà | Cartography of complex networks: modules and universal roles[END_REF]to characterize the community role of nodes. The within module degree is defined as the -score of the internal degree:

= -µ , , (4)
Here, µand denote the mean and standard deviation of over all nodes belonging to , respectively.It expresses how much a node is well connected to other nodes in its community, relatively to this community. In [START_REF] Guimerà | Cartography of complex networks: modules and universal roles[END_REF], the authors distinguish nodes depending on whether their is above or below a limit of 2.5. If 2.5, the node is considered to be a community hub, because it is significantly more connected to its community than the other members of the same community. If < 2.5, the node is said to be a community non-hub.

The participation coefficient, introduced in the same study [START_REF] Guimerà | Cartography of complex networks: modules and universal roles[END_REF], is based on the notion of community degree = ∩ , which represents the number of links a node has with nodes belonging to community . Incidentally, one can see the internal degree is a specific case of community degree, for which = . This measure is formally defined as:

= 1 - 2 1 (5)
whereisthe number of communities in . characterizes the distribution of the neighbors of a node over all communities. More precisely, it measures the heterogeneity of this distribution. It gets close to 1 if all the neighbors are uniformly distributed among all the communities and 0 if they are all gathered in the same community.

The embeddedness represents the proportion of neighbors of a node belonging to its own community [START_REF] Lancichinetti | Characterizing the Community Structure of Complex Networks[END_REF]. Unlike the within module degree, the embeddedness is normalized with respect to the node, and not the community.

= (6)

A node descriptor iseither any of these five topological measures explained above, or a node attributefrom . Let = 1 , 2 , … , be the set of all descriptors. Each descriptor from can take one of several discrete values, defined in its domain [START_REF] Newman | The Structure and Function of Complex Networks[END_REF].

III. CHARACTERIZATION METHOD We break down the problem of community interpretationin two

sub-problems:1) findingan appropriate way ofrepresenting acommunity, and 2) taking advantage of this representation to identify the community most characteristic features. We solve the first sub-problemby representing a community as a set of sequences describing the evolution of its nodes. This encoding allows handling attributed dynamic networks, via their nodes topological measures and attributes. For the second sub-problem, we mine this set to identify sequential patterns fitting several criteria.

The process we propose includes 3 steps. The first is to identify a reference community structure, as explained in subsection A. In the second step, we search for emergingsequential patterns and extract the corresponding supporting nodes for each community. We explain the details of this process in subsectionB. Finally, the third step is to choose the most representative patterns to characterize the communities according to various criteria that we explain in subsection C.

A. Step 1: Detecting Communities

To detect how nodes evolve in terms of community membership, we need first a reference community structure. It would be possible to apply a dynamic method; however this results in complications due to the merging, splitting, disappearing and appearing of communities through time. For this reason, in this fist version of our tool, we decided to use only static communities. We detected them on the global weighted network described in subsectionII-A. Note that a similar approximation appears in [START_REF] Aynaud | Multi-Step Community Detection and Hierarchical Time Segmentation in Evolving Networks[END_REF].To perform the detection, we apply the Louvain [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF]algorithm, which is atwophase hierarchical agglomerative approach. During the first phase, the algorithm applies a greedy optimization to identify the communities. During the second phase, it builds a new network whose nodes are the communities found during the first phase. Then, the process is repeated again iteratively.

B. Step 2: Mining Emerging Sequences

We want to characterize each community according to the common evolution of the descriptors of its nodes over time. For this purpose, we need to identify series of descriptor values which appear often in the same community and over several time slices. This is precisely the goal of sequential pattern mining methods. Here, we describe the principle they rely upon, and how we take advantage of it.

We present an example network inFigure 1to illustrate our method and the concepts it relies upon.It has 7nodes whose interconnections change over 3 time slices. There is one attribute assigned to each node, whose valuecan also evolve through time. For the sake of simplicity, we only one topological measure: the degree. Let us first define the concepts necessary to the description of the method itself. An item , × i is a couple constituted of a descriptor and a value from its domain i . The set of all items is noted . The set of all possible items for the example network fromFig. 1is = = 1, = 2, = 3, = 4, = 5, = 6, = 1, = 2, = 3, = 4 , where is the only considered attribute and is the degree. Anitemset is any subset of . For example, = = 1, = 4 is an itemset for our example network.Asequence = 1 , … , is a chronologically ordered list of itemsets. The size of sequence is the number of itemsets it contains. For example, = 1, = 2 = 3, = 3 is a sequence of size 2 extracted from the network described in Fig. 1

.A sequence = 1 , … , µ is a sub-sequence of another sequence = 1 , … , iff ∃ 1 , 2 , … , µ such that 1 1 < 2 < ⋯ < µ and 1 ⊆ 1 , 2 ⊆ 2 , … , µ ⊆ µ . This is noted
. It is also said that is a super-sequenceof , which is noted . An example of such relation for Fig. 1is = 4 = 1 = 4 . The node sequence ofa node is a specific type of sequence noted = 11 , … , 1 … 1 , … , where is the item containing the value of descriptor for at time . A node sequence includes itemsets, i.e. it represents all time slices. Each one of these itemsets contains all descriptor values for the considered node at the considered time. In other words, contains all the available descriptor-related data for node . These tuples will be used later to constitute the database analyzed by our method.As an example, the node sequence for node 1 in the networkofFig. 1is

= 2, = 1 = 2, = 1 = 6, = 2 . The set of supporting nodes of a sequence is defined as = :

. The support of a sequence , =

, is the proportion of nodes, in , whose node sequences are super-sequence of . In this study, we used the algorithm CloSpan [START_REF] Yan | CloSpan: Mining Closed Sequential Patterns in Large Datasets[END_REF] to find out all possible CFS for a given . It has two steps. At the first step, CloSpan creates the candidate set, which is a super-set of closed frequent sequences, and stores the elements into a so-called prefix sequence lattice. At the second step, the algorithm prunesthis lattice, in order to eliminate non-closed sequences. This pruning technique relies onthe fast subsumption checking method introduced by Zaki [START_REF] Zaki | CHARM: An Efficient Algorithm for Closed Itemset Mining[END_REF]. This technique manages a hash table in which the hash keys of a sequence is the sum of all the sequence ID's supportings that sequence.

CloSpanis an efficient algorithm, which can mine long sequences in practical time for real-world data. It outputs both the sequences and their supports, but not the supporting node sets, so an additional processing is required to identify them.In our case, we want to characterize communities in terms of CFS. Thus, we need to identify, for each community, its most representative sequential pattern(s). For this purpose, we turn to the notion of emerging pattern, i.e. a pattern more frequent in a part of the nodes than in the rest of it. The emergence of a pattern relatively to a community is measuredby its growth rate given in Equation [START_REF] Silva | Mining attribute-structure correlated patterns in large attributed graphs[END_REF].

, = , , (7)
Here is the complement of in , i.e. = ∖ . The growth rate is the ratio of the support of in to the support of in .Therfore, a value larger than 1 means is particularly frequent (i.e. emerging) in , when compared to the rest of the network. We consider that the higher the growth rate, and the more representative the sequence for community .

In order to calculate the growth rate, it would be necessary to search CFS in all communities separately, which can be a costly operation. However, a more efficient method was proposed in [START_REF] Plantevit | Condensed Representation of Sequential Patterns According to Frequency-Based Measures[END_REF] to handle the case where classes are assigned to item sequences. Our communities can be considered as classes, which is why the method is also relevant to our case. It is based on a modification of the analyzed data. First, let us note • the concatenation of a sequence = 1 , … , µ and a symbol , such that • = 1 , … , µ ,

. Instead of working on a sequence database constituted of tuples of the form ,

, we use a database ℳ = , • , containing each node , its node sequence and community . Note that

• = 1 , … , ,
, where is the itemset of at time . After having identified the frequent sequences by applying CloSpan to ℳ, the patterns concerning a community of interest can be obtained simply by selecting all the CFS ending with . The support of such CFS (of the form • ) in ℳ corresponds to the support one would have obtained on the non-concatenated database. Thus, all the necessary information to calculate is provided when applying CloSpan to ℳ.

Processing the growth rate of all CFS relatively to all communities then requires separating the CFS depending on how they end: we group together patterns related to the same community, and also those not related to any community. Let us note the number of CFS typically found for a community, as well as those found for the whole network. Indeed, the order of magnitude of these quantities is approximately the same. Then, we process each one of the patterns found in each one of the communities. For such a pattern, we retrieve its support and that of the corresponding community-less pattern, as outputted by CloSpan.

Once the emerging CFS are identified for a community, we extract their supporting nodes, which are not directly outputted by CloSpan. To extract the supporting node set , , for some specific pattern and community , we use a naive approach consisting in accessing ℳ and selecting the nodes whose sequences are the super sequences of .

C. Step 3: SelectingSequential Patterns and Identifying

Anomalies After the emergingpatterns are identified for a given community, together with their support, growth rate and supporting nodes, we need to select the most representative ones, in order to characterize the considered community. We give more attention to the most emerging pattern, i.e. the onewhose growth rate is the highest. However, there is no guarantee for this pattern to cover a sufficient part of the community. And indeed, in practice it appears to be the opposite. It is thus needed to identify other complementary patterns, allowing us to obtain a more complete coverage of the community. Intuitively, we want to find a small number of patterns, such that they cover a significant part of the community, and are different in terms of supporting nodes. This amounts to defining the following constraints:

1. The intersection of the patterns supporting nodes sets must be minimal; 2. The union of these supporting nodes sets must be maximal (if possible: the whole community); 3. The number of patterns must be minimal. Thus, the problem that we want to solve is to find the minimal number of patterns whose supporting nodes sets intersections is minimal while their union is maximal. Note that, in any case, we consider the patterns with the highest growth rate as the most emerging one, and search for additional ones to finish the coverage. In order to solve our problem, we select iteratively the most distant patterns, in terms of supporting node set. We use Jaccard's coefficient [START_REF] Jaccard | The distribution of flora in the alpine zone[END_REF]as a distance measure between the node sets. In case of equality, the growth rate is considered as a secondary criterion. This iteration continues until it converges.

Besides considering patterns according to their growth rate, we also consider them according to their support, as a complementary analysis. For a given community, it is likely the highest supported patterns already include the majority of the nodes. So, unlike for growth rate-based patterns, it might not be necessary to apply the process designed to identify additional patterns. However, this cannot be guaranteed, since it depends on the considered network, attributes and topological measures. Supports are directly produced by CloSpan, so in order to select the highest supported patterns, we just need to analyze each pattern in each community.

Once the most characteristic patterns of a community have been identified (the most emerging one with its supplementary patterns, and the one with highest support), it is possible to use them to detect anomalies, i.e. nodes not following those patterns. Let be the set of supporting nodes of pattern in community , and = 1,.., the supporting nodes forall representative patterns in the same community. Then we define the anomaly nodes set = \ as the set of nodes not following any representative pattern. These nodes are different in the sense they do not follow the general trends of their communities. We detect anomalies automatically when finding representative patterns.

The overall complexity of our method includes calculating all topological measures, creating a global weighted network, applying the Louvain algorithm to detect the communities, applying the CloSpan algorithm to identify the patterns, processing their growth rates, and finally selecting the most representative ones. Among the considered topological measures, the transitivity has the highest complexity:

3 2 , for links and time slices.The processing of the global weighted network is in 2 . According to their respective authors, Louvain is in [START_REF] Blondel | The Louvain method for community detection in large networks[END_REF]and CloSpan in 2 [START_REF] Li | CP-Miner: Finding Copy-Paste and Related Bugs in Large-Scale Software Code[END_REF], where is the number of nodes. However, the operations with the highest complexitiesare the processing of the growth rateand the selection of the most representative sequence, which areboth in 2 , where and are the numbers of communities and of detected sequences, respectively.By definition, we have , and in practice, is generally much larger than .Moreover, the number of time slices is smaller than both and by several orders of magnitude. Considering all simplifications and negligible terms, we geta total complexity of 2 . In other words, the processing time mainly depends on the number of communities and sequences found in the data.

IV. RESULTS

We now present the results obtained on real-world data. We selected the dynamic co-authorship network from [START_REF] Desmier | Cohesive Co-evolution Patterns in Dynamic Attributed Graphs[END_REF], extracted from the DBLP database. Each one of the 2145 nodes represents an author.

Two nodes are connected if the corresponding authors published an article together. Each time slice corresponds to a period of five years. There are totally 10 time slices ranging from 1990 to 2012.The consecutive periods have a three year overlap for the sake of stability. For each author, at each time slice, the database provides the number of publications in 43 conferences and journals. We use this information to define 43 corresponding node attributes, and we add two more: the total number of conference and journal publications. Finally we have a total of 45 attributes. Our descriptors are these attributes and the topological measures described in subsection II-A.

The topological measures are discretized differently, depending on their nature. For node degree, we use the thresholds 3, 10 and 30. For transitivity, which is defined for 0; 1 , they are 0.35, 0.5, and 0.7. For embeddedness, which is also defined for 0; 1 , the intervals are 0.3 and 0.7.These intervals were determined to take into account distributions of these measures on the set of nodes and time slices: different thresholds correspond to areas of low density. For Guimerà et Amaral measures, we use the thresholds originally defined in [START_REF] Guimerà | Cartography of complex networks: modules and universal roles[END_REF], i.e., 2.5 for z et 0.05, 0.6, and 0.8 for P. The threshold used for z distinguishes community hubs > 2.5 and community non-hubs 2.5 . For the conference/journal publications, we consider the values 1, 2, 3, 4 and > 5 . For total journal or conference publications, we use the intervals of 5,10,20 and 50. These ranges are determined according to our knowledge of the domain.

After having applied Louvain, we found 127 communities in the global weighted network, for a modularity of 0.59. This value tells us that global weighted network is clearlymodular. We discarded 96 of the communities, because theycontainonly one node. Amongst the remaining ones, 17 contain more than 10 nodes; the largest one having 335 nodes. We then searched the sequential patterns for these communities only, for a minimum supportof0.02. We could not execute the CloSpan algorithm for the smallest minimum supports, because of memory limitations. For each communities whose size is larger than 40, we find more than 5000 patterns. Most of these patterns include only topological measures.

A. Most Supported Patterns

The most supported patterns are always a sequence of < 2.5 for all communities, with changing sizes. This means the majority of the nodes for each community have the role of non-hub. As a reminder, Amaral&Guimerà define a community hub as a node whose internal degree is well above the average internal degree of its community [START_REF] Guimerà | Cartography of complex networks: modules and universal roles[END_REF]. Thus, the detected pattern means that the majority of the nodes are not particularly well-connected to their communities. Although this type of pattern appears in all communities, we can make a distinction in considering the size of the sequence.

In Table I, we list the size of the most supported sequential patterns with, for each one, its community label, community size and support. The communities whose sizes are between 39 and 45 (i.e. #40, 55 and 77) have long sequences (8, 7 and 7 resp.). Especially, the supports of communities 55 and 77 both reach the maximal value 1. This means in these communities, there is no remarkable hub author for a long time, or even if they appear sometime, they disappear very quickly. This observation is particularly interesting, and reflects the absence of a community leader who would structure the community through its many connections.

For community #115, the size of the sequence is 1, and its support is also 1. This means all the nodes which create this community had the role of non-hub together once, but for the rest of the time slices, they at least took the hub roleonce. For communities #38, 40 and 75, the support is less than 1, so we can say there is at least one hub, different from the rest of itscommunity, and probably leadingit. For communities #38, 40 and 75, the support is less than 1, meaning that an overwhelming majority of nodes plays the role of non-hub for long periods; however a small number of nodes take the place of hub possibly intermittently. Weidentifiedthe authors who do not follow the most supported patterns for these 3 communities. For community #38, Philip S. Yu, Jiawei Han and Beng Chin Ooiare different from their communities. As expected, these nodes have a remarkably high number of connections within their communities, and the represented authors actually have leadership roles in their fields. Further analysis of the data also shows that they publish a total of more than 10 articles per time slice. In addition, they never took the non-hub role. Anomalies for communities #40 and 75 are respectively Hans-Peter Kriegel and Divesh Srivastava. Here also, they are important authors in their community. Their sequences confirm that they are productive and do not take the non-hub role during all time slices.

B. Most Emerging Patterns

For communities whose sizes are between 39 and 45, we do not find any emerging pattern containing a conference or journal. The most emerging patterns have a maximalgrowth rate of 1.79 , which means there is no very distinctive sequential pattern for these communities. For the majority of the large communities, the most emerging pattern includes a specific conference or journal, which can be interpreted in terms of maintheme of the community.

The other descriptors constituting the pattern are topological measures. As the most supported patterns, the item < 2.5 appears the most often amongthe detected patterns. However, these most emerging patterns do not cover the majority of nodes. That is why, as we explained in subsection III-C, we looked for additional sequential patterns while minimizing the intersection of their supporting nodes with the previously chosen ones. These patterns generally consist of topological measures and do not have a very high growth rate. In the following part, we focus on the communities leading to the most interesting results. For each of them, we describe the most emerging pattern and present the anomalies. Each pattern is formally represented in brackets, as a sequence of itemsets which are represented between parentheses.

For community #61, the most emerging pattern is < (ICML PUB. NUM=1) (DEGREE 3-10 Z<2.5)>, with growth rate 3.52 and support 0.30. This pattern refers to the authors who published once in ICML, then had adegree between 3 and 10 and became non-hubs. We extract 7 supplementary patterns to cover all the nodes of thiscommunity. Some of the interesting ones are<(Z<2.5)( Z<2.5)( Z<2.5 CONF. PUB 1-5)(AAAI PUB 1)> with growth rate1.69 and support 0.30,and<(PART. COEFF 0.05-0.6 CIKM PUB. 1)> with growth rate 1.40 and support 0.30. The former pattern refers to nodes that stay nonhub for a while, and then publish in conferences, before publishing inAAAI while losing their status of non-hub (without massively becoming hubs). The latter has no temporal dimension, but it shows the existence of nodes publishing in CIKM while having a peripheral position in the community, i.e. being significantly connected to other communities. The anomalies of this community are Alex AlvesFreitas, Claire Cardie ,Edwin P. D. Pednault. Among these authors Alex AlvesFreitas does not have any publication for the first 8 time slices,beforehe starts publishing very efficiently in various conferences otherthan ICML or AAAI and journals. This can be interpreted as a Junior searcher progressively maturing. For the other two authors, while Claire Cardiepublishes inICML during thefirst 6 time slices at least once routinely, Edwin P. D. Pednaultnever published in not only ICML but also AAAI or CIKM.

The pattern <( PODS PUB 1)> is the most emergingonein community #75. Its growth rate is 3.59 and its support is 0.40. This pattern shows that 40% of the authors of this community published at least once inPODS, which is a behavior significantly different from the rest of the network. There are 4 supplementary patterns to cover the rest of the community. These patterns refer to non-hub and peripheral nodes whose transitivity is very high, which means authors from this community tend to work in subgroups. The anomalies are Ninghui Li, Feifei Li, AbdullahMueen who never published in PODS. The most emerging pattern of community 106 is <(Z<2.5) (Z<2.5) (Z<2.5) (Z<2.5) (Z<2.5) ( PART. COEFF 0.05-0.6 KDD PUB. 1)> with growth rate 2.87 and 0.40. This pattern refers to non-hub nodes staying non-hub for a while, then becoming peripheral nodes and publishing once in KDD. This evolution reflects a change in the community connectivity: nodes are at first loosely connected to other nodes in their own community, this overall internal connectivity improves, while the external connectivity (i.e. links with other communities) tend to become more heterogeneous. There are 4 supplementary patterns to cover the whole community. The supplementary patterns refer to the nodes with ultra-peripheral role, whose connections are usually insidetheir own community. Two anomalies of this community are Stan Matwin who is publishing in KDD more than one article routinely for every time slice,whilenot taking the non-hub role, and Hua-Jun Zeng who never publishes in KDD. In fact, Hua-Jun Zeng, while he does not produce any publication for the first 5 time slices, becomes very productive afterwards.

The most emerging pattern of community #45 is <(VLDB PUB. 3)( DEGREE 3-10 Z<2.5 )> with growth rate 6.40 and support 0.30. This sequence tells us that there is a remarkable group of authors who published 3 times in the VLDB conference,before seingtheir degree reach a valuebetween 3 and 10 and holding a non-hub role. There are 6 more sequential patterns that we have found to cover the rest of the community. One of them is<( Z<2.5CONF. PUB 1-5)( Z<2.5 EMBED 0.3-0.7 ICDE PUB. 1 )>with growth rate 2.30 and support 0.30. This pattern covers the non-hub nodes who published between 1 and 5 times in aconference, followed by being non-hub and having some connections outside of their community and publishing once in ICDE. The anomalies are Ingmar Weber, Anastasia Ailamakiwho do not have any publication for the first 7time slices, while they both become more and more productive for the last 3time slices. Their publication number increases fast.

C. Final Observations

To summarize our observations, the most emerging patterns in almost all communities usually include being non-hub and having a small number of publications in various journals or conference. Depending on the conferences or journals appearing in these patterns, it is possible to deduce the main theme of these communities. For some communities, however, the emerging sequential patterns are purely topological (no attributes). We can then assume that the members of these communities do not publish in a sufficiently homogeneous way so that it can appear under the form of patterns, which is itself a characteristic of the community. Another reason may simply be that the community members are connected to each other for different reasons than a common research theme (e.g. geographic or logistic constraints), in which case those do not appear in the attributes selected for our study. Regarding anomalies, one can distinguish different types of profiles. Some seem tocorrespond to authors whose main theme is different from that of the community in which they were placed. In some cases, we found out the authors had clearly moved to a different theme, or just started working in a given theme. They may also be authors active in another field, including conferences and journals not part of those used in the data we considered here. Another profile is that of junior researcher, whose number of publications and community position evolvjointly.These authors do not seem very active in their field in the first time slices. However, their number of publication and importance in their community increase with time.

V. CONCLUSIONS In this work, we tackled the problem of the characterization of communities in dynamic and attributed complex networks. We proposed a new representation of the information encoded in the network to store the topological information, the node attributes and the temporal dimension simultaneously. We used this representation to perform a search of emergingsequential patterns. Each community could then be characterized by its most distinctive patterns. We also took advantage of patterns to detect and characterize anomaly nodes in each community. We applied our method to a scientific collaboration network constructed from the public database DBLP. The results showed that our method is able to characterize the communities,in particular their research topic. The anomaly nodes we identified correspond to different types of profiles, such as community leaders, emerging researchers, or others changing research theme.

To our knowledge, this is the first formulation of the characterization of communities as a problem of data mining. Our goal was to overcome the limitations of the few existing studies [START_REF] Lancichinetti | Characterizing the Community Structure of Complex Networks[END_REF][START_REF] Tumminello | Community characterization of heterogeneous complex systems[END_REF][START_REF] Labatut | Detection and Interpretation of Communities in Complex Networks: Practical Methods and Application[END_REF] by proposing a systematic approach, taking into account the topologic structure, the nodal attributes and time. The representation of data we use has not been applied to the treatment of graphs before. The proposed process to extract the most relevant patterns based on a sequential pattern under constraint is original and we showed the consistency of interpretations with an application on a real-world network.

To limit the complexity of this first approach, we deliberately limited our analysis method by not considering the evolution of communities over time. In future works, we plan to take advantage of such communities, by inserting the appropriate information in the database used for the search patterns. We also plan to apply our method of analysis to other types of networks to explore its characterization capabilities. As another perspective, we can better use our representations of dynamic attributed network. Here we are only interested in mining emergingsequences. However, our data representation of the network can also be used to handle queriesconcerning the nodes,expressed in terms of topological measures or attributes. For instance, in our experiment, we saw that there were many nodes whose behavior was not typical of their community. Such queries could be used to studythemin further details,and better understand how they are different.

Fig. 1 .

 1 Fig. 1. Example Dynamic Network with 3 time slices, 7 nodes and 1 attribute