Detecting overlapping communities using ensemble-based distributed neighbourhood threshold method in social networks

Abstract

In this paper, we have proposed a novel overlapping community detection algorithm based on an ensemble approach with a distributed neighbourhood threshold method (EnDNTM). EnDNTM uses pre-partitioned disjoint communities generated by the ensemble mechanism and then analyzes the neighbourhood distribution of boundary nodes in disjoint communities to detect overlapping communities. It is a form of seed-based global method since boundary nodes are considered as seeds and become the starting point for detecting overlapping communities. A threshold value for each boundary node is used as the minimum influence by the neighbours of a node in order to determine its belongingness to any community. The effectiveness of the EnDNTM algorithm has been demonstrated by testing with five synthetic benchmark datasets and fifteen real-world datasets. The performance of the EnDNTM algorithm was compared with seven overlapping community detection algorithms. The F1-score, normalized mutual information ONMI and extended modularity $Q_{ov}$ metrics were used to measure the quality of the detected communities. EnDNTM outperforms comparable algorithms on 4 out of 5 synthetic benchmarks datasets, 11 out of 15 real world datasets and gives comparable results with the remaining datasets. Experiments on various synthetic and real world datasets reveal that for a majority of datasets, the proposed ensemble-based distributed neighbourhood threshold method is able to select the best disjoint clusters produced by a disjoint method from a collection of methods for detecting overlapping communities.

Keywords

Community detection social networks analysis overlapping communities graph clustering

1. Introduction

Discovering communities in networks from different domains like social networks, biological networks, collaboration networks, word-association networks, traffic networks have a deep history and is of tremendous importance [1, 2]. Since a community is composed of nodes representing the members of a community, and edges representing relationships amongst its members, the study of such community structures in real-world networks reveal significantly important properties of these networks. Consequently, the exploration of methods to extract such communities from these networks is of great importance. Community detection (also termed as graph clustering) where a network is represented as a graph, is a process of grouping the most densely connected nodes of a graph, to form a community (cluster). In general, the nodes of the discovered clusters are associated with a high number of edges within the cluster when compared to the rest of the network. Methods for graph clustering can be categorized in two groups: hard (non-overlapping) clustering and soft (overlapping) clustering.

Figure 1.

Flow diagram of EnDNTM algorithm.

In hard clustering, the graph network is partitioned into disjoint partitions resulting in crisp clusters where each node (member) can belong to at most one cluster only. Well-known disjoint community detection methods include: graph partitioning [3], hierarchical methods [1], random walk [4], methods based on optimization [5] and greedy approach [6]. Recently, a novel tolerance-based method [7] was proposed to detect disjoint communities.

In contrast to hard clustering, in soft clustering, the clusters are overlapped such that a node can belong to more than one cluster. Many real-world networks inherently display overlapping characteristics. For example, in a Facebook network, a user can be a member of many groups such as a study group, sports team or music club. Similarly, co-author networks, collaboration networks are some examples of real-world networks having an overlapping community structure. There are a plethora of methods for detecting overlapping communities in social networks for both synthetic and real-world datasets starting from [8]. Classical strategies include: local expansion of seed nodes [9, 10], label propagation [11, 12, 13], clique-based [14] and ensemble-based methods [15, 16] to name a few.

In general, overlapping community structures are identified using two different strategies. Direct methods where an overlap structure is assumed and naturally occurring communities are detected (where the links between the communities are examined to detect overlapping communities). In contrast, indirect methods assume a partitioned structure, and then proceed to uncover the overlapping structures. It is the second method that is used in this paper, with a focus on detecting overlapping communities using a collection of disjoint methods as a starting point and selecting the best method using an ensemble mechanism for subsequent processing.

In this paper, we propose a new method based on detecting overlapping communities by i) utilizing disjoint communities produced by ensemble method, and ii) analyzing the neighbourhood distribution of boundary nodes in disjoint communities to detect overlapping clusters. The neighbourhood distribution of boundary nodes was first presented in [17]. Our method is akin to the more recent class of ensemble methods [15] that uses disjoint methods as a starting point for development of overlapping method. Figure 1 shows the high level flow of our proposed method.

The contribution of this paper is a novel graph clustering algorithm EnDNTM to detect overlapping clusters by utilizing disjoint clusters produced by an ensemble and analyzing its neighbourhood distribution. This includes an optimized implementation of TCD (tolerance community detection) method to enable it to work efficiently on large networks. The robustness of the EnDNTM method is demonstrated by testing its performance with various well-known overlapping community detection measures. Empirical evidence of our proposed solution is given by comparing the performance of EnDNTM with 8 popular overlapping methods on 5 benchmark synthetic networks and 15 real-world datasets.

The paper is organized as follows: In Section 2 we discuss research related to our paper. In Section 3, we give basic definitions used in this work. In Section 4, we give details of the EnDNTM algorithm and its time complexity. In Section 5, we give implementation details and describe the datasets used in this work. In Section 6, we discuss the results of experiments performed on various synthetic and real-world networks.

2. Related works

Detecting communities in graph networks is an active research area. In the case of real-world social networks, it has been observed that certain node belongs to multiple communities which draw the attention of researcher to study the nature of overlapping communities. Several algorithms have been proposed to discover overlapping communities. Clique percolation method CPM [14] is a clique based approach in which communities are detected by discovering cliques. Since a node can occur in multiple cliques this property resembles the overlapping nature of node hence in CPM this concept is used as a foundation for detecting overlapping communities. Order statistics local optimization method OSLOM [9] follows the local expansion and optimization strategy. In this, community expansion is performed by comparing its statistical significance with the random graph called global model which is generated using the configuration model. In 2010, the label propagation algorithm (LPA) is extended in order to develop Community overlap propagation algorithm COPRA [12] to produce overlapping communities. Speaker-listener label propagation algorithm SLPA [13] is also based on LPA. It uses speaker-listener mechanism to detect communities. Democratic estimate of the modular organization of a network DEMON [11, 18] is another overlapping communities detection algorithm which uses label propagation at its core. In recent years some more methods for finding overlapping communities has been produced which includes Node-centric overlapping community detection algorithm NECTAR [19] it is a node-centric overlapping community detection algorithm in which the best communities for a given node are found using objective function and further this node is added to these communities to obtain the overlapping communities. It is observed that results obtained from the node-centric method are exceptionally good as compared to result obtained from the community-centric method. In this method, Louvain’s local search heuristic approach is generalized to discover overlapping communities. This algorithm tries to maximize the dynamically chosen objective function (i.e. Weighted overlapping community clustering (WOCC) and Extended modularity ( $Q^{E}$ )) by testing every possible existence of each node in it’s neighbouring cluster in order to generate overlapping communities. All the clusters with a maximum value of objective function are considered to obtain the overlapping communities. Internal and external association to detect communities IEDC [20] provides an integrated framework for discovering both overlapping and non-overlapping communities. On one hand, it uses the internal association of node degree which emphasizes non-overlapping pattern discovery. On the other hand, it utilizes the external association of node degree with the motive to uncover the overlapping structure. In this algorithm, it uses features like interaction matrix which is basically the number of connections between any two given communities in order to measure the interaction between two communities. More connections imply high overlap. The next feature is the importance level, which is the count of the total number of internal edges or neighbours termed as $p_{1}$ and the count of the total number of outer edges or neighbours termed as $p_{2}$ . This algorithm begins with some basic community patterns obtained from the network by using a scalable edge clustering mechanism. The propagation probability for each node and for each community is initialized and is further updated. For stabilizing, this method is run for certain number of iterations. Finally, to obtain overlapping communities, nodes are assigned to all such communities, with which it has propagation probability higher than the threshold. Local spectral clustering based approach Local expansion via minimum one norm LEMON [10] was purposed in 2018. This algorithm is based on seed sets, local spectral diffusion, and local spectra concepts. In this method, in order to discover the overlapping community, the subspace around the initial seed sets called local spectra is explored using a short random walk also known as local spectral diffusion. Since the random walk is one of the most effective techniques to discover structure similar to real-world communities, this method is utilized here for expanding the community. In this method, two major limitations of spectral clustering were addressed by i) replacing a large number of singular vectors with short random walks, thereby significantly reducing the computation time, ii) enabling the detection of overlapping communities which was not possible with earlier spectral clustering methods.

