Qinna Wang
email: qinna.wang@ens-lyon.freric.fleury@inria.fr

Eric Fleury

Fuzziness and Overlapping Communities in Large-Scale Networks

Keywords: fuzzy community detection, overlapping community detection, community detection, modularity, large-scale networks Category: L.3, L.6 Overlaps High Frequent Topic Keywords Involving Communities Genetic Association Association, Susceptibility, Polymorphism, Linkage Disequilibrium, Disease, Major Histocompatibility Complex, Linkage, Complex Traits, Risk, Population Molecular Biology, Neuroscience: Biological Psychology Discrete-event Systems Systems, Supervisory Control, Petri Nets, Complexity, Discrete-Event Systems, Verification, Design, Automata, Synchronization, Discrete Event Systems Computer Science: Communication Systems, Ecosystems Computational Complexity Complexity, Algorithms, Computational Complexity, Algorithm, Networks, Optimization, Time, Systems, Search, Computational-Complexity Computer Science: Communication Systems, Ecosystems Astronomy-ISM (Interstellar Medium) Turbulence, Ism: Clouds, Star-Formation, Stars: Formation, Molecular Clouds, Ism: Structure, Ism: Kinematics And Dynamics, Evolution, Radio Lines: Ism, Intergalactic Medium Dynamics Turbulence, Clinical Psychology Systems, Multi-Agent Systems, Multiagent Systems, Design, Agents, Architecture, Multi-Agent System, Framework, Model, Intelligent Agents Computer Science: Communication Systems, Ecosystems Visual Cortex Complex Cells, Lateral Geniculate-Nucleus, Cat Striate Cortex, Primary Visual-Cortex, Striate Cortex, Cortical-Neurons, Receptive-Fields, Contrast, Orientation Selectivity, Simple Cells Neuroscience: Biological Psychology, Neural Networks Community Cluster High Frequent Topic Keywords Flow Over Turbulence, Model, Flow, Simulation, Complex Terrain Complex Terrain, Large-Eddy Simulation, Flows, Behavior, Boundary-Layer, Plasticity Dynamics Astronomy-Ism Turbulence, Ism : Clouds, Turbulence ( Interstellar Star-Formation, Stars : Formation, Medium ) Ism : Structure, Molecular Clouds, Ism : Kinematics And Dynamics, Evolution, Radio Lines : Ism, Intergalactic Medium Telecommunication Systems, Performance, Channels, System Synchronization, Fading Channels, Capacity, Ofdm, Equalization, Networks, Multiuser Detection Computer Control Theory Systems, Stability, Design, Science: Robust Control, Optimization, Communication Linear-Systems, Model-Predictive Systems Control, Stabilization, H-Infinity Control, Model Predictive Control Wireless Network Ad Hoc Networks, Sensor Networks, Wireless Sensor Networks, Self-Organization, Networks, Wireless Networks, Clustering Cryptography Stream Ciphers, Cryptanalysis, Linear Complexity, Stream Cipher, Sequences Expression Expression, Complex, Gene-Expression, Protein, Saccharomyces-Cerevisiae, Gene, Activation, In-Vivo, Identification, In-Vitro Molecular Dendritic Cells Dendritic Cells, In-Vivo, Expression, Biology T-Cells, Infection, Complex, Mice, Activation, Major Histocompatibility Complex, Antigen Crystal structure Crystal-Structure, Complex, Of Escherichia Coli Escherichia-Coli, Binding, Protein, Recognition, Mechanism, Proteins, Molecular-Dynamics, Complexes Gene Expression Escherichia-Coli, Gene-Expression, In Escherichia Coli Systems, Expression, Model, Networks, Systems Biology, Protein, Transcription, Rhythms Atherosclerosis Atherosclerosis, Inflammation, Expression, Disease, Myocardial-Infarction, In-Vivo, C-Reactive Protein, Smooth-Muscle-Cells, Activation, Low-Density-Lipoprotein Membrane Fusion Membrane-Fusion, And Exocytosis Neurotransmitter Release, Exocytosis, Syntaxin, Snare, Complex, Protein, Snare Complex, Transmitter Release Proteomics Identification, Proteomics, Mass-Spectrometry, Proteins, Peptides, Protein Identification Chaotic Dynamics Chaos, Dynamics, Systems, Complexity, Stability, Model, Time-Series, Synchronization, Nonlinear Dynamics, 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, Search, Computational-Complexity Ecosystems Ecology, Dynamics, Evolution, Biodiversity, Patterns, Diversity, Growth, Model, Management, Conservation Absorption Adsorption, Sorption, Speciation, Complexation, Humic Substances, Water, Natural-Waters, Kinetics, Ph, Copper Cellular Automaton Cellular Automata, Systems, Simulation, Self-Organization, Model, Cellular-Automata, Flow, Cellular-Automaton Model, Traffic Flow, Dynamics Multi-agent Systems, Multi-Agent Systems, Systems Multiagent Systems, Design, Agents, Architecture, Multi-Agent System, Framework, Model, Intelligent Agents Division Of Labor Self-Organization, Behavior, In Insect Societies Division-Of-Labor, Hymenoptera, Ants, Colonies, Formicidae, Social Insects, Swarm Intelligence, Evolution Complex Adaptive Complexity, Self-Organization, Systems Chaos, Emergence, Science, Complex Adaptive Systems, Complexity Theory Malaria Malaria, Culicidae, Identification, Transmission, Complex, Diptera, Africa, Mosquitos, Anopheles-Gambiae Complex, Gambiae Complex Neural Networks Neural Networks, Classification, Systems, Model, Self-Organizing Map, Neural Network, Algorithm, Identification, Artificial Neural Networks, Prediction Neural Networks Genetic Algorithm Optimization, Genetic Algorithms, Genetic Algorithm, Design, Systems, Neural Networks, Model, Algorithm, Algorithms, Simulation Simulated Optimization, Simulated Annealing, Annealing Algorithm, Model Gene Expression Patterns, Self-Organizing Maps, Patterns Gene-Expression, Microarray, Identification, Gene Expression, Saccharomyces-Cerevisiae, Cancer, Expression, Classification Complex Complex Systems Complex Networks, Dynamics, Systems Small-World Networks, Model, Internet, Networks, Evolution, Scale-Free Networks, Systems, Organization

