Spectral coarse graining for random walks in bipartite networks

DOI10.1063/1.4773823MaRDI QIDQ2944672zbMATH OpenOpenAlexWikidataFDO

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)

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

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 3514781 (Why is no real title available?)
• Collective dynamics of `small-world' networks
• Community structure in social and biological networks
• Complex networks: structure and dynamics
• Emergence of Scaling in Random Networks
• Networks. An introduction.
• Statistical mechanics of complex networks
• The Structure and Function of Complex Networks

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)