NON-OVERLAPPING COMMUNITY DETECTION HOCINE CHERIFI

Introduction

Many real-world systems are typically made of numerous interacting elements. With simply a local knowledge of the overall system and minimal communications with each other, these individual elements tend to achieve a global goal. Such systems can be adequately described using graph theory. Here, individuals are the nodes of the graph and a link between two nodes represents the interaction. There are many variations of this basic model. For instance, links can be directed, i.e., pointing in one direction. For example, in Web networks nodes are the Web pages, and oriented links represent the hyperlinks pointing to the pages. It is also possible to assign to each link of the graph a weight proportional to the intensity of the connections. To illustrate, in the air-transportation network, nodes represent airports, and there will be a link if there is a flight between two airports. The number of flights between two destinations can weigh the links. In practice, there may also be more than one different type of node or more than one different type of link in a network. A network is said to be "multi relational" or "multiplex" if it contains two or more kinds of relations on a single type of node. This is typical of social networks where the primary objects of study are people and their multiple types of relations. Graphs may contain nodes of distinct types as well. In such cases, they are called "multimodal networks." For example, bipartite graphs contain two types of nodes with links running only from one type to the other. Affiliation networks, in which people are joined together by common membership of groups, can be represented using such a graph. These two types of nodes represent people and groups. A link accounts for the fact that an individual belongs to one group. Besides these extensions, one can also consider many other levels of sophistication such as adding different features to nodes and links and so on.

To understand network behaviour thoroughly, proper knowledge of its topological properties is required. This analysis can be performed at different levels of granularity ranging from microscopic (at the node level) to macroscopic (at the overall network level). However, identifying intermediate scales is a critical issue in order to gain insight into their functional organization. Indeed, communities have always been ubiquitous as elementary forms of organization both in society and nature. As an example, in biology, groups of proteins having the same specific function within the cell can be identified in protein-protein interaction networks. On the World Wide Web, communities correspond to groups of pages dealing with the same or related topics. Therefore, uncovering the community structure is crucial to understanding many real-world networks. It may specifically help to formulate realistic mechanisms for their genesis and evolution.

Although there has been a tremendous effort regarding the communitydetection issue, there is no formal consensus on a definition that captures the gist of a community. It is intuitively understood as a cohesive group where members interact with each other more intensely than with those outside the group. As there are many diverse understandings of how cohesiveness translates in formal graph-theoretic terms, various algorithms have appeared in the related literature to discover this hidden structure of a network.

In addition to the variety of definitions, communities can overlap or not. Historically, a great deal of attention has been devoted to nonoverlapping community-detection algorithms. In this case, the network is partitioned into separated communities where each node belongs to only one group. Even so, in some situations -particularly in social networks -a node might belong to different communities. In order to reflect this intuition more precisely, there has been a growing interest in the study of overlapping communities in recent years.

Besides the distinction between overlapping and non-overlapping communities, one may consider either global or local approaches to the community-detection problem. Certainly, for networks that are too large and evolve too quickly to have a fully known structure, one cannot rely on global knowledge to uncover a community structure. In order to overcome this limitation, the so called "ego-centred" community methods attempt to find communities related to a single node.

The richness of definitions and features of the community-detection problem has led to an impressive body of literature. In fact, many community-detection methods and surveys have been introduced in recent years. The goal here is to present a state-of-the-art of the most mature research in this area. We will therefore concentrate on non-overlapping community detection with the basic graph model. In this chapter we will give an overview of the most influential approaches to community detection that encompass most of the main methods and techniques. A special focus will also be given to community evaluation.

The chapter is organized as follows: In the preliminaries section, we will review necessary definitions to ensure a good understanding of all elements being addressed. We will then present and analyse the different models used to represent real-world complex networks with a community structure in the network-model section. The taxonomy of communitydetection algorithms will be discussed in the following section, and the most influential community-detection methods will subsequently be presented. In the performance evaluation section, we will describe performance measures commonly used to evaluate community-detection algorithms. Finally, test results conducted with synthetic benchmarks will be analysed in order to provide insight into the advantages and drawbacks of the evaluated algorithms

Preliminaries

In order to understand a complex network fully, one has to analyse its structural features from the microscopic level to the macroscopic level without neglecting the mesoscopic level. The microscopic level concentrates on the differences between individual nodes in order to identify the most influential ones. At the macroscopic level, statistical measures are used to summarise some of the overall network features. Meanwhile, the mesoscopic level results from properties shared by groups of nodes. In this section, we will briefly recall the main measures used to capture, in quantitative terms, their underlying organizing principles.

Microscopic Topological Properties

The degree of a node refers to the number of links attached to the node. It can be understood as a measure of the node's leadership in the network. Highly connected nodes, referred to as hubs, are critical elements of the networks. A bottleneck is a node controlling the flow from one part to another part of the network whose deletion increases the number of unconnected sub-networks. A bridge is a link connected to bottlenecks. As such, the network is separated into unconnected sub-networks when the bridges are removed.

A clique in an undirected graph is a subset of nodes set such that each node is linked to all the other nodes of the subset (complete graph). Its size corresponds to the number of nodes it contains.

The local clustering coefficient quantifies the embeddedness of a node in a clique. It is ascertained by taking the proportion of links between the nodes within its neighbourhood divided by the number of links that could exist between them. Its value is 0 if none of the node's neighbours are connected, and its value is 1 if all of the neighbours are connected. The origins of the local-clustering coefficient can be traced back to sociology, where similar concepts have been used. In a typical social network, a person's friends are very likely to know each other. This inherent tendency for people to cluster in circles of friends, in which every member knows every other member, is quantified by the clustering or transitivity coefficient. Such a concept -known also as a "fraction of transitive triples" in sociology -is used to capture the degree of social embeddedness that characterizes the nodes.

The distance between two nodes is the number of links in the shortest path existing between those nodes in which each link and node appear at most once.

Centrality determines how influential a node is within a network. Degree, closeness, and betweenness centrality are the most widely used measures to define such a characteristic. Degree centrality measures the involvement of a node in the network by the number of nodes connected to it. This local definition does not take into account the position of the node in the network and therefore cannot measure its ability to reach others quickly. Closeness centrality captures this feature. It is based on the inverse sum of the shortest distances to the other nodes of the network. Betweenness centrality asserts the ability of a node to play a "broker" role in the network by measuring how well it lies on the shortest paths connecting other nodes.

Macroscopic Topological Properties

Undirected real-world networks are known to share some common properties. In this section, we will present the most usual properties that are implemented to characterize complex networks.

Density is the ratio of the number of existing links to the number of possible links. For a complete network (where all nodes are connected to all other nodes), the density is 1. A dense network is a network in which the number of links of each node is close to the number of nodes. A sparse network, by contrast, is connected by a low number of links only.

The small-world property refers to the low average distance value between any two nodes of a network. This property has been popularized by the ''six degrees of separation'' concept, i.e., anyone on the planet can be connected to any other person through a chain of acquaintances that has no more than five intermediaries on average. This is typical of many realworld networks where shortcuts connecting different areas of the networks allow for the reduction of distance between any two network nodes. For instance, on the Internet, a computer can be reached on average through six routers, and the co-authors in mathematics are on average within four authors from each other.

The global clustering coefficient reflects the tendency of link formation between neighbouring nodes in a network. It is also called transitivity. This characteristic can be measured by the mean value of the local clustering coefficients. (Note that alternative definitions exist for this quantity as well.) Transitivity is known to be higher in real-world networks as compared to uncorrelated random networks in which triangles are sparse.

Degree distribution measures the statistical repartition of the network nodes' degrees. Along these lines, one of the most interesting developments in our understanding of complex networks is that they exhibit an inhomogeneous distribution with few nodes linked to many other nodes and a large number of poorly connected nodes. In particular, for a large number of networks, such distribution can be adequately described as a power-law distribution. These networks are often referred as "scale-free networks" because their degree distribution does not depend on their size. Related experimental studies show that the exponent value of the power law usually ranges from 2 to 3 [START_REF] Albert | Statistical Mechanics of Complex Networks[END_REF][START_REF] Boccaletti | Complex Networks: Structure and Dynamics[END_REF][START_REF] Newman | The Structure and Function of Complex Networks[END_REF].

The degree correlation measures the tendency of nodes to associate with other nodes sharing the same characteristics and especially the same degree values. In assortative networks, the nodes tend to associate with their connectivity peers, and the degree correlation is positive. In disassortative networks, high-degree nodes tend to associate with lowdegree ones, and the degree correlation is negative. Social networks appear to be assortative while information, technological and biological networks appear to be disassortative.

The centralization measures the ability of a network to be focused around a few central nodes. Centralization measures are based on the differences between the centrality scores of the most central point and those of all other points. The definition of centralization measures is general, so it can be based on any centrality measure. Its value ranges from 0 to 1 for the local centrality concepts presented previously. Correspondingly, a value of 0 is obtained on all three measures for a "complete" graph, while a value of 1 is achieved for a "star" or "wheel" graph. Very centralized networks are very sensitive to the dominating central node failures or attacks, while less centralized ones are more resilient.

Mesoscopic Topological Properties

At this scale, the communities are elementary units of the topology. Before addressing community properties, the first issue to be solved is to express a formal definition of a community. This is quite a challenging task because until now, the debate has remained open so that there is no consensual definition. There are also many interpretations of the intuition of cohesiveness and separation tied to the community notion. Moreover, in many cases, community-detection algorithms are not based on a formal definition of the communities. In an exhaustive survey, Fortunato (2010) identifies three types of definitions: local, global, and similarity-based definitions.

