### Abstract

Many real-world networks display a natural bipartite structure, yet analyzing and visualizing large bipartite networks is one of the open challenges in complex network research. A practical approach to this problem would be to reduce the complexity of the bipartite system while at the same time preserve its functionality. However, we find that existing coarse graining methods for monopartite networks usually fail for bipartite networks. In this paper, we use spectral analysis to design a coarse graining scheme specific for bipartite networks, which keeps their random walk properties unchanged. Numerical analysis on both artificial and real-world networks indicates that our coarse graining can better preserve most of the relevant spectral properties of the network. We validate our coarse graining method by directly comparing the mean first passage time of the walker in the original network and the reduced one.

Bipartite networks are naturally suited to understanding and modeling many real systems. However, when the network contains a very large number of nodes, it becomes practically impossible to deal with dynamical processes on it. A promising way to address this problem is to coarse grain the network, namely, to reduce the networks' complexity by mapping the large network into a smaller one while keeping its dynamical properties unchanged. Unlike monopartite networks which only contain one kind of nodes, bipartite networks consist of two distinct sets of nodes, such that links cannot exist between nodes in the same set. The dynamics on both types of nodes should be preserved in coarse graining. Additionally, the coarse graining should preserve the bipartite structure of the network. However, existing coarse graining methods for monopartite networks cannot achieve these two objectives. In this paper, we propose a spectral coarse graining method to preserve the random walkproperties for bipartite networks. By introducing for each set of nodes a stochastic matrix, our method treats the two different kinds of nodes separately. As a result, the reduced networks remain bipartite. Both artificial and real bipartite networks are considered, and we find that the reduced networks have very similar spectral properties to the original ones. We validate our method by comparing the mean first passage time in the original and reduced networks. Our method can be easily extended to preserve many other spectral-determined dynamical properties in bipartite networks.

This work was supported by the NSFC under Grant Nos. 61174150, 70771011, and 60974084, NCET-09-0228, and fundamental research funds for the Central Universities of Beijing Normal University. Y.W. thanks the China Scholarship Council (CSC) for support.

I. INTRODUCTION

II. SPECTRAL COARSE GRAINING METHOD ON BIPARTITE NETWORKS

A. Random walks on monopartite networks

B. Random walks on bipartite networks

C. Spectral coarse graining method for bipartite networks

III. RESULTS

A. Artificial networks

B. Real-world bipartite networks

IV. CONCLUSION

### Key Topics

- Eigenvalues
- 57.0
- Random walks
- 27.0
- Networks
- 14.0
- Spectral properties
- 9.0
- Cluster analysis
- 4.0

## Figures

The top figure is a social bipartite network of terrorists with . Nodes' size is proportional to their degree. The two different colors represent the two kinds of vertices. The blue squares stand for people and the red circles represent the organizations. The bottom figure is the coarse-grained network from the BSCG method with . Nodes' size is proportional to its strength in this weighted network.

The top figure is a social bipartite network of terrorists with . Nodes' size is proportional to their degree. The two different colors represent the two kinds of vertices. The blue squares stand for people and the red circles represent the organizations. The bottom figure is the coarse-grained network from the BSCG method with . Nodes' size is proportional to its strength in this weighted network.

The evolution of the three largest nontrivial eigenvalues , , and as a function of the size of the coarse-grained network. (a)–(c) The original network is movielens network. (d)–(f) The original network is Netflix network. Red circles correspond to the random coarse graining method, the green line is the community detection method, and the blue squares represent the BSCG method.

The evolution of the three largest nontrivial eigenvalues , , and as a function of the size of the coarse-grained network. (a)–(c) The original network is movielens network. (d)–(f) The original network is Netflix network. Red circles correspond to the random coarse graining method, the green line is the community detection method, and the blue squares represent the BSCG method.

Comparison of the MFPT. The walker starts at each node in the top set and the sink *i* is selected as the node with the strongest weight in the bottom set. The blue circles represent the average MFPT ranked for each group in the original network. The MFPT of the corresponding nodes in the coarse-grained network is displayed with red lines. (a) Nodes merged by BSCG method in Movielens network. (b) Nodes merged randomly in Movielens network. (c) Nodes merged based on community detection method in Movielens network. (d) Nodes merged by BSCG method in Netflix network. (e) Nodes merged randomly in Netflix network. (f) Nodes merged based on community detection method in Netflix network. Insets: Comparison of the exact MFPT between original and the reduced bipartite network. Slope 1 represents the well preserved MFPT in the reduced network.

Comparison of the MFPT. The walker starts at each node in the top set and the sink *i* is selected as the node with the strongest weight in the bottom set. The blue circles represent the average MFPT ranked for each group in the original network. The MFPT of the corresponding nodes in the coarse-grained network is displayed with red lines. (a) Nodes merged by BSCG method in Movielens network. (b) Nodes merged randomly in Movielens network. (c) Nodes merged based on community detection method in Movielens network. (d) Nodes merged by BSCG method in Netflix network. (e) Nodes merged randomly in Netflix network. (f) Nodes merged based on community detection method in Netflix network. Insets: Comparison of the exact MFPT between original and the reduced bipartite network. Slope 1 represents the well preserved MFPT in the reduced network.

## Tables

The three largest nontrivial eigenvalues of in the artificial networks including the bipartite network with community structure and the ER bipartite network. and are the eigenvalues before and after coarse graining, respectively.

The three largest nontrivial eigenvalues of in the artificial networks including the bipartite network with community structure and the ER bipartite network. and are the eigenvalues before and after coarse graining, respectively.

The three largest nontrivial eigenvalues of in real-world bipartite networks including a small terrorists' social network, movielens network, and Netflix network. and are, respectively, the eigenvalues before and after coarse graining.

The three largest nontrivial eigenvalues of in real-world bipartite networks including a small terrorists' social network, movielens network, and Netflix network. and are, respectively, the eigenvalues before and after coarse graining.

Article metrics loading...

Full text loading...

Commenting has been disabled for this content