Overlapping community detection is a popular topic in complex networks. As compared to disjoint community structure, overlapping community structure is more suitable to describe networks at a macroscopic level. Overlaps shared by communities play an important role in combining different communities. In this paper, two methods are proposed to detect overlapping community structure. One is called clique optimization, and the other is named fuzzy detection. 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. 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. Experimental studies in synthetic networks and real networks show that both methods provide good performances in detecting overlapping nodes but in different views. In addition, a new extension of modularity is introduced for measuring the quality of overlapping community structure.

Introduction

The empirical information of network datasets can be used to study several characteristics of networks, like small-world property, heavy-tailed degree distributions [START_REF] Albert | An event-based framework for characterizing the evolutionary behavior of interaction graphs[END_REF]] and rumor spreading. These characteristics are closely related to the property of community structure. In the study of complex networks, a network is said to have community structure if the nodes of the network can be easily grouped into sets of nodes such that each set of nodes is densely connected internally, between which connections are sparse.

Modularity optimization is a popular approach to detect partitions of networks. A partition is the division of a network into disjoint communities, where each node belongs to one and only one community. Due to inhomogeneity of link distribution in real networks, the modularity [START_REF] Girvan | Community structure in social and biological networks[END_REF], which compares differences between the number of links within communities and the expected number of links in the null model, can be used to measure the Figure 1: An example of overlapping communities in an adjacency network of common adjectives and nouns in the novel David Copperfield by Charles Dickens [Newman 2006]. The result is obtained by clique optimization [see Section 4], which shows communities through colors: orange denotes community "HUMAN", composed of "boy", "child", "friend", etc. , green represents community "OBJECT", comprised by "door", "house", "room", etc. , and light blue denotes community "HEAD", consisting of "hand", "head", and "eye", etc. . We observe an overlapping node "little", which can be used to describe these subjects. quality of partitions. A good partition usually has the high modularity. Thus, modularity optimization is applied to a lot of datasets for capturing structural properties [START_REF] Guimerà | Functional cartography of complex metabolic networks[END_REF].

However, the modularity fails to measure the quality of covers. A cover is the division of a network into communities which are allowed to share common nodes. Overlaps are the common nodes shared by at least two communities, which play an important role in combining communities. Figure 1 shows an example: the overlapping node "little" can be used to describe humans, like "boy", "child", "friend", and can be used to describe objects, like "door", "house", "room", too.

Several algorithms for overlapping community detection are known in the literature. These methods include CPM [START_REF] Palla | Uncovering the overlapping community structure of complex networks in nature and society[END_REF], fitness-based algorithm [Lancichinetti et al. 2009] and OSLOM [START_REF] Lancichinetti | Finding statistically significant communities in networks[END_REF]]. These algorithms aim at detecting local communities without respect to the graph as a whole. The definition of fuzzy community structure is also used to detect overlapping communities, which considers a community as a group of nodes having high probability together with each other. For example, Reichardt et al. [Reichardt 2004] 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. Both them detect fuzzy community structure by computing the probability that a pair of nodes belong to the same community.

In the following, we will propose a new extension of modularity for measuring the quality of overlapping community structure, which is derived from the Hamiltonian [START_REF] Reichardt | Statistical mechanics of community detection[END_REF]. In addition, we introduce two complement methods to detect covers. We 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/subcommunity. 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.

This paper is organized as follows. Section 2 introduces the current work in cover detection. In [Section 3], we describe our new extension of modularity. In [Section 4] and [Section 5], we present our methods and show their performances by applying them to synthetic networks, respectively. We also compare their performances in analysing real networks in [Section 6]. Finally, we conclude our current work and the prospect for the future, in [Section 7].

Related work

Definition and notation

A complex network is modelled by a graph (network) which is used to describe the topology structure of a complex system. The nodes of the graph are individuals connected by edges which mimic their interactions.

Let us start with a graph G = (V, E) comprising n = |V | nodes (or vertices) connected by m = |E| links (or edges). 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. Given a n× n matrix A = [A ij ] n×n , its element A ij is equal to 1 when the link e ij exists, and zero otherwise.

A group of nodes having denser internal connections than external connections is called a community. Given a community C of a graph G, we define the internal and external degree of node v ∈ C, k int v and k ext v , as the number of edges connecting v to other nodes belonging to C or to the rest of the graph, respectively. 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 . A partition P = {C 1 , . . . , C k } is a division of a graph into disjoint com- munities.
For every pair of communities C i and C j in a partition P, they have C i ∩C j = ∅. A cover S = {S 1 , . . . , S k } denotes a division of a graph into communities sharing nodes. Given a cover S, someone may find that a pair of communities S i and S j share overlapping nodes such as S i ∩ S j = ∅.

The partitions can be measured by the quality function, which assigns a score to the partition of a graph. In this way, we can rank partitions based on their score given by the quality function. Partitions with high scores are "good", so the partition with the largest score is by definition the best.

The widest accepted quality function is the modularity of Newman and Girvan [Newman 2004], which is defined as:

Q = 1 2m i =j A ij - k i k j 2m δ(σ i , σ j ) ( 1 )
where σ i is the community to which node i belongs and δ(σ i , σ j ) is the Kronecker delta symbol, which is equal to 1 if the pair of nodes i and j belong to the same community; otherwise it is equal to 0. The modularity is always smaller than one, and can be negative as well. For instance, the partition where each node represents a single community, is always negative. When taking the whole graph as a single community, the modularity is zero as the two terms in this case are equal.

Current work

We then present a class of algorithms for network clustering, which allow nodes belonging to more than one community.

The CPM (clique percolation method) [START_REF] Palla | Uncovering the overlapping community structure of complex networks in nature and society[END_REF]] is one of early work for cover detection, which detects k-clique communities. A k-clique community is a series of adjacent k-clique. Two k-cliques are adjacent if and only they share k -1 nodes. However, this definition is too strict. It fails to resolve non-trivial communities, like WikiTalk [Lancichinetti et al. 2010a] which is a sparse network consisting of star-like communities.

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 seeds for network clustering. The seed can be a random node or a disjoint community. As shown in their results, there is a huge difference in the number of communities based on different types of seeds.

Lancichinetti et al. has made many efforts in cover detection including fitness-based function [Lancichinetti et al. 2009] 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 result is limited by the tunable parameter k, and the later uses the statistical significance [START_REF] Lancichinetti | Statistical significance of communities in networks[END_REF] of clusters with 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 popular techniques for overlapping community detection. There are similar endeavours 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 they applied Lancichinetti et al. [Lancichinetti et al. 2009]'s k-fitness function, the results are limited by the tunable parameter k.

