{'fraction_non_alphanumeric': 0.034608733773350546, 'fraction_numerical': 0.0102291823960642, 'mean_word_length': 4.789622109419064, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Ensemble-based Overlapping Community Detection using Disjoint Community Structures

While there has been a plethora of approaches for detecting disjoint communities from real-world complex networks, some methods for detecting overlapping community structures have also been recently proposed. In this work, we argue that, instead of developing separate approaches for detecting overlapping communities, a promising alternative is to infer the overlapping communities from multiple disjoint community structures. We propose an ensemble-based approach, called EnCoD, that leverages the solutions produced by various disjoint community detection algorithms to discover the overlapping community structure. Specifically, EnCoD generates a feature vector for each vertex from the results of the base algorithms and learns which features lead to detect densely connected overlapping regions in an unsupervised way. It keeps on iterating until the likelihood of each vertex belonging to its own community maximizes. Experiments on both synthetic and several real-world networks (with known ground-truth community structures) reveal that EnCoD significantly outperforms nine state-of-the-art overlapping community detection algorithms. Finally, we show that EnCoD is generic enough to be applied to networks where the vertices are associated with explicit semantic features. To the best of our knowledge, EnCoD is the second ensemble-based overlapping community detection approach after MEDOC [1].


Introduction
Real-world networks are complex, high-dimensional and multi-faceted, thus can be interpreted in many different ways. A fundamental property of a real-world network is its "community structure", which is often assumed as organizational units in social networks [2], functional modules in biological networks [3], scientific communities in citation networks [4], and so on. Despite a huge amount of effort devoted in past decade or more [5,6], the problem of community detection (CD) has turned out to be more complicated because of two reasons -(i) CD is an ill-defined problem [5]; therefore one can obtain multiple solutions for a given network, each of which is important in its own way. Moreover a single objective function (even the "best", if exists) may not be able to effectively model such vast dimensions present in a network. (ii) The vertices in real-world networks often belong to multiple communities [7,8], leading to the community structure being overlapped. None of the existing disjoint CD algorithms are able to detect overlapping regions inside a community structure.
Although a growing body of literature is focusing on discovering the overlapping community structure after the introductory work of Palla et al. [7], the number is considerably less compared to the vast amount of literature on disjoint CD. Moreover, in recent years, Chakraborty et al. [9,1] showed that one can successfully detect overlapping regions inside a community structure by leveraging huge number of diverse and accurate disjoint community structures.
In this paper, we attempt to utilize multiple views of the disjoint community structure observed in a given network (obtained from different disjoint CD algorithms) by merging these views, distilling all their good qualities into an ensemble solution [10,11]. The motivation for our work comes from the fact that ensemble approaches have already been proved to be successful in clustering and classification tasks [12]. Hence, ensemble approaches, if designed properly, can perform well in overlapping community detection as well. However, the challenge in applying ensemble techniques to networkbased analysis is due to the lack of sufficient information such as representative features of each vertex, extent of similarity between pair-wise vertices, and so on.
Empirical observations and Motivation. Our algorithm is primarily Figure 1: Conditional probability P (in y-axis) of (a) existence of an edge between two vertices, and (b) common overlapping community (OC) membership of two vertices in the ground-truth community structure of six real networks, given the fraction of the base disjoint communities that both the vertices share. We conclude that the more the vertices share common base disjoint communities, the more the chance that they are connected in the graph and belong to the same overlapping community.
built on two interesting empirical observations on six large real networks (see Section 4 for dataset description). While analyzing the ground-truth community structures of these networks, we find many solutions by running each of the base disjoint CD algorithms on every single network. The solutions have significant (dis)similarity with the ground-truth, corroborating the observation in [13]. We represent the memberships of each vertex in different base disjoint communities by a feature vector. Then we examine the probability of two vertices u and v being connected in the network, given that they have k u,v fraction of common base community memberships. Figure 1(a) plots this conditional probability for the six networks. We see an increasing relationship, i.e., the more base disjoint communities a pair of vertices has in common, the higher the probability of an edge connecting them. Further, we examine the conditional probability that two vertices belong to the same ground-truth overlapping community given that they have k u,v fraction of common base disjoint community memberships. Once again we observe a positive correlation in Figure 1(b). Thus, the probability of a pair of vertices belonging to the same overlapping community increases with the increase of their shared base community memberships. The above observations motivated us to develop an overlapping CD algorithm, by combining disjoint community structures identified for a given network.
Ensemble-based overlapping community detection. Our method iteratively learns major dimensions of features for vertices that lead to denselyconnected groups. In practice, since base disjoint CD algorithms produce many (and significantly different) community structures from a network, we leverage this information to extract the latent feature information associated with each vertex. 1 Our algorithm, named EnCoD is built on two hypotheses -first, an overlapping community is formed by a group of densely-connected vertices; second, vertices within a community have significantly high feature similarity. We represent the memberships of each vertex in different base disjoint communities by a feature vector, and then use the similarity between two vertices. We then learn important features that may lead to discover densely-connected overlapping communities [14,15]. To the best of our knowledge, EnCoD is the second algorithm after MEDOC [1] to propose ensemble-based overlapping CD algorithm by leveraging several disjoint community structures. Note that other two algorithms, namely PEACOCK [16] and PVOC [9] can detect overlapping community from a single disjoint community structure by applying an efficient post-processing technique. They do not leverage multiple disjoint community structures.
Summary of the evaluation. Experiments are conducted on both synthetic and six large real-world networks with known ground-truth overlapping community structure. We experiment with various disjoint CD algorithms as the base algorithms for EnCoD. For comparative evaluation, we choose seven non-ensemble based overlapping CD algorithms. Additionally, we compare EnCoD with PVOC [9] and MEDOC [1], two most recent overlapping CD algorithms that leverage disjoint community structures. Few notable observations are as follows. (i) EnCoD is almost independent of how perfect the base CD algorithms are; however, stronger base algorithms have more impact in the aggregation stage than the weaker base algorithms. Also, the accuracy of EnCoD never decreases with the increase in base solutions. (ii) EnCoD tends to get saturated after aggregating a certain number of base solutions, after which there is almost no effect on the final performance. However, the accuracy never decreases with the increase in base solutions.
(iii) On average, EnCoD outperforms the best baseline overlapping CD algorithm in terms of the overlapping NMI metric (ON M I) [17], Ω index and F-Score. (iv) We further apply EnCoD to networks where, apart from the topological structure, every vertex is associated with additional feature information. In such cases, EnCoD systematically combines the features into the model and produces more accurate overlapping community structure.
Contributions of the paper. The major contributions of the paper are four-fold: • Ensemble algorithms for community detection have rarely been studied. This paper will pave the way for enhancing the state-of-the-art on ensemble based community detection.
• The idea of using the membership of a vertex in different disjoint community structures as features is unique and, to our knowledge, has not been used earlier in community detection.
• Empirical results indicate that EnCoD is either as good as the best baseline CD algorithm, or sometimes performs even better than that. Therefore, one can rely on such ensemble framework instead of choosing and picking the best one from the jungle of CD algorithms available at present.
• The framework used in EnCoD is generalized enough to be used to combine any feature set of vertices to detect community structure (as shown in Section 6). Therefore, if the topology of a network is incomplete and sparse in nature and the properties of vertices are available, one can use the proposed framework to combine the features into the model for overlapping community detection.

Related Work
Due to the abundance of literature on community detection (CD) algorithms [5,6,18], we restrict our discussion to some selected works that we deem as pertinent to our study. Two extensive survey articles on CD are [5] and [6].
Traditional community detection algorithms. Most of the early research in CD assumed the communities to be disjoint. Many different CD approaches have been proposed, including, modularity optimization [19,20,21], information theoretic approaches [22], vertex similarity-based approaches [23], significance-based approaches [24], label propagation [25], diffusionbased approach [26], and so on (see [5,6] for surveys). Gradually, researchers realized that in real-world networks, a vertex can belong to multiple communities, resulting overlapping community structure. Palla et al. proposed 'CFinder' [7], the first ever method to detect overlapping communities based on clique-percolation technique. Subsequently, several overlapping CD techniques have been proposed, including modified modularity [27], fitness function [28], local density function [29], affinity propagation function [30], integrated approach [31], node location analysis based approach [32], nonnegative matrix factorization [8], and so on. Recently, Li et al. [33] proposed a local spectral clustering for overlapping community detection. Huang et al. [34] proposed an overlapping community detection algorithm in heterogeneous social networks via the user model. Sattari and Zamanifar [35] suggested a spreading activation-based label propagation algorithm for overlapping community detection in dynamic social networks. Notably, though there have been several recent studies on the topic, the depth of study on overlapping community detection is much lesser than that for the disjoint case.
Ensemble-approach for community detection. Ensemble approach has been well-studied in traditional data mining for clustering data points (see [12] for a detailed review). These approaches can be classified into two categories [12]: object co-occurrence based approaches and median partitioning based approaches. However, this number is significantly less when we talk about clustering vertices in the network. A pioneering attempt was made by Dahlin and Svenson [10] to propose ensemble clustering for network data. Raghavan et al. [36] showed the effectiveness of merging outputs of several community detection algorithms. Ovelgönne and Geyer-Schulz proposed CGGC [37], an ensemble-based modularity maximization approach. Kanawati proposed YASCA [38] that for each seed vertex considers its egocentric network, partitions the network in different ways and combines the outputs. He further tuned two parameters -quality and diversity of the partitions for final combination [39]. Recently, Lancichinetti and Fortunato [11] proposed 'consensus clustering' which utilizes a consensus matrix for disjoint community detection. However, all the above works focused on identifying disjoint communities.
Recently, two algorithms, PEACOCK [16] and PVOC [9] argued that intelligently post-processing a disjoint solution can lead to the detection of overlapping community structure. PVOC was reported to outperform PEA-COCK [9]. The difference between PVOC and EnCoD is that PVOC uses a novel post-processing technique that modifies a given disjoint community structure using a metric called 'permanence' [40,41], whereas EnCoD does not do any post-processing; rather it considers multiple disjoint community structures and uses them as features of a vertex for detecting overlapping regions. Another ensemble algorithm, called MEDOC [1] uses the idea of meta community (community of communities). It creates a multi-partite network using the base disjoint community structure. After this, it runs an existing CD algorithm to partition the multi-partite network. Finally, a membership function is to determine the membership of a vertex to a community. EnCoD does not create any meta-community using base community structures; rather it uses them to generate features for each vertex to be used further in the optimization algorithm. In Section 5.2, we will show that our algorithm outperforms both PVOC and MEDOC.

Ensemble-based Overlapping CD Algorithm
We design an overlapping CD algorithm by leveraging the solutions obtained from several disjoint CD algorithms. This section details the proposed overlapping CD algorithm, named EnCoD. We start by formally defining the ensemble-based overlapping community detection problem.

Definition 1. (Ensemble-based Overlapping Community Detection)
Given a network G = (V, E) and a set of M disjoint community detection algorithms AL = {Al m } M m=1 , we aim at grouping the vertices into communities OC = {OC 1 , OC 2 , · · · } in such a way that a vertex may belong to multiple communities and the following conditions are satisfied: We now describe our algorithm, called EnCoD, an Ensemble based Overlapping Community Detection. The overall framework of the algorithm is presented in Algorithm 1 and important notations are summarized in Table  1.
Inputs to the algorithm: Two main inputs of the algorithm are the network G(V, E) and the set of M base algorithms AL = {Al m } M m=1 which Table 1: Important notations used in this paper.
An undirected network with sets of vertices V and edges Average size of a base community structure ξāM K, approx. total number of communities in Γ OC {OC 1 , OC 2 , · · · }, final overlapping community structure consisting of overlapping communities OC t Overlapping community structure at iteration t of EnCoD ζ {τ 1 , τ 2 , · · · }, set of thresholds where τ j corresponds to overlapping community OC j τ L Global community threshold used to control the community size F v Feature vector of vertex v yield disjoint community structures. Apart from these, one needs to specify: K, number of vertex orderings of a particular network on which a base CD algorithm will run; 2 INV(v, C), an involvement function that will determine to what extent v is a part of a base community C; SIM (C, v), a function that will measure the similarity of a vertex v with a community C; and τ L , a threshold that confirms the minimum similarity value required by the vertices in a community to remain together, failing which the community is discarded. Possible definitions of these functions are discussed in Section 5.1. Summary of the algorithm: Motivated by the ego-centric circle detection algorithms proposed in [43,44], we design EnCoD that aims at maximizing the likelihood of the membership of each node inside a community. EnCoD starts by running all the base disjoint CD algorithms on different vertex orderings 3 of a network, which produce dissimilar base community structures (Section 3.1). Following this, the base community information is used to generate a feature vector for each vertex (Section 3.2); this in turn transforms the vertices in the network into a feature space. The algorithm now tries to infer the overlapping community structure from the vector representation of vertices, by iteratively optimizing an objective function (detailed in Section 3.3). The actual iteration starts by assigning each vertex to a sin-gleton community, and a high similarity threshold value is assigned to each community to maintain high integrity among its constituent vertices. In each iteration, the algorithm manipulates the community structure by randomly removing vertices from their assigned communities and allocating vertices to some unassigned communities, such that the similarity condition is not violated (Section 3.4). After each iteration, the similarity threshold associated with each community is updated (Section 3.5). The iteration continues as long as the value of the objective function does not decrease.
In the rest of the section, we elaborate the subroutines mentioned in Algorithm 1.

Generate Base Communities
Assume that we are given a network G = (V, E) and M different base CD algorithms AL = {Al m } M m=1 . For each such base algorithm Al m , EnCoD generates K different vertex orderings of G and runs Al m on each vertex ordering. This results in K different community structures denoted as Γ m = {C k m } K k=1 , where each community structure C k m = {C 1k m , · · · , C ak m } constitutes a specific partitioning of vertices in G. The size of each C k m might be different. We choose to use different vertex orderings of G since it has been shown that many of the disjoint CD algorithms produce different community structures depending on the ordering of vertices in the input [40,11]. Here we use random vertex ordering strategy which ensures that the base algorithm starts from different seed vertices without any predefined bias and produces diverse community structures. At the end of this step, we obtain Γ, a set of M K base community structures (Step 3 of Algorithm 1).

Generate Feature Vectors for Vertices
The ensemble step in Function 1 (which is invoked in step 5 of Algorithm 1) intends to leverage the base community structures Γ to construct the feature vector of vertices.
We now describe how we compute F v for a vertex v using Function 1. To start with, we measure INV(v, C), the involvement v into each base community C ∈ C k m (see Section 5.1 for the possible definitions of INV). Note if v is not a part of a certain community C, we leave the corresponding field as zero. The value returned by INV is subtracted from 1 to get the distance of v from the community (Step 5). Following this, we construct an auxiliary feature vector AF (v) for vertex v, which consists of elements indicating the distance of v from each base community (Step 6). The number of communities ξ ∈ Γ can be approximated by ξ =āM K, where the average size of a community is denoted byā. Therefore, the size of AF (v) is same as ξ. D v = max i AF i (v) denotes the maximum distance of v from any of the base community present in Γ (Step 8).
To construct the actual feature vector F v for vertex v, we measure the probability associated with each base community C i given that vertex v is observed. For a given vertex v, the community label C i is assumed to be a random variable from a distribution with probabilities {P (C i |v)} ξ i=1 . One can provide a non-parametric estimation of such probabilities based on the evidences of the data and the community structure. To transfer the distance into probability (the smaller the distance, the larger the probability), we use the following conditional probability [1] for vertex v to be a part of C i (Step 11): The denominator of the above equation ensures that ξ i=1 P (C i |v) = 1. Adding 1 in the numerator ensures a non-zero probability for all vertexcommunity pairs. For smaller distance values, P (C i |v) increases proportionately to D v − AF i (v), i.e., the larger the deviation of AF i (v) from D v , the more the increase. As a consequence, the corresponding community C i becomes more likely for v. Now we can construct the actual feature vector Step 12). This process essentially maps a vertex to a ξ-dimensional vector space.

