Detecting Overlapping Communities in Modularity Optimization by Reweighting Vertices

Abstract

On the purpose of detecting communities, many algorithms have been proposed for the disjointed community sets. The major challenge of detecting communities from the real-world problems is to determine the overlapped communities. The overlapped vertices belong to some communities, so it is difficult to be detected using the modularity maximization approach. The major problem is that the overlapping structure barely be found by maximizing the fuzzy modularity function. In this paper, we firstly introduce a node weight allocation problem to formulate the overlapping property in the community detection. We propose an extension of modularity, which is a better measure for overlapping communities based on reweighting nodes, to design the proposed algorithm. We use the genetic algorithm for solving the node weight allocation problem and detecting the overlapping communities. To fit the properties of various instances, we introduce three refinement strategies to increase the solution quality. In the experiments, the proposed method is applied on both synthetic and real networks, and the results show that the proposed solution can detect the nontrivial valuable overlapping nodes which might be ignored by other algorithms.

1. Introduction

Determining the group with some particular properties helps the analysts to capture the common properties from the members in the community. Many applications could be considered based on the community detection. For example, the precise information delivery, e.g., Google AdWords [1] increases the transaction amounts for sending the advertisement information to the right person. Therefore, detecting communities is a popular research topic [2,3,4,5,6,7,8].

Many results focus on the disjoin community sets that each node belongs to exactly one community [2,3]. However, in the real-world networks, many people may belong to multiple communities, so the communities may overlap with each other. For example, an engineer may belong to many projects in a company. Thus, instead of strict partitions, fuzzy partitions are more appropriate for understanding the network structures [9,10]. Fuzzy partitions allow a node belongs to multiple communities simultaneously. Considering a real-world situation, some staff work together in a building, and the manager would like to track the movement history for each staff [11]. Each one may move to various rooms, and the move purpose comes from the role of each staff. When we treat the purpose of all staff to be the communities, the staff may belong to different communities.

The modularity function proposed by Newman and Girvan [12] is the famous measurement of network partitions to measure the structure of a given network. The modularity function calculates the difference between the number of real intra-community edges and the expected number of edges to identify the qualities of the communities. The partition with larger modularity value has better community structure than those with lower modularity values. Finding the partitions with maximum modularity is a straightforward solution to the community detection. However, the modularity maximization has been proved as an NP-hard problem [13], and finding the partition with maximum modularity is difficult. Therefore, many results are proposed to calculate the near optimal solutions, such as the random walk processes [14], the structural clustering [15], and the polynomial-time approximation algorithms [16].

On the other hand, besides the computation complexity, the modularity maximization has two problems in detecting communities:

• Resolution limits Fortunato et al. introduced that small communities cannot be detected in large networks [17,18]. Since the null model of modularity provides the global connectivity, the expected number of edges between two small groups in a large network might be very small. Eventually, the two small groups will be treated as one community. Many approaches are proposed for solving resolution limits to provide high solution qualities, such as greedy algorithms [19,20], spectral algorithms [21,22,23], simulating annealing algorithms [24] and mathematical programing [25].
• Overlapping community Some nodes may belong to several communities, so simply assigning the nodes to one community is difficult. Thus, the straightforward solution is to modify the modularity for allowing the nodes belonging to multiple communities at the same time [26,27,28,29,30]. Figure 1 shows two benchmarks about overlapping communities. In Figure 1a, the node $v_9$ is the overlapping node, and we assign $v_9$ to community B and C. Thus, we get three communities, and they are {{$v_1$, $v_2$, $v_3$, $v_4$}, {$v_5$, $v_6$, $v_7$, $v_8$, $v_9$}, {$v_9$, $v_{10}$, $v_{11}$, $v_{12}$, $v_{13}$, $v_{14}$}}. Moreover, $v_5$ is assigned to A and B in Figure 1b.

In this paper, we focus on the overlapping community detection, and propose the node weight allocation problem denoted by $NW{A}_{OCD}$ to formulate the community overlap. Since computing the partition with maximum modularity is NP-complete, decreasing the computation cost to seek the near optimal partitions is the popular approach in solving the overlapping community detection. The heuristic algorithms are outstanding in seeking better solutions in large search space, especially for the genetic algorithms (GAs) [2,3,8]. Therefore, some works consider GA as the core approach in their solutions. Mu et al. use a hybrid heuristic approach including GA and the simulated annealing to find out the communities [2]. Shang et al. use GA with an extra local search [3]. The heuristic algorithms perform well in seeking the solution with high quality in a large search space. However, the above results do not deal with the overlapping properties. The overlapping networks have various properties, so some approaches consider the multi-objective approach to find the balanced results [4,5,6,31]. The balanced results mean that most properties are considered, but the derived results may not be closed to the real-world properties. Therefore, Behera et al. check the similarity between each pair of nodes [8]. The node similarity is also considered by Ezeh et al. to the overlapping nodes and their neighbors [32]. To emphasize the community attribution of each node, Shakya et al. combine fuzzy with the GA to calculate the detail properties of the nodes [7]. Shakya et al. consider the GA to reduce the computation time without decreasing the solution quality too much and adopt the fuzzy communities to identify the overlapping nodes.