Meta clustering based disjoint and overlapping community detection MEDOC [16] and Ensemble-based overlapping community detection EnCoD [15] introduced by Chakraborty et al., are ensemble based overlapping community detection methods which leverages the disjoint clusters generated by disjoint methods.

3. Theoretical framework

3.1 Principles of graph theory

The theoretical concepts, which are used to develop this algorithm, will be introduced in this section.

3.1.1 Undirected graph

A graph $G$ is defined as a pair of ( $V, E$ ) where $V$ is a set consisting all the nodes and $E$ is a set consisting all the edges $E\subseteq V\times V$ . Undirected graphs are such graphs in which if an edge ( $x, y$ ) $\in$ $E$ , then edge ( $y, x$ ) must also be in $E$ . These graphs are also called bi-directional graphs. The degree of a node $v$ is defined as the number of edges containing $v$ . Two nodes are adjacent if they share a common edge.

3.1.2 Path

A path is composed of a series of nodes $P=(v_{1},$ $v_{2},\ldots,v_{n})\in V^{n}$ where $\forall i,1\leqslant i<n$ , $v_{i}$ is adjacent to $v_{i+1}$ . The path length of $P$ is measured as $n-1$ where $n$ is the total number of nodes in path $P$ . It is also measured as the number edge(s) in that path. The path with minimum length (or number of edge(s)) from a source node $s$ to a destination node $d$ is called the shortest path $s p$ from $s$ to $d$ .

3.1.3 Neighbourhood node

In a graph $G(V,E)$ , the neighbourhood of a node $x\in V$ , is all such vertexes $y\in V$ , which are within the threshold distance $\varepsilon$ of $x$ . It is formally defined by Eq. (1):

$\displaystyle N_{r}(x)=_{\text{def}}\{y\in V:\text{dist}(x,y)<\varepsilon\}$ (1)

where

$\displaystyle\text{dist}(x,y)=\begin{cases}\infty&\text{if no $sp$ exists}\\ |sp|&\text{else}\end{cases}$ (2)

where $\varepsilon$ is a user-defined positive real threshold value, $s p$ is the shortest path from $x$ to $y$ and $|sp|$ is the number of edge(s) in $s p$ . A breadth first search is used for traversing the graph in order to find the neighbourhood of any given node. The best value of $\varepsilon$ chosen in this work is 2.

3.2 Preliminaries for clustering

In this section, the basic concepts used for the clustering method described in this work will be explained.

3.2.1 Neighbourhood cluster

Let $C=\{C_{1},C_{2},\ldots C_{m}\}$ be a set of disjoint clusters that cover the graph $G$ , where $C_{i}=\{v_{1},v_{2},\ldots v_{n}\}$ is a cluster or community, such that $v_{i}\in V$ . Let $x\in C_{j}$ where $C_{j}$ is the home cluster, then

$\displaystyle\textit{NC}(x)=_{\text{def}}\{C_{i}\in{C\setminus C_{j}}:\exists y% \in C_{i}\wedge y\in N_{r}(x)\}.$

In Fig. 2, the neighbourhood cluster(s) NC for the green node belonging to cluster ${C_{1}}$ are: clusters ${C_{2}}$ and ${C_{3}}$ . Note, for the green node, cluster ${C_{1}}$ is considered as the home cluster.

3.2.2 Distributed neighbourhood threshold $(D_{t})$

It is the measurement of distribution of neighbours of a node $v$ over the clusters. It is defined as the ratio of total number of the neighbours of given node $v$ over the total number of clusters in which these neighbours are spread. $D_{t}$ for node $v$ is formally defined by Eq. (4).

$\displaystyle D_{t}(v)=_{\text{def}}\left\lfloor{\frac{|N_{r}(v)|}{|\textit{NC% }(v)|+1}}\right\rfloor,$ (4)

where $|N_{r}(v)|$ is the number of neighbours of node $v$ , $|\textit{NC}(v)|$ is the number of neighbourhood clusters of node $v$ . In Eq. (4), the addition of 1 in the denominator represents the inclusion of home cluster.

This parameter is introduced with the intuition that for a node to be included in a cluster, one must consider its edges as one of the important characteristics of that node. In addition, the distribution of these characteristics (edges) is analyzed and the minimum threshold $D_{t}$ is calculated. A node must be placed in all such cluster(s) for which it satisfies the minimum threshold criteria.

3.2.3 Overlapping candidate node

A node $v$ $\in\textit{cluster}C_{j}$ is considered as a candidate overlapping node if it satisfies Eq. (5):

$\displaystyle O_{cn}(v)=_{\text{def}}\{\textit{NC}(v)\neq\emptyset\}.$ (5)

All such nodes that have neighbours outside their home clusters are candidates and are labelled as overlapping candidate nodes.

Figure 2.

Overlapping candidate node.

The green node in Fig. 2 has its neighbours in clusters $C_{2}$ and $C_{3}$ apart from its home cluster $C_{1}$ . Hence it is considered an overlapping candidate node which needs to be investigated in order to identify if it is an overlapping node and also to discover overlapping clusters. Since the overlapping candidate node can have its neighbours distributed over different clusters, the distributed neighbourhood threshold ( $D_{t}$ ) needs to be calculated for this node to decide whether it is an overlapping node or not.

3.2.4 Overlapping node

A overlapping candidate node is classified as overlapping node if its number of neighbours in at least one of its neighbourhood clusters is greater than (or equal to) the distribution threshold $D_{t}$ value. Formally a node $v$ is classified as a overlapping node if for any $C_{i}\in\textit{NC}(v)$ it satisfies the following equation:

$\displaystyle\textit{ON}(v)={}_{\text{def}}O_{cn}(v)\land(D_{t}(v)\leqslant|\{% y:y\in N_{r}(v)\land y\in C_{i}\}|)$ (6)

Figure 3.

Sample overlapping clusters

Example 1 In Fig. 2, the green node in cluster ${C_{1}}$ is an overlapping candidate node since it has neighbours in clusters ${C_{2}}$ and ${C_{3}}$ . All nodes that have neighbours outside their home clusters are considered as overlapping candidate nodes. Using Eq. (4), $|N_{r}(\textit{green node})|=8$ and $|\textit{NC}(\textit{green node})|=2$ , hence $D_{t}(v)=2$ . In other words, $D_{t}(v)$ is considered as the minimum threshold value for a node $v$ to be classified as an overlapping node. As shown in Fig. 2, the green node shares 3 edges with ${C_{3}}$ which also means $|N_{r}(\textit{green node})|$ in $C_{3}$ is 3. Since the cluster ${C_{3}}$ includes neighbours of the green node and $D_{t}(\textit{green node})$ meets the threshold requirement, the green node will be shared with ${C_{3}}$ as shown in Fig. 3.

3.3 Evaluator function

To obtain the best disjoint cluster from a group of disjoint clusters is one of the critical tasks of EnDNTM. In order to filter out the best quality disjoint cluster the following evaluator function is defined. This function is referenced from [7] which is composed of two well-known disjoint cluster quality functions: modularity ( $Q$ ) [21] and coverage [3].

The evaluator function is defined as a combination of modularity $Q$ and coverage:

$\displaystyle\textit{eval}=\eta\cdot Q+(1-\eta)\cdot\text{coverage}$ (7)

where $\eta$ is a constant used to weight the function $Q$ and coverage.

3.4 Cluster quality measures

To measure the quality of generated overlapping clusters, different measures can be used based on the availability of ground-truth values. Measures such as Overlapping Normalized Mutual Information ONMI and F1-score can be used only if the ground-truth communities are available, whereas Extended Modularity $Q_{ov}$ measure does not require ground-truth communities. In this work, we have used ONMI and $F1$ scores and $Q_{ov}$ for synthetic networks, whereas for real world networks we have used only $Q_{ov}$ .

3.4.1 Overlapping normalized mutual information (ONMI)

ONMI [22] is derived from the domain of information theory. It is considered a benchmark to measure the quality of overlapping clusters where the similarity of detected communities are measured using known ground-truth communities. For a given network, $A$ and $B$ are two partitions representing detected communities and ground-truth communities respectively. Overlapping NMI is defined by Eq. (8):