Local definitions consider communities as autonomous entities that can be evaluated independently of the rest of the graph except for their local neighbourhood. Cohesion is related to basic patterns such as a clique or relaxed variants. The community structure is obtained by searching for maximal subsets of the pattern.

In global definitions, communities are defined with respect to the graph as a whole, and a global criterion is used to uncover the community structure. More often, the criterion compares a property of the graph to a similar random graph known to have no community structure. Many global definitions are based on the density of nodes guided by the intuition that a community is a group of densely connected nodes that are sparsely connected to the rest of the network. Community-detection algorithms try to maximise the number of links inside the groups while minimising the number of edges between nodes in different groups.

Node-similarity definitions assume that communities are made of nodes with common properties. Irrespective of whether they are connected by an edge or not, nodes are classified according to a similarity measure of a given local or global property (distance, commute time between nodes, etc.). Recently, Coscia et al. [START_REF] Coscia | A Classification for Community Discovery Methods in Complex Networks[END_REF] introduced a meta-definition of a community based on the following intuition: a community is made of entities that are closer to others within the community than to the ones outside it. A community is defined as a set of entities sharing a "common set of actions". This meta-definition encompasses the vast majority of models used in the related literature. For example, considering the links between two nodes as a particular kind of action allows for representing density-based definitions. Node-similaritybased definitions can be apprehended by modelling the similarity measures as the similarity of the action set. However, note that some definitions of community cannot fit into these taxonomies.

While the extreme richness of definitions and features has led to the publication of extensive literature on the community-discovery problem, few authors have been interested in the analysis of real-world network community structures. An important issue in this regard is whether or not there is a characteristic size for a community. Studies show that community-size distribution is inhomogeneous. It can be adequately described by a power law [START_REF] Guimerà | Self-similar Community Structure in a Network of Human Interactions[END_REF]Newman 2004a) with an exponent ranging from 1 to 3 [START_REF] Palla | Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society[END_REF]. Thus, many small communities coexist with a few very large ones.

The "embeddedness" of a node measures the proportion of its neighbours belonging to its community. Its value is 1 when all of the node neighbours are in its community, whereas it is 0 when all its neighbours belong to different communities. In real-world networks, low-degree nodes predominantly have a very high embeddedness. Some networks (like the Internet, communication networks and biological networks) exhibit a peak of around 0.5, whereas others have a more uniform distribution (such as social networks and information networks) [START_REF] Lancichinetti | Characterizing the Community Structure of Complex Networks[END_REF].

The density of a community indicates the cohesion of the community as compared to the overall network density. Undoubtedly, a community is supposed to be denser than the network it belongs to. The scaled density is obtained by multiplying the density by the community size [START_REF] Lancichinetti | Characterizing the Community Structure of Complex Networks[END_REF]). Its value is 2 when the community has a tree structure. On the other hand, if it is a completely connected subgraph, its value is the size of the community. According to this measure, real-world networks such as the Internet or communication networks have essentially tree-like communities. Meanwhile, on social and information networks, the scaled density increases with the community size, suggesting a clique-type behaviour. Then we have biological networks, which exhibit a hybrid behaviour as their small communities are tree-like, while the large ones are denser and close to cliques [START_REF] Lancichinetti | Characterizing the Community Structure of Complex Networks[END_REF].

Hub dominance reveals the presence of hubs in communities. This factor corresponds to the maximal internal-degree ratio in the community and the maximal theoretical degree given the community size. Its value is 1 when at least one node is connected to all other nodes in the community. Yet it can reach 0 in the unlikely case where no nodes are connected. For communication networks, the hub dominance value is close to 1 and rather independent of the community size. More generally, complex networks do not have as many hubs in their large communities. This is why their hub dominance generally decreases when the community size increases [START_REF] Lancichinetti | Characterizing the Community Structure of Complex Networks[END_REF].

Modularity measures the deviation of "intra-community" links' repartition of a given community structure compared to the one obtained in a similar network with links placed at random. This measure is based on the idea that the number of links between nodes in a community is higher than in a random network. It has been introduced by Newman and Girvan to measure the quality of a partition. When the communities are not better than a random partition, or when the network does not exhibit any community structure, its value is low. Moreover, it can be negative if the network has a disassortative structure. For real-world networks, modularity values between 0.3 and 0.7 are considered high. Modularity is used as a performance measure to quantify how good a given network partition is. It is also an optimisation criterion in many communitydiscovery algorithms. Nonetheless, one should note that modularity presents some drawbacks. For example, it is sensitive to community size [START_REF] Fortunato | Resolution Limit in Community Detection[END_REF]Lancichinetti and Fortunato 2011) and it is possible to find partitions of random networks with relatively high modularity values [START_REF] Guimera | Modularity from Fluctuations in Random Graphs and Complex Networks[END_REF].

Networks Models

Traditionally, large networks with no apparent design principles have been described as "random graphs." The classical Erdös-Reyni random network model, abbreviated as ER, is the most influential model to represent such graphs. It is based on the assumption of independent and purely random link formation. Even if it shares with real-world networks a short average distance, this model does not capture the main characteristics of real-world data. Indeed, the clustering coefficient is several orders of magnitude larger in real-world networks. Furthermore, its degree distribution follows a Poisson law, while a power law is a better fit for real-world networks. Note that the power law indicates the presence of hubs, whereas these highly connected nodes have a very low probability in Poissonian distribution. Given that the Erdös-Reyni model is evidently unable to mimic real networks, various attempts have been made to find appropriate theoretical models. In addition, since the seminal paper of Watts and Strogatz on "small-world networks" was published, activity in this field has been growing. From that time on, the major focus of research has moved from small-world networks to "scale-free" networks. Within this framework, there exist two main approaches: static or dynamic network models. Static models give a snapshot of a real-world network, while dynamic models try to capture how the network actually grows.

The so called "inhomogeneous random graph" is a static model aimed at generating graphs with a given degree distribution. To do so, equal edge probabilities of the Erdös-Reyni random graph are replaced by edgeoccupation statuses that are independent and are moderated by certain node weights. The Configuration Model, abbreviated as CM, is another static model introduced to generate random networks with controlled degree distribution [START_REF] Molloy | A Critical Point for Random Graphs with a Given Degree Sequence[END_REF]. It operates in two steps. First, to each node a number of half links called "stubs" is assigned at random according to the degree distribution. Then, pairs of stubs are chosen at random, and a link is made between the corresponding nodes. So even though the node degree distribution of the graph remains intact, the configuration model results in a completely random network. The reader should observe that vertices having self loops as well as multiple edges may occur. However, such types of connections are scarce. Furthermore, one can add a constraint to avoid such patterns.

The network models discussed thus far assume that the size of the graph is fixed, while many real-world networks grow continuously throughout the lifetime of the network by the addition of new nodes. In order to explain the network-formation process, Barabási and Albert (1999) popularized the concept of preferential attachment introduced by Yule in the context of species evolution. Their model, hereafter referred to as the BA model, is based on two ingredients: growth and preferential attachment. Starting with a small network of arbitrary structures where each node is at least connected to one other node, new nodes are sequentially added with a number of links connected to them. These links are attached to another node with a probability proportional to the degree of the receiving node. Such a process, also known as "the rich get richer," favours highly connected nodes. For a large network size, it leads to a scale-free degree distribution with an exponent value equal to 3. Following the publication of Barabási's and Albert's study, a large body of work investigating dynamic models appeared in the relevant literature. Building on this model, many fitness-based models have been proposed [START_REF] Nguyen | Fitness-Based Generative Models for Power-Law Networks[END_REF]. The basic idea of such models is to use more sophisticated features than the simple degree value to explain the propensity of a node to attract new links. Once a fitness value is associated with each node, the growing process can be implemented.

To date, many network models can generate scale-free features based on different ideas and mechanisms, but few network models with community structure have been proposed. In the rest of this section, we provide an overview of the most famous benchmarks specifically designed for community-structured complex networks. Also, we report a recent work showing that these models can be improved to reproduce the structural properties observed in real networks.

In order to test the performance of community-detection algorithms on networks with varying degrees of community structure, [START_REF] Girvan | Community Structure in Social and Biological Networks[END_REF] introduced one of the first models (abbreviated as GN). Each graph is constructed with 128 nodes separated in 4 communities of equal size and each node is linked on average to 16 nodes. Links joining nodes inside a community are placed independently at random according to a given intra-community probability value. Conversely, nodes of different communities are linked at random according to an intercommunity probability value. The strength of community associations is controlled by the ratio of intra-community to inter-community links. Although this model deviates drastically with measurements from realworld networks, it has been widely used in order to test communitydetection algorithms [START_REF] Donetti | Detecting Network Communities: a New Systematic and Efficient Algorithm[END_REF][START_REF] Duch | Community Detection in Complex Networks Using Extremal Optimization[END_REF][START_REF] Girvan | Community Structure in Social and Biological Networks[END_REF][START_REF] Radicchi | Defining and Identifying Communities in Networks[END_REF]. First of all, the network size is not realistic. Nowadays, many complex networks are actually made of millions of nodes. Furthermore, the nodes' degrees follow a Poisson distribution, while in many real networks, the degree distribution displays a fat tail. Finally, communities have identical size, whereas experimental studies on real networks show that the community-size distribution follows a power law. In order to overcome these limitations, several variants of this model have been defined producing larger networks and communities with heterogeneous sizes [START_REF] Danon | Effect of Size Heterogeneity on Community Identification in Complex Networks[END_REF][START_REF] Pons | Computing Communities in Large Networks Using Random Walks[END_REF].

