Explore of the fuzzy community structure integrating the directed line graph and likelihood optimization

Abstract

Detecting fuzzy network communities in directed network is a classic and very difficult task in the field of complex network analysis, principally for its applications in domains such as social or biological networks analysis. Present techniques rely heavily on network topology, which cannot provide a lot of important information, such as module correlation and hierarchical structure. In this paper, we present a new fuzzy community detection method, which is able to find fuzzy communities in directed line graphs by maximizing likelihood function. Firstly, the directed node graph is transformed to a new type directed line graph, and the direction and weight of line graph are defined. Then, the community unit consists of membership and correlation information is defined in the line graph. Specifically, there are two main contributions of this method: 1) to adequately characterize the community structure, the node and module correlation with different granularity can be calculated; 2) based on the membership and correlation information, we can extract the multiplex patterns between communities, according to different domain requirements. Furthermore, we are able to map the link community configuration to the optimal situation dynamically by maximizing the likelihood function with rigorous mathematical proof. Based on the spectral analysis of the Markovian transition matrix, a mathematical theory is provided to identify the optimum number of network communities, and to analyze the stability of the community structure. Extensive simulations using both synthetic and real-world benchmark networks are performed to verify the algorithmic performance.

Keywords

Fuzzy community line graph optimization method likelihood function benchmark networks

1 Introduction

Recent years have witnessed an increasing interest in detecting communities in large-scale networks of various kinds. Communities are clusters of closely connected nodes within a network. Since massive online social networks have been deeply integrated into our daily life, detecting meaningful communities from them has become a critical task for research and applications of various purposes. Early work in graph partitions [1 –3] could be adopted for community detection. However, these methods usually require the knowledge on the number of communities as part of the input, which is unrealistic in community detection problems. Modularity [2, 3], proposed by Newman et al., is the first successful attempt to resolve the drawback specified above. Modularity scores prefer those partitions containing communities with an internal edge density larger than expected in a given graph model. The other well-known optimization approaches used in community detection problem include simulated annealing (SA) [4], external optimization (DA) [5, 10], Potts dynamical [6, 7], Bayesian inference [8, 12] and model selection analysis [9]. To the best of our knowledge, the most competitive approach of this kind is Louvain [11], which can scale to graphs with hundreds of millions of objects.

Most existing community detection algorithms focus on partitioning a network such that each node belongs to only one community exactly, however, in many real social and biological networks, nodes may simultaneously participate in multiple communities [13 –15]. In this paper, we present a new fuzzy community detection method, which is able to find fuzzy communities in directed line graphs by maximizing likelihood function. Firstly, the directed node graph is transformed to a new type directed line graph, and the direction and weight of line graph are defined. Then in the line graph, we define the community unit including membership and correlation information. Specifically, there are two main contributions of this method: 1) to adequately characterize the community structure, the node and module correlation with different granularity can be calculated; 2) based on the membership and correlation information, we can extract the multiplex patterns between communities, according to different domain requirements. Furthermore, we are able to map the link community configuration to the optimal situation dynamically by maximizing the likelihood function with rigorous mathematical proof. Based on the spectral analysis of the Markovian transition matrix, a mathematical theory is provided to identify the optimum number of network communities, and to analyze the stability of the community structure. Extensive simulations using both synthetic and real-world benchmark networks are performed to verify the algorithmicperformance.

2 Line graph and link communities

The fuzzy characteristic exists pervasively in the community structure of many real networks, where each node participates in more than one modules. In this paper, rather than regarding communities as assemble of nodes simply, we reveal and analyze communities as groups of links, which successfully coincide with the organizing principles of overlapping communities. Different from the existing hard partition methods, link communities [16 –18] focus on revealing the overlapping organization using topological information, naturally.

In Ref [16, 17], Evans et al. introduced a pioneering model which transformed a network of nodes into a line graph using a random walk, and then detected link communities by applying an existing algorithm for node partition on this line graph. The most popular method for identifying link communities was proposed by Ahn et al. [18], which used a hierarchical clustering on a similarity between links to build a dendrogram of links to form a hierarchy of link structure. In order to derive the most relevant communities, they introduced a density function to determine the best level to cut the tree of links. He et al. [19] proposed a link dynamics based algorithm, called UELC, which using the stochastic process of a link-node-link random walk is employed to unfold an embedded bipartition structure of links in a network. The local mixing properties of the Markov chain underlying the random walk are then utilized to extract two emerged link communities. Li et al. [20] proposed a quantity function for identifying link community, and based on this quantity function, they further formulate the link community partition problem into an integer programming model which able to partition a complex network into overlapping communities. He et al. [21] introduced a mixing approach for identifying complex structures including both node and link communities, called hybrid node-link communities, which using a probabilistic model that accommodates node, link and hybrid community structure.