Objective Function
After the ensemble step, each vertex is represented by a feature vector. Our method of detecting the overlapping community structure (denoted by OC = {OC 1 , OC 2 , · · · }) aims at maximizing a certain objective function which represents the likelihood of each vertex being a part of its own community. The likelihood function assumes that if two vertices u and v are found to have very similar feature vectors, then they -(i) should be connected by an edge in the network, and (ii) should stay in the same community. These two assumptions are supported by the observations in Figure 1. We use the knowledge of the edges in the network to validate the inferred community structure.
To start with, let us define few measures required to formulate the objective function. Note that all the communities mentioned in this subsection correspond to the overlapping communities that we aim to detect from a network.
Definition 3. Similarity between two vertices. For vertices u and v, let represent their feature vectors respectively. Then the similarity between two vertices u and v is calculated using the cosine similarity among the feature vectors.
We also tried other similarity measures (see Section 5.1), and obtained best results with cosine similarity. With this similarity measure, we further define the similarity of a vertex with a community as follows.
Definition 4. Similarity between a vertex and a community. Given a community OC and a vertex v, the similarity of v and OC is calculated as the average similarity of v with all other vertices in OC.
Each community is associated with a minimum similarity threshold which every vertex needs to satisfy in order to be a part of the community.
Definition 5. Similarity threshold per community. Each community OC j in our model is assigned a similarity threshold τ j in such a way that if vertex v ∈ V is in OC j then it should satisfy SIM (OC j , v) ≥ τ j .
Definition 6. Membership similarity of pair-wise vertices. The membership similarity of two vertices u and v is defined in terms of their memberships in different communities as follows: where, We consider {u, v} ⊆ OC j if both the vertices u and v belong to the same community OC j ; whereas {u, v} OC j if OC j does not contain either u or v or both. One should consider λ as large as possible so that individual terms in the summation are always positive. In practice, we set λ as the maximum of all the threshold values corresponding to the communities mentioned in Definition 5 (i.e., λ = max{τ 1 , τ 2 , · · · }). The value of β 1 (u, v) (resp. β 2 (u, v)) tends to become high if both u and v share (resp. do not share) common communities with very high thresholds. Furthermore, the value of membership similarity β(u, v) depends not only on the common community memberships, but also on the threshold specific to the communities. In particular, with the increase of the number of the common communities where both u and v belong to and the community threshold, the value of β(u, v) also increases.
Given the membership similarity of all pair-wise vertices, we further define the probability that a pair of vertices u and v are connected by an edge E u,v as follows: Similarly, the probability of two vertices not being connected is p increases with the increase in β(u, v), and add-one smoothing is applied to p(E u,v ∈ E) in order to avoid "divided by zero" situation. One can thus obtain the predicted probability p(E u,v ∈ E) from the information of the overlapping community structure OC and the set of thresholds ζ. The idea is that, the more the similarity between the feature vectors of two vertices, the common communities both of them are part of and the similarity threshold of the common communities, the more the membership similarity between them. Given the probability estimation, our model should therefore assure that its resultant network corresponds to the real network.
Let us assume that each edge is generated independently. Then the joint probability of G and OC is estimated as: The log likelihood of the joint probability is: EnCoD attempts to maximize the objective function mentioned in Equation 8 (see line 31 in Algorithm 1) in order to obtain the final overlapping community structure OC.  y): a random number between x and y