Even if some approaches provide the solutions with high modularity, the partitions may not reflect the properties of the real-world networks in some situations. We found that the solution quality could be refined by considering following issues: ignoring overlapping nodes, merging clusters, and reweighting nodes. Therefore, we consider the modularity to design the solution searcher of the approach $G{A}_{IMR}^{NWA}$. We firstly modify the fitness function in $G{A}_{IMR}^{NWA}$ to show the network properties by considering the null model, so the revised fitness function could output the partitions that are closer to the real-world behavior. Moreover, we design three refinement strategies to make the solutions to reflect the real-world properties.

In the simulation, we consider the synthetic network and popular networks that include Zachary Karate Club Network, Books about American Politics, and American College Football to evaluate the solution quality calculated by $G{A}_{IMR}^{NWA}$ and other approaches. The derived networks correctly reflect the real-world properties in the synthetic networks and the real-world networks. Moreover, the proposed refinement strategies are also evaluated, and the refinement strategies provide higher quality of the derived partitions in the perspective of the real-world behavior. Therefore, the simulation results show that $G{A}_{IMR}^{NWA}$ outputs the partitions, and the results are closed to the real-world properties.

This paper is organized as follows. The overlapping communities and the problem definition are introduced and formulated in Section 2. The proposed approach $G{A}_{IMR}^{NWA}$ is shown in Section 3, and the refinement strategies are also listed in this section. The simulation and comparisons are arranged in Section 4, and we show the network partitions in this section. Eventually, the conclusion and future works are stated in Section 5.

2. Preliminary

2.1. Modularity in Overlapping Communities

The community detection of a given network involves two processes. The first one is to find out the network structure and the other one is to determine the numbers of communities. Here we introduce the works proposed by Nepusz et al. [33] to explain the modularity in overlapping communities. Nepusz et al. consider a belonging coefficient matrix $U={\left[{\alpha }_{ic}\right]}_{n\times k}$, where n is the number of nodes, and k is a given number of communities. Each entry ${\alpha }_{ic}$ shows how strongly the node $v_i$ belongs to the community c. The constraint of the relationship between $v_i$ and all communities is:

$$\sum _{c=1}^k{\alpha }_{ic}=1,\forall {\alpha }_{ic}\in [0,1],0<\sum _i^n{\alpha }_{ic}<n.$$

(1)

So, the objective function is:

$$\begin{array}{c}\hfill D_G\left(U\right)=\sum _{i,j=1}^n{w}_{ij}{(\widetilde{s_{ij}}-s_{ij})}^2,\end{array}$$

(2)

where $w_{ij}$ is the predefined weight, $s_{ij}={\sum }_{c=1}^k{\alpha }_{ic}{\alpha }_{jc}$, and $\widetilde{s_{ij}}$ is the prior similarity of $v_i$ and $v_j$. By minimizing Equation (2), the nodes with high similarity will be grouped together. So, U with optimal result $D_G\left(U\right)$ is the overlapping community structure.

To determine an appropriate number of communities k, Nepusz et al. iteratively increase the value of k from 2, and then choose the value of k with the highest fuzzy modularity value calculated by Equation (3).

$$\begin{array}{c}\hfill Q_{ov}^{Ne}=\frac{1}{2m}\sum _{c=1}^k\sum _{i,j=1}^n(A_{ij}-\frac{k_i{k}_j}{2m}){\alpha }_{ic}{\alpha }_{jc}\end{array}$$

(3)

2.2. Problem Definition

The overlapping community detection problem is considered as a node weight allocation problem, denoted by $NW{A}_{OCD}$ for short. Given a network $G(V,E)$, a maximum number of communities k, and a null model weight $\gamma$. Find a modified belonging coefficient matrix $M={\left[{\lambda }_{ic}\right]}_{n\times k}$, such that the $Q_{ov}^{{}^{\prime }}$ value is maximized. The objective function and constraints are:

$$\begin{array}{cccc}\hfill & \max \hfill & \hfill & Q_{ov}^{{}^{\prime }}=\frac{1}{2m}\sum _{c=1}^k\sum _{i,j=1}^n(A_{ij}-\gamma \frac{k_i{k}_j}{2m}){\lambda }_{ic}{\lambda }_{jc}\hfill \\ \hfill & \mathrm{s}.\mathrm{t}.\hfill & \hfill & {\lambda }_{ic}\in [0,1]\hfill \\ \hfill & \hfill & \hfill & \sum _{c=1}^{\left|C\right|}{\lambda }_{ic}^{in{c}_f}=1.\hfill \end{array}$$

(4)

We consider $in{c}_f$ as the increasing factor. Given $in{c}_f>1$, the total weight of an overlapping node over all communities is larger than one, i.e., ${\sum }_{c=1}^k{\lambda }_{ic}>1$. The total weight of a non-overlapping node is still equal to one exactly, i.e., ${\sum }_{c=1}^k{\lambda }_{ic}=1$.

By solving the $NW{A}_{OCD}$ problem, the overlapping community structure will be obtained by modifying the optimal solution. Note that if $in{c}_f=1$ and $\gamma =1$, Equation (4) is the same with Equation (5), which means the fuzzy modularity is a special case of the $NW{A}_{OCD}$ problem.