Some cover detection approaches are based on other 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 together with each other. As indicated in [START_REF] Sales-Pardo | Extracting the hierarchical organization of complex systems[END_REF], they are limited by scales of networks.

Evans et al. [START_REF] Evans | Line graphs, link partitions, and overlapping communities[END_REF] proposed to construct a line graph (A line graph is constructed by using nodes to represent edges of the original graphs.) which transforms the problem of node clustering to the link clustering and allows nodes shared by several communities. The main drawback is that, in their results, overlapping communities always exist.

The problem of overlapping community detection remains.

A new extension of modularity

Modularity has been employed by a large number of community detection methods. However, it only evaluates the quality of partitions. Here, we introduce its extension for covers, which is combined with the energy model Hamiltonian for the spin system [START_REF] Reichardt | Statistical mechanics of community detection[END_REF].

Let a community structure be represented by a spin configuration {σ}. Each spin state represents a community, and the number of spin states represents the number of communities of the graph. Thus, the quality of a community structure can be represented through the energy of spin glass.

In [START_REF] Reichardt | Statistical mechanics of community detection[END_REF], a simplified Hamiltonian is proposed to measure the quality of community structure, which is written in:

H({σ}) = - i =j (A ij -γp ij ) δ(σ i , σ j ) , ( 2
)
where (A ijγp ij ) represents a coupling between nodes i and j, σ i , σ j denote the spin states of nodes i and j, respectively. The Kronecker delta symbol δ(σ i , σ j ) yields 1 if and only if σ i = σ j and 0 otherwise. Therefore, we can rewrite the modularity Q Eq. 1 as:

Q = - 1 m H({σ}) , (3)
with γ = 1 and p ij = kikj 2m . Since a good quality function of community structure should reward the internal links and penalize the external links, the Hamiltonian Eq. 2 can be expressed in two ways. One describes the cohesion within the community, and the other shows the adhesion among different communities:

H({σ}) = - s (m ss -γ[m ss ] pij ) = - s c s , (4)
and n1 n2 2. when n r is an union cluster composed of n 1 and n

H({σ}) = s<r (m sr -γ[m sr ] pij ) =
(a) n1 ∩ n2 = ∅ n2 n1 n0 (b) n01 ∩ n02 = n0 n2 n1 nr ns (c) nrs1 ∩ nrs2 = nr ∪ ns
2 , [m rr ] pij = [m 11 ] pij + [m 22 ] pij + [m 12 ] pij .
We show three different subdivisions of one community n 3 in [Fig. 3]. In the first subdivision [see Fig. 3(a)], community n 3 consists of n 1 and n 2 with empty intersection such as n 1 ∪ n 2 = n 3 , n 1 ∩ n 2 = ∅. From Eq. 4 and Eq. 5, we can easily prove