More recently, [START_REF] Bagrow | Evaluating Local Community Methods in Networks[END_REF] introduced a different approach based on rewiring an initial network such as a community structure. Starting from a graph with a given degree distribution, nodes are randomly assigned to different communities. Afterwards, a random pair of intercommunity links is rewired to be intra-community links. This switching process of the link-pair extremities preserves the degree distribution of the network. In his experiments, Bagrow used the BA model to generate the initial network. Meanwhile, the community structure is made of four equally sized communities, and 25% of the edges are rewired. Keep in mind that since the partition is random, the initial modularity is very small. This is because with edges being moved within communities, the modularity increases with the proportion of rewired pairs. [START_REF] Lancichinetti | Benchmark Graphs for Testing Community Detection Algorithms[END_REF] introduced a model based on a rewiring principle, which has obvious advantages over Bagrow's scheme. In this model, denoted as LFR, users chooses the network size. Furthermore, the degree of the nodes and the community size can be adjusted in order to follow a power-law distribution while controlling the exponent value. The LFR algorithm produces networks with non-overlapping communities using a two-step process. First, a scalefree network with controlled size n is generated using the configuration model. The minimum and maximum degree are chosen such that the degree distribution follows a power law with a given average degree value <k> and exponent γ. Then, the second step is applied in two phases. First, the communities are randomly drawn so that their distribution size follows a power law with a given exponent value β. Second, an iterative rewiring process takes place to control the fraction of links μ shared by a node with nodes in other communities. As it is generally not possible to meet such a constraint exactly, this tunable parameter called the "mixing coefficient" is only approximated in practice. Its value determines how clearly the communities are defined. For small μ values, the communities share only a few links and are therefore clearly separated. Increasing μ, the proportion of inter-community links grows and the original communities gradually disappear.

The configuration model used in the first step of the LFR model is very flexible as it is able to produce networks with any size or degree distribution. Nevertheless, it is known to generate networks with no correlation between the degrees of connected nodes [START_REF] Serrano | Weighted Configuration Model[END_REF] and low transitivity when degrees are power-law distributed [START_REF] Newman | The Structure and Function of Complex Networks[END_REF]. To overcome these drawbacks, more realistic models can be used. For this purpose, in (Orman, Labatut, and Cherifi 2013) two alternative models have been evaluated : the BA model and a fitness-based model called evolutionary preferential attachment [START_REF] Poncela | Complex Cooperative Networks from Evolutionary Preferential Attachment[END_REF]) abbreviated as EV. Both models generate scale-free networks with a desirable size and average degree.

In the BA model, the capacity of a node to attract links from newcomers depends on its current degree value while in the EV model it is linked to its evolutionary fitness. This dynamical-variable value is proportional to the payoffs obtained when playing a prisoner's dilemma game with its neighbours. In this setting, nodes with higher scores are more attractive to newcomers because their strategy has proven to be successful. Meanwhile, in every iteration, each node plays either cooperation or defection against all of its neighbours. It gets a total score depending on the individual results: 0 for unilateral cooperation or bilateral defection, 1 for bilateral cooperation, and b for unilateral defection, with b >1. The first move is randomly chosen, whereas the next one depends on the respective results of the considered node and a randomly picked neighbour. If the neighbour's score is better, the node might switch its strategy with a probability depending on the difference between their scores. A parameter called the "selection pressure" (ε) allows modulating the influence of fitness in the attachment mechanism. The evolutionary dynamic has no influence for ε=0 while the fitness scores are fully considered for ε=1. According to its authors, when the selection pressure is large, networks generated by this model display both high transitivity and degree-correlation values.

Hereafter, we will refer to the network models by using the following abbreviations: LFR-CM denotes the original LFR method, while LFR-BA and LFR-EV are the modified versions utilising respectively BA and EV in the first step of the algorithm. In order to illustrate the comparative realism of the networks generated by the three algorithms, we report representative results on the degree correlation, the clustering coefficient, and the degree centralization on figure 11-1. More details are given in (Orman, Labatut, and Cherifi 2013). For every value of the mixing parameters ranging from 0.05 to 0.95 with a step value of 0.05, 25 networks have been generated, and the mean and standard deviation values of the topological properties have been computed. Note that parameters values have been chosen such that generated networks exhibit realistic topological properties.

The models exhibit a very different behaviour concerning the degree correlation. Specifically, for LFR-EV, the degree correlation decreases almost linearly when the proportion of inter-community links increases. Whatever the mixing coefficient value, it exhibits a rather higher degree correlation value as compared to its competitors. In contrast, the degree correlation increases with the mixing parameter in LFR-BA. This almost linear growth is nevertheless observed with a lower slope and lower variance estimates. We also have LFR-CM, which is the less realistic benchmark. Starting from a reasonable value when the communities are well separated, it decreases rapidly and oscillates around zero for mixing coefficient values greater than 0.4.

The behaviour of the three algorithms is quite similar regarding the clustering coefficient. As the proportion of inter-community links increases, transitivity decreases. Nonetheless, the three models exhibit realistic transitivity when the communities are more or less well separated. Most definitely, real-world networks with a transitivity greater than 0.3 are considered highly transitive (da F. Costa et al. 2008). Whatever the mixing coefficient value, LFR-BA is always the worst, while the results are more mixed for the two other models. In addition, LFR-CM outperforms LFR-EV when the mixing coefficient is less than 0.3, and the latter takes a slight advantage for higher values. In any case, the results are not very satisfactory for high μ values.

Degree centralization is very insensitive to the mixing-proportion variations. It is higher for LFR-BA and LFR-EV as compared to LFR-CM. Moreover, there are virtually no influential nodes in the networks generated by LFR-CM as suggested by the very low values of the centralization. The attachment mechanism used in the dynamic models tends to generate nodes highly connected to their neighbours. As such, the presence of these hubs results in higher centralization values. Note that the same behaviour is observed with closeness and betweenness centralization.

Overall, we can conclude that dynamic models produce more realistic networks, at least for the degree correlation and the centralization as compared to the original LFR model. Even so, except for well separated communities, the three models fail to reproduce networks with high transitivity values. The explanation may originate from the rewiring process or more fundamentally from the construction process of these networks. Indeed, pairwise relations (dyads) between nodes make for the fundamental unit when modelling a network, regardless of whether they come by growth or probabilistic models. The basic assumption underlying these models is that dyads are independent. However, the large clustering coefficient observed in many networks hints at dependence between the connections. This observation thusly suggests that models should be defined based on triads (sets of three nodes) rather than dyads [START_REF] Winkler | Motifs in Triadic Random Graphs Based on Steiner Triple Systems[END_REF].

Algorithms

Community detection is a prolific subject in the literature regarding complex networks. A great variety of algorithms have been developed so far to deal with this issue. However, there has evidently been no clear and precise definition of what a community is, so the problem has been dealt with from many points of view. For instance, a community has been expressed as a graph partitioning, community mining, spectral analysis, an optimisation problem, a statistical problem, and so on. Some recent surveys that aimed at providing an overview of the field have proposed taxonomies of the community-detection methods. Even in the relatively mature area of non-overlapping community detection, there is no consensus on a classification. To this end, the main difficulties lie in the fact that there is an overlap of methods and in the underlying definition used, if any. Finally, work is still in progress, and new solutions are constantly scrambling the proposed taxonomies.

Not to add to the confusion, we adopt in the following section the classification proposed in [START_REF] Coscia | A Classification for Community Discovery Methods in Complex Networks[END_REF]. To our knowledge, this is the most recent work on the subject. Furthermore, rather than focusing on how communities are detected, the classification is based on the definition of the community used by the algorithms. Starting from a meta definition of a community, algorithms are classified into eight categories according to different interpretations of the meta definition. Using the same terminology, we present the most influential categories. Among the various solutions existing in the pertinent literature, we also present a representative sample of community-detection algorithms known for their effectiveness or their popularity.

Internal Density

Internal density is highly influential in the community-detection literature. It is based on the widespread assumption that a community is a set of densely connected nodes. Generally, the algorithms in this category try to expand or collapse the node partitions in order to optimize a given density function. Despite the fact that different density functions have been proposed, the key concept linked to the approach is modularity. Under this definition, a community is a set of nodes with a higher density than what would be expected in a random network with the same degree distribution. Numerous solutions to this NP complete-optimisation problem have been proposed ranging from greedy heuristics to stochastic formulations. We present here three widespread algorithms.

FastGreedy is an agglomerative hierarchical clustering method developed by Newman et al. (Newman 2004b). Starting with each node in its own community, it iteratively merges the two communities producing the greatest modularity increase. At each step, communities sharing one or more links are allowed to merge. The process stops when all of the nodes are in the same final community. At this point, the outcome is a dendrogram representing the hierarchical decomposition of the network into communities. The optimal community structure is obtained by cutting the dendogram at the maximum point of its modularity.

Louvain is another greedy agglomerative hierarchical algorithm proposed by [START_REF] Blondel | Fast Unfolding of Communities in Large Networks[END_REF]. In this case, two phases are repeated iteratively. Starting with each node in its own community, the gains in modularity obtained by placing a node in the same community than its neighbours are evaluated. The community offering maximal gain is then retained. This process is applied repeatedly and sequentially for all nodes until no individual move can improve the modularity. At the end of this first phase, the algorithm yields the first partitioning scheme. In the second phase, a new network is built whose nodes are the communities found during the first phase. The intra-community links are represented by selfloops, whereas the inter-community links are aggregated and represented as links between the new nodes. It is then possible to start the first phase again on the resulting weighted network. This process is iterated until only one community remains.

