Spectral coarse graining for random walks in bipartite networks

DOI10.1063/1.4773823zbMATH Open1319.05122arXiv1209.1028OpenAlexW3105522936WikidataQ51235747 ScholiaQ51235747MaRDI QIDQ2944672FDOQ2944672

Authors: Yang Wang, An Zeng, Zengru Di, Ying Fan 

Publication date: 2 September 2015

Published in: Chaos: An Interdisciplinary Journal of Nonlinear Science (Search for Journal in Brave)

Abstract: Many real-world networks display a natural bipartite structure, while analyzing or visualizing large bipartite networks is one of the most challenges. As a result, it is necessary to reduce the complexity of large bipartite systems and preserve the functionality at the same time. We observe, however, the existing coarse graining methods for binary networks fail to work in the bipartite networks. In this paper, we use the spectral analysis to design a coarse graining scheme specifically for bipartite networks and keep their random walk properties unchanged. Numerical analysis on artificial and real-world bipartite networks indicates that our coarse graining scheme could obtain much smaller networks from large ones, keeping most of the relevant spectral properties. Finally, we further validate the coarse graining method by directly comparing the mean first passage time between the original network and the reduced one.

Full work available at URL: https://arxiv.org/abs/1209.1028

Recommendations

• A spectral method for bipartizing a network and detecting a large anti-community
• Spectral coarse grained controllability of complex networks
• Bipartite structure of all complex networks
• Exploiting the structure of bipartite graphs for algebraic and spectral graph theory applications
• Discovering bipartite substructure in directed networks

Mathematics Subject Classification ID

Applications of graph theory (05C90) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random walks on graphs (05C81)

Cites Work

• Statistical mechanics of complex networks
• Complex networks: structure and dynamics
• Emergence of Scaling in Random Networks
• The Structure and Function of Complex Networks
• Community structure in social and biological networks
• Collective dynamics of `small-world' networks
• Networks. An introduction.
• Title not available (Why is that?)

Cited In (2)

• Spectral coarse graining of complex clustered networks
• Identifying missing and spurious connections via the bi-directional diffusion on bipartite networks

This page was built for publication: Spectral coarse graining for random walks in bipartite networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2944672)