Anne-Marie Mme

Mr Matthieu Kermarrec

Latapy

Mr Christophe Prieur

M Bertrand

Mr Pablo Jensen D'

Guillaume Chelius

Andreea Chis

Christophe Crespelle

Adrien Friggeri

Lucie Martinet

Sèverine Morin

Keywords: community detection, overlapping community structure, complex networks, dynamic networks, community evolution, network science Je remercie, en premier lieu, mes rapporteurs, Bifurcation Chaos Theory Quantum Chaos Universality, Quantum Chaos, Systems, And Universality Chaos, States, Model, Random-Matrix Theory, Complex Systems, Fluctuations, Spectra Chaos In Chaos, Stability, Dynamics, Population, Population Permanence, Models, Systems, Dynamics Bifurcation, Predator-Prey System, Birth Pulses Neuroplasticity Rat, Neurons, Plasticity, Hippocampus, Brain, Central-Nervous-System, Synaptic Plasticity, Long-Term Potentiation, Food-Intake, Memory Neuroscience: Long-Term Long-Term Potentiation, Biological Potentiation Synaptic Plasticity, Plasticity, Psychology Hippocampus, Nmda Receptor, Glutamate Receptors, Expression, Neurons, In-Vivo, Hippocampal-Neurons Genetic Association Association, Susceptibility, Polymorphism, Linkage Disequilibrium, Disease, Major Histocompatibility Complex, Linkage, Complex Traits, Risk, Population Pre-Botzinger Pre-Botzinger Complex, In-Vitro, Complex Prebotzinger Complex, Brain-Stem, Respiratory Rhythm Generation, Rhythm Generation, Rat, Control Of Breathing, Neurons, Pacemaker Neurons Prefrontal Cortex Performance, Attention, Fmri, Children, Prefrontal Cortex, Brain, Working-Memory, Cortex, Memory, Activation Diabetes Mellitus Mellitus, Glycemic Control, Complications, Hypertension, Randomized Controlled-Trial, Diabetes, Therapy, Risk, Diabetes Mellitus, Management Crystal Structure Complexes, Self-Organization, Crystal-Structure, Derivatives, Chemistry, Polymers, Behavior, Films, Nonlinear-Optical Properties, Phase-Transition Chemistry: Anodic Alumina Fabrication, Arrays, Films, Anodic Spectroscopy Alumina, Anodization, Self-Organization, Growth, Self-Organized Formation, Hexagonal Pore Arrays, Titanium Soc Soc Self-Organized Criticality, Model, Dynamics, Econophysics, Evolution, Systems, Fluctuations, Models, Behavior, Turbulence Innovation Management, Innovation, Economics, Management Performance, Model, Complexity, Systems, Technology, Firm, Knowledge Ecosystems Discrete-Event Systems, Supervisory Control, Systems Petri Nets, Complexity, Discrete-Event Systems, Verification, Design, Automata, Discrete Event Systems, Synchronization Computational Complexity, Algorithms, Complexity Computational Complexity, Algorithm, Networks, Optimization, Time, Systems

In complex networks, the notion of community structure refers to the presence of groups of nodes in a network. These groups are more densely connected internally than with the rest of the network. The presence of communities inside a network gives an insight on network structural properties. For example, in social networks, communities are based on common interests, location, hobbies.... Generally, a community structure is described by a partition of the network nodes, where each node belongs to a unique community. A more reasonable description seems to be overlapping community structure, where nodes are allowed to be shared by several communities. Moreover, when considering dynamic networks whose interactions between nodes evolve in time, it appears crucial to consider also the evolution of the intrinsic community structure.

This thesis focus on mining dynamic community evolution and overlapping community detection. We have proposed two distinct methods for overlapping community detection. The first one named clique optimization and the second one called fuzzy detection. Our clique optimization aims to identify granular overlaps and it is a fine grain scale approach. Our fuzzy detection is at a coarser grain scale with the strategy of identifying modular overlaps. Their applications in synthetic and real networks indicate that both methods can be used for characterizing overlapping nodes but in distinct and complementary views. We also propose the definition of predecessor and successor in mining community evolution. Such definition describes the relationship between communities at different time steps. We use it to detect community evolution in dynamic networks and show how modular overlaps evolve over time. A visualization tool called lineage diagrams is used to show community evolution by connecting communities in relationship of predecessor and successor. Several cases are studied.

Résumé

Dans le contexte des réseaux complexes, la structure communautaire du réseau devient un sujet important pour plusieurs domaines de recherche. Les communautés sont en général vues comme des groupes intérieurement denses. La détection de tels groupes offre un éclairage intéressant sur la structure du réseau. Par exemple, une communauté de pages web regroupe des pages traitant du même sujet. La définition de communautés est en général limitée à une partition de l'ensemble des noeuds. Cela exclut par définition qu'un noeud puisse appartenir à plusieurs communautés, ce qui pourtant est naturel dans de nombreux (cas des réseaux sociaux par exemple). Une autre question importante et sans réponse est l'étude des réseaux et de leur structure communautaire en tenant compte de leur dynamique. Cette thèse porte sur l'étude de réseaux dynamiques et la détection de communautés recouvrantes.

Nous proposons deux méthodes différentes pour la détection de communautés recouvrantes. La première méthode est appelée optimisation de clique. L'optimisation de clique vise à détecter les noeuds recouvrants granulaires. La méthode de l'optimisation de clique est une approche à grain fin. La seconde méthode est nommée détection floue (fuzzy detection). Cette méthode est à grain plus grossier et vise à identifier les groupes recouvrants. Nous appliquons ces deux méthodes à des réseaux synthétiques et réels. Les résultats obtenus indiquent que les deux méthodes peuvent être utilisées pour caractériser les noeuds recouvrants. Les deux approches apportent des points de vue distincts et complémentaires. Dans le cas des graphes dynamiques, nous donnons une définition sur la relation entre les communautés à deux pas de temps consécutif. Cette technique permet de représenter le changement de la structure en fonction du temps. Pour mettre en évidence cette relation, nous proposons des diagrammes de lignage pour la visualisation de la dynamique des communautés. Ces diagrammes qui connectent des communautés à des pas de temps successifs montrent l'évolution de la structure et l'évolution des groupes recouvrantes. Nous avons également appliquer ces outils à des cas concrets.

Mots clés: structure communautaire, communautés recouvrantes, réseaux de terrain dynamiques, évolution de communautés, réseaux complexes

Introduction Modular organization of complex networks

Complex networks are obtained by modeling real systems with graphs. This paradigm is used to represent a wide variety of systems in different areas, such as the Internet [START_REF] Gabrilovich | Computing semantic relatedness using wikipedia-based explicit semantic analysis[END_REF], World Wide Web, citation networks [START_REF] Giles | Citeseer: An automatic citation indexing system[END_REF], coauthorship networks [START_REF] Jin | Structure of growing social networks[END_REF], metabolic networks [START_REF] Hartwell | From molecular to modular cell biology[END_REF]. Each citizen, as an individual, can construct a social network whose nodes are connected by one or more specific types of relations, like friendship, kinship, common interest [START_REF] Backstrom | Group formation in large social networks: membership, growth, and evolution[END_REF][START_REF] Bekkerman | Automatic categorization of email into folders: Benchmark experiments on enron and sri corpora[END_REF].

Studies in complex networks become a popular interest of research area. It was triggered by two seminal papers: Watts and Strogatz on small-world networks [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF] and Barabasi and Albert on scale-free networks [START_REF] Barabasi | Scale-free networks[END_REF]. These studies have introduced common non-trivial properties, which do not occur in simple networks such as lattices or random graphs. It induced a large development of work on the studies of properties of real networks.

The massive and comparative analysis of networks from several fields has produced a series of unexpected and impressive results. One important issue is community structure. Empirical studies on different networks such as World Wide Web, protein interaction networks, email networks, etc. find their degree distributions different from each other. Studies also find that the distribution of node degrees is not only globally, but also locally heterogeneous. In another words, networks can be characterized by communities, with dense connections within them and sparse connections between them.

The community structure of a real network is not only the result of the topology, but also refers to system functions: in protein-protein interaction networks, communities correspond to specific functions [START_REF] Chen | Detecting functional modules in the yeast protein-protein interaction network[END_REF]; in the World Wide Web, they may relate to topics [START_REF] Dourisboure | Extraction and classification of dense communities in the web[END_REF]; in food webs they correspond to compartments [START_REF] Krause | Compartments revealed in food-web structure[END_REF], etc. Studies in community structure should lead to a better understanding of complex systems.

Community detection

In order to detect community structures, diverse techniques are proposed and are applied to real networks. As early as 1955, Weiss and Jacobson [START_REF] Robert | A method for the analysis of the structure of complex organizations[END_REF] carried out the first analysis of community structure, which was at the basis of graph partitioning. Graph partitioning divides nodes into predefined communities, such that the number of edges lying between the groups is minimal. In a seminal paper appeared in 2001, Girvan and Newman [START_REF] Girvan | Community structure in social and biological networks[END_REF] proposed a new algorithm, which identified edges lying between communities for successive removal until the isolation of communities. This paper triggered a big activity in the field, and many new modern methods have been proposed. For example, modularity optimization is the most popular method for community detection on large graphs [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF][START_REF] Newman | Fast algorithm for detecting community structure in networks[END_REF][START_REF] Wakita | Finding community structure in mega-scale social networks[END_REF], dynamic algorithms are based on physical techniques: spin models [START_REF] Son | Random field ising model and community structure in complex networks[END_REF], random walks [START_REF] Pons | Computing communities in large networks using random walks[END_REF] and synchronization [START_REF] Arenas | Synchronization reveals topological scales in complex networks[END_REF], and others like methods based on statistical inference: Bayesian inference [START_REF] Yang | A bayesian approach toward finding communities and their evolutions in dynamic social networks[END_REF], blockmodeling [START_REF] Batagelj | Generalized blockmodeling of two-mode network data[END_REF], model selection [START_REF] Burnham | Model selection and multimodel inference: a practical information-theoretic approach[END_REF] and information theory.

These methods provide good performance in community detection, and have been applied to real networks for analysis. Is the subject of community detection deserving another report? At least two reasons have deeply motivated our work.

The first is that current complex networks become more complex, with the main focus moving from the analysis of small static networks to that of systems with thousands or millions of nodes, and with a renewed attention to the properties of networks of dynamical units. For instance, the network of communications of millions of users is changing its interactions across time. The structure of a real network is the result of the continuous evolution of interactions which correspond to system functions. So that the research on communities in dynamic networks would lead to a better knowledge of system evolutionary mechanisms, and to a better cottoning on dynamical and functional behaviours. Most of community detection methods are proposed for static networks. There is a crucial need for algorithms that detect communities in dynamic networks.

The second is that overlapping community structure is still a problem. Most of community detection methods are proposed to detect disjoint communities without overlapping nodes. Overlapping nodes are shared by several communities in overlapping community structure. They are interesting to investigate since they play a key role as intermediate between communities, with a special effect in predicting dynamic behaviors of individuals in networks. Studies [START_REF] Vedres | Structural folds: Generative disruption in overlapping groups[END_REF] in histories of personnel ties among the largest enterprises in Hungary showed that overlapping nodes were possible mixing or recombining memberships of groups. The membership of a long duration community changed year by year. Some communities were built up through splitting and reuniting in an ongoing pattern. This phenomenon, indeed, represents a crucial feature of overlapping nodes in understanding structural organization of complex systems. Studying overlapping community structure of networks will be helpful to understand system dynamic mechanisms and predict future trends.

We explore this thesis to deal with the analysis of overlapping community structure in different networks and their dynamics. For this, methods for overlapping community structure are proposed as well as approaches to track the evolution of these structures over time. To verify their applicability, the presented methods are applied to different real work data sets and the obtained results are evaluated.

Main contributions

The main contributions of this thesis are briefly summarized in the following.

• Two different views on overlapping node detection: In order to detect overlapping community structure and characterize overlapping nodes, we have proposed two definitions of overlapping nodes: granular overlaps and modular overlaps. Granular overlaps are a set of nodes, each of which connects several communities with high cohesion. Modular overlaps are a set of groups, each of which is a group of nodes having high community membership degree (how strong the group of nodes belongs to the community) with at least two communities.

For the detection of granular overlaps, we have proposed clique optimization, which detects cliques k-adjacent to communities (A clique which does not belong to the community but shares at least k -1 common nodes). A granular overlapping node in a weak sense is the member of one clique, which is adjacent to other communities different from its community membership in the partition. A granular overlapping node in a strong sense is the member of one clique, which is adjacent to at least two communities simultaneously.

By running the Louvain algorithm several times, we can compute the probability that pair of nodes appear in the same community. It allows us to detect robust clusters, which have high stability against random impacts as every pair of connected nodes has a high co-appearance probability. Furthermore, we are able to detect community cores and modular overlaps. The community core is the maximum robust cluster within one community. The modular overlaps is one robust cluster has the high co-appearance probability with several communities.

The applications of both methods to benchmark graphs have a high agreement with the known community structure. We also apply them to a real network. In the experiments, we observe that both methods provide meaningful but different results in characterizing overlapping nodes.

• Tracking community evolution and identifying community dynamics: In order to track community evolution and identify community dynamics, we have proposed a two-stage method: we firstly apply our fuzzy community detection to detection community structure at each time step, and secondly establish the relationship between communities at different time steps through the definition of group persistence. As the definition of group persistence is used to establish the relationship between predecessor community and successor community, we are able to characterize community dynamics even if parts of the membership fluctuate. To further analyze and explore community dynamics, we introduced a visualization technique called lineage diagrams. The lineage diagrams allow us to observe how stable communities hold their members over time and how structure changes in the evolution of communities. This approach has been applied to a dynamic co-citation network called historic complex system science. In the experiments, we have applied citation analysis to understand the history of complex system science over time.

An important advantage of our method is its efficiency in detecting and characterizing community dynamics in highly dynamic networks. Therefore, our method is desirable to detect and analyse the evolution of communities in large, noisy networks that exhibit a high number of changes over time.

Outline of this thesis

The thesis is organized as follows. Chapter 1 is the survey of community detection in dynamic networks. We describe the definition of community structure and how a community changes over time. Community detection in dynamic networks becomes a popular issue. This problem is very hard and not yet satisfactorily solved. We review the main algorithms designed for dynamic networks, which are based on techniques for static networks. We also discuss crucial issues like how methods should be tested and compared against each other. Chapter 2 concerns on overlapping community detection. We discuss the importance of overlapping community structure in network analysis and limits of existing algorithms in practice. Then, we transform the problem of overlapping community detection to overlapping node detection, with the developed concept of overlapping nodes into overlapping granularity and overlapping clusters. Therefore, we proposed two distinct methods: clique optimization and fuzzy detection. One is to detect overlapping granularity and the other is to detect overlapping clusters. Applications of the both methods in synthetic networks and real networks have good performances. Particularly, applications in the network between articles, describing the common references of articles relevant to complex systems provide an impressive result: the both methods provide knowledge of intermediate between communities but different characteristics.

In Chapter 3 we consider overlapping community structure on dynamic networks and propose a method based on our previous work. The applications in dynamic networks such as the past history of complex system science, reveal overlapping nodes are important for structural functions and interactions between modules.

Finally, we end in Chapter 4 by concluding our work in community detection with the discussion in future work.

Chapter 1

A survey of community detection in dynamic networks

The material in this chapter is intended to serve as a brief description of recent developments in community detection for dynamic network description. In Section 1.1, we first introduce the concept of community, and discuss the basic quantities of community structure. Then in Section 1.2, we introduce the description of community evolution in dynamic networks. Next, we describe existing algorithms designed for dynamic networks in Section 1.3. The evaluation of the obtained clusterings is an important task, therefore, Section 1.4 is devoted to the discussion of benchmarks for testing the reliability of algorithms. Section 1.5 ends this chapter with a discussion about future research directions in this issue.

Communities in networks

It appears natural and common to model the topology structure of a complex system by a graph (or network). Many real world problems (biological, social, web) can be effectively modeled as networks or graphs where nodes represent entities of interest and edges mimic the interactions or relationships among them. A graph G = (V, E) consists of two sets V and E, where V = {v 1 , v 2 , . . . , v n } are the nodes (or vertices, or points) of the graph G and E ⊆ V × V are its links (or edges, or lines). The number of elements in V and E are denoted by n and m, respectively. In the context of graph theory, an adjacency (or connectivity) matrix A is often used to describe a graph G. Specifically, the adjacency matrix of a finite graph G on n vertices is the n × n matrix A = [A ij ] n×n , where an entry A ij of A is equal to 1 if the link e ij = (v i , v j ) ∈ E exists, and zero otherwise.

In the study of networks, such as computer, information networks, social networks or biological networks, finding underlying community structure is common. Social networks often include community groups based on common location, interests, hobbies, etc. Metabolic networks have communities based on modular functions [START_REF] Ravasz | Hierarchical organization of modularity in metabolic networks[END_REF]. Citation networks form communities by research topic. In each context, communities are groups of nodes in a network with more edges inside than edges linking the rest of the network.

In the following, we introduce the definition of community, which depends on the context. Social network analysts have devised many definitions of communities with various degrees of internal cohesion among nodes [START_REF] James | Structural cohesion and embeddedness: A hierarchical concept of social groups[END_REF][START_REF] Scott | Social network analysis: a handbook[END_REF]. Many other definitions have been introduced by computer scientists and physicists. We distinguish three main classes of definitions: local, global and based on vertex similarity. We review the notion of community structure and hierarchies of communities. We also discuss the definition of the modularity function, derived to measure the quality of a graph partition into communities.

Definitions of community

Local definitions

Communities are parts of the graph (group of nodes), within which the connections are dense and between which the connections are sparse. In some specific systems or applications, they can be considered as separate entities with their own autonomy, which do not depend on the whole graph. For instance in [START_REF] Luce | A method of matrix analysis of group structure[END_REF], communities are defined in a very strict sense and require that all pairs of nodes are connected. In other words, this corresponds to a clique, i.e., a subset whose nodes are all adjacent to each other. However, such a criterion is too strict. A relaxable extended definition is k-clique community, which is the basis of CPM (Clique Percolation Method) [START_REF] Palla | Uncovering the overlapping community structure of complex networks in nature and society[END_REF]. A k-clique community is a series of adjacent cliques, where two k-cliques are adjacent if they share k-1 nodes.

Another criterion for community cohesion is the difference between the internal and external cohesion of the community. This idea is also used to define communities. For instance, Radicchi et al. [START_REF] Radicchi | Defining and identifying communities in networks[END_REF] proposed the definitions of strong communities and weak communities. A set of nodes is a community in a strong sense if the internal degree of each node is greater than its external degree. This definition seems too strict. Its relaxable definition is the community in a weak sense: the internal degree of the community (sum of all its node internal degree) should exceed its external degree. Note that a community in a strong sense is also a weak community, while the converse is not generally true.

Global definitions

Communities can be defined with respect to the graph as a whole. This seems to be reasonable when the community structure is exactly the division of the graph into several groups of nodes. In such a context, many global criteria are used to identify communities, which are all based on the intrinsic idea that a graph offers a community structure if it is not a random graph. Random networks such as Erdös-Renyi's graphs do not display community structure. Indeed, as any pair of nodes are linked with the same probability, there should be no preferential wiring involving special groups of nodes. Therefore, one may define a null model, i.e., a random graph that shares some structural properties of the original graph such as its degree distribution. The null model is the basic element in the conception of the notion of modularity. The modularity is a quality function that evaluates the partition of a graph into disjoint communities. The most popular modularity is proposed by Newman and Girvan [START_REF] Newman | Fast algorithm for detecting community structure in networks[END_REF], which compares the number of edges inside the community to the expected number of internal edges in the null model. A series of algorithms using modularity maximization heuristics [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF][START_REF] Newman | Modularity and community structure in networks[END_REF] for finding communities are proposed and developed.

Definitions based on node similarity

It seems also natural to assume that communities are groups of nodes similar to each other. One can compute the similarity between each pair of nodes with respect to some reference properties. An important class of node similarity measures is based on properties of random walks on graphs, such as commute-time. The commute-time between a pair of nodes is the average number of steps needed for a random walker, starting at either node, to reach the other node for the first time and to come back to the starting node. Saerens et al. [START_REF] Saerens | The principal components analysis of a graph, and its relationships to spectral clustering[END_REF] have studied and used the commute-time as a similarity measure: the larger the commute-time is, the less similar nodes are.

Community structure

Basics

A partition is a division of a graph into disjoint communities, such that each node belongs to a unique community. A division of a graph into overlapping (or fuzzy) communities is called a cover. We use P = {C 1 , . . . , C nc } to denote the partition, which is composed of n c communities. In P, the community to which the node v belongs to is denoted by σ v . By definition we have V = ∪ nc 1 C i and ∀i � = j, C i ∩ C j = ∅. We denote by S = {S 1 , . . . , S nc } a cover composed of n c communities. In S, we may find a pair of community S i and S j such that S i ∩ S j � = ∅.

Given a community C ⊆ V of a graph G = (V, E), we define the internal degree k int v (respectively the external degree k ext v ) of a node v ∈ C, as the number of edges connecting v to other nodes belonging to C (respectively to the rest of the graph). If k ext v = 0, the node v has only neighbors within C: assigning v to the current community C is likely to be a good choice. If k int v = 0 instead, the node is disjoint from C and it should better be assigned to a different community. Classically, we note

k v = k int v + k ext v
the degree of node v. The internal degree k int of C is the sum of the internal degrees of its nodes. Likewise, the external degree k ext of C is the sum of the external degrees of its nodes. The total degree k C is the sum of the degrees of the nodes of C. By definition:

k C = k int C + k ext C .

Modularity

One may want to measure the quality of a partition through a quality function, which assigns a score to each partition of a graph. In this way, partitions can be ranked based on their score given by the quality function. Partitions with high scores are "good ", so the one with the highest score is by definition the best.

The widest accepted quality function is the modularity introduced by Newman and Girvan [START_REF] Newman | Fast algorithm for detecting community structure in networks[END_REF][START_REF] Newman | Finding and evaluating community structure in networks[END_REF]. Let e ij be the fraction of edges in the network that connect nodes in community i to those in community j, and a i = � j e ij . The modularity measure is defined as:

Q = � i � e ii -a 2 i � . (1.1)
This quantity measures the fraction of the within-community edges in the network minus the expected value in a network with the same community division but when connections between nodes are random. If the number of within-community edges is less than the expected number of edges in a random graph, we will get Q = 0. Values approaching Q = 1, which is the maximum, indicate networks with strong community structure. In practice, values for real networks typically fall in the range from 0.3 to 0.7. Higher values are rare. Suppose we have a division of a network into communities. Let σ i be the community to which node i is assigned. The fraction of the edges in the graph that fall within communities, i.e., that connect nodes that both lie in the same community, is

� ij A ij δ(σ i , σ j ) � ij A ij = 1 2m � ij A ij δ(σ i , σ j )
where the function δ(σ i , σ j ) is 1 if σ i = σ j and 0 otherwise. At the same time, the expected number of edges between nodes i and j if edges are placed at random is k i k j /2m, where k i and k j are the degrees of the nodes and m is the total number of edges in the network. Thus the modularity [START_REF] Newman | Analysis of weighted networks[END_REF], as defined above, is given by:

Q = 1 2m � i� =j � A ij - k i k j 2m � δ(σ i , σ j ) . (1.2)
Note that the modularity is always smaller than one but can be negative as well. For instance, the partition where each node represents a single community is always negative. When considering the whole graph as a single community, the modularity is zero as the two terms in this case are equal and cancels each other out. There are also other types of modularity, some of which are motivated by specific classes of clustering problems or graphs [START_REF] Fortunato | Community detection in graphs[END_REF].

Modularity has been employed as quality function in many algorithms, like some division algorithms [START_REF] Newman | Modularity and community structure in networks[END_REF] which give a tradeoff between high accuracy and low complexity. In addition, modularity optimization is the most popular method for community detection. Heuristic proposed in [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF] runs fast and handles very large-scale networks. Modularity also allows to assess the stability of partitions [START_REF] Massen | Thermodynamics of Community Structure[END_REF].

However, the applicability and reliability of modularity for the problem of graph clustering may be limited. An important issue concerning the limits of modularity is raised by Fortunato and Barthelemy [START_REF] Fortunato | Resolution limit in community detection[END_REF]. The study shows that a large value for the maximum modularity does not necessarily mean that a graph has a clear community structure. In a random graph, such as the Erdös-Rényi model, the distribution of edges among the nodes is highly homogeneous. For instance, the distribution of the number of neighbours of a node, or degree, is binomial, so most nodes have equal or similar degree. The random graph is supposed to have no community structure, as the link probability between nodes is either constant or a function of the node degrees, so there is no bias a priori towards special groups of nodes. Still, random graphs may have partitions with large modularity values [START_REF] Guimerá | Modularity from fluctuations in random graphs and complex networks[END_REF][START_REF] Reichardt | Statistical mechanics of community detection[END_REF]. This is due to fluctuations in the distribution of edges in the graph, which determine concentrations of links in some subsets of the graph, which then appear as communities.

Moreover, Fortunato and Barthelemy [START_REF] Fortunato | Resolution limit in community detection[END_REF] have found that modularity optimization has a resolution limit. It may prevent from detecting communities which are comparatively small with respect to the graph as a whole. Given two communities A and B, with a total degree k A and k B respectively and where the number of edges connecting A and B is l AB . The difference of modularity determining the merge of two communities with respect to the whole graph partition is:

ΔQ = � k int A + k int B + 2l AB 2m - � k A + k B 2m � 2 � - � k int A + k int B 2m - � k A 2m � 2 - � k B 2m � 2 � . If l AB = 1, i.e.
, there is a single edge joining A to B, we expect that the two communities should be separated. If k A k B /2m 2 < 1 m , we have ΔQ AB > 0. For simplicity, let us suppose that k A ∼ k B = k, i.e., that the two subgraphs have roughly the same number of edges. We conclude that when k < √ 2m and the two communities A and B are connected, then the modularity is higher if they are in the same cluster [START_REF] Fortunato | Resolution limit in community detection[END_REF]. So, if the partition with maximum modularity includes clusters with total degree of the order of O( √ m) (or smaller), one can not know a priori whether the clusters are composed of single communities or are in fact a combination of smaller weakly interconnected communities. This resolution problem may have important impacts in practical applications.

Hierarchy