$\displaystyle\textit{NMI}(A,B)=$ $\displaystyle\frac{-2\sum^{C_{A}}_{i=1}\sum^{C_{B}}_{j=1}C_{ij}\log\left(\frac% {C_{ij}.n}{C_{i}.C_{j}}\right)}{\sum^{C_{A}}_{i=1}C_{i}\log\left(\frac{C_{i}}{% n}\right)+\sum^{C_{B}}_{j=1}C_{j}\log\left(\frac{C_{j}}{n}\right)},$ (8)

where $C$ is a confusion matrix, $C_{ij}$ represents the number of common shared nodes in community $i$ of partition $A$ and community $j$ of partition $B$ . The number of clusters in partition $A$ (or $B$ ) is represented by the $C_{A}$ (or $C_{B}$ ). $C_{i}$ (or $C_{j}$ ) is the sum of elements of row $i$ (or column $j$ ). If partitions $A$ and $B$ are identical, then $\textit{NMI}(A,B)=1$ , and $\textit{NMI}(A,B)=0$ is if the partitions $A$ and $B$ are entirely different.

3.4.2 Average F1-Score

F1-Score [23] is another most widely used ground-truth measure to assess cluster quality. In this method the generated cluster is compared with the best matching cluster of ground-truth cover. It is computed as the harmonic mean of Precision and Recall.

The best value obtained for $\text{F1-Score}=1$ whereas F1-Score $=0$ is obtained for the worst quality cluster. F1-Score is defined by Eq. (9):

$\displaystyle F1=\frac{2*\textit{Precision}*\textit{Recall}}{\textit{Precision% }+\textit{Recall}},$ (9)

where Precision is the percentage of nodes in $X$ labeled as $Y$ and defined as

$\displaystyle\textit{Precision}=\frac{|X\cap Y|}{|X|}\in[0,1],$ (10)

Recall is the percentage of nodes in $Y$ covered by $X$ and defined as

$\displaystyle\textit{Recall}=\frac{|X\cap Y|}{Y}\in[0,1].$ (11)

3.4.3 Extended modularity (

Q_{ov}

)

To measure the quality of generated overlapping clusters, Extended Modularity( $Q_{ov}$ ) [24, 25] is used. The Extended Modularity does not require the ground-truth clusters to measure the quality of the generated clusters.

$\displaystyle Q_{ov}=$ (12) $\displaystyle\frac{1}{m}\sum_{c\in C}\sum_{i,j\in V}\left[\beta_{l(i,j),c}A_{i% ,j}-\frac{\beta_{l(i,j),c}^{\text{out}}k_{i}^{\text{out}}\beta_{l(i,j),c}^{% \text{in}}k_{j}^{\text{in}}}{m}\right],$

In this section, we have utilized Extended Modularity ( $Q_{ov}$ ) introduced by Nicosia in [24, 25]. It uses Eq. (3.4.3) to measure the quality of the generated clusters where $V$ is the set of nodes, $|V|$ represents the number of nodes, $C$ is set of overlapping clusters, $m$ is the total number of edges and $A_{i,j}$ is the Adjacency Matrix for the Graph.

$\displaystyle\beta_{l(i,j),c}^{\text{in}}=\frac{\sum_{i\in V}{F(\alpha_{i,c},% \alpha_{j,c})}}{|V|}$ (13) $\displaystyle\beta_{l(i,j),c}^{\text{out}}=\frac{\sum_{j\in V}{F(\alpha_{i,c},% \alpha_{j,c})}}{|V|}$ (14)

In overlapping communities, each node can belong to multiple communities but with different strengths of belonging. An array of belonging factor $[\alpha_{i,1},\alpha_{i,2},$ $(\alpha_{i,|C|}]$ is calculated and allotted to each node $i$ in the graph $G$ . The strength of node $i$ belonging to community $c$ is measured by the coefficient $\alpha_{i,c}$ . Since the belonging coefficient for each node is already defined, it is also possible to define the belonging coefficient to each community for edges incoming to or outgoing from a node. Belonging coefficient of edge $l=(i,j)$ with source node $i$ and target node $j$ to community $c$ is represented by function $\beta_{l,c}$ . Further, the belonging coefficient for link $l(i,j)$ pointing to a node going into the community $c$ is represented by $\beta_{l(i,j),c}^{\text{in}}$ and is given by Eq. (13). The belonging coefficient for link $l(i,j)$ pointing to a node going out of the community $c$ is obtained by using Eq. (14) and is represented by $\beta_{l(i,j),c}^{\text{out}}$ . Extended Modularity measures for overlapping clusters depend on $F(\alpha_{i,c},\alpha_{j,c})$ which is defined in the Eq. (15):

$\displaystyle F(\alpha_{i,c},\alpha_{j,c})=\frac{1}{(1+e^{-f(\alpha_{i,c})})(1% +e^{-f(\alpha_{j,c})})},$ (15)

where $f(\alpha_{i,c})$ is a simple linear scaling function:

$\displaystyle f(x)=2px-p,∼{}p\in\mathcal{R}.$ (16)

The value of $p$ is set to 30 in [25]. Generally, good quality overlapping clusters have higher $Q_{ov}$ value. The value of $Q_{ov}$ will be 0 when only one cluster is obtained with all the nodes in it.

4. Ensemble-based distributed neighbourhood threshold method

EnDNTM algorithm takes crisp partitioned clusters produced from a family of disjoint methods and generates overlapping clusters irrespective of the specific method used to produce the disjoint clusters. The motivation underlying EnDNTM is to take advantage of the best disjoint clusters generated by pre-existing non-overlapping algorithms and analyzing the obtained disjoint clusters to produce overlapping clusters for a given real-world network. Details of the EnDNTM algorithm shown in Fig. 1 are given in the following sections.

4.1 Generate non-overlapping clusters

In step 4.1.2, for a given input graph $G(V,E)$ 5 disjoint methods: Louvain [5], Girvan-Newman [1], Greedy Modularity [6], InfoMap [4] and recently introduced tolerance-based TCD [7] methods were used to generate crisp clusters.

TCD is computationally bound to work with smaller networks (the biggest network tested is Political Books [26] with 105 nodes and 441 edges). In EnDNTM this limitation of TCD is addressed by optimizing it with multi-processing parallelization to enable it to work efficiently with bigger networks (like Pretty Good Privacy Network [27] with 10680 nodes and 24316 edges). Figure 4 shows the flow of optimized TCD where i) all combinations of parameters ( $\varepsilon,\alpha,\beta$ ) are generated, ii) multiple processes are launched in parallel, each executing the TCD algorithm with a single combination of parameters, iii) the best cluster evaluated by an objective function defined in [7] is retrieved.

Figure 4.

Flow of optimized TCD

The architecture of EnDNTM is given in Fig. 5. For a given graph, all such disjoint methods with non-deterministic output will be executed 10 times and the best cluster measured by the evaluator function is stored. Disjoint methods with deterministic output are executed only once and the generated clusters are stored. All of the obtained disjoint clusters are further evaluated using an evaluator function in order to obtain the best cluster.

Figure 5.

Architecture of EnDNTM

4.1.1 Evaluator function

[!ht] Evaluator functionProcedure evalFunction $G,\text{clusterList}$

$\eta\leftarrow 0.5$

$mod\leftarrow\text{modularity}(G,\text{clusterList})$

$cover\leftarrow\text{coverage}(G,\text{clusterList})$

$val\leftarrow(1-\eta)*\text{cover}+\eta*mod$

$v a l$

Generate disjoint clustersProcedure generateDisjointClusters $G,d_{m},\textit{shrQ},\textit{lock}$ $d_{m}=d_{m_{1}}$

clusterList $\leftarrow d_{m_{1}}(G)$

$d_{m}=d_{m_{2}}$

clusterList $\leftarrow d_{m_{2}}(G)$ $d_{m}=d_{m_{3}}$

clusterList $\leftarrow d_{m_{3}}(G)$ $d_{m}=d_{m_{n}}$

clusterList $\leftarrow d_{m_{n}}(G)$

$val\leftarrow\textit{evalFunction}(G,\textit{clusterList})$

lock.acquire()

shrDict $\leftarrow$ shrQ.get() val $>$ shrDict[1]shrDict[1] $\leftarrow$ val

shrDict[2][1] $\leftarrow d_{m}$

shrDict[2][2] $\leftarrow$ clusterList

shrQ.put(shrDict)

lock.release()