Even though each link is assigned only a single membership, we can use link communities to capture multiple relationships between nodes, since many nodes may belong to several different communities together, simultaneously. A representative example is the heterogeneous cliques network, which shown in Fig. (1). In this network, each community is a single clique which marked by different shapes and two adjacent communities are overlapped by only one node.

Fig.1

A heterogeneous cliques network, where each link community is a clique. Between two adjacent link communities, two overlapping nodes are highlighted.

To reveal the emerged link communities, we first transform the original unweighted directed node-node network N, to an equivalent weighted directed link-link line graph G. For a given network N, each node of its corresponding line graph G represents a directed link of N and two nodes of G are adjacent when their corresponding links share a common endpoint in N. We denote the adjacent matrix of node graph N as A = {a_i}. Different from traditional unweighted node graph, the line graph is weighted. However, few researchers has focused on the study of direction and weight calculation of directed line graph. Here, we explore this problem and transform the node-node direction in node graphs to the link-link direction in the corresponding line graphs (Fig. 2). Then, the edge weight is calculated by the following function: $w (l_{ik}, l_{jk}) = \frac{a_{i} \cdot a_{j}}{| a_{i} |^{2} + | a_{j} |^{2} - a_{i} \cdot a_{j}},$ (1) where a_i is the i-th row of symmetric adjacent matrix $\bar{A} = A + A^{T}$ in node network N, the numerator a_i · a_j represents the number of common inclusive neighbors (without consider the edge direction) between node i and j; the denominator represents the number of all inclusive neighbors of node i and j. One can observe that the value of w (l_ik, l_jk) lies between [0, 1] and larger the weight w, more common neighbors shared by the endpoint i and j. A simple example is shown in Fig. 3. The weight w defined in Equation (1) is a simplified and reasonable definition, which is driven just by the network topology.

Fig.2

The transformation of node-node direction in node graphs to the link-link direction in the corresponding line graphs.

Fig.3

An toy example that transforming the original network into the corresponding weighted line graph. (a) The original network N contains two link communities highlighted by different shapes. As the joint part, node 3 can be considered as the overlapping node. (b) The transformed line graph L. The width of edges is proportional to its weight, which calculated according to Equation (1). If we cluster the line graph using any hard partition algorithm(weighted), the links belong to different link communities can also be recognized.

From the practical point of view, the overlapping node in any communities can be naturally detected by partitioning the links into communities in line graphs using any hard partition method, because the links connected to a node could belong to different link communities and consequently the node could be assigned to multiple communities of links.

3 The community detection algorithm

3.1 The community unit

For a weighted and directed line graph G = (V, E), denote V (G) and E (G) are the set of nodes and directed edges, respectively. We denote the weight matrix of line graph G as W_n×n, where n represents the size of G (number of nodes). Suppose the network G is divided and separated into L (1 ≤ L ≤ n) modules, the node membership is denoted as B_n×L, where b_il = 1 if node i belongs to module l, otherwise b_il = 0. Consider each module is inseparable, one can use the average size of modules g = n/L as the “granularity”, which represents the line graph G evolves from the finest to coarsest as g increases from 1 to n.

In our framework, two different kinds of correlations, i.e. node correlation and module correlation, are defined. Correspondingly, two kind of correlation matrix with different resolutions are defined. We denote node forward-correlation matrix as P_n×n and node back-correlation matrix as Q_n×n, where p_ij and q_ij represent the expect probabilities that node i correlates with or to be correlated by node j, respectively. We expect to cluster nodes with similar forward-correlation and back-correlation distributions into the same modules. If L represents the number of modules, we also define the module forward-correlation matrix Φ_L×L and module back-correlation matrix Ψ_L×L, where φ_pq and ψ_pq represent the expect probabilities that module p correlates with or to be correlated by module q, respectively. It will be shown later that module correlation matrix can be inferred based on node correlation matrix and viceversa.