$$\begin{array}{cccc}\hfill & \max \hfill & \hfill & Q_{ov}=\frac{1}{2m}\sum _{c=1}^k\sum _{i,j=1}^n(A_{ij}-\frac{k_i{k}_j}{2m}){\alpha }_{ic}{\alpha }_{jc}\hfill \\ \hfill & \mathrm{s}.\mathrm{t}.\hfill & \hfill & {\alpha }_{ic}\in [0,1]\hfill \\ \hfill & \hfill & \hfill & \sum _c^k{\alpha }_{ic}=1.\hfill \end{array}$$

(5)

Although Griechisch et al. [34] apply the fuzzy modularity to find overlapping communities, there are still some networks are unresolved. We introduce the networks with more than two communities and two communities to show this issue. The benchmark is shown in Figure 1. The values of $Q_{ov}$ for G4415 and G415 are shown in

Table 1. The values of $Q_{ov}$ in G4415 and G415.

(a) The $Q_{ov}$ values with different assignments of $v_9$ in G4415.
${\alpha }_{9,B}$	${\alpha }_{9,C}$	${\alpha }_{9,D}$	$Q_{ov}$
1	0	0	0.5736
0.7	0.3	0	0.5709
0.3	0.7	0	0.5664
0	1	0	0.5624
0	0	1	0.5560
(b) The $Q_{ov}$ values with different assignments of $v_5$ in G415.
${\alpha }_{5,A}$	${\alpha }_{5,B}$	${\alpha }_{5,C}$	$Q_{ov}$
1	0	0	0.4305
0	0	1	0.4151
0	1	0	0.4058

. We can see that $v_9$ belongs to B in G4415 while $v_5$ belongs A in G415, and they are not overlapping nodes.

The major difference between Equations (4) and (5) is the coefficient matrix. Each entry in Equation (5) is unweighted while that is weighted in Equation (4). Therefore, we need a mapping as shown in the following equations.

$$\begin{array}{cc}\hfill & {\lambda }_{ic}=\sqrt[in{c}_f]{{\alpha }_{ic}}\hfill \\ \hfill & {\alpha }_{ic}={\lambda }_{ic}^{in{c}_f}\hfill \end{array}$$

(6)

3. Allocate Node Weight by Genetic Algorithms

Computing the partition with maximum modularity has been proved as the NP-complete problem [13]. Even if we consider the solution with high computation performance, e.g., the cloud computing [35,36] and the parallel computing [37], to compute the partitions for maximizing the modularity, it still requires huge computation resource. Therefore, we propose a GA-based approach to get the near-optimal solution with minimum computation. The proposed algorithm $G{A}_{IMR}^{NWA}$ includes two steps. We first apply GA to obtain a high-quality feasible solution, and then design three refinement strategies to improve the derived solution to modify the derived partition to be closer to the real-world behavior. In the following context, we will introduce the revised GA algorithm and the refinement strategies.

3.1. Genetic Algorithm

The iterative process of GA as shown in Algorithm 1 includes three major processes: crossover, mutation, and selection. Before invoking the iterative process, the initial population P with $ind{i}_n$ chromosomes will be determined firstly. Each chromosome is represented by $M={\left[{\lambda }_{ic}\right]}_{n\times k}$, as shown in Figure 2. Each entry ${\lambda }_{ic}$ is a weight to indicate the assignment from $v_i$ to c. The initial population is generated randomly, and each row of M must satisfy the problem constraints. Given a maximum number of iterations $ma{x}_t$, the GA then invokes following processes.

• Crossover: we randomly select two chromosomes $C_A$ and $C_B$ form P, and a random column. The offspring is generated by the selected column of $C_B$ and the remaining part of $C_A$ as shown in Figure 3. The number of offsprings is determined by $ind{i}_n$, and in other words, we will obtain $2\times ind{i}_n$ chromosomes after the crossover.
• Mutation: the mutation process is launched in 80% probability after finishing the crossover. Once the mutation is invoked, one ${\lambda }_{ic}$ of a randomly selected chromosome will be picked up within $[-0.1,0.1]$. Eventually, the offspring will be normalized to be a feasible solution to fit the requirements in $NW{A}_{OCD}$.
• Selection: we consider the modularity to be the objective function, and finding the partition with maximum modularity is the purpose of GA. We use $Q_{ov}^{{}^{\prime }}$ to be the fitness function and calculate $Q_{ov}^{{}^{\prime }}$ of each solution. Moreover, all chromosomes are sorted in the descending order of $Q_{ov}^{{}^{\prime }}$. Computing the chromosomes with maximum $Q_{ov}^{{}^{\prime }}$ is the major goal of the GA, so we select top $ind{i}_n$ individuals, and they will survive to the next generation.

Algorithm 1: Genetic algorithm for allocating node weight

To keep the heavily overlapping nodes, a threshold ${\alpha }_T$ in terms of $\alpha$ is given. We transform ${\alpha }_T$ to the corresponding $\lambda$ with the threshold ${\lambda }_T$ by Equation (6).

3.2. Refinement Strategies

GA provides an elite solution from the population, but this solution may not be suitable for all instances. In the pre-analysis phase, we observed three situations derived by $G{A}_{IMR}^{NWA}$, and we could receive better solutions by some extra processes. The situations are (1) lightly overlapping nodes, (2) mergeable clusters, and (3) reweight nodes. We call the processes that are used to get better solutions the “refinement strategies”. Therefore, we provide three refinement strategies to refine the solutions for the above situations, respectively.

