The comparison of significance of fuzzy community partition across optimization methods

Abstract

The analysis of fuzzy(overlapping) community structure in complex networks is an important problem in data mining of network data sets. However, due to the exist of random factors and error edges in real networks, how to measure the significance of community structure efficiently is a crucial question. In this paper, we present a novel statistical framework comparing the significance of fuzzy community structure across various optimization models. Different from the universal approaches, we calculate the similarity between a given node and its leader and employ the distribution of link tightness to derive the significance score, instead of a direct comparison to a randomized model. Based on the distribution of community tightness, a new “p-value” form significance measure is proposed for community structure analysis. Specially, the well-known approaches and their corresponding quality functions are unified to a novel general formulation, which facilitate providing a detail comparison across them. To determine the position of leaders and their corresponding followers, an efficient algorithm is proposed based on the spectral theory. Finally, we apply the significance analysis to some famous benchmark networks and the good performance verified the effectiveness and efficiency of our framework.

1 Introduction

A common feature observed in real networks is the presence of community structures [1–5, 18], i.e. subgraphs which are densely connected to each other while less connected to the subgraphs outside. In many scenarios, nodes in a network can belong to more than one community, called fuzzy(overlapping) communities [2–9]. In order to estimate how much a decomposition of a network which is found by a community detection algorithm is meaningful, we need a quality measure. Consequently, for a particular measure, the community detection algorithms can be ranked. To this end, various measures have been proposed in the literature, so far. The most prevalent measure which has been used extensively in the literature is due to Newman and Girvan [18]. This measure, called modularity, quantifies how much the density of the edges inside identified communities differs from the expected edge density in an equivalent network with similar number of vertices and edges but randomized edge placement, which is taken as the null model for statistical tests. Considering the modularity measure, the community detection problem is transformed to the modularity maximization problem. Modularity function can naturally extended to fuzzy form, which used to detect overlapping communities.

Recently, some optimization algorithms based on Potts models which used to detect community structure have attracted attention. Communities correspond to Potts model spin states, and the associated system energy indicates the quality of a candidate partition. It models an inhomogeneous ferromagnetic system where each node is viewed as a labeled spin in the network. Let A be the adjacency matrix of graph G and let σ _i denote the label of the community that node i belongs to. Furthermore, the Kronecker Delta function is defined by δ (σ _i , σ _j ) =1 if σ _i  = σ _j and δ (σ _i , σ _j ) =0, otherwise. Having the community membership labels σ, Reichardt and Bornholdt (RB) [16] proposed a generalized Hamiltonian as the core energy function, $H_{\mathit{RB}}\left(\right\{\sigma \left\}\right)=-\frac{1}{2}\sum _{i\ne j}(a_{\mathit{ij}}-{\gamma }_{\mathit{RB}}{p}_{\mathit{ij}})\delta ({\sigma }_i,{\sigma }_j).$(1) where γ _RB is the resolution parameter, $p_{\mathit{ij}}\in ℝ$ is the random form of adjacent matrix A = (a _ij ). The Potts dynamical model is a powerful tool which has been wildly applied to uncover the dynamics of community structure in networks [8, 9].

Label propagation is another famous algorithm for community detection [27]. Briefly, the algorithm starts with randomly assigning a community label to each node. Then, each node updates its label by replacing it by the label most used by its neighbors. The other well-known optimization approaches used in community detection problem are Simulated Annealing (SA) [25], extermal optimization (DA) [13], expectation maximization [20], Bayesian inference [17], and variational Bayes [15]. For a comprehensive and comparative review on this topic we refer the reader to [4].