As it can be expected that the distribution of node correlations within the same modules are homogeneous, we should characterize the correlation distribution for modules instead of nodes. We denote the module matrix B with specific granularity g as B_g. Specifically, when g = 1, there is B₁ = I_n×n. It can be expected that cluster L modules into a specific number of communities so that the nodes within modules belonging to the same communities exhibit similar correlation distributions. The module membership is represented by matrix Z_L×K (1 ≤ K ≤ L), where z_lk = 1 if module l is clustered into community k, otherwise z_lk = 0, K is the number of communities. Furthermore, for a specific Z, Θ_K×n = (θ_kj) is denoted as the probability that a node out of community k expects to correlate with node j; Δ_K×n = (δ_kj) is denoted as the probability that a node out of community k expects to be correlated with node j; Ω (ω₁, . . . , ω_K) ^T = (ω_k) is denoted as the prior probability that a randomly selected node will belong to community k. It can be easily found that P = {p_ij} = B_gZΘ and Q = {q_ij} = B_gZΔ.

For B_g, we consider X = (K, Z, Θ, Δ, Ω) as a community unit (CU) of line graph G with respect to B_g, where Z = {z_ik} is the module membership matrix that Z_ik = 1 indicates node i belongs to module k, and otherwise. From the hypothesis space of X, one can expect to find the optimal one to predict the module correlation exactly in terms of B_g. Based on the posteriori maximum principle, for a given line graph G, we expect to select the optimal X according to B_g by maximizing the posterior probability. Specifically, there is $P (X | G, B_{g}) \propto P (G | X, B_{g}) P (X | B_{g}) .$ (2) Here, P (X|G, B_g), P (G|X, B_g), and P (X|B_g) denote the posteriori of X given line graph G and B_g, the likelihood of line graph G given X and B_g, and the priori of X given B_g, respectively.

