Abstract
Detecting communities in complex networks is an important problem. Spectral method has been successfully used to solve data clustering and community detection problems. However getting the proper eigenvectors is usually difficult and depends on extra thresholds. In this paper, we devise an effective method to choose suitable eigenvectors. The method needs no extra thresholds and can get the reasonable communities in the network. Furthermore we can identify the overlapping communities in complex networks by clustering the chosen eigenvectors with fuzzy c-means algorithm. Experimental results show that the algorithm is effective in detecting communities.
Introduction
The complex network is a hot topic due to its wide applications. Complex network may be used to represent relationships among collection of objects. Many kinds of network, such as the World Wide Web [1] , transportation network [2] , social network [3] , citation and co-authorship network [4] can be regarded as complex networks. Complex networks have been studied for their mathematical properties and as a tool for modeling and optimization [5] [6] [7] . Several important properties, such as the scale-free property [8] , community structure [27] and the small world property [9] , have been found and exploited.
Detecting communities, also called module, in complex network is an interesting problem. Although a number of algorithms for identifying the communities have been developed in various fields [10, 11] . There are two challenges in detecting community structure. The first is how to figure out the number of communities in a given network. The second is about overlapping community structure, which means some nodes in a network may belong to different communities. Overlapping nodes may play a special role in a complex network system and identifying overlapping communities is key problem for some cases. The existing algorithms such as divisive algorithm [12] [13] [14] [15] [16] do not solve the problem. In this paper, we devise a spectral based method to solve the problem.
Spectral methods are widely used in community detection for complex networks [18, 23, 26] . But they all use the first K eigenvectors to cluster for getting the communities, which can not get the ideal clustering result and the computational cost is prohibitive expensive. In this paper, we devised an effective and efficient algorithm to choose eigenvectors. Based on spectral methods, we can both detect the reasonable number of communities in the network and solve the overlapping community problem with the fuzzy c-means algorithm. The rest of the paper is organized as follows: In Section 2, we describe spectral based Eigenvector selection method and its associated algorithm. In Section 3, we do experimental study with real-world networks and present an analysis on algorithm's performance. The conclusion and discussion is presented in Section 4.
Eigenvector Selection Method and Its Algorithm

Affinity Matrix
Affinity matrix is widely used in community detection, and different matrix can get different networks' partition, i.e. cluster or community. In this paper we give a new definition of the matrix:
where A is adjacency matrix of the network, and N i ∩ N j denotes the number of neighbors that both node i and node j share. d i is the degree of the node.
Spectral Method
Given a complex network and its affinity matrix W , and a diagonal matrix
. By using another Laplacian matrix L = D − W . So the problem is turned out to be how to choose the eigenvectors.
Different from the formula proposed in [19] , we develop a new formula for eigenvector sorting. The formula is as follows:
where max k and min k denote the maximum and minimum of the k th eigenvector respectively. V is the matrix constructed by the eigenvectors of the Laplacian matrix. Another affinity matrix is built as:
From the formula it is clear that the scope of S ij is 0 ≤ S ij ≤ 1. Entropy is defined in terms of probabilities, and we find that it is not a monotonic function. So we should improve it to represent the probability. So entropy is always expressed as E = −P i log P i , we need a monotonic one with the variable of P i :
To construct a monotonic increasing function, let S ij divides constant e, e is a natural constant, whose value is about 2.71828. S ij is replaced by S ij , where
Then we give the sum eigenvector entropy of each eigenvector:
E k is the sum entropy from the above formula of the k th eigenvector. Then we can get different entropy values. Sorting the value and choose the suitable eigenvectors to cluster from the sorting result. A graceful result derived is that we choose all the values below 1, and then we get the best result. Experimental result will show it in the next section.
Eigenvalue Gap of the Laplacian Matrix
Much research work has proved that the gap of the sorting eigenvalues means the reasonable number of clusters, or communities. In this paper, we get the sorting descending eigenvalue from the matrix, and then compute the distance between the two adjacent eigenvalues. Sorting the eigenvalues as
, then we can get the biggest value G n , and n is the number of clusters or communities.
Main Thinking of the Algorithm
Given a adjacent matrix A = (a ij ) n×n and λ. The main thinking of the algorithm is stated as follows:
Computing the affinity S, and the diagonal matrix
Building a Laplacian matrix L = D − S, calculating the eigenvector and eigenvalue of the matrix. Through the eigenvector selection algorithm we choose the eigenvectors to form a new dataset, and use fuzzy c-means algorithm to cluster it. From the gap of eigenvalues, we can easily get the reasonable number of the communities. With the threshold of λ, we can easily get overlapping communities and get the detected communities.
Experimental Study