An important aspect related to community structure is the hierarchical organization. A community structure can be hierarchically ordered, when the graph has several levels of organization/structure at different scales. In this case, the community structure is hierarchically composed of small communities at each level that are nested within large communities at higher levels. As an example, in a social network of children living in the same town, one could group the children according to schools they attend, but within each school one can make a subdivision into classes. The hierarchical form of organization is often represented as a tree or dendrogram, as shown, for example, in Fig. 1.1. The hierarchy allows efficient analysis of several specific functions using modules, such as majority consensus. Majority consensus is widely used in the reconstruction of phylogenetic trees [START_REF] Clauset | Structural inference of hierarchies in networks[END_REF]. As we move up the tree, the nodes join together to form larger and larger communities, as indicated by the lines, until we reach the top, where all are joined together in a single community. Alternatively, the dendrogram depicts an initially connected network splitting into smaller and smaller communities as we go from top to bottom. A cross section of the tree at any level, such the one indicated by a dotted line, will give the communities at that level. The vertical height of the split points in the tree are indicative only of the order in which the splits or joins take place, although it is possible to construct more elaborate dendrograms in which these heights contain other information. The figure is obtained from Ref. [START_REF] Newman | Finding and evaluating community structure in networks[END_REF].

The presence of hierarchy motivates hierarchical clustering [START_REF] Newman | Finding and evaluating community structure in networks[END_REF], which is a wellknown technique in social network analysis [START_REF] Wasserman | Social Network Analysis: Methods and Applications (Structural Analysis in the Social Sciences)[END_REF], biology [START_REF] Eisen | Cluster analysis and display of genome-wide expression patterns[END_REF] and finance [START_REF] Mantegna | Hierarchical structure in financial markets[END_REF]. Starting from a partition in which each node is its own community, or all nodes are in the same community, one merges or splits clusters according to a topological measure of similarity between nodes. Though this method naturally produces a hierarchy of partitions, nothing is known a priori about their qualities. The modularity is a good quality function to identify a single partition, i.e., the selected partition corresponds to the largest value of the modularity.

Community evolution in dynamic networks

In complex networks, the interactions between entities dynamically evolve over time [START_REF] Bar-Yam | Dynamics of complex systems[END_REF]. Lets take Facebook1 as an example: users add or delete "friends" [START_REF] Ellison | The benefits of facebook friends: Social capital and college students use of online social network sites[END_REF]. Similarly, new forms of social contacts can be observed in phone calls, e-mail exchanges [START_REF] Leskovec | Empirical comparison of algorithms for network community detection[END_REF] or other communications on the Internet.

Traditional analysis treats networks as static graphs, which is either derived from an aggregation of data over the whole network life (experiment measure), or from a snapshot of data at a particular time step. Although this study provides meaningful results, the dynamic features are neglected. Dynamic features are also important in the study of complex networks.

During the last decade, the availability of large data set (thanks to Open Data initiative), the optimized rating of computing facilities, as well as the development of powerful and reliable data analysis tools, have constituted a better and better machinery to explore the topological properties of several networked systems from the real world. This has allowed to study the topology of the dynamic interactions in a large variety of Big Data [START_REF] Crawford | Six provocations for big data[END_REF] as diverse as communication [START_REF] Pastor-Satorras | Evolution and Structure of the Internet: A Statistical Physics Approach[END_REF][START_REF] Pastor-Satorras | Dynamical and correlation properties of the internet[END_REF], social [START_REF] Ebel | Scale-free topology of e-mail networks[END_REF][START_REF] Newman | The Structure and Dynamics of Networks[END_REF] and biological systems [START_REF] Jeong | Lethality and centrality in protein networks[END_REF][START_REF] Camacho | Robust patterns in food web structure[END_REF].

The goal of community detection in dynamic networks is to track community evolution and to identify their dynamics. In the following, we first describe the definitions and notations of a community which is observed at different time steps. Second, we present community dynamics which are used to describe community changes.

Communities in dynamic graphs

A dynamic graph G(V, E) on a finite time sequence 1 . . . Δ is a sequence of graph snapshots {G(1), . . . , G(Δ)}. There is a set V = {v 1 , . . . , v n } of nodes. Each node v i ∈ V appears at least one during the dynamic graph lifetime, i.e., ∃t s.t. v i ∈ G(t).

At each time step t where 1 ≤ t ≤ Δ, the corresponding snapshot G(t) describes interactions between active nodes at time t, where the edges of a snapshot graph is a set of active dynamic links. G(t) is partitioned into a set of temporal clusters P(t) = {C 1 (t), . . . , C n t c (t)}, where n t c denotes the number of temporal clusters in G(t). In some definitions of communities in dynamic networks [START_REF] Falkowski | Data mining for community dynamics[END_REF][START_REF] Falkowski | Users in volatile communities: Studying active participation and community evolution[END_REF], the number of temporal clusters may be not equal to the number of communities at the same time step t . One community C i at time step t is possibly represented by a set of temporal clusters such that C i (t) = {C 1 (t), . . . }.

The problem of tracking community evolution can be resolved by the identification of a set of community evolution paths (or community evolution traces [START_REF] Wang | Community Evolution of Social Network: Feature, Algorithm and Model[END_REF], dynamic communities [START_REF] Greene | Tracking the evolution of communities in dynamic social networks[END_REF]).

Definition 1 (Community evolution path). For a given time window [δ, δ+Δ], an evolution path Evol(C i ) is a time-series of temporal clusters:

Evol(C i ) := {C i (δ), . . . , C i (δ + Δ)} where each temporal cluster C i (t) ∈ Evol(C i ), t ∈ [δ, δ + Δ] is the observation of the com- munity C i .
In the definition of Wang et al. [START_REF] Wang | Community Evolution of Social Network: Feature, Algorithm and Model[END_REF], the observation of the community C i at time t can be the union of several temporal clusters. When a community appears for the first time, it should be a unique temporal cluster.

Community dynamics

When we track community evolution, one problem is to characterize community dynamics. How does a community change over time? Palla et al. have introduced the main phenomena occurring during the lifetime of a community (See Fig. 1.2): creation, growth, reduction, fusion, split and death (or removal). Moreover, Chakrabarti et al. [START_REF] Chakrabarti | Fully automatic cross-associations[END_REF] Figure 1.2: Possible scenarios in the evolution of communities. The figure is gained from [START_REF] Palla | Quantifying social group evolution[END_REF].

proposed the definition of change point to describe a significant change in community structure. In the following, we describe them in details.

Community changes

We show six community changes in Fig. 1.2, which are used to describe the main events occurring in dynamic graphs. In order to identify them, Asur et al. [START_REF] Asur | An event-based framework for characterizing the evolutionary behavior of interaction graphs[END_REF] have proposed a definition.

Definition 2. Let G(t) and G(t + 1) be snapshots of G at two consecutive time steps with the cluster C i (t) and C i (t + 1) denoting the observations of the community C i at time step t and t + 1, respectively.

Continue: C i (t + 1) is the continuation of C i (t) if C i (t + 1) is the same as C i (t): C i (t) = C i (t + 1) κ-Merge: two clusters C i (t) and C j (t) merge into C i (t + 1) if C i (t + 1) contains at
least κ% of nodes belonging to the union of C i (t) and C j (t) and the renewal of C i (t) and C j (t) is at least 50%:

|(C i (t) ∪ C j (t)) ∩ C i (t + 1)| max(|C i (t) ∩ C j (t)|, |C i (t + 1)|) > κ |C i (t) ∩ C i (t + 1)| > |C i (t)|/2 |C j (t) ∩ C i (t + 1)| > |C j (t)|/2 κ-Split: C i (t) is split into C i (t +
|(C i (t + 1) ∪ C j (t + 1)) ∩ C i (t)| | max(|C i (t + 1) ∩ C j (t + 1)|, |C i (t)|) > κ |C i (t) ∩ C i (t + 1)| > |C i (t + 1)|/2 |C i (t) ∩ C j (t + 1)| > |C j (t +
(t + 1), such that |C i (t) ∩ C i (t + 1)| > 1 .
This definition has several limits. First, the definition of one continuation is so strict that almost all communities do not have any continuation at the next time step. Second, the value of κ needs be set to determine when a community is merged or when a community is split. Varying κ may lead to different results. Finally, the definition of emerging community or disappearing community has weaknesses. Some clusters may be generated only by the fluctuation of degree distribution. This artificial clusters will not share a strong common interest. For the disappearance, the process may be too slow: a community may lose its core nodes but still have node attached to it. In this case, the observed community does not share a strong common interest anymore. It is difficult to determine whether a community exists.

There are also other types of definitions [START_REF] Chen | Detecting and Tracking Community Dynamics in Evolutionary Networks[END_REF][START_REF] Gongla | Where did that community go? -communities of practice that disappear[END_REF][START_REF] Greene | Tracking the evolution of communities in dynamic social networks[END_REF]. For example, Chen et al.. [START_REF] Chen | Detecting and Tracking Community Dynamics in Evolutionary Networks[END_REF] characterize community dynamics by tracking community core evolution. Greene et al.. [START_REF] Greene | Tracking the evolution of communities in dynamic social networks[END_REF] use the definition of dynamic communities described above but require that if several dynamic communities share the same temporal cluster at time t, then these dynamic communities should merge.

In Fig. 1.3, we have shown examples of community evolution. There are four dynamic communities over the total three time steps, whose evolution paths are expressed as following: Through these evolution paths, we observe two new communities appearing during network evolution: the community C 2 is the branch of C 1 and the community C 2 emerges at time t = 2. This is an example to illustrate the relationship between community dynamics and community evolution paths. We conclude that the problem of identifying and characterizing community dynamics can be revealed by community evolution paths, whereas the problem of tracking community evolution in dynamic networks can be reformulated as a problem of constructing community evolution paths across one or more time steps.

Evol(C 1 ) ← {C 1 (t), C 1 (t + 1), C 1 (t + 2)} Evol(C 2 ) ← {C 2 (t + 1), C 2 (t + 2)} Evol(C 3 ) ← {C 3 (t), C 3 (t + 1), C 3 (t + 2)} Evol(C 4 ) ← {C 4 (t + 2)}

Change point

There is another definition about community dynamics. Chakrabarti et al. [START_REF] Chakrabarti | Fully automatic cross-associations[END_REF] have detected change point, which represents a significant time point when the system evolves, i.e., a major change (or critical event) occurs in the graph structure during a short period. The approach called GraphScope [START_REF] Chakrabarti | Fully automatic cross-associations[END_REF] applied the MDL (Minimum Description Length) principle [START_REF] Grnwald | Advances in Minimum Description Length: Theory and Applications[END_REF] to compute the encoding cost of assigning nodes into communities. A segment presents a sequence of graphs without any change in its community structure. So the graphs of each segment are characterized by the same partition with the lowest encoding cost. If the cost for encoding a graph into the existing segment is higher than the cost for encoding the graph into a new segment, a significant change of community structure occurs. The change point offers one important benefit of detecting community evolution using information theory.

Community detection in dynamic networks

In order to track community evolution, it is necessary to identify communities at different time steps. In [START_REF] Hopcroft | Tracking evolving communities in large linked networks[END_REF] by hierarchical clustering [START_REF] Jain | Algorithms for Clustering Data[END_REF], and then matched communities at different time steps through natural communities. Natural communities are groups of nodes having high stability against perturbations of interactions. In analysing citation networks, natural communities can be used to denote topics of communities. Tracking natural community evolution allows us to understand the history of topics, such as the emergence of new topics. The idea of detecting time-independent communities at different time steps and then matching them, becomes the basis for several algorithms. They are called two-stage approaches. Each time-independent community is detected independent of the results at other time steps.

Another method [START_REF] Tang | Community evolution in dynamic multimode networks[END_REF][START_REF] Tseng | Facetnet: a framework for analyzing communities and their evolutions in dynamic networks[END_REF][START_REF] Tseng | Analyzing communities and their evolutions in dynamic social networks[END_REF] called evolutionary clustering is proposed to detect time-dependent temporal clusters. The principle of evolutionary clustering [START_REF] Chakrabarti | Fully automatic cross-associations[END_REF] is to simultaneously optimize two potentially conflicting criteria: first, the clustering at any time step should remain faithful to the current data as much as possible; and second, the clustering should not shift dramatically from one time step to the next.

There are also many other methods, such as coupling graph clustering. The coupling graph clustering is a framework which detects community structure of a coupling graph. A coupling graph is a graph linking a sequence of graphs over several time steps by adding coupling edges between the same nodes at different time steps (See Fig. 1.4). Given a coupling graph, a subgraph which describes all interactions at a specific time step is call a slice.

In the following, we begin by listing the challenges raised by community detection in dynamic communities. Next, we review current techniques proposed for community detection in dynamic networks.

Dynamic community detection challenges

Quality function: the cost Reliable algorithms are supposed to provide results having a high quality value. In the case of community detection in dynamic networks, a famous function named α-cost has been used by several algorithms [START_REF] Kumar | Evolutionary clustering[END_REF][START_REF] Sun | Graphscope: parameter-free mining of large time-evolving graphs[END_REF][START_REF] Tseng | Analyzing communities and their evolutions in dynamic social networks[END_REF] for measuring the quality of the found dynamic communities. This α-cost is motivated by the principle of evolution clustering: the community structure at each time step is the evolution of the community structure at the previous time step. Therefore, it is a combination of a snapshot cost and a past history cost. The parameter α controls the relative weight of recent and past history:

cost = α CS + (1 -α) CT (1.3)
where the snapshot cost CS measures how a community structure fits the graph interactions at time t and the past history cost CT qualifies how consistent the community structure is with the past history community structure at time t -1. Let X represent the current community structure, Y represent the community structure at the previous time step, W denote current graph interaction, Λ be an non-negative diagonal matrix, and D(•) be the function for measuring the cost such that D(•) computes the similarity between the network structure and the community structure and the similarity between the current community structure and the previous community structure.

In [START_REF] Tseng | Analyzing communities and their evolutions in dynamic social networks[END_REF], authors defined D(•) as a KL-divergence between two objects such that: CS = D(W � XΛX T ) and CT = D(Y � XΛ). Given two objects A and B, D(A �

B) = � ij � a ij log a ij b ij -a ij + b ij �
. Through this cost definition, the snapshot cost is high when the approximate community structure fails to fit the graph interactions at time t while the past history cost is high when there is a dramatic change of community structure from time t -1 to t.

There exist also other definitions of D(•). In [START_REF] Kumar | Evolutionary clustering[END_REF], two definitions of the cost are introduced: one is the distance between all pairs of objects in an agglomerative hierarchical clustering, and the other is associated with the centroid of the community in k-means clustering [START_REF] Bezdek | Pattern Recognition with Fuzzy Objective Function Algorithms[END_REF]. In k-means clustering, community memberships are measured by the membership degrees of nodes, i.e., the distance between the node to the centroid of its community. Then, in the cost of the community structure of a dynamic graph, the snapshot cost is associated with the distance between the node and the centroid of its community, and the past history cost is computed by the difference between the current community centroid and the community centroid at the previous time step.

In the case of multi-mode networks, Tang et al. [START_REF] Tang | Community evolution in dynamic multimode networks[END_REF] have suggested the resolution by transforming the problem in multi-mode networks into the problem of two-mode. Most of existing work concentrates on one-mode network. That is, there is only one type of social actors (nodes) involved in the network and the ties (interactions) between actors are all of the same type. This is common in a broad sense such as friendship network, Internet, phone call network, etc. . However, some applications such as web mining, collaborative filtering, and online targeted marketing involve more than one type of actors and multiple heterogeneous interactions between different types of actors. Such a network is called multi-mode network [START_REF] Wasserman | Social Network Analysis: Methods and Applications (Structural Analysis in the Social Sciences)[END_REF].

Given an m-mode network, for each mode i, let X i denote this mode of nodes, such as X i = {x i 1 , . . . , x i n i }, where n i is the number of nodes for X i . Then, for each pair of modes, we use R t ij ⊆ X i × X j to represent interactions between two modes of nodes X i , X j at time t. Ideally, the interaction between nodes can be approximated by:

R t ij ≈ C t i A t ij (C t j ) T
where C t i is the cluster membership for X i at time t and A t ij represents the group interaction. The group interaction is computed by

A t ij = (C t i ) T R t ij C t j .
Therefore, for each temporal m-mode graph at time t, its snapshot cost CS can be formulated as:

� 1�i<j�m w (i,j) a D � R t ij � C t i A t ij (C t j ) T � ,
and its history cost CT is expressed as:

� 1�i�m w i b D � C t i � C t-1 i � ,
where w ij a is an importance factor for every pair of modes i and j, and w i b is a relative importance factor for each mode i.

The optimal value of the cost corresponds to a good community structure which incorporates the deviation from the past history. There exist several algorithms detecting community evolution by optimizing α-cost, such as community model (See Section 1.3.3). However, the value of the parameter α is a priori unknown, which is a major limitation. Since the parameter α controls the relative weight of recent and past history, the obtained results [START_REF] Kumar | Evolutionary clustering[END_REF] depend on the value of α: a lower value of α yields to a less change of community structure. If α = 0, the obtained community structure is exactly the same as applying the community detection algorithm independently on each snapshot. A good quality function for dynamic graphs should find the perfect compromise and accommodate past history without compromising the snapshot quality.

Matching metric

A matching metric is a similarity function, which measures how similar two communities are. It is often used in two-stage approaches to connect similar communities. Of course, we can measure the similarity between two temporal clusters at different time steps. Then, we obtain how one community evolves from one time step to the following time steps.

Hopcroft et al. [START_REF] Hopcroft | Tracking evolving communities in large linked networks[END_REF] defined a match function. Let C and C � be two clusters, their match value is written as follows: The definition ensures that a high matching value (close to 1) occurs when two clusters have many common nodes and are roughly of the same size. The best match value for C at time t, is the highest match(C, C � ) value for any cluster C � at time t.

match(C, C � ) = min � |C ∩ C � | |C| , |C ∩ C � | |C � | � (1.
Palla et al. [START_REF] Palla | Quantifying social group evolution[END_REF] defined relative overlap, which is a Jaccard index. The relative overlap value between two communities X and Y is written as follows:

J(X, Y ) = |X ∩ Y | |X ∪ Y | . (1.5)
By definition, the cluster C(t + 1) at time t + 1 is matched to the cluster C(t) which has the largest overlap at time t.

Another bipartite mapping metric is dynamic Jaccard's index, whose definition is:

JacD � (X, Y ) = J(X, Y ) |t -t � | (1.6)
where |tt � | represents the time interval duration between communities X and Y . It allows a temporal cluster matched to an old one (|tt � | > 1) which disappeared during several time steps.

Two communities are matched if they share the highest matching value. The matching metric is a natural resolution to connect temporal clusters over time. So it is often used in two-stage methods [START_REF] Hopcroft | Tracking evolving communities in large linked networks[END_REF][START_REF] Palla | Quantifying social group evolution[END_REF][START_REF] Tantipathananandh | A framework for community identification in dynamic social networks[END_REF]. Its another advantage is to characterize community dynamics (See Section 1.2.2). However, there is no standard definition of matching metric. In Hopcroft et al. [START_REF] Hopcroft | Tracking evolving communities in large linked networks[END_REF]'s match function (Eq. 1.4), the minimum size of communities is important for the comparison. Instead, the size of the union of communities is essential in the relative overlap (Eq. 1.5). Furthermore, a minimum intersection size threshold needs to set, i.e., the minimum number of common nodes shared by the matching communities.

Two-stage approaches

The basic idea of two-stage approaches is to detect temporal clusters at each time step, and then establish relationships between clusters for tracking community evolution over time. Figure 1.3 illustrates the result of applying a two-stage approach to a dynamic network across three time steps. In a first phase, clusters at each time step are detected: at time t, there are two clusters, then there are three clusters at time t + 1 and four clusters at time t + 2. In a second phase, the relationship between clusters at different time steps are established, which is shown by colours. Through the above results, we learn how the community structure of this graph evolves from the time step t to the time step t + 2. For the first phase, we apply a graph clustering algorithm [START_REF] Girvan | Community structure in social and biological networks[END_REF]. For the second phase, we can use a matching metric (See Section 1.3.1). However, it may lead to noisy results where some nodes often change their community memberships. Therefore, many advanced resolutions are proposed to resolve this matching problem.

Core-based methods

If a partition is significant, it will be recovered even if the structure of the graph is modified, as long as the modification is not too extensive. Instead, if a partition is not significant, we may observe that minimal perturbations of the graph will suffice to disrupt its group memberships. A significant cluster, i.e., a significant group of nodes, is often defined as a community core. We can reduce noisy results by matching community cores. This is the main principle of core-based methods. The matching metric (See Section 1.3.1) is often applied. Two temporal clusters are matched if their community cores share the highest similarity value.

Hopcroft et al. have proposed the concept of natural communities, which are significant clusters that have high stability against modification of graph structure. Given a temporal graph, by applying 5% of perturbations, a set of modified graphs are produced, each of which has 95% of core nodes. Each natural community is identified by the partitions corresponding to these modified graphs, which has the best match value with clusters in those partitions.

Rosvall et al. [START_REF] Rosvall | Mapping change in large networks[END_REF] used a bootstrap method [START_REF] Efron | An Introduction to the Bootstrap[END_REF] to detect significance of clusters. The bootstrap method assesses the accuracy of an estimate by resampling from the empirical distribution of observations. Each graph can be resampled by assigning to each edge a weight taken from a Poisson distribution with mean equal to the original edge weight. A graph clustering method is applied to the original graph and the samples. For each community in the original graph's partition, they define its largest subset of nodes that are classified in the same community in at least 95% of all bootstrap samples, as the significant cluster.

In some methods, core nodes are identified through their roles within their communities. Given a community, there are core nodes and peripheral nodes. Guimerá and Amaral [START_REF] Guimerá | Cartography of complex networks: modules and universal roles[END_REF] have classified community members into different roles according to intraand inter-module connection patterns. With respect to core node identification, Wang et al. [START_REF] Wang | Community Evolution of Social Network: Feature, Algorithm and Model[END_REF] defined core nodes, where each core node v satisfies � u∈neighbours (k vk u ) > 0. In [START_REF] Beiró | Visualizing communities in dynamic networks[END_REF], k-cores nodes [START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF] are detected with a threshold k where k-core decomposition is used for filtering out peripheral nodes.

Although core-based approach can smooth variances caused by peripheral nodes, its results still suffer from some limits such as the parameters used in matching metrics. In additional, if we only track evolution of community cores, there is a risk of missing important structural changes which are related to peripheral nodes. Another important early work [START_REF] Palla | Quantifying social group evolution[END_REF] for detecting community evolution is related to the union graph. Each union graph merges two graphs (union of their links) present at contiguous time steps. Let G(t, t + 1) denote the union graph resulting from the union of two graphs at time t and t + 1. We have E t,t+1 = E t ∪ E t+1 . Figure 1.7 gives an example of an union graph. Any community present at t or t + 1 is contained in exactly one community in the union graph. Thus, communities in the union graph provide a natural connection between communities at t and t + 1. If a community in the joined graph contains a single community from t and a single community from t + 1, then they are matched. If the joined group contains more than one community from both time steps, the communities are matched in decreasing order of their relative node overlap (Eq. 1.5). The technique is validated by applying it to two social systems: a graph of phone calls between customers of a mobile phone company over one year and a collaboration network between scientists spanning a period of 142 months.

Union-graph-based methods

The union graph smooths the change between every pair of consecutive time steps. This property can reduce the fluctuation caused by noisy data. In addition, the union graph allows us to directly determine the links between temporal clusters at consecutive time steps. It simplifies the problem of tracking community evolution.

The main disadvantage of this technique is that the CPM algorithm used only detects communities in certain contexts, i.e., CPM algorithm fails to detect community structure of networks with few cliques. In addition, some parameters are used to determine how community change due to the application of similarity metric.

Survival-graph-based methods

Given a dynamic graph, its community survival graph is constructed by representing community instances as nodes which are linked via edges based on their similarity. One can divide this community survival graph into final communities. Each final community groups a set of temporal clusters and spans several time steps as shown in Fig. 1 The first approach associated with survival graph is proposed by Falkowski et al. [START_REF] Falkowski | Data mining for community dynamics[END_REF][START_REF] Falkowski | Users in volatile communities: Studying active participation and community evolution[END_REF]: first cluster each temporal graph to find community instances at each time step, then construct a community survival graph, and finally cluster the community survival graph to find final communities by using a hierarchical edge betweenness clustering [START_REF] Girvan | Community structure in social and biological networks[END_REF].

To construct a community survival graph, a time window is set to compare the similarity between community instances and connect the similar community instances with edges. In another words, this time window size is the largest time distance between every pair of connected community instances in a community survival graph. The applied hierarchical edge betweenness clustering (see Algorithm 1) contains an iteration, which eliminates edges to separate subgraphs. In Falkowski et al.'s method, a parameter k is applied to determine the number of iterations. The connected subgraphs retained after k iterations correspond to the final communities. A connected subgraphs consists of similar community instances.

Chi et al. [START_REF] Chi | Structural and temporal analysis of the blogosphere through community factorization[END_REF] have detected final communities through a soft clustering [START_REF] White | A spectral clustering approach to finding communities in graphs[END_REF], after detecting community instances [START_REF] Newman | Modularity and community structure in networks[END_REF][START_REF] Shi | Normalized cuts and image segmentation[END_REF][START_REF] White | A spectral clustering approach to finding communities in graphs[END_REF] at each time step. At a time step i, the graph interaction is denoted by

A i ⊆ V × V with l i basis subgraphs B i = [B i 1 , . . . , B i l i ].
Each basis subgraph describes interactions between nodes within a community instance. Across a time window [1, . . . , Δ], graph interactions can be denoted by a 3-dimensional tensor:

A = [A 1 , . . . , A Δ ] ∈ R n×n×Δ . For the total N c = � Δ i=1 l i basis subgraphs, another 3-dimensional tensor is defined: B = [B 1 1 , . . . , B Δ l Δ ] ∈ R n×n×Nc .
Then, the final communities are obtained by minimizing the objective function:

D(A � BUV T ). The matrices U = [u kj ] Nc×nc and V = [v ij ]
Δ×nc are the solution of the optimization problem. For each dynamic community j, u kj is a vector of weight on k-th basis subgraph. At each time step i, v ij is a community intensity for j-th final community.

In this method, the size of time windows and basis subgraphs are issues. A good size value of time windows allows us to group small community instances into a final community, if these small community instances have high frequency grouped together. The size of basis subgraphs is related to insignificant subgraphs (for example, a subgraph with only a couple of nodes), as insignificant subgraphs are removed for the computation. The larger size threshold of basis subgraphs is, the less iterations are used for computing U as less number of N c . Therefore, the computation time can be optimized by increasing the size threshold of basis subgraphs.

For the number of communities n c , they try different values to compare the reconstruction error and then choose one that is reasonably small and at the same time explains data reasonably well.

In [START_REF] Tantipathananandh | A framework for community identification in dynamic social networks[END_REF], authors use a similar approach which tracks community evolution by connecting community instances but they use another notion of final community. A quality function called node cost is defined to determine the community membership for each node over time. This function is the sum of two costs: the cost of one node to keep its community membership and the cost of one node to change its community membership. Therefore, final community detection is transformed into the problem of optimizing this function. Optimizing this function is shown to be a NP-complet problem. Another solution withan approximate factor is proposed in [START_REF] Tantipathananandh | Constant-factor approximation algorithms for identifying dynamic communities[END_REF]. In their proposed node cost function, the importance of different costs is predefined. Giving a high importance to cost of a node to keep its community membership, makes node membership stable for a long time duration. Giving a high importance to the cost of a node to change its community member, makes node membership to fit to current snapshot structure. Survival-graph-based method gives results about how dynamic communities evolve over time directly. It simplifies the problem of tracking community evolution. Compared to other two-stage approaches, which track community evolution by identifying observations at each time step, this technique is more practical. However, some issues arise: How to choose the time window size ? How to choose the number of clustering iterations in [START_REF] Falkowski | Users in volatile communities: Studying active participation and community evolution[END_REF]? How to choose the size threshold of basis subgraphs and the number of final communities in [START_REF] Chi | Structural and temporal analysis of the blogosphere through community factorization[END_REF]? And how to choose the importance value in [START_REF] Tantipathananandh | A framework for community identification in dynamic social networks[END_REF].

Conclusion

Methods presented above are two-stage like approaches:

1. Clusters are detected at each time step independently of the results at any other time step;

2. Relationships between clusters at different time steps are inferred successively.

Such natural process often produces significant variations between partitions that are close in time, especially when the datasets are noisy. Since the first phase is independent of the past history, smooth transitions are impossible. Such an approach may produce artifacts if the data are noisy and variations between partitions may also be generated by the community detection algorithm it-self. Such artifacts yield to artificial community dynamics rather than the real graph evolution. For each graph, let O(P ) denote the partition detection time and O(M ) represent the computation time for the matching problem. The total time complexity of a two-stage approach on a time window of length T is in O((P + M ) T ).

Evolutionary clustering

An evolutionary clustering approach follows a principle of detecting community structure based on the current graph topology information at a given time t and on the community structure at previous time steps. The quality function used for dynamic community structure is: α-cost (See Eq. 1.3). By assuming that a good community structure has a high α-cost value, many optimization methods are proposed and are applied to real dynamic networks. For instance, Lin et al. [START_REF] Tseng | Facetnet: a framework for analyzing communities and their evolutions in dynamic networks[END_REF][START_REF] Tseng | Analyzing communities and their evolutions in dynamic social networks[END_REF] used a probabilistic model to capture community evolution by maximizing α-cost. On one hand, proposed frameworks called community model usually search the optimal community structure for modeling the sequence of graphs by encompassing interactions of the whole graphs. On the other hand, incremental/online algorithms only consider interaction changes such as link insertion or link deletion which also make sense in detecting structural changes. In the following, we will review these evolutionary clustering methods.

Community model

Community evolution can be modelled by a sequence of graphs based on a probabilistic model, which assumes that:

1. The interactions of the graph at each time step follow a certain distribution; 2. The community structure follows a certain distribution that is determined by the community structure at the previous time step.

The first attempt has been done by Lin et al. [START_REF] Tseng | Facetnet: a framework for analyzing communities and their evolutions in dynamic networks[END_REF][START_REF] Tseng | Analyzing communities and their evolutions in dynamic social networks[END_REF] through α-cost function optimization. Let W t denote a graph structure at time t and X t Λ t represent its community structure. By defining Z t = X t Λ t (X t ) T , the authors have devised an α-cost (Eq. 1.3):

cost = α D(W t � Z t ) + (1 -α) D(Z t-1 � Z t ) .
Consequently, they estimate X t and Λ t for optimizing the cost. The problem of community detection at each time step becomes a problem in terms of maximum a posteriori (MAP) estimation. An EM algorithm for solving the MAP problem is given in [START_REF] Tseng | Facetnet: a framework for analyzing communities and their evolutions in dynamic networks[END_REF][START_REF] Tseng | Analyzing communities and their evolutions in dynamic social networks[END_REF] with a low complexity where the graph structure is sparse.

This technique enables to detect overlapping community structure and track community evolution directly. So it is a good resolution for the problem of community detection in dynamic graphs. However, a priori the value of α is a drawback.

Yang et al. [START_REF] Yang | A bayesian approach toward finding communities and their evolutions in dynamic social networks[END_REF] also used a dynamic stochastic block model (DSBM) for finding communities and their evolutions in a dynamic social network. In their study, they have applied a Bayesian treatment for parameter estimation that computes the posterior distributions for all the unknown parameters.

Let W t ∈ R n×n denote a graph structure at time t and Z t ∈ R n×nc is its community structure. For each node i, it is assigned into community k with a probability π k , such as Π = [π 1 , . . . , π nc ] ∈ R nc . For a pair of nodes i and j whose community memberships are k and l respectively, the link connecting them is assumed to follow a Bernoulli distribution with parameter P kl , such as

w t ij ∼ Beronulli(• | P kl ), i.e., W t ∼ Pr(W t | P, Z t )
, where P = [P kl ] nc×nc . For a community matrix Z t-1 , a transition matrix B ∈ R n×n is assumed to model Z t , such as Z t ∼ Pr(Z t | Z t-1 , B). So we write the likelihood for the DSBM model as follows:

Pr(W t , Z t | Π, P, B) .

With the Bayesian Model, a posterior probability Pr(Z t | W t ) is computed with an inference algorithm.

There is no parameter in this technique. However, the authors only provide performances of the applications to networks with nearly ten time steps and a few hundred nodes. For large networks such as millions nodes and hundreds of time steps, the performance of this technique is not clear.

The community model captures community evolution by modeling the sequence of graphs. It performs well when applied to stable evolving graphs. However, it suffers from scalability problems due to an expensive matrix computation and storage cost.

Incremental/Online algorithms

The incremental spectral clustering [START_REF] Ning | Incremental spectral clustering with application to monitoring of evolving blog communities[END_REF] is one of the early incremental algorithms that update matrices like the degree matrix or the Laplacian matrix according to changes of graph interactions [START_REF] Luxburg | A tutorial on spectral clustering[END_REF]. In traditional spectral clustering, community detection is transformed into the eigenvalue problem of Lq = λDq, where L is the Laplacian matrix, q is the cluster indicator, λ is the eigenvalue and D is the degree matrix. Using incremental computation yields to a lower computational cost than the standard spectral clustering. Incremental computation only takes into account changes, thus the computation matrix is sparse. In addition, a tunable threshold τ is used to balance the computational cost and the accuracy. One drawback is that errors are accumulated after several steps and when the dataset grows or changes frequently the associated cost becomes expensive.

Modularity optimization is the most popular method for community detection. It is extended to detect community evolution, e.g., the modularity-driven clustering proposed by Gorke et al. [START_REF] Görke | Modularity-Driven Clustering of Dynamic Graphs[END_REF]. Their basic idea is to detect community structure by starting from a pre-clustering obtained from a standard modularity optimization heuristic. Then, they proposed and discussed heuristics based on global greedy algorithms or on local greedy algorithms. They pass a pre-clustering to the global version to adapt it to the dynamic case (dGlobal). Similarly, the local version remembers its old results: roughly speaking, the dynamic local version (dLocal) starts by letting all free (elementary) nodes reconsider their cluster. Then it lets all those (super-)nodes on higher levels reconsider their cluster, whose content has changed due to lower level revisions. Similarly, Dinh et al. [START_REF] Dinh | A General Approach for Modules Identification in Evolving Networks[END_REF] proposed another method extended from community optimization.

The community detection based on node similarity such as DBSCAN [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF] is also extended for detecting dynamic community evolution [START_REF] Ester | Incremental clustering for mining in a data warehousing environment[END_REF]. DBSCAN considers a community as a core node and a neighbourhood. For each core node, its community must consist of at least η nodes within a radius distance ε. In IncrementalDBSCAN [START_REF] Ester | Incremental clustering for mining in a data warehousing environment[END_REF], each community updates its neighbourhood if its community members have changed their neighbours. Similarly, DENGRAPH [START_REF] Falkowski | Studying community dynamics with an incremental graph mining algorithm[END_REF] detected community evolution according to the core nodes and their neighbourhoods. Instead of a distance radius ε, a different distance function is proposed to compute core nodes and their neighbourhoods.

Incremental or online method can detect dynamic communities and save time by avoiding computations on sub-graphs where there is no change. However, all above approaches need predefined parameters.

Conclusion

There exist many other evolutionary clustering approaches. As mentioned in Section 1.2.2, information theory has also been used to detect community evolution in dynamic graphs. Sun et al. applied the MDL to find the minimum encoding cost to describe a time sequence of graphs and their partitions into communities. The basic principle of this method is to encode the graph topology into a compression information with the minimum cost of the description. This method enables to provide meaningful information on community evolutions. However, one drawback is the problem called relevant variable, which is the variance between real data and data compression. To what extent is information theory able to capture community structures? To our knowledge, we are still far from a precise definition of community while modularity (defined by Eq.1.2) is the widest accept quality function. (2) all-to-all inter-slice coupling, appropriate for categorical slices. The figure is gained from Ref. [START_REF] Mucha | Community structure in time-dependent, multiscale, and multiplex networks[END_REF].

As opposed to two-stage approaches, evolutionary clustering does not encounter the matching problem. However, most methods are using parameters. Furthermore, we stress that evolutionary clustering results are generally too strongly correlated with community history which may occult structural changes.

Coupling graph clustering

Coupling graph clustering approach is based on a coupling graph as shown in Fig. 1.4. The underlying idea is once the coupling graph built (encompassing the time dimension as edges) to use an efficient standard static community detection heuristic. The first attempt is [START_REF] Jdidia | Communities detection and analysis of their dynamics in collaborative networks[END_REF] where authors built a temporal graph and then used the classical community detection algorithm Walktrap [START_REF] Pons | Computing communities in large networks using random walks[END_REF]. The community evolution can be traced through group memberships over time.

Another method is proposed by Mucha et al. [START_REF] Mucha | Community structure in time-dependent, multiscale, and multiplex networks[END_REF]. They detected dynamic communities by optimizing a modified modularity, which is motivated by α-cost (Eq. 1.3). The modified modularity balances the contribution of community memberships to each slice and the cost for changing community memberships. The major advantage of this algorithm is to smooth community evolution. However, its results rely on the parameter α and the relative weight of coupling. This idea of coupling graph clustering simplifies the problem of detecting community evolution. However, it introduces the problem about how to construct coupling graphs: how to add the weight on coupling edges? what is the length of coupling windows (i.e., the longest time interval between nodes connected by coupling edges)? For the length of coupling windows, we illustrate examples in Fig. 1.8. This figure is taken from [START_REF] Mucha | Community structure in time-dependent, multiscale, and multiplex networks[END_REF], where each snapshot graph is called a slice. Two different lengths of coupling windows are given: a) couplings between neighboring slices such that the length is two time steps; and b) all-to-all inter-slice couplings such that the length is the total time steps.

Benchmarks

When designing a new algorithm, it is necessary to stress it through series of simple benchmark graphs, artificial or from the real world, for which the community structure is known. If the algorithm provides results agreeing with the ground truth, we may consider that the algorithm is reliable and can be used in applications. In this section, we firstly describe current benchmarks for testing dynamic community detection algorithms, and secondly review measures for comparing the similarity between computed modular structure and a ground truth.

Benchmark graphs

Computer-generated graphs

Computer-generated graphs try to build random graphs that have natural partitions. The simplest model of this form is for the graph bisection problem. This is the problem of partitioning the vertices of a graph into two equal-sized sets while minimizing the number of edges bridging the sets. To create an instance of the planted bisection problem, we first choose a partition of the vertices into equal-sized sets V 1 and V 2 . When then choose probabilities p in > p out , and place edges between vertices with the following probabilities: The expected number of edges crossing between V 1 and V 2 will be p out |V 1 | |V 2 |. If p in is sufficiently larger than p out , then every other bisection will have more crossing edges. There have been many analyses of the generalization of planted partition models to more than 2 partitions [START_REF] Condon | Algorithms for graph partitioning on the planted partition model[END_REF][START_REF] Mcsherry | Spectral partitioning of random graphs[END_REF]. The number of sub-graphs is equal to the number of predefined communities, and nodes within the same community are connected with a probability of p in and connect to the rest with a probability of p out . In addition, each subgraph is modeled by an Erdös-Rényi's model, which assigns equal probability to all graph edges. The model is motivated by the idea that vertices (or general items) belong to certain categories, and that vertices in the same categories are more likely to be connected. Such models also arise in the analysis of clustering algorithms. However, it is not clear that these models represent practice very well.

Lin et al. [START_REF] Tseng | Facetnet: a framework for analyzing communities and their evolutions in dynamic networks[END_REF] have proposed a computer-generated benchmarks for testing their evolutionary clustering framework called FacetNet (See Section 1.3.3). They use the model of Newman [START_REF] Newman | Finding and evaluating community structure in networks[END_REF] similar to the previous model as a basis (4 clusters of 32 nodes). They generate different graphs for each time steps. In each time step, dynamic is introduced as the following: from each community, they randomly select 3 members to leave their original community and to join randomly the other three communities. Edges are added randomly with a higher probability p in for within-community edges and a lower probability p out for between-community edges. The average degree for nodes is set to 16.

Another similar benchmark is proposed in [START_REF] Duan | Community mining on dynamic weighted directed graphs[END_REF]. To introduce change points (See Section 1.2.2), sequence of graphs are separated into segments. Each segment is a sequence of graphs sharing the same community structure. The average degree of nodes and the internal and external connection probability are fixed. The edge weights are integers randomly chosen from 1 to 10 for intra-community edges and from 1 to 6 for inter-community edges.

All benchmarks for dynamic community detection extended from the planted partition model, used by Newman et al. have two main drawbacks: a) all nodes have the same expected degree; b) all communities have equal size. These features are unrealistic, as complex networks are known to be characterized by heterogeneous distributions of degree and community sizes.