Algorithm 4.1.1 describes the evaluator function. It takes a graph $G$ and list of clusters clusterList derived from $G$ as input and computes the value representing the quality of input in clusterList. In this function, the quality of clusters is computed using the objective function defined in Eq. (7) where modularity and coverage are used in combination. Higher values indicate good quality clusters. Here $\eta$ is used as weighted variable to prioritize the measures. The best value of $\eta$ observed for this work was 0.5.

4.1.2 Generate disjoint clusters

Algorithm 4.1.1 represents a generic disjoint community wrapper function responsible for generating disjoint clusters using any disjoint algorithm. Graph $G$ , disjoint method $d_{m}$ , shared Queue shrQ and shared lock lock are passed as input to this algorithm. It generates the disjoint clusters for a graph $G$ by applying disjoint method $d_{m}$ on $G$ . Next, the generated clusters are evaluated using evaluator function described in the previous section. If the quality of these generated clusters (output of the evaluator function) is higher than existing clusters in shrQ, then these clusters are updated in shrQ. Since the shrQ is shared with multiple processes, in order to avoid a race condition, a lock is acquired on shrQ, before updating shrQ. Once the update is done, lock is released.

4.1.3 Ensemble method

The ensemble mechanism given in Algorithm 4.1.3, takes a graph $G$ and a list of disjoint methods stored in $D_{m}\textit{List}$ . It starts with initializing shared queue shrQ which is used to store the best quality cluster and is shared between different processes. This function is a multiprocess method, in which for each disjoint method $d_{m}$ in $D_{m}\textit{List}$ , a process is launched in order to operate on all the disjoint methods in parallel. At end of this process, the best cluster measured by the evaluator function which resides in shrQ is retrieved from shrQ for further processing. This method acts as driver function for generating the best disjoint clusters using a variety of disjoint methods.

Ensemble methodProcedure ensembleMethod $G,D_{m}\textit{List}$

$val\leftarrow 0$

method $\leftarrow\emptyset$

clusterList $\leftarrow\emptyset$

algClstr $\leftarrow$ {method, clusterList}

shrDict $\leftarrow$ {val, algClstr}

shrQ $\leftarrow$ Queue()

shrQ.put(shrDict)

lock $\leftarrow$ multiprocessing.lock()

Processes $\leftarrow\emptyset$

disjoint method $d_{m}\in D_{m}\textit{List}$

$p\leftarrow$ multiprocessing.Process(generateDisjointClusters, $d_{m}$ , $G$ , shrQ, lock)

Processes.append( $p$ )

p.start()

Process $p\in$ Processes p.join()

recvDict $\leftarrow$ shrQ.get()

val $\leftarrow$ recvDict[1]

$bestD_{m}\leftarrow$ recvDict[2][1]

clusterList $\leftarrow$ recvDict[2][2]

clusterList

[!h] Find overlapping clustersProcedure findOverlapCluster $G,L,\epsilon$

$NC_{\text{dic}}\leftarrow\emptyset$

$L_{\text{dic}}\leftarrow\emptyset$

$L_{o}\leftarrow\emptyset$

$c_{id}\leftarrow 0$ cluster $C\in L$

$c_{id}\leftarrow c_{id}+1$ node $v\in C$

$NC_{\text{dic}}[v]\leftarrow c_{id}$

$L_{\text{dic}}[c_{id}]\leftarrow C$

$C_{o}N_{\text{dic}}\leftarrow\emptyset$

$N_{r}N_{\text{dic}}\leftarrow\emptyset$ cluster $C\in L$ node $v\in C$

$N_{r}(v)\leftarrow\textit{BFS}(G,v,\epsilon)$

$N_{r}N_{\text{dic}}[v]\leftarrow N_{r}(v)$

$N_{r}(v)\leftarrow N_{r}(v)-C$ $N_{r}(v)\neq\emptyset$ $C_{o}N_{\text{dic}}[v]\leftarrow N_{r}(v)$ $v\in C_{o}N_{\text{dic}}.keys()$

$N_{r}C_{\text{dic}}\leftarrow\emptyset$

$N_{r}(v)\leftarrow C_{o}N_{\text{dic}}[v]$ vertex $v_{n}\in N_{r}(v)$

$c_{id}\leftarrow NC_{\text{dic}}[v_{n}]$

$N_{r}C_{\text{dic}}[c_{id}]\leftarrow\{v_{n}\}$

$NC(v)\leftarrow N_{r}C_{\text{dic}}.keys()$

$D_{t}(v)\leftarrow{\displaystyle\frac{|N_{r}N_{\text{dic}}[v]|-1}{|NC(v)|+1}}$

clusterId $c_{id}\in NC(v)$ $\textit{Size}(N_{r}C_{\text{dic}}[c_{id}])\geqslant D_{t}(v)$

$L_{\text{dic}}[c_{id}]\leftarrow L_{\text{dic}}[c_{id}]\cup v$ clusterId $c_{id}\in L_{\text{dic}}.keys()$ $L_{o}.append(L_{\text{dic}}[c_{id}])$

$L_{o}$

The generated clusters in this step is used as input along with the input graph $G$ and a distance threshold $\varepsilon$ , to the findOverlapCluster function given in Algorithm 4.1.3. What follows is a detailed discussion of the steps used in this function.

4.2 Find overlapping clusters

There are four main steps in this method which are described below and refer to line numbers in Algorithm 4.1.3.

4.2.1 Preprocessing disjoint clusters

Preprocessing of disjoint clusters is done in order to create and store the information required for generating overlapping clusters. Two data structures: Node-Cluster Dictionary $\textit{NC}_{\text{dic}}$ and Cluster-Node Dictionary $L_{\text{dic}}$ are created. $\textit{NC}_{\text{dic}}$ stores the cluster information of each node. It takes a node as a key and stores the cluster Id to which it belongs to and is created by assigning Id of cluster $C$ to each node $v$ of a cluster $C$ (shown in lines 8–9). This dictionary is used to identify the cluster id of the neighbourhood node. $L_{\text{dic}}$ is designed to save clusters along with its Ids. Alternatively, it also consists of information about all the nodes in a cluster. It is constructed by allocating an id to each cluster $C$ (shown in lines 6–10). Using this dictionary, the required cluster is retrieved, which is updated with the overlapping node in order to get the overlapping clusters.

4.2.2 Find overlapping candidate node

In order to find an overlapping candidate node, Node-Neighhbour Dictionary $N_{r}N_{\text{dic}}$ and Overlapping-Candidate-Node Dictionary $C_{o}N_{\text{dic}}$ data structures are constructed and utilized. Each cluster $C$ in cluster list $L$ and each node $v$ in cluster $C$ is inspected. To obtain all the neighbours of $v$ , a breadth-first search BFS is performed and the obtained neighbour $N_{r}$ is stored in $N_{r}N_{\text{dic}}$ . Outer neighbour(s) are obtained by removing the neighbours of home cluster $C$ from $N_{r}$ . If a node $v$ has outer neighbour(s) in $N_{r}$ , then the node $v$ is candidate and considered as an overlapping candidate node. The outer neighbour(s) $N_{r}$ is stored in $C_{o}N_{\text{dic}}$ with $v$ as its key (shown in lines 13–19).

4.2.3 Calculate distributed neighbourhood threshold

Prior to computing $D_{t}$ , the information about outer neighbour(s) and neighbourhood cluster(s) of a node $v$ is required. Hence each outer neighbour of node $v\in N_{r}(v)$ , is stored along with its clusterd id in the NeighbourNode-Cluster dictionary $N_{r}C_{\text{dic}}$ (shown in lines 20–25). To calculate $D_{t}$ , distinct neighbourhood clusters are retrieved from $N_{r}C_{\text{dic}}$ and stored in $\textit{NC}(v)$ and the count is incremented by 1 to include the home cluster $C$ . Next, the count of the total number of neighbours of node $v$ is obtained from $N_{r}N_{\text{dic}}$ which also includes node $v$ . Hence the count is decremented by 1. Finally, $D_{t}$ is calculated by using Eq. (4) (shown in lines 26–27).

4.2.4 Filter overlapping node

Using $D_{t}$ calculated in the previous step, for a given overlapping candidate node $v_{p}$ , each of its neighbourhood clusters in $N_{r}C_{\text{dic}}[c_{id}]$ is examined. If any of these clusters have the number of neighbours of $v_{p}$ greater than or equal to $D_{t}$ , then $v_{p}$ is classified as an overlapping node $v$ (shown at line 29). Hence $v$ must be included in these clusters $L_{\text{dic}}[c_{id}]$ .