• Ignore slight overlapping nodes The overlapping degree of each $\lambda$ is important for splitting the communities. Determining the community with low value of $\lambda$ is easier than that with a higher value. We use a threshold ${\lambda }_T$ corresponding to Equation (6) to determine that the entry should be treated as an entry without overlaps. In addition, we also can derive ${\lambda }_T$ by Equation (6). When $\lambda <{\lambda }_T$, we set $\lambda$ as zero. When ${\lambda }_T$ is set as a higher value, more entries will be assigned to single community.
• Merge clusters Some small communities should be merged by other large community. If the overlapping ratio of any two communities is larger than a given merge threshold $m_T$, they should be simply merged to a single community. Given two non-empty communities, we define $o{v}_{ratio}=|C_1\cap C_2|/\min (|C_1|,|C_2\left|\right)$ to be the overlapping ratio. When $o{v}_{ratio}$ is larger than a given threshold, $C_1$ and $C_2$ will be merged.
• Reweight node values To calculate the weight distribution of each overlapping node, directly converting $\lambda$ to $\alpha$ via Equation (6) results in a situation that a node belongs to multiple communities but the majority of its weight is allocated to one community. To avoid this problem, we propose the reweight strategy. The weight should be proportional to the number of edges that $v_i$ linked in c. Moreover, if the neighbors of $v_i$ in c are more than the average number of nodes in c, c is more important than others for $v_i$. Given a community c, $avgNighbo{r}_c={\sum }_{i,j\in V\left(c\right)}{A}_{ij}/\left|V\left(c\right)\right|$ represents the average number of neighbors and ${\alpha }_i={\sum }_{c\in C\left(i\right)}{\sum }_{j\in V\left(c\right)}{A}_{ij}/avgNighbo{r}_c$ be the normalized term. Therefore, we have the new weight is:

  $${\alpha }_{ic}=\frac{1}{{\alpha }_i}\sum _{j\in V\left(c\right)}\frac{A_{ij}}{avgNighbo{r}_c},$$

  (7)

  where $V\left(c\right)$ is the set of nodes belong to c and $C\left(i\right)$ is the set of communities that $v_i$ belongs to. We use ${\alpha }_i$ for normalization, so we have ${\sum }_{c=1}^k{\alpha }_{ic}=1$.

4. Simulations

We consider a synthetic network and three real networks including Zachary Karate Club network, Books about American Politics, and American College Football to evaluate the performance of $G{A}_{IMR}^{NWA}$. The evaluation criteria involve detecting overlapping community structure, detecting meaningful communities, detecting dense overlaps, and detecting heavily overlapping nodes.

4.1. Synthetic Network

We consider G210 as our synthetic network which has 210 nodes and four pre-defined communities A, B, C and D. Each of them has 60 nodes and 10 shared by any two continuous communities, i.e., $A=\{v_1:v_{60}\}$, $B=\{v_{51}:v_{110}\}$, $C=\{v_{101}:v_{160}\}$, and $D=\{v_{151}:v_{210}\}$. Note that A and B share nodes $\{v_{51},\dots ,v_{60}\}$, B and C share nodes $\{v_{101},\dots ,v_{110}\}$ and so on. Each pair of nodes has 3% chances to be linked to each other, and for each community they shared, an extra 55% chances for them to be linked. Thus, overlapping parts will be denser than non-overlapping parts [38].

Since the fuzzy modularity is a special case of the $NW{A}_{OCD}$ problem, we could use the same optimization strategy to solve the problem. The parameter settings are $in{c}_f=1.5$ and 1, ${\alpha }_T=0$, $m_T=-1$, $k=6$, and $\gamma =1$. Figure 4 shows the bitmaps of sorted adjacency matrices. The black and white points represent the entries of 1s and 0s respectively. The adjacency matrices are sorted by the following strategy:

• Nodes are grouped by the detected community id. For the overlapping nodes, only the smallest id is counted.
• For each c, all nodes are sorted in descending order of ${\lambda }_{ic}$. Therefore, the overlapping nodes will be in the bottom area of each community.

Figure 4a is the result obtained by $G{A}_{IMR}^{NWA}$. The dense blocks indicate four communities, and two continuous blocks have an overlapping part which is composed of overlapping nodes. In this result, all the overlapping and non-overlapping nodes are correctly identified. Figure 4b is the result of fuzzy modularity. Four communities are detected too, but no overlapping nodes are identified.

Although the maximum number of communities is six, only four communities were detected while the other two were empty communities. Since the number of communities could be captured by modularity [39], it is unnecessary to know the exactly value of number of communities in our method.

4.2. Zachary Karate Club Network

Zachary karate club network [40] is a popular benchmark for community detection algorithms. It has 34 nodes and 78 edges while nodes are members and edges are friendships between them. This network includes two groups due to a disagreement between the administrator and the instructor. Figure 5 is the result captured by the fuzzy modularity. In this experiment, we evaluate the results with different $in{c}_f$ settings, and show the importance of “ignore slight overlapping nodes” and “reweight node values”. Finally, we apply our method on the case with the value $k=2$, and halved the null model.

4.2.1. Effects of Weight Increasing Factor

We first evaluate the communities captured by $G{A}_{IMR}^{NWA}$ in the networks with $in{c}_f=\{1,1.2,1.5,1.7\}$ while ${\alpha }_T=0.01$, $m_T=-1$, $k=8$, and $\gamma =1$. The corresponding $Q_{ov}^{{}^{\prime }}=\{0.419,0.422,0.427,0.430\}$. We consider the fuzzy modularity with $in{c}_f=1$ as our baseline since it outputs the correct solution.