Greene and Doyle [START_REF] Greene | Tracking the evolution of communities in dynamic social networks[END_REF] proposed a set of benchmarks based on Lancichinetti and Fortunato's technique [START_REF] Lancichinetti | Benchmark graphs for testing community detection algorithms[END_REF]. Lancichinetti and Fortunato assumed that the distributions of degree and community size are power laws, with exponents τ 1 and τ 2 , respectively. Each node shares a fraction 1µ of its edges with the other nodes of its community and a fraction µ with the rest of the graph; µ is a mixing parameter in range of [0, 1]. Greene and Doyle contracted four different synthetic networks for four different event types, covering 15, 000 nodes over 5 time steps. In each of the four synthetic datasets, 20% of node memberships were randomly permuted at each step to simulate the natural movement of users between communities over time. Subsequently, community dynamic events were added as follows:

Intermittent communities at each time step, 10% of communities are unobserved from time t = 2 onwards.

Expansion and Contraction at each time step, 40 randomly selected communities expand or contract by 25% of their previous size.

Birth and death at each time step, 40 additional communities are created by removing nodes from other existing communities, and randomly remove 40 existing communities.

Merging and splitting at each time step, 40 temporal clusters of communities split, together with 40 cases where two existing communities were merged.

Chen et al. [START_REF] Chen | Detecting and Tracking Community Dynamics in Evolutionary Networks[END_REF] constructed benchmark graphs using GTgraph [START_REF] Bader | Gtgraph: A synthetic graph generator suite[END_REF] based on a recursive matrix graph model (R-MAT) [START_REF] Chakrabarti | R-mat: A recursive model for graph mining[END_REF]. The R-MAT model follows the preferential attachment idea (growing model where new nodes prefer to connect to existing nodes with higher degrees). In order to build a graph, the R-MAT recursively subdivides the adjacency matrix into four equal-sized partitions, and assigns edges within these partitions with a unequal probabilities:

1. Starting with an empty adjacency matrix, which represents a subgraph for edge assignment;

2. Assign edges into the matrix with probabilities a, b, c, d respectively (See Fig. 1.9).

The chosen partition is again subdivided into four smaller partitions, and the above procedure is repeated until the chosen partition is composed of a simple cell such as a single node. In Chen et al.'s method, they define some nodes as graph-dependent nodes. These graph-dependent nodes play the role of core nodes, and are used to identify communities. The community dynamics can be revealed by the community member changes, where these communities are mapped through graph-dependent nodes.

The main drawback of above computation-generated benchmarks is that the evolution of a dynamic network corresponds to a fixed probability. We may expect that in real networks communities may experience heterogeneous changes such as bursty node insertion probability, node deletion probability, link insertion probability or link deletion probability.

Real networks

Real networks are also used to show performances of algorithms, such as Karate, Football, Dolphins and Neural. When dealing with real data, the main issue is generally the ground truth or a fine and precise expertise on the data sets. Real networks are released by Newman and can be downloaded from http://www-personal.umich.edu/ ~mejn/ netdata/. Mucha et al. [START_REF] Mucha | Community structure in time-dependent, multiscale, and multiplex networks[END_REF] performed simultaneous community detection across multiple resolutions (scales) in the well-known Zachary Karate Club network, which encoded the friendships between 34 members of a 1970s university karate club [START_REF] Zachary | An information flow model for conflict and fission in small groups[END_REF]. Keeping the same unweighted adjacency matrix across slices (each slice represents a graph at a time step), the resolution associated to each slice is dictated by a specified sequence of γ Δ parameters, such as γ Δ = {0.25, 0.5, 0.75, . . . , 4}. In other words, given a serie of slices A ijΔ = {A ij (1), . . . , A ij (Δ)}, these slices share the same unweighted adjacency matrix such as ∀ t r , t s , A ij (t r ) = A ij (t s ). Figure 1.10 depicts the community assignments obtained for coupling strengths ω = {0, 0.1, 1} between each neighboring pair of the 16 ordered slices. These results simultaneously probe all scales, including the partition of the Karate Club into four communities at the default resolution of modularity. Additionally, nodes that have an especially strong tendency to break off from larger communities are identified.

The previous definition for building benchmark graphs does not change interactions between nodes. Community structure changes observed are caused by tuning the resolution (scale) of the networks. Therefore, we can not use it to test the reliability of community dynamic detecting algorithms. Its other drawback is that the algorithm should use the same resolution parameter, otherwise it fails to test the performance of the algorithm in smoothing community evolution.

Comparing partitions

To measure the similarity between the built-in modular structure of a benchmark and the one delivered by an algorithm, several similarity measurements are possible. The most used similarity measurement is the normalized mutual information, which is based on information theory [START_REF] Danon | Comparing community structure identification[END_REF]. The idea is that, if two community structures are similar to each other, only little information is used to infer one community structure by given the other one.

The normalized mutual information is based on the mutual information. The mutual information for two random variables X, Y is denoted by I(X, Y ), and is defined as:

I(X, Y ) = � x � y P (x, y) log P (x, y) P (x)P (y)
where P (x) indicates the probability that X = x (similarly for P (y)) and P (x, y) is the joint probability of X and Y , i.e., P (x, y)

= P (X = x, Y = y). Actually, I(X, Y ) = H(X) -H(X|Y )
, where H(X) is the Shannon entropy of X and H(X|Y ) is the the entropy of X conditional on Y . Danon et al. [START_REF] Danon | Comparing community structure identification[END_REF] defined the normalized mutual information (NMI) for comparing the similarity between two partitions: P x and P y . Let n x and n y denote the number of communities in the partition P x and P y respectively. The normalized mutual information is defined as: NMI = 2I(P x , P y ) H(P x ) + H(P y )

.

(1.7)

Let

I(P x , P y ) = nx � i=1 ny � j=1 P (C i , C � j ) log P (C i , C � j ) P (C i )P (C � j ) H(P x ) = - nx � i=1 P (C i ) log P (C i )
where n x and n y denote the number of communities in two partitions P x and P y respec-

tively, P (C i ) = |C i | n and P (C i , C � j ) = |C i ∩C � j |
n . Danon et al.'s normalized mutual information can be directly written in:

NMI = -2 � � N ij log N ij N N i• N •j � nx i=1 N i• log N i• N + � ny j=1 N •j log N •j N , (1.8)
where N ij represents the size of overlaps in communities i and community j, N i• is the sum of i-th row in matrix N ij , and N •j is the sum of j-th column. The normalized mutual information is equal to 1 if the partitions are identical, whereas it has an expected value of 0 if the partitions are independent. This normalized mutual information is extended for comparing covers in [START_REF] Lancichinetti | Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[END_REF]. The normalized mutual information for covers S x and S y is denoted by N(S x |S y ), and is defined as:

N(S x |S y ) = 1 - 1 2 [H(S x |S y ) norm + H(S y |S x ) norm ] (1.9)
where the normalized conditional entropy of H(S x |S y ) norm (similarly to H(S y |S x ) norm ) of the cover S x with respect to S y is defined as:

H(S x |S y ) norm = 1 n x nx � i=1 H(S i |S y ) H(S i ) , where S i ∈ S x , n x = |S x |
The conditional entropy of S i with respect to all the components of S y is defined by:

H(S i |S y ) = min S � j ∈Sy H(S i |S � j ) (1.10)
where H(S i |S � j ) denotes the conditional entropy of a community S i by given a community S � j .

As Eq. 1.10 only counts the minimum H(S i |S � j ), this extended normalized mutual information suffers from the following problem: some communities sharing few common nodes may be not be taken into account. Moreover, this normalized mutual information is not ideal: given two covers S x , S y , if only one community of S x is divided into several small ones in S y while all the others communities stay identical, the normalized mutual information is low because some communities have very low conditional entropy.

The main drawback of the above similarity measurements is that they are proposed for static graphs, and they do not consider the community dynamics. Therefore, we propose to measure the similarity between the found community structure and the ground truth of dynamic graphs by counting the similarity between every pair of communities' evolution paths. We can write NMI (Eq. 1.7) by setting

P (C i ) = � Δ t=1 |C i (t)| � Δ t=1 n(t) P (C i , C j ) = � Δ t=1 |C i (t) ∩ C j (t)| � Δ t=1 n(t)
where n(t) represents the nodes assigned to the partition in time t and C i (t) represents the observation of community C i at time t (similarly for C j (t)).

Conclusion

In this chapter, we have reviewed current research about community detection in dynamic networks. From our review, we observe that this issue has attracted a lot of work in recent years. Diverse approaches have been proposed and applied for detecting communities in dynamic networks and mining community dynamic models. A number of important issues stay open, such as benchmark graphs, overlapping community evolution. Finally, the main motivation encouraging us is to mine the relationship between the algorithmic communities compare to the reality. Why communities split, or merge, or disappear? What is the effect of overlapping nodes? To answer these questions, we study features behind graph topology and hope to learn more information.

Chapter 2

Overlapping communities and modularity

In real networks, it is common for nodes to belong to several communities. Communities may thus overlap with each other. For example, people may share the same hobbies in social networks [START_REF] Traud | Community Structure in Online Collegiate Social Networks[END_REF], some predator species have the same prey species in food webs [START_REF] Krause | Compartments revealed in food-web structure[END_REF] and different sciences are connected by their interdisciplinary domain in co-citation networks [START_REF] Michon | The dynamic interest in topics within the biomedical scientific community[END_REF]. However, most of heuristic algorithms are proposed for partition detection, whose results are disjoint communities. We devote this chapter to the detection of overlapping community structure. Diverse methods have been proposed to detect overlapping community structure. However, the problem remains. For example, Palla et al. [START_REF] Palla | Uncovering the overlapping community structure of complex networks in nature and society[END_REF] have proposed the clique percolation method (CPM) to detect overlapping communities. This method is based on clique percolation: a k-clique (a complete subgraph of k nodes) is rolled over the network through other cliques with k -1 common nodes. In this way a set of nodes can be reached, which is identified as a community. One node can participate in more than one community, therefore overlaps naturally occur. The method, however, is not suitable for non-trivial networks, such as WikiTalk which is a sparse network consisting of star-like communities.

In order to provide the exhaustive information about overlapping community structure of a graph, we introduce a novel quality function to measure the quality of the overlapping community structure. This quality function is derived from the Hamiltonian and explains the quality of community structure through the energy of spin system.

In this chapter, we propose two different methods to detect overlapping nodes based on partitions. We can obtain overlapping community structure by adding these overlapping nodes to their related communities. Our first method is called clique optimization. Clique optimization aims at detecting granular overlaps. The clique optimization method is a fine grain scale approach. Each granular overlap is a node connected to distinct communities and it is highly connected to each community. Roughly speaking, a granular overlap is shared by several distinct communities while being intrinsically a member of each of them. The second method is named fuzzy detection. Fuzzy detection is at a coarser grain scale and aims at identifying modular overlaps. Modular overlaps represent groups of nodes that have high community membership degrees with several communities. A modular overlap is itself a possible cluster/sub-community. As opposed to granular overlaps, modular overlaps imply the hierarchical organization of the graph: modular overlaps are sub-communities shared by several communities. The obtained results of the two methods are different. Since the two methods offer a different granularity scale (fine and coarse), they are complementary and meaningful in characterizing overlapping nodes.

The outline of this chapter is as follows. Section 2.1 introduces current work in cover detection. In Section 2.2, we describe our novel extension of modularity. In Section 2.3 and Section 2.4, we present clique optimization and fuzzy detection in details. We also show their performances when analyzing a real network in Section 2.5. In Section 2.6, we discuss our methods and give a brief conclusion in Section 2.7.

Related work on cover detection

In the following, we present a class of network clustering algorithms which allow nodes to belong to more than one community.

Baumes et al. [START_REF] Baumes | Efficient identification of overlapping communities[END_REF] proposed a density metric for clustering nodes. In their method, nodes are added into clusters if and only if their fusion improves the cluster density. Under this condition, the results really depend on the initial seeds. Seeds can be a random node or disjoint communities. As shown in their results, there is a huge variation in the number of communities regarding the type of seed used.

Lancichinetti et al. has made efforts in cover detection including fitness-based function [START_REF] Lancichinetti | Detecting the overlapping and hierarchical community structure in complex networks[END_REF] and OSLOM (Order Statistics Local Optimization Method) [START_REF] Lancichinetti | Finding statistically significant communities in networks[END_REF]. The former is based on the local optimization of a k-fitness function, whose drawback is to introduce the tunable parameter k. The later uses the statistical significance [START_REF] Lancichinetti | Statistical significance of communities in networks[END_REF] of clusters wich induces an expansive computational cost as it sweeps all nodes for each "worst" node. For the optimization, Lancichinetti et al. [START_REF] Lancichinetti | Finding statistically significant communities in networks[END_REF] propose to detect significant communities based on a partition. They detect a community by adding nodes, between which the togetherness is high. This is one of the popular techniques for overlapping community detection. There have similar endeavors like greedy clique expansion technique [START_REF] Lee | Detecting highly overlapping community structure by greedy clique expansion[END_REF] and community strength-based overlapping community detection [START_REF] Wang | Adjusting from disjoint to overlapping community detection of complex networks[END_REF]. However, as all approaches applied Lancichinetti et al.'s k-fitness function, the results are limited by the tunable parameter k.