4.2.5 Generate overlapping clusters

This is the final step of the EnDNTM algorithm. In this step, the actual overlapping clusters are generated shown in lines 31–33. The overlapping node $v$ detected in previous step is included in all such clusters $L_{\text{dic}}[c_{id}]$ which satisfies Eq. (17).

$\displaystyle\text{Size}(N_{r}C_{\text{dic}}[c_{id}])\geqslant D_{t}$ (17)

Each of the resultant clusters are stored in the overlapping clusters list $L_{o}$ .

4.3 Time complexity

From a detailed analysis of the EnDNTM Algorithm, it can be observed that it is composed of two modules: first obtaining the disjoint clusters and next finding the overlapping clusters.

4.3.1 Time complexity for disjoint cluster detection

The run time of each disjoint method is given in Table 1 where $n$ represents the number of nodes, $m$ represents the number of edges. Further in TCD method, $b$ represents the branching factor and $\varepsilon$ represents the maximum depth of the BFS. Similarly, in the Greedy Modularity method, $d$ represent the depth of the dendrogram. To obtain better performance, we have optimized the EnDNTM method with multiprocessing, where each disjoint method executes in parallel.

Table 1
Running time of disjoint methods

Disjoint method	Time complexity
TCD	$O(n^{2}+n\cdot b^{2\varepsilon})$
Louvain	$O(n\log n)$
Girvan-Newman	$O(m^{2}n)$
Greedy modularity	$O(md\log n)$
InfoMap	$O(m)$

4.3.2 Time complexity for overlapping cluster detection

In the EnDNTM algorithm for a graph $G(V,E)$ , the time complexity for pre-processing the disjoint clusters is $O(|L|.|C|)$ . This is less than or equal to $O(|V|)$ , where $|L|$ is the number of disjoint clusters, $|C|$ represents the number of nodes in a cluster $C$ and $|V|$ represents the total number of nodes in graph $G$ . Time complexity of BFS is $O(b^{d})$ where $b$ is branching factor and $d$ is maximum depth. In EnDNTM, we consider neighbours at depth 1, so time complexity is $O(b)$ . To find overlapping candidate nodes, the time complexity is $O(|L|.|C|).O(b)=O(|V|.b)$ . To filter overlapping nodes, the time complexity is $O(|\textit{OCN}|).O(|N_{r}|+|N_{r}C_{\text{dic}}|)$ where $|\textit{OCN}|$ is the number of overlapping candidate nodes, $|N_{r}|$ is the number of neighbourhoods in other clusters and $|N_{r}C_{\text{dic}}|$ is the number of neighbourhood clusters. Since $|N_{r}|\geqslant|N_{r}C_{\text{dic}}|$ , the time complexity will be $O(|\textit{OCN}|.|N_{r}|)$ . Finally, the overlapping clusters is obtain in $O(|L|)$ time complexity. So, the final time complexity for overlapping cluster detection is $O(|V|.b+|\textit{OCN}|.|N_{r}|)$ .

5. Implementation and data sets

This section includes a description of data structures and frameworks used for manipulating the input graph, the development environment used for the coding of the EnDNTM method, followed by a detailed explanation of datasets used in this work.

5.1 Data structures used in EnDNTM

Various other data structures used include dictionary, sets, lists and numpy array. Some of them are illustrated in Table 2.

Table 2
Data structure used in EnDNTM

Symbol	Definition
$N_{r}$	Set of neighbourhood node
$L_{o}$	Set of overlapping clusters
$NC_{\text{dic}}$	Node-cluster dictionary
$L_{\text{dic}}$	Cluster-node dictionary
$N_{r}C_{\text{dic}}$	Neighbour node-cluster dictionary
$C_{o}N_{\text{dic}}$	Overlapping-candidate-node dictionary
$N_{r}N_{\text{dic}}$	Node-neighbour dictionary

5.2 Development environment

For the development of the overlapping method proposed in this work, we used Python programming language version 2.7 and 3.6, Networkx libraries, and Gephi 0.9.2. The hardware configuration was IntelCore i7 CPU 3.6 GHz, 16GB RAM, 500GB SSD with Ubuntu 16.04 and 18.04 operating system.

5.3 Datasets used for experiment

Various small, medium and large-sized real-world datasets with good mixture of social, biological, collaboration and word association network were used for experiments. To test the communities generated by EnDNTM method with ground-truth communities, system generated synthetic networks [28] also known as the LFR benchmark network [8] were used. The input data file was pre-processed by removing repeated edges, self loop and converting non-compatible formats into required formats. Table 3 shows the default number of edges before pre-processing and after pre-processing for the real-world dataset along with the number of nodes. A brief description of these datasets is given in following subsections.

5.3.1 Real-world networks

Table 3
Summary of real-world networks

Datasets	Vertices	Edges (default)	Edges (preprocessed)
Karate [29]	34	78	78
Dolphin [30]	62	159	159
Lesmis [31]	77	254	254
Football [1]	115	613	613
Polbooks [26]	105	441	441
Jazz [32]	198	2742	2742
Power grid [33]	4941	6594	6594
Drugnet [34]	293	286	286
Highschool [27]	70	366	275
Netscience [35]	379	914	914
C.elegans [36]	453	4596	4574
Bible-names [27]	1773	16401	9131
Protein [27]	1870	2777	2203
Internet-Route [37]	6474	13895	12572
PGP [38]	10680	24316	24316

5.3.2 LFR benchmark networks

In this work, we have used five LFR benchmark networks [28] to evaluate the EnDNTM method on synthetic networks and to examine the accuracy of communities discovered by the EnDNTM with the ground-truth communities generated by LFR. Detailed description of these synthetic networks is given in Table 4 where Bench_30 represents the benchmark network with 30 nodes, Bench_40 represents the benchmark network with 40 nodes and so on,

Table 4
Summary of synthetic networks, where $N_{ovr}$ is the number of overlapping nodes and $Avg_{cc}$ is the average clustering co-efficient

Datasets	Vertices	Edges (default)	Edges (pre-processed)	Clusters	$N_{ovr}$	$Avg_{cc}$
Bench_30	30	120	60	3	2	0.419
Bench_40	40	220	110	3	5	0.416
Bench_50	50	282	141	4	4	0.396
Bench_60	60	260	130	6	4	0.577
Bench_60_dense	60	262	131	6	5	0.313

Table 5

F1-score for synthetic networks with all disjoint methods

Datasets	EnDNTM (TCD)	EnDNTM (LN)	EnDNTM (GN)	EnDNTM (GM)	EnDNTM (IM)	EnDNTM (ensemble)
Bench_30	0.940	0.940	0.477	0.642	0.940	0.94 (TCD)
Bench_40	0.690	0.384	0.433	0.697	0.256	0.697 (GM)
Bench_50	0.665	0.775	0.410	0.528	0.797	0.67 (TCD)
Bench_60	0.232	0.793	0.232	0.662	0.652	0.652 (IM)
Bench_60_dense	0.222	0.513	0.183	0.337	0.407	0.407 (IM)

Table 6

ONMI-score for synthetic networks with all disjoint methods

Datasets	EnDNTM (TCD)	EnDNTM (LN)	EnDNTM (GN)	EnDNTM (GM)	EnDNTM (IM)	EnDNTM (ensemble)
Bench_30	0.902	0.902	0.477	0.642	0.902	0.94 (TCD)
Bench_40	0.526	0.487	0.487	0.567	0.404	0.567 (GM)
Bench_50	0.670	0.698	0.483	0.694	0.741	0.67 (TCD)
Bench_60	0.312	0.674	0.312	0.683	0.622	0.622 (IM)
Bench_60_dense	0.281	0.586	0.269	0.427	0.515	0.515 (IM)

6. Experiments, results and analysis

To examine the performance of EnDNTM, experiments with 15 real world datasets and 5 synthetic benchmark networks were carried out. The $F1$ , ONMI and $Q_{ov}$ measures were used as metrics to measure the quality of the detected communities.

6.1 Experiment with various disjoint methods

