• centrality measures
• cospectral vertices
• Estrada's conjecture
• exponential subgraph centrality
• graph theory
• interlacements
• network science
• resolvent subgraph centrality
• spectral graph theory
• walk-regular graph

Centrality measures have been used to determine the importance of a vertex in a graph, with many applications in network science, and other fields such as biology, finance, sociology, epidemiology. For example, traffic networks, internet and web pages, collaboration between researchers, neuron interaction in the brain, can be modelled using graphs, with static or dynamic aspects. With these objectives in mind, it is often useful to determine the most important nodes in a network. This is accomplished by using a centrality measure: it is a function which assigns a positive value (weight) to a vertex, with more important nodes having more weight.

Many centrality measures have been proposed in the literature. In this thesis, we focus mostly on centrality measures derived from linear algebra and the adjacency matrix of the graph. A survey of the most popular measures is described in chapter 2.1.
In particular, we study the Exponential Subgraph Centrality and the Resolvent Subgraph Centrality. Both centrality measures are defined as the diagonal entry of a certain matrix functions, respectively exponential and shifted inverse (resolvent). This expression can be related, by means of Taylor series, to the sum of closed walks starting and ending in a vertex, appropriately weighted. Both function have a parameter, to give more importance to shorter or to longer walks.

In chapter 2.2 we show a result of Benzi, Klymko for the limit behaviour of the Exponential and Resolvent Subgraph Centrality. As the parameter goes to zero, the ranking of vertices converges to the ranking given by Degree Centrality, while as the parameter grows, the ranking converges to the ranking given by Eigenvector Centrality.

After this brief introduction to centrality measures, we are interested in studying when two “different" vertices have the same score for a centrality measure. We introduce the definition of cospectral vertices, and walk-regular graph, which is a graph with all vertices cospectral. Cospectral vertices are not necessarily identical, but have similar spectral properties, and cannot be distinguished by measures based on linear algebra. A conjecture posed by Estrada, states that a graph is walk regular if and only if all vertices have the same Exponential Subgraph Centrality, with parameter beta=1.

In Theorem 3.7, we prove that two vertice which have the same Exponential Subgraph Centrality, with an algebraic parameter beta, are necessarily cospectral. This results implies the above-mentioned conjecture.

A related problem we are interested in studying, is to determine when a vertex can be more important than the other for some values of the parameter of a centrality measure, and less important for other values.
When two vertices swap ranking, we say that they interlace. We study the number of interlacing values, and determine upper and lower bounds in different situations.

In Theorem 3.2, we prove that for a directed weighted graph with n vertices, there can be at most n-1 interlacing values for any couple of vertices for the Resolvent Subgraph Centrality. Theorem 3.4, provides a better estimate in the case the graph is simple. In Theorem 3.5, we obtain an upper bound for the number of interlacing values for the Exponential Subgraph Centrality.

These theorems are original results of this thesis.