The X is used to characterize the membership and correlation behavior of line graph G. Next, in order to compress the correlation behavior in node level to module level, we propose the detailed definition of module correlation, module forward-correlation Φ = {φ_ij} and module back-correlation Ψ = {ψ_ij} in terms of Θ, Δ, Z, and Ω: $\begin{matrix} {\begin{matrix} Φ = & Θ B_{1} Z D_{- 1} = Θ Z D_{- 1} \\ Ψ = & Δ B_{1} Z D_{- 1} = Δ Z D_{- 1} \end{matrix} \end{matrix}$ (3) where D = diag (nΩ), Z is the module membership matrix. For the detailed derivation of Equation (3), please refer to the Supplementary Material[30].

Then some important properties can bedefined.

The forward and back coupling strength between two communities k and s can be represented by Φ_ks and Ψ_ks, defined as the module correlation.

The “importance” of a given community μ is defined intuitively as the sum of forward and back coupling strength, i.e. I_μ = ∑_sΦ_μs + Ψ_μs.

Specifically, we can also compress and map the membership matrix Z into module label y, where y (i) = k if the entry (i, k) of B₁Z = Z is 1 (node i belongs to module k). For a given combination y, Φ, and Ψ, we can transform the node correlation p_ij and q_ij by $p_{ij} = φ_{y (i), y (j)}; q_{ij} = ψ_{y (i), y (j)} .$ (4)

3.2 Likelihood maximization

As discussed above, we expect to find the optimal X by maximizing the posterior probability of Equation (2). According to Equation (2), as P (X|G, B_g) proportional to the product of P (G|X, B_g) and P (X|B_g), we can maximize P (X|G, B_g) by maximizing P (G|X, B_g) and P (X|B_g), respectively.

First, let’s consider the likelihood P (G|X, B_g). We use the logarithmic transformation L (G|X, B_g) = lnP (G|X, B_g), and there is

$\begin{matrix} L (G | X, B_{g}) \\ = \sum_{l = 1}^{L} \sum_{b_{il} \neq 0} \sum_{k = j}^{K} \prod_{j = 1}^{n} f (θ_{kj}, a_{ij}) f (δ_{kj}, a_{ji}) w_{k}, \end{matrix}$ (5) where f (x, y) = x^y (1 - x) ^1-y (for the detailed calculation of Equation (5), please refer to the Supplementary Material [30]). Based on the Equation (5), there is the following theorem:

Theorem 1. A local optimum of maximizing Equation (5) will be guaranteed by recursively calculating Equations (6) and (7): $\begin{matrix} {\begin{matrix} θ_{kj} = & \frac{\sum_{l = 1}^{L} \sum_{b_{il} \neq 0} a_{ij} γ_{lk}}{\sum_{l = 1}^{L} \sum_{b_{il} \neq 0} γ_{lk}} \\ δ_{kj} = & \frac{\sum_{l = 1}^{L} \sum_{b_{il} \neq 0} a_{ji} γ_{lk}}{\sum_{l = 1}^{L} \sum_{b_{il} \neq 0} γ_{lk}} \\ ω_{k} = & \frac{\sum_{l = 1}^{L} \sum_{b_{il} \neq 0} γ_{lk}}{n} \end{matrix} \end{matrix}$ (6)

$\begin{matrix} γ_{lk} & = & \frac{1}{\sum_{i = 1}^{n} b_{il}} \\ \times \sum_{b_{il} \neq 0} \frac{\prod_{j = 1}^{n} f (θ_{kj}, a_{ij}) f (δ_{kj}, a_{ji}) w_{k}}{\sum_{k = 1}^{K} \prod_{j = 1}^{n} f (θ_{kj}, a_{ij}) f (δ_{kj}, a_{ji}) w_{k}} . \end{matrix}$ (7) The detailed proof of Theorem 1 is shown in Supplementary Material [30]. Here, γ_lk = E [z_lk] = P (y = k|b = l, X, B_g), i.e., the probability that module l is labeled with community k given X and B_g.

3.3 The optimal community membership

Next, we employ the information theory and approximate the prior P (X|B_g). As 1 ≤ K ≤ L = n/g, a larger number of communities K implies a finer granularity. In the following, we will show that a more complexity of community unit X will be caused by a larger K. One can note that a finer granularity results in more complex models. There is the following mathematical relationship: $P (X | B_{g}) = η (X)^{g} .$ (8) Here, η (X) represents the complexity of pattern X based on its parameters. Specifically, the complexity is set as η (X) = P (X|B₁) = P (X), i.e. the prior of X with g = 1.

Based on the information theory, with prior P (X), ln (1/P (X)) can be used to describe the “minimum description length” of X. We denote $\bar{X}$ as the optimal coding schema of X, and denote $C (\bar{X})$ as the coding length of X under this schema, which indicates the complexity. There is $- lnP (X | B_{g}) = - glnP (X) = gC (\bar{X}) .$ (9)

In order to calculate the prior P (X|B_g), we need to design a compressed coding schema as close to $\bar{X}$ as possible. Finally, we have $C (\bar{X}) \approx C (\hat{X}) = 2 K^{2} ln K^{2} + 2 n ln 2 n .$ (10) For the detailed calculation of Equation (10), please refer to the Supplementary Material [30]. Based on Equation (2) and analysis before, for a given line graph G, there is

$\begin{matrix} arg & max_{X} P (X | G, B_{g}) \\ = & arg min_{X} (- ln P (G | X, B_{g}) - ln P (X | B_{g})) \\ = & arg min_{X} (- ln P (G | X, B_{g}) + gC (\bar{X})) \\ = & arg min_{X} (- L (G | X, B_{g}) \\ + g (2 K^{2} ln K^{2} + 2 n ln 2 n)) \\ = & arg min_{X} (- L (G | X, B_{g}) + 2 {gK}^{2} ln K^{2}) . \end{matrix}$ (11) Equation (11) tries to make a good balance between the precision of this model (measured by the likelihood function) and its complexity (measured by the optimal coding length of this model). If the number of communities K is fixed, the penalty term, i.e. 2gK² ln K² is a constant. Thus, maximizing the term P (X|G, B_g) is transformed to maximize L (G|X, B_g). In our algorithm, K is not known as a priori and it always matters for community detection algorithms. In the next section, we will discuss an efficient method to determine the reasonable numbers of communities in a multiscale way.

3.4 The computational complexity

In the proposed algorithm, maximizing the likelihood function of Equation (5) of multiplex structures is the most computationally costly step, and its running time will dominate the time complexity of the whole computing process. We will analyze its worst time complexity. It is easy to verify that the calculation of θ, δ and ω by Equation (6) will take O (nK) time, and the calculation of γ by Equation (7) will take O (n²K²) time. As mentioned, n is the number of nodes in the whole network, and K is the number of clusters. Therefore, the time complexity of the proposed algorithm is O (tn²K²), where t is the required iterations. Actually, by means of an efficient greedy strategy, the efficiency of the procedure would be greatly improved.

4 Determine the optimal number of communities

One issue that should be addressed before running the algorithm is the number of communities. In fact, The number of the communities is not known as a priori and it always matters for community detection algorithms. Here, by employing the Markov process and spectral theory, we provide a rigorous proof and deduce the optimal number of community theoretically. Furthermore, some important hidden information, such as stability of community structure, can also be obtained.

In an ergodic Markov process, P^t is represented as the transition probability matrix of line graph G among nodes after t steps. In order to calculate the matrix P^t, we use the eigenvalue decomposition of P. The eigenvalue λ_k , k = {1, ⋯ , n} and its corresponding eigenvectors satisfy: $P^{t} u_{k} = λ_{k}^{t} u_{k}, f_{k} P^{t} = λ_{k}^{t} f_{k},$ (12) where u_k and f_k are the right and left eigenvectors. Then, we can symmetrize P^t as ${\bar{G}}^{(t)} = (P^{t} + (P^{t})^{T}) / 2$ .

Assuming that the network A is divided into c disjoint sets(communities) V_μ ⊂ V, μ ∈ {1, 2, ⋯ , c}, forming a partition of V jointly. We use n_μ = |V_μ| to represent the number of nodes in each community. To facilitate further discussion, we reformulate the objective function in a matrix form. We use binary vector x_μ, which describes the involvement of each node in community μ, to represent the membership vector. Considering the orthogonal vectors x_l and x_s, the c community structure can be detected by the maximization of the following function: $J_{c}^{(t)} = \sum_{μ = 1}^{c} \sum_{i, j \in V_{μ}} \frac{[{\bar{G}}^{(t)}]_{i, j}}{n_{μ}} = \sum_{μ = 1}^{c} \frac{x_{μ}^{T} {\bar{G}}^{(t)} x_{μ}}{x_{μ}^{T} x_{μ}} .$ (13) By assembling the eigenvectors u_μ into a matrix X = (x₁, x₂, . . . , x_c), Equation (13) can be rewritten in a matrix trace. $J_{c}^{(t)}$ can be written as

$\begin{matrix} J_{c}^{(t)} & = & tr {(X^{T} X)^{- 1} X^{T} {\bar{G}}^{(t)} X} \\ = & tr {(X^{T} X)^{- 1 / 2} X^{T} {\bar{G}}^{(t)} X (X^{T} X)^{- 1 / 2}} . \end{matrix}$ (14) The optimization problem can be simplified to $J_{c}^{(t)} = tr {Y^{T} {\bar{G}}^{(t)} Y}$ by the substitution Y = X (X^TX) ^-1/2, where matrix X^TX is diagonal. It can be observed that the vectors y_μ which are orthogonal to each other all have unit length. In terms of Y, we can rewrite the optimization problem as $max_{Y^{T} Y = I} tr {Y^{T} {\bar{G}}^{(t)} Y} .$ (15)

On the basis of Rayleigh-Ritz theorem [6, 7], we can calculate the maximum of this problem on condition that columns of Y are the right eigenvectors U = {u₁, . . . , u_c} according with the c largest eigenvalues of ${\bar{G}}^{(t)}$ . Then the strength of community μ at time t, $S_{μ}^{(t)}$ , is $S_{μ}^{(t)} \approx \frac{u_{μ}^{T} {\bar{G}}^{(t)} u_{μ}}{u_{μ}^{T} u_{μ}} = λ_{μ}^{t} \frac{u_{μ}^{T} u_{μ}}{u_{μ}^{T} u_{μ}} = λ_{μ}^{t} .$ (16) The robustness of μ-community state, $λ_{μ}^{t}$ , can be regarded as the strength of community μ at time t, since we sort the eigenvalues as λ₁ = 1 > |λ₂| ≥ |λ₃| ≥ . . . ≥ |λ_n|. Thus we can interpret the eigengap $λ_{μ - 1}^{t} - λ_{μ}^{t}$ as the “difficulty” that the μ-communities state transform into the (μ - 1)-communities state at time t. Then we can infer the most suitable community number at time t, Λ (t), from the location of largest eigengap, and we also can use this maximal value to measure the quality of states to find the most stable one. The formal definition of Λ (t) is $Λ (t) = \arg [\max_{μ} (λ_{μ - 1}^{t} - λ_{μ}^{t})] .$ (17) From a global perspective, Λ can be considered as the optimal number of communities, which is represented by Ψ, when it doesn’t change for maximum airtime.

5 Experiments

The proposed algorithm shows an excellent performance on both artificial benchmark networks and real-world data networks. In addition, it can be used to detect overlapping communities and corresponding correlation patterns. Results show the proposed algorithm obtains quite good results for all cases. Please refer to Supplementary materials for more details, for example, experiments on artificial networks and “Les Miserables” network [30].

The large scale scientific collaboration network. We apply our mode on large-scale scientific collaboration network (SCN) [23]. This real network contains 315,810 weighted edges, which illustrates the cooperation among 56,276 physicists according to their coauthored papers posted on arxiv . org.

First, according to the partition membership, we bundle the node with identical community membership together and exhibit a transformed adjacent matrix in Fig. 4(a), which illustrate a quite strong hierarchical structure. Specifically, among the total 793 communities, the size of the biggest community is 184, the size of the smallest community is 3, and the average size is 69. Moreover, 1,433 of 6,931 pairs of communities have fuzzy membership with each other, and the 5% communities with largest size account for 25.4% nodes while the other ones are relatively small. Furthermore, in Fig. 4(b), to visualize the community partition membership, we highlight four regions which include 10 overlapping nodes by four circles in a sub-network including eight communities, which is identical with the Refs. [6] and [23]. Experimental results on this large scale real-world networks have demonstrated that our method can successfully discover higher quality communities. From the efficiency validation, the proposed method exhibits good scalability and can efficiently handle networks with millions of edges.

Fig.4

(a) The transformed adjacent matrix which bundles the node with identical community membership together. (b) We pick up a small subnetwork for illustration, which contains 8 communities and 10 overlapping nodes. Different communities are highlighted with different shapes, and overlapping nodes found by our method are enclosed by circles.

Performance on more real world networks. Finally, we evaluate our model for more wildly used real-world data, which shown in Table 1. Seven wildly used networks are employed and there corresponding references are represented. For sake of comparison, the best published Modularity Q results are provided, which are obtained in the networks by the computation of a lot of partition methods. As can be seen in Table 1, the results are very close to the best published values after applying our algorithm, but at a small computational cost.

Table 1

This summary of results using our algorithm in real-world networks. For sake of comparison, the best published Modularity Q results are provided

Network	Ref.	Best	Source	Q of the
published	proposed
Q	model
Zachary Karate Club	[22]	0.420	[29]	0.416
US Football	[23]	0.606	[29]	0.602
Les Miserables	[24]	0.561	[29]	0.554
Jazz	[27]	0.446	[29]	0.439
PGP-key signing	[28]	0.878	[29]	0.883
Dolphin Social Network	[25]	0.531	[29]	0.527
Email	[26]	0.579	[29]	0.568

6 Conclusion

In this paper, we first transform the directed node graph to a new type directed line graph, and the direction and weight of line graph are defined. Then in the line graph, we define the community unit including membership and correlation information. There are two main contributions of this method. 1) To adequately characterize the community structure, the node and module correlation with different granularity can be calculated; 2) based on the membership and correlation information, we can extract the multiplex patterns between communities, according to different domain requirements. Furthermore, we are able to map the link community configuration to the optimal situation dynamically by maximizing the likelihood function with rigorous mathematical proof. Based on the spectral analysis of the Markovian transition matrix, a mathematical theory is provided to identify the optimum number of network communities, and to analyze the stability of the community structure. Extensive simulations using both synthetic and real-world benchmark networks are performed to verify the algorithmic performance.

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.