c 3 = c 1 + c 2 + a 12 , ( 6
)
where c 3 denotes the cohesion of n 3 that is the union of n 1 and n 2 with 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. In the second subdivision [see Fig. 3(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 cohesions of the sub-communities n 01 and n 02 respectively, a 0 01 and a 0 02 denote the adhesions between n 0 and n 1 , n 2 . Here, n 0 is shared by n 01 and n 02 . In terms of 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 . ( 7
)
In the third subdivision [see Fig. 3(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 , (8)
where c r r and c s s denote the cohesions 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. 7. Therefore, we propose the contribution of a rs for all communities {C 1 , . . . , C k } written in:

k 1 1 |d r ∪ d s | a rs = |d r ∩ d s | |d r ∪ d s | a rs , ( 9
)
where d r and d s denote the community memberships of n r and n s , respectively. For the relation between the Hamiltonian and the modularity Eq. 3, we write the quality of overlapping community structure in form of modularity:

Q ov = 1 2m i =j A ij - k i k j 2m |d i ∩ d j | |d i ∪ d j | , ( 10
)
where d i and d j are memberships of nodes i and j, respectively. Then, 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 - kikj 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 in range of 0, A ij - kikj 2m
. Furthermore, if the found community structure is a partition, its quality Q ov is equal to the modularity Q Eq. 1.

This extension of modularity is able to measure the quality of overlapping community structure. However, we can not detect covers by optimizing it. Therefore, we propose two methods based on other basis. 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 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 is only one group of granular overlapping nodes.

Clique optimization

The definition of community is not standard. 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.

Definition of granular overlaps

Given a partition, we often observe that cliques are cut by disjoint communities. For example, given a pair of communities C i and C j , they may cut a clique K such as (K ∩ C i ) ∪ (K ∩ C j ) = K , where K ∩ C i = ∅ and K ∩ C j = ∅. In our mind, a clique is an exclusive group of people who share common interests, views, purposes, patterns of behavior, etc. . Therefore, we define that a node is a possible granular overlapping node if it is involved into a clique cut by a partition.

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. Extended from the definition of k-clique community, we define that a clique and a community are adjacent if they share k -1 nodes. We also define that, if a clique is k-adjacent to a disjoint community, all members of this 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 1. A node v is a k-granular overlapping node shared by l communities E = {C 1 , . . . , C l } in a strong sense if it belongs to a clique K adjacent to these communities, such as:

∀C i ∈ E , |K ∩ C i | ≥ k -1. Definition 2. A node v is a k-granular overlapping node shared by l com- munities E = {C 1 , . . . , C l } in a weak sense if it is involved in l cliques K = {K 1 , . . . , K l } which are adjacent to them such as: ∀C i ∈ E , ∃K j ∈ K, |K j ∩C i | ≥ k -1.
Clearly an overlapping node in a strong sense is also an overlapping node in a weak sense, whereas the converse is not true. Find a clique K j , which is k-adjacent to at least one community 5:

Our algorithm of clique optimization Algorithm 1 Clique optimization

Input: G = (V, E), k Output: S = {S 1 , . . . , S nc } an overlapping community covering of V 1: Obtain a partition P = {C 1 , . . . ,
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 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. 1. 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. 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, we find a k -1 clique whose members belong to N (N is initialized by the neighbourhood of the chosen granular overlapping node candidate). Then, we obtain a clique k-adjacent to one community by adding the overlapping node candidate to the found k -1 clique.

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. Finally, we obtain a cover where granular overlapping nodes are shared by overlapping communities.

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 that 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.

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.

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

It is now possible to show performances of clique optimization. We have considered a set of artificial networks with the known community structure. We show their accuracy through the normalized mutual information (NMI) [Lancichinetti et al. 2009] by comparing to ground truth. The higher value of 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. CORPA [Gregory 2010] and OSLOM [Gregory 2010]. 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 maxk = 300, minus exponent for the degree sequence t1 = 2, minus exponent for the community size distribution t2 = 1, minimum for community sizes minc = 10, maximum for community maxc = 300, and number of memberships of overlapping nodes om = 2.

In [Fig. 4], we present the comparison of NMI for clique optimization with the other cover detection algorithms including CPM [START_REF] Palla | Uncovering the overlapping community structure of complex networks in nature and society[END_REF]], CO-PRA [Gregory 2010] and OSLOM [START_REF] Lancichinetti | Finding statistically significant communities in networks[END_REF]] through their applications to LFR benchmarks [START_REF] Lancichinetti | Statistical significance of communities in networks[END_REF]. LFR benchmarks are constructed corresponding to a series of parameters, including the number of nodes, average degree, the maximum degree, the number of overlapping nodes, the number of overlapping community memberships, and the mixing parameter. The mixing parameter μ is the ratio of external degree to the node degree. For each overlapping node i shared by ν i communities, if it belongs to community ξ, its adjacent links to ξ satisfies:

k ξ i = k in i /ν i .
As we can see, clique optimization performs well such as N M I ≥ 0.9 when μ < 0.5 in [Fig. 4(a) and Fig. 4(b)]. It also has good performance in [Fig. 4(c) and Fig. 4(d)] when μ ≤ 0.3 and has lower NMI than OSLOM when μ > 0.3. It can be understood since OSLOM 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 to be an individual node and is not considered in the community structure.

Fuzzy detection

In this section, we will introduce another method for cover detection. It is named fuzzy detection, which is proposed for identifying modular overlaps. Modular overlaps are groups of nodes shared by communities. Different from granular overlaps, modular overlaps are related to the hierarchy organization. That is, modular overlaps are sub-communities shared by several communities.

Motivation

Our fuzzy detection is based on the Louvain algorithm [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF]]. The Louvain algorithm is a partition detection algorithm and provides good partitions with high modularity. It consists of two phases that are iteratively repeated until no more positive gain of modularity. Initially, all nodes are assigned into a single community. Then, for each node whose move improves the modularity, will be removed from its current community to the neighbour community which yields the largest positive increase of modularity. The first phase repeatedly and sequentially sweeps all nodes until no further improvement of modularity can be gained. The second phase is building a new graph based on communities found in the first phase. 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, whose height of hierarchy is determined by the number of iterations. The Louvain algorithm is extremely fast and provides partitions having 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.

Algorithm 2 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.

Our algorithm of fuzzy detection

To have the benefit of the potential Louvain algorithm instability [Aynaud 2011], 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 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 Algorithm 3 Fuzzy detection. Input: G = (V, E), α * , β * Output: S an overlapping community covering of V // STEP 1: Detect robust clusters

1: P 0 ← 0; k ← 0;modularity max ← -∞ 2: repeat 3: k ← k +
S i ← S i ∪ c j 21:
end if 22: end for 23: Return S 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 [Zachary 1977] and Word adjacencies [Newman 2006].

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. 3. First, (lines 2 -9) we compute the co-appearance matrix P = [p ij ] n×n by running the Louvain algorithm of Algo. 2 several times with a random seed. The number of runs is determined by the Figure 6: 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 . convergence criteria (line 9):

P k+1 -P k = 1 m (i,j)∈E (p k+1 ij -p k ij ) 2 < ε, ( 11
)
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 small threshold. Figure 5 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. 6].

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 cj⊆Ci |c j | (12)
We assign each robust cluster c j to the community C i if and only if their community membership p cj , ci is larger than a threshold β * such as p cj, ci > β * (typically β * = 0.1). If one robust cluster is assigned to at least two communities, we call it a modular overlap. Given a modular overlap, its members are possible granular overlapping nodes. Only the granular overlapping nodes are required to have dense connection with related communities

Ð Ð Ð Ð Ð Ð Ð Ð Ð ?>=< 89:; 7 Ð Ð Ð Ð Ð Ð Ð Ð Ð Figure 7
: 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. 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).

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 subcommunities 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. Figure 7 illustrates such case. Due to unstable nodes, we do not use fuzzy detection to identify granular overlaps. Moreover, we may observe some modular overlaps that are not real overlapping nodes but are more like 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 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 show performance of fuzzy detection in testing benchmark graphs with the known community structure in hierarchical organization.

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.

We apply fuzzy detection to an artificial graph containing hierarchical structure [Lancichinetti et al. 2009] and a modular overlap. The benchmark graph consists of 512 nodes, which belong to 16 groups, arranged into 4 supergroups and one group is shared by two supergroups. Every node has an average of k 1 = 30 links with the nodes in the same micro-community, k 2 = 13 links with the 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 overlap has macro-links with two communities, its nodes have the total degree k = 61 while the other nodes only have the total degree k = 48. Remark that, when running our fuzzy detection to identify modular overlaps, the community core is not a single robust cluster. As each community has four large robust clusters with comparable size. By increasing the value of α * , we obtain a reasonable community core whose size is larger than the others within the same community.

Applications in real networks

Yeast protein complexes

As a further test, we consider the application to yeast protein complexes. The combined-AP/MS network1 describes 9070 interactions among 1622 proteins. With a catalogue of protein complexes provided by CYC2008 [START_REF] Pu | Up-to-date catalogues of yeast protein complexes[END_REF] 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 [Lancichinetti et al. 2009]. NMI measures the similarity between the results and the ground truth based on information theory. We also provide sensitivity, specificity, accuracy and modularity. Sensitivity relates to the ability to identify the real overlapping nodes, which is the proportion of real overlapping nodes among the found overlapping nodes. Specificity relates to the ability of 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 with the equal importance. We use the accuracy to show the goodness in detecting overlapping nodes. We observe that clique optimization has the highest accuracy, too.

Compared to other methods, the advantage of our fuzzy detection in identifying granular overlaps, is not obvious. Its has the lower NMI and accuracy value than the clique optimization. Moreover, 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. In contrast, 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.

Complex System Science

Next, 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 [Kessler 1963]). 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 | .
In [Fig. 9], we find 12 communities in scale above 100. These communities can be identified by research topics or theoretical fields through studies in topic keywords, see [Tab. 2]. 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 Table 4 shows results of clique optimization in identifying granular overlaps. 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..

