Structural measures of similarity and complementarity in complex networks

Abstract

The principle of similarity, or homophily, is often used to explain patterns observed in complex networks such as transitivity and the abundance of triangles (3-cycles). However, many phenomena from division of labor to protein-protein interactions (PPI) are driven by complementarity (differences and synergy). Here we show that the principle of complementarity is linked to the abundance of quadrangles (4-cycles) and dense bipartite-like subgraphs. We link both principles to their characteristic motifs and introduce two families of coefficients of: (1) structural similarity, which generalize local clustering and closure coefficients and capture the full spectrum of similarity-driven structures; (2) structural complementarity, defined analogously but based on quadrangles instead of triangles. Using multiple social and biological networks, we demonstrate that the coefficients capture structural properties related to meaningful domain-specific phenomena. We show that they allow distinguishing between different kinds of social relations as well as measuring an increasing structural diversity of PPI networks across the tree of life. Our results indicate that some types of relations are better explained by complementarity than homophily, and may be useful for improving existing link prediction methods. We also introduce a Python package implementing efficient algorithms for calculating the proposed coefficients.

arXiv commentAuthors' copy of the published version

References in corpus (17)

• The architecture of complex weighted networks
• Spectral Measures of Bipartivity in Complex Networks
• Network Geometry
• The clustering coefficient and community structure of bipartite networks
• On network bipartivity
• Cumulative effects of triadic closure and homophily in social networks
• Network Geometry Inference using Common Neighbors
• Clustering implies geometry in networks
• Unbiased sampling of network ensembles
• Division of labor, skill complementarity, and heterophily in socioeconomic networks
• Trust transitivity in social networks
• Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints
• Small worlds and clustering in spatial networks
• Homophily as a Process Generating Social Networks: Insights from Social Distance Attachment Model
• Extracting Complements and Substitutes from Sales Data: A Network Perspective
• Functional structure in production networks
• Triadic closure in configuration models with unbounded degree fluctuations

Cited by in corpus (3)

• Polarization and multiscale structural balance in signed networks
• Topological properties and organizing principles of semantic networks
• Pattern detection in bipartite networks: a review of terminology, applications and methods