Figure 6a is the result with $in{c}_f=1.2$, and we get four communities and three overlapping nodes while $\lambda$ is shown in

Table 2. The comparison with various $in{c}_f$ settings.

(a) $\lambda$ values of overlapping nodes in Figure 6a with $in{c}_f=1.2$
Node	${\lambda }_{iA}$	${\lambda }_{iB}$	${\lambda }_{iC}$	${\lambda }_{iD}$
$v_1$		0.967		0.068
$v_{10}$	0.747	0.362
$v_{24}$	0.419		0.696
(b) $\lambda$ values of overlapping nodes in Figure 6b with $in{c}_f=1.5$
Node	${\lambda }_{iA}$	${\lambda }_{iB}$	${\lambda }_{iC}$	${\lambda }_{iD}$
$v_1$		0.917		0.246
$v_3$		0.986	0.075
$v_{10}$	0.700	0.556
$v_{12}$		0.993		0.048
$v_{24}$	0.553		0.703
$v_{34}$	0.993		0.048
(c) $\lambda$ values of overlapping nodes in Figure 6b with $in{c}_f=1.7$
Node	${\lambda }_{iA}$	${\lambda }_{iB}$	${\lambda }_{iC}$	${\lambda }_{iD}$
$v_1$		0.888		0.369
$v_3$		0.987	0.108
$v_{10}$	0.694	0.636
$v_{12}$		0.926		0.290
$v_{24}$	0.600		0.726
$v_{34}$	0.989		0.097

a. The network separation in Figure 6a is identical to that in Figure 5, but maximizing the modularity outputs a larger one than that we derived. When $in{c}_f$ is increased from 1.2 to 1.5, we get two extra overlapping nodes, and they are $v_{12}$ and $v_{34}$. When $in{c}_f$ is set as $1.7$, the values of $\lambda$ are changes as shown in Table 2c, and others are identical to that derived by $in{c}_f=1.5$. Therefore, larger settings of $in{c}_f$ results in more overlapping nodes.

Considering that a node has only one edge connecting to an overlapping node, e.g., $v_{12}$, the isolation has the same property with that held by the overlapping node. Moreover, we found that $Q_{ov}^{{}^{\prime }}$ derived by $G{A}_{IMR}^{NWA}$ is higher than the optimal Q. It implies that the overlapping structure is easier to be detected as assigning higher weight to the overlapping nodes.

Here we consider an extreme case that all nodes are overlapped, i.e., $in{c}_f=4$. We analyze the obtained result, and then find the “duplicate communities”. Two or more communities are extremely overlapped with each other, and even some of them are just the same community.

Figure 7 shows the fuzzy partition result. Four communities are detected, but two of them denoted by dotted lines are the subsets of the rest two communities denoted by solid lines. Therefore, two sets should be merged to a correct community. After merging the communities, we derive two communities, and there is only one overlapping node $v_{10}$. However, the value of $Q_{ov}^{{}^{\prime }}$ is decreased from 0.526 to 0.371 simultaneously.

Even if we derive the result with maximized value of $Q_{ov}^{{}^{\prime }}$, the solution does not show the correct properties of the communities. We use the refinement strategies to get the solution with lower quality but more closed to the real-world properties. Therefore, the refinement strategies are useful for improving the solution quality in terms of the real-world consideration.

4.2.2. Effects of Ignoring Slight Overlapping Nodes

We consider the network with $in{c}_f=1.5$ to evaluate the effects of the ignore step. The result with and without the ignore step are 0.427114 and 0.427117, respectively. Figure 8 and

Table 3. $\lambda$ values of overlapping nodes in Figure 8 with $in{c}_f=1.5$ (before ignoring).

Node	${\mathit{\lambda }}_{\mathbf{iA}}$	${\mathit{\lambda }}_{\mathbf{iB}}$	${\mathit{\lambda }}_{\mathbf{iC}}$	${\mathit{\lambda }}_{\mathbf{iD}}$
$v_1$		0.917		0.246
$v_3$		0.986	0.075
$v_{10}$	0.700	0.556
$v_{12}$		0.993		0.048
$v_{24}$	0.553		0.703
$v_{28}$	0.002		0.999
$v_{30}$	0.999		0.004
$v_{34}$	0.993		0.048

are the detected communities and values of $\lambda$. Two overlapping nodes $v_{28}$ and $v_{30}$ are ignored. Since most of their weights were kept in a specific community, reducing the weights will not decrease $Q_{ov}^{{}^{\prime }}$ dramatically. Therefore, the process of ignoring slight overlapping nodes helps to keep those heavily overlapping nodes.

4.2.3. Effects of Reweight Strategy

To emphasize the importance of the communities, we propose a reweight strategy to assign various weights. The result with reweight strategy is identical to that shown in Figure 6b.

Table 4. The comparison of $G{A}_{IMR}^{NWA}$ with reweighting and without reweighting.