Although a lot of optimization method and their functions are proposed, How to determine the hidden properties of a given community [9] effectively remain unclearly answered. To answers these crucial questions, in this paper, we present a novel statistical framework comparing the significance of soft community structure across various optimization methods. Different from the universal approaches, we calculate the similarity of a given node to its leader and employ the distribution of link tightness to derive the significance score, instead of a direct comparison to a randomized model. A small example is shown in Fig. 1a, which illustrates that tighter the following nodes link to its leader, more significant the community is. Based on the distribution of community tightness, a new “p-value” form significance measure is proposed for community structure analysis. Specially, the well-known approaches and their corresponding quality functions are unified to a novel general fuzzy formulation, to provide a detail comparison across them. Then, we can choose the most suitable form of the function by set the parameters properly. To determine the position of leaders and their corresponding followers, an efficient fuzzy detection algorithm is proposed based on the spectral theory. Finally, we apply the significance analysis to some famous benchmark networks and the good performance verified the effectiveness and efficiency of our framework. The detailed procedure can be observed in Fig. 1b.

2 Community structure and the leader

Leader-driven algorithms [11, 12] constitute a special case of seed-centric approaches. These methods show that, in many real world, especial the social networks, nodes of a network are usually classified into two categories: leaders and followers. For example, considering the famous Karate network [28], nodes 1 and 33 are two significant leaders and corresponding communities are built around them (see Fig. 2a). If two leaders are removed, these communities will be split up, as they link to most followers and keep the community together. Since community are consequence of information spreading, a given community can be defined as the area in which a leader has most influence. So, one can uncover the community partition by finding all natural leaders and their corresponding followers on which they influence. We believe if followers are more tightly linked to the leader, or leader spreads more influence on their followers, this community are more significant or robust. When we use a given optimization method to evolve the community configure, the significance of communities also evolves correspondingly, which shown in Fig. 2b.

3 The fuzzy community detection algorithm based on leader position

In this study, the relative positions of leader and corresponding followers are crucial to analyze the significance situation. In order to obtain the leader of corresponding community, we extract the candidate fuzzy membership by minimizing the following objective function $J_m=\sum _{i=1}^n\sum _{j=1}^k{x}_{\mathit{ij}}{\parallel d_i-c_j\parallel }^2,$(2) where variables x _ij is the fuzzy membership that node i in community j, with ∑ _j x _ij  = 1. This method is similar as the famous k-means method and can be obtain both center and assignment iteratively. d _i is the ith n-dimensional data point, c _j is the n-dimensional center(leader) of the community j, and ∥* ∥ is any norm expressing the similarity between a given node and the center. One can use an iterative optimization of the objective function shown above, to obtain the network partition by the update of fuzzy membership x _ij and the community leaders c _j . This procedure converges to a local minimum or a saddle point of J _m .

Suppose K is the upper bound of number of clusters and A = (a _ij ) _n×n is the adjacent matrix of a network, then, the detailed algorithm is shown in Algorithm 1 and stated straightforwardly as follows:

Step 1: for a given K

(i) Calculate the diagonal matrix D = (d _ii ), where d _ii  = ∑ _k a _ik .

(ii) Computing the top K eigenvectors based on generalized eigensystem Ax = tDx, and then establish the eigenvector matrix E _K  = [e₁, e₂, . . . , e _K ].

Step 2: for each number of communities 2 ≤ k ≤ K:

(i) Establish the matrix E _K  = [e₂, e₃, . . . , e _K ] from the matrix E _K .

(ii) Normalize the rows of E _K to unit length using Euclidean distance norm.

(iii) Cluster the row vectors of E _K using any community detection method by minimizing Equation.(2) to obtain a membership matrix X _k and corresponding leaders.

Step 3: Maximizing the modular function: Pick the optimal number of communities k and the corresponding partition X _k that maximizes Q (X _k ).

In step 1, given the adjacent matrix A = (a _ij ) _n×n and a diagonal matrix D = (d _ii ), d _ii  = ∑ _k a _ik , two matrices D^-1/2AD^-1/2 and D^-1A are used. This is motivated by Ref. [7], which uses the top K eigenvectors of the generalized eigensystem Ax = tDx instead of the K eigenvectors of the adjacent matrix. It shows that after normalizing the rows using Euclidean norm, their eigenvectors are mathematically identical and emphasize that this is a numerically more stable method. In step 2, we choose the initial the starting centers to be as orthogonal as possible which already used in k-means clustering method [6, 26]. This way of choosing centers(leaders) does not cost additional time complexity, and also improve the quality of the partition, thus at the same time reduces the need for restarting the random initialization process. In step 3, the Q function measures the quality of a given community structure organization of a network and can be used to automatically select the optimal number of communities k according to the maximum Q value [26], we will discuss the multiple optimization methods and their corresponding Q function in detail in the following section.