In view of robust clusters [Fig. 10], these robust clusters can be considered as sub-specialities of the identified disciplines [Tab. 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. termine whether a genetic variant is associated with a disease or trait.

Comparing the results of granular overlaps and modular overlaps, we see their difference. 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 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 indicates that, for some cases, the two types of overlapping nodes can reach an agreement in characterizing overlaps.

Obviously, we can not compare the goodness between granular overlaps and modular overlaps in a definitive and quantitative way as they represent results based on different definitions. To the best of our knowledge, both definitions seem reasonable to use. Finally, we conclude that both methods: clique optimization and fuzzy detection, are useful to identify overlaps in complex networks.

Table 3: Results of fuzzy detection: ten high frequent topic keywords contained by modular 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.

Conclusion and future work

In this paper, we propose a new extension of modularity for measuring the quality of overlapping community structure. And two different methods are introduced to identify overlapping nodes. One is called clique optimization for identifying granular overlaps, and the other is named fuzzy detection for detecting modular overlaps. Both methods have been tested successfully in synthetic graphs. Moreover, studies and 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 paper 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. Several researches remain. We are currently studying underlying network organizations in both static and dynamic viewpoints. We are investigating the evolution of communities to mine more structural properties of complex networks.

Figure 2 :

 2 Figure 2: Example of [•] pij , 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 3 :

 3 Figure 3: 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 sub-communities 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 4 :

 4 Figure4: 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[Gregory 2010] and OSLOM[Gregory 2010]. 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 maxk = 300, minus exponent for the degree sequence t1 = 2, minus exponent for the community size distribution t2 = 1, minimum for community sizes minc = 10, maximum for community maxc = 300, and number of memberships of overlapping nodes om = 2.

Figure 5 :

 5 Figure 5: As the number of runs increases, the shape of the function value Eq. 11 gets closer and closer to 0. The figure shows results on College football [Girvan and Newman 2002], Karate club[Zachary 1977] and Word adjacencies[Newman 2006].

Figure 8 :

 8 Figure8: 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 8

 8 (b) illustrates the co-appearance matrix by running the Louvain algorithm without fixing the level threshold l * [Algo. 2], while Figure 8(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. 8(b)], we use [Fig. 8(a)] for the visualization, where we observe 4 communities, 32 robust clusters and one modular overlap. It shows the good performance of fuzzy detection in detecting modular overlaps.

Figure 9 :

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

Figure 10 :

 10 Figure 10: Results of fuzzy detection on Complex System Science. Robust clusters are marked by the highest frequent topic keywords. Their colours correspond to the relevant communities as shown in [Fig. 9].

  1Save the partition P in P opt and update modularity max P sc = P opt 11: for all edge e = (i, j) such that p ij < α * do 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 Identify community core: c i = arg max cj ⊆Ci |c j | 16: end for 17: Compute P ci,cj 18: for all c j ∈ P sc and c

	4:	P ← Run the Louvain algorithm on G
	5:	Update P k
	6:	if modularity of P greater than modularity max then
	7:
	8:	end if
	9: until P k -P k-1 ≤
	10: 12:
	15:

j / ∈ { c 1 , . . . , } do 19: if p cj, ci ≥ β * then 20:

Table 1 :

 1 ], results are shown in[Tab. 1]. Results of different overlapping community detections on Yeast protein complexes, in views of NMI, sensitivity, specificity, accuracy and modularity.

	Method	NMI Sensitivity Specificity Accuracy Modularity Eq. 10
	Clique Optimization	0.824323 0.514852 0.874587 0.6947195	0.772569
	Fuzzy detection	0.702184 0.970297 0.290757 0.630527	0.866759
	CPM	0.699512 0.287129 0.801471 0.5442995	0.816893
	OSLOM [Lancichinetti et al. 2010b] 0.52039 0.257426 0.965677 0.6115515	0.662716
	Copra [Gregory 2010]	0.517806 0.118812 0.967657 0.5432345	0.888672

Wang Q., Fleury E.: Fuzziness and Overlapping Communities ...

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

In terms of modular overlaps, our results are shown in [Tab. 3]. 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 multiagents are very common for modelling and analysing 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], Limbergen et al. 2007] studies are often used to de-


Remis Balaniuk

Pierre Bessiere
email: pierre.bessiere@college-de-france.fr

Emmanuel Mazer
email: emmanuel.mazer@inria.fr

Paulo Cobbe
email: paulocobbe@yahoo.com

Risk based Government Audit Planning using Naïve Bayes Classifiers

Keywords: Data mining, naïve Bayes, fraud detection

In this paper we consider the application of a naïve Bayes model for the evaluation of fraud risk connected with government agencies. This model applies probabilistic classifiers to support a generic risk assessment model, allowing for more efficient and effective use of resources for fraud detection in government transactions, and assisting audit agencies in transitioning from reactive to proactive fraud detection model.

Introduction

Computer technology gives auditors a large set of techniques for examining the automated business environment. Computer-assisted auditing techniques (CAATs) have become standard practice in corporate internal auditing.

Audit software permits auditors to obtain a quick overview of the business operations and drill down into the details of specific areas of interest.

Audit software can also highlight individual transactions that contain characteristics often associated with fraudulent activity. A 100% verification can identify suspect situations such as the existence of duplicate transactions, missing transactions, and anomalies.

Auditors usually look for patterns that indicate fraudulent activity. Data patterns such as negative entries in inventory received fields, voided transactions followed by "No Sale," or a high percentage of returned items may indicate fraudulent activity in a corporation. Auditors can use these data patterns to develop a "fraud profile" early in their review of operations. The patterns can function as auditor-specified criteria and transactions fitting the fraud profile can trigger auditor reviews [START_REF] Coderre | Auditing -Computer-Assisted Techniques for Fraud Detection[END_REF].

Nevertheless, when it comes to government auditing, the scale and the complexity of the roles to be considered can prevent the use of most methods and technologies so successful on the corporate world.

As stated by the US Comptroller General [START_REF]Government Auditing Standards (The Yellow Book)[END_REF], the major roles and responsibilities of governmental auditing are: combating corruptions, assuring accountability, enhancing economy, efficiency, and effectiveness, increasing insight, facilitating foresight.

Corruption can exist within government or on the part of contractors and others who conduct business with government. Fighting corruption requires a strong and effective audit function. For that to occur, government audit agencies must be assured free access to process, routines and records of government organizations.