Since EnDNTM leverages a variety of disjoint methods to produce crisp clusters, it is critical to select best quality crisp clusters in order to generate good quality overlapping clusters. EnDNTM is first executed with each disjoint method separately. For example, EnDNTM (TCD) represents the independent execution of EnDNTM with the input crisp clusters obtained from disjoint TCD (Tolerance Community Detection) method. Similarly, EnDNTM (LN), EnDNTM (GN), EnDNTM (GM), EnDNTM (IM) represent independent execution of EnDNTM with disjoint methods Louvain, Girvan Newman, Greedy Modularity and InfoMap respectively. EnDNTM (Ensemble) represents the execution of EnDNTM with all disjoint methods taken together. Next, the generated overlapping clusters are evaluated using classical measures such as ONMI, $F1$ and $Q_{ov}$ to identify the disjoint method that produces the best overlapping clusters for each network and to identify the disjoint method selected by EnDNTM (Ensemble). It should also be noted that disjoint method TCD tends to produce varying results for each of the measures with every execution. As a result, in this work, any disjoint method producing a varying result is executed 10 times and an average of the top 5 results was used for reporting. In other words, the EnDNTM results reported is the outcome of an average of several runs of a specific method in order to accommodate for the variations in the results.

6.1.1 Synthetic networks

Since the ground-truth clusters are only available for large networks like DBLP [39], Amazon [39] etc, in such cases, computer generated benchmark network(s) known as synthetic network(s) are used. In EnDNTM it is observed that it generates consistent result with both version of input file (i.e. repeated and non-repeated edgelist). Detailed analysis of results obtained using $F1$ , ONMI and $Q_{ov}$ measures for overlapping clusters generated by EnDNTM executed taking each disjoint method separately on synthetic network is explained below.

Table 7
$Q_{ov}$ -score for synthetic networks with all disjoint methods

Datasets	EnDNTM (TCD)	EnDNTM (LN)	EnDNTM (GN)	EnDNTM (GM)	EnDNTM (IM)	EnDNTM (ensemble)
Bench_30	0.7489	0.7489	0.4046	0.6836	0.7489	0.7489 (TCD)
Bench_40	0.6240	0.5760	0.5590	0.6160	0.4930	0.616 (GM)
Bench_50	0.6902	0.6798	0.3718	0.5148	0.6734	0.6902 (TCD)
Bench_60	0.7130	0.6457	0.7128	0.6612	0.7876	0.7876 (IM)
Bench_60_dense	0.4330	0.4814	0.4597	0.3111	0.5575	0.5575 (IM)

Table 8

$Q_{ov}$ -score for Real-World Networks with all disjoint methods

Datasets	EnDNTM (TCD)	EnDNTM (LN)	EnDNTM (GN)	EnDNTM (GM)	EnDNTM (IM)	EnDNTM (ensemble)
Karate	0.734	0.6150	0.7185	0.5861	0.7136	0.734 (TCD)
Dolphins	0.744	0.6193	0.7232	0.7359	0.6431	0.7232 (GN)
Lesmis	0.755	0.6644	0.2689	0.7034	0.5795	0.755 (TCD)
Football	0.773	0.6563	0.7777	0.6493	0.6333	0.77 (TCD)
Polbooks	0.832	0.8138	0.8090	0.8250	0.7886	0.831 (TCD)
Jazz	0.643	0.7064	0.0379	0.7016	0.7303	0.7303 (IM)
Power	0.905	0.9513	0.8709	0.9511	0.6831	0.9513 (LN)
Durgnet	0.842	0.7299	0.8654	0.7907	0.4568	0.7907 (GM)
Highschool	0.783	0.5909	0.5964	0.7329	0.5516	0.786 (TCD)
Netscience	0.952	0.9100	0.8674	0.9256	0.7958	0.9256 (GM)
C.elegans	0.665	0.3668	0.0756	0.5035	0.1583	0.666 (TCD)
Bible names	0.696	0.3664	0.1000	0.5815	0.1909	0.5815 (GM)
Protein	0.805	0.8076	0.6095	0.8172	0.6050	0.8172 (GM)
Internet route	0.527	0.4348	0.0152	0.4375	0.2408	0.4348 (LN)
PGP	0.818	0.8986	0.2042	0.9082	0.7062	0.8986 (LN)

Analysis using F1-Score:

Table 5 gives the F1-Score of EnDNTM algorithm on 5 synthetic datasets and with 5 disjoint methods. The results in BOLD are the best values. EnDNTM represents the F1-Score for the score after the selection of one of the methods. For the dataset Bench_30, it can be observed that EnDNTM with TCD, LN, IM produce the best score, whereas the final F1-Score is obtained by selecting the TCD method. In this case, since TCD, LN, IM all produce the same score, the first one in the list is chosen. For the dataset Bench_50, the final F1-Score is obtained using TCD rather than IM. This is a case where the best disjoint method was not chosen by the EnDNTM algorithm. The same problem shows up with datasets Bench_60 and Bench_60_dense

Analysis using ONMI-Score:

Table 6 gives ONMI-Score for overlapping clusters generated by the EnDNTM algorithm with each disjoint method separately. EnDNTM represents the ONMI-Score for the score after the selection of one of the methods. As mentioned in previous section, in this table also, results in BOLD are the best values. Again, for datasets Bench_50, Bench_60 and Bench_60_dense, the best disjoint method was not chosen by the EnDNTM algorithm.

Analysis using $Q_{ov}$ -Score:

Table 7 gives $Q_{ov}$ -Score for overlapping clusters generated by EnDNTM algorithm with each disjoint method separately. EnDNTM represents the $Q_{ov}$ -Score for the score after the selection of one of the methods. As mentioned in previous section, in this table also, results in BOLD are the best values. Here, for only one dataset Bench_40, the best disjoint method was not chosen the EnDNTM algorithm. In other words, EnDNTM ensemble method does best in terms of the $Q_{ov}$ -Score on synthetic networks.

6.1.2 Real world networks

Here, 15 real-world networks from different domains such as social, collaboration, protein, word-association networks were used.

Analysis using $Q_{ov}$ -Score:

Since the $Q_{ov}$ measure does not require ground-truth communities, it is used here to evaluate the overlapping clusters generated by EnDNTM. Table 8 gives the score obtained after evaluating overlapping clusters for each of the networks using $Q_{ov}$ . TCD is favoured in 6 out of 15 cases, followed by GM and then LN.

6.2 Cluster analysis

In this section we will analyze the generated overlapping clusters by EnDNTM, and compare it with the ground-truth clusters generated by the LFR benchmark network for Bench_30. The system generated ground-truth clusters by LFR for the synthetic network Bench_30 is given in Fig. 6. It consists of three clusters with two overlapping nodes [12,21].

Clusters detected for the Bench_30 network by EnDNTM is given in Fig. 7. From Fig. 7, it can be seen that EnDNTM is able to discover three clusters which is identical to the ground-truth clusters and four overlapping nodes [12,17,18,21] including two ground-truth overlapping nodes [12,21].

The overlapping nodes classified by other overlapping methods is shown in Table 9 along with number of communities detected.

Figure 6.

Ground-truth clusters of the LFR benchmark network (Bench_30).

Figure 7.

EnDNTM generated clusters for the LFR benchmark network (Bench_30).

Table 9

Overlapping nodes for Bench_30 network

Algorithm	OverlappingNodes	Communities
COPRA	10, 11, 21	4
SLPA	16, 22, 18, 21, 19, 20	6
NodePer.	26, 28, 22, 25, 23, 21, 29, 30, 24, 27, 16, 20	17
CONGO $(h=2)$	27, 30	3
CONGO $(h=3)$	27, 29, 30	3

Table 10

F1-score for Synthetic Networks with different algorithms

Datasets	CPM	OSLOM	COPRA	SLPA	NodePer.	DEMON	CONGO $(h=2)$	CONGO $(h=3)$	EnDNTM
Bench_30	0.813	0.430	0.685	0.317	0.056	0.590	0.807	0.793	0.940
Bench_40	0.236	0.213	0.544	0.211	0.044	0.407	0.363	0.443	0.697
Bench_50	0.632	0.710	0.587	0.511	0.045	0.610	0.249	0.229	0.670
Bench_60	0.587	0.232	0.267	0.324	0.115	0.282	0.188	0.326	0.652
Bench_60_dense	0.155	0.083	0.139	0.203	0.054	0.135	0.083	0.083	0.407

Table 11

ONMI-score for synthetic networks with different algorithms