Algorithm 1 The fuzzy community detection algorithm

Require:    Graph G with size n and volume m, the algorithm parameters, i.e. $f_{\mu }^{+}$, $f_{\mu }^{-}$ and R _μ which shown in Equation. (3)

Ensure    The fuzzy membership matrix X;

   For a given number of communities K

   repeat

     Calculate the top K eigenvector matrix E _K  = [e₁, e₂, . . . , e _K ] and initiate the community membership X (0) = E _K .

     Update the position of center and corresponding community membership matrix X to minimize the Equation.(2)

   Until exceeding the maximum number of iterations

   Select the optimal number of communities K and corresponding community membership according to the maximum of Q defined in Equation. (3)

4 The general and expanded formation of function Q

For many community detection algorithms, the target function Q is critical. Here, Q can be tried to be optimized has the following general fuzzy form:

$\begin{array}{ccc}\hfill Q_{i\mu }& \hfill =\hfill & \sum _{j=1}^n{f}_{\mu }^{+}{a}_{\mathit{ij}}{x}_{j\mu }\hfill \\ \hfill & \hfill \hfill & -\sum _{j=1}^n{f}_{\mu }^{-}(1-a_{\mathit{ij}})x_{j\mu }+R_{i\mu },\hfill \end{array}$(3) and choose R _iμ such that ∂R _iμ /∂x _iμ  = 0 and $R_{\mathit{mu}}={\sum }_{i=1}^n{R}_{i\mu }$, e.g. $R_{i\mu }=\frac{2}{l_{\mu }}{R}_{\mathit{mu}}$. Interestingly, when all x _iμ are in fuzzy membership state, the H function with Q _iμ defined as Equation. (3) can be reduced to well-known measures by following considerations:

(1) Hofman and Wiggins [15]

$\begin{array}{ccc}\hfill f_{\mu }^{+}& \hfill =\hfill & log\frac{p^{\mathit{in}}}{p^{\mathit{out}}},f_{\mu }^{-}=log\frac{1-p^{\mathit{out}}}{1-p^{\mathit{in}}},\hfill \\ \hfill R_{\mu }& \hfill =\hfill & l_{\mu }log{\pi }_{\mu }.\hfill \end{array}$(4) (2) Ronhovde and Nussinov [23] $f_{\mu }^{+}=1,f_{\mu }^{-}=\underset{\mu }{min}{p}_{\mathit{in},\mu },R_{\mu }=0.$(5) (3) RB Potts model (Erdős-R$\acute{e}$nyi null model) [16] $f_{\mu }^{+}=1-{\gamma }_{\mathit{RB}}p,f_{\mu }^{-}={\gamma }_{\mathit{RB}}p,R_{\mu }=0.$(6) (4) RB Potts model (Configuration null model)[16]

$\begin{array}{ccc}\hfill f_{\mu }^{+}& \hfill =\hfill & 1-\frac{{\gamma }_{\mathit{RB}}}{2m},f_{\mu }^{-}=\frac{{\gamma }_{\mathit{RB}}}{2m},\hfill \\ \hfill R_{\mu }& \hfill =\hfill & \sum _{i>j}\frac{{\gamma }_{\mathit{RB}}}{2m}(k_i{k}_j-1)x_{i\mu }{x}_{j\mu }.\hfill \end{array}$(7) where k _i is the degree of node i and m is the number of all edges in the network.

(5) Modularity [18] $f_{\mu }^{+}=1,f_{\mu }^{-}=\frac{k_i{k}_j}{2m},R_{\mu }=\sum _{i>j}\frac{1}{2m}(k_i{k}_j-1)x_{i\mu }{x}_{j\mu }.$(8) where k _i is the degree of node i and m is the number of all edges in the network.

(6) Label propagation [27] $f_{\mu }^{+}=1,f_{\mu }^{-}=0,R_{\mu }=0.$(9) where k _i is the degree of node i and m is the number of all edges in the network.