Some cover detection approaches are based on different basis. For example, Reichardt et al. [START_REF] Reichardt | Statistical mechanics of community detection[END_REF] introduced the energy landscape survey method, and Sales Pardo et al. [START_REF] Sales-Pardo | Extracting the hierarchical organization of complex systems[END_REF] proposed the modularity-landscape survey method to construct a hierarchical tree. They aim at detecting fuzzy community structure, whose communities consist of nodes having high probability to belong to the same group. As noticed in [START_REF] Sales-Pardo | Extracting the hierarchical organization of complex systems[END_REF], they are mainly limited by a scalability factor in terms of network size.

Evans et al. [START_REF] Evans | Line graphs, link partitions, and overlapping communities[END_REF] proposed to construct the line graph of the original network which transforms the problem of node clustering into the problem of link clustering. It allows nodes to be shared by several communities. The main drawback is that, in their results, whatever the network, overlapping communities always exist.

Modified modularity for covers 2.2.1 A novel modularity

Modularity has been employed by a large number of community detection methods. However, it only evaluates the quality of partitions. Here, we introduce a novel extension for covers, which is combined with the Hamiltonian. Many scientists deal with the problems in the area of computer science based on principles from statistical mechanics or analogies with physical models. When using spin models for clustering of multivariate data, the similarity measures are translated into coupling strengths and either dynamical properties such as spin-spin correlations are measured or energies are interpreted as quality functions. A ferromagnetic Potts model has been applied successfully by Blatt et al. [START_REF] Pu | Up-to-date catalogues of yeast protein complexes[END_REF]. Bengtsson and Roivainen [START_REF] Bengtsson | Using the potts glass for solving the clustering problem[END_REF] have used an antiferromagnetic Potts model with the number of clusters as input parameter and the assignment of spins in the ground state of the system defines the clustering solution. These works have motivated Reichardt and Bornholdt [START_REF] Reichardt | Statistical mechanics of community detection[END_REF] to interpret the modularity of the community structure by an energy function of the spin glass with the spin states. The energy of the spin system is equivalent to the quality function of the clustering with the spins states being the community indices.

Let a community structure be represented by a spin configuration {σ} associated to each node u of a graph G. Each spin state represents a community, and the number of spin states represents the number of communities of the graph. The quality of a community structure can thus be represented through the energy of spin glass. In [START_REF] Reichardt | Statistical mechanics of community detection[END_REF], a function of community structure is proposed to 1. reward within-community links (internal links), 2. penalize within-community missing links (internal non-links), 3. reward non-links between different communities (external non-links), and

penalize existing links between different communities (external links).

Its expression is written as:

H({σ}) = - � i� =j a ij A ij δ(σ i , σ j ) � �� � internal links + � i� =j b ij (1 -A ij )δ(σ i , σ j ) � �� � internal non-links + � i� =j c ij A ij (1 -δ(σ i , σ j )) � �� � external links - � i� =j d ij (1 -A ij )(1 -δ(σ i , σ j )) � �� � external non-links
where σ i denotes the spin state (or community index) of node i, and a ij , b ij , c ij , d ij denote the weights of different contributions, respectively. The Kronecker delta symbol δ(σ i , σ j ) yields 1 if and only if σ i = σ j and 0 otherwise. Let the weights on existing links be equal, i.e., a ij = c ij . (Similarly for non-links, we have b ij = d ij ). Then, only internal links and non-internal links are considered. A convenient choice to balance the importance of internal links and non-internal links is

a ij = 1 -γp ij and b ij = γp ij ,
where γ is a parameter and p ij denotes the probability of a link existing between nodes i and j, normalized such that � i� =j p ij = 2m. A further simplified Hamiltonian for measuring the quality of a community structure, is written as:

H({σ}) = - � i� =j (A ij -γp ij ) δ(σ i , σ j ) (2.1)
We also can write the function (Eq. 2.1) in the following two ways:

H({σ}) = - � s (m ss -γ[m ss ] p ij ) = - � s c s (2.2)
and 2. when n r is an union cluster composed of n 1 and n

H({σ}) = � s<r (m sr -γ[m sr ] p ij ) = � s a sr (2.
] p ij + [m 2s ] p ij = [m 1+2,s ] p ij ; n1 n2 (a) n1 ∩ n2 = ∅ n2 n1 n0 (b) n01 ∩ n02 = n0 n2 n1 nr ns (c) nrs1 ∩ nrs2 = nr ∪ ns
2 , [m rr ] p ij = [m 11 ] p ij + [m 22 ] p ij + [m 12 ] p ij .
Similarly, we give a relation for the cohesion of a community n 3 (the whole graph) and two sub-communities n 1 and n 2 with an empty intersection such as n 1 ∪ n 2 = n 3 and n 1 ∩ n 2 = ∅ (See Fig. 2.2 (a)). From Eq. 2.2 and Eq. 2.3, we can easily prove:

c 3 = c 1 + c 2 + a 12 (2.4)
where c 3 denotes the cohesion of n 3 that is the union of n 1 and n 2 with an empty intersection, a 12 denotes the adhesion between n 1 and n 2 , c 1 and c 2 are the cohesions of sub-communities n 1 and n 2 respectively. Furthermore, we can give the relations for the cohesion of n 3 and two sub-communities n 1 and n 2 in other cases (See Fig. 2.2).

In the subdivision (See Fig. 2.2 (b)), there is an overlapping cluster n 0 between n 01 and n 02 . We write the cohesions for sub-communities n 01 and n 02 as:

� c 0 01 = c 0 0 + c 1 + a 0 01 c 0 02 = c 0 0 + c 2 + a 0 02 ,
where c 0 01 and c 0 02 denote the cohesion of the sub-communities n 01 and n 02 respectively, a 0 01 and a 0 02 denote the adhesion between n 0 and n 1 , n 2 . Here, n 0 is shared by n 01 and n 02 .

For the adhesion, we have:

a 0 01,02 = a 0 01 + a 0 02 + a 12
between n 01 and n 02 .

For the union of n 3 = n 01 ∪ n 02 , we obtain

c 3 = c 0 + c 1 + c 2 + a 01 + a 02 + a 12 = 2c 0 0 + c 1 + c 2 + 2a 0 01 + 2a 0 02 + a 12 .
So we derive

c 0 0 = 1 2 c 0 , a 0 01 = 1 2
a 01 and a 0 02 = 1 2 a 02 .

(2.5)

In the subdivision (See Fig. 2.2 (c)) such as n r ∪ n s = n 0 , we replace c 0 and c 0 0 by

� c 0 = c r + c s + a rs c 0 0 = c r r + c s s + a rs rs , (2.6)
where c r r and c s s denote the cohesion of overlapping sub-communities n r and n s respectively. a rs rs denotes the adhesion between overlapping sub-communities n r and n s , which satisfies a rs rs = 1 2 a rs due to Eq. 2.5. Therefore, we propose the contribution of a rs for all communities {C 1 , . . . , C k }:

k � 1 1 |d r ∪ d s | a rs = |d r ∩ d s | |d r ∪ d s | a rs , (2.7)
where d r and d s denote the community memberships of n r and n s , respectively. With the Hamiltonian (Eq. 2.1), we rewrite the modularity Q 1.2 as:

Q = - 1 m H({σ}) . (2.8)
Consequently, we can write the quality of an overlapping community structure in the form of the modularity function:

Q ov = 1 2m � i� =j � A ij - k i k j 2m � |d i ∩ d j | |d i ∪ d j | , (2.9)
where d i and d j are memberships of nodes i and j, respectively. For a pair of nodes i and j always belonging to the same community such as d i ∩d j = d i ∪d j , their contribution to the modularity is

� A ij - k i k j 2m
� . For a pair of nodes i and j never belonging to the same community such as d i ∩ d j = ∅, their contribution is 0. Otherwise, their contribution is within the range of

� 0, � A ij - k i k j 2m � �
. Furthermore, if the found community structure is a strict partition, its quality Q ov is equal to the initial modularity Q defined by the Equation 1.2.

Existing modularity for covers

There are other extensions of modularity designed to evaluate the quality of overlapping community structure. However, we are going to prove that they fail to satisfy above necessary constraints.

In the case Fig. 2.2 (c), we assume that n r is an overlapping node v i . Similarly for n s , n s is an another overlapping node v j which connects to v i . The union of v i and v j is n 0 such that n 0 = v i ∪ v j . The overlapping communities n 01 and n 02 are denoted by C x and C y of a graph G example , respectively.

Let O v be the number of communities to which node v belongs. Shen et al. [START_REF] Shen | Quantifying and identifying the overlapping community structure in networks[END_REF] have introduced an extended modularity:

Q shen = 1 2m nc � i=1 � v∈C i ,w∈C j ,v� =w 1 O v O w � A vw - k v k w 2m � δ(σ v , σ w ) (2.10)
From Eq. 2.8, it is easy to obtain a 0 01 shen derived from Q shen (Eq. 2.10):

a 0 01 shen = 1 2 � v∈n 0 ,w∈Cx\n 0 � A vw - k v k w 2m � + 1 2 � A v i v j - k v i k v j 2m �
It fails to satisfy a 0 01 = 1 2 a 0 (Eq. 2.5), where

a 01 shen = � v∈n 0 ,w∈Cx\n 0 � A vw - k v k w 2m � + 2 � A v i v j - k v i k v j 2m �
In other words, through the definition of Q shen , we obtain different values of the quality in views of Fig. 2.2 (b) and Fig. 2.2 (c) although they represent the same cover.

In [START_REF] Nepusz | Fuzzy communities and the concept of bridgeness in complex networks[END_REF], Tamas Nepusz et al. haved proposed a variant of modularity measure, which is defined by:

Q fuzzy = 1 2m � i,j � A ij - k i k j 2m � s ij
where s ij = � nc k=1 u ki u kj . The membership degree between node i and community k, u ki satisfies � nc k=1 u ik = 1. As we did previously, for node v k ∈ n 0 in G example , under the assumption:

u v i Cx = u v i Cy = u v j Cx = u v j Cy = 1
2 , it is easy to obtain

s v k vw =      0 v w / ∈ C x ∪ C y , 0.5 v w ∈ C x ∪ C y , v w / ∈ n 0 , 0.25 v k � = v w (2.11)
We obtain that

a 0 01 fuzzy = 1 2 � v∈n 0 ,w∈Cx\n 0 � A vw - k v k w 2m � + 1 2 � A v i v j - k v i k v j 2m
� It also does not satisfy a 0 01 = 1 2 a 0 (Eq. 2.5) with a 01 fuzzy = a 01 shen . By using the novel proposed modified modularity (Eq. 2.9), we obtain

a 0 01ov = 1 2 � v∈n 0 ,w∈Cx\n 0 � A vw - k v k w 2m � + � A v i v j - k v i k v j 2m � .
It satisfies a 0 01 = 1 2 a 0 (Eq. 2.5), therefore we consider that our novel modified modularity is more reasonable to evaluate the quality of overlapping community structure. However, we can not detect covers by optimizing it since overlapping nodes may degenerate the modularity value. For example, in the case Fig. 2.2 (b), the quality can be represented by

Q cover ov = - 1 m H({σ}) = - 1 m � c 0 + c 1 + c 2 + a 0 01 + a 0 02 �
where a 0 01 = 1 2 a 01 and a 0 02 = 1 2 a 02 . And the quality of the partition is

Q partition ov =      - 1 m (c 0 + c 1 + c 2 + a 01 ) ,when P = {n 01 , n 2 } - 1 m (c 0 + c 1 + c 2 + a 02 ) ,when P = {n 1 , n 02 } We find Q cover ov = Q partition ov when a 01 = a 02 ; otherwise, Q cover ov < Q partition ov
due to min(a 01 , a 02 ) < a 0 01 + a 0 02 = 1 2 a 01 + 1 2 a 02 < max(a 01 , a 02 ). Thus, even in a toy example where clearly there is a clear overlap (See Fig 2 .2 (b)), if the number of links between n 0 et n 1 differs from the number of links between n 0 et n 2 the quality of the cover will be less than the quality of the partition once the difference between the number of links is greater than 0.

To overcome this optimization issue, we propose two methods not based on modularity like function. One is called clique optimization for detecting granular overlaps, and the other is named fuzzy detection aiming at identifying modular overlaps. Although granular overlaps and modular overlaps are used to denote overlapping nodes shared by several communities, they are intrinsically different. Granular overlaps represent nodes that have high togetherness with distinct communities while modular overlaps denote sub-communities shared by several communities. Therefore, given a pair of communities, we may observe several modular overlaps shared by them, while there are only one group of granular overlaps.

Communities are groups of nodes which probably share common properties. For instance, communities are groups of proteins participating a specific function in proteinprotein interaction networks; communities are groups of pages dealing with the same or related topics in the World Wide Web; communities are groups of customers with similar interests in the network of purchase relationships between customers and products of online retailers (e.g., www.amazon.com). Communities may overlap, i.e., distinct communities share many nodes. These overlapping nodes reveal the relationships between communities. Detecting these overlapping nodes and characterizing them can help us to more understand communities.

One method to detect overlapping nodes is through cover detection, i.e., communities in covers share overlapping nodes. Of course, we can detect covers by overlapping node detection, i.e., only overlapping nodes are shared by several communities. Therefore, we propose the following methods to detect covers. Both them are composed of two phases: in the first phase, we detect overlapping nodes based on a partition, i.e., the found overlapping nodes have strong connection or strong membership degree (how strong the nodes belong to the communities.); and in the second phase, we add these overlapping nodes to their related communities. Both phases are based on the same partition. Consequently, we obtain covers and become able to characterize overlapping nodes.

Clique optimization

The definition of community is not standard. There are different definitions, which depend on the context such as global definition, local definition and the community based on node similarity (See Section 1.1.1). Although communities are detected based on any of above definitions, the most commonly used one for overlapping community detection is that communities are clique-like objects. Given a clique, each member has connections with all other members. They are supposed to share common interests. The applications which detect clique-like communities like CPM [START_REF] Palla | Uncovering the overlapping community structure of complex networks in nature and society[END_REF], SCP [START_REF] Kumpula | A sequential algorithm for fast clique percolation[END_REF] on social networks have good performance. Based on these observations, we propose to detect covers based on cliques.

Our proposed definition

On the graph example shown on Figure 2.3, its community structure is a cover composed of two k-cliques. By applying a partition detection method (a modularity optimization algorithm such as the Louvain algorithm), we obtain two different partitions with the same high modularity (See Fig. 2.3). We observe that overlapping nodes are separated by disjoint community boundaries. This observation motivates us to detect overlapping nodes through cliques, which are separated by disjoint community boundaries.

CPM [START_REF] Palla | Uncovering the overlapping community structure of complex networks in nature and society[END_REF] is one popular method for cover detection. It is designed to uncover the community structure composed of k-clique-communities. A k-clique-community is the union of all k-cliques that can be reached from each other through a series of adjacent k-cliques. Two k-cliques are said to be adjacent if they share k -1 nodes. A k-clique template is a clique-like object. It is placed onto any k-clique of the network, and rolled to an adjacent k-clique by relocating one of its nodes and keeping its other k -1 nodes fixed. In CPM, each k-clique-community of a graph is a subgraph that can be fully explored by rolling a k-clique template on them. Each k-clique template is maximal for the 'rolling' process: there does not exist any other k-clique k -1 adjacent to the k-clique template. Through the definition of k-clique-community, each k-clique can be assigned to the community that contains its one adjacent k-clique.

Similarly, for each disjoint community of a partition, we propose to apply the kclique adjacency rolling process on them. A clique is adjacent to a community if and only if both share k -1 common nodes. If a disjoint community can be rolled to an adjacent k-clique, all members of this k-clique can be assigned to this community. If a node can be assigned into more than one community, it is a granular overlapping node.

In the following, we give the definition of granular overlapping nodes in two senses:

Definition 3. A node v is a k-granular overlapping node shared by � communities E = {C 1 , . . . , C � } in a strong sense if it belongs to a clique K adjacent to these communities, that is: ∀C i ∈ E, |K ∩ C i | ≥ k -1. Definition 4. A node v is a k-granular overlapping node shared by � communities E = {C 1 , . . . , C � } in a weak sense if it is involved in � � cliques K = {K 1 , . . . , K � � } which are adjacent to them, that is: ∀C i ∈ E, ∃K j ∈ K such that |K j ∩ C i | ≥ k -1.
Remark: Clearly an overlapping node in the strong sense is also an overlapping node in the weak sense, whereas the converse is not true.

Algorithm 2 A k-clique detection Input: e = (i ini , j ini ), N ini ij , k Output: K a set of nodes describing a k-clique 1: N ← N ini ij , κ ← k -2, K ← {i, j} 2: while κ > 0 do 3: if κ = 1 then 4: Add a node v ∈ N to K: K ← K ∪ v 5: κ ← κ -1 6: else 7:
Add a pair of connected nodes {i pic , j pic } ⊆ N to K: K ← K ∪ {i pic , j pic } 8: Find a clique K j , which is k-adjacent to at least one community 5:

N ← N ∩ N pic
Find all communities E j = {C 1 , . . . , C � } k-adjacent to K j : ∀C i ∈ E j , |K j ∩C i | ≥ k-1 // STEP 2: Update overlapping communities 6:
for all k-adjacent communities C i ∈ E j do 7:

Merge K j to C i :S i ← S i ∪ K j 8:
end for 9: end for 10: Return S

The clique optimization algorithm

Our clique optimization is proposed to detect k-granular overlapping nodes for cover detection. This algorithm consists of two phases: based on a partition, the first phase is to detect cliques which are k-adjacent to communities; the second phase is merging the above detected cliques into communities. The algorithm is sketched in Algo. 3. We describe it in details below.

After obtaining a partition by running an efficient partition detection algorithm (such as the Louvain algorithm) on the graph (line 1), we start our first phase.

In order to detect cliques, we use a k-clique detection algorithm (Algo. 2). It starts by one edge e = (i ini , j ini ). Then this algorithm proceeds by collecting all nodes that are neighbors of both nodes N ini ij = N i ini ∪ N j ini , where N denotes neighborhood. Now, when the edge e = (i ini , j ini ) is added, each k -2-clique contained in the set N (N is initialized by N ini ij ) will give rise to a new k-clique (lines 2 -11 in Algo. 2). Therefore, all newly formed k-cliques are found by detecting all the k -2-cliques in the N , where N is iteratively updated through the selected edges (i pic , j pic ). For commonly used small clique sizes, this is very fast: for 3-cliques, k -2-clique is a single node, while for k = 4, all connected pairs of nodes in N give rise to a new 4-clique.

We define a node to be a granular overlapping node candidate if its external degree is at least k -1. In the first phase (line 3 -9), we detect all cliques which are k-adjacent to communities. A simple resolution is based on edges connecting one granular overlapping node candidate to detect a clique which is k-adjacent to at least one community. Chosen a granular overlapping node candidate, when a k -1-clique whose k -1 nodes belong to the same community is found from N (N is initialized by the neighbourhood of the chosen granular overlapping node candidate), we find another k-1 clique whose members belong to another community from the current N . The final clique is k-adjacent to at least one community.

Next, we merge this clique to communities in the second phase (line 6 -8). For each clique which shares sets of k -1 nodes with one community, we merge them. If this clique shares sets of k -1 nodes with several communities, we merge this clique into several communities. Finally, we obtain a cover where granular overlapping nodes are shared by overlapping communities.

In general, we detect granular overlapping nodes in a weak sense by setting k = 4, where 4-clique is the smallest cluster larger than a triangle. However, if more than half of nodes are identified as granular overlapping nodes in a weak sense by using k = 4, we restrict the definition such that the number of granular overlapping nodes should be less than half of the nodes in the graph.

The granular overlapping nodes in the strong sense can be used to characterize community overlaps when we observe many communities sharing a large number of granular overlapping nodes in a network. In this case, we use granular overlapping nodes in the strong sense to characterize community overlaps for the following reasons: a) granular overlapping nodes in the strong sense are granular overlapping nodes in the weak sense and b) the number of nodes sharing the same common interest with a granular overlapping node in the strong sense is larger than in the weak sense.

Since granular overlapping nodes in the strong sense are granular overlapping nodes in the weak sense, the obtained characteristics through granular overlapping nodes in the strong sense should be shared by granular overlapping nodes in the weak sense. When the number of overlapping nodes between communities is large enough (e.g., more than 100), these overlapping nodes can be considered as a large community for the characterization 1 . Therefore, we expect to identify the common interest shared by these overlapping nodes. Although the weak overlapping nodes have dense connections between several communities, the number of nodes sharing the same common interest with a granular overlapping node in the strong sense is more than in the weak sense. For instance, the maximal clique containing one weak granular overlapping nodes may have k members. In other words, only k -1 nodes share the common interest with this weak granular overlapping node. However, for a strong granular overlapping node, at least 2k -2 nodes share the common interest.

The worst-case complexity of clique optimization is in O(n k k 2 ): there are O(n k ) subgraphs to check, each of which has O(k 2 ) edges, where n represents the number of nodes whose external degree is at least 1. Note than n is the size of the community given by the partition algorithm and one may expect that n is smaller than the total number of nodes in the graph. Our method is faster than CPM [START_REF] Palla | Uncovering the overlapping community structure of complex networks in nature and society[END_REF] or SCP [START_REF] Kumpula | A sequential algorithm for fast clique percolation[END_REF], since it only detects cliques separated by community boundaries.

Remark on directed graph: From the definitions given above, our clique optimization is defined for undirected and unweighted graphs. When analyzing an arbitrary system, one could decide that the directionality of the links could be ignored if it makes sense. If u → v means that the entity u is in interaction with the entity v, we may want to infer that v → u remains valid, yielding u ↔ v.

Remark on weighted graphs: If connections are weighted, a threshold weight ω * is used to prune weak links and keep those that are stronger than ω * . Depending on the weight distribution, the threshold could be ω

* = 1 2m � n v=1 k v ,
where k v is the weighted degree of node v. If we want to keep all links, ω * is simply set to zero. If the threshold weight is increased, the number of edges is decreased and so is the number of overlapping nodes. Note that, if ω * is increased, the granular overlapping nodes should have stronger links to their related communities.

Benchmark graphs

We are now going to test the performances of clique optimization. We have considered a set of synthetic networks and a real network for which the community structure is known. We show the accuracy of our method through the normalized mutual information (NMI) [START_REF] Lancichinetti | Detecting the overlapping and hierarchical community structure in complex networks[END_REF] by comparing the computed covers to a ground truth. The higher the variation of information is, the more similar two covers are. If two covers are identical, NMI is 1. The results obtained by our clique optimization on the following benchmark graphs are good and presented bellow.

Synthetic networks

In Fig. 2.4, we present the comparison between our clique optimization heuristic and other cover detection algorithms including CPM [START_REF] Palla | Uncovering the overlapping community structure of complex networks in nature and society[END_REF], COPRA [START_REF] Gregory | Finding overlapping communities in networks by label propagation[END_REF] and OSLOM [START_REF] Lancichinetti | Finding statistically significant communities in networks[END_REF]. Figure 2.4 presents the NMI of the results of all selected algorithms applied to LFR benchmarks [START_REF] Lancichinetti | Statistical significance of communities in networks[END_REF]. LFR benchmarks are constructed by using a series of parameters: N the number of nodes, k the average degree, max k the maximum degree, number of overlapping nodes on, the number of overlapping community memberships om and a mixing parameter µ. The mixing parameter µ is the ratio of intra-community to intercommunity connections. For each overlapping node u shared by ν u communities, if it belongs to community ξ, its adjacent links to ξ satisfies: k ξ u = k in u /ν u . As we can see, clique optimization performs near perfectly for small µ and small portion of overlapping nodes on/N : the NMI obtained if roughly greater than 0.9 when µ < 0.5. It outperforms all other heuristic when µ ≤ 0.3 and has only a lower NMI than OSLOM when µ > 0.3. Such case could be early explain since OSLOM only detects significant communities. A significant community is a group of nodes having a larger density of internal connections than of external links. If a node can not improve any community's significance (the difference between the internal connection density and external connection density), it is defined as an individual node and it is not considered in the community structure which changes the rules of the comparison. [START_REF] Palla | Uncovering the overlapping community structure of complex networks in nature and society[END_REF], CORPA [START_REF] Gregory | Finding overlapping communities in networks by label propagation[END_REF] and OSLOM [START_REF] Gregory | Finding overlapping communities in networks by label propagation[END_REF]. Here, x-axis denotes the varying mixing parameter µ and y-axis represents the average NMI of 50 samples by comparing the found community structure and the ground truth. Besides the number of nodes N , the number of overlapping nodes on and the tunable parameter µ, the other parameters are identical: average degree k = 20, maximum degree max k = 300, minus exponent for the degree sequence t 1 = 2, minus exponent for the community size distribution t 2 = 1, minimum community sizes min c = 10, maximum for community max c = 300, and number of memberships of overlapping nodes om = 2.

Yeast protein complexes

To perform further tests, we consider yeast protein complexes data base (See Fig 2 .5). The combined-AP/MS network2 describes 9070 interactions among 1622 proteins. In order to compare the results to a ground truth, we use a catalogue of protein complexes provided by CYC2008 [START_REF] Pu | Up-to-date catalogues of yeast protein complexes[END_REF]. All results are shown in Tab. 2.1. We see that clique optimization identifies protein complexes with a high degree of success. By comparing to other overlapping detection techniques, it provides the highest NMI [START_REF] Lancichinetti | Detecting the overlapping and hierarchical community structure in complex networks[END_REF]. Remind that NMI measures the similarity between the results and the ground truth. We also provide additional measures: sensitivity, specificity, accuracy and modularity. Sensitivity is related to the ability to identify the real overlapping nodes, which is the proportion of real overlapping nodes among the found overlapping nodes. The low sensitivity of clique optimization is caused by our definition of k-granular overlapping nodes, i.e., not all real overlapping nodes participate in k-cliques. Specificity is related to the ability to identify non-overlapping nodes, which is the proportion of nonoverlapping nodes among all found non-overlapping nodes. The accuracy is a "balanced accuracy", which is the sum of sensitivity and specificity. The accuracy focuses on the capacity of detecting overlapping nodes. One can observe that our clique optimization heuristic offers the highest accuracy score.

Fuzzy detection

In this section, we will introduce another method for cover detection named fuzzy detection. This novel cover detection heuristic aims at identifying modular overlaps. Modular overlaps are groups of nodes shared by communities. As mentioned above, there is a difference between granular overlaps introduced in the previous section and modular overlaps. Modular overlaps are related to the hierarchy organization. That is, modular overlaps are sub-communities shared by several communities.

Motivation