Manipulate Community Structure
The framework for manipulating the overlapping community structure in each iteration is shown in Function 2. The function originally starts with the initializations mentioned in lines 7-9 of Algorithm 1. Initially at iteration t = 0, each vertex v is assigned to a separate community OC v 0 with a very high threshold value τ v 0 . In every iteration, we change the memberships of v by removing it randomly from certain communities it belongs to, and assigning it to certain communities where it did not belong to. The threshold corresponding to each community is updated accordingly such that the constraint in Definition 5 is not violated. For a certain community C j , if threshold τ j falls below a certain lower limit τ L , the community is discarded because such a community is too heterogeneous to represent a dense group in our model. The value of τ L is empirically determined as described in Section 5.1. Since we intend to discover the communities of each vertex, in every iteration, we concentrate more on those vertices which are yet assigned to less number of communities, than those vertices which are already assigned to many communities. Therefore, with the increase in the number of communities a vertex is already part of after iteration t, it is less likely that the community membership of v is manipulated at iteration t + 1.
At each iteration t, the function M anipulateComm takes the set of overlapping communities OC t = {OC 1 t , OC 2 t , · · · }. Then for each vertex v, denote the number of communities to remove v from. These variables are measured as follows: Here, p 1 is a random integer chosen from [1, |S2 v t |) such that the number of communities AC v t+1 to add v to, never exceeds |S2 v t |, indicating the number of v's current communities. Similarly, p 2 is an integer randomly chosen from [1, |S1 v t |) such that the value of RC v t+1 is less than or equal to |S1 v t | (number of communities that v is currently part of). Note both the values AC v t+1 and RC v t+1 tend to decrease with the increase of |S1 v t |, ensuring that, the more the number of communities v is currently part of, the less the manipulation of v in the current iteration, and vice versa.
After selecting the number of communities v is to be added to and to be removed from, we choose the set of communities OC AC from S2 v t randomly such that |OC AC | = AC v t+1 and assign v to OC AC (Step 12). Similarly, we randomly choose RC v t+1 many communities (indicated by the set OC RC ) from S1 v t and remove v from it ( Step 14). The corresponding changed communities are updated accordingly.