References

Fortunato

, Community detection in graphs, Physics Reports 486(3) (2010), 75–174.

Newman

M.E.J.

, Fast algorithm for detecting community structure in networks, Physical Review E 69(6) (2004), 066133.

Newman

M.E.J.

, Girvan

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

Guimera

, Nunes Amaral

L.A.

, Functional cartography of complex metabolic networks, Nature 433(7028) (2005), 895–900.

Duch

, Arenas

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

H.J.

, Wang

, Wu

L.Y.

, Zhang

X.S.

, Potts model based on a Markov process computation solves the community structure problem effectively, Physical Review E 86(1) (2012), 016109.

H.J.

, Zhang

X.S.

, Analysis of stability of community structure across multiple hierarchical levels, Europhysics Letters 103(5) (2013), 58002.

Hastings

M.B.

, Community detection as an inference problem, Physical Review E 74(3) (2006), 035102.

Hofman

J.M.

, Wiggins

C.H.

, Bayesian approach to network modularity, Physical Review Letters 100(25) (2008), 258701.

10.

Ronhovde

, Nussinov

, Local resolution-limit-free Potts model for community detection, Physical Review E 81(4) (2010), 046114.

11.

Blondel

V.D.

, Guillaume

, Lambiotte

, Lefebvre

, Fast unfolding of communities in large networks, Journal of Statistical Mechanics, Theory and Experiment 2008(10) (2008), 10008.