Datasets	CPM	OSLOM	COPRA	SLPA	NodePer.	DEMON	CONGO $(h=2)$	CONGO $(h=3)$	EnDNTM
Bench_30	0.633	0.246	0.702	0.538	0.291	0.596	0.539	0.561	0.902
Bench_40	0.261	0.086	0.389	0.433	0.293	0.211	0.289	0.394	0.567
Bench_50	0.592	0.516	0.638	0.733	0.441	0.456	0.487	0.453	0.670
Bench_60	0.497	0.244	0.459	0.523	0.423	0.347	0.441	0.477	0.622
Bench_60_dense	0.053	0.044	0.177	0.281	0.134	0.069	0.143	0.075	0.515

Table 12

$Q_{ov}$ -score for Synthetic Networks with different algorithms

Datasets	CPM	OSLOM	COPRA	SLPA	NodePer.	DEMON	CONGO(h=2)	CONGO $(h=3)$	EnDNTM
Bench_30	0.653	0.659	0.735	0.691	0.116	0.603	0.720	0.662	0.7489
Bench_40	0.538	1.85E-13	0.580	0.559	0.113	0.431	0.352	0.535	0.6160
Bench_50	0.626	0.715	0.560	0.634	0.138	0.289	0.490	0.408	0.6902
Bench_60	0.701	0.713	0.738	0.672	0.331	0.409	0.383	0.365	0.7876
Bench_60_dense	0.435	1.39E-13	0.389	0.551	0.100	0.300	0.307	0.258	0.5575

Figure 8.

Comparison of EnDNTM using F1-score on synthetic networks.

Figure 9.

Comparison of EnDNTM using ONMI-score on synthetic networks.

Figure 10.

Comparison of EnDNTM using $Q_{ov}$ -score on synthetic networks.

6.3 Comparison with various overlapping methods

We have compared the performance of the EnDNTM algorithm with seven overlapping community detection algorithms: CPM [14], OSLOM [9], COPRA [12], SLPA [13], Node Perception [40], DEMON [11, 18], CONGO [41] with $h=$ 2 and $h=$ 3. Most of these algorithms are available in CDlib [42] Python package. Results using $F1$ measure for synthetic networks is given in Table 10. Results for ONMI and $Q_{ov}$ for synthetic networks are given in Tables 11 and 12 respectively. Bold values represent the best score among all the algorithms. Also, Figs 8–10 visually represent the performance of EnDNTM on synthetic networks in comparison with other overlapping methods using $F1$ , ONMI and $Q_{ov}$ measures respectively. It can be observed that EnDNTM outperforms the other overlapping methods in 4 out of 5 synthetic datasets, and produces the second best result in the 5th dataset.

Table 13
$Q_{ov}$ -score for real-world networks with different algorithms

Datasets	CPM	OSLOM	COPRA	SLPA	NodePer.	DEMON	CONGO $(h=2)$	CONGO $(h=3)$	EnDNTM
Karate	0.510	0.7099	0.7228	0.5405	0.1944	0.380	0.3423	0.4880	0.7340
Dolphins	0.660	0.7426	0.7434	0.7231	0.1947	0.457	0.4085	0.1340	0.7232
Lesmis	0.586	0.6908	0.7156	0.7772	0.3259	0.385	0.3150	0.6586	0.7550
Football	0.440	0.6674	0.6962	0.7052	0.0720	0.353	0.4332	0.4955	0.7700
Polbooks	0.786	0.8263	0.8226	0.8286	0.1420	0.279	0.3468	0.4945	0.8310
Jazz	0.096	0.5142	0.6626	0.7401	0.0438	0.382	0.2400	0.2200	0.7303
Power	0.150	0.3887	0.4842	0.6363	0.0970	0.077	0.8312	0.7878	0.9513
Durgnet	0.207	0.1697	0.7664	0.6255	0.1355	0.155	0.2350	0.2350	0.7907
Highschool	0.056	0.6762	0.7064	0.6581	0.1440	0.056	0.4612	0.7015	0.7860
Netscience	0.000	0.7862	0.8444	0.8353	0.5120	0.436	0.7547	0.7314	0.9256
C.elegans	0.217	0.4551	0.2120	0.4346	0.0800	0.028	0.0743	0.1036	0.6660
Bible names	0.425	0.2965	0.4025	0.3657	0.0938	0.013	0.1900	0.1600	0.5815
Protein	0.160	0.1784	0.3630	0.7402	0.1015	0.140	0.5722	0.5858	0.8172
Internet Route	0.245	0.3475	0.1020	0.6300	0.0213	0.0045	0.1467	0.2548	0.4348
PGP	0.568	0.5364	0.7750	0.7370	0.2523	0.2024	0.5607	0.5563	0.8986

Figure 11.

Comparison of EnDNTM using $Q_{ov}$ -score on real-world networks.

Figure 12.

Comparison of EnDNTM using $Q_{ov}$ -score on Real-World Networks

Table 13 gives the results of the performance of EnDNTM for real world networks using the $Q_{ov}$ measure. Figures 11 and 12 represent the results visually. It can be observed that EnDNTM outperforms in 11 out 15 datasets and gives the second or third best result for the remaining datasets

Since most of the referenced algorithms have a non-unique output for the different runs, for all such algorithms, $Q_{ov}$ score is computed by executing the algorithms 10 times. Then, the average of best 5 scores is considered for comparison. Similarly for some algorithms, number of clusters parameter is needed. For such algorithms, we have analyzed the number of clusters generated by other algorithms and we have used the number given by the majority of the algorithms.

The quality of generated overlapping clusters from EnDNTM is greatly affected by the number of disjoint clusters generated by the initial ensemble method. From Eq. (4), it can be observed that $D_{t}$ has an inverse relation with the number of communities. $D_{t}$ is highly sensitive and dependent on the number of communities. As a result, increasing the number of communities, will decrease the value of $D_{t}$ , which will in turn affect the overlap between the communities. In our experiments, the number of communities range from 2 to 109. We also observed that in general, for the datasets, where the number of communities is greater than 4, EnDNTM achieves the best result. Also, EnDNTM depends on the boundary nodes in the disjoint clusters as well as their internal and external links (edges). If the number of external links of a node is extremely less as compared to its internal links, this node is less likely to qualify the condition outlined in Eq. (6) to be classified as an overlapping node.

7. Conclusion

In this work, we have proposed a new overlapping community detection algorithm (EnDNTM) based on utilizing disjoint communities produced by an ensemble method and analyzing the neighbourhood distribution of boundary nodes of discovered disjoint communities to detect overlapping clusters. We have developed an ensemble model consisting various community detection algorithms and utilized an evaluator function for generating the best disjoint communities. The effectiveness of the EnDNTM algorithm has been demonstrated by testing on five benchmarks synthetic networks with ground-truth communities and fifteen real-world datasets and compared with seven overlapping community detection algorithms in terms of an extended modularity $Q_{ov}$ , F1-score and ONMI measures. Five disjoint methods have been considered including a recently proposed tolerance based community detection (TCD) method. EnDNTM outperforms comparable algorithms with 4 out of 5 synthetic benchmark datasets and 11 out of 15 real-world datasets and gives comparable results for the remaining datasets. Experiments with various disjoint algorithms on 5 synthetic benchmark datasets and 15 real world datasets reveal that the ensemble model selects the disjoint method that generates the best overlapping clusters on a majority of the datasets. Another noteworthy feature of EnDNTM is that it performs comparatively well not only on social networks but also on biological, collaboration networks, word-association networks and traffic (internet routes) networks. Since different disjoint methods perform well for different networks, this challenge is addressed by ensemble model. However, for some datasets EnDNTM is limited in the selection of the best disjoint method. Future works will include: i) extending EnDNTM to handle larger Networks like DBLP [39] with nodes 317080 and edges 1049866 and bigger, ii) Parallel version of EnDNTM, iii) Enhancing EnDNTM with more disjoint methods iv) improving EnDNTM by considering other objective function.

Footnotes

Acknowledgments

Sheela Ramanna’s research has been supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) discovery grant 194376. Rajesh Jaiswal’s research is supported by the UW Graduate Studies Scholarship and Linda and Vana Kirby Scholarship.

References

Girvan

Newman

. Community structure in social and biological networks. Proceedings of the National Academy of Sciences. 2002; 99(12): 7821-7826.

Xie

Kelley

Szymanski

. Overlapping community detection in networks: The state-of-the-art and comparative study. Acm Computing Surveys (CSUR). 2013; 45(4): 1-35.