Our fuzzy detection algorithm is based on the Louvain algorithm [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF]. The Louvain algorithm is an efficient partition detection algorithm that provides good partitions with high modularity. It consists of two phases that are iteratively repeated until no more positive gain of modularity is obtained. Initially, all nodes are assigned into a single community. Then, for each node whose move improves the modularity, it will be removed from its current community to the neighbor community which offers the largest gain of modularity. The first phase repeatedly and sequentially sweeps all nodes until no further improvement of modularity can be gained. The second phase builds a new meta graph based on communities found in the first phase. It aggregates nodes of the same community and builds a new network whose nodes are the communities. Once the second phase is completed, the first phase is reapplied to the new network. The two phases are iteratively applied until no more change in community structure or maximum modularity is achieved. In the following, we use iteration to denote the combination of these two phases. The partition found by this algorithm is hierarchical organized, the hierarchy height is determined by the number of iterations. The Louvain algorithm is extremely fast and provides highly optimized partitions with high modularity.

When running several times the Louvain algorithm on the same given network, we observe from a run to another that nodes may be grouped together with different community members in distinct partitions. Since the Louvain algorithm sweeps nodes in a non deterministic fashion (a random permutation of V ), it naturally introduces instability which may be a weakness. It turns out that we can take benefit of this instability. By detecting nodes that jump from one community to another between distinct runs, we are in fact able to uncover nodes that have high community memberships with distinct communities. Such "oscillating" nodes can be considered as overlapping nodes. Therefore, we propose a fuzzy detection algorithm which detects groups of nodes having strong connection probability with several communities.

Fuzzy detection algorithm

To have the benefit of the potential Louvain algorithm instability [START_REF] Aynaud | Détection de communautés dans les réseaux dynamiques[END_REF], we force the algorithm to use a random seed at each run. The random seed makes the nodes be swept in a random permutation during the modularity optimization. Thus, different runs may produces different partitions. By repeating Louvain algorithm, we are able to compute, a Algorithm 4 Louvain algorithm.

Input: G = (V, E), l * a level threshold Output: P a partition

1: l ← 0; G 0 ← G 2: repeat 3: l ← l + 1 4:
Initialize a partition P l of G l (V l , E l ) // First phase: partition update 5:

repeat 6:
Nodes in a random permutation

7:
for all Nodes: v ∈ V l do 8:

Move from σ v to one selected σ v � (v � is a neighbour of v) Replace each community by a node

12:

Replace connections between a pair of communities by one weighted edge 13: until P l is not updated or l = l * . 14: Return P corresponding to the roots of the hierarchical tree. if modularity of P greater than modularity max then 7:

Save the partition P in P opt and update modularity max 8:

end if 9: until �P k -P k-1 � ≤ � 10: P sc = P opt 11: for all edge e = (i, j) such that p ij < α * do 12:

Remove the external edge e from P sc 13: end for // STEP 2: Adjust the membership of robust clusters Input: G = (V, E), P sc , S ← P opt 14: for all C i ∈ P opt do 15:

Identify community core: � c i = arg max c j ⊆C i |c j | 16: end for 17: Compute P c i ,c j 18: for all c j ∈ P sc and c j / ∈ {� c 1 , . . . , } do 19:

if p c j ,� c i ≥ β * then 20:

S i ← S i ∪ c j 21:
end if 22: end for 23: Return S co-appearance matrix P = [p ij ] n×n . For each pair of nodes (i, j), p ij of P represents the probability for the pair nodes i and j to appear in the same community. Having p ij = 1 implies that nodes i and j are always in the same community while edges e = (i, j) having a p ij close to 0 implies that edge e connects two different communities. The underlying idea of fuzzy detection approach is thus to detect overlapping communities from a classical partition approach.

Detecting overlapping nodes also allows to detect more stable nodes that always belong together in the same community. In this algorithm, we use the notion of community cores to denote communities. Given a community, its core is a group of nodes offering high stability against random perturbation. To detect community cores, we're going to remove edges in order to keep only core nodes. First we remove all external edges, i.e., all edges e = (i, j), having a connection probability p ij less than a threshold α * . After this pruning phase, a set of disjoint robust cluster is obtained. A robust cluster is a group of nodes connected by edges having in-cluster probability larger than or equal to α * . Note that a given community may have several robust clusters. We choose the community core corresponding to the robust cluster having the maximum size. The notion of external edges was used in [START_REF] Gfeller | Finding instabilities in the community structure of complex networks[END_REF] where authors add a random noise over the weight of the edges of the network (equally distributed between [-σ, σ]). Once community cores are identified, we continue iteratively, following the Louvain approach. Similarly, in our method, we replace the robust clusters by supernodes and connect them through the connection between robust clusters. In this case, the weight of the edge between the supernodes is the sum of the weights of the edges between the identified robust clusters. We run again the Louvain algorithm to compute the probability of robust clusters and community cores to appear in the same community. Finally, we add each robust cluster to the community if they have a high community membership degree such as their probability of appearing in the same community is high. The global algorithm is shown in Algo. 5. First, (lines 2 -9) we compute the coappearance matrix P = [p ij ] n×n by running the Louvain algorithm of Algo. 4 several times with a random seed 3 . The number of runs is determined by the convergence criteria (line 9):

�P k+1 -P k � = � � � � 1 m � (i,j)∈E (p k+1 ij -p k ij ) 2 < ε, (2.12)
where P k represents the result after k-th run and p k ij denotes the statistical probability of nodes i and j to belong to the same community after k-th runs (line 5) and ε is a 3 Louvain algorithm is a hierarchical clustering algorithm. It iteratively merges small clusters to maximize modularity. Therefore, it provides a hierarchical tree (or dendrogram) to illustrate the hierarchical form of organization. If the level parameter is not set, Louvain algorithm gives the partition corresponding to the largest value of the modularity; otherwise, this algorithm returns the partition corresponding to the roots, that is the partition obtained in the last iteration. small threshold. Figure 2.6 illustrates the convergence of the norm when running fuzzy detection algorithm. We observe that �P k+1 -P k � decreases as the number k of runs increases.

Then, we detect robust clusters {c 1 , c 2 , . . . , c s } = P sc (lines 10 -13). Given a partition P opt which has the maximum modularity among all computed partitions obtained during the first phase, the robust clusters are detected by removing all edges having a probability p ij lower that a given threshold α * (typically α * = 0.9). A simple illustration is given in Fig. 2.7.

Finally in the second phase, we identify modular overlaps which have high community memberships with several communities. Given a community C i ∈ P opt , its core � c i is the robust cluster c j ⊆ C i having the maximum size, such as:

� c i = arg max c j ⊆C i |c j | (2.13)
We assign each robust cluster c j to the community C i if and only if their community membership p c j ,� c i is larger than a threshold β * such as p c j ,� c i > β * (typically β * = 0.1). If one robust cluster is assigned to at least two communities, we call it a modular overlaps. Given a modular overlaps, its members are possible granular overlapping nodes. Only the granular overlapping node are required to have dense connection with related communities. The nodes shared by the same modular overlaps are not only required to have dense connection with related communities and also are required to have high internal modular degree (the number of links connected to other members within the robust cluster).

Fine tunning:

In cases where a community consists of several robuster clusters of comparable size, one may tune and increase the value of α * in order to refine the core identification.

Since fuzzy detection is used to identify modular overlaps, which are sub-communities shared by several communities, we restrict the modular overlaps to have a size greater than 3. We can now introduce the notion of unstable nodes, which are nodes connecting communities with few links but are observed to have high co-appearance probability with several communities. The Fig. 2.8 illustrates such case. Due to unstable nodes, we do not use fuzzy detection to identify granular overlaps. As shown in Tab. 2.1, the results of fuzzy detection may be degenerated by unstable nodes. Moreover, the method suffers from the classical resolution limit of modularity optimization [START_REF] Fortunato | Resolution limit in community detection[END_REF]. Indeed, due to this resolution limit, two weakly connected communities may possibly be grouped together if their merge improves the modularity during modularity optimization phase. Therefore, we may observe some modular overlaps that are not real overlapping nodes but are the results of modularity optimization. We call them unstable clusters.

The running time of fuzzy detection mainly depends on the co-appearance matrix calculation. The complexity to find a partition by the Louvain algorithm is estimated by authors in [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF] to be in O(m), where m is the number of edges in the network (the worst complexity is much higher, but in practice, on real network, Louvain algorithm performs very well). Thus the computational complexity of fuzzy detection is in O(Km), where

���� ���� 1 � � � � � � � � � ���� ���� 9 � � � � � � � � � ���� ���� 2 � � � � � � � � � � � � � � � � � � ���� ���� 4 0.5 ���� ���� 5 0.5 ���� ���� 6 � � � � � � � � � � � � � � � � � � ���� ���� 8 ���� ���� 3 � � � � � � � � � ���� ���� 7 � � � � � � � � �
Figure 2.8: An example graph that contains a unstable node 5. Node 5 has a relatively high membership degrees with two communities (p = 0.5). However, it is connected to each community with only 1 link.

K is the number of runs of Louvain algorithm needed before reaching an acceptable convergence of P. Once more, in practice, we take benefit of the efficient Louvain algorithm running time and our fuzzy detection is fast. We experiment storage limitation due to the matrices P k and P k+1 more that time computing one.

Benchmark graphs

In the following, we test the performances of fuzzy detection. We have considered a set of synthetic networks and a real network for which the community structure is known. The results show that our fuzzy detection algorithm extracts communities while preserving the hierarchical organization and also providing overlaps.

A community structure can be hierarchically ordered when the graph offers several levels of organization/structure at different scales. In this case, the community structure is hierarchically constructed by small communities at each level, all nested within large communities at higher levels. As an example, one may consider in a social network the granularity of the living place (town), the working place (school) and refine it toward the graduate or class level.

Synthetic graphs containing hierarchical structure

First, we apply the fuzzy detection algorithm to an artificial graph containing hierarchical structure [START_REF] Lancichinetti | Detecting the overlapping and hierarchical community structure in complex networks[END_REF]. The result is shown in Fig. 2.9. We observe that fuzzy detection extracts communities in hierarchical organization. The benchmark graph consists in 512 nodes, assigned into 16 groups of 32 nodes each. These 16 groups are ordered into 4 supergroups. The benchmark is constructed by assigning edges between nodes within the same micro-community. Each node has a micro-internal degree k 1 = 41. Then we assign edges between nodes belonging into different micro-communities but in the same macro-community. Each node has a macro-internal degree k 2 = 17. Finally we add edges between nodes to connect them to the rest of the network. All nodes have the same total degree k = 64 and an external degree k 3 = 6. This process constructs two The co-appearance matrix of synthetic networks containing a hierarchical structure. The color corresponds to the probability of nodes to be in the same community: the darker the color, the higher the probability; color is white if the probability is 0.0. hierarchical levels: one consisting of 16 small groups, and the other one composed of 4 supergroups with 128 nodes each. Figure 2.9 (b) illustrates the co-appearance matrix by running the Louvain algorithm without fixing the level threshold l * (See Algo. 4), while Figure 2.9 (a) provides the result by running the Louvain algorithm with l * = 1. In both figures, the nodes are sorted in the same order corresponding to the robust clusters and the selected partition P opt . As the distinction among robust clusters is not clear in Fig. 2.9 (b), we use Fig. 2.9 (a) for the visualization. We observe 4 communities and 32 robust clusters, which agrees with the ground truth.

Remark that, when running our fuzzy detection to identify modular overlaps, we may need to increase the value of α * to obtain a reasonable community core whose size is larger than the others within the same community. It occurs when one community contains several large robust clusters having comparable size.

Next, we apply the fuzzy detection algorithm to a random graph containing modular overlaps. The graph is composed of 512 nodes, which belong to 12 groups, arranged into 4 supergroups and one group is shared by two supergroups. Every node has an average of k 1 = 30 links with nodes in the same micro-community, k 2 = 13 links with nodes in the same macro-community but different micro-community. In addition, each node has k 3 = 5 links with the rest of the networks. As the modular overlaps has macro-links with two communities, its nodes have a total degree k = 61 while the other nodes only have a total degree k = 48. Figure 2.10 illustrates the result. We observe two communities that share one modular overlap. Results show the good performance of fuzzy detection algorithm in uncovering modular overlaps. The co-appearance matrix of college football network by running our fuzzy detection. We order the nodes corresponding to their conferences and mark the conference indices. The color corresponds to the probability of nodes in the same community: the deep color represents the high probability; the color is white if the probability is 0%.

College football network

We also run the fuzzy detection algorithm to real networks. A famous real but small and tractable network is the US college football [START_REF] Girvan | Community structure in social and biological networks[END_REF] . This network records the schedule of Division I games for the 2000 season: 115 nodes represent teams (identified by their college names) and 613 edges represent regular season games between the two teams they connect. What makes this network interesting [START_REF] Girvan | Community structure in social and biological networks[END_REF] is that it incorporates a known community structure. The teams are divided into "conferences" containing around 8 to 12 teams each. Games are more frequent between members of the same conference than between members of different conferences, with teams playing an average of about 7 intra-conference games and 4 inter-conference games fraction of vertices classified correctly in the 2000 season. Inter-conference play is not uniformly distributed; teams that are geographically close to one another but belong to different conferences are more likely to play one another than teams separated by large geographic distances.

In Fig. 2.11, we illustrate the results: the community "Mountain West Sunbelt" is split into "Mountain West" and "Sunbelt 1 ", the community "Sunbelt SEC" has a possible subdivision into "Sunbelt 2 "4 and "SEC", and a node "CentralFlorida" is split from the community "Pac 10". Among them, only "Sunbelt 1 " is identified as a modular overlaps. "CentralFlorida" has high membership degree with different communities, too. But it is a granular overlapping node rather than a modular overlaps. In reality, the team "CentralFlorida" did not belong to any conference, and the teams in the "Sunbelt" conference played nearly as many games against Western Athletic teams as they did within their own conference. Therefore, we consider fuzzy detection has a good performance in detecting modular overlaps for this real network.

Application to real networks: Complex System Science

In this section we consider the applications of clique optimization and fuzzy detection to a real network called Complex System Science. It is a co-citation network, whose dataset is composed of articles extracted from the ISI Web of knowledge. Article were published between 2000 and 2009. The network is composed of 141 163 nodes and 19 603 888 links. The nodes correspond to articles containing a set of keywords relevant to the field of complex systems. The weight of the links between articles is calculated through their common references (bibliographic coupling [START_REF] Kessler | Bibliographic coupling between scientific papers[END_REF]). A link exists between two articles if they share references, meaning that they cite common work which may implies that they are dealing with a same scientific object/domain. More precisely, given two articles (nodes) i and j, each one having a set of references R i (respectively R j ), there exists a link e = (i, j) between i and j if i and j share at least one reference and the weight is measured by:

w ij = |R i ∩ R j | � |R i | |R j | .
For the visualization, we only show clusters which contain at least 100 nodes5 . The partition of the graph is shown in Fig. 2.12. Each community corresponds to a unique color. Our obtained robust clusters are shown in Fig. 2.13. The color of each robust cluster corresponds to the relevant community in the partition shown in Fig. 2.12. Only robust clusters belonging to the same community in the partition share the same color.

In Fig. 2.12, we observe 12 communities. These communities can be identified by research topics or theoretical fields through studies in topic keywords, see Tab. B.1. We compute the frequency of topic keywords by aggregating the number of units (articles). For instance, if only one unite contains the topic keywords "Neurons", the corresponding frequency is 1. In the figure, the light green community is identified by neuroscience: biology psychology. This community contains high frequent keywords (Neurons, Performance, Central-Nervous-System) very general in neuroscience while some high frequent keywords (Brain, Long-Term Potentiation, Disease) seem to emphasize the study in the field of biological psychology. To our knowledge, biological psychology or behavioral neuroscience is the study of the biological substrates of behavior and mental processes. Physiological psychologists use animal models, typically rats, to study the neural, genetic, and cellular mechanisms that underlie specific behaviors such as learning and memory and fear responses. Cognitive neuroscientists investigate the neural correlates of psychological processes in humans using neural imaging tools, and neuropsychologists conduct psychological assessments to determine, for instance, specific aspects and extent of cognitive deficit caused by brain damage or disease. Table B.2 shows results of clique optimization in identifying granular overlaps in a strong sense 6 with a choice of k = 5. We see the applications of chaos theory in different disciplines including complex networks, nervous systems and ecosystems. We also observe the intermediation: visual cortex between neural networks and neuroscience: biological psychology. Visual cortex is one part of the visual systems, which receives visual information for processing images. These results are interesting in understanding the combination of different disciplines and applications. Robust clusters are depicted on Fig. 2.13. These robust clusters can be considered as sub-specialities of the identified disciplines listed in Tab. B.5. For example, the community identified by neuroscience: biology psychology is composed of several clusters, which are also characterized by research topics or theoretical areas. Note that, the study in neuroplasticity supports the treatments of brain damage, long-term potentiation concerns learning and memory, pre-botzinger complex is essential for respiratory rhythm, and the activities in prefrontal cortex are considered to be orchestration of thoughts and actions in accordance with internal goals. All these topics and fields refer to the study in neuroscience and biological psychology. It reveals that fuzzy detection can extract communities in hierarchical organization.

In terms of modular overlaps, our results are shown in Tab. B.4. Except astronomy-ISM(Interstellar medium) which acts like a unstable cluster, the rest has a good agreement compared to the reality: discrete-event systems and multi-agents are very common for modeling and analyzing general systems, computational complexity is a common property of complex systems, and genetic expression [START_REF] Hugot | Association of nod2 leucine-rich repeat variants with susceptibility to crohn's disease[END_REF][START_REF] Limbergen | Contribution of the nod1/card4 insertion/deletion polymorphism +32656 to inflammatory bowel disease in northern europe[END_REF] studies are often used to determine whether a genetic variant is associated with a disease or trait.

Granular and/or Modular Overlaps. Comparing the results of granular overlaps and modular overlaps is interesting since it reveals their intrinsic differences. For instance, fuzzy detection considers three modular overlaps related to computer science: communication systems and ecosystems simultaneously, while clique optimization does not provide any result. We can also observe their similarity. For example, both results use visual cortex to characterize the overlapping nodes shared by neural networks and neuroscience: biological psychology. It mainly indicates that, for some cases, the two types of overlapping nodes can reach an agreement in characterizing overlaps.

Obviously, we can not compare and rank the two methods in a definitive and quantitative way. Granular overlaps and modular overlaps represent results based on different definitions. To the best of our knowledge, both definitions seem really reasonable to use since they are more complementary by their intrinsic uncovering structure. Finally, we conclude that both methods: clique optimization and fuzzy detection, are useful to identify overlaps in complex networks and to give insights on the complex structure of real networks.

Discussion

In this section, we discuss the value of parameter used in our methods. We first present two networks used in our discussion.

Geography collaboration Geography collaboration is a co-author network combined with NUTS (The Nomenclature of Territorial Units for Statistics or Nomenclature of Units for Territorial Statistics) 7 . Nodes represent geo-codes, which are subdivisions of countries. Nodes are connected if there exists the collaboration between regions in scientific publications.

Wikipedia vote network Wikipedia is a free encyclopedia written collaboratively by volunteers around the world. A small part of Wikipedia contributors are administrators, . The number of overlaps decreases 2.14 (a) as k is increasing. The modularity value increases 2.14 (b) as k is increasing. We notice that the modularity of the community structure containing overlapping nodes is less than the partition whose modularity is 0.620506.

who are users with access to additional technical features that aid in maintenance. In order for a user to become an administrator a Request for adminship (RfA) is issued and the Wikipedia community via a public discussion or a vote decides who to promote to adminship. Using the dump of Wikipedia page edit history, 2, 794 elections with 103, 663 total votes and 7, 066 users participating in the elections (either casting a vote or being voted on) are extracted. About half of the votes in the dataset are by existing admins, while the other half comes from ordinary Wikipedia users 8 .

Granular overlaps and the parameter k

In clique optimization, the parameter k is used to prune nodes that are not overlapping nodes. If k increases, the number of granular overlapping nodes becomes smaller, but they are also more cohesive to the relevant communities. By applying clique optimization to real networks, we discuss the impacts of the parameter k.

We apply our clique optimization to the geography collaboration network. The average weight of the network edges ω * = 0.00402245 is used to prune the weak links. We compare the relative performances in detecting weak granular overlapping nodes for different values of k. In Fig. 2.14 (a) the number of overlapping nodes decreases as the value of k increases. The modularity of overlapping community structure is less than the modularity of the partition P opt (Q Popt = 0.620506), see Fig. of overlapping nodes is 9, but it is 6 for k = 10. We also note the small difference for the membership number distribution for overlapping nodes between k = 4 and k = 6: only 26% overlapping nodes have the membership number om ≤ 3 for k = 4 while it is 30% for k = 4 however due to nearly 51% overlapping nodes have the membership number om ≤ 5 for k = 4 while it is 50% for k = 6. It reveals that the overlapping nodes obtained at k = 4 are easier to have the membership number om = 4. We also study the results in characterizing overlapping nodes. The community structure is displayed on the map of EU Countries (See Fig. 2.16): each color represents a computed community. We observe that the community structure corresponds to countries. For example, the regions belonging to United Kingdom form a light green community. The organization of the geography collaboration network into different countries indicates that the collaborations within the same countries are much more important (from a quantitative point of view) than international collaborations.

Our clique optimization detects a large number of overlapping nodes at k = 4. Some "popular " overlapping nodes can even be assigned up to 8 communities. The results are shown in Tab. 2.2. We observe that they refer to large cities or regions have well established and famous universities. For example in UKJ14(Oxf ordshire), there is the University of Oxford. It reveals that our results are well matched to the reality since these large cities or regions having famous universities play important roles in international collaborations.

By comparing to the results obtained at k = 5 or k = 6, we observe their high similarity. We define popular overlapping nodes as nodes having the maximum number of memberships at different values of k. We found 18 popular overlapping nodes for k = 5 and 12 for k = 6 that are part of popular overlapping nodes for k = 4. The total number of popular overlapping nodes (om = 8) are 27 for k = 4, the total number (om = 7) are 18 for k = 5 and the number (om = 6) are 12 for k = 6. Of course, the popular overlapping nodes are also large cities or regions that have famous universities and international collaborations (See Tab. 2.2). It tends to show that our method can characterize the fundamental properties of overlapping nodes among communities, which are independent of the value of k.

Next we study the impact of k on another dataset: Complex System Science (See details in Section 2.5). The results are listed in Tab. B.2 and Tab. B.3. It can be seen that the obtained granular overlaps have the same highest frequent topic keywords and very similar high frequent topic keywords at k = 5 or k = 6. For example, high frequent topic keywords owned by overlaps between ecosystems and chaos theory obtained for k = 6 totally match to the results obtained for k = 5: Dynamics, Self-Organization, Model, Complexity, Chaos, Systems, Stability, Patterns where "Evolution" and "Celluar Automata" are not shown in Tab. B.3 as their frequency are not high enough for k = 6. Totally, we obtained the same characteristics by mining these granular overlaps at different values of k. In other words, the fundamental properties of the found granular overlaps are largely independent of k and represent the characteristics owned by the system itself.

Node

Community memberships and membership degree

Our fuzzy detection typically sets β * = 0.1 to determine community memberships. If the threshold β * increased, the number of modular overlaps decreased; otherwise, more robust clusters are identified as modular overlaps. The criterion we used to fix the optimal β * values should be based on finding a community structure having the good quality.

We studied the membership degree, which is used to determine community memberships. In Fig. 2.17, we show results by applying fuzzy detection to Geographical Collaboration and Wikipedia vote network. The figures show the obtained p c i ,c j for pairs of robust clusters, where the nodes are listed through their size in ascending order. From the results, we observe that most p c j ,c i are in values of approximate 99.9% (dark blue) and a few of p c j ,c i are in values of nearly 10% (light pink). It seems that robust clusters which perform unstable (belonging to different communities in the partition examples) have the low membership degree with the relevant community. If we set β * in a high value, we would find no modular overlap.

In Fig. 2.18, we show the modularity by increasing the value of β * . These results are obtained by applying fuzzy detection in Geographical Collaboration and Wikipedia vote network. We observe some critical points, which are important for the modularity like β * = 9% in Fig. 2.18 (a) and β * = 18% in Fig. 2.18 (b). In practice, we use the value corresponding to the critical point to set β * , which is approximate 10%.

Conclusion

In this chapter, we have presented our studies in overlapping community structure. We have discussed the limits of existing modularity for qualifying the covers, and proposed a new extension, which is based on the Hamiltonian. We have also introduced two novel methods to identify overlapping nodes. One is called clique optimization for identifying granular overlaps, and the other is named fuzzy detection for modular overlaps. Both methods have been tested successfully in synthetic graphs. Moreover, studies and the analysis on large networks like the Complex System Science one give good results and useful insights on the structure of the network. We believe that the elements presented in this chapter can be of great help in the analysis of networks. On the one hand, the definition of granular overlaps and modular overlaps provide different insights in characterizing overlapping nodes for network analysis. On the other hand, the introduction of clique optimization and fuzzy detection could open the way for applications to large-scale systems. Remind the results in studying Yeast protein complexes in Section 2.3.3. The low sensitivity of clique optimization is caused by our definition of k-granular overlapping nodes, i.e., not all real overlapping nodes participate in k-cliques. However, fuzzy detection provides results with a high sensitivity. Since fuzzy detection assigns nodes into communities without computing their connections. Simultaneously, clique optimization will not misclassify unstable nodes. Therefore, it has a higher specificity value than fuzzy detection. It suggests us to combine both methods to study overlapping community structure. We may obtain the complementary results.

Chapter 3

Overlapping communities and community evolution

In dynamic networks, change is a fundamental ingredient of interaction patterns in biology, technology, economy, and science: interactions within and between organisms change; transportation patterns by air, land, and sea all change; the global financial flow changes; and the frontiers of scientific research change.

Network clustering methods have become important tools to detect community evolution. Most methods make endeavours to distinguish between real trends and noisy data. However, detecting community dynamics is also important to study community evolution. For example: How has the network of global air traffic changed over the past half century? How does the organization of social contacts change when diseases develop and spread? How does the network structure of the federal funds market change when credit markets freeze up? How do gene regulatory networks differ between cancer and non-cancer states? And how does science evolve as research tools, strategies, and agendas shift through time?

Asur et al. [START_REF] Asur | An event-based framework for characterizing the evolutionary behavior of interaction graphs[END_REF] have detected clusters at each snapshot graph independently and used event definitions (Def. 2) to compute and identify community dynamics. Their studies in the DBLP co-authorship network showed how semantic content and category hierarchy information were related to community fusion or split. However, their event definitions need the parameter value. Furthermore, we do not have a good visualization tool to illustrate these diverse community dynamics.

In this chapter, we contribute to community detection in dynamic networks (Section 3.1) including a matching technique and a visualization tool. Our matching technique is able to resolve the problem of characterizing community dynamics. Our visualization tool makes community dynamics observable. We validate our method by applying it to a synthetic dataset and a blog network in Section 3.2. We also analyze a dynamic co-citation network called the past history of complex system science in Section 3.3 with the discussion of modular overlaps.

Tracking community evolution in dynamic networks

In the context of dynamic graphs, the interactions between nodes change over time. As the community is defined as a set of nodes having dense internal connections and sparse external connections, the changes of interactions can cause the evolution of communities in networks.

