Bipartite Graphs as Models of Complex Networks

Abstract

It appeared recently that the classical random graph model used to represent real-world complex networks does not capture their main properties. Since then, various attempts have been made to provide accurate models. We study here a model which achieves the following challenges: it produces graphs which have the three main wanted properties (clustering, degree distribution, average distance), it is based on some real-world observations, and it is sufficiently simple to make it possible to prove its main properties. This model consists in sampling a random bipartite graph with prescribed degree distribution. Indeed, we show that any complex network may be viewed as a bipartite graph with some specific characteristics, and that its main properties may be viewed as consequences of this underlying structure. We also propose a growing model based on this observation.

References in corpus (10)

• The structure and function of complex networks
• Cascade-based attacks on complex networks
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• On the uniform generation of random graphs with prescribed degree sequences
• Epidemic spreading in complex networks with degree correlations
• Tuning clustering in random networks with arbitrary degree distributions
• Rate equation approach for correlations in growing network models
• Metric structure of random networks
• Competition and adaptation in an Internet evolution model
• Evolving Scale-Free Network Model with Tunable Clustering

Cited by in corpus (44)

• Networks beyond pairwise interactions: structure and dynamics
• Complex network approaches to nonlinear time series analysis
• Public transport networks: empirical analysis and modeling
• Clique Graphs and Overlapping Communities
• Empirical analysis of web-based user-object bipartite networks
• Bond percolation on a class of clustered random networks
• Evolutionary game model of group choice dilemmas on hypergraphs
• Evolving small-world scale-free networks consist of cliques
• Look Who's Talking: Bipartite Networks as Representations of a Topic Model of New Zealand Parliamentary Speeches
• Degree distributions of bipartite networks and their projections
• A generative graph model for electrical infrastructure networks
• Performance of Hyperbolic Geometry Models on Top-N Recommendation Tasks
• Component Evolution in General Random Intersection Graphs
• Randomizing hypergraphs preserving degree correlation and local clustering
• Competition for Popularity in Bipartite Networks
• Scalable Hyperbolic Recommender Systems
• Sampling from naturally truncated power laws: The matchmaking paradox
• Understanding how both the partitions of a bipartite network affect its one-mode projection
• Pattern detection in bipartite networks: a review of terminology, applications and methods
• The Higher Education Space, Connecting Degree Programs from Individuals' Choices
• Construction of bipartite and unipartite weighted networks from collections of journal papers
• Random intersection graphs with communities
• Stay Awhile and Listen: User Interactions in a Crowdsourced Platform Offering Emotional Support
• Nonlinear consensus on networks: equilibria, effective resistance and trees of motifs
• The role of bipartite structure in R&D collaboration networks
• Network-based confidence scoring system for genome-scale metabolic reconstructions
• Ridesharing in the era of Mobility as a Service (MaaS): An Activity-based Approach with Multimodality and Intermodality
• Canonical fitness model for simple scale-free graphs
• Random Choices can Facilitate the Solving of Collective Network Coloring Problems by Artificial Agents
• Hyperbolic Neural Collaborative Recommender
• On the Termination of Some Biclique Operators on Multipartite Graphs
• Termination of Multipartite Graph Series Arising from Complex Network Modelling
• Robustness of Bidirectional Interdependent Networks: Analysis and Design
• The influence of the network topology on the agility of a supply chain
• Nonrandom behavior in the Projection of Random bipartite networks
• Diffusion in Networks With Overlapping Community Structure
• Hypothesis Testing for Two Sample Comparison of Network Data
• Collaboration and followership: a stochastic model for activities in social networks
• Convergence law for hyper-graphs with prescribed degree sequences
• Superexponential growth of epidemics in networks with cliques
• Assessing the significance of knockout cascades in metabolic networks
• A Decentralized Shared CAV System Design and Application
• Detection of network inhomogeneity by total neighbor degree
• Scale-Invariant Strength Assortativity of Streaming Butterflies