12.

Yang

, Liu

J.M.

, Liu

D.Y.

, Characterizing and extracting multiplex patterns in complex networks, IEEE Transactions on Systems, Man, and Cybernetics, Part B 42(2) (2012), 469–481.

13.

, Havens

T.C.

, Quadratic program-based modularity maximization for fuzzy community detection in social networks, IEEE Transactions on Fuzzy Systems 23(5) (2015), 1356–1371.

14.

Whang

, Gleich

J.D.

, Dhillon

, Overlapping community detection using neighborhood-inflated seed expansion, IEEE Transactions on Knowledge and Data Engineering 28(5) (2015), 1272–1284.

15.

Bhat

S.Y.

, Abulaish

, HOCTracker, Tracking the evolution of hierarchical and overlapping communities in dynamic social networks, IEEE Transactions on Knowledge and Data Engineering 27(4) (2015), 1019–1013.

16.

Evans

T.S.

, Lambiotte

, Line graphs, link partitions, and overlapping communities, Physical Review E 80(1) (2009), 016105.

17.

Evans

T.S.

, Lambiotte

, Line graphs of weighted networks for overlapping communities, European Physical Journal B 77(2) (2010), 265.

18.

Ahn

Y.Y.

, Bagrow

J.P.

, Lehmann

, Link communities reveal multiscale complexity in networks, Nature 466(7307) (2010), 761–764.