Government auditing can also add value by analyzing the efficiency and effectiveness of government organizations, programs and resources.

Compared to corporate internal auditing, government auditing acts on a much larger universe, with concerns ranging from auditing specific operations or contracts to evaluating program effectiveness and performance.

As indicated by a survey by the Global Audit Information Network [START_REF] Vito | CCP, Auditing Employee Hiring and Staffing[END_REF], the top challenge facing all government audit organization is adequate audit staffing. The large audit universe, the diversity and complexity of the topics being covered makes it impossible for audit agencies to perform a 100% verification on all government operations or entities. The same survey also indicated the ability to plan based on risk as being part of the top ten challenges imposed to all government audit organizations.

Traditional methods for audit planning are usually based on management requests, auditors' experience or expertise or simply on statutes or regulations. These methods can work fine inside a corporation but are much less effective at the government level.

Risk-based audit planning, on the other hand, can result in disciplined analytical approaches to evaluate the audit universe, highlights potential risks that might otherwise be unknown, fosters dedicated audit coverage to high-risk areas, and allocates resources where pay-back is greatest [START_REF]The Institute of Internal Auditors: International Professional Practices Framework (IPPF)[END_REF].

A risk assessment process for audit planning proposed by the Institute of Internal Auditors (IIA) [START_REF]The Institute of Internal Auditors: International Professional Practices Framework (IPPF)[END_REF] is based on five steps:

• Define the audit universe • Identify and weight risk factors • Establish a mechanism and score risk factors for auditable units • Sort the auditable units by total risk score • Develop the audit plan based on the ranked audit universe. The aim of this paper is to propose a method, based on a probabilistic classifier, to support this generic risk assessment process. Our method can score auditable units using a formally defined mathematical framework. Extensive databases containing records from government operations can be combined to auditors knowledge, fraud profiles, impact factors or any other relevant metric in order to rank an audit universe.

Related work

Fraud detection and Risk analysis using data mining

Data mining has become an increasingly popular tool used by business, organizations and governments for aiding audit professionals in risk analysis and fraud detection. Several scholarly works have been written on application techniques, particularly for such businesses as financial and security exchange institutions, telecommunications and insurance companies, whom, along with their clients, incur incalculable financial losses due to fraud every year around the world [START_REF] Ngai | The application of data mining techniques in financial fraud detection: A classification framework and an academic review of literature[END_REF] [START_REF] Panigrahi | Credit card fraud detection: A fusion approach using Dempster-Shafer theory and Bayesian learning[END_REF].

When properly applied, data mining techniques are able to identify trends that indicate suspicious or fraudulent activities, casting light on transactions hidden among the crowd. By reducing the universe of transactions or activities to a smaller subset, data mining allows decision makers to concentrate their efforts on higher risk transactions, and act to mitigate the repercussion of fraudulent activity in affected organizations [START_REF] Ngai | The application of data mining techniques in financial fraud detection: A classification framework and an academic review of literature[END_REF][7] [START_REF] Hormazi | Data Mining: A Competitive Weapon for Banking and Retail Industries[END_REF].

Risk prediction is an important contribution of data mining to a decision making process. By quantifying the possibility that a given event may occur in the future, it provides the decision maker with a basis for comparing alternative courses of action under uncertainty [START_REF] Nilsen | Models and model uncertainty in the context of risk analysis[END_REF]. Despite of the fact that it is impossible to ascertain with complete certainty events which have yet to take place, risk analysis allows decision makers to define possible outcomes and assess the risks associated with each, and make a decision based on these possible alternatives. This assessment does not shield the decision maker from negative outcomes, but should ensure that positive outcomes are reached more often than not [START_REF] Nilsen | Foundations of Risk Analysis: A Knowledge and Decision-Oriented Perspective[END_REF].

Naïve Bayes classifiers and fraud detection

Naïve Bayes is a mining technique not commonly associated with fraud detection in the scientific literature. In their review of the academic literature on data mining applications in financial fraud detection, Ngai et al [START_REF] Ngai | The application of data mining techniques in financial fraud detection: A classification framework and an academic review of literature[END_REF] indicate very few studies that applied naïve Bayes algorithms for this purpose.

That trend contrasts with Viaene, Dering and Dedene [START_REF] Viaene | A Case Study of Applying Boosting Naive Bayes to Claim Fraud Diagnosis[END_REF] findings, who present a successful application of naïve Bayes algorithm to personal injury protection (PIP) claims for the State of Massachusetts. Their findings suggest that this algorithm can lead to efficient fraud detection systems for insurance claim evaluation support.

Viaene et al [START_REF] Viaene | A Comparison of State-of-the-Art Classification Techniques for Expert Automobile Insurance Claim Fraud Detection[END_REF] also indicates that naïve Bayes algorithms showed comparative predictive performance to more complex and computationally demanding algorithms, such as Bayesian Learning Multilayer Perceptron, least-squares support vector machine and tree-augmented naïve Bayes classification, in a benchmark study of algorithm performance for insurance fraud detection.

The emphasis of research of complex unsupervised algorithms presents to Phua et al [START_REF] Phua | A comprehensive survey of data mining-based fraud detection research[END_REF] a problem for the future. The authors suggest that in order for fraud detection to be successfully implemented in real time applications, less complex algorithms, such as naïve Bayes, have to be considered as the only viable options.

The method proposed in this paper performs risk evaluation based on classification rules. Rules are built by exploring large databases collected in daily activity of government agencies. Typically, the auditable universe is large and we want to classify auditable units to one of two groups: high risk units and low risk units. Moreover, these units should be sorted with respect to their risk.

Naïve Bayes classifiers

The probability model for a classifier is a conditional model : P(C H 1 ,...,H n ) over a dependent class variable C with a small number of outcomes or classes, conditional on several feature variables H 1 through H n .

