Uncovering fuzzy community structure in complex networks

There has been an increasing interest in properties of complex networks, such as small-world property, power-law degree distribution, and network transitivity which seem to be common to many real world networks. In this study, a useful community detection method based on non-negative matrix factorization (NMF) technique is presented. Based on a popular modular function, a proper feature matrix from diffusion kernel and NMF algorithm, the presented method can detect an appropriate number of fuzzy communities in which a node may belong to more than one community. The distinguished characteristic of the method is its capability of quantifying how much a node belongs to a community. The quantification provides an absolute membership degree for each node to each community which can be employed to uncover fuzzy community structure. The computational results of the method on artificial and real networks confirm its ability.

Figure 1

(Color online) A toy network with one unstable node (6) and one overlapping node (11) and its corresponding $W$ entries. The three curves (circle, square, and triangle) represent the corresponding values of every node in every column of $W$.

Figure 2

Test of the method on computer-generated networks with known community structure and comparison with the GN algorithm and the spectral algorithm. It is a plot of the fraction of nodes correctly classified in computer-generated networks with respect to ${\overline{z}}_{out}$. Each point is an average over 100 realizations of the networks.

Figure 3

(Color online) The fuzzy community structure of the karate club network detected by the proposed method.

Figure 4

The sorted $S$ values for the karate club network. The inline small figure is plotted with larger $S$ bound.

Figure 5

$Q$ values vs $k$ of our method for scientific collaboration network.

Figure 6

(Color online) The fuzzy community structure of scientific collaboration network obtained by our method.

Figure 7

The sorted $S$ values for scientific collaboration network.

Figure 8

(Color online) Three fuzzy modules (module-specific nodes are denoted by different shapes) have been shown with three overlapping proteins YAR044W, YAR042W and YPR041W (labeled in circles).