19.

, Liu

, Zhang

, Jin

, Yang

, Discovering link communities in complex networks by exploiting link dynamics, Journal of Statistical Mechanics: Theory and Experiment 2012(10) (2012), 10015.

20.

, Zhang

X.S.

, Wang

R.S.

, Liu

, Zhang

, Discovering link communities in complex networks by an integer programming model and a genetic algorithm,e, PloS One 8(12) (2013), 83739.

21.

, Jin

, Chen

, Zhang

, Identification of hybrid node and link communities in complex networks, Scientific Reports 5(8638) (2015), 1–14.

22.

Zachary

, An information flow model for conflict and fission in small groups, Journal of Anthropological Research (1977), 452–473.

23.

Girvan

, Newman

M.E.J.

, Community structure in social and biological networks, Proceedings of the National Academy of Sciences of the United States of America 99(12) (2002), 7821–7826.

24.

Knuth

D.E.

, The stanford graphBase: A platform for combinatorial computing, Reading, MA: Addison-Wesley Professional 37 (1993), 592.

25.

Lusseau

, Schneider

, Boisseau

O.J.

, Haase

, Slooten

, Dawson

S.M.

, The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations, Behavioral Ecology and Sociobiology 54(4) (2003), 396–405.

26.

Guimera

, Danon

, Diaz-Guilera

, Giralt

, Arenas

, Self-similar community structure in a network of human interactions, Physical Review E 68(6) (2003), 065103.

27.

Gleiser

, Danon

, List of edges of the network of jazz musicians, Advances in Complex Systems 6 (2003), 565.

28.

Boguna

, Pastor-Satorras

, Diaz-Guilera

, Arenas

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

29.

Agarwal

, Kempe

, Modularity-maximizing graph communities via mathematical programming, The European Physical Journal B 66(3) (2008), 409–418.

30.

Please download the Supplementary Material file from the website http://doc.aporc.org/wiki/Mapping