The Advantage of Eigenvector Choosing
Different choices of eigenvectors can get different results [20] . So it is important to pay attention to the choice of eigenvector. To get a better cluster result, we do some research on the selection of eigenvectors. Comparing with the existing approaches our method shows a better result.
Where the ideal result happens is that the number of the eigenvectors we choose to get the biggest value Q [17] has some relationship with the entropy value, we discovery that the eigenvectors we choose are easily to get high value Q. What's more, we find that the collection of the eigenvector entropy under 1 is the best choice for clustering. From the Fig. 1 and Fig. 2 we can find that 9 eigenvectors we choose by our method can get the maximum value Q, while the common method should select 10. In some degree, the method can reduce the computational complexity. From the Fig. 3 we can find that the eigenvectors we choose have lower entropy value, and from the Fig. 4 we can easily get the biggest value. In the example, the number with biggest is the number of the communities in the network. 
The Result of Real Network by Using Our Algorithm
In this section, we do the experiment in three real network, Zachary's karate club, Dolphins network and Network of American college football teams [18, [20] [21] [22] .
The network of Zachary's karate club consists of 34 members of a karate club as nodes and 78 edges representing friendship between members of the club which was observed over a period of two years. Due to a disagreement between the club's administrator and the club's instructor, the club split into two smaller ones. We get two communities by our methods, which are shown in Fig. 5 . The second example we discuss is the network studied by the biologist Lusseau who divided a set of dolphins into two groups according to their age. We get two followed communities by our methods which are shown in Fig. 6 .
The third real-world network we have investigated is the college football network that represents the game schedule of the 2000 season of Division I of the US college football league. The nodes in the network represent the 115 teams, while the links represent 616 games played in the year. The natural community structure in the network makes it a commonly used benchmark for evaluation of community-detecting methods. Fig. 5 shows the 12 communities identified by our algorithm. From the figure, we can see that our algorithm works well on this benchmark data (see Fig. 7 ). 
Overlapping Community Detection in the Real Network
We use fuzzy c-means to cluster the eigenvector chosen. Different threshold value can get different overlapping community in the given network. We test the algorithm in two real networks: Zachary's karate club and Dolphins network. The result is presented as follows:
We set the threshold λ at 0.1, we know that the node 3, 9, 10 are overlapping fuzzy nodes in the network of Zachary's karate club (see Fig. 8 ).
We set the threshold λ at 0.15, we know that the node 8, 20, 31, 40 are overlapping fuzzy nodes in the network of Dolphins network (see Fig. 9 ).
Precision Comparison
In this subsection, we make a comparison of different algorithm in the detection of the network of American college football teams. We compare the precision of result obtained by our method with the one detected by some well-known approaches, such as GN [24] algorithm, MID method [25] , FCM algorithm [23] , ISM (Improved Spectral Method) [18] and MSLM [18] . The conclusion is that the precision of result detected by our method is the highest one, and with the biggest value of modularity Q (see Table 1 ). 
Conclusions
In this paper, we devised a novel method of eigenvector selection with spectral methods. We test the algorithm in three real networks. Unlike the existing spectral approaches, our method is not based on iterative bisection. By using the proposed affinity matrix, the algorithm can get the clustering nodes. We compare the test results with other comparable algorithms. The result shows our method can obtain ideal accuracy.

{'paper_id': '18097032', 'title': 'Spectral Based Eigenvector Selection Method for Community Detection', 's2_url': 'https://api.semanticscholar.org/CorpusID:18097032', 'source': 'S2ORC'}