Spinglass was introduced by Reichardt and Bornholdt [START_REF] Reichardt | Statistical Mechanics of Community Detection[END_REF]. The authors show that searching for the optimal modularity partition is analogous to finding the spin configuration that minimizes the energy of a statistical physical model named Potts spin glass. In this setting, the spin states are the hidden community membership. Simulated annealing is used to minimise the non-quadratic energy function. Note that any other scheme that can deal with this combinatorial optimisation problem can be implemented.

Leading Eigenvector is a spectral partitioning technique introduced by Newman (Newman 2006). While in traditional methods, a good partition is one that minimises the number of links running between the communities (known as cut size), Newman claims that a good partition is one where it is smaller than expected. In other words, rather than minimizing the cut size, he proposes to minimise the modularity. To do so, the modularity is written in matrix form, and the principal component analysis is applied on this matrix.

Notice that although widely used, modularity suffers from some limitations. In particular, it fails to identify communities smaller than a network-dependent critical size. For a good review of modularity limitations, refer to [START_REF] Good | The Performance of Modularity Maximization in Practical Contexts[END_REF].

Closeness

The closeness approach is based on the assumption that a community member can reach any other member of the same community by crossing a smaller number of links as compared to the network's average distance. Undoubtedly, a community is supposed to be a smaller world than the overall network. Inspired by this definition, several algorithms rely on random walks to uncover the community structure. Recall that in a random walk, a walker performs a series of sequential moves from node to node, and each move is chosen randomly from its neighbours. The basic idea of these algorithms is to perform several random walks and to cluster the nodes frequently crossed in the same walk. We will present three wellknown algorithms of this type.

At the heart of the Markov Cluster algorithm lies the idea of simulating a controlled flow through random walks in order to detect communities (Van Dongen 2008). The basic idea here is that the current is strong in the communities yet weak between communities. Promoting the flow where the current is strong and mitigating the flow where the current is weak will result in no flow between communities, thus revealing the community structure of the network. This algorithm simulates random walks by iteratively applying two transformations (expansion and inflation) on the network-transfer matrix until convergence occurs. The final matrix can be interpreted as the adjacency matrix of a network with disconnected components representing the communities. Expansion corresponds to the computation of random walks of higher length. Since higher length paths are more common within communities than between different communities, the probabilities associated with node pairs lying in the same cluster will, in general, be relatively large as there are many ways of going from one to the other. Inflation changes the probabilities of random walks, favouring more probable walks over less probable ones. This operation boosts the probabilities of intra-community walks and demotes intercommunity walks. Eventually, iterating expansion and inflation results in the separation of the graph into distinct components interpreted as communities.

WalkTrap [START_REF] Pons | Computing Communities in Large Networks Using Random Walks[END_REF] is based on the intuition that random walks are able to unveil the real distance among nodes. Based on the information given by random walks, a distance that captures structural similarity between the nodes is computed. At this point, the communitydetection problem reduces to a clustering one. The algorithm thusly uses a hierarchical agglomerative approach. At each step, the two communities that minimize the variation of the squared distances' mean value between each node and its community are merged. Ultimately, to find the optimal community structure, the dendrogram is cut at the maximum point of the modularity.

InfoMap [START_REF] Rosvall | Maps of Random Walks on Complex Networks Reveal Community Structure[END_REF] uses a compression technique to describe the information flow on networks. Random walks of a given length and with a given probability of jumping to a random node are performed. Each walk is described as a sequence of steps inside a community followed by a jump through a two-level nomenclature based on Huffman coding. The first one is used to distinguish communities in the network and the other to distinguish nodes in a community. Each node codeword is derived from the visit-node frequency of an infinitely long random walk. This coding strategy leads to a compact representation of the walks. Indeed, with a partition featuring limited inter-community links, the walker is statistically more likely to stay longer inside communities. Therefore, only the second part of the nomenclature is needed to describe its path. The authors showed that the optimal partitioning problem is reduced to finding the minimum description length for all of the walks.

Diffusion

The main idea with diffusion is to consider a community as a set of nodes grouped by the propagation of the same property or information in the network. Algorithms based on this definition usually perform a diffusion on the network following a particular set of transmission rules and then group together any nodes that end up in the same state.

Label Propagation [START_REF] Raghavan | Near Linear Time Algorithm to Detect Community Structures in Large-scale Networks[END_REF], simulates the diffusion of some information in the network to identify communities. Initially, each node carries a label denoting the community to which it belongs. Then, each node updates its community based on the labels of its neighbours. The rule used is to join the most frequent community in its neighbourhood (ties are broken randomly). As the labels propagate, densely connected groups of nodes reach a consensus on a unique label. This process goes on until each node has the majority label of its neighbours.

Even if we focus on only one algorithm of this class, it is worth mentioning influence-spreading propagation techniques. The idea is to take advantage of the influence propagation in order to identify a group of users -often called tribes -that behave homogeneously [START_REF] Chen | Efficient Influence Maximization in Social Networks[END_REF][START_REF] Goyal | Discovering Leaders from Community Actions[END_REF][START_REF] Khorasgani | Top Leaders Community Detection Approach in Information Networks[END_REF].

Bridge Detection

The bridge-detection approach relies on the idea that a community is made of dense components linked by a few bridges. Removing these bridges allows for uncovering the communities. The core issue is to define these bridges, which can be either nodes or links. The basic procedure is to compute a measure of either nodes' or links' contribution to keep the network connected and to remove the ones with the highest scores. We will present two methods. The first one is based on a global-link-centrality measure, while the second utilises a local-link-centrality definition.

The most popular algorithm in this category, Edge Betweeness, uses a link centrality measure. Proposed by Newman [START_REF] Girvan | Community Structure in Social and Biological Networks[END_REF], Edge Betweeness measures the centrality of a link by considering the proportion of shortest paths going through it. The main assumption here is that all of the shortest paths between different communities must go along the bridges leading to high scores for these links. The algorithm uses a divisive hierarchical approach. Starting with the initial network, the most central link is removed, and the link centrality is computed on the remaining network. When ties exist, one edge is to be chosen at random. Accordingly, this process is iterated until no links remain. The main drawback with this algorithm is that centrality must be computed at each step, making it unsuitable for large networks.

Radetal, [START_REF] Radicchi | Defining and Identifying Communities in Networks[END_REF]) uses an alternative centrality measure. This local measure is defined in analogy with the usual node-clustering coefficient, as the number of triangles to which a given edge belongs, divided by the number of triangles that might potentially include it. Note that, unlike betweenness centrality, this measure called link clustering takes high values for links inside a community and low ones for bridges. Indeed, clustering is higher in a community while links connecting nodes in different communities are included in few or no triangles. Radetal works exactly as Edge Betweeness with the difference that, at every step, the removed edges are those with the smallest edge clustering value.

Evaluation Criteria

Objective evaluation of the community-detection algorithms is a strategic issue. Indeed, we need to verify that the communities identified are actually the good ones. Moreover, it is necessary to compare results between two distinct algorithms to determine which is most effective. This complex and open problem is mainly considered from the evaluation-ofclustering-algorithms perspective. In such a setting, validation is simply accomplished by comparing discovered communities against known ones. Various clustering-comparison measures have been proposed that can be classified into three main categories: measures based on pair counting, setmatching-based measures and information-theoretic-based measures. Because of the overwhelming number of measures and their heterogeneity, choosing the most adapted is a difficult problem. The following section presents the standard evaluation measures emerging for the evaluation of community-detection methods. Note that all of the measures presented here can be derived from the confusion matrix whose elements are the number of nodes that are common to both partitions.

Pair-Counting-Based Measures

With pair-counting-based measures, clustering comparison is based on counting the pairs of points on which two partitions agree or disagree. Any pair of points can be classified under one of the following four categories. In the first two cases, the two partitions are in accordance: either the pair of points is in the same cluster in both partitions or it does not belong to the same cluster in both partitions. In the two remaining cases, the partitions disagree. It is when a pair of points belongs to different clusters in a partition but is in the same cluster in the other partition. The Rand Index [START_REF] Rand | Objective Criteria for the Evaluation of Clustering Methods[END_REF]) is a well-known measure in this class. It computes the proportion of agreement between the two partitions. Its value is 1 when the two partitions are identical and 0 when no pair of points appears either in the same cluster or in different clusters in both partitions. This extreme situation happens only when a partition consists of a single cluster. Meanwhile, the other consists only of clusters containing single points. As the expected value between two random partitions does not take a constant value, Hubert and Arabie [START_REF] Hubert | Comparing Partitions[END_REF] proposed a corrected for chance version of the Rand Index. The so called Adjusted Rand Index takes on the value 0 when the two partitions are picked at random. Negative values indicate a strong divergence between the partitions. The Jaccard Index is the ratio of the number of point pairs classified in the same cluster in both partitions, to the number of pairs classified in the same cluster by at least one partition. There is a corrected for chance version of this measure. It should be remembered that, there are many other measures in this class [START_REF] Albatineh | On Similarity Indices and Correction for Chance Agreement[END_REF]). However, after correction for chance, many of these measures are equivalent [START_REF] Warrens | On Similarity Coefficients for 2x2 Tables and Correction for Chance[END_REF].