Using the well-known Bayes' theorem we write:

) ,..., ( ) ( ) ,..., ( ) ,..., ( 1 1 1 n n n H H P C P C H H P H H C P =
Because the denominator does not depend on C we are usually interested only in the numerator of the right side fraction. The values of the features are also given and consequently the denominator is constant.

The numerator is equivalent to the joint probability model:

P(C,H 1 ,...,H n ).
The problem is that if the number of features is large or when a feature can take on a large number of values, the computation of such a model can be infeasible.

The "naive" conditional independence assumption assumes that each feature is conditionally independent of every other feature: P(H i C,H j )= P(H i C).

This strong assumption can be unrealistic in most cases, but empirical studies related to fraud detection show that most frequently the method presents good performance [START_REF] Viaene | A Case Study of Applying Boosting Naive Bayes to Claim Fraud Diagnosis[END_REF]. Zhang [START_REF] Zhang | The Optimality of Naive Bayes[END_REF] explained the superb classification performance of naïve Bayes in real applications, where the conditional independence is rarely true, showing that dependence among attributes usually cancel out each other.

Under these independence assumptions the conditional distribution over the class variable can be expressed as:

) | ( ) ( 1 ) ,..., ( 1 1 C H p C p Z H H C P i n i n = =
where Z is a constant if the values of the feature variables are known. P(C) is called the class prior and P(H i C) are the independent probability distributions By using this naïve Bayesian algorithm it is then possible to obtain a probability distribution of objects belonging into classes. Threshold rules can be used to decide when a probability is strong enough to assign an object into a group. Depending on these rules it happens that an object is not assigned to any group or to more than one group, like in fuzzy logic. Naïve Bayes also naturally deals with missing values, what is difficult to achieve using other methods like decision trees or neural networks. Resulting models are self explainable, unlike other methods like neural networks.

Further information about Bayesian Classifiers can be obtained at [START_REF] Phua | A comprehensive survey of data mining-based fraud detection research[END_REF].

Adapted Naïve Bayes Classifier

A major difficulty imposed on risk evaluation by government auditing agencies is the lack of consistent fraud databases. Most methods used in AI are based on supervised learning, where a set of examples are used to define an inference model. Neural networks and decision-trees are examples of supervised learning methods. Detected fraud cases are usually reported in unstructured documents. These are typically disconnected, identified and described in very specific contexts and are not statistically relevant considering the number of "variables" and "states" in which a systemic fraud could be described.

This lack of information compromises the typical use of Bayesian classifiers. Conditional probabilities for the output classes cannot be established without a consistent base of tagged examples distributed on the input space.

In order to overcome this handicap we adapted the standard naïve Bayes classification approach making two assumptions:

1. Statistically, the high risk group is much smaller than the low risk group: fraud is an exception (typically less than 1% of the auditing units) 2. High risk units can be described by rules: auditing experts are able to describe fraud profiles from their field expertise From these assumptions and having a non labeled extensive database describing our auditing universe, our problem is decomposed in two different steps:

• Find the conditional probabilities for the low risk group: from the first assumption we can consider that the fraud cases inside our large database are not statistically relevant, so we will estimate this conditional probability using all the data contained in the database as if there were no fraudulent units there: P(H i C=low risk)= P(H i ) • Find the conditional probabilities for the high risk group: the audit expert directly defines the shape of a probability distribution based on his expertise.

The risk assessment process

Distinct risk assessment processes are defined for distinct sets of auditable entities. The first step in implementing a successful risk based audit process is to clearly define and understand a chosen audit universe.

The adoption of CAATs by government audit agencies enables the compilation of timely, reliable, and meaningful data that can be used for planned audits on an ongoing basis. Based on compiled data, once CAATs are implemented, auditors or auditing systems can routinely review significant financial and non-financial processes and identify potential audit issues.

Once an audit issue is identified the corresponding audit universe will be defined as the set of entities to be classified in order to reflect the risk associated to that issue.

An audit issue can be related to a business process as government purchasing / procurement, general ledger, treasury, payroll, accounts payable, inventory and fixed assets. Broader issues can be related to government programs. More specific issues can be related to public employees or public contractors. Correspondingly, the audit universe can be a set o purchases, contracts, assets, programs, public employees or contractors.

Once the audit universe is defined the second step is to identify its risk factors. The risk factors of an audit universe are related to the audit issue and the business rules associated to the entities set.

The risk factors will define the conditional features of the probabilistic classifier. Because of the naïve Bayes assumption of variables independence, a careful choice of risk factors must be made considering their independence. As explained by Zhang [START_REF] Zhang | The Optimality of Naive Bayes[END_REF], violations of the independence usually do not compromise the optimality of the model once local dependencies usually cancel out each other. However, if the model does not perform well is still possible to identify which factors are affecting the model performance using analysis of covariance as proposed by Zhang [START_REF] Zhang | The Optimality of Naive Bayes[END_REF].

There is no need to define weight factors while using probabilistic classifiers once the nature of the feature variables define a common framework to all measures.

To illustrate how the choice of the risk factors occurs, consider as audit issue the fraud detection on public purchasing/procurement. Public procurement comprises government purchasing of goods and services required for State activities, the basic purpose of which is to secure best value for public expenditures. In both developed and developing economics, however, the efficient functioning of public procurement may be distorted by the problems of collusion or corruption or both [START_REF]Roundtable on Collusion and Corruption in Public Procurement[END_REF].

Considering fraud on public procurement our audit issue, our audit universe will be the set of public purchases, preferably over a large period of time (five to ten years) and a large scope of purchasing organizations, contractors and purchased goods and services. The risk assessment would be ideally performed based on a detailed database describing all relevant aspects of each purchase.

One obvious first risk factor associated to public purchases is the space left for competition between potential sellers. The corresponding high risk rule would be: less competition = higher risk. To compute the competition level within a procurement process one could use a heuristic model based on its characteristics. The existence or not of an open call for bids or tenders, the type of procurement and the number of registered bidders can be the input for this model. The heuristics can be based on business rules: restricted or invited tenders are more suitable for fraud; electronic procurement auctions (e-procurement, e-reverse auctioning, e-tendering), on the other hand, tend to be more competitive and less suitable for fraud; the competition of a bid is proportional to the number of registered bidders.

Other risk factors to consider could be:

• Value: more money = higher risk • Bid protests: more protests = higher risk • Bid winner profile: no qualified winner = higher risk • Bid winner previous sanctions: sanctioned winner = higher risk Some risk factors can require the use of external data, not directly related to the audit universe. The winner previous sanctions, for instance, would require a sanctions database. This a common issue when adopting CAATs. Analytical auditing databases require information covering a broad scope of related themes.

Factors associated with different concerns than the risk itself can be added.

• Political and economic impact: expenditure contributes to the achievement of policy goals = higher economic impact

• Social impact: public health spend = higher social impact • Timing and effectiveness: older purchases = less auditing effectiveness The only requirements to include a new factor to the model are the possibility to estimate a corresponding numerical value for each entity belonging to the audit universe and the existence of a rule for the high risk/impact/effectiveness group.

Once the risk factors are identified and computed for the whole audit universe, the next step will be to run the naïve Bayes algorithm and compute the probability distribution of entities belonging into classes.

Because we have only two classes (high and low risk) we obtain two values for each entity: P(C=high risk H1,...,Hn ) and P(C=low risk H1,...,Hn ).

If a choice of subsets of risky and non-risky entities is required a threshold rule must be defined in order to decide when a probability is strong enough to assign an entity into a class.

Moreover, the probability P(C=high risk H 1 ,...,H n ) can be directly used to sort the auditable units by total risk score. The ranked audit universe can then be used to develop an audit plan.

As in any knowledge discovery process, the auditing results should be feedbacked to refine the assumptions upon which the whole model was constructed.

Experiments

This approach was tested by the Tribunal de Contas da União -TCU, the Brazilian Court of Audit. The TCU have been using CAATs in the last five years intensively, and has gathered extensive information about the Brazilian public sector. It receives on an ongoing basis data from IT systems of major government agencies. All relevant data is assembled into a large data warehouse.

This test was done as part of a research project involving the TCU, the Institut pour la Recherche en Informatique et Automatique-INRIA and the company Probayes 1 .

ProBayes developed the ProBT engine [START_REF] Mekhnacha | Exact and approximate inference in ProBT[END_REF], a powerful tool that facilitates the creation of Bayesian models.

A number of risk assessment models were built in order to analyze major audit issues like high risk private contractors, collusion between private contractors and corruption between public bodies and private contractors. The audit issues, the audit universes and the risk factors were designed by TCU auditors.

In the following we detail one of these models.

Corruption in public procurements

As pointed out by the Organization for Economic Co-operation and Development -OECD Global Forum on Competition Debate on Collusion and Corruption in Public

Procurement in October 2010 [START_REF]Roundtable on Collusion and Corruption in Public Procurement[END_REF]:

"Corruption occurs where public officials use public powers for personal gain, for example, by accepting a bribe in exchange for granting a tender. While usually occurring during the procurement process, instances of post-award corruption also arise. Corruption constitutes a vertical relationship between the public official concerned, acting as buyer in the transaction, and one or more bidders, acting as sellers in this instance."

We used the proposed naïve Bayes approach to assess risk of corruption between a public body and private companies awarded with its public contracts.

The audit universe was the of pairs of public and private parties of all public contracts signed by the Brazilian federal administration between 1997 and 2011, totalizing 795954 pairs.

The risk factors chosen by the auditors were:

• Competition: purchases awarded to restricted or invited tenders without a open call bid were considered risky • Post-award renegotiations of values rising the initial awarded purchase value raise corruption risk • Post-award renegotiations of values reducing the initial awarded purchase value reduce corruption risk • The existence of links between the parties was considered risky: a possible link would be public employees from the public body or their relatives which are or were partners or employees of the private company. The risk factors were then transformed in numerical features. To reduce the computation effort the features were discretized and their values bounded.

The following features were computed for each pair of (public body, private company) from the audit universe:

•

Results

The conditional probabilities for the seven features are illustrated on the following Figures. Conditional probabilities The class prior was assigned an empirical value P(C) =0.01 based on the auditors expectation of corruption inside the audit set.

The computation of P(C=high risk NISLICIT, TISLICIT, NREFOR,TREFOR, NANULA, TANULA, TSESO) for the set of 795,954 pairs of public and private parties indicate 2,560 pairs with probability higher than 99% (0.99).

This result included parties with obvious links, like private not-for-profit foundations for which the Brazilian public procurement law gives special treatment. Moreover, a number of high risk pairs were known by the auditors from previous investigations where corruption was effectively found. The overall feeling from all auditors to which the high risk list was presented was that the result was very reasonable. Future audit plans will possibly be based on our risk rank.

Conclusion

With a growing number of governmental agencies transitioning into unified and consolidated data information platforms, access to information and uniformity are increasing. To deal with all this information government audit organizations are increasingly adopting CAATs in order to routinely review significant financial and non-financial processes and identify potential audit issues.

The steps taken to accumulate and identify significant data elements allow audit organizations to use that data during planned and unplanned audits. The perpetual development of data repositories and implementation of ongoing monitoring can also contribute to the development of periodic government-wide risk assessment.

In this paper we proposed a risk assessment method, based on naïve Bayes classifiers, that can be used by government audit organizations. The proposed method is suitable to the typical risk assessment process for audit planning, as formalized by the Institute of Internal Auditors (IIA).

The main advantages of the proposed method are:

• Integration of auditors knowledge to large data repositories in order to analyze audit issues • Integration of quantitative risk factors to qualitative aspects to compose probabilistic features • Natural framework to deal with missing data, data in different scales and from different sources • Low computational complexity Upon implementation, this semi-automated risk assessment procedure can help audit organizations transition from a reactive response to a proactive approach to identify and correct issues that may be indicative of fraud, waste or abuse.

  NISLICIT: number of purchases awarded without an open call bid o The final feature value was the natural logarithm of the count of purchase awards (values between 0 and 9) • TISLICIT: total amount of the purchases awarded without an open call bid o The final feature value was the logarithm base 10 of the total amount of purchases (values between 0 and 5) • NREFOR: the number of post-award purchase value increases o The final feature value was the natural logarithm of the count of purchase value increases (values between 0 and 7) • TREFOR: total amount of the purchases value increases o The final feature value was the logarithm base 10 of the total amount of purchase value increases (values between 0 and 6) • NANULA: : the number of post-award purchase value reductions o The final feature value was the natural logarithm of the count of purchase value reductions (values between 0 and 7) • TANULA: total amount of the purchases value reductions o The final feature value was the logarithm base 10 of the total amount of purchase value reductions (values between 0 and 6) • TSESO: indicates the existence or not of links between the public body and the private company o The final feature value was 1 for linked pairs and 0 otherwise.

  for the low risk class, obtained from the purchase database are displayed on the left side of the Figures. Conditional probabilities for the high risk class directly assigned by the audit experts, are displayed on the right.

Figure 1 :Figure 3 :Figure 4 :

 134 Figure 1: left: P(NISLICIT C=low risk) and right: P(NISLICIT C=high risk)

Figure 5 :

 5 Figure 5: left: P(TREFOR C=low risk) and right: P(TREFOR C=high risk)

Figure 6 :Figure 7 :Figure 8 :

 678 Figure 6: left: P(NANULA C=low risk) and right: P(NANULA C=high risk)

http://www.probayes.com