On network bipartivity

Abstract

Systems with two types of agents with a preference for heterophilous interaction produces networks that are more or less close to bipartite. We propose two measures quantifying the notion of bipartivity. The two measures--one well-known and natural, but computationally intractable; one computationally less complex, but also less intuitive--are examined on model networks that continuously interpolates between bipartite graphs and graphs with many odd circuits. We find that the bipartivity measures increase as we tune the control parameters of the test networks to intuitively increase the bipartivity, and thus conclude that the measures are quite relevant. We also measure and discuss the values of our bipartivity measures for empirical social networks (constructed from professional collaborations, Internet communities and field surveys). Here we find, as expected, that networks arising from romantic online interaction have high, and professional collaboration networks have low bipartivity values. In some other cases, probably due to low average degree of the network, the bipartivity measures cannot distinguish between romantic and friendship oriented interaction.

References in corpus (21)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Assortative mixing in networks
• Cooperative Game Theory Approaches for Network Partitioning
• The large-scale organization of metabolic networks
• Random graphs with arbitrary degree distributions and their applications
• Evolution of networks
• Exchange Monte Carlo Method and Application to Spin Glass Simulations
• Clustering and preferential attachment in growing networks
• The Web of Human Sexual Contacts
• Scale-free topology of e-mail networks
• Ferromagnetic Phase Transition in Barabasi-Albert Networks
• Mean field solution of the Ising model on a Barabasi-Albert network
• Ising model in small-world networks
• XY model in small-world networks
• Instant Messaging as a Scale-Free Network
• Dynamic critical behavior of the XY model in small-world networks
• Interface Motion and Pinning in Small World Networks
• Freezing in random graph ferromagnets
• Cycles structure and local ordering in complex networks

Cited by in corpus (37)

• Finding community structure in networks using the eigenvectors of matrices
• Characterization of complex networks: A survey of measurements
• Critical phenomena in complex networks
• Vital nodes identification in complex networks
• How to project a bipartite network?
• Mixture models and exploratory analysis in networks
• The Statistical Physics of Real-World Networks
• Spectral Measures of Bipartivity in Complex Networks
• Cycles and clustering in bipartite networks
• Quantifying the effect of temporal resolution on time-varying networks
• Homophily and minority size explain perception biases in social networks
• Progresses and Challenges in Link Prediction
• Empirical analysis of web-based user-object bipartite networks
• Communication activity in a social network: relation between long-term correlations and inter-event clustering
• Personal Recommendation via Modified Collaborative Filtering
• Balance and Frustration in Signed Networks
• New approaches to model and study social networks
• Stochastic block model and exploratory analysis in signed networks
• Communicability and multipartite structures in complex networks at negative absolute temperatures
• Detecting Core-Periphery Structures by Surprise
• Exploiting the Structure of Bipartite Graphs for Algebraic and Spectral Graph Theory Applications
• Meta-validation of bipartite network projections
• Empirical studies on the network of social groups: the case of Tencent QQ
• Clustering under the line graph transformation: Application to reaction network
• Detecting mesoscale structures by surprise
• Structural measures of similarity and complementarity in complex networks
• Functional structure in production networks
• Understanding how both the partitions of a bipartite network affect its one-mode projection
• Communication activity in social networks: growth and correlations
• Interplay between HIV/AIDS Epidemics and Demographic Structures Based on Sexual Contact Networks
• Scale-free networks with a large- to hypersmall-world transition
• Emergence of (bi)multi-partiteness in networks having inhibitory and excitatory couplings
• Nonrandom behavior in the Projection of Random bipartite networks
• Network topology mapping of Chemical Compounds Space
• Refinement for community structures of bipartite networks
• Shaping Magnetic Order by Local Frustration for Itinerant Fermions on a Graph
• Domain matters: Towards domain-informed evaluation for link prediction