Set-Matching-Based Measures

Set-matching-based measures are based on set cardinality. They intend to find the largest overlaps between pairs of different partition clusters. Purity is the proportion of correctly assigned nodes. Each identified cluster is matched to the one with the maximum overlap in the reference cluster, and then the accuracy of this assignment is measured by counting the number of correctly assigned nodes. When community structures are very dissimilar, the purity value is close to 0, while a perfect clustering has a purity of 1. High purity is easy to achieve when the number of clusters is large. In particular, purity is 1 if each node gets its own cluster. The classification error [START_REF] Meila | Comparing Clusterings -An Axiomatic View[END_REF]) and the Van Dongen metric are two alternative measures aimed at finding the best match for each cluster in both partitions. The main drawback of these measures is that they fail to take into account some clusters when their overlap with the other partitions is not enough large.

Information-Theoretic-Based Measures

Information-theoretic-based measures have gained increasing attention in the clustering literature. They are based on the mutual information shared by two partitions in order to assess their agreement. When two partitions are independent, they do not share any information. On the contrary, when they have the same distribution, the information shared is maximum. Knowing one of the partitions gives a perfect knowledge of the other one. This mutual information is a non-negative quantity upper bounded by the entropies of both partitions. We also have the variation of information that was introduced by [START_REF] Meila | Comparing Clusterings -An Axiomatic View[END_REF]. This metric is defined as the sum of the entropies of two partitions minus two times the mutual information. It measures the amount of information lost and gained in changing from one partition to the other. When the two partitions are identical, its value is 0, and its upper bound depends on the size of the network. Normalized mutual information (NMI) is defined as the ratio of the mutual information to the mean value of the entropy of both partitions. It takes the value of 1 when the two partitions are identical and 0 when they are independent.

Quality Functions

When there is no ground truth, the only way to evaluate a partition is to use a quality function. Existing quality functions formalise in different ways the idea that communities are sets of nodes densely connected and poorly connected to the rest of the network. In [START_REF] Yang | Defining and Evaluating Network Communities Based on Ground-truth[END_REF], eleven quality functions are reported. The authors show that these functions can be grouped into four classes: quality functions based on internal connectivity of the partition, quality functions based on external connectivity of the partition, quality functions based on internal and external connectivity, and quality functions based on a model. In the first group, we notice the internal density, which is the internal-link density of the node set. In the second group, the cut ratio is the fraction of existing edges out of all possible links leaving the communities. Conductance is a prominent measure of the third group. It measures a fraction of the volume of the total edges that points outside the cluster. The fourth group includes the modularity and its variants. Modularity is the most widely used quality function to compare the effectiveness of community-detection algorithms on real data when the underlying community structure is not known. This approach expresses how a community structure has a high-density ratio as compared to a random graph with the same degree sequence. The main weakness of the modularity approach is that it is also an optimization criterion used by a large number of algorithms; using it as a quality function introduces a bias in the comparisons. Furthermore, it has been reported that a community-detection method yielding strong modularity results is not always the best choice.

More recently, an alternative to modularity called surprise has been proposed [START_REF] Aldecoa | Surprise Maximization Reveals the Community Structure of Complex Networks[END_REF]. It assumes as a null model that links between nodes emerge randomly. It then evaluates the departure of the observed partition of the expected distribution of nodes and links into communities according to the null model. The higher the surprise value the more unlikely the partition is a realisation of a random graph.

Tests on Synthetic Networks

The evaluation of community-detection algorithms is a complex problem that has received very little attention in the related literature. We can distinguish two main trends for assessing the performance of community-detection methods based respectively on subjective or objective evaluations. Subjective evaluation relies on a panel of experts who decide whether or not the community structure revealed by the algorithm is valid. This decision depends on the relevance of results in the domain. In the subjective procedure, which is difficult to carry out on large networks, the results may vary depending on the expert and on the angle of interpretation adopted. On the other hand, objective evaluation is conducted using a set of benchmark graphs with a well known community structure and one or more evaluation measures chosen among the ones presented in the previous section. Both real-world and synthetic data can be used for this purpose. In some real-world networks, group membership for the nodes is explicitly defined. It is used to define ground-truth communities. A typical example, called the Zachary's Karate Club network, is widely used in the literature. This small graph is made of two groups that are easily recovered by any community-detection method. The Stanford Large Network Dataset Collection 1 is a solid attempt at establishing a standard real-world benchmark. It contains a set of social, information and collaboration networks with ground-truth communities. Networks in this benchmark cover a wide range of density, size and community structures. However, as of now, there has been no consensus in the scientific community on a standard real-world data set to explore the properties of community-detection algorithms. Most papers introducing a new method just use the simple classical benchmark graphs that can be visually interpreted in order to quantify the performance of their algorithm on real data. Things evolve more favourably regarding synthetic data. To date, the LFR benchmark is a de facto standard used for the large-scale evaluation of diverse community-detection methods. In what follows, we will focus on the objective assessment of artificial benchmarks. In this case the networks can be arbitrarily designed and controlled to highlight the strengths and weaknesses of community-detection algorithms in a broad range of situations. We will briefly review recent works on experimental evaluation, concentrating on the algorithms presented above, with two questions in mind: 1) Is there a community definition better suited than another according to performances? 2) How do the performances evolve according to the degree of the benchmarks' realism used in the evaluation?

Table 11-1 reports the results of an experimental evaluation of the algorithms presented in the previous section using the LFR model with 5,000 nodes. The exponent values of the power law of the degree distribution and of the community-size distribution are respectively γ≈3 and β=2. The average degree is <k> ≈30, and the maximum degree is kmax=90. Two different values of the mixing parameter μ {0.2, 0.6} are used. The first one corresponds to well separated communities, while the second one is not far from the limit where the networks have no community structure. For each parameter set, 25 networks are generated. The Rand Index, the Adjusted Rand Index and Normalized Mutual Information have been computed to assess the performance of the algorithms. For clarity, only the mean NMI values are reported. The result of this empirical evaluation illustrates the general behaviour of the algorithms well. It clearly shows that algorithms can be grouped into two categories: algorithms that are more or less efficient and ones that perform poorly. Along these lines, FastGreedy and Leading Eigenvector cannot identify the real community structure in any situation. The strength of the community structure clearly exerts a major influence on performances. As a matter of fact, performances generally decrease when the mixing parameter increases. Moreover, when the communities are well separated, all of the algorithms belonging to the first category easily uncover the community structure leading to high values of NMI. Differences are more pronounced when communities are more mixed. In this case, where communities are harder to detect, Markov Cluster and Radetal are not far from their limits. InfoMap outperforms all of the other algorithms under test. While WalkTrap and Label Propagation exhibit a good performance level, Spinglass and Louvain are one step behind. Note that the ranking deduced from the different measures of performance is quite comparable. Indeed, rank correlation values between any two performance measures are always higher than 0.95.

Algorithm

These results corroborate previous studies on the subject. In [START_REF] Lancichinetti | Community Detection Algorithms: a Comparative Analysis[END_REF], the authors conducted a comparative evaluation of twelve community-detection algorithms including Radetal, Louvain, FastGreedy, InfoMap and Markov Cluster. Performances have been computed using the NMI on two benchmark graphs with a known community structure (GN, LFR) and two random graphs (ER, CM) with no community structure. The results demonstrate that most methods perform rather well on the GN benchmark. But this is not the case when graphs are generated using the LFR. In particular, FastGreedy performs poorly. Its performances deteriorate rapidly when the network size increases and when community size decreases. Radetal and Markov Cluster are not very impressive either as their performances deteriorate with larger communities. As for the best algorithms, InfoMap ranks first followed by Louvain. When comparing these two, tests conducted on graphs with 100,000 nodes and community size ranging from 20 to 1000 have shown that InfoMap is not affected by these hard conditions, while it gets harder for Louvain to find the real communities. In addition, tests on random graphs are very informative. They should ideally lead to trivial solutions such as only one community or as many communities that there are nodes. Such is the case for Radetal, which always finds a single community with both benchmarks. InfoMap discovers no community on the ER benchmark but a few on the CM benchmark. On the contrary, Markov Cluster finds always as many communities as there are nodes. The remaining algorithms always find a few communities in these networks with no community structure. One of the major lessons of this work is that realistic benchmarks must be used for testing community-detection algorithms. In addition, the GN benchmark does not qualify to support the idea that new algorithms perform well as far as representing real-world networks adequately.

In (Orman, Labatut, and Cherifi 2011), eleven algorithms have been compared using the NMI. The LFR benchmark was tuned with parameters values typical of measurements on real-world networks. Results are in agreement with our previous observations concerning the ordering of the nine algorithms presented in table 11-1. Infomap outperforms the eleven algorithms under investigation. WalkTrap, Label Propagation, Spinglass and Louvain follow with satisfying performances, although not as good. Markov Cluster is very effective until the mixing proportion gets close to 0.4. Above this value, its performances decrease until a limit NMI value around 0.8. Radetal is very erratic and, FastGreedy and Leading Eigenvector are clearly outclassed. Besides the mixing coefficient, network size and average degree also affect the algorithms' performances but to a lesser extent. Performances worsen for Spinglass, Leading Eigenvector, Louvain, and Radetal when the network size increases, while the others are more insensitive to this parameter. To a certain extent, performances get better when the average degree increases. This may be due to an increase of the inter-community density that makes the community more visible. Undeniably, even if the intra-community links increase in the same proportion, the effect is distributed among many communities.