5 Significance of community structure

It is essential to establish a detail framework analyzing the significance of community structure, since real networks own specific characteristics [5, 29]. In this section, we discuss these important characteristics and give a detailed introduction of the framework.

Node similarity. We define the similarity of nodes i and j, sim (i, j), as the ratio between the intersection and the union of their neighborhoods Γ (i) and Γ (j), $\mathit{sim}(i,j)=\frac{\left|\Gamma \right(i)\cap \Gamma (j\left)\right|}{\left|\Gamma \right(i)\cup \Gamma (j\left)\right|},$(10) By employing Equation. (10), we can calculate the expected similarity between a given node and the community leader z, $\mathit{E}\left[\mathit{sim}\right(x,z\left)\right]={\int }_{{ℝ}^M}\mathit{sim}(x,z)Q\left(x\right|z)\mathit{dx},$(11) where Q (x|z) is a distribution of nodes in a community with leader z.

Next, using the maximum entropy principle, the statistical unbiased distribution fulfilling constraint can be obtained using the maximum entropy principle: $Q\left(x\right|z,\eta )=\frac{1}{Z_{\eta }}{P}_0(x)e^{\eta \mathit{sim}(x,z)}\mathit{dx},$(12) where P₀ (x) is the background distribution used to contrast with an alternative hypothesis: node x being part of a community, a group of nodes distinguished by enhanced mutual similarity. Z _η is the normalisation constant depends on the value of the scoring parameter η: $\frac{\partial }{\partial \eta }log{Z}_{\eta }=\mathit{E}\left[\mathit{sim}\right(x,z\left)\right].$(13)η is the parameter which used to control the “width” of a community and the larger the value of η, the smaller the expected width or scale of a given community. Specially, the distribution Q (x|z, η) is the same as the background model P₀ (x) when η = 0.

Log-likelihood score and community tightness. We define the log-likelihood score as the deviations of the community distribution from the null model $s\left(x\right|z,\eta )\equiv log\frac{Q\left(x\right|z,\eta )}{P_0\left(x\right)}=\eta \mathit{sim}(x,z)-log{Z}_{\eta }.$(14) By Equation. (14), nodes which are more likely to be in a community with center z and scoring parameter η own larger positive value, than in the null background model. Given a community with nodes set {1, . . . , N}, for a given leader z and a scoring parameter η, the log-likelihood scores s (i|z, η) are positive. The community tightness is the sum of the scores of the community elements, $S(1,...,N|z,\eta )=\sum _{i}max[s\left(i\right|z,\eta ),0].$(15)

However, we can’t determine the scoring parameter η easily. Here, the tightness function of Equation.(15) can be simplified as: $S(1,...,N|z,\eta )=\sum _{i=1}^{N}max[s\left(i\right|z)-\mu ,0],$(16) where s (i|z) = sim (i, z). By this transformation, one can control the width of community using parameter μ simply. The community tightness is determined both by the number of elements and by their similarities with the leader, that is, tighter communities with fewer elements own comparable more tightness to looser but larger communities.

Calculation of Significance score. We can the quantified the quality of the true and random communities by characterize the distribution of the tightness score p (S) from the background distribution. A new “p-value” form measure [14] can be used to define the statistical significance of score S₀, as the probability that a random chosen nodes set contains a community with score greater than or equal to S₀. This “p-value” form significance can be explained by a null hypothesis: “These nodes are drawn from the background distribution”. To test this hypothesis, we compute the statistical significance of score S₀: low value suggests that the null hypothesis is unlikely and allows for rejecting it. This method provides a new connection between statistical p-value theory and network analysis and then get an interesting significance measure.

If the network is large enough, according to the mean field theory, s _i  = s (i|z) owns an approximate Gaussian-distribution with variance M, $P\left(s\right(i\left|z\right))=\sqrt{1/\left(2M\pi \right)}exp\{-s^2/\left(2M\right)\}$. The distribution of the tightness S can be calculated straightforwardly using the derivation. Specifically, we need to compute the following quality function:

$\begin{array}{ccc}\hfill & \hfill \hfill & Z_c(\beta ,\mu )={\int }_{{ℝ}^N}{e}^{\beta S(1,...,N|z,\eta )}P\left(s_1\right)...P\left(s_N\right){\mathit{ds}}_1...{\mathit{ds}}_N\hfill \\ \hfill & \hfill \hfill & ={\left[{\int }_{-\infty }^{+\infty }{e}^{\beta max[s_i-\mu ,0]}P\left(s\right)\mathit{ds}\right]}^N\hfill \\ \hfill & \hfill \hfill & ={\left[{\int }_{-\infty }^{\mu }P\left(s\right)\mathit{ds}+{\int }_{\mu }^{+\infty }{e}^{\beta (s_i-\mu )}P\left(s\right)\mathit{ds}\right]}^N\hfill \\ \hfill & \hfill \hfill & ={\left[(1-H(\mu \left)\right)+e^{\frac{(\beta {)}^2}{2}-\beta \mu }H(\mu -\beta )\right]}^N,\hfill \end{array}$(17) where $H\left(x\right)={\int }_x^{+\infty }\frac{1}{\sqrt{2\pi }}{e}^{-\frac{1}{2}{y}^2}$ is the complementary cumulative Gaussian distribution. In Equation.(17), two intervals are divided: below the score threshold μ, the score is zero, which contributes the cumulative distribution ${\int }_{-\infty }^{\mu }\mathit{ds}/(2\pi {)}^{1/2}exp[-s^2/2]$ to the generating function. Above μ, the score is positive, which generates a contribution of ${\int }_{\mu }^{+\infty }\mathit{ds}/(2\pi {)}^{1/2}exp[-s^2/2+\beta (s-\mu )]$. The free energy function reads $-\beta f(\beta ,\mu )=log\left[\right(1-H\left(\mu \right))+e^{\frac{(\beta {)}^2}{2}-\beta \mu }H(\mu -\beta \left)\right],$(18) and the entropy is $\omega (s,\mu )=-\underset{\beta }{max}[\beta s+\beta f(\beta ,\mu \left)\right].$(19) Using the distribution of community tightness, there is $logp(S,\mu )\simeq N\omega (S/N,\mu )-\frac{1}{2}logN.$(20)

Given a specifical community, we can calculated the significance score F using the probability that the community tightness S, p (S), larger than or equal to S, $F(S,\mu )={\int }_S^{+\infty }p(S^{\prime },\mu ){\mathit{dS}}^{\prime }.$(21) Furthermore, from the perspective of the whole network, we use the average significance score 〈F〉 _Q to indicate the robustness of a partition, defined as the average value among F values of all communities partitioned by maximizing a particular quality function Q shown in Section 4.

6 Experiments on benchmark network

In this section, we will test the validity of our framework on some famous benchmark network and real networks.

GN benchmark network. First, we apply to the classical Girven-Newman benchmark [21], where the network with n = 128 nodes are divided into four 32 nodes communities. According to the establish mechanism, the community structure will fuzzier and thus when 〈k ^out 〉 increases, it is more difficult to identify them correctly. Hence, the significance of communities will tend to be weaker and the value of F index will also decrease. The comparison results of F value corresponding to all five optimization algorithms are shown in Fig. 3a when μ = 0.3. It can be observed that the index F has a great performance on GN benchmark: when 〈k ^out 〉 approaching 0, the community structure is quite strong and all corresponding 〈F〉 value is close to 1; while when the network is fuzzy enough, the corresponding 〈F〉 value of all algorithm is low, extremely for Modularity optimization method and Label propagation method, only near 0.2–0.3.

Moreover, by comparing five algorithms, we find in Fig. 3a that the 〈F〉 values corresponding to Hofman & Wiggins method is largest, and the Label propagation method is the lowest. This may because Label propagation method emphasize the simplicity of calculation too much while ignoring the accuracy of results. Furthermore, the 〈F〉 values between Modularity optimization method and Label propagation method are similar when 〈k ^out 〉 becomes lower. This result is similar as Ref. [22], which verifies the inner correlation between these two methods. These observations are no evidence of overall superiority of one method over another, but an example of how to compare the significance and use the different partitioning algorithms on a given network.

