Convexity in complex networks

Abstract

Metric graph properties lie in the heart of the analysis of complex networks, while in this paper we study their convexity through mathematical definition of a convex subgraph. A subgraph is convex if every geodesic path between the nodes of the subgraph lies entirely within the subgraph. According to our perception of convexity, convex network is such in which every connected subset of nodes induces a convex subgraph. We show that convexity is an inherent property of many networks that is not present in a random graph. Most convex are spatial infrastructure networks and social collaboration graphs due to their tree-like or clique-like structure, whereas the food web is the only network studied that is truly non-convex. Core-periphery networks are regionally convex as they can be divided into a non-convex core surrounded by a convex periphery. Random graphs, however, are only locally convex meaning that any connected subgraph of size smaller than the average geodesic distance between the nodes is almost certainly convex. We present different measures of network convexity and discuss its applications in the study of networks.

27 pages, 11 figures, 3 tables

References in corpus (18)

• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Maps of random walks on complex networks reveal community structure
• Critical phenomena in complex networks
• Hierarchical structure and the prediction of missing links in networks
• Higher-order organization of complex networks
• Biological network comparison using graphlet degree distribution
• Mixture models and exploratory analysis in networks
• Classes of complex networks defined by role-to-role connectivity profiles
• Core-periphery organization of complex networks
• Network Lasso: Clustering and Optimization in Large Graphs
• Identification of core-periphery structure in networks
• Robust network community detection using balanced propagation
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Role models for complex networks
• $k$-core percolation on complex networks: Comparing random, localized and targeted attacks
• Embedding Graphs in Lorentzian Spacetime
• Corrected overlap weight and clustering coefficient

Cited by in corpus (4)

• Core-periphery structure requires something else in the network
• Convexity in scientific collaboration networks
• Convex skeletons of complex networks
• On convex decision regions in deep network representations