In [START_REF] Coscia | A Classification for Community Discovery Methods in Complex Networks[END_REF], thirteen algorithms have been compared using a graph extracted from the ego network of one of the authors' Facebook profiles. In this small graph (261 nodes and 1,772 edges), communities are well separated. The authors had a perfect knowledge of the network's community structure. Thusly, the comparison relies on quality measures such as the modularity and the reverse conductance. Seven out of eight of the non-overlapping communitydetection methods used in their evaluation are quite effective according to modularity. In fact, modularity ranges from 0.71 to 0.74. Label Propagation, WalkTrap, and Edge Betweeness tied for first, and were followed by InfoMap. Interestingly, WalkTrap favours a few bigger and denser communities, whereas InfoMap focuses on smaller and sparser ones. No solid conclusions can be drawn from this experiment. Of course, this network is not a very severe test and consequently not very discriminating for the algorithms. Moreover, testing the algorithms was not the primary goal of the authors in this work. They were more focused on classification according to the underlying community definition.

In (Orman, Labatut, and Cherifi 2012), the authors empirically tackle the relationship between performance measures and topological properties of the discovered community structure. The LFR benchmark is tuned in order to match the topological properties of three real-world networks (biological, Internet, communication). A comparative evaluation of eight algorithms is conducted using four performance measures (Purity, RI, ARI, NMI) and topological measures of the detected communities (embeddedness, community-size distribution, transitivity, scaled density, average distance, hub dominance). Table 11-2 summarizes some results for the algorithms previously evaluated. In extreme situations, the results are consistent. For example, InfoMap is still the best performing and FastGreedy is recognised as a substandard performer in both cases. Results are more mixed for the other algorithms. Thus, although the community structure identified by Louvain deviates significantly from the original, its NMI score is rather high. To summarise, there is no clear relation between these two types of evaluations that are rather complementary. In order to investigate the realism level of synthetic benchmarks' effect on the performance of community-detection algorithms, eleven algorithms have been tested using LFR-CM, LFR-BA and LFR-EV (Orman, Labatut, and Cherifi 2013). The major trend is that performances deteriorate when the degree of the networks' realism increases. The highest performances are in general obtained when applied to the LFR-CM benchmark, whereas the lowest correspond to LFR-BA data. It turns out that InfoMap is the least sensible algorithm to network characteristic variations followed by Spinglass and WalkTrap. Focusing on the various community-structure definitions, we will notice that three definition classes out of four have one of their members in the top four (Spinglass for internal density, InfoMap for closeness, and Label Propagation for diffusion). Radetal is one step behind the other categories. Unfortunately, as it is the only algorithm for the bridgedetection category, no serious conclusions can be drawn. Although it is somewhat risky to generalise from the study of a limited number of algorithms, it seems as if different definitions allow for the defining of equally efficient methods. To substantiate this intuition, it is necessary to conduct an extensive assessment on both synthetic and real-world data using a larger number of algorithms that must be selected among the top performers in each category.

Conclusion

Initially focused on either microscopic or macroscopic properties, research on complex networks has shifted to mesoscopic properties of networks. While a great deal of work has been devoted to the communitydetection issue, there are very few papers that analyse topological properties of the community structure in real-world networks. Strange as that might seem, most of the works are interested in discovering the community structure without really knowing what it may look like. Proposed solutions are usually based on a specific interpretation of an ill-defined concept of community. To demonstrate the effectiveness of their solution, small sized networks such as the Zachary Karate Club are used and (or) non-realistic synthetic benchmark graphs associated with traditional quality measures. This distorted view is aimed at pressing the point on the three complementary aspects of the community-detection issue: data, detection algorithms and objective evaluation. In order to ascertain a clear picture, progress must be made regarding these three directions.

Traditionally, in order to characterise real-world networks, research has been focused on macroscopic statistical properties to highlight their similarities. Empirical studies have demonstrated that numerous real-world networks share small-world and scale-free properties. It is now time to conduct a finer analysis of these networks to highlight their differences. Building a taxonomy of networks is one of the major steps in order to reach a consensus on ground-truth data to use for testing purposes. Furthermore, a taxonomy can have multiple benefits such as to shed light on networks' construction process. Mention may be made of two recent studies in this direction. In [START_REF] Nicosia | Characteristic Exponents of Complex Networks[END_REF], node properties' values such as the degree, the average degree of the nearest neighbours, and the clustering coefficient are used to build time series generated by random walks. Based on these time series, a set of characteristic exponents is used to classify networks. More interestingly, the approach used in [START_REF] Onnela | Taxonomies of Networks from Community Structure[END_REF]) is based on the community structure of the networks. The authors introduce three mesoscopic response functions representing the evolution of the community structure according to a resolution parameter. The minimum value of this parameter forces each node into its own community, while the maximum value corresponds to a single community. The effective energy function is linked to the modularity. The two others, respectively denoted as "effective entropy" and "effective number of communities", are correspondingly a normalised measure of the entropy and the number of communities at a given scale. Based on these signatures, they build a taxonomy for 746 networks. Besides classifying networks in different categories, their approach allows for classifying networks within individual categories. These works can be exploited to define a set of real-world networks in order to test the algorithms in specific situations. They may also allow us to identify better what realistic properties according to the different network categories are. This idea is in line with the development of models for generating synthetic graphs with controlled properties. Indeed, there is room for improvement on models in order to provide an adequate description of real graphs with community structure. For instance, models whose transitivity can be adjusted might make for a significant refinement over existing solutions. Furthermore, knowledge about the topological properties of community structures must be developed in order to define appropriate models that can generate realistic networks. It is essential to progress in this area as tests on artificial data with controlled properties are needed to characterize detection algorithms. Undoubtedly, with real-world data, there is no guarantee that communities defined on a subjective basis are encoded in the structural information of the network. To date, even if there is some divergence on the way to organising community-detection algorithm categories, the situation gets clearer. The main difficulty is linked to the overlap between the definitions of community, which undermine the necessary consensus. To overcome this drawback, there is a need for someone to produce an extensive study on the complex connections between the algorithms and the definitions. Moreover, investigating if one definition is more relevant than the others or if these multiple views of the same problem are complementary is also essential. Finally, although traditional performance measures are used extensively, it appears very clearly that they cannot distinguish community structures with different topological properties. It is therefore necessary to propose alternative measures more sensitive to the community-structure variations in order to conduct more effective comparisons. Throughout this chapter we deliberately did not address the complexity issue. However, the analyst must not ignore this crucial information in order to choose an effective algorithm and a fair comparison should involve algorithms from the same class of complexity.

Fig

  Fig.11-1. Variation of macroscopic topological properties with the mixing coefficient μ. Red squares represent LFR-BA, green triangles LFR-EV, and blue crosses LFR-CM. The vertical lines represent the average mixing limit above which communities stop being clearly defined. Networks parameters are n = 5000, <k>= 30, γ ≈ 3, β=2.

  Figure 11-2 represents the best performing algorithms for each class of community definition. It shows that performances of Spinglass and InfoMap are insensitive to benchmark variations in a broad range of the mixing-proportion value. Differences appear when community discovery becomes a challenging task. On the contrary, Radetal and Label Propagation are affected almost in the whole range of mixing-proportion variation. The key lesson learned from this study is that even a slight variation of the network model can have important consequences on performances. It is therefore important to develop more realistic network models in order to have a clear view of the algorithms' efficiency. a) Internal Density (Spinglass)

Fig. 11

 11 Fig.11-2. Performances of the community-detection algorithms on the three benchmarks. Crosses are used for LFR-CM, dots for LFR-BA and triangles for LFR-EV. Each data point corresponds to an average over 25 generated networks with parameters values n = 5000, <k> = 30, γ ≈ 3, β=2. The vertical lines at μ = 0.86 represent the average mixing limit above which communities stop being clearly defined.

Table 11 -

 11 2. Qualitative comparison of the discovered communities' characteristics with the real community structure. The properties are average distance (d), embeddedness (Emb.), community-size distribution (Dis. Size), hub dominance (Hub Dom.), transitivity (Clust.), and scaled density (Sc. Dens.). When both properties are akin, Ok is reported.

http://snap.stanford.edu/data/


Giovanni Chierchia

Davide Cozzolino

Giovanni Poggi

Carlo Sansone

Luisa Verdoliva

GUIDED FILTERING FOR PRNU-BASED LOCALIZATION OF SMALL-SIZE IMAGE FORGERIES

Keywords: Digital forensics, forgery detection, photo response non-uniformity, guided filters

PRNU-based techniques guarantee a good forgery detection performance irrespective of the specific type of forgery. The presence or absence of the camera PRNU pattern is detected by a correlation test. Given the very low power of the PRNU signal, however, the correlation must be averaged over a pretty large window, reducing the algorithm's ability to reveal small forgeries. To improve resolution, we estimate correlation with a spatially adaptive filtering technique, with weights computed over a suitable pilot image. Implementation efficiency is achieved by resorting to the recently proposed guided filters. Experiments prove that the proposed filtering strategy allows for a much better detection performance in the case of small forgeries.

INTRODUCTION

