Picture map of Europe with pins indicating European capital cities

Open Access research with a European policy impact...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by Strathclyde researchers, including by researchers from the European Policies Research Centre (EPRC).

EPRC is a leading institute in Europe for comparative research on public policy, with a particular focus on regional development policies. Spanning 30 European countries, EPRC research programmes have a strong emphasis on applied research and knowledge exchange, including the provision of policy advice to EU institutions and national and sub-national government authorities throughout Europe.

Explore research outputs by the European Policies Research Centre...

Hyperspherical embedding of graphs and networks in communicability spaces

Estrada, Ernesto and Sanchez-Lirola, M.G. and de la Pena, Jose Antonio (2013) Hyperspherical embedding of graphs and networks in communicability spaces. Discrete Applied Mathematics, n/a (n/a). pp. 1-25.

Full text not available in this repository. Request a copy from the Strathclyde author

Abstract

Let GG be a simple connected graph with nn nodes and let fαk(A)fαk(A) be a communicability function of the adjacency matrix AA, which is expressible by the following Taylor series expansion: ∑k=0∞αkAk. We prove here that if fαk(A)fαk(A) is positive semidefinite then the function ηp,q=(fαk(A)pp+fαk(A)qq−2fαk(A)pq)12 is a Euclidean distance between the corresponding nodes of the graph. Then, we prove that if fαk(A)fαk(A) is positive definite, the communicability distance induces an embedding of the graph into a hyperdimensional sphere (hypersphere) such as the distances between the nodes are given by ηp,qηp,q. In addition we give analytic results for the communicability distances for the nodes in paths, cycles, stars and complete graphs, and we find functions of the adjacency matrix for which the main results obtained here are applicable. Finally, we study the ratio of the surface area to volume of the hyperspheres in which a few real-world networks are embedded. We give clear indications about the usefulness of this embedding in analyzing the efficacy of geometrical embeddings of real-world networks like brain networks, airport transportation networks and the Internet.