In the early analysis of community structure in dynamic networks, Palla et al. [START_REF] Palla | Quantifying social group evolution[END_REF] have already introduced six basic scenarios in the evolution of communities: birth, growth, contraction, merging, splitting and death as we mentioned in Fig. 1.2. Recently, some studies [START_REF] Malhotra | Knowledge management and virtual organizations[END_REF][START_REF] Pauleen | Virtual teams: projects, protocols and processes[END_REF] have discussed the reason why a community structure may change. Their reasons can be divided into two categories: a) internal and b) external influences.

• Internal influences

Common ground. It is the "mutual knowledge, mutual beliefs, and mutual suppositions" shared by individuals [START_REF] Clark | Grounding in communication[END_REF]. It attracts interactions between individuals. However, the common ground may change. For instance, increasing community size may increase fringe nodes (or unstable nodes). It increases the dissimilarity among members. Therefore, it can be observed that a rapidly growing community looses its common ground, and then changes.

Community membership. A community may have relatively permanent members (or core nodes), but also has many fluid members (who join in communities occasionally and change their community memberships after several time steps). In addition, there are new members joining in communities, which also influences community dynamics.

• External influences: The external influences are various: a specie community changes by following food seasons [START_REF] Chen | Detecting and Tracking Community Dynamics in Evolutionary Networks[END_REF]; a political community might be more active in the run-up to elections; and a science field community can disappear caused by a replaced criteria such as AIDS-related complex1 .

The influences described above result in the change of a community: creation, growth, shrunken, fusion, split or disappearance.

If one community is not involved in fusion events or split events but only increases its size or decreases its size, we say that the community survives. In [START_REF] Palla | Quantifying social group evolution[END_REF], it turns out that the age of a community is positively correlated with its size, i.e., the older communities are also larger (on average).

In an organizational context, a community is created or survives if it maintains a coherence, i.e., common ground. The investigation of a survival community allows us to learn how common ground evolves over time.

For the fusion of communities, Gongla and Rizzuto [START_REF] Gongla | Where did that community go? -communities of practice that disappear[END_REF] have given two definitions: a) fusion between equal communities and b) fusion between unequal communities.

Fusion between equal communities. If communities share a lot of common members or properties, i.e., interests, they may merge and are replaced by a new larger community.

Fusion between unequal communities. If a community constitutes a specialized sub-domain of a larger community it may willingly join in the broader community or be absorbed.

In the event of community split or community disappearance, Gongla and Rizzuto [START_REF] Gongla | Where did that community go? -communities of practice that disappear[END_REF] have identified three factors: Organizational change. A community is usually sponsored by a particular interest such as a topic, a function or a group of leaders. When these interests change, the community is at risk of changing such as dying. For example, a change of the group leaders may result in new priorities and redeployment of resources [START_REF] Gongla | Where did that community go? -communities of practice that disappear[END_REF].

Knowledge domain change.

A knowledge domain of a community is not necessarily static. An interest may change, and the community evolves. For example, in a co-citation network, the cooperation between communities can innovate a new research topic.

Community leadership change. The leaders (or the core members) of a community have a high influence on the evolution of the community. They can be more active and attract more new members. They also can make the community less active and finally disappear.

A disappearing community usually becomes gradually smaller or attracts less and less new members: community members have less and less interactions until the community vanishes.

As shown above, communities changes may caused by diverse factors. Their dynamic behaviors make the problem of tracking community evolution more complex. However, in analyzing networks, the properties of community persistence and community development should not be ignored. These properties can be important as they reveal the evolving tendencies of networks. The evolution of communities may be significant (Section 1.2.2). For example, a unique new created community is enough to change the whole community organization. Capturing when community dynamics occur and charactering these dynamics is an important aspect when investigating communities over time.

Group persistence two-stage method

We describe a novel heuristic to track community evolution in dynamic network. Given a dynamic graph G, its community structure is a set of communities {C 1 , . . . , C nc } which evolve over time. A given community C i can be observed at several time steps. Of course, It also may change.

To resolve the problem of community detection in dynamic networks, we apply a twostage approach which is briefly described as: in the first step, we use the fuzzy detection algorithm described in the previous chapter to detect a partition with the maximum modularity, robust clusters and modular overlaps at each time step (Section 2.4); in the second step, we use a mapping method (Section 3.1.4) to connect partitions at different time steps. Simultaneously, we track community evolution and identify community dynamics. For tracking community evolution, we use an evolution path (Def. 1) to describe how one community evolves over time. The length of the evolution path denotes the duration time of the community. The variation of community members shows how one community attracts new members or loses old members. The connection between communities at different time steps is used to identify communities changes: creation, continuation, fusion, split or disappearance.

Although as described in Section 1.3.2, diverse mapping methods [START_REF] Falkowski | Community dynamics mining[END_REF][START_REF] Hopcroft | Tracking evolving communities in large linked networks[END_REF][START_REF] Spiliopoulou | Monic: modeling and monitoring cluster transitions[END_REF] are proposed and are used to identify communities at different time steps, the limit remains. For example, in terms of matching metric, a problem is whether the similarity value is based on min(|X|, |Y |) or |X ∪Y |, where X, Y represent the temporal clusters at different time steps. Moreover, definitions used for characterizing communities dynamics need parameter value such as the parameter κ in Def. 2.

To overcome the matching problem, we apply group persistence to match communities. Our method is motivated by [START_REF] Simmel | The persistence of social groups[END_REF] and connects communities depending on overlap size, i.e., |C(t) ∩ C(t + 1)|, for two temporal clusters at time steps t, t + 1 respectively. Next, we describe our method in details.

Motivation

Let take an example illustrating the notion of group persistence [START_REF] Simmel | The persistence of social groups[END_REF]. A group of five members {a, b, c, d, e}, is strongly related to a subsequent group with {m, b, c, d, e} members. It is also clear that a group with {a, b, c, d, e} is not related to a subsequent group of {f, g, h, i, j}. Through the knowledge of dynamic network analysis, one can infer that the properties of a group are not a summary of the properties of individual members. Instead, they emerge from the structure of interactions among members. Therefore, given a group {a, b, c, d, e}, one supposes that the development takes the following course: a, b, c,d,b,c,d,n,c,d,n,o,d,n,o,p,n,o,p,q. In this case, each stage is differentiated from the previous stage by only one member, and at each moment it shares the same majority elements with its neighboring moments. Consequently, the group with {a, b, c, d, e} is defined to be linked with its subsequent group of {m, n, o, p, q}.

Motivated by this simple toy example, we use group persistence to track community evolution. First, we establish a relationship called community predecessor and successor between temporal clusters for every pair of contiguous stages. For two temporal clusters in predecessor/successor relationship, their overlap size must exceed a threshold γ * . Then, we use this community predecessor and successor relationship to map temporal clusters and identify community dynamics.

Definition 5 (Community predecessor and successor). Given a temporal cluster C i (t) at time t, if the temporal cluster C j (t -1) has the maximum overlap size among all temporal clusters at time t -1, we define that C j (t -1) is the predecessor of C i (t). If the temporal cluster C k (t + 1) has the maximum overlap size among all temporal clusters at time t + 1, we define that C k (t + 1) is the successor of C i (t).

In the following, given a pair of temporal clusters (X, Y ), we use X → Y to denote that Y is X's successor and X ← Y to represent that X is Y 's predecessor.

When a community changes, the predecessor/successor relationship may be obtained by nodes which participate temporally in this community. It can be observed that some nodes may easily change their memberships. The threshold γ * is used to handle this problem by filtering relationships caused by member fluctuation. This ensures that linked temporal clusters have high correlation when communities evolve over time, i.e., for one community, there are few changes in its community members over time.

Remark. The relationship between one community and its successor (or its predecessor) may be asymmetrical. That is, for one community and its successor, this community may be not the predecessor of its successor. Similarly, for one community and its predecessor, it is possible that the community is not the successor of its predecessor. This asymmetrical property allows us to characterize community dynamics.

Community dynamics

As listed above, there are six basic community dynamics: a community emerges (creation), a community may grow (growth), a community can shrink (shrunken), several communities can merge together (fusion), a community can be split into several communities (split) or a community may disappear (disappearance).

The above definition of community predecessor/successor relationship allows us to characterize community dynamics. Definition 6. Let G(t) and G(t + 1) be snapshots of G at two consecutive time steps with the temporal partition P(t) and P(t + 1) denoting the community structure of G at time step t and t + 1, respectively.

Survive. C j (t + 1) is the continuation of C i (t), if and only if C i (t) is the predecessor of C j (t + 1) and C j (t + 1) is the successor of C i (t), such that:

C i (t) ← C j (t + 1) ∧ C i (t) → C j (t + 1)
This relationship is denoted by C i (t) � C j (t+1). We say that community C i whose observation at time step t is C i (t), survives at time step t + 1. The relationship between a temporal cluster and its continuation is symmetrical, such that, given a continuation, it must be the successor of its predecessor. If a community survives at the current time step, we identify whether it is a growing community or whether it is a shrinking community through the variance in size between its observation at previous time step and its current observation. We say that, a growing community has an increasing number of community members and a shrinking community has a decreasing number of community members.

Emerge. C j (t + 1) is a creation if and only if C j (t + 1) has no predecessor such that:

�C i (t) ∈ P(t)| (C i (t) → C j (t + 1))
We say that a new community emerges if and only if its first observation has no predecessor.

Merge. C j (t+1) is a fusion if and only if C j (t+1) is the successors of several clusters at time step t such that:

∃{C i (t), C k (t)} ⊆ P(t)| (C i (t) → C j (t + 1) ∧ C k (t) → C j (t + 1))
where i � = k. In case of C i (t) → C j (t + 1) and C i (t) � C j (t + 1), we say that, community C i is merged into C j where C i (t) is the observation of C i at time step t and C j (t + 1) is the observation of C j at time step t + 1.

Split. C j (t + 1) is a split if and only if C j (t + 1) is not the successor of its predecessor such that:

C i (t) ← C j (t + 1) ∧ C i (t) � C j (t + 1)
We say that, a community is split from others if and only if its first observation is a split;

Disappear. A community disappears at time t + 1 if and only if its observation C i (t) at time step t has no successor such that:

�C j (t + 1) ∈ P(t + 1)| (C i (t) � C j (t + 1))
Diagrams in Fig 3 .1 show several cases illustrating community dynamics which can be featured by continuation, creation, disappearance, fusion and split. For better understanding community evolution, we show their evolution paths (Def. 1). For each community C, its evolution path is Evol(C) := {C(1), . . . , C(Δ)}, where each element C(i) (1 ≤ i ≤ Δ) represents its observation at time step t = i. .

In the example illustrated by the Fig 3 .1, we observe four communities, whose evolution paths are:

• Evol(C 1 ) := {C 1 (1), C 1 (2), C 1 (3), C 1 (4)} , • Evol(C 2 ) := {C 2 (2), C 2 (3)} , • Evol(C 3 ) := {C 3 (1), C 3 (2), C 3 (3)} , • Evol(C 4 ) := {C 4 (3), C 4 (4)} .
We can observe nearly all types of community changes:

• Community C 2 is created at t = 2 as it has no predecessor at t = 1; CHAPTER 3. OVERLAPPING COMMUNITIES AND COMMUNITY EVOLUTION81

t = 1 t = 2 t = 3 t = 4 C 1 : ���� ���� C 1 (1) � � ���� ���� C 1 (2) � � � � ���� ���� C 1 (3) � � � � ���� ���� C 1 (4) � � C 2 : ���� ���� C 2 (2) � � ���� ���� C 2 (3) � � � � � � � � � � � � � � C 3 : ���� ���� C 3 (1) � � ���� ���� C 3 (2) � � � � ���� ���� C 3 (3) � � C 4 : ���� ���� C 4 (3) � � � � � � � � � � � � � � ���� ���� C 4 (4)
� � • Community C 3 disappears at t = 4 as it has no successor at t = 4;

• Community C 2 is merged into C 1 at t = 4 since its successor at t = 4 is C 1 (4) whose predecessor is not C 2 (3);

• Community C 4 is split from C 2 since t = 2 as its predecessor at t = 2 is C 3 (2) whose successor is not C 4 (3).

Community C 1 is observable during all the observation window (only four time steps on this toy example). At time step t = 4, community C 2 joins it. This community fusion event seems to be more an event related to C 2 rather than to C 1 .

A more complex diagram is displayed in Fig. 3.2. We observe the changes of communities from time step t = 2 to t = 3. At time step t = 3, community C 2 partially merges with C 3 while its split

C 1 (3) starts a new community C 1 .
The definition of community predecessor/successor relationship allows for linking communities at different time steps. It also makes the problem of characterizing community dynamics be captured easily.

Mapping method

Our framework uses fuzzy detection to detect community structure in each snapshot graph. The results include the optimal partitions in terms of modularity, a set of robust clusters, the community cores and the modular overlaps. Having a range of granularity and resolution in the results is an opportunity. We use a mapping method to track

t = 1 t = 2 t = 3 t = 4 C 1 : ���� ���� C 1 (3) � � � � � � � � � � � � � � ���� ���� C 1 (4) � � C 2 : ���� ���� C 2 (1) � � ���� ���� C 2 (2) � � � � � � � � � � � � � � C 3 : ���� ���� C 3 (1) � � ���� ���� C 3 (2) � � � � ���� ���� C 3 (3) � � � � ���� ���� C 3 (4) � �
t = 1 t = 2 t = 3 t = 4 Evol(C 1 ) ���� ���� C 1 (1)
� � ���� ���� × � � ���� ���� C 1 (3) � � ���� ���� C 1 (4) Evol(C 2 ) ���� ���� C 2 (1) � � ���� ���� × � � ���� ���� × � � ���� ���� C 2 (4)
Figure 3.3: Community evolution paths of two evolutionary communities over four time points. During their evolution, they are unobserved at some time steps. For instance, community C 1 is unobserved at t = 2 while it reappears at t = 3, and community C 2 seems missing at t = 2 and t = 3. community evolution and identify community dynamics. We are also able to use the same method to track robust cluster evolution. The results can help us to understand leadership change (community core members change) and influences of community members. Another advantage is to track the evolution of modular overlaps. In the context of science whose community structure is captured by different research fields, it provides insights in the evolution of interdisciplinary fields, which link several communities. Before our description of our framework in details, we illustrate some special cases as depicted in Fig. 3.3 and introduce the definition of reappearing community. This Figure illustrates the case where some communities become unobservable at a time step but reappear after several time steps. For community C 1 in Fig. 3.3, we say that its observation at time step t = 2 is an invisibility, i.e., it occurs when one community is unobserved but reappears lately.

Our mapping method uses the definition of community predecessor and successor to track community evolution. Additionally, it uses a backward method to identify reappearing communities. The details of how we track community evolution is sketched in Algorithm 6.

We use the definition of community predecessor and successor to track community evolution: two temporal clusters are mapped if they share the relationship of community predecessor and successor. If a community becomes unobservable, we hold its last observation. Lately, we apply a backward method to identify it when it reappears.

For a community which is not the continuation, we use a possible predecessor and successor relationship to connect it with a disappeared community: Definition 7 (Possible predecessor and successor). Given a temporal cluster C i (t) at time t which is not a continuation, it is a possible successor of a disappeared community C j , if the last observation of C j , i.e., C j (t -Δ), shares the maximum overlap size among all temporal clusters at time t and the overlap size exceeds the size threshold γ * . For a disappeared community C j whose last observation is C j (t-Δ), it is a possible predecessor of C i (t): if C i (t) has a predecessor C k (t-1), the overlap size between C i (t) and C j (t-Δ) exceeds the overlap size between C i (t) and C k (t -1); otherwise, the overlap size between C i (t) and C j (t -Δ) exceeds the size threshold γ * .

We connect a temporal cluster and a disappeared community if and only if the temporal cluster is a possible successor of the disappeared community and the disappeared community is the possible predecessor of this temporal cluster with the maximum overlap size among all disappeared communities. We use C j (t -Δ) � C i (t) to denote this relationship between a temporal cluster C i (t) and a disappeared community whose last observation is C j (t -Δ). In this case, we say that a community reappears.

Our results are based on partitions. We do not consider overlapping communities for tracking community evolution since they make the problem more complex. For instance, when we establish the relationship between temporal clusters at different time steps, we count the total community members or only non-overlapping parts? When overlaps between a pair of communities become an independent community, this dynamic is classified into merge event or split event? When a community shares a lot of nodes with others, we may obtain a wrong successor for large overlapping nodes.

However, our fuzzy detection is able to provide modular overlaps. We can track modular overlaps to study how overlapping parts evolve. Therefore, we also use the same mapping method (Algo. 6) to track robust cluster evolution: two temporal robust clusters are mapped if they share a relationship of predecessor and successor. When tracking robust cluster evolution, we do not only study modular overlaps evolution but also investigate community cores evolution. The later is helpful to understand how leadership changes affect community evolution.

Visualizing community evolution

In this section we present our novel visualizing tool for revealing structural changes and illustrating "stories" in dynamic networks. We first review existing tools for visualizing

Visualizing community evolution through lineage diagrams

Our visualization tool illustrates "stories" in dynamic networks through lineage diagrams (See Fig. 3.5). Each lineage represents a separate evolutionary path, and occupies a column. The evolution of a community is shown from left to right. The temporal clusters representing the observations of the same community are shown in the same y-axis. Each cluster is shown by a circle whose size is proportional to its number of nodes. A lineage tie is added between two clusters if they share a successor or predecessor relationship. Therefore, if a circle has a link to another column, it indicates a community change. For example, in Fig. 3.5, we observe a link connecting a violet cluster and an orange cluster between t = 2 and t = 3. It represents a change event. We can characterize community dynamics through the orientation of links:

• If this link is oriented from left to right, it indicates that a community merges into another one;

• If this link is oriented from right to left, it indicates that a community is the result of a split from another one.

Figure 3.5: Applying our method to a sample dynamic network. Between t = 2 to t = 3, an orange cluster is split from the violet community. At t = 3, a new green cluster is emerged. Between t = 3 to t = 4, the orange cluster is merged into the violet community. Between t = 4 to t = 5, a blue cluster is split from the violet cluster and it is merged with the green community simultaneously.

The orientation of links is shown in colour such that the link colour is given by the link parent. For example, in Fig. 3.5, we observe a violet cluster having a link with blue colour which connects it and a blue cluster. In this case, we say that the blue cluster is a split of the violet community. Moreover, the blue cluster has a link with green colour which link it to a green cluster. We say that the green community merges into the blue community.

In addition, we use colours to indicate community memberships. The observations of a community at different time steps share the same colour.

In terms of robust clusters, we also use lineage diagrams to show structural changes. Each lineage represents a separate evolutionary path of a robust cluster, and occupies a column. The evolution of a cluster is shown from left to right. The temporal clusters representing the observations of the same clusters are shown in the same y-axis. Each cluster is shown by a circle whose size is proportional to its node number. Each lineage tie is added between two clusters if they have the successor or processor relationship.

As colors correspond to community memberships, we can study community member shifts. For instance, some robust clusters may change their community memberships as the graph evolves.

Experimental results

Through our method, community dynamics like merge or split become easy to be identified. In case of reappearing communities, we validate our method through a set of synthetic networks. We also show performance of our method by applying it to a real dataset.

Synthetic datasets

Greene and Doyle [START_REF] Greene | Tracking the evolution of communities in dynamic social networks[END_REF] proposed a set of benchmarks based on Lancichinetti and Fortunato's technique [START_REF] Lancichinetti | Benchmark graphs for testing community detection algorithms[END_REF]. Lancichinetti and Fortunato assumed that the distributions of degree and community size are power laws, with exponents τ 1 and τ 2 , respectively. Each node shares a fraction 1µ of its edges with the other nodes of its community and a fraction µ with the rest of the graph; µ is a mixing parameter in range of [0, 1]. After predefining community structure, edges are randomly assigned corresponding to node internal degrees and external degrees.

For the event of community reappearance, Green and Doyle has constructed a set of synthetic datasets, which covers 15, 000 nodes over 5 time steps. At each time step, 10% of communities are unobserved by randomly permuting node memberships (and edges).

By applying our method to this dataset with l * = 1 over all time steps2 and γ * = 5 for matching communities3 (Def. 5), we track community evolution and observe at least 40 reappearing communities at each time step.

To validate our method, we compare our results and the ground truth. We describe our results by observed communities and the ground truth by expected communities. The true positive nodes represent the nodes assigned in both observed reappeared communities and expected reappeared communities. Table 3.1 show our results in views of the number of observed reappeared communities (NOC) and number of expected reappeared communities (NEC), the number of true positive and the number of the reality (NPOCM/NECM), and the mean positive predictive value (mean PPV) with the standard error (SE).

From Tab. 3.1, we observe the similar number of reappeared communities obtained by our methods to the ground truth. For each observed reappeared community, it has a positive predictive value. It is the ratio of the number of true positive nodes in the observed community. Therefore, the high value of mean PPV represents that most nodes in observed reappeared communities are positive truth nodes. Especially at t = 4 and t = 5, the mean PPV value is 1. It reveals that all nodes belonging to the observed reappeared communities totally match to the reality. The number of the reality (NECM) is the number of nodes belonging to the expected reappeared communities. Thus, the similar number of true positive nodes to NECM represents that most nodes belonging to the expected reappearing communities are found. As we can see, our framework has good performance in detecting reappeared communities.

Blogs

Given a blogs network, approximately six thousand blogs were monitored to track the various articles and comments posted or the citation links between them for four months. We used the networks between blogs containing the aggregated data to the relevant day. we begin at the 1st day and then add each new day blogs and links between them. So we get a growing network consists 120 time steps. By applying our method to blogs network, we show the results in Fig. 3.6. The node is labelled by the highest frequency class. When one post is added, its blog source and blog destination are classified into three levels. In the highest level, there are only three different classes (iindividualite, ssociete, lloisirs). We compute the frequency of classes by aggregating them. For example, once one blog is classified into the class of iindividualite, we aggregate the frequency of iindividualite in the community in which the blog is assigned. Finally, we select the class with the highest frequency to label the community. For the visualization and comparison, the color of nodes corresponds to the label. For instance, the nodes at the bottom are coloured by green in Fig. 3.6 (b). It corresponds to their labels: all nodes are labelled by iindividualite. Since there are 120 days, we set a time window t = 2 weeks (i.e., 14 days), such that when t = 1, G(1) is the aggregation of interactions between nodes during [0, 14] days; when t = 2, G(2) is the aggregation of interactions between nodes during [0, 28] days; and so on. We set a size threshold n * = 100 such that all shown temporal clusters contain at least 100 nodes. In this figure, the evolution is shown from left to right with x-axis denoting the time step and y-axis representing community index. Circles represent the found communities, with size proportional to community size. Links represent member continuity of at least 5 nodes, with size proportional to the continuity. The color of links corresponding to link parents denotes their orientation.

We compare the results labelled by classes in the lowest level and the highest level. We observe that nearly all communities hold their classes over all time steps. For example, we observe the community (3-th line) labelled by ccuisine in Fig. 3.6 (a) (or labelled by lloisirs in Fig. 3.6 (b)) survives from t = 1 until t = 8. In views of the highest level shown in Fig. 3.6 (b), we observe that most changes occur within the same classes. For example, the merge event at t = 3 occurs within the class ssociete. In views of the lowest level (See Fig. 3.6 (a)), more information is provided. For example, these observed communities (whose duration is at least two time steps) show the evolution of different classes. We observe a community labelled by mmode (in orange at the bottom) emerges at t = 3 (nearly 42 days). We also observe the community labelled by mmode has a split at t = 3. This split community is labelled by ccarnet bd, which merges into the community ttech revolution at t = 5. It may represent the close relation between ccarnet bd and ttech revolution.

These results are used to show that our method provides a good visualization tool: how communities change becomes easy to learn.

Application to a dynamic co-citation network

Finally, we apply our method to a dynamic co-citation network. It is called past history of complex system science. This data set (See also Section 2.5), collects extracted articles from the Institute for Scientific Information Web of knowledge4 . All selected articles contain topic keywords relevant to the field of complex systems such as "complex * ", "self organ * ", "complex network * ", "econophysics * ", and so on.

Complex systems is a new approach to science that mathematically models behavior of systems, and builds relationship between system interacts and its environment. As early as 19th century, complex systems theory was used to capture economic computation problem. So far, it is used to model processes in computer science, biology, economics, physics, chemistry, and many other fields. The key problems of complex systems are modeling and simulating system behaviors. Various kinds of methods for identifying, exploring, designing and interacting with complex systems are used. In our early study of complex system science (Section 2.5), we obtain various claims to the universality. The identified community structure provides a broader view of disciplines and methodologies using complex systems approach.

The past history of complex system science could be represented by a dynamic network. In the network, entities (articles) associated to their published time evolve over time. An intuitive way to capture the history of complex system science is to construct a sequence of snapshot graphs, whose community structure changes correspond to the science evolution. In the following, we first build a dynamic graph, and then detect, visualize and analyze community evolution and their dynamics.

Why use dataset about bibliographic coupling Citation analysis is the study of the frequency, patterns and graphs of citations in articles and books. It uses citations in scholar works to establish links to other works or other researchers. Today, there have various applications of citation analysis tools, which provide the understanding and analysis of information retrieval and science evolution. In the context of community organization of graphs, a citation network is associated with citation patterns, where each citation pattern corresponds to a scientific topic or research field.

The evolution of community structure in a citation network reveals science history. For instance, HELLSTEN et al. [START_REF] Hellsten | Self-citations, coauthorships and keywords: A new approach to scientists' field mobility?[END_REF] have used OPM (Optimal Percolation Method) to study the community structure of a citation network. The dataset is the ISI-indexed publication record of Werner Ebeling. The results showed that communities of this network corresponded to the author (Werner Ebeling)'s general contribution (sequences, chaos, self-organization, systems), a specific branch (plasma research) and collaboration contributions (with other authors).

Hopcroft et al. [START_REF] Hopcroft | Tracking evolving communities in large linked networks[END_REF] used a network extracted from the NEC CiteSeer database [START_REF] Giles | Citeseer: An automatic citation indexing system[END_REF] related to computer science, with a small collection covering other topics like physics, mathematics, and economics. In the result of their application, they observed the change of one community: the field of quantum algorithms and communication is emerged.

Applying a computational technique to a citation network becomes a popular method to analyse science history. In the later, we apply our method to a dynamic co-citation network. Before starting our dynamic studies, we review our investigation in a static co-citation network (See Section 2.5). Through its community structure, we observe:

Communities refer to research topics or theoretical fields. By characterizing community structure, we observe molecular biology, ecosystems, complex networks, dynamic turbulence these common research topics or theoretical fields in the science of complex systems but obviously refer to diverse disciplines.