(a) Before reweighting
Node	${\lambda }_{iA}$	${\lambda }_{iB}$	${\lambda }_{iC}$	${\lambda }_{iD}$
$v_1$		0.917		0.246
$v_3$		0.986	0.075
$v_{10}$	0.700	0.556
$v_{12}$		0.993		0.048
$v_{24}$	0.553		0.703
$v_{34}$	0.993		0.048
(b) After reweighting
Node	${\alpha }_{iA}$	${\alpha }_{iB}$	${\alpha }_{iC}$	${\alpha }_{iD}$
$v_1$		0.611		0.389
$v_3$		0.709	0.291
$v_{10}$	0.52	0.48
$v_{12}$		0.440		0.560
$v_{24}$	0.468		0.532
$v_{34}$	0.725		0.275

a,b show the value of $\lambda$ without and with considering the reweight strategy, respectively. The reweight strategy reduces the gap of the number of edges for connecting the inside-community nodes and outside-community nodes. However, the structure of the main community may be changed after reweighting, because the values are inversely proportional to the average number of neighbors in the communities to that out of communities. For example, $v_{12}$ is unbalanced before reweighting, but the value of $\lambda$ of $v_{12}$ reflect the real-world behavior.

4.2.4. The Network with Two-Communities

We examine the network with exactly two communities to verify the property illustrated in Figure 1b can be captured by $G{A}_{IMR}^{NWA}$. We consider $in{c}_f=1.5$, ${\alpha }_T=0.01$, $m_T=-1$, $k=2$, and $\gamma =0.5$. In this case, we easily find out the overlapping nodes. The results are shown in Figure 9 and

Table 5. $\lambda$ values of overlapping nodes in Figure 9.

Node	${\mathit{\lambda }}_{\mathbf{iA}}$	${\mathit{\lambda }}_{\mathbf{iB}}$
$v_3$	0.493	0.753
$v_9$	0.987	0.071
$v_{10}$	0.984	0.085

.

$G{A}_{IMR}^{NWA}$ derives three overlapping nodes as shown in Table 5. From Figure 9, we have $Q_{ov}^{{}^{\prime }}=0.628$, and the dotted curve is the real split of the club network. $v_3$ is the main overlapping node since it has a roughly balanced weight value. In summary, the two-community problem is solved by reducing the number of expected edges.

4.2.5. Compare with Different Algorithms

In the above simulations, $G{A}_{IMR}^{NWA}$ detects two communities, and we compare the result with previous algorithms in this dataset. Shen et al. captured three overlapping communities [30], and the overlapping nodes are $v_1$, $v_3$ and $v_9$. However, $v_{12}$ is missed in the method of Shen et al. The property of the overlapping communities in $v_{12}$ is not discovered. The node $v_{12}$ has exactly one neighbor that is node $v_1$, so $v_{12}$ should have the same overlapping properties as that of $v_1$.

Chen et al. captured two overlapping communities [29], and their results are similar to ours as shown in Figure 9. Chen et al. found one overlapping node $v_{10}$. Node $v_{10}$ has two edges that one connects to the left community while the other one comments to the right community. Therefore, considering $v_{10}$ as the overlapping node is reasonable. However, the node $v_3$ has five edges where three edges connect to the left community while two connect to the right community. $v_3$ is more appropriate than $v_{10}$ to be the overlapping node.

From the above observation, the communities are split more precisely by $G{A}_{IMR}^{NWA}$ than the previous works. For the considerations of the split appropriateness, e.g., the number of detected communities, and the split correctness, e.g., the overlapping nodes, $G{A}_{IMR}^{NWA}$ provides more precise results than other approaches.

4.3. Books about American Politics

This network is built from the transaction data from amazon.com [41]. The network has 105 nodes and 441 edges while nodes indicate books and edges are frequent co-purchase events. The nodes are labeled by three categories including liberal, neutral, or conservative. Each category has 43, 13, and 49 nodes respectively. In this simulation, we consider $in{c}_f=1.5$, ${\alpha }_T=0.01$, $m_T=0.5$, $k=8$, and $\gamma =1$. We evaluate the performance of the merge strategy. Figure 10a,b are the solutions with and without merge strategies respectively. The text on each node is the node id and the real label. The results of $Q_{ov}^{{}^{\prime }}$ are 0.528 and 0.533 for the results with and without merge strategy.

4.3.1. The Result with Merge Strategy

$G{A}_{IMR}^{NWA}$ with the merge strategy detects four communities denoted by W, X, Y, and Z. Most nodes belong to two large communities W and X, which are mainly consisted of conservative and liberal books respectively. Most neutral books belong to two small communities. This result is similar to that obtained by Newman [39].

Table 6. $\lambda$ values of overlapping nodes in Figure 10a.

Node	${\mathit{\lambda }}_{\mathbf{iW}}$	${\mathit{\lambda }}_{\mathbf{iX}}$	${\mathit{\lambda }}_{\mathbf{iY}}$	${\mathit{\lambda }}_{\mathbf{iZ}}$	Label
$v_3$	0.986			0.076	conservative
$v_7$			0.254	0.913	neutral
$v_9$	0.975		0.11		conservative
$v_{18}$	0.528			0.724	neutral
$v_{22}$	0.955			0.164	conservative
$v_{25}$	0.922			0.236	conservative
$v_{28}$		0.72		0.533	neutral
$v_{46}$	0.921	0.238			neutral
$v_{50}$	0.458		0.781		conservative
$v_{85}$			0.981	0.093	liberal

is the values of $\lambda$ for ten overlapping nodes. There are four neutral nodes, that is $40\%$ of all overlapping nodes and $30\%$ of all neutral nodes. The result implies that neutral books are often co-purchased with different books.

