Edge-based analysis of networks: curvatures of graphs and hypergraphs
- PDF / 1,816,108 Bytes
- 12 Pages / 595.276 x 790.866 pts Page_size
- 2 Downloads / 191 Views
ORIGINAL ARTICLE
Edge‑based analysis of networks: curvatures of graphs and hypergraphs Marzieh Eidi1 · Amirhossein Farzam1 · Wilmer Leal1,2 · Areejit Samal3 · Jürgen Jost1,4 Received: 1 October 2020 / Accepted: 4 November 2020 / Published online: 20 November 2020 © The Author(s) 2020
Abstract The relations, rather than the elements, constitute the structure of networks. We therefore develop a systematic approach to the analysis of networks, modelled as graphs or hypergraphs, that is based on structural properties of (hyper)edges, instead of vertices. For that purpose, we utilize so-called network curvatures. These curvatures quantify the local structural properties of (hyper)edges, that is, how, and how well, they are connected to others. In the case of directed networks, they assess the input they receive and the output they produce, and relations between them. With those tools, we can investigate biological networks. As examples, we apply our methods here to protein–protein interaction, transcriptional regulatory and metabolic networks.
Introduction A central paradigm of structuralism (De Saussure 1972; Lévi-Strauss 1958) is the analysis of structural relations regardless of the identity of the elements involved. That is, a structure is conceived in terms of the relations between elements. One wants to understand the types of relations, rather than the nature of the elements. This paradigm is obviously also fundamental for the analysis of empirical networks, be they from the biological sciences or other domains. Such an analysis then again abstracts from the specific content of the elements and concentrates on the formal relations between them. In that manner, one can both find universal features that hold across a wide range of networks from different domains, and properties that are specific to particular empirical domains. For that purpose, many different measures have been developed. Some of these measures, like for instance the
* Jürgen Jost [email protected] 1
Max Planck Institute for Mathematics in the Sciences, 04103 Leipzig, Germany
2
Bioinformatics Group, Department of Computer Science, Universität Leipzig, 04107 Leipzig, Germany
3
The Institute of Mathematical Sciences (IMSc), Homi Bhabha National Institute (HBNI), Chennai 600113, India
4
The Santa Fe Institute, Santa Fe, NM 87501, USA
assortativity (see for instance Newman 2003; Jackson 2008), are of a global nature, that is, associate some number to the entire network. Such a number is usually an average or perhaps, like the diameter of a network, an extremum of locally measured quantities. In any case, the basis for such global measures is to first develop local measures. For a more refined analysis, one can then also look at the statistics of those local measures, instead of lumping them together in a single number (for instance Piraveenan et al. 2010; Farzam et al. 2020 for assortativity). Some of these local measures require global computations in the network; for instance, for computing the diameter, one needs to evalu
Data Loading...
