Convex skeletons of complex networks

Abstract

A convex network can be defined as a network such that every connected induced subgraph includes all the shortest paths between its nodes. Fully convex network would therefore be a collection of cliques stitched together in a tree. In this paper, we study the largest high-convexity part of empirical networks obtained by removing the least number of edges, which we call a convex skeleton. A convex skeleton is a generalisation of a network spanning tree in which each edge can be replaced by a clique of arbitrary size. We present different approaches for extracting convex skeletons and apply them to social collaboration and protein interactions networks, autonomous systems graphs and food webs. We show that the extracted convex skeletons retain the degree distribution, clustering, connectivity, distances, node position and also community structure, while making the shortest paths between the nodes largely unique. Moreover, in the Slovenian computer scientists coauthorship network, a convex skeleton retains the strongest ties between the authors, differently from a spanning tree or high-betweenness backbone and high-salience skeleton. A convex skeleton thus represents a simple definition of a network backbone with applications in coauthorship and other social collaboration networks.

23 pages, 14 figures, 4 tables

References in corpus (13)

• Power-law distributions in empirical data
• Finding community structure in networks using the eigenvectors of matrices
• Maps of random walks on complex networks reveal community structure
• Comparing community structure identification
• Community Structure in Jazz
• Missing and spurious interactions and the reconstruction of complex networks
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Graph Evolution: Densification and Shrinking Diameters
• Core-periphery organization of complex networks
• The many facets of community detection in complex networks
• Modeling Interactome: Scale-Free or Geometric?
• Bridges in Complex Networks
• Convexity in complex networks

Cited by in corpus (4)

• backbone: An R package to extract network backbones
• Convexity in scientific collaboration networks
• The Atlas for the Aspiring Network Scientist
• Computing well-balanced spanning trees of unweighted networks