4.3.2. The Result without Merge Strategy

$G{A}_{IMR}^{NWA}$ without the merge strategy splits W and X into two parts respectively denoted by $W_1$, $W_2$, $X_1$ and $X_2$. A small community including $v_{48}$, $v_{49}$ and $v_{57}$ has been detected by the modularity maximization [25]. Therefore, we also found this community and labeled it by $W_2$.

Moreover, we also detect an extra community $X_2$. After analyzing the edge density of $X_1$ and $X_2$, they are both denser than the merged community X. Besides, the overlapped part is even denser as shown in

Table 7. Density value of each part of community X.

	X	${\mathit{X}}_1$	${\mathit{X}}_2$	${\mathit{X}}_1\cap {\mathit{X}}_2$
$D\left(c\right)$	0.20	0.27	0.34	0.63

. The density function definition is as follows:

$$\begin{array}{c}\hfill D\left(c\right)=\frac{1}{\left(\genfrac{}{}{0pt}{}{\left|V\right(c\left)\right|}{2}\right)}\sum _{i,j\in V\left(c\right)}\frac{A_{ij}}{2}.\end{array}$$

(8)

The overlapping ratios of ($W_1$, $W_2$) and ($X_1$, $X_2$) are 57% and 53%, respectively. High overlapping ratios indicate that we could merge each pair of them without decreasing $Q_{ov}^{{}^{\prime }}$ too much. Therefore, modularity can not detect $X_2$ because of high overlapping ratio and dense overlapped part. This result shows the dense overlaps can be discovered by $G{A}_{IMR}^{NWA}$ correctly.

4.4. American College Football

This is the network of American football games between Division IA colleges in 2000 [42]. It has 115 nodes, 613 edges and 12 conferences as shown in

Table 8. Labels of conferences.

Label	Conference	#Teams	Label	Conference	#Teams
0	Atlantic Coast	9	6	Mid-American	13
1	Big East	8	7	Mountain West	8
2	Big Ten	11	8	Pacific Ten	10
3	Big Twelve	12	9	Southeastern	12
4	Conference USA	10	10	Sun Belt	7
5	Independents	5	11	Western Athletic	10

. Nodes are teams and edges are games between the corresponding two teams while nodes are labeled by the conferences they belong to. We apply $in{c}_f=1.5$, ${\alpha }_T=0.01$, $m_T=-1$, $k=15$, and $\gamma =1$ in this simulation.

Figure 11 shows the result with $Q_{ov}^{{}^{\prime }}=0.607$, true labels are on the nodes. Ten communities and 17 overlapping nodes are detected. Most conferences are well matched to the detected communities except for the conferences Independents (Label 5) and Sun Belt (Label 10). There are total seven overlapping nodes in these two conferences. From

Table 9. $\lambda$ values of overlapping nodes in Figure 11.

Node	${\mathit{\lambda }}_{\mathbf{iA}}$	${\mathit{\lambda }}_{\mathbf{iB}}$	${\mathit{\lambda }}_{\mathbf{iC}}$	${\mathit{\lambda }}_{\mathbf{iD}}$	${\mathit{\lambda }}_{\mathbf{iE}}$	${\mathit{\lambda }}_{\mathbf{iF}}$	${\mathit{\lambda }}_{\mathbf{iG}}$	${\mathit{\lambda }}_{\mathbf{iH}}$	${\mathit{\lambda }}_{\mathbf{iI}}$	${\mathit{\lambda }}_{\mathbf{iJ}}$	Label
$v_2$				0.06	0.99						2
$v_8$			0.058			0.991					8
$v_9$			0.971			0.123					7
$v_{11}$			0.937	0.204							10
$v_{23}$			0.981			0.094					7
$v_{36}$	0.575	0.682									5
$v_{44}$							0.11	0.975			4
$v_{50}$			0.902			0.274					10
$v_{58}$	0.961								0.149		11
$v_{66}$	0.067							0.989			4
$v_{67}$			0.05						0.993		11
$v_{69}$			0.992						0.054		10
$v_{78}$			0.05			0.992					8
$v_{80}$							0.941	0.121		0.126	5
$v_{82}$				0.065	0.082	0.097	0.953				5
$v_{97}$	0.704			0.326				0.368			10
$v_{112}$	0.065							0.989			4

, 41% overlapping nodes and 58% nodes are in the two conferences.

The conference Independents has five teams, and only one game was held. This is the major reason that makes this conference undetectable. However, the teams often play with other teams in varied conferences, and this phenomenon results in the overlapping property. For example, $v_{82}$ is assigned to four communities, although it connected to community G with four edges. $v_{82}$ still connects to other three communities with a significant number of edges, so that is why it belongs to many communities simultaneously as shown in Figure 12. On the other hand, Sun Belt is in the similar situation. In this example, the heavily overlapping nodes could be detected by our method.

4.5. Dolphin Network

The Dolphin Network is a common benchmark for evaluating the overlapping communities. Some results consider the Dolphin Network to evaluate the community quality [26,43]. We compare the proposed $G{A}_{IMR}^{NWA}$ with related results in this simulation. The Dolphin Network includes 62 nodes and 159 edges, and two communities are detected eventually for a long-term observation.

The distribution of $\lambda$ for overlapping nodes is listed in