Robust clusters can be considered as sub-specialities. Robust clusters have close relationship with their communities. That is, the relationship between robust clusters and their communities can be expressed by the relationship between subspecialities and specialities in views of cluster characterization. It reveals that robust clusters represent a possible hierarchical organization of communities.

Module overlaps link several topics and/or theoretical fields. Modular overlaps represent clusters of overlapping nodes, which link several topics and/or theoreti-

I 1 : t 1 � �� � t 2 t 3 . . . t n t n + 1 G (1)
I 2 : t 1 t 2 � �� � t 3 . . . t n t n + 1 G (2)
. . . cal fields in views of cluster characterization. For example, visual cortex is used to characterize the overlapping nodes shared by neural networks and neuroscience: biological psychology.

I s : t 1 t 2 t 3 . . . t n � �� � t n+1 G(s)
In case of dynamic co-citation networks, analysis in community evolution may provide us insights in understanding the past history of complex system science.

Building a dynamic graph

Articles in the past history of complex system science were published during 1985-2009. An edge e = (i, j) connects two articles i and j if both articles share common references and the weight w ij of the edge is given by the bibliographic coupling between i and j [START_REF] Small | Co-citation in the scientific literature: A new measure of the relationship between two documents[END_REF]. We note R i the set of references cited by an article i. The bibliographic coupling between two articles i and j is w

ij = |R i ∩ R j | � |R i | |R j | .
We construct a dynamic graph according to each publishing year. Each snapshot graph captures interactions between nodes during a given time interval. Motivated by Palla et al. [START_REF] Palla | Quantifying social group evolution[END_REF], we use a time overlapping window. It smooths out the gaps that sometimes occur between two discrete time intervals. We set the time interval size to 10 years with an overlapping time of 5 years. Then, we construct a dynamic graph on the obtained overlapping window (See Fig. 3.7). More details on the dynamic graph in the sequence of snapshot graphs are given in Tab. 3.2.

Detecting and visualizing community evolution

Let list the result factually. On the data set described above we obtained: 1985 -1994: there are 14 communities In terms of community dynamics, we observe:

between 1985 -1994 and 1990 -1999: 4 communities split and 3 merge ;

between 1990 -1999 and 1995 -2004: 3 communities split and 1 merges ;

between 1995 -2004 and 2000 -2009: 1 community splits and 3 merge.

The lineage diagrams are shown in Fig. 3.8. The Figure illustrates structural changes that occur in the past history of complex system science co-citation network over the years 1985 to 2009. We see the evolution of the number of communities and observe how important the split or merge events are to explain structural changes.

Evaluating the results

A key question remaining is how well our method is to track community evolution in our dataset. We choose to study the stability of communities. The stability measures the probability of community members to maintain their community memberships over time. Given a community C whose observation at time t is C(t), its stability is the portion of active nodes at time t + 1 that are assigned to its successor C(t + 1):

stability(C)(t) = |C(t) ∩ C(t + 1)| |C(t) ∩ G(t + 1)| (3.1)
where C(t) ∩ G(t + 1) denotes the nodes belonging to C(t) which are still active (or are recorded) at time t + 1 and C(t) ∩ C(t + 1) represents the nodes in common between C(t) and C(t + 1) .

Similarly, we also study the core stability, which is the portion of active core nodes � c(t) which are assigned to the successor C(t + 1): where � c(t)∩G(t+1) denotes the core nodes of C(t) which are still active (or are recorded) at time t + 1. As discussed in [START_REF] Hopcroft | Tracking evolving communities in large linked networks[END_REF], the core nodes have high stability to hold their community memberships. Here, we compare the stability of core nodes and the disjoint community members to show how well our method is to track community evolution.

stability(� c)(t) = |� c(t) ∩ C(t + 1)| |� c(t) ∩ G(t +
Table 3.3 gives the average stability value of clusters and core nodes between every pair of consecutive snapshot graphs. We observe that our results have a high agreement with the results of community identification through core nodes. Compared to general community members, the core nodes have higher probability to maintain their community memberships. For example, the first row in the table shows that for all communities with the size threshold6 n * = 100 during 1985-1994 (the total number of communities is 14), their average stability value is 0.740646 with a standard deviation of 0.152708. We also observe that most of core nodes during 1985-1994 appeared in their successor communities. In the following, we show our results through the citation analysis.

Study of the community evolution

By using citation analysis to detected communities, we examine the topics or fields (see Tab. B.6, Tab. B.7, Tab. B.8 and Tab. B.9), which are used to claim the universality of complex systems, and explain the complex systems history evolution. Stable communities. From our results, we can observe that some communities remain very stable and hold their community interests. For example, the community SOC (Self-organized criticality) has not been involved into any fusion or split event. By examining its high frequent topic keywords, we can see that the highest frequent topic keywords is "Self-organized criticality" over all time steps, whereas other high frequent topic keywords may change but are still very general in the studies referring to the topic "Self-organized criticality".

Fusion. We can examine fusion events, such as the evolution of the community in red with the highest frequent topic keywords "expression":

• the community molecular biological:protein and molecular biological:gene merge into the community molecular biology at t =1990 -1999;

• the community molecular biology combines molecular biology: saccharomyces cerevisiae and fission yeast at t =1995-2004;

• the community molecular biology joins the community immunology at t =2000-2009.

By analyzing in details high frequent topic keywords, we observe the effects of merge events. At t =1990 -1999, the merging cluster molecular biology contains many high frequent topic key workds like "complex", "binding", "messenger-RNA" and "escherichiacoli". Remark that "complex", "binding" have high frequency in the previous cluster molecular biology: protein, and "messenger-RNA" and "escherichia-coli" also have high frequency in the previous cluster molecular biology:gene. It means that the merging cluster is similar to the original clusters. Furthermore, the new formed cluster reflects the cooperation between the merged topics or fields. This kind of behavior is helpful to capture history of complex systems, and other new science topics or disciplines.

Split. We analyse split events. For example, the community neural networks is split into three distinct clusters neural networks, genetic algorithm and computation theory in networks at t =1995 -2004. This change reflects the link between the new clusters and original communities: the genetic algorithm and computation theory in networks seem to be popular approaches to study neural networks.

Our observation over the structural changes have shown the benefits of the computational technique to analyze the history of science. First, it shows important information about science evolution, such as topic evolution, new topic or field emergence. Secondly, it is a good method to analyze cooperation between topics or fields, merge events enable to capture the cooperation between a priori distinct topics or fields. Finally, it is helpful to analyze how a new topic or filed emerges in views of community dynamics.

Robust cluster evolution and overlaps evolution

We use modular overlaps to discuss effects of overlapping nodes in structural changes in dynamic networks. Our approach is different from current academic work on structural properties. For instance, Balazs Vedres and David Stark [START_REF] Vedres | Structural folds: Generative disruption in overlapping groups[END_REF] studied the contribution of overlapping nodes to the structural changes and demonstrated that the overlapping nodes are correlated with interwoven lineages, which are ongoing patterns of separation and reunification. Our studies on overlapping nodes are from an evolution perspective and the aim is to better understand how overlapping nodes may explain field evolution.

We study modular overlaps of each snapshot graph, whose results are shown in Tab. B.10, Tab. B.11, Tab. B.12 and Tab. B.13. We observe several modular overlaps over time. For example, the cluster malaria transmission and mosquito is shared by ecosystems, molecular biology: serum and hormone and neuroscience at t =1990 -1999. The cluster cellular automata is shared by chaos theory and timeless (gene) at t =1995 -2004. The cluster genetic association is shared by molecular biology and biological psychology at t =2000 -2009. These modular overlaps enable to link different fields, such as cellular automata, it is a popular model used in chaos theory and gene studies.

The Fig. 3.9 shows the results of tracing robust cluster evolution when they contain modular overlaps evolution. We see that modular overlaps may change their community memberships in partitions, such as the modular overlaps visual cortex, which emerges and becomes one robust cluster of the community neural networks at t =1995 -2004, and changes its community membership in the partition at t =2000 -2009: it becomes one robust cluster of neuroscience. This case reveals that network evolution may change overlapping nodes performance. It also suggests us to consider overlapping nodes when studying community evolution.

Robust cluster evolution provides an excellent method for examining evolution of modular overlaps. By using robust cluster identification, we can follow their community membership evolution, and analyze the effects of modular overlaps in structural changes. In some cases, we can see that our method can provide reliable information for tracing community cores. For example, at t =1995 -2004, the community immunology joins into the community neuroscience. At t =2000 -2009, we can trace the evolution of the community immunology through its core, which is marked by "DCs" in Fig. 3.9.

Discussion and conclusion

Our empirical results show that structural changes can reveal the emergence of new topics or fields. For example, we observe the community computation science appearing at t =1995 -2004. As the community computation science is the result of a split of neural networks, it implies the intrinsic existence of a link between computation science and neural networks. Through citation analysis in the cluster computation theory in networks like "algorithm", "stability", "networks", we learn that many computational algorithms are used to analyse networks. Although this result fails to capture how research topics or fields (computation science, ecosystems,...) are formed in the complex system science, it sheds lights on how to understand complex system science and history. Many topics or fields are used to describe experimental work like neural networks, self-organization criticality while new topics or fields come from modelling practices or theoretical applications like computation science.

Our framework supports modular overlaps and enables to trace their evolution. In the complex system science studies, modular overlaps refer to collaborations between distinct topic of fields, such as visual cortex which is a topic relating to neuroscience and neural networks. In other contexts of citation analysis such as the analysis on biology and social systems [START_REF] Lazer | Computational social science[END_REF], modular overlaps may refer to interdisciplinary collaborations, which are essential scientific challenges. As our framework is able to trace modular overlaps evolution, it provides new insights in understanding the history of interdisciplinary evolution.

Many studies on co-citation networks endeavours to mine the evolution of science construction and expect to give insights into field mobility or paradigm shift. The field mobility describes how one author changes its topic over time [START_REF] Hellsten | Self-citations, coauthorships and keywords: A new approach to scientists' field mobility?[END_REF]. The paradigm shift is proposed by Thomas Kuhn [START_REF] Kuhn | The Structure of Scientific Revolutions[END_REF]. The author describes a discipline change in views of paradigm, where a paradigm is a scientific community. The results of field mobility is measured through a function of publications over time. The field mobility is defined as scientists moving into new research topics. Corresponding to the performance of our method, it seems that both paradigm shift and field mobility can be captured by analysing community dynamics.

Chapter 4

Conclusion 4.1 Summary

In this thesis, we have explored computational techniques to study community organization of complex networks with overlapping nodes. It is known that finding the communities within a network is a powerful tool for understanding the structure and the functioning of the network, and its dynamic mechanisms. In Section 1.1, we have described the definition of communities. Lately, we focus on the current problem in community detection. The two major problems concerning community detection are overlapping community detection and dynamic community detection.

In Chapter 1, we have discussed current research on the problem of community detection in dynamic networks, which have left us with a number of important open issues such as benchmark graphs. From our exposition it appears that current methods can be classified into three categories: two-stage methods, evolutionary clustering and coupling graph clustering. Different problems are raised by them, respectively.

Communities may overlap in real networks. In Chapter 2, we proposed a quality function for measuring the quality of covers and two definitions for overlapping nodes: granular overlaps and modular overlaps. For both definitions, we proposed a method called clique optimization to detect granular overlaps and also proposed a method named fuzzy detection to capture modular overlaps. Both methods have been applied to synthetic networks and real networks. The obtained results have shown that both methods can be used for characterizing overlapping nodes but in distinct and complementary views.

In Chapter 3, we have explored a mapping method and a visualization tool to study community evolution in dynamic networks. We have applied the definition of predecessor/successor relationship to track community evolution and identify community dynamics. The visualization tool of lineage diagrams has been introduced. It enables to show and explore the evolution of dynamic communities. We have conducted experiments with real data sets to assess the applicability of the proposed methods. The experiments have shown that the algorithms achieve the goals they are designed for.

Future works

This work is a first step in a more global research on dynamic networks. Next, we will apply our methods to the visual tool, such as in Fig. 4.1. (Communities are identified by colors. Among different communities, it is overlapping nodes that connect them such as the overlapping node labelled by "little".) Of course, many effects will be made. It is still a problem to visualize the evolution of overlapping communities, in particular the evolution of overlapping nodes. Moreover, our method for detecting community evolution needs additional improvements and require further investigations. For example, our method is desirable to detect and analyse the evolution of communities in large, noisy networks that exhibit a high number of changes over time. But it fails to identify artificial community changes, which are caused by the community detection algorithm itself. If we want to improve the accuracy of our method, it is better to add more constraints to smooth the shifts of community members. We hope to mine more time-dependent structural properties, in particular the structural properties about overlapping nodes. For instance, Asur et al. [START_REF] Asur | An event-based framework for characterizing the evolutionary behavior of interaction graphs[END_REF] have measured the sociability index, which gave high scores to nodes that were involved in interactions with different groups. Their analysis showed that the sociability index could be used to predict future co-occurrences of nodes in clusters. It is not difficult to measure the sociability index of overlapping nodes. Then we can analyse the influence of overlapping nodes to future community evolution. It is meaningful to take overlapping nodes into account for studying structural properties.

Several problems remain in community detection such as benchmark graphs. We have reviewed benchmarks [START_REF] Chen | Detecting and Tracking Community Dynamics in Evolutionary Networks[END_REF][START_REF] Duan | Community mining on dynamic weighted directed graphs[END_REF][START_REF] Greene | Tracking the evolution of communities in dynamic social networks[END_REF] in Section 1.4. The current computer-generated benchmark graphs for community detection in dynamic graphs, are constructed by randomly changing interactions between nodes. In these benchmarks, most changes on topology correspond to a predefined probability, that is, the nodes belonging to the same community change their neighbours with the same probability. However, in real networks, changes on topologies should be heterogeneous.

Therefore, it is better to validate the proposed algorithm by applying it to real network benchmarks. In [START_REF] Mucha | Community structure in time-dependent, multiscale, and multiplex networks[END_REF], some real networks are used as benchmark graphs. These real networks do not have any topology change. They only change the resolution scale by varying the resolution parameter. We need real network benchmarks whose community evolution is analysed and known a priori.

Offering benchmark graphs is a crucial problem in the area of community detection in dynamic networks. [START_REF] Newman | Finding community structure in networks using the eigenvectors of matrices[END_REF]. The observed overlapping communities are detected by our clique optimization. The community membership is shown by color such that the nodes belonging to the same community are in the same colour. For the visualisation, we only show internal edges. Between different communities, all observed connections are adjacent to overlapping nodes. Moreover, the color of overlapping nodes correspond to the number of community memberships: if a node is in green such as the node labelled by "pretty", it is shared by two communities; if it is in rose, it is shared by 4 communities. We observe that the overlapping node in rose labelled by "little" combines several communities such as the community in red describing manner ("manner", "way", "natural", etc. ), the community in blue describing place ("place","room","door", etc. ), the community in green describing people ("child","boy","mother", etc. ) and the community in violet describing eye and hand ("eye", "hand", "black", "strong", etc. ). Therefore, "little" seems important for these descriptions.

• Q. Wang

Figure 1 . 1 :

 11 Figure 1.1: A hierarchical tree or dendrogram illustrating the hierarchical form of organization described here. The circles at the bottom of the figure represent the individual nodes of the network.As we move up the tree, the nodes join together to form larger and larger communities, as indicated by the lines, until we reach the top, where all are joined together in a single community. Alternatively, the dendrogram depicts an initially connected network splitting into smaller and smaller communities as we go from top to bottom. A cross section of the tree at any level, such the one indicated by a dotted line, will give the communities at that level. The vertical height of the split points in the tree are indicative only of the order in which the splits or joins take place, although it is possible to construct more elaborate dendrograms in which these heights contain other information. The figure is obtained from Ref.[START_REF] Newman | Finding and evaluating community structure in networks[END_REF].

Figure 1 . 3 :

 13 Figure 1.3: Examples of community evolution over three snapshot graphs by matching temporal clusters to dynamic communities. We observe 4 dynamic communities, indicated by colours: C 1 in dark blue, C 2 in red, C 3 in green and C 4 in light blue. During their evolution, we observe the community C 1 is split into C 1 and C 2 between t and t + 1.

Figure 1 . 4 :

 14 Figure 1.4: An example of a coupling graph, where graphs at different time steps are connected through couplings. The real interactions between nodes are shown in solid lines while the coupling interactions are denoted by dotted lines. The figure is gained from Ref. [62].

Figure 1 . 7 :

 17 Figure 1.7: An example of an union graph which is constructed by jointing two graphs at time t and t + 1. The figure is obtained from Ref. [97].

Figure 1 . 8 :

 18 Figure 1.8: Schematic of a multislice (couplings) network. Four slices s = {1, 2, 3, 4} represented by adjacencies A ijs encode intra-slice connections (solid). Inter-slice connections (dashed) are encoded by C jrs , specifying coupling of node j to itself between slices r and s. For clarity, inter-slice couplings are shown for only two nodes and depict two different types of couplings: (1) coupling between neighboring slices, appropriate for ordered slices; and (2) all-to-all inter-slice coupling, appropriate for categorical slices. The figure is gained from Ref. [88].

Figure 1 . 9 :

 19 Figure 1.9: The R-MAT model. The figure is gained from Ref. [20].

Figure 1 . 10 :

 110 Figure 1.10: Multislice community detection of the Zachary Karate Club network [133] across multiple resolutions. Colors depict community assignments of the 34 nodes in each of the 16 slices (with resolution parameters γ Δ = {0.25, 0.5, . . . , 4}), for ω = 0 (top), ω = 0.1 (middle), and ω = 1 (bottom). Dashed lines bound the communities obtained using Newman-Girvan modularity [95]. The figure is gained from Ref. [88].

Figure 2 . 1 :

 21 Figure 2.1: Example of [•] p ij , where the union of clusters n 1 and n 2 is n r such that n 1 ∪ n 2 = n r and the cluster n s belongs to the rest of the graph.

Figure 2 . 2 :

 22 Figure 2.2: Let us denote the union of the clusters n 0 and n 1 by n 01 . Similarly, we denote the union of the clusters n 0 and n 2 by n 02 , the union of the clusters n r and n s by n rs , the union of the clusters n 1 , n r and n s by n rs1 and the union of the clusters n 2 , n r and n s by n rs2 . Three different subdivisions of the community n 3 : (a) two disjoint subcommunities n 1 , n 2 ; (b) two overlapping sub-communities n 01 , n 02 sharing a cluster n 0 ; and (c) two overlapping sub-communities n rs1 , n rs2 sharing two clusters n r , n s , where n r , n s are disjoint sub-communities of n 0 such as n r ∩ n s = ∅ and n r ∪ n s = n 0 .

Figure 2 . 3 :

 23 Figure 2.3: Two different partitions given by a partition detection method. One partition is shown in green and the other is in red. Both partitions have the same modularity.

Algorithm 3 1 :

 31 Clique optimizationInput: G = (V, E), k Output: S = {S 1 , . . . , S nc } an overlapping community covering of V Obtain a partition P = {C 1 , . . . , C nc } by running an efficient partition detection algorithm on the graph G. 2: S ← P // STEP 1: Find cliques which are k-adjacent to communities 3: for all Edges connecting one granular overlapping node candidate do 4:

Figure 2 . 4 :

 24 Figure 2.4: Tests of our clique optimization on computer generated networks with known community structure and comparison with CPM[START_REF] Palla | Uncovering the overlapping community structure of complex networks in nature and society[END_REF], CORPA[START_REF] Gregory | Finding overlapping communities in networks by label propagation[END_REF] and OSLOM[START_REF] Gregory | Finding overlapping communities in networks by label propagation[END_REF]. Here, x-axis denotes the varying mixing parameter µ and y-axis represents the average NMI of 50 samples by comparing the found community structure and the ground truth. Besides the number of nodes N , the number of overlapping nodes on and the tunable parameter µ, the other parameters are identical: average degree k = 20, maximum degree max k = 300, minus exponent for the degree sequence t 1 = 2, minus exponent for the community size distribution t 2 = 1, minimum community sizes min c = 10, maximum for community max c = 300, and number of memberships of overlapping nodes om = 2.

Figure 2 . 5 :

 25 Figure 2.5: Graphical representation of three different types of yeast interactome datasets. (taken from High-Quality Binary Protein Interaction Map of the Yeast Interactome Network, Yu et al., Science 2008.)

Figure 2 . 6 :Algorithm 5

 265 Figure 2.6: As the number of runs increases, the shape of the function value Eq. 2.12 gets closer and closer to 0. The figure shows results on College football[START_REF] Girvan | Community structure in social and biological networks[END_REF], Karate club[START_REF] Zachary | An information flow model for conflict and fission in small groups[END_REF] and Word adjacencies[START_REF] Newman | Finding community structure in networks using the eigenvectors of matrices[END_REF].

Figure 2 . 7 :

 27 Figure 2.7: Illustration of our fuzzy detection on a toy graph which consists of two overlapping cliques. After removing all edges in low probability p ij = 50% shown in red, robust clusters are obtained, concluding {v 1 , v 2 , v 3 , v 4 , v 5 }, {v 6 , v 7 , v 8 , v 9 , v 10 }, and a single v 0 .

Figure 2 . 9 :

 29 Figure2.9: The co-appearance matrix of synthetic networks containing a hierarchical structure. The color corresponds to the probability of nodes to be in the same community: the darker the color, the higher the probability; color is white if the probability is 0.0.

Figure 2 . 10 :

 210 Figure 2.10: The co-appearance matrix of artificial networks containing hierarchical structure. The color corresponds to the probability of nodes in the same community: the deep color represents the high probability; the color is white if the probability is 0%.

Figure 2 .

 2 Figure2.11: The co-appearance matrix of college football network by running our fuzzy detection. We order the nodes corresponding to their conferences and mark the conference indices. The color corresponds to the probability of nodes in the same community: the deep color represents the high probability; the color is white if the probability is 0%.

Figure 2 . 12 :

 212 Figure 2.12: The community structure of Complex System Science, in which communities are identified by research topics or theoretical fields.

Figure 2 . 13 :

 213 Figure 2.13: Results of fuzzy detection on Complex System Science. Robust clusters are marked by the highest frequent topic keywords. Their colors correspond to the relevant communities as shown in Fig. 2.12.

9 Figure 2 . 14 :

 9214 Figure 2.14: Relative performances of clique optimization for the Geography Collaboration network when k =[START_REF] Aynaud | Détection de communautés dans les réseaux dynamiques[END_REF][START_REF] Batagelj | Generalized blockmodeling of two-mode network data[END_REF]. The number of overlaps decreases 2.14 (a) as k is increasing. The modularity value increases 2.14 (b) as k is increasing. We notice that the modularity of the community structure containing overlapping nodes is less than the partition whose modularity is 0.620506.

Figure 2 . 15 :

 215 Figure 2.15: Statistics of clique optimization for Geography Collaboration at k = 4, 6, 8, 10. (a) the cumulative distribution function of the membership number of overlapping nodes (b) the cumulative distribution function of the overlap size, (c) the cumulative distribution function of p out which is the portion of the sum weights on external degrees to the sum of the weights on the total degrees for a overlapping node.

Figure 2 .

 2 15 (b) shows the overlap size distributions for pairs of communities found in the network. We observe that most pairs of communities share 1 or 0 overlapping nodes: 56% for k = 4 and 79% for k = 10. It is a very good agreement between the relevant statistic distributions that overlapping nodes are not very common. Finally the distributions of the portion of the sum weights on external degrees are shown in Fig.2.15 (c). we note all overlapping nodes having p out < 50%.

Figure 2 . 16 :

 216 Figure 2.16: Community structure of Geography Collaboration. The figure illustrates communities by different colors. We find the found communities corresponding to countries, where each country can be identified by its geographic boundaries.

Figure 2 . 17 :

 217 Figure 2.17: Performances of fuzzy detecting in networks for p c j ,c i between pairs of robust clusters, where robust clusters are sorted by their size in ascending order.

Figure 2 . 18 :

 218 Figure 2.18: Performances of fuzzy detection in Geographical Collaboration and Wikipedia vote network, where the value of the modularity corresponds to the community structure obtained by the relevant β * . Several critical points for modularity are observed.

Figure 3 . 1 :

 31 Figure 3.1: Diagrams of four communities observed during four time steps, featuring continuation, creation, disappearance, fusion and split.

Figure 3 . 2 :

 32 Figure 3.2: Diagram of four clusters observed during over 4 time steps, featuring fusion and split community events.

Figure 3 . 4 :

 34 Figure 3.4: Example of mapping between communities. In the bottom networks, the darker colors represent nodes that are clustered together in at least 95% of the 1000 bootstrap networks. The alluvial diagram highlights and summarizes the structural changes between the time 1 and time 2 significance clusters. The height of each block represents the volume of flow through the cluster. The clusters are ordered from bottom to top by their size, with mutually nonsignificant clusters placed together and separated by a third of the standard spacing. The orange module merges with the red module, but the nodes are not clustered together in 95% of the bootstrap networks. The blue module splits, but the significant nodes in the blue and purple modules are clustered together in more than 5% of the bootstrap networks. The figure is obtained from [108].

  labelled by the class in the highest level

Figure 3 . 6 :

 36 Figure 3.6: Applying our method to a blogs network.

Figure 3 . 7 :

 37 Figure 3.7: An example of sliding window with overlaps. The interval size is 2 with an overlap of 1.

Figure 3 . 8 :

 38 Figure 3.8: Results of our framework on the past history of complex system science network. Temporal clusters are marked by the most popular topic keywords. Their colors correspond to the relevant communities as shown in Fig. 2.12.

Figure 3 . 9 :

 39 Figure 3.9: Results of our framework on the past history of complex system science network. Robust clusters are marked by the most popular topic keywords. Their colors correspond to the relevant communities as shown in Fig.2.12.

Figure 4 . 1 :

 41 Figure 4.1: The community structure of adjacency network of common adjectives and nouns in the novel David Copperfield by Charles Dickens[START_REF] Newman | Finding community structure in networks using the eigenvectors of matrices[END_REF]. The observed overlapping communities are detected by our clique optimization. The community membership is shown by color such that the nodes belonging to the same community are in the same colour. For the visualisation, we only show internal edges. Between different communities, all observed connections are adjacent to overlapping nodes. Moreover, the color of overlapping nodes correspond to the number of community memberships: if a node is in green such as the node labelled by "pretty", it is shared by two communities; if it is in rose, it is shared by 4 communities. We observe that the overlapping node in rose labelled by "little" combines several communities such as the community in red describing manner ("manner", "way", "natural", etc. ), the community in blue describing place ("place","room","door", etc. ), the community in green describing people ("child","boy","mother", etc. ) and the community in violet describing eye and hand ("eye", "hand", "black", "strong", etc. ). Therefore, "little" seems important for these descriptions.

  1) and C j (t + 1) if κ% of nodes belonging to C i (t) are in two different clusters at time t + 1, such as