Fortunato

. Community detection in graphs. Physics Reports. 2010; 486(3-5): 75-174.

Rosvall

Bergstrom

. Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences. 2008; 105(4): 1118-1123.

Blondel

Guillaume

Lambiotte

Lefebvre

. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment. 2008; 2008(10): P10008.

Clauset

Newman

Moore

. Finding community structure in very large networks. Physical Review E. 2004; 70(6): 066111.

Kardan

Ramanna

. Tolerance methods in graph clustering: Application to community detection in social networks. in: International Joint Conference on Rough Sets. Springer; 2018. p. 73-87.

Lancichinetti

Fortunato

. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Physical Review E. 2009; 80(1): 016118.

Lancichinetti

Radicchi

Ramasco

Fortunato

. Finding statistically significant communities in networks. PloS ONE. 2011; 6(4): E18961.

10.

Kloster

Bindel

Hopcroft

. Local spectral clustering for overlapping community detection. ACM Transactions on Knowledge Discovery from Data (TKDD). 2018; 12(2): 17.

11.

Coscia

Rossetti

Giannotti

Pedreschi

. Demon: A local-first discovery method for overlapping communities. in: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM; 2012. 615-623.

12.

Gregory

. Finding overlapping communities in networks by label propagation. New Journal of Physics. 2010; 12(10): 103018.

13.

Xie

Szymanski

Liu

. Slpa: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. in: 2011 IEEE 11th International Conference on Data Mining Workshops. IEEE; 2011. 344-349.

14.

Palla

Derényi

Farkas

Vicsek

. Uncovering the overlapping community structure of complex networks in nature and society. Nature. 2005; 435(7043): 814.

15.

Chakraborty

Ghosh

Park

. Ensemble-based overlapping community detection using disjoint community structures. Knowledge-Based Systems. 2019; 163: 241-251.

16.

Chakraborty

Park

Subrahmanian

. Ensemble-based algorithms to detect disjoint and overlapping communities in networks. in: 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM). IEEE; 2016. 73-80.

17.

Jaiswal

Ramanna

. Detecting overlapping communities using distributed neighbourhood threshold in social networks. in: International Joint Conference on Rough Sets. Springer; 2020. Accepted.

18.

Coscia

Rossetti

Giannotti

Pedreschi

. Uncovering hierarchical and overlapping communities with a local-first approach. ACM Transactions on Knowledge Discovery from Data (TKDD). 2014; 9(1): 6.

19.

Cohen

Hendler

Rubin

. Node-centric detection of overlapping communities in social networks. in: International Conference and School on Network Science. Springer; 2017. 1-10.

20.

Hajiabadi

Zare

Bobarshad

. IEDC: An integrated approach for overlapping and non-overlapping community detection. Knowledge-Based Systems. 2017; 123: 188-199.

21.

Newman

Girvan

. Finding and evaluating community structure in networks. Physical Review E. 2004; 69(2): 026113.

22.

Mc Daid

Greene

Hurley

. Normalized mutual information to evaluate overlapping community finding algorithms. arXiv preprint arXiv: 11102515. 2011.

23.

Rossetti

Pappalardo

Rinzivillo

. A novel approach to evaluate community detection algorithms on ground truth. in: Complex Networks VII. Springer. 2016; 133-144.

24.

Nicosia

Mangioni

Carchiolo

Malgeri

. Extending the definition of modularity to directed graphs with overlapping communities. Journal of Statistical Mechanics: Theory and Experiment. 2009; 2009(3): P03024.

25.

Nicosia

Mangioni

Malgeri

Carchiolo

. Extending modularity definition for directed graphs with overlapping communities; 2008.

26.

Krebs

. Books about US Politics. Available from: http://networkdata.ics.uci.edu/data.php?d=polbooks.

27.

Kunegis

. KONECT – The Koblenz Network Collection. in: Proc Int Conf on World Wide Web Companion; 2013. 1343-1350. Available from: http://userpages.uni-koblenz.de/kunegis/paper/kunegis-koblenz-network-collection.pdf.

28.

Ponomarenko

Pitsoulis

Shamshetdinov

. Overlapping community detection in networks based on link partitioning and partitioning around medoids. arXiv preprint arXiv: 190708731. 2019.

29.

Zachary

. An information flow model for conflict and fission in small groups. Journal of Anthropological Research. 1977; 33(4): 452-473.

30.

Lusseau

Newman

. Identifying the role that animals play in their social networks. Proceedings of the Royal Society of London Series B: Biological Sciences. 2004; 271(suppl_6): S477–S481.

31.

Knuth

. The Stanford GraphBase: A platform for combinatorial computing. AcM Press New York; 1993.

32.

Gleiser

Danon

. Community structure in jazz. Advances in Complex Systems. 2003; 6(04): 565-573.

33.

Watts

Strogatz

. Collective dynamics of ‘small-world’ networks. Nature. 1998; 393(6684): 440.

34.

Weeks

Clair

Borgatti

Radda

Schensul

. Social networks of drug users in high-risk sites: Finding the connections. AIDS and Behavior. 2002; 6(2): 193-206.

35.

Rossi

Ahmed

. The network data repository with interactive graph analytics and visualization. in: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence; 2015. Available from: http://networkrepository.com.

36.

Duch

Arenas

. Community detection in complex networks using extremal optimization. Physical Review E. 2005; 72(2): 027104.

37.

Leskovec

Kleinberg

Faloutsos

. Graph evolution: Densification and shrinking diameters. ACM Trans Knowledge Discovery from Data. 2007; 1(1): 1-40.

38.

Boguná

Pastor-Satorras

Díaz-Guilera

Arenas

. Models of social networks based on social distance attachment. Physical Review E. 2004; 70(5): 056122.

39.

Yang

Leskovec

. Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems. 2015; 42(1): 181-213.

40.

Soundarajan

Hopcroft

. Use of local group information to identify communities in networks. ACM Transactions on Knowledge Discovery from Data (TKDD). 2015; 9(3): 21.

41.

Gregory

. A fast algorithm to find overlapping communities in networks. in: Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 2008; 408-423.

42.

Rossetti

Milli

Cazabet

. CDLIB: A python library to extract, compare and evaluate communities from complex networks. Applied Network Science. 2019; 4(1): 52.

Detecting overlapping communities using ensemble-based distributed neighbourhood threshold method in social networks

Abstract

Keywords

1. Introduction

3. Theoretical framework

3.1 Principles of graph theory

3.1.1 Undirected graph

3.1.2 Path

3.1.3 Neighbourhood node

3.2.1 Neighbourhood cluster

3.2.2 Distributed neighbourhood threshold ( D t )

3.4.1 Overlapping normalized mutual information (ONMI)

4.1 Generate non-overlapping clusters

4.1.2 Generate disjoint clusters

4.1.3 Ensemble method

4.2 Find overlapping clusters

4.2.1 Preprocessing disjoint clusters

4.2.2 Find overlapping candidate node

4.2.3 Calculate distributed neighbourhood threshold

4.2.4 Filter overlapping node

4.2.5 Generate overlapping clusters

4.3.1 Time complexity for disjoint cluster detection

Table 1 Running time of disjoint methods

5. Implementation and data sets

5.1 Data structures used in EnDNTM

Table 2 Data structure used in EnDNTM

5.3 Datasets used for experiment

5.3.1 Real-world networks

Table 3 Summary of real-world networks

Table 4 Summary of synthetic networks, where N o ⁢ v ⁢ r is the number of overlapping nodes and A ⁢ v ⁢ g c ⁢ c is the average clustering co-efficient

6.1 Experiment with various disjoint methods

6.1.1 Synthetic networks

Table 7 Q o ⁢ v -score for synthetic networks with all disjoint methods

6.2 Cluster analysis

Table 13 Q o ⁢ v -score for real-world networks with different algorithms

Footnotes

Acknowledgments

References

3.2.2 Distributed neighbourhood threshold $(D_{t})$

Table 1
Running time of disjoint methods

Table 2
Data structure used in EnDNTM

Table 3
Summary of real-world networks

Table 4
Summary of synthetic networks, where $N_{ovr}$ is the number of overlapping nodes and $Avg_{cc}$ is the average clustering co-efficient

Table 7
$Q_{ov}$ -score for synthetic networks with all disjoint methods

Table 13
$Q_{ov}$ -score for real-world networks with different algorithms