Table 10. $\lambda$ values of overlapping nodes in Figure 13.

Node	${\mathit{\lambda }}_{\mathbf{iA}}$	${\mathit{\lambda }}_{\mathbf{iB}}$	${\mathit{\lambda }}_{\mathbf{iC}}$	${\mathit{\lambda }}_{\mathbf{iD}}$	${\mathit{\lambda }}_{\mathbf{iE}}$
$v_0$		0.008		0.999
$v_1$	0.998				0.023
$v_2$		0.076		0.986
$v_7$	0.990			0.061
$v_8$				0.022	0.998
$v_{15}$			0.999	0.000	0.013
$v_{19}$	0.986			0.074
$v_{20}$		0.361		0.364	0.682
$v_{23}$			0.909		0.261
$v_{28}$				0.823	0.400
$v_{30}$	0.051			0.992
$v_{36}$		0.013			0.999
$v_{37}$		0.990			0.062
$v_{39}$	0.255				0.912
$v_{40}$		0.998			0.021
$v_{44}$		0.844		0.362	0.038
$v_{45}$			0.992		0.053
$v_{47}$				0.999	0.011
$v_{50}$		0.928	0.175	0.103
$v_{52}$		0.999	0.009
$v_{59}$			0.138		0.965
$v_{61}$		0.925		0.229

while the separation with $Q^{\prime }=0.535$ is illustrated in Figure 13. According to the refinement strategy Ignore slight overlapping nodes, we get three overlapping nodes $v_{20},v_{28}$, and $v_{44}$ after decreasing the setting of ${\lambda }_T$ from 1.0 to 0.9. The overlapping nodes are marked by the red circle with dot lines, and they are marked by the overlapping nodes based on the distribution of $\lambda$. On the other hand, we also consider $m_T=-1$ in Dolphin network as the same setting in the above simulations. The community B, C, D, and E are merged according to the refinement strategy Merge clusters. Eventually, we get two communities.

Nicosia et al. found four communities in Dolphin network [26]. The overlapping nodes are mentioned, but the authors did not list the overlapping nodes. Wang and Fleury provided detail analysis and found two communities from Dolphin network with $Q=0.385$[43]. The separation is acceptable, but the network structure is not so strong comparing to Figure 13. After considering the refinement strategies, the separation derived by the proposed $G{A}_{IMR}^{NWA}$ is similar to that provided by Wang and Fleury in [43], but the structure of our network is stronger than the network in [43]. In summary, the refinement strategies are useful in revising the network separation to be closer to the real-world behavior, and the strength of the network structure is also improved.

5. Conclusion and Discussion

Given a network, the modularity is used for measuring the partition quality while the fuzzy clustering recognizes the overlapping communities. Combining above concepts together to be the fuzzy modularity is an appropriate method to formulate the structure of the given network with overlapping communities. Maximizing the modularity outputs the partition with well network structure, but computing the partition with maximum modularity requires huge computation cost. Therefore, the heuristic algorithms are outstanding in seeking high quality solution from a large search space, and we can find some research results of using heuristic algorithms for finding the partitions with maximum modularity. However, there are some special cases that we have to deal with. We find out three common situations from the partitions derived from the GA with modularity maximization and propose three solution refinement strategies to ignore overlapping nodes, merge clusters, and reweight nodes to separate the network to be closer the real-world behaviors. Moreover, we modify the fitness function of the GA to consider the null model for measuring the distance between the derived partition and the random graph. Thus, the simulation results show that the proposed $G{A}_{IMR}^{NWA}$ provide significant improvement comparing with previous approaches. The derived partition may not always have maximum modularity, but the community structure is more reasonable than the partitions derived by previous works. $G{A}_{IMR}^{NWA}$ measures the connectivity of nodes and reweight the overlapping nodes to reflect the correct properties in the given networks. Eventually, $G{A}_{IMR}^{NWA}$ determines the partitions appropriately, but the heavily overlapping nodes may be marked as the interior nodes by other approaches.

The overlapping nodes could be detected and provided appropriate allocation by $G{A}_{IMR}^{NWA}$. During the simulations, we found some extension works that will be address in the future, and they are listed as follows:

• In our simulations, we got an interesting result as shown in Figure 14 from the karate network with $in{c}_f=2$. The result consists of three communities, and they are grouped by $v_{33}$, $v_3$ and $v_1$. The community with $v_3$ that the nodes are marked by red could be consider as an overlapping set. It means that the networks not only have overlapping nodes but also overlapping groups. Thus, applying the fuzzy concept to the communities will eliminate the group with $v_3$, and they may be more closed to the real-world behavior. Since the members in the group with $v_3$ may belong to different communities based on the situations, e.g., the competitions or the events. Therefore, assigning the red nodes to any community may be inappropriate.
• The proposed algorithm invokes GA to compute the preliminary partitions and then adopts proposed refinement strategies to correct the partitions by the secondary processes. The refinement strategies could be considered as the local search to improve the partition quality in each iteration. However, it is a tradeoff between the computation cost and the partition quality. Once the refinement strategies are modified from the external processes to the internal processes in GA, the computation cost will be increased. Moreover, the given networks may not always consist of the target properties that could be improved by the refinement strategies. Therefore, the refinement strategies could be designed as local search approaches, but the trigger of launching the local search approaches should be analyzed in the future.