Image forgery detection and localization is a very challenging task due to the large variety of manipulations a malicious user can perform by means of more and more sophisticated image editing tools [START_REF]Photo tampering throughout history[END_REF]. In recent years, research has focused especially on passive techniques which retrieve traces of manipulations from the sole analysis of the image content. The image acquisition phase, in particular, is a valuable source of information as it often leaves peculiar traces, related to characteristics of the lens [START_REF] Yerushalmy | Digital Image Forgery Detection Based on Lens and Sensor Aberration[END_REF][START_REF] Fu | Forgery Authentication in Extreme Wide-Angle Lens Using Distortion Cue and Fake Saliency Map[END_REF], the color filter array (CFA) pattern [START_REF] Popescu | Exposing digital forgeries in color filter array interpolated images[END_REF][START_REF] Kot | Accurate Detection of Demosaicing Regularity for Digital Image Forensics[END_REF], or the sensor array [START_REF] Lukas | Detecting digital image forgeries using sensor pattern noise[END_REF][START_REF] Chen | Determining Image Origin and Integrity Using Sensor Noise[END_REF]. Indeed, one of the most promising approaches to date relies on the photo response non-uniformity (PRNU) noise. The PRNU arises from tiny imperfections in the silicon wafer used to manufacture the imaging sensor [START_REF] Healey | Radiometric CCD camera calibration and noise estimation[END_REF]. These physical differences generate a unique sensor pattern, specific of each individual camera, constant in time, independent of the scene, and fairly robust to several forms of image processing. Therefore, this pattern can be considered as a sort of camera fingerprint and used as such to accomplish forgery detection or image identification tasks. Different types of tampering, like copy-move, splicing, retouching, all remove the original PRNU from the target area, enabling the detection of the forgery irrespective of the type of attack.

An intense research activity began as soon as the potential of this approach was recognized. In the first PRNU-based technique, proposed in [START_REF] Lukas | Detecting digital image forgeries using sensor pattern noise[END_REF] in 2006, blocks extracted from the estimated PRNU of the target image are compared with homologous blocks of the camera PRNU (estimated in advance from a set of sample images) and a tampering is declared whenever the normalized correlation falls below a given threshold. However, since the PRNU is a very weak signal, estimated by means of imperfect tools, its traces can be easily overwhelmed by noise in some regions of the image characterized by saturation or strong textures, leading to false alarms. Therefore, the authors of [START_REF] Lukas | Detecting digital image forgeries using sensor pattern noise[END_REF] proposed themselves a new version in [START_REF] Chen | Determining Image Origin and Integrity Using Sensor Noise[END_REF] to reduce the false alarms by identifying the potentially troublesome regions (through a predictor) and declaring them as genuine irrespective of the observed correlation index. Similar considerations guide the algorithm proposed in [START_REF] Liu | Source camera identification from significant noise residual regions[END_REF], where only regions with high signal quality are used, discarding those heavily deteriorated by irrelevant noise. In [START_REF] Li | Source Camera Identification Using Enhanced Sensor Pattern Noise[END_REF] a strategy to reduce the interference of scene details on the PRNU is proposed, while in [START_REF] Li | Color-Decoupled Photo Response Non-Uniformity for Digital Image Forensics[END_REF][START_REF] Fridrich | Sensor Defects in Digital Image Forensic[END_REF][START_REF] Goljan | Sensor-fingerprint based identification of images corrected for lens distortion[END_REF][START_REF] Gloe | Unexpected Artefacts in PRNU-Based Camera Identification: A 'Dresden Image Database' Case-Study[END_REF] the suppression of nonunique artifacts is considered. In [START_REF] Zhang | Exposing Digital Image Forgeries by Using Canonical Correlation Analysis[END_REF], canonical correlation analysis is used to increase the reliability of the decision variables. We ourselves proposed several improvements to the basic algorithm of [START_REF] Lukas | Detecting digital image forgeries using sensor pattern noise[END_REF][START_REF] Chen | Determining Image Origin and Integrity Using Sensor Noise[END_REF] concerning a better method for PRNU estimation based on nonlocal filtering [START_REF] Chierchia | On the influence of denoising in PRNU based forgery detection[END_REF], the adoption of a variable-size analysis window to improve resolution [START_REF] Chierchia | PRNU-based detection of small-size image forgeries[END_REF] and, more recently, the reformulation of PRNU-based forgery detection as a Bayesian estimation problem [START_REF] Chierchia | PRNUbased forgery detection with regularity constraints and global optimization[END_REF][START_REF] Chierchia | A Bayesian-MRF Approach for PRNU-based Image Forgery Detection[END_REF].

This work, following the path initiated in [START_REF] Chierchia | PRNU-based detection of small-size image forgeries[END_REF], aims at improving the resolution of PRNU-based algorithms. In fact, since the PRNU pattern is a very weak signal, it can be reliably detected only by jointly processing a large number of image samples, through a sliding-window analysis. The size of the sliding-window dictates therefore the effective resolution of the algorithm, causing forgeries smaller than the analysis window to remain often undetected. In [START_REF] Chierchia | PRNU-based detection of small-size image forgeries[END_REF] we resorted to a preliminary image segmentation to adapt the analysis window to the shape of candidate forgeries. Segmentation, however, is itself a source of errors, and the experimental analysis proved the heavy impact of such errors on performance. Here, we replace hard segmentation with a more flexible soft-segmentation strategy, using adaptive weights in the analysis window, computed on the basis of image content. A fast and effective implementation of this concept is obtained by resorting to guided filters [START_REF] He | Guided Image Filtering[END_REF]. Experiments prove the proposed algorithm to provide much better results on critical small-size forgeries, with a negligible increase in complexity. In the following, Section II provides the necessary background material, Section III describes the proposed algorithm and Section IV analyzes its performance by numerical experiments.

BACKGROUND

Let y ∈ R N be a digital image observed at the camera output, where yi indicates the value at site i, either as a single color band or the composition of multiple color bands. Let us assume, in a simplified model [START_REF] Chen | Determining Image Origin and Integrity Using Sensor Noise[END_REF][START_REF] Healey | Radiometric CCD camera calibration and noise estimation[END_REF], that y can be written as

yi = (1 + ki)xi + θi = xiki + xi + θi (1)
where x is the ideal noise-free image, k the camera PRNU, and θ an additive noise term which accounts for all types of disturbances.

The PRNU k is by now our signal of interest, very weak w.r.t. both additive noise θ and ideal image x. To increase the signal-to-noise ratio, we subtract from (1) an estimate of the ideal image, x = f (y), obtained by means of a denoising algorithm, obtaining the so-called noise residual

ri = yi -xi = yiki + (xi -yi)ki + (xi -xi) + θi = yiki + ni (2)
where, for convenience, k multiplies the observed image y rather than the unknown original x. and all disturbances have been collected in a single noise term n.

When a section of the image is tampered with, for example by replacing it with material drawn from other regions, the PRNU term is cancelled. Therefore, to decide about a possible forgery, PRNUbased techniques try to discover whether the PRNU term is present or not. In the following we briefly describe the technique proposed by Chen et al. [START_REF] Chen | Determining Image Origin and Integrity Using Sensor Noise[END_REF], based on sliding-window analysis, referring the reader to the original paper for more detail.

As a preliminary step, the true camera PRNU pattern, k, must be reliably estimated, which requires that either the target camera, or a large enough number of photos taken by it, are available. Note that such an hypothesis is not always satisfied in practice, representing the main limitation of this approach. Given k, the detection is formulated as a binary test between hypothesis H0 that the camera PRNU is absent (i.e. the pixel has been tampered with) and hypothesis H1 that the PRNU is present (i.e. the pixel is genuine):

H0 : ri = ni H1 : ri = zi + ni (3)
with zi = yiki. The decision is based on the normalized correlation between r W i and z W i , namely, the restrictions of r and z, respectively, to a window Wi centered on the target pixel:

ρi = corr(r W i , z W i ) = (r W i -r W i ) (z W i -z W i ) r W i -r W i • z W i -z W i (4)
where denotes inner product, and x indicates mean of x. The algorithm then compares the correlation with a threshold γ1 ui = 0 ρi < γ1 1 otherwise [START_REF] Kot | Accurate Detection of Demosaicing Regularity for Digital Image Forensics[END_REF] where ui ∈ {0, 1} is the algorithm output, 0 for forgery and 1 for genuine pixel. The threshold is selected according to the Neyman-Pearson criterion so as to guarantee a suitably small false acceptance rate (FAR) Pr( ui = 1 | ui = 0), with ui ∈ {0, 1} the true pixel class. Once fixed the FAR, however, there is no guarantee that the other type of error, the false rejection rate (FRR), remain reasonably small. In fact, under hypothesis H1, the decision statistic is influenced by the image content. Even in the absence of forgery, the correlation might happen to be very low when the image is dark, saturated, or heavily textured. In [START_REF] Chen | Determining Image Origin and Integrity Using Sensor Noise[END_REF] this problem is addresses by means of a predictor which, based on local images features, computes the expected value ρi of the correlation index under hypothesis H1. When ρi is too low, indicating that no reliable decision can be made, the pixel is always labeled as genuine, the less risky decision, irrespective of the value of ρi. Therefore, the test becomes ui = 0 ρi < γ1 AND ρi > γ2 1 otherwise [START_REF] Lukas | Detecting digital image forgeries using sensor pattern noise[END_REF] with γ2 chosen heuristically by the user. Better strategies are considered in [START_REF] Chierchia | PRNUbased forgery detection with regularity constraints and global optimization[END_REF] and [START_REF] Chierchia | A Bayesian-MRF Approach for PRNU-based Image Forgery Detection[END_REF] where decisions are made jointly on all pixels based on a Bayesian/MRF modeling.

