{'fraction_non_alphanumeric': 0.03910190599473285, 'fraction_numerical': 0.019640226755345266, 'mean_word_length': 4.402459609356161, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Recognizing number of communities and detecting community structures in complex networks

Recognizing number of communities and detecting community structures of complex network are discussed in this paper. As a visual and feasible algorithm, block model has been successfully applied to detect community structures in complex network. In order to measure the quality of the block model, we first define an objective function WQ value. For obtaining block model B of a network, GSA algorithm is applied to optimize WQ with the help of random keys. After executing processes AO (Adding Ones) and RO (Removing Ones) on block model B, the number of communities of a network can be recognized distinctly. Furthermore, based on the advantage of block model that its sort order of nodes is in correspondence with sort order of communities, so a new fuzzy boundary algorithm for detecting community structures is proposed and successfully applied to some representative networks. Finally, experimental results demonstrate the feasibility of the proposed algorithm.


Introduction
In recent years, detecting community structure in complex networks has attracted a growing attention of many researchers [1,2]. Community structures widely exist in many networked systems including friendship networks [1], coauthor networks, protein-protein interaction network [3,4], mobile phone networks [5], WWW networks [6], transportation networks [7], online shopping networks, animal relationship networks, etc. However, it is very difficult to provide an accurate and recognized definition for community structure, due to its idiosyncratic middle scale property and the complexity and heterogeneity of these real networks in our society [8]. It is generally thought that community structures are subgroups of a network with dense internal links and sparse external links. As one of the most important tasks in complex networks researches, detecting community structure can be utilized for researching network topological structure, determining cause of group formation [9], understanding network underlying laws [2,10], learning network functions [11,12] and discovering group evolution [12], etc.
A great deal of novel approaches and technologies have been proposed successfully to discover communities in complex networks. Among these existing methods, after the measurement of algorithms modularity was introduced by Newman and Girvan [13]modularity optimization methods emerged with a large number in a brief period [1,4,14,15]. These methods include greedy optimization [16]hierarchical clustering [17], extremal optimization [18], spectral algorithm [19,20], intelligent algorithm [21][22][23], mathematical programming [24][25][26] and so on. However, modularity optimization methods are NP-complete problem and modularity has the resolution limit problem due to its definition and selection of null model. So many researchers improved and extended modularity through great efforts, and some new algorithm measurements were also proposed such as partition density [27], normalized mutual information (NMI) [28], modularity density [29], local modularity [30], linked matrix factorization [31]. For some other algorithms, such as core nodes based methods [28,32,33], k-means methods [4,[34][35][36]k-rank methods [37], hierarchical clustering methods [4] and spectral clustering [2] for more communities, they can obtain satisfactory community structures, but they are bound by the priori knowledge of the number of communities or a related threshold value [1,9,11,33,37]. Identifying gaps between the eigenvalues of Laplacian matrix [4] of a network or Clumpiness matrix [2] was often applied to estimate the number of communities. For networks with indistinct community boundaries and mixed communities, there are not distinct gaps between the eigenvalues of their Laplacian matrixes or Clumpiness matrixes. In order to detect communities precisely, Wei Tang et al. proposed a block model approximation algorithm called Linked Matrix Factorization Algorithm [31]. This algorithm needs a block indicator matrix S that is costly obtained by calculating top k eigenvectors of network adjacency matrix with maximum eigenvalues.
Considering that complex calculation of eigenvectors of matrices exists in the current block model approximation algorithms, a novel measurement WQ of block model is proposed according to the property that most elements with a value of one are around the leading diagonal in block model. Furthermore, GSA [38,39] and Random Keys algorithms [40] are employed to optimize objective function WQ value in order to obtain the block model of complex network. For some algorithms are bound by the number of communities, a method to recognize number of communities is proposed using strong block of the network. The proposed processes AO and RO are executed on block model and a strong block is obtained, then the number of communities can be counted artificially from strong block model. In order to detect communities in complex networks, a novel fuzzy boundary algorithm is proposed according to the advantage that the order of rows and columns of block model B corresponds with the order of communities. Experimental results demonstrate the feasibility of the proposed algorithm.

Preliminaries and definitions
A connected network with no node strength, link weight and direction is denoted as G = (V, E), where V and E are the set of nodes and links, respectively. |V | = n is the number of nodes and |E| = m is the number of links of network G. The network G can also be represented by its adjacency matrix A, in which elements represent connections of network nodes. When a link between nodes v i and v j exists, then a i,j = 1 and a i,j = 0 otherwise. The degree of node v i is denoted as k i and k i = i a i,j . Let G i (V i , E i ) represents a sub-network of a partition of G, i.e., a community of network G.

Definition
Definition 1. W Q value. We take adjacency matrix A of network G as a table ∆ with n 2 cells and the size of each cell is 1. Element a i,j is a cell of ∆. If a i,j =1, the element is called as 1-element. Then the distance between cell a i,j and leading diagonal of matrix A is . So the W Q value of network G is defined as the sum of all distances from 1-elements to main diagonal divided by 2 √ 2n(2n − 1).
Clearly, W Q ∈ (0, 1). In the following we will verify that less W Q value corresponds more distinct blocks and two isomorphic networks may have different W Q values. Definition 2. Airtightness Value. Suppose the cell of element a i,j has r neighbor cells, then the airtightness value of element in a i,j is defined as Clearly, H A i,j ∈ (0, 1) and the larger the airtightness value, the tighter the network structure. Definition 3. Block. For a network G and its adjacency matrix A, we can get its isomorphic network G ′ and corresponding adjacency matrix A ′ by renumbered all nodes of G. And we can obtain A ′ by swapping two rows and corresponding two columns of adjacency matrix A repeatedly. So the main idea of model approximation algorithm can be visualized in Fig.1, where Fig.1(a) is heat map of adjacency matrix A and Fig.1(b) represents A ′ which is called block structure or block model denoted as B. Then the block B i,j (i < j) of block model B in this paper is defined as Clearly, a block of network G is a sub-matrix of its block model B and the sub-matrix is symmetric around the leading diagonal of B.
One block in B is a community.
In this paper, if all blocks of a block model B satisfy equation (4), then B is a d-Strong block model and denoted as d − B in this paper.

Gravitational Search Algorithm (GSA)
Inspired by the law of gravity, a novel heuristic optimization algorithm, namely Gravitational Search Algorithm (GSA) was proposed [38]. It has been proved that GSA is superior to some existing intelligent algorithms including real genetic algorithm, particle swarm optimization and central force optimization. GSA has five main steps which are as follows: Step 1: Initialize Agents. Randomly initialize the positions of N agents as where x k i is the position of the ith agent in the kth dimension and h is the dimension of an agent.
Step 2: Determine the best and worst fitness of agents. For minimization problems, the best (denoted as best(t)) and worst (denoted as worst(t)) fitness for all agents at the tth iteration are where f it j (t) is the fitness value (object function value) of the jth agent at the tth iteration.
Step 3: Calculate and update attribute values of agents.
(1) Gravitational constant Ψ. Gravitational constant Ψ is a function of iteration t and defined as where Ψ 0 is the initial value of gravitational constant, T is the number of iterations and α is a free parameter. According to experiments and analysis in reference [38], we set Ψ 0 = 100 and α = 20 in this paper.
(2) Masses of the agents. At the tth iteration, gravitational and inertia masses of agents can be updated by the followings where M a,i (t) is the active gravitational mass and M p,i (t) is the passive gravitational mass related to the ith agent. M i,i (t) represents inertial mass of the ith agent.
(3) Acceleration. At the tth iteration, the force acting on the ith agent from the jth agent at the kth dimension is where R i,j (t) is the Euclidian distance between X i and X j , power is a positive integer, ε is a very small constant. Here we set power = 1, ε = eps. eps is machine zero in the tool of MATLAB. Then the resultant force of the ith agent exerted from other agents at the kth dimension is where rand j is a random variable in the interval [0,1]. So the acceleration of the ith agent at the kth dimension is Step 4: Calculate and update positions and velocities of agents. After executing the above procedures, the velocities and positions of agents at the (t + 1)th iteration can be updated by the following equations where rand i is a uniform random variable in the interval [0,1], u k i (t) and x k i (t) are the velocity and position of the ith agents in the kth dimension at the tth iteration, respectively. We set u k i (1) = 0 for i = 1, 2, . . . , N , k = 1, 2, . . . , h.

Recognizing number of communities
For many community detection algorithms such as partitional clustering methods [4], the number of communities should be given in advance and is often imposed as stopping conditions of algorithms. Identifying gaps between eigenvalues of Laplacian matrix of a network was often applied to estimate the number of communities. However, for networks with indistinct community boundaries and mixed communities, there are not distinct gaps between their Laplacian matrixes or Clumpiness matrixes eigenvalues. So we creatively utilize GSA algorithm to optimize the proposed W Q value and eventually obtain network block model, then the number of communities (that is strong or weak blocks) can be recognized readily. In order to obtain network block model B, GSA algorithm is employed to search the best sort order of nodes by swapping two rows and corresponding two columns of adjacency matrix A for each circulation. As we all know, A and B have the same eigenvalues and eigenvectors. So we can approximate network adjacency matrix A as A ≈ P BP T , where P corresponds to the top k eigenvectors of A with maximum eigenvalues.
In order to apply GSA to develop the block models of a complex network, there are three problems should be resolved primarily. Firstly, for the problem of initializing agents in GSA, 50 agents are initialized as . . x n i for i = 1, 2, . . . , 50, where n is the number of nodes, x k i is a random integer, x k i ∈ {1, 2, . . . , n} and x k i = x s i for k = s. Secondly, for calculating the fitness value in Step 2 of GSA, the WQ value is utilized as the target function of minimization problem in the optimization model. Thirdly, the best agent we want to obtain is a permutation of integers, but the position of agents may be non-integer after updated in Step 4 of GSA. So the random keys [40,41] is applied to deal with this problem. As an example of the idea of random keys, suppose x = 0.5, 1. In order to recognize blocks more clearly, a two-steps strategy is proposed including Adding Ones (AO) and Removing Ones (RO). AO is executed by assigning element a i,j and all its neighbor cells to one when H A i,j is greater than a threshold value d 1 ∈ (0, 1). Whereas RO is executed by assigning element a i,j and all its neighbor cells to zero when H A i,j is less than a threshold value d 2 ∈ (0, 1). Then a block model with d-Strong blocks can be obtained eventually.
Moreover, according to the special structure of block model, we calculate the number of 1-elements along each diagonal (line) which parallel to minor diagonal (including minor diagonal). For a n × n block model B, there are 2n − 2 diagonals parallel to its minor diagonal and the first one is at the top left of B, the last one at the bottom right. So the value range of X-axis is [1, 2n − 1], and the (2k − 1)th line passes through the element b k,k , we can use this rule to calculate the label of a node according to the label of parallel diagonal.
In this paper, hierarchical communities, overlapping communities and nonoverlapping communities are considered in un-weighted and undirected connected networks. Figs.2-4 are block models of three typical networks obtained by GSA algorithm. The RB125 network shown in Fig.2 is a popular synthetic hierarchical and scale-free network [4] and it has 25 little communities or 5 large communities. The proposed three-star network shown in Fig.3 has 27 nodes and can be divided into three communities. The networks G # with overlapping communities in Fig.4 and non-overlapping communities in Figs.1 are GN benchmark networks, which have 128 nodes and four communities. Clearly, in Fig.2(c), the block model of RB125 has 25 blocks or communities. In Fig.2(b) and Fig.3(b), there are five "cross" in block model of RB125 and three "cross" in block model of three-star network. As a matter of fact, the cross represents community. So we can conclude that RB125 has five communities and the three-star network has three communities. For GN benchmark networks in Fig.4, the block model has four blocks with two pairs of overlapping blocks. So the network has four communities and two overlapping communities in Fig.4.   [1,255]. There are four small-scale peaks on two large-scale peaks, and it was caused by two overlapping communities. So we can consider this network has two large communities or four little communities with two overlapping communities.

Detecting community structures
From the above discussion, we can obtain the block model of a network by the GSA algorithm with the optimal WQ value proposed in this paper. Then the communities can be detected by many existing algorithms such as k-means [4,[34][35][36], and hierarchical clustering [4]. Moreover, these algorithms need to calculate node similarities and even some similarity indices which cost vast time. So we present a novel fuzzy boundary algorithm that can directly process the block model and utilize the proposed fuzzy boundary to detect community structures.
A block model has a corking advantage that its sort order of nodes or rows and columns is in correspondence with the sort order of communities, for example, the first 5 nodes belong to the first community in Fig.2. So the communities can be discovered by detecting boundaries between blocks. We can clearly see that it is hard to observe the distinct boundary between blocks in Fig.2(c), because of the attribution of some nodes could not be decided by our eyeballing. So the set of nodes in a gap between two strong blocks is defined as their fuzzy boundary denoted as F b . For a strong block model B of a network, we renumbered all nodes and blocks by their sequence from left to right in the block model. So all nodes from left to right are v 1 , v 2 , v 3 , · · ·, v n and all blocks are B 1 , B 2 , B 3 ,· · ·, B k which correspond to communities G 1 , G 2 , G 3 , · · ·, G k . For ∀v l ∈ F b , ∃B i , B i+1 , and for ∀v p ∈ B i and ∀v q ∈ B i+1 we can obtain p ≤ l ≤ q.
After obtaining all F b , the rest blocks which are separated by F b compose initial community structures {G 1 , G 2 , . . . , G k }, where k is the number of blocks. In order to distribute nodes in F b , the similarity between a node and blocks (communities) is defined as the number of links between them. Moreover, the nodes in F b belong to the adjacent block which has the greatest similarity with them, and the nodes with identical similarity are overlapping nodes. After each circulation of distributing nodes in F b , all similarities of remaining nodes should be updated until F b is empty or all nodes in F b are overlapping nodes. We call this strategy of detecting communities as fuzzy boundary algorithm and it can be described as follows: Input: Network G = (V, E) Output: Communities {G 1 , G 2 , . . . , G k } Step 1: Use GSA algorithm to optimize the WQ value of adjacency matrix A to get block model B.
Step 2: Obtain d-Strong block model d-B by applying AO and RO to B.
Step 5: Distribute nodes in F b to the adjacent communities and update {G 1 , G 2 , . . . , G k } and F b .
Step 6: Repeat steps from Step 4 to Step 6 until F b = ∅.
Step 7: Calculate similarities between nodes and communities, adjust misallocated nodes.

Experimental results
The fuzzy boundary algorithm is applied to two representative networks including Football team network [42] and pol-blog network [6], and experimental results are compared with some existing methods by modularity Q and NMI. Experimental results are shown in Figs.5-7. The Football team network contains 115 nodes and 613 edges, nodes are college football teams and edges are competition schedule of teams, and it has 12 communities originally. The pol-blog network, with 1490 nodes and 19090 links, represents a set of web-blogs of US politics. This network primitively has two communities including conservative and liberal, and its maximal connected network with 1222 nodes and 16714 links is discussed in this paper.
On Football team network, the block model B has 11 blocks shown in Fig.5, then 11 communities are discovered with WQ=0.1420 which is less than WQ= 0.4271 of original adjacency matrix A. After executing AO with d=0.9 and RO with d=0.6, block model 0.6-B is obtained, and its corresponding communities are detected and shown in Fig.6. The optimal modularity Q=0.5621 and NMI=0.9043. Modularity of initial communities is Q = 0.5540. This network is also discussed in [14], and its optimal modularity is Q = 0.546 and NMI=0.6838 with 6 communities. In [43]their optimal modularity is Q=0.6005 and NMI=0.9095 with 11 communities.
From Fig.6, the proposed fuzzy boundary algorithm can successfully detect communities G 1 , G 2 , G 3 , G 4 , G 5 , G 6 and G 9 of original communities. Community G 7 is divided into two communities, and nodes of communities G 11 and G 12 are distributed to other communities. In football team network, the initial 12 communities are obtained by football teams from different geographical location, and their links represent schedule of competition between teams. So in initial community structures, several nodes such as v 29 , v 37 and v 111 may have more intercommunity links than intra-community links. Then experimental results may have some distinctions compared with initial community structure. In general, the fuzzy boundary algorithm is feasible.
Two communities are detected from pol-blog network shown in Fig.7, and the optimal WQ value is 0.5803 which is less than 0.6804 of original adjacency matrix A. After executing AO with d=0.2 and RO with d=0.9, 0.9-Strong block model 0.9-B is obtained. Because there are two communities in pol-blog network, the labels of nodes in F b correspond to the labels of parallel lines from 1292th to 1450th, then F b can be obtained by transforming parallel line label to node label. Eventually, we get two communities with modularity Q=0.4052. This network was also discussed in [1] and [44], their optimal modularity are Q=0.424236 and Q=0.4176, respectively. Actually, it can be found from Fig.7(a) that two blocks exist in the heat map of original adjacency matrix, so experimental results of the proposed fuzzy boundary algorithm are reasonable.   [1,229]. There are 11 nonoverlapping peaks and it means 11 non-overlapping communities. According to gaps between peaks, F b can be obtained. Community structure of football team network detected by the proposed fuzzy boundary algorithm. 11 communities are detected with WQ=0.1420, modularity Q=0.5514 and NMI=0.8827.Nodes of the same color originally belong to the same community.

Conclusion
In this paper, in order to measure the quality of block model, we first define an objective function WQ value. For obtaining block model B of a network, GSA algorithm is applied to optimize WQ with the help of random keys. After executing AO and RO on block model B, the number of communities of a network can be recognized distinctly. Furthermore, based on the advantage of block model that its sort order of nodes or rows and columns is in correspondence with sort order of communities, an algorithm for detecting community structures called Fuzzy Boundary is proposed and successfully applied to some representative networks. Finally, experimental results demonstrate the feasibility of our algorithm. There are some rooms need to improve in the future. Firstly, the threshold value d in AO and RO needs an in-depth study, for example, AO may merge some block together with too small threshold and RO may break a block into more with too large threshold. Secondly, for some large-scale network, GSA has high time-complexity and the problem of trapping in local optimum. So the experimental results in this paper may not be optimal division but feasible. Thirdly, if the number of nodes in F b is overmuch, cohesiveness of existing communities might be weakened. Whats more, other similarity indices between nodes and communities can be applied to distribute nodes in F b . Finally, we hope the algorithm presented here can be expanded to other types of networks, such as weighted network, directed network, bipartite network and dynamic network. We hope such improvements and more applications of the proposed algorithm in the future.