The dendrogram is produced from a top down approach: the network is split into different communities with successive removals of links. The leaves of the dendrogram are individual nodes.

  .6.

	Algorithm 1 Hierarchical edge betweenness clustering
	Input: G = (V, E)
	Output: A dendrogram
	repeat
	Compute edge betweenness for all edges
	Remove edge with highest betweenness
	until no more edges in graph
	Return a dendrogram //

  [START_REF] Asur | An event-based framework for characterizing the evolutionary behavior of interaction graphs[END_REF] where for each community C s , we note m ss the number of links within C s , m sr represents the number of links between a community C s and another community C r , [m ss ] p ij and [m sr ] p ij are the expected number of links given a link distribution p ij . The cohesion of C s is noted c s and a sr represents the adhesion between a community C s and another community C r .We can assume diverse expressions of [•] p ij , which is an expectation under the link distribution p ij . In case of Fig.2.1 for disjoint clusters n 1 and n 2 , the choice should satisfy the following:1. when n s is a cluster belonging to the rest of the graph, [m 1s

Table 2 .

 2

1: Results of different overlapping community detections on Yeast protein complexes, in views of NMI, sensitivity, specificity, accuracy and modularity. The results of fuzzy detection are used to show its performance in identifying granular overlaps. As we can see, its advantage is not obvious.

Table 2 .

 2 2: Part results of popular overlapping nodes which are shared by 8 communities for k = 4 (which are still popular for k = 5). These popular overlapping nodes are related to big cities or regions having famous universities.

		Location	Node	Location
	DE122 Karlsruhe, Stadtkreis	ES300	Madrid
	ES523	Valencia	FR101	Paris
	FR716	Rhône	ITC11	Torino
	ITC45	Milano	ITD36	Padova
	ITD55	Bologna	NL326	Amsterdam
	SE010	Stockholm County	SE044 Skane County
	UKD52	Liverpool	UKJ14	Oxfordshire

Table 3 .

 3 1: Results of our method on hide dataset where 10% of communities are unobserved from time t = 2 onwards. In views of reappeared community number, i.e., number of observed reappeared community (NOC) and number of expected reappeared community (NEC), our results are similar to the real ground truth. For instance at time t = 3, we observed 48 reappeared communities through our method, while the ground truth is that 50 communities reappear. In views of the mean positive predictive value (Mean PPV), our results gave a really high mean PPV value. Especially at t = 4 and t = 5, the mean PPV value is 1. It reveals that all nodes belonging to the observed reappeared communities totally match to the reality. The comparison between the number of true positive nodes and the number of the reality (NPOCM/NECM) shows that how many nodes belonging to the reappeared communities in the ground truth are found by our methods. As we can see, our framework has good performance in detecting reappeared communities.

	Time NOC/NEC Mean PPV	SE	NPOCM/NECM
	t=3	48/50	0.95826	0.199826	1152/1198
	t=4	45/48	1	0	1244/1283
	t=5	41/47	1	0	1096/1155

Table 3 .

 3 2: Properties of the past history of Complex System Sciences.

	5 ;

Table 3 .

 3 3: Stability values of clusters and core nodes between every pair of consecutive snapshot graphs. Mean and standard deviation are given.

	Time transition	Mean stability(� c)	std(� c)	Mean stability(C)	std(C)
	From 1985-1994	0.916185	0.0830868	0.740646	0.152708
	to 1990-1999
	From 1990-1999	0.944751	0.0556874	0.812754	0.126775
	to 1995-2004
	From 1995-2004	0.825698	0.302496	0.778244	0.151847
	to 2000-2009

Table B .

 B and E.Fleury, Fuzzy community structure and modular overlaps, SNSI2012 (Studies in Mining Social Networks and Security Informatics by Springer Verlag) (en review) • Thomas Aynaud, Eric Fleury, Jean-Loup Guillaume, Qinna Wang, Communities in evolving networks: definitions, detection and analysis techniques, en preparation • Q.Wang and E.Fleury, Overlapping time-dependent community detection in dynamic networks, en preparation A.4 Seminars • Q.Wang and E.Fleury, Fuzziness and overlapping communities in large-scale networks Journées non thématique Octobre, Paris, 2011. • Q.Wang and E.Fleury, Mining time-dependent communities Journées automnales ResCom, Lyon, 2010 Table B.3: Results of clique optimization at k=6: ten high frequent topic keywords contained by granular overlaps between pairs of communities. These high frequent topic keywords are contained in at least 20 articles and are shown in order of descending frequency. The highest frequent topic keywords are shown in bold font. 11: Results of fuzzy detection during 1990-1999: ten high-frequent topic keywords contained by modular overlaps between pairs of communities. These high frequent topic keywords are contained in at least 15 articles and are shown in order of descending frequency. The highest frequent topic keywords are shown in bold font. Turbulence, Ism : Clouds, Star-Formation, Stars : Formation, Molecular Clouds, Ism : Structure, Ism : Kinematics And Dynamics, Evolution, Radio Lines : Ism, Intergalactic Medium

	SOC	Complex Networks,	Dynamics, Organiza-	tion, Saccharomyces-	Cerevisiae, Model,	Evolution	Dynamics, Self-	Organized Criticality,	Time-Series, Systems,	Chaos, Complexity,	Model, Complex Net-	works, Econophysics,	Synchronization
	Ecosystems Cluster Chemical: Adsorp-tion Industrial And Cluster Organizational Genetic Association		Dynamics, Self-Adsorption, Complexation, Speciation, Sorption, Organization, Model, Chaos, High frequent topic keywords Stability, Cadmium, Copper, Ph, Natural-Waters, Transport, Zinc Complexity, Systems, Management, Organizations, Model, Performance, High frequent topic keywords Patterns Economics, Organization, Innovation, United-States, Association, Susceptibility, Polymorphism, Linkage Disequilib-Involving commu-nities Ecosystems, Molecular Biol-ogy: Serum And Hormone, Dynam-ics Turbulence Ecosystems, Molecular Bi-Involving communities ology: Serum Molecular Biology, Bi-
	Psychology					Industry, Complexity rium, Disease, Major Histocompatibility Complex, Linkage, Com-And	Hormone, ological Psychology
	Semiconductor super-Malaria Transmis-lattice materials and growth technology sion And Mosquito Discrete-Event Sys-tems Computational Com-plexity Protein Expression: Binding Astronomy-Ism(Interstellar	Self-Organization, Malaria, Culicidae, Transmission, Diptera, Complex, Superlattices, Nanoparticles, Clus-ters, Quantum Dots, Total-Energy Calcu-lations, Nanocrys-tals, Self-Organized Growth, Nanostruc-Identification, Anopheles-Gambiae Complex, West-Africa plex Traits, Risk, Population Systems, Supervisory Control, Petri Nets, Complexity, Discrete-Neuroscience Ecosystems, Molecular ogy: Serum And Biol-Hormone, Dynam-ics Turbulence Event Systems, Verification, Design, Automata, Synchronization, Discrete Event Systems Computer Ecosystems Complexity, Algorithms, Computational Complexity, Algorithm, Networks, Optimization, Time, Systems, Search, Computational-Computer Ecosystems tures, Wave Basis-Set Binding, Expression, Complex, Protein, Cells, Rat, Messenger-Rna, Escherichia-Coli, Purification, Phosphorylation Complexity Metabolic Control Dynamics Turbulence, Science, Science, Analysis, Genetics Clinical Psychology
	Medium)													Molecular Biology:
	Complex networks Systems neuroscience Structural Molecular Biology Saccharomyces-Cerevisiae, Identification, Yeast, Gene-Expression, Patterns, Cell-And Multi-Agent Systems Protein Cell Physiology: Cell Signaling Molecular Biology: Metabolism Mitochondria And Visual Cortex Protein Expression:	Cycle, Database, Complex	Networks, Neural-Network, Escherichia-Coli, Crystal-Structure, Resolution, Binding, Self-Organizing Maps Synchronization, Sys-tems, Dynamics, Com-plex Networks, Chaos, Model, Self-Organized Criticality, Stability, lators Chaotic Systems, Oscil-Chaos, Systems, Neural Net-works, Dynamics, Complexity, Time-Series, Model, Stability, Communication, Synchroniza-tion Neurons, Model, Epistasis, Multifactor-Dimensionality Reduction, Primary Visual-Cortex, Receptive-Fields, Mechanism, Complex, 3-Dimensional Structure Systems, Multi-Agent Systems, Multiagent Systems, Design, Saccharomyces Cerevisiae Fission Yeast, And Agents, Architecture, Multi-Agent System, Framework, Model, In-telligent Agents Computer Ecosystems Association, Complex Cells, Genetics Identification, Binding, Cells, Escherichia-Coli, Gene Analysis, Genetics Signal Transduction, Map Kinase, Phosphorylation, Signal-Transduction, Activation, Ras, Tyrosine Phosphorylation, Activated Protein-Kinase, Epidermal Growth-Factor, Cells Molecular Biology: Saccharomyces Cerevisiae And Fission Yeast, Genetics Cells, Expression, Inhibition, Liver Analysis, Genetics Metabolism, Mitochondria, Complex, Brain, Binding, Rat, Metabolic Control Complex Cells, Lateral Geniculate-Nucleus, Cat Striate Cor-Receptive-Fields, Contrast, Orientation Selectivity, Simple Cells Biological Psychology, Science, Cortex, Natural Images Proteins, Expression, Complex, Purification, Protein, Metabolic Control tex, Primary Visual-Cortex, Striate Cortex, Cortical-Neurons, Systems Neuroscience
		Molecular biol-	ogy				Chaos theory						Biological Psy-	chology	Spectroscopy

Table B .

 B 13: Results of fuzzy detection during 2000-2009: ten high-frequent topic keywords contained by modular overlaps between pairs of communities. These high frequent topic keywords are contained in at least 15 articles and are shown in order of descending frequency. The highest frequent topic keywords are shown in bold font. ������� ��������� ���� ������� ��� �� ������������ �� �������� ����� ���� ��� �������� �� ��������� ��� ������� ���� ����������� ��� ������ ������� �� �������� ���� ��� �������� ���������� ���� ��� ��������� ����� ���� ���� ��� ������� �� ������������� ��� ������� �� ��������������� ��� ������� ������������� ������ �������� ��� ������ ���� ������ ���� ���������� �� ������ ������ ���� ��� ����� ���� ������ ��� ��� ������������ �������������������������� ���������� ��� ������ ���� ��� ������� ��������� ���������� �� ������� ��������� ���� �� ���������� ��� ������ ��� ��� ����������� ��� ���� �������� ��� ��� ������� ������ ������ �� ��� ������� ����������� ��� �������� ��� �������� ��� ���������� �������������� ��� �� �� ���� ������� ��� ���� ��� ������� ������� ���� ��� �� ������� �� �������� �� ��� ������� ����� ������� ���� � �������� �� ����� ������������� ��� ������ ��� ��� ���������� ��� ������� ������ ��������� ����������� �� ������� ��� ������� �� ��������� �������� � ������� ��� ����� �� ��������� ���������� �� ���������������� ��� �������� ���������� ��� � ������ ��� �� ������������� ��� ���������� �� ������������ ��� ������ ���������� ��� ��� ������� ��������� ���� ��� ����� ���� ���� ��� ������� ��������� ���������� ��� ������� �� ������������ ���� � ������� �� �������� ��� ����� ������������� �� ������ ��� ��� ���������������� �������������� ��� ������ ��� ��������� �������� ��� �� ������������ ��� ������ ��� ����� ����� ��� ��������� ������������� ��� ���������� �� ������� �������� ���� ����� ����� ����� ����������� �� �������� ����� ��� ������� ������� ���� ������� ��� ��� ������������ ���� ��� ���������� ������ �� ���� ���� �� ��� ���������� ������� ����� ���� �� ��������� �� �� ���������� ���� ������ ���� ����� ��� ��������� �� �������� �� �� ���������� ���� ����� �� ������ ��� ��������� �� ������� � ���� ��� ������� �� ��������� ���������� ��� ����������� ������������� � ��� ��������� ���������� � ���� �� ����� ���� ���� ��� ����� ��� ����� ��� ��� ������ � ���� ��� ������� ����������� ��� ���������� ���� � ��� �������������� ���� � ��� ������ ��� �� ��������� �� ����������� ��������� �������� � ��� ��������� ������������� ��� �������� ���������� ��������� �� ����������� ��� �� �������� ��� ���������� ��������������� �������� ���������� ���� ��������� �� ���� ���������� � ��� ������� ������ ��� ����� ����� �� �������� ��� ������� �� �������� ������� �� ���������� ��������������� ��� ����� � �� ���� ��� ����������� �� ���������� ������ �� ������� ��� ����������� �� ��������������� �� ������ �������� ��� ������ �� ����������� ����������� ������ ��� �� ������ �������� ����� ��� ������� ��� ������� � ���� �� ������� ��������� ���� �� ����� ������ �� ������ ��� ������� �� ������ ����� ������� ��� � �������� ��� ������ ������ ����� ��� ����������� ���� ������������� ������� ���� ������� ����������� ��� ������������ �� �������� � ��������� ��� ������ �������� ���� �� �������� �� �� ���������� ��������� �������� �������� ��� ��� ���������� ��� �������� �������������� �� �� ���������� ��� �� ������� �� ���� ��������� ���� �� ������ ���� �� ����������� ���� ��� ������ �������� ��� ����������� ���������� ���� ����� ��� ��� ���������� ��������� � ���� ������� ��� ������� ���������� �� �� ���������������� �� ��������� ����� ��� �������� ������ ��� ����������� ����������� � ��������� ����������� �������������� �� ��������� �� ������ �� �� ������� �� �������������� ��� �������� ����������� �� ������ ������������ ���� �� ��������� �� ������������ �� ��� ��� ���������� � �� ������� ����� ���� ���� �������� �� ��������� �� ����������� ������������� ������ �������� ������ ���� ������������ � �� ����� ���� ������� ��� ������ ����� ������� �� ����������� �� �������� ��� ������� ��� ��� ��� ������� ����� ��������� ���������� �� ���� �� ���� ���������� � ������ �� ��������� �� ������ ������� ��������� ���� ������� ���� �������� � ������� �� �������� ���� ��� �������� �� ��� �������� �� ������ �� ������� ������������� ���� ����� ��������� ��� ��� ���������� ��� ������� ����������� ��� �������� �� ������ ��� �������������� �� �������� �������������� ������ ��� ������������ �� �� �� ������ �� ��������� ���� ������ ���� ��� �� �������� �� ����������� �������� ��� ������������ ��� ������������� ��� ��������� �� �������� �� ����� ��� �� ��������� ��� ��� ����������� ���� ��� ������� ���������� ���������� � ��� ��������� ������������ ��� ���������� �� ����������� �� �������� �� � ��� ��������� ��������� ��� ��� ������������� ���������� �� ������������� �� ������� ��� �������� �� ��������� �� ����������� ���� ��������� ���� ��� ������� ���������� �� � � �� ������ ������� ������������� ��� ��������� ��� ���� �������� ���� ��� ������� ����������� �� ������� ������ ��� ��� �� ��������� �� ����������� ������������ ��� �������� �� ��������� �� ������� ��� �������� �� �� ��������� �� ����������� ���� ��������� ���� �������� ��� ����������� ���������� ���� ����� ������������ ��� ����� ����������� ���� �������� ��� ��������� ����������� ��� �� ���������� ���� �� ��������� ������ ��������� ��� ���� ������������ � �������� ��� ��� ������ �� ���� ��� �� ���� ���������������� ����� ��� ������������ ���� �� ���� ������� ���� �� ���������� �� ������������� ��� �������� ��� ����������� ���� ��� �������� ��� ������ ���� ��� ��������� �������������� �������� ����������� �� ������� ��� ������ ����� ��� �������� �� ���������� ��� ��������� ��� ������� �������������� ��� ����� ������������ �� ����� �� ������ ��� ������ ����� ���� �������� � ��� �������� ��������� ����������� ��� ��� ����������� ��� �� �������������� ����� ���������� ���� �� �������� ��� �� ������������ �� ��������� ����������� ������ �� ���������� �� ����� ���������� ��� ��������������� ����������� �� ����� ����������� ���� �� ������������� �� �������������� ������������ ��� �������� ���������� ��� ������ �� ����������� ������������ ������ ������ ���� ���������� ��� ���������� ��� �������� ���������� �� ������� ��� ��������� �������� ���� ��������� ����� ����� ���� ����� ���� � ��������� �� �� ��������� �� ����������� ������������ ���� ��� ������� ��������� ����� ���� ��� ������� ����������� ���� �� ������ ���� �������� ���������� �� �� ��������� �� ����������� ������������ ���� ���������� ���� ���������� ����� ��� ��������� ���� ������ ����������� �� ���������� � �� �� �� ������ ���� ������� ��� ��������� ���� ��� ����� ���������� � ������� ������� ����������� ��� ��������� ������� ���� �������� ��� ������������� ��� ������������� ����������� �� ����� ����� ���� ���������� �������� ���������� � � ���� ������ �� ��� ��������� ��� �� ��������� �� ����� ����������� � ���� ��� ������ ��� ����������� ������������ �� ������������ ��� ����� ������������ ���� ����� ������� ���� ���������� �� ����� ����������� � ��� ����� ����������� ����� ������� �� ��� ������� ������������ ������ ���� ���������� ���������� �� �������� � ��������� ����������� ���� ��� ����� ��������� ������ ������ ���������� ��� �� �������� �� ����� ����� �� ���� ����� �������������� � ��� ���������� ��� ����� �� ������ �� ������ ���������� � �� ����������� ���� �� ����� ���� ������������ ���� �� ��������� �� ����� ����������� ������������ ���� ����� ������� ��������� ������ �� �������� �� ��� ������� ��� ������� ������������ ��� ����������� ���� ������ ��� ������������ ��� � �� ����������� ���� ������� �� ����� � � � ����� ��������� �� ���� ���������� ���������� ���� �� ���� ������ ��� �� ������ ����� ������� ��� ��� �������� � �������� ����������� ���������� �� ������������ ��� ���� �� ���������� �� ���� ���������� ���������� ���� �� ���� ���� ��� ��������� ����� ������� ��� ��� ��������� � �� ����� ���� ����������� �� ���� ������ ����� ����� � ���� ��� ����������� ��� ������� ������������ ���� ��������� �� ������� ������ ��������� ���� ������ ����������� �� ��������� �� ������������ �� ������� � ��������� ��������� ���� ������� �������� �� ����������� ������ ����� �� ������ ������������ ���� ��� ���� ����������� �� ���� ������ �� �������� ��� ������� ��������� ��� ��� ��� ������ ��������� ������ ��� ����� ����������� ������ ����� �� ������ ��������� ���� ������ ������� � ��� ����� ����������� �� ��� ������������ �� ������ ���� ������ �� ������ �� �������� ��� ������ �� �� ���� ������� �� ��� ������� ������������ �� ����� �� �� ���������� ��� �� ������ ������� ������� ���� ��� ����������� �� ������ ���������� ��� �� ������ ��� ����� ����� ��� ����� ����������� �� �������������� ���� ��������� ������������ ��� ������������ �� ��� ���� �������� � ��� ������� �� ��������� ���� ������ ���� ��� ����������� �������� ���� ��� ���������� ��������� � �� ������ ����� ���� ��� ������������ ���� ��������� ��� ��� ���� �������� ������� ��� ��������� ������������� ���� ���������� ���� ������������ ��� ����� ������������ � ����� �� ����������� ��� ����������� �� ������������� �� �� ��������� ��� ���� �������� � ���� ������ ����������� ��� ����������� �� ��������� �� ��������� ��� ������������ ���� ����� ������� ��� ������� �� ���� ������ � ���� �������� ���� ���������� ����� ��������� ���� � �� ��������� �� �� ��������� ������������� � ������ ��� �� ������ �� ������� ���� ����������� �� �������� ����� ��� ����������� � ��� ��� �� ����� ���������� ����� �� ��������� �� �� ����������� �� ������ ��� ��������� ���� ������ �� ������ �� ������������ �� ��������� ��� ������������ ���� �� ��������� ������� �� �� ����������� ������� � ��� �� ����� �������� �� ���������� �� ��������� ��� ������������ ���� ����� ��������� ��� ��������� �� ������������� �������� ���������� �� �������� ��� ��� �������� �� �� ������ ���� ���������� ���������� �� ����� �� ��������� ��� ���� �������� ������� ��� ����� ������� �� �� �� ����� �� ������� ��� ����������� �� ��������� �������� ���� ��� ������������ ����� �������� � ��� ��������� � �� ������ ���������� �� �������� ��������� �� ����� ������� ��� ��� �������� ���� �� ��������� �� �� ��������� ��� ����������� ���� ��� ������� �������� �� ����� �� ������ ��� ����������� ����� ������� ��� ������ �� �������� �� ������� ���� ����������� ��� ����������� ���� ��� ������ �������� �� ������������ ���� ��� ���������� �� ������ ����� �� ����������� �� �� �� ������ ������ �� ����� ����� �� ����� ��� ��������� ����� ����� �� �������� � ��� ��������� �� �� ��������� ���� ���������� ���� ��� ������� ����������� ���� ��������� �� ��������� �� �� ��������� ������������� �� ��� ����������� ��� ����������� �� �� �� ������ �� ��������� �� ����������� ���� ��� ������� ���������� ������� ��� �������� ���������� �� ����� ���� ��� ���� ������� � ��������� ���� ������� �� ����� ��� ����������� ������ ���� ��� ������� ����������� ��� ���� ����� ��� ��� ���������� �� �� ��������� �� ����������� ���� ��� ������� ���������� ���� ��������� ��������� ��� ��������� ��������� ����� �� ����� ���� ��� �������� ������� ���� ������� �� ��������� ����� ������ �� �������� � �������� �� ��������� �� ����������� ������������� ���� ��������� ������������ �� �� ��������� �� ����������� ������������ ���� ��������� ��� ������� �� ��� ������� ��� ����������� ���������� �������� ���� ������������ �� �������� �� �� ������ ���� �� ����������� ������������ �� �������� �� �� ��������� �� ����� ������������ ���� �� ��������� �� ����� ����������� ����������� �� �� ��������� �� ������� ������ ������� ��� ����������� ���� ����� ������� ���� �������� ���������� � �������������� �� ������ �� �� ��������� ����� �� �������� �������� � �������� ��� ����� ����������� ����� ������� �� �� ������� ���� � �������� ��� ������� ������������ ��� ������������ �� ���� �������� ���� ��� ������� ������������ �� ��� ������� ����� ��� �� ������ ������������� �� ������������ ��� ������������ ���� �� ������ �� ���������� ��� �������� ��������� ����� ������� �� �������� �������������� � ��� ���� �������� ����������� ��� ������������ ��� ��� ��������� ����� ��� ������������ ���� ������� ��� ����������� ���� �� �������� � ���� ����������� �� ��������� ��� ����������� ������������ ���� ��� ������� ���������� �� ��������� ��� ������� ����� ��� ��� ������� ������� ������������� ��� ������������ ���� ��� ������� ���������� ������ ��� ���������� �� �� ������� ��� �������� ���������� �������� ��� ��� ����� ����������� ���� ���������� ���� ��� ��������� �� ��� ������������ ������������� ����� ��� ������������ ����� ���� ��������� ���� �� �������� � �� ��������� ����� ������� �� ������� �� ��������� ����������� �� �� ���������� ��� ��� ������������ ��� ������� �� ��������

	��	������ �����������
	�������������� ��������� �� ������� ���������

���

http://www.facebook.com/

In[START_REF] Leskovec | Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters[END_REF], best communities are defined to have a size scale between 10 to 100 nodes. Therefore, when the number of overlapping nodes is above 100, it is better to treat it as a community for the characterization.

Available at http://interactome.dfci.harvard.edu/S_cerevisiae/

We do not mark "Sunbelt2" due to the visualization, since its position is too close to "CentralFlorida" in the figure.

In[START_REF] Leskovec | Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters[END_REF], the community which has size roughly 100 nodes is good.

Between several pairs of communities, their granular overlaps contain more than 100 nodes.

NUTS is a geocode standard for referencing the subdivisions of countries, which is based on the existing national administrative subdivisions.

AIDS-related complex was widely discontinued by the year

in the United States after having been replaced by modern laboratory criteria

Studies have shown our method gives the partition with the highest NMI at l * = 1.

In[START_REF] Leskovec | Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters[END_REF], best communities are defined to have the size scale of between 10 to 100 nodes. This is also the size scale of communities in the synthetic networks. Setting γ * = 5 is able to filter artificial clusters caused by degree variation and guarantee the matched small communities maintaining their most community members.

http://www.webofknowledge.com

One community is not shown in the figures as its frequency of topic key words is really too small and does not allow us to characterize it.

For the visualization, we only show and analyse communities which have size above 100 nodes. In[START_REF] Leskovec | Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters[END_REF], the community which has size roughly 100 nodes is good.

Only 10-15 articles contain them

Remerciements

Algorithm 6 Method for tracking community evolution

Input: An evolving graph G(V, E), which consists of a sequence of snapshot graphs

Visualizing dynamics in communities

In early work, several tools such as SoNIA [START_REF] Moody | Visualizing network dynamics[END_REF] and TeCFlow visualize dynamic networks by creating graph movies, where nodes move as a function of changes in relations. However, these tools fail to indicate a changing behaviour of community memberships and community dynamics. In [START_REF] Mucha | Community structure in time-dependent, multiscale, and multiplex networks[END_REF], matrix is used (Similar as Fig. 1.10), whose element represents the community membership of a node at a time step. Each node occupies a column. Colours are used to depict communities. We can observe how a node changes its community membership through the colour change in the corresponding column. The drawback is that we do not directly observe how one community emerges, merges, splits or disappears.

An example of a graph with dynamic communities is depicted in Fig. 3.4. The evolution path of a dynamic community is depicted by a diagram occupying a column. Each diagram represents a community as a block and show relationships between preceding and succeeding clusters through horizontally connected stream fields. This result is obtained by the algorithm of bootstrap [START_REF] Efron | An Introduction to the Bootstrap[END_REF] in [START_REF] Rosvall | Mapping change in large networks[END_REF]. It enables to show community dynamics. For example, we observe the orange module merges with the red module in Fig. 3.4. In addition, in this case, we are also able to observe the significance of clusters, which is shown by dark colour.

The tool of alluvial diagram seems good in displaying structural change in science, economics, and business. Next, we introduce our visualization tool which has the similar Gaas, Growth, Molecular-Beam Epitaxy, Quantum Dots, Photoluminescence, Islands, Self-Organized Growth, Self-Organization, Surfaces, Ingaas Molecular Biology Expression, Complex, Protein, Binding, Gene, Cells, Messenger-Rna, Escherichia-Coli, Identification, Gene-Expression Table B.7: Partition results in the past history of complex system science during 1990-1999: ten high-frequent topic keywords contained by disjoint communities. These high frequent topic keywords are contained in at least 15 articles and are shown in order of descending frequency. The highest frequent topic keywords are shown in bold font.

List of publications