Update Thresholds and Compute Objective Function
Once the manipulation of the current overlapping community structure is over (as described above), we obtain a new overlapping community structure OC t+1 . The next task is to update the threshold corresponding to the new overlapping community structure (Steps 23-31 in Algorithm 1). For community OC j t+1 ∈ OC t+1 , we set the new threshold τ j t+1 as the minimum value of all the similarities of the OC j t+1 's constituent vertices with OC j t+1 itself, i.e., Step 25). This assignment ensures that Definition 5 is never violated.
Apart from the minimum threshold assigned to each community, we also maintain another global threshold τ L , which ensures the overall coherence among the members in each community. Once all the community-centric thresholds are updated, we further check whether all these thresholds are higher than τ L (Step 26). If some threshold τ j t+1 corresponding to community OC j t+1 falls below τ L , we discard OC j t+1 and set each of its constituent members as a separate community (Steps [26][27][28][29]. The value of τ L controls the size of the final overlapping communities -a higher value of τ L results in smaller community size. The selection of the value of τ L is described later in Section 5.1. Finally, we compute the log likelihood after the current iteration l ζ t+1 (G; OC t+1 ) using Equation 8 (Step 31) and compare it with l ζt (G; OC t ) ( Step 20). If the former is greater than the latter, we keep the current community structure OC t+1 and the current set of thresholds ζ t+1 and continue the iteration. Otherwise, we discard the updated sets and retain the sets obtained in the previous iteration (Step 21). We terminate the process when there is no sufficient increase of the log likelihood. Note that this step is not shown in Algorithm 1 (which rather shows that the iteration immediately stops once the condition is violated) as it depends on the users' confidence on the number of iterations she wants to continue after the log likelihood condition is violated. In practice, continuing the iterations ensures that the algorithm does not get stuck at any local optima of the objective function.

Complexity Analysis
EnCoD terminates when it reaches a maxima of the objective function and the objective function does not change further. In the worst case, after any iteration the maximum number of overlapping communities is |V | and the maximum number of vertices within each community is also |V |. Therefore, the runtime after each iteration is O(|V | + |OC|). Importantly, a manipulation of the current community structure is only possible if the log likelihood increases. Therefore, EnCoD generally converges after a finite number of iterations. In practice, we assume that the local maxima is reached if the log likelihood does not change after |V | iterations.
Note that, since EnCoD is an ensemble algorithm, it requires the running of all base algorithms. However, speedup might be achieved by parallelizing the base algorithms, or by using fewer base algorithms (potentially at the cost of performance, as analyzed later in Section 5).

Experimental Setup
In this section, we describe the datasets and the experimental setup used to evaluate the performance of EnCoD.

Datasets
We use two types of network datasets to evaluate various CD algorithms: (1) Synthetic networks: We use the LFR benchmark model [47] to generate synthetic networks along with their ground-truth communities. We follow the parameters configuration suggested in [9] while generating networks: number of vertices N = 10, 000, average degreek = 50, maximum degree k max = 150, maximum community size c max = 150, minimum community size c min = 50, percentage of overlapping vertices O n = 15%, number of communities to which a vertex belongs O m = 20, and mixing parameter µ = 0.3 (representing the ratio of inter-and intra-community edges; the lower the value of µ, the better the communities are). For each configuration, we create 100 such LFR networks and report the average result. (2) Real-world networks: We use six real-world networks of widely different scales, whose ground-truth communities are available a priori (see Table 2).

Base Disjoint CD Algorithms for Aggregation:
There exist numerous disjoint CD algorithms, which differ in the way they define the community structure. Here we select the following disjoint CD algorithms from different categories based on their working principles: (i) Modularity-based approach: FastGreedy [21], Louvain [19] and CNM [20]; (ii) Node similarity-based approach: WalkTrap [23]; (iii) Compression-based approach: InfoMap [22]; (iv) Diffusion-based approach: Label Propagation [25]. EnCoD ensembles the outputs of all these six algorithms and generates the feature vectors for the vertices.

Experimental Results
In this section, we discuss how the performance of EnCoD depends on various parameters, and compare its performance with state-of-the-art overlapping CD algorithms. We run EnCoD on both synthetic and real-world networks, and compare its performance with that of seven state-of-the-art overlapping CD algorithms.  Figure 2(a) shows that the performance of EnCoD tends to be always superior with INV as permanence.

Parameter Selection
• Similarity between two vertices (SIM): Although in Definition 3, we have mentioned to measure the similarity between the feature vectors of two vertices using cosine similarity, we also measure the similarity with Pearson correlation coefficient between two feature vectors. Cosine similarity turns out to be the better similarity measure than Pearson correlation coefficient (see Figure 2(b)).
• Number of iterations (K): We set K as a function of the number of vertices N in the network. The analysis in Figure 2(c) confirms that for most of the networks, especially the ones which possess distinct community structure (such as LFR network with µ = 0.1, Senate), the performance of EnCoD converges at K = 0.2|V |. We therefore consider this value as default.
• Global threshold (τ L ): τ L controls the size of the overlapping communities -the size changes inversely with the value of τ L . We vary τ L from 0.05 to 0.50 (in steps of 0.05) and observe that the maximum accuracy is attained at τ L = 0.20 for most of the networks (Figure 2(d)). Therefore, unless otherwise stated, we will report the results of EnCoD with the following parameter settings: INV = permanence, SIM = cosine, K = 0.2|V | and τ L = 0.20.

Comparative Evaluation
Here we perform a two-fold evaluation of EnCoD with the baseline algorithms.
Comparison with state-of-the-art overlapping CD algorithms. We run EnCoD and seven other state-of-the-art overlapping CD algorithms on default LFR network and six real-world networks, and compare the output with the ground-truth community structures in terms of three evaluation metrics. Tables 3, 4, and 5 show the performance of the competing methods in terms of ONMI, Ω Index and F-Score respectively.  Overall, EnCoD shows the best performance, followed by BIGCLAM. The absolute average ONMI of EnCoD for all the networks taken together is 0.82, which is 14.08% higher than BIGCLAM (0.71). The absolute average values of Ω index and F-Score for EnCoD are 0.80 and 0.80 respectively.

Effect of Base Algorithms
One can anticipate some noise in the ensemble process due to those base CD algorithms which are generally weak in detecting accurate communities. Therefore we test which base algorithm has the most effect on the final output of EnCoD. To this end, we first consider all base algorithms together and measure the performance of EnCoD. Subsequently, we remove each base  algorithm in isolation (i.e., one at a time) and compare the change in accuracy due to the removal. Figure 3(a) shows that for all the removals, the accuracy decreases significantly. InfoMap (which has been shown to be the best among all the base algorithms [22]) seems to be the one for which the accuracy of EnCoD deteriorates significantly. But Label Propagation and WalkTrap seem to have less effect on the performance of EnCoD.
In another experiment, we remove the base algorithms one after another (not in isolation), and report the performance of EnCoD in Figure 3(b). Even with only the two 'weakest' base CD algorithms (WalkTrap and Label Propagation), EnCoD achieves more than 80% of its performance when all six base algorithms are used.
In general, these results indicate that combining results from all sorts of (strong or weak) base CD algorithms is important to enhance the final performance of the ensemble method. Importantly, using more base algorithms Comparison with PVOC and MEDOC. As mentioned earlier, EnCoD is the fourth algorithm after PEACOCK [16], PVOC [9] and MEDOC [1] which use disjoint community structure to detect the overlapping communities 5 . PVOC has been proved to outperform PEACOCK [9]; hence we compare EnCoD with PVOC along with MEDOC and present the results in Table 6. For all the networks, EnCoD performs significantly better than both PVOC and MEDOC. The performance of EnCoD (PVOC, MEDOC) averaged over all the datasets is as follows -ONMI: 0.82 (0.74, 0.75), Ω Index: 0.81 (0.75, 0.70), F-Score: 0.80 (0.68, 0.76).
The superior performance of EnCoD over PVOC and MEDOC is potentially due to the following reason. In a sense, the final performance of both PVOC and MEDOC depends upon the performance of a single CD algorithm. PVOC brings in the overlapping property as a post-processing step after finding a single disjoint community structure, and hence the quality of the overlapping community structure is dependent upon that of the disjoint community structure found initially. MEDOC uses a CD algorithm to partition the multi-partite network that is created using the base disjoint community structures; hence the quality of the final overlapping community structure depends on the performance of the CD algorithm used over the multi-partite network. On the other hand, EnCoD obtains the features of vertices from the disjoint community structures given by several disjoint CD algorithms, and uses these features in an optimization setting. Thus the performance of EnCoD does not depend upon that of any one CD algorithm, and it can effectively learn from multiple disjoint community structures.

Community Detection with Vertex Features
In Section 3, one could notice that the solutions of the base algorithms are used to derive only the feature vector of each vertex. This approach is useful for most real networks, where additional information about the vertices is unavailable or difficult to obtain [8]. However, we hypothesize that if vertexcentric features are available along with the network structure, our algorithm can equally be effective to adopt these features. In this case, one needs to replace the ensemble-based features with the real features associated with each vertex (i.e., Step 3 in Algorithm 1 is not required in this case).
To show the generic adaptation of EnCoD for overlapping community detection on networks where vertex-features are available, we set the following experimental framework. We acquire a coauthorship network 6 of Computer Science domains, used in [4], where vertices are authors and edges represent collaborations, with at least one paper written by the adjacent authors. There are 24 research areas (such as Algorithms, Data Mining, etc.), and each paper is annotated with one or more research areas. The (overlapping) ground-truth communities are marked by the publication venues (conferences/journals). The network contains 103, 677 vertices, 352, 183 edges and 1, 705 communities.
To obtain vertex features, we assign each author a with a feature vector F a of size 24 where F a (i) denotes the fraction of papers published by a in the i th research area. We run all seven competing algorithms (see Section 4) along with modified non-ensemble based EnCoD (we call it MEnCoD) and detect the underlying community structure. We further consider SPAEM [2], a joint probabilistic model to detect communities by combining node attributes and topological structure, as another baseline. Table 7 shows the performance of all the competing algorithms along with EnCoD and MEnCoD. We observe that MEnCoD is superior to all other competing algorithms (followed by EnCoD).

Conclusion
We proposed EnCoD, the second ensemble algorithm for overlapping community detection by leveraging the outputs of many disjoint CD algorithms. We examined the dependencies of our algorithm on different parameters. We showed that EnCoD significantly outperforms several standard overlapping  CD algorithms, and can be used for detecting the overlapping community structure of networks whose vertices are associated with features. There is still a lack of proper theoretical explanations to justify the superiority of network-based ensemble approaches. Also, since all base CD algorithms are not equally important in terms of community assignment for vertices (as observed in Section 5.3), it might be possible to retain only the most important base CD algorithms through a correlation study or a machine learning-based approach. This could also potentially reduce the runtime cost of the algorithm. We plan to explore this possibility in future.