Although the above description remains necessarily at a conceptual level, it is worth going into some more detail for what concerns the decision statistic of equation ( 4). Given the low, and spatially varying, signal-to-noise ratio characterizing this problem, the two conditional pdf's p ρ|H 0 (•) and p ρ|H 1 (•) can overlap significantly, causing large probabilities of error. To obtain a reasonable separation between them, one is forced to compute the correlation over a large window, for example, 128×128 pixels, as done in [START_REF] Chen | Determining Image Origin and Integrity Using Sensor Noise[END_REF]. By so doing, however, one is implicitly renouncing to detect forgeries much smaller than the window size (or just much thinner). In these cases, in fact, the analysis window comprises pixels of both types, forged and genuine, providing a highly unreliable decision statistic. In the original algorithm, in fact, detected forged regions smaller than 64 × 64 pixels (one fourth of the window size) are canceled right away, as they are more easily generated by random errors than by actual forgeries. Low resolution is therefore a major problem of this algorithm.

PROPOSED METHOD

To gain a better insight into our estimation problem let us elaborate some more on equation ( 4) introducing some simplifications. First of all, we neglect the means (which are typically negligible) and, considering that the terms at the denominator serve only to normalize the correlation, focus on the scalar product on the numerator. Remember that z = yk is the camera PRNU multiplied point-wise by the input image and, likewise, r = hy + n is the noise residual, with h the observed PRNU which might or might not coincide with k. Therefore, if we divide all terms point-wise by y, we obtain eventually the quantity

τi = 1 |Wi| j∈W i rj yj zj yj = 1 |Wi| j∈W i (hj + nj yj )kj (7)
By defining a new noise field η = nk/y, and introducing generic weights ωij, eq.( 7) becomes

τi = j∈W i ωij(hjkj + ηj) (8)
which can be interpreted as the linear filtering of the image hk affected by the additive noise η. In [START_REF] Chen | Determining Image Origin and Integrity Using Sensor Noise[END_REF] the weights are all equals to one 1/|Wi|, hence, a simple boxcar filtering is carried out. Assuming that the whole analysis window is homogeneous, either genuine (h = k) or forged (h = k) and, for the sake of simplicity, that y is constant over the window, so that E[ηi] = σ 2 η , we can characterize the random variable τ

E[τ ] = k 2 i h = k 0 h = k (9) VAR[τ ] = σ 2 η j ω 2 ij ( 10
)
where k 2 is the power of the camera PRNU estimated over Wi. In this condition, using uniform weights ωij = 1/|Wi| is indeed optimal, as it minimizes the variance of the estimate, and maximizes the probability of deciding correctly. However, if some of the predictor pixels are not homogeneous with the target, that is, forged instead of genuine or viceversa, the estimate will suffer a systematic bias, namely, the means will not be 0 or k 2 anymore, but some intermediate values, heavily affecting the decision performance. In this case, the uniform weights are no more optimal, in general, and one should instead reduce the influence of heterogeneous pixels by associating a small or even null weight with them. This is exactly the problem of small-size forgeries. By using a large analysis window with fixed weights we happen to include pixels of different nature, and the decision variable becomes strongly biased and basically useless, even in favourable (bright, smooth, unsaturated) areas of the image. If we could find and include in the estimation only predictors homogeneous with the target, all biases would disappear, at the cost of an increased estimation variance.

The bias / variance trade-off is indeed well-known in the denoising literature. This problem has received a great deal of attention, recently, in the context of nonlocal filtering, the current state of the art in denoising [START_REF] Buades | A Review of image denoising algorithms, with a new one[END_REF][START_REF] Dabov | Image denoising by sparse 3-D transform-domain collaborative filtering[END_REF], where predictor pixels are weighted based on their expected similarity with the target. The similarity, in its turn, is typically computed by comparing patches of pixels centered on the target and the predictor pixels respectively. This approach cannot work with our noise-like input image, rz, as it lacks the structures necessary to compute a meaningful similarity measure. However, we can take advantage of the original observed image y, using it as a "pilot" (again a well-known concept in denoising) to compute similarities, and applying the resulting weights in the actual filtering of the rz field.

Interestingly, this conceptual path has lead to an approach pretty similar to that followed in [START_REF] Chierchia | PRNU-based detection of small-size image forgeries[END_REF]. In both cases we use the original image to drive the filtering process emphasizing predictors that are likely to belong to the same object as the target. This happens through a preliminary segmentation in [START_REF] Chierchia | PRNU-based detection of small-size image forgeries[END_REF], by means of a more flexible adaptive filtering, here. It is worth underlining that our changes will concern only the correlation computation, while the decision process remains the same as in [START_REF] Chen | Determining Image Origin and Integrity Using Sensor Noise[END_REF].

Implementation by guided filtering

Adaptive space-variant filters are typically characterized by high computational complexity and this is certainly the case with nonlocal filtering, where intensive patch-based processing is required. Considering, in addition, that the weak PRNU signal calls for large filtering windows, conventional nonlocal filters [START_REF] Buades | A Review of image denoising algorithms, with a new one[END_REF][START_REF] Dabov | Image denoising by sparse 3-D transform-domain collaborative filtering[END_REF] become unacceptably complex for this application. We resort therefore to guided filters, a recently proposed technique, which implements nonlocal filtering by leveraging heavily on the use of a pilot image associated with the target image.

Here, we follow closely the development and notation used in [START_REF] He | Guided Image Filtering[END_REF], referring the reader to the original paper for a more detailed treatment. Let p be the image to be filtered, q the filter output, and I a pilot image assumed to bear valuable information on p. We consider linear filtering, in the form

qi = j ωijpj (11)
Then, we assume that, locally to each pixel i, q depends linearly on

I, that is qj = aiIj + bi, ∀j ∈ Ωi ( 12
)
where Ωi is a square window of radius r centered on i. The parameters ai and bi are chosen to minimize over Ωi the squared error between observed image and model

(ai, bi) = arg min (a,b) j∈Ω i [(aiIj + bi -pj) 2 + εa 2 i ] (13)
with ε a regularizing parameter that penalizes large values of a. The optimal values are ai = 1 |Ωi| where xi indicated average of x over Ωi and σ 2 i is the variance of I over Ωi. By substituting the optimal values back into [START_REF] Fridrich | Sensor Defects in Digital Image Forensic[END_REF] we obtain an estimate of qj for all output pixels in the window Ωi. Each of these pixels, however, falls in several such windows, and hence, to obtain the final filtered value, we average all such estimates

j∈Ω i Ij pj -Īi pi σ 2 i + ε (14
qj = 1 |Ωj| i∈Ω j (aiIj + bi) = ā Ij + b (16)
which is the final expression of the linear filtering process of p guided by the pilot image I under the local linear model [START_REF] Fridrich | Sensor Defects in Digital Image Forensic[END_REF]. The main reason for reporting all intermediate expression is to point out that all computations amount to a few boxcar filtering, applied to p, I, I 2 , a, and b, carried out by integral image techniques with negligible complexity. For our algorithm, of course, the input image is the product rz, the output is the decision statistic ρ, while the pilot (scalar) image can be a combination of the color bands of the original image y, its denoised version x, or any suitable field of features extracted from these images. By tuning the two parameters of the filter, the window radius r and the regularizing parameter , the influence of the pilot image in the filtering process can be modulated at will.

EXPERIMENTAL RESULTS

To prove the potential of the proposed approach we begin by showing, in Fig. 1, a few sample images and the corresponding correlation fields. The image on the first row presents a large forgery, easily detectable in both the correlation fields (last two columns) as the region is much darker than in the predicted field (middle column). On the second and third row, instead, we have quite small forgeries, which leave little or no trace in the field computed by boxcar filtering, while are clearly detectable in the field obtained by guided filtering. Although these last examples are very favourable for the guided filtering approach, due to the high contrast between forgeries and background, they make clear that the original image can help making a better decision.

More convincing results are presented in Fig. 2, showing the receiver operating curves (ROC) obtained using the original algorithm [START_REF] Chen | Determining Image Origin and Integrity Using Sensor Noise[END_REF] and three implementations of the proposed method using different pilots (grayscale image, image in RGB, and some features extracted from the image). We use a test set of 200 768×1024-pixel images with a square forgery at the center, drawn at random from a different image. The camera (a Canon EOS-450D) PRNU is estimated off-line on a separate training set, used also to design the predictor. Each ROC is the upper envelope of pixel-level (PD, PF A) points obtained as the algorithm parameters vary. For guided filtering we used r = 32 and ε = 0.16, while the usual 128×128 window (r = 64) is used for boxcar filtering, and in all cases, to allow a fair comparison, the minimum size of acceptable detected forgeries was lowered to 32×32 pixels. Comparison is carried out separately for very-small, small, medium and large forgeries. With forgeries of dimension 48×48 pixels and 64×64 pixels (first two graphs), guided filtering guarantees a large performance improvement over boxcar filtering, synthesized by the area under curve (AUC) figure which grows from 0.63 to 0.78 in the first case and from 0.71 to over 0.85 in the second. With medium-size forgeries, 96×96 pixels, the performance gain is much more limited, with the AUC growing from 0.85 to 0.90, and becomes almost negligible, as expected, with larger 128×128 forgeries. No significant difference is observed, instead, as the pilot image changes, with the RGB pilot only slightly preferable to the others.

Fig. 1 .

 1 Fig. 1. Sample results. From left to right, original and forged image, correlation field predicted, and computed by boxcar and guided filtering.

Fig. 2 .

 2 Fig.2. ROCs obtained with boxcar and guided filtering with forgeries of size: 48×48, 64×64, 96×96, and 128×128 pixels.