Furthermore, when 〈k ^out 〉 increases, the topology becomes fuzzier and the sizes of communities will become more and more smaller correspondingly. At the same time, as the width parameter μ increases, the significance will favor tighter communities with fewer elements. We test the Hofman & Wiggins method and Label propagation method in Fig. 3b, the value of 〈F〉 corresponding to μ = 0.3 will be larger than μ = 0.1 for all two examples. As a conclusion, we argue that when the corresponding 〈F〉 is smaller than 0.3 on average (〈k ^out 〉≈4), it is not safe to say there exists significant community structure for a given network.

LFR benchmark network. We also test the index on the more challenging LRF benchmark presented by Lancichinetti, Fortunato and Radicchi [3]. In this network, the average degree k = 20, maximum degree is 50 and P (k) ∝ k ^γ . Maximum and minimum community sizes are 50 and 20 respectively. The significance score changes when we adjust the value of θ in LFR benchmark, and numerical results in the LFR-benchmark are shown in Fig. 4a. It can be observed that with the augment of θ, F decreases for all five optimization methods when μ = 0.3. Same as GN network, the 〈F〉 values corresponding to Hofman & Wiggins method is largest at the begining, and the Label propagation method is the lowest. However, the 〈F〉 values corresponding to Ronhovde & Nussinov method will exceed Hofman & Wiggins method when when θ is larger than 0.4. Furthermore, when θ larger than 0.32, the 〈F〉 value corresponding to Label propagation method is close to Modularity optimization method. In addition, from Fig. 4b, it can be observed the value of 〈F〉 corresponding to μ = 0.3 will larger than μ = 0.1 when we take the Hofman & Wiggins method and Label propagation method as examples.

Stochastic block model. Furthermore, we consider the famous stochastic block model which used to detect community structure by Decelle and Zhang et al. [1, 24]. In this benchmark, ɛ = c _out /c _in is the parameter used to control the fuzziness of generated network. To verify the performance on sparse stochastic block model with low average degree, we generate a large network with N = 5000 nodes and q = 10 groups with average degree c = 8, which shown in Fig. 5. Each point in curves is the result averaged by testing 100 times. When ɛ is close to 0, it can be observed the community structure is quite strong and the corresponding 〈F〉 value of all five algorithms are very high when μ = 0.3. In contrast, when ɛ is increased close to 0.8, the network is nearly a fuzzy random one, and all 〈F〉 values are very low, near 0.1–0.3. Furthermore, we find that the 〈F〉 value of Hofman & Wiggins method will larger than all others when ɛ < 0.81, while lower than Ronhovde & Nussinov method when ɛ > 0.81. Specifically, we argue that for all algorithm when the corresponding 〈F〉 is nearly larger than 0.3 on average(ɛ ≈ 0.4), there exists significant community structure which may detectable [1]. From the results, the F shows a great ability in characterizing the significant modular structure for optimization methods as we adjust the parameter ɛ.

Real network. Finally, we show significance can also be used to rank the real network partitions obtained by different algorithmic strategies. Zachary karate club network, Collage football network and Political books network are employed as the examples. Table 1 presents the results estimated from three algorithms and we observed that they are coincided with the analysis in artificial networks. These observations are no evidence of overall superiority of one method over another, but an example of how to compare the significance and use the different partitioning algorithms on a given network.

7 Discussion

In this paper, we present a novel framework comparing the significance of fuzzy community structure revealed by multiple optimization functions. Based on the distribution of community tightness, a new “p-value” form significance measure is proposed for analysis. As part of the future work, it is necessary to take a deeper look into how different similarity measures impact the results of this method. Additionally, this framework can be easily extended to a weighted and directed form, which only needs to modify the formation of the quality function Q. As a conclusion, this method shows a great performance and deserves more attention from us.

Acknowledgments

We are grateful to the anonymous reviewers for their valuable suggestions which are very helpful for improving the manuscript. The authors are separately supported by NSFC grants 71401194, 91324203, 11131009 and “121” Youth Development Fund of CUFE grants QBJ1410.