Curvature-based Analysis for Complex Networks @ NetSci 2017

Abstract

It is not by chance that the emergence of network science has coincided with fast developments in the computational sciences. Ever more powerful computational machinery gives unprecedented access to diverse high-resolution data from the social, life and physical sciences. Networks have emerged as popular means of representing relationships and commonalities in complex systems as underlying these data sets.The complexity of such networks easily exceeds the limits of efficient computational accessibility creating a need to identify key structural features on which to focus further analysis. In this context it is important to understand their higher order organization, namely the major network communities and the connections between them. We present geometric tools for characterizing the structure and evolution of complex networks through the evaluation of edge weights and local connectivity.Our geometric methods are based on a discrete notion of curvature as an edge-based network characteristic (Weber, Saucan, Jost; J. Compl. Net. 2017a). Together with its associated geometric flows, the curvature tool extracts long-range connections of high curvature acting as bridges between major network communities. With this, the curvature-based method gives important insights into the higher order organization of complex networks. When applied to real-world networks, the method aids in identifying functionally meaningful substructures of the underlying complex system. Furthermore the curvature notion gives rise to a tool for reducing complex network structures to essential features (backbone effect), thus making high-resolution data better accessible to computational tools.The curvature-based formalism can be extended to not only characterize local geometry, but also the global shape of complex networks (Weber, Saucan, Jost; J. Compl. Net. 2017b). While there exists a body of knowledge concerned with local network characteristics, the systematic study of global network structure is a largely untouched field. Our setting allows for a network-theoretic analogue of the classic Gauß-Bonnet theorem and the computation of Euler characteristics. Attempting to analyze the long-term evolution of networks qualitatively, we introduce prototype networks that give rise to a global classification scheme based on discrete Forman-Ricci curvature.