Keywords: Estrada indices, matrix functions, algebraic graph theory, eigenvalues of graphs, complex networks Mathematics Subject Classication 05C12, 05C22, 05C35, 05C50, 05C80, 05C82, 05C92, 15A16, 15A42

The many facets of the Estrada indices of graphs and networks

Introduction

At the dawn of the XXI century the current author proposed an index to quantify the degree of folding of a linear chain in a three-dimensional space [START_REF] Estrada | Characterization of 3d molecular structure[END_REF]. The motivation of this work came from the fact that many scientic articles make claims like that the structure A is more folded than the structure B (see examples at: [START_REF] Chu | Relationship between the nativestate hydrogen exchange and folding pathways of a four-helix bundle protein[END_REF][START_REF] Enns | The dynamics of subduction and trench migration for viscosity stratication[END_REF]128,237]), or that certain structure is highly folded (see for instance: [START_REF] Chen | Perforated block copolymer vesicles with a highly folded membrane[END_REF]129,142,246]), etc. These expressions could be referring to protein or polymer structures, but also to brain regions or even geological structures (see previous refs.). However, in neither of these works there was an index that quanties how folded a linear chain is. Thus, the author proposed the index I 3 = n j=1 exp (λ j (W )), where λ j (W ) are the eigenvalues of Institute for Cross-Disciplinary Physics and Complex Systems (IFISC, UIB-CSIC), Campus Universitat de les Illes Balears E-07122, Palma de Mallorca, Spain. E-mail: estrada@isc.uibcsic.es certain tridiagonal matrix W whose diagonal entries are related to the cosines of the dihedral angles between adjacent planes and W i,i+1 and W i+1,i are equal to one. This index characterizes very well the degree of folding of a geometric chain and it has been mainly applied to the study of the degree of folding of proteins (see for instance [START_REF] Estrada | Characterization of the folding degree of proteins[END_REF][START_REF] Estrada | Characterization of the amino acid contribution to the folding degree of proteins[END_REF]211]), although it can be applied to the folding of any linear chain.

Five years after the publication of the folding degree paper, the authors of [START_REF] Estrada | Subgraph centrality in complex networks[END_REF] proposed the subgraph centrality as a way to characterize the importance of the nodes in a complex network. Complex networks are large graphs representing the skeleton of complex systems in social, ecological, cellular, molecular, infrastructural, semantic and other scenarios [START_REF] Estrada | The structure of complex networks: theory and applications[END_REF]. The subgraph centrality of a node v in a network is dened as SCv = n j=1 ψ 2 jv exp (λ j (A)), where λ j = λ j (A) are the eigenvalues of the adjacency matrix of the graph and ψ jv is the vth entry of its jth normalized eigenvector. Then, the so-called subgraph centralization of the network is v SCv = n j=1 exp (λ j (A)) [START_REF] Estrada | Subgraph centrality in complex networks[END_REF], which is similar to the folding degree I 3 .

In June 2005 the current author presented the lecture Topological characterization of complex networks at the International Academy of Mathematical Chemistry in Dubrovnik, Croatia. As a consequence Ivan Gutman proposed to organize a small seminar at a park near the port of Dubrovnik to discuss some of the mathematical aspects of the index v SCv = n j=1 exp (λ j ) for general graphs. As a result, a paper was published in 2006 in Croatica Chemica Acta introducing v SCv as a molecular structure descriptor [113]. A year later the paper Estimating the Estrada index was published, where the authors proposed to call EE (G) = n j=1 exp (λ j ) the Estrada index [START_REF] De La Peña | Estimating the Estrada index[END_REF]. The same year a statistical mechanics interpretation of EE (G) as the partition function of a graph [START_REF] Estrada | Statistical-mechanical approach to subgraph centrality in complex networks[END_REF] appeared. A year later, in 2008, there were more than 30 papers published in the mathematical literature containing Estrada index in the title.

It seems a priori that EE (G) has emerged in dierent, apparently unrelated, sce- narios: folding of linear chains, subgraphs in networks, and partition function in statistical mechanics. This reminds us the story told by Eugene Wigner in the rst paragraph of his paper The unreasonable eectiveness of mathematics in the natural sciences [233] where a fellow asked a former classmate, now a statistician, about a symbol in a paper dealing with population trends. The statistician replied that the symbol was π and to clarify the skepticism of the other he added that it is the ratio of the circumference of the circle to its diameter. The fellow then replied more skeptical: Well, now you are pushing your joke too far, surely the population has nothing to do with the circumference of the circle. The situation of the Estrada index seems murkier than the one in that story, particularly after the ad hoc denition of several other variations of the index based not on the eigenvalues of the adjacency matrix, but of the graph Laplacian, distance matrix, resolvent of the adjacency matrix, Hadamard pseudo-inverse of the distance matrix (a.k.a. Harary matrix), Mittag-Leer matrix functions of A, etc.

The goal of this paper is to make an account of the dierent facets of the Estrada indices. In doing so we will provide contextualization of several of these indices, many of which have been proposed in an ad hoc way. Therefore, we will provide a physical and/or mathematical context and interpretation of these indices. They include a combinatorial interpretation based on counting subgraphs, a statistical mechanics approach, a probabilistic interpretation in the context of walk-regular graphs, an interpretation on the basis of oscillations in (quantum and classical) systems of ball-and-springs, a contextualization on the basis of epidemiological models (normal and fractional) on graphs, diusive processes with negative diusiveness, nonlocal processes on graphs, quantication of graph radius of gyration. Although this paper does not intend to describe all the results published in the literature on this topic we make an account of many of the dierent bounds and estimations of the Estrada, Seidel Estrada, Harary Estrada, Laplacian Estrada, resolvent Estrada, Mittag-Leer Estrada, and distance Estrada indices. For this purpose we include some numerical analysis of these bounds in the set of 11,117 connected graphs with 8 nodes and in ve real-world networks representing a variety of complex system scenarios. The paper is written in a way that intend to be self-contained and make the necessary denitions for understanding the concepts used in it. The paper is then intended as a guide for further studies and developments in this area of spectral graph theory.

General denitions

Here we present some denitions which are used across the paper and settle down the notation. We consider here simple, connected graphs G = (V, E) with n nodes (vertices) and m edges.

Denition 1 A walk of length k in G is a set of nodes and edges v 1 , e 1,2 , v 2 • • • v k-1 , e k-1,k , v k such that for all 1 ≤ l ≤ k, (v l , v l+1 ) ∈ E. A closed walk is a walk for which v 1 = v k+1 .

Denition 2 A path of length k in G is a walk in which neither vertices nor edges are repeated. A cycle is a closed path. The length of the shortest path connecting two vertices v and w is the (topological) shortest path distance dvw between the two nodes. The diameter of G is the longest distance between two vertices of G.

Denition 3 A subgraph G ′ = (V ′ , E ′ ) of G is a graph such that V ′ ⊆ V and E ′ ⊆ E ∩ V ′ × V ′ .
An induced subgraph is a subgraph formed by a subset of the vertices of the graph and all of the edges connecting pairs of vertices in that subset. Denition 4 A graph G = (V, E) is connected if there is a path between every pair of nodes v, w ∈ V . If the graph is directed we said that it is strongly connected if there is a directed path between every pair of nodes v, w ∈ V . A (strongly) connected component in a (directed) graph is a subgraph in which any two vertices are connected to each other by (directed) paths, and which is connected to no additional vertices in the rest of the graph. Denition 5 The degree of a node v is the number kv of edges incident with that node. A graph is regular if the degree of all its nodes is the same.

The following matrices will be considered (Table 1):

Other matrices such as the Seidel adjacency matrix and Harary matrix, are dened in situ in the corresponding sections of the paper. The following types of graphs are used in this work.

Complete graph of n vertices Kn : the graph having an edge between every pair of vertices.

name symbol denition spectrum adjacency

A A ij = 1 (i, j) ∈ E 0 (i, j) / ∈ E λ 1 ≥ • • • ≥ λn Laplacian L L ij =    -1 (i, j) ∈ E k i i = j 0 otherwise 0 = µ 1 ≤ • • • ≤ µn distance D D ij = d ij i ̸ = j 0 i = j σ 1 ≥ • • • ≥ σn
Table 1: Denition of some matrices used in this paper.

Empty graph of n vertices Kn : the graph having n vertices and no edges.

Complete bipartite graph Kn 1 ,n2 : the graph with n = n 1 + n 2 vertices in which the vertex set is partitioned into two disjoint subsets of cardinalities n 1 and n 2 , respectively, such that every vertex in one set is connected to every vertex in the other set.

Star graph Sn: the particular case of Kn 1 ,n2 in which n 1 = 1 and n 2 = n -1.

Path graph of n vertices Pn: the connected graph in which every vertex has degree 2, except two vertices which have degree one.

Cycle Cn: a connected graph in which every vertex has degree 2.

Finally we consider two kinds of random graphs.

Erd®s-Rényi (ER) G (n, p) [START_REF] Erdos | On the evolution of random graphs[END_REF] graph with n nodes: constructed by connecting nodes randomly in such a way that each edge is included in G (n, p) with probability p independent from every other edge.

Barabási and Albert (BA) one [START_REF] Barabási | Emergence of scaling in random networks[END_REF]: created on the basis of a preferential attachment process. The graph is constructed from an initial seed of m 0 vertices connected randomly like in an Erd®s-Rényi G (n, p). Then, new nodes are added to the network in such a way that each new node is connected to c ≤ m 0 of the existing ones with a probability that is proportional to the degree of these existing nodes.

Estrada index and subgraph centralization

The main goal in proposing the Estrada index was for the structural characterization of networks. This index corresponds to the centralization, a global structural index, derived from the node centrality known as subgraph centrality. In network theory a centrality measure (see [START_REF] Estrada | The structure of complex networks: theory and applications[END_REF] Chapter 7 and refs. therein) is any graph-theoretic quantity that captures the relative importance of a node in the network. Here importance means a relevantmainly from applications point of viewstructural feature such as connectivity, closeness to the rest of the nodes, position of a node in relation to the shortest paths connecting other others, etc. The simplest of these centrality measures is the degree of a node, which counts the number of connections that a node has. Let us rst introduce the following result.

Theorem 1 Let G = (V, E) be a simple graph with adjacency matrix A. Let v, w ∈ V , then the number of walks of length k between the nodes v and w is given by A k vw .

Remark 1 The roots of Theorem 1 can be traced back to the paper The analysis of sociograms by matrix algebra by Leo Festinger in 1949 [93], although Festinger mentioned it only for the case of walks of length three. Then, Leo Katz in his seminal paper A new status index derived from sociometric analysis extended it to longer walks in 1953 [141]. The result appeared formally in the book of Claude [START_REF] Berge | The theory of graphs (trans. alison doig)[END_REF] in the form of Corollary 1 on page 131 [START_REF] Berge | The theory of graphs (trans. alison doig)[END_REF].

Then, from a walks perspective, the degree is dened as the number of closed walks of length two starting at the given node. That is, let v ∈ V , then the degree of v is given by:

kv = A 2 vv . (3.1)
The degree of a node can be seen as a rst order approximation of centrality measures that accounts for the walks of all length in the graph. That is, in a graph without self-loops the following measures can be dened

Cv -1 = ∞ k=2 c k A k vv , (3.2)
where c k are coecients which give more weight to the shorter than to the longer

walks. Then, if c k = (k!) -1 : EEv -1 = ∞ k=2 (k!) -1 A k vv = (exp (A)) vv -1, (3.3)
where EEv is known as the subgraph centrality of the node v [START_REF] Estrada | Subgraph centrality in complex networks[END_REF]. The term subgraph in the name of this centrality is due to the following.

Lemma 1 Let G be a (directed) graph. Then, every closed walk of length k starting at the node v ∈ V encloses one (strongly) connected subgraph having at most k (directed) edges and at most k vertices including v.

Proof A (directed) graph G is (strongly) connected is there is a (directed) path connecting every pair of vertices G. By the denition of walk it is clear that a walk of length k between two nodes v and w cannot visit more than k + 1 vertices. Therefore, a closed walk, where the initial and nal nodes coincide, can visit no more than k nodes.

In a closed walk of length k without backtracking the number of edges visited is k, i.e., in a cycle. For a given length k, backtracking reduces the number of edges that can be visited. Therefore, a closed walk of length k cannot visit more than k edges. Obviously, the nodes and edges visited by the closed walk form the sets V ′ ⊆ V and

E ′ ⊆ E ∩ V ′ × V ′ , which implies that G ′ = V ′ , E ′ is a subgraph of G = (V, E).
Finally, because the walk of length k is a sequence vv, e v,v+1 , v v+1

• • • v v-1 , e v-1,i , vv
there is a (directed) path connecting every pair of nodes in the subgraph, which means that G ′ is (strongly) connected. ⊓ ⊔

The previous result implies that we can express EEv as a weighted sum of subgraphs, which gives the index its name. However, as we are focused here on the Estrada index let us move to the fact that the Estrada index is the sum of the subgraph centralities of all nodes in the graph:

EE (G) = n v=1
EEv.

(3.4)

The sum of node centralities in a graph is known as the corresponding centralization of the graph, or simply as a graph-theoretic invariant. Therefore, the Estrada index of the graph can be seen as its subgraph centralization.

Theorem 2 Let G be a (directed) graph and let F be the set of all (strongly) connected subgraphs of G, and let us designate the cardinality of the set F by η. Then,

EE (G) = η l=1 c l F l , (3.5)
where F l ∈ F and c l ∈ Q.

Proof Using Lemma 1 we can show that that M k = tr A k can be expressed as a weighted sum of (strongly) connected subgraphs. The weight of each subgraph is

given by the number of closed walks of length k in the given subgraph. Then, grouping together all identical subgraphs and summing their weights we obtain the nal result.

⊓ ⊔

For instance, let us consider the rst seven powers of the adjacency matrix. Then,

tr A 2 = 2F 2 , (3.6) tr A 3 = 6F 4 , (3.7)
tr

A 4 = 2F 2 + 4F 3 + 8F 7 , (3.8)
tr

A 5 = 30F 4 + 10F 8 + 10F 10 , (3.9)
tr A 6 = 2F 2 + 12F (3.11) where the subgraphs are illustrated in Fig. 3.1.

Then, we have the following result.

Lemma 2 Let G be a simple graph. Then, the Estrada index of G is bounded as The expressions for calculating these subgraphs are given in the Appendix as adapted from [START_REF] Alon | Finding and counting given length cycles[END_REF]. The formula for F 20 is given here by the rst time.

EE (G)

Some elementary properties of the Estrada index

Before proceeding to more complex properties of the Estrada index let us state a few elementary ones that could be helpful in understanding the structural nature of this index. The reader is referred to the following references [START_REF] De La Peña | Estimating the Estrada index[END_REF][START_REF] Deng | The Estrada index. Applications of Graph Spectra[END_REF]112,116] for details and references. Lemma 3 Let G be a simple graph and let G -e the same graph from which edge e has been removed. Then EE (G -e) ≤ EE (G) . Theorem 3 [START_REF] Das | On the Estrada index conjecture[END_REF][START_REF] Deng | A proof of a conjecture on the Estrada index[END_REF] Let G be a simple connected graph with n nodes. Then EE (Pn) ≤ EE (G) ≤ EE (Kn) . The Estrada indices of some elementary graphs are given below.

EE (Kn) = e n-1 + (n -1) e -1 ; EE (Kn 1 ,n2 ) = n 1 + n 2 -2 + 2 cosh ( √ n 1 n 2 ) ; EE (Sn) = n -2 + 2 cosh √ n -1 ; limn→∞ EE (Cn) = nI 0 , where I 0 = 1 π π 0 e 2 cos x dx; limn→∞ EE (Pn) = (n -1) -2 cosh (2).

Numerical analysis

We consider here two datasets which will be used in the rest of the paper for the numerical evaluation of the dierent indices and bounds. The rst one consists of the 11,117 connected graphs with 8 nodes. The second one is formed by ve real-world networks, which correspond to a food web at Stony stream, a network of the neurons in the worm C. elegans, the protein-protein interaction network of yeast, a representation of the Internet at the autonomous system (AS) level, and a network of the USA western power grid system. The number of nodes n, of edges m, the maximum degree of the nodes kmax, and the diameter dmax of each network are given in In

Estrada index and matrix functions

Soon after the denition of the Estrada index and the subgraph centrality several authors started to be interested in these indices due to their clear relation to functions of the adjacency matrix. The study of matrix functions is an active area of research in (numerical) linear algebra [START_REF] Belyayev | On the calculation of functions of matrices[END_REF][START_REF] Frommer | Matrix functions[END_REF]127,222]. The topic of matrix functions in network theory has been recently reviewed by the authors of [START_REF] Benzi | Matrix functions in network analysis[END_REF]. Therefore, we will not give too many details here and the interested reader is directed to the excellent review [START_REF] Benzi | Matrix functions in network analysis[END_REF].

The goal of this section is then to establish the connection between the Estrada indices and functions of the corresponding matrices which pave the way for further sections of the article. Here we will follow the book [127].

Let M be any graph-theoretic matrix, e.g., adjacency, Laplacian, distance, etc.

Then, its Jordan canonical form is given by

Z -1 M Z = J = diag (J 1 , J 2 , • • • , Jp) , (4.1)
where

J k = J k (λ k ) =       λ k 1 λ k . . . . . . 1 λ k       ∈ C m k ×m k , (4.2)
where Z is nonsingular and

m 1 + m 2 + • • • + mp = n.
f (j) (λ i ) , j = 0, . . . , n i -1, i = 1, . . . , s (4.3)
exist, which are called the values of the function f on the spectrum of M . Here f (j) represents the jth derivative of f .

Then we have a denition of matrix function via the Jordan canonical form.

Denition 7 Let f be dened on the spectrum of M and let M have the Jordan canonical form given before. Then, the matrix function f (M ) is given by

f (M ) := Zf (J) Z -1 = Zdiag (f (J k )) Z -1 , (4.4)
where

f (J k ) :=         f (λ k ) f ′ (λ k ) • • • f (m k -1) (λ k ) (m k -1)! f (λ k ) . . . . . . . . . f ′ (λ k ) f (λ k )         . (4.5)
Another, equivalent, denition is given via the Cauchy integral.

Denition 8 Let M ∈ C n×n , then

f (M ) := 1 2πi Γ f (z) (zI -M ) -1 dz, (4.6)
here f is analytic on and inside a closed contour Γ that encloses the spectrum of M .

Estrada index and spectral graph theory

An obvious connection exists between the Estrada index and the area of algebraic graph theory. Algebraic graph theory [START_REF] Beineke | Topics in algebraic graph theory[END_REF][START_REF] Biggs | Algebraic graph theory[END_REF]105] deals with the use of algebraic methods to solve problems about graphs. Of particular interest is the use of the spectra of graph theoretic matrices to understand the structure of graphs, which is known as spectral graph theory [START_REF] Chung | Spectral graph theory[END_REF]5052,213,214]. This area of research started in an applied context when Collatz and Sinogowitz published their paper entitled: Spektren endlicher grafen motivated by application problems such as the vibrations of a membrane [223]. Let us consider a simple example of the connections between structural properties of graphs and their spectra: counting triangles in a graph. The number of triangles, which is a combinatorial property of the graph, can be obtained from the spectrum of the adjacency matrix as:

1 6 n j=1 λ 3 j , where λ j are the eigenvalues of the adjacency matrix.

The eld of spectral graph theory had a tremendous impulse in the 1970's due to its connection with electronic properties of conjugated molecules [START_REF] Dias | Molecular orbital calculations using chemical graph theory[END_REF][START_REF] Fowler | Hückel spectra of möbius π systems[END_REF]124,215,216,219].

The relation between the trace of a matrix and its eigenvalues immediately implies that the Estrada index of a graph can be expressed in terms of the eigenvalues of A as follows:

EE (G) = n j=1
exp (λ j ) .

(5.1)

In general, the exponentiation of A enlarges the spectral gap λ 1 -λ 2 and contracts the negative part of the spectrum. On the contrary, exp (-A) largely contracts the positive part of the spectrum and enlarges its negative part. These simple dilation/contraction eects of the main parts of the spectrum of A have important consequences on the Estrada index of a graph as we will see in the next parts of this review.

The analysis of the relation between the spectrum of a graph, i.e., the eigenvalues of its adjacency matrix, and the structure of the graph is the main goal of spectral graph theory. One of the rst results on spectral graph theory related to the Estrada index was the following bounds obtained by the authors of [START_REF] De La Peña | Estimating the Estrada index[END_REF].

Theorem 5 Let G be a simple graph with n nodes and m edges. Then, the Estrada index of G is bounded as

n 2 + 4m ≤ EE (G) ≤ n -1 + exp √ 2m , (5.2)
with equality attained if and only if G ∼ = Kn.

These bounds were further improved in [166] where the following was proved.

Theorem 6 Let G be a simple graph with n nodes and m ≥ 1 edges. Then, the Estrada index of G is bounded as

n 2 + 5 3 m < EE (G) < n -1 + exp √ m .
(5.3)

Based on Gauss-Radau quadrature rule the authors of [START_REF] Benzi | Quadrature rule-based bounds for functions of adjacency matrices[END_REF] obtained the following bounds.

Theorem 7 Let G be a simple graph and let a, b ∈ R be such that the spectrum of A

is contained in [a, b]. Then, the Estrada index of G is bounded as n i=1 b 2 exp (k i /b) + k i exp (-b) b 2 + k i ≤ EE (G) ≤ n i=1 a 2 exp (k i /a) + k i exp (-a) a 2 + k i , (5.4)
where k i is the degree of the node i. Another set of bounds was obtained in 2016 [156] by using the number of triangles t and tr A 4 in addition to the number of nodes and edges of the graph.

Theorem 8 Let G be a simple graph with n nodes, m edges, t triangles and let Q = tr A 4 . Then, the Estrada index of G is bounded as Theorem 11 [110] Let G be a simple graph with n nodes and m edges, such that 2m/n < 1. Then, the Estrada index of G is bounded as

m + n ≤ n 2 + mn + 2nt + 1 12 nQ + m 2 ≤ EE (G) ≤ n -1 + exp
EE (G) ≥ n -2m + 2m cosh (1) , (5.8)
where equality holds if and only if G consists of n -2m isolated vertices and m copies of K 2 .

Theorem 12 [110,119] Let G be a simple graph with n nodes, m edges and graph nullity η 0 . Then, the Estrada index of G is bounded as

EE (G) ≥ η 0 + (n -η 0 ) cosh 2m n -η 0 , (5.9)
where equality is attained if and only if n -η 0 is even, and if G consists of copies of complete bipartite graphs Kr i,si , i = 1, • • • , (n -η 0 ) /2, such that all products r i • s i are mutually equal. Theorem 13 [190] Let G be a simple graph with n nodes, m edges and minimum degree k min . Then, the Estrada index of G is bounded as

EE (G) ≥ 2 cosh 2 (m -k min ) n -1 + n -2,
(5.10)

with equality if and only if G ∼ = Kp,p ∪ K 1 with n = 2p + 1.

Theorem 14 [190] Let G be a simple graph with n nodes, m edges and minimum degree k min . Then, the Estrada index of G is bounded as

EE (G) ≥ 2 cosh 2 cos π n + 1 + n -2, (5.11)
with equality if and only if G ∼ = P 2 or G ∼ = P 4 .

Theorem 15 [START_REF] Bamdad | New lower bounds for Estrada index[END_REF] Let G be a simple graph with n nodes, m edges and t triangles.

Then, the Estrada index of G is bounded as

EE (G) ≥ n 2 + mn + 2nt, (5.12)
with equality if and only if G ∼ = Kn.

Other bounds reported in the literature are based on dierent graph-theoretic indices and properties or for specic classes of graphs. A non-exhaustive resume is provided in Table 4.

type of graphs ref.

general [START_REF] Andrade | Extremal graphs for Estrada indices[END_REF][START_REF] Carmona | An increasing sequence of lower bounds for the Estrada index of graphs and matrices[END_REF][START_REF] Du | On the Estrada index of graphs with given number of cut edges[END_REF]101,121,189,198,201,238] weighted general [197,200] trees [START_REF] Deng | A note on the Estrada index of trees[END_REF][START_REF] Du | The Estrada index of trees[END_REF]159,188,244] molecular trees [115,134] unicyclic [START_REF] Du | The Estrada index of unicyclic graphs[END_REF] bicyclic

[228] tricyclic [252] tetracyclic [186] pentacyclic [185]
bipartite [START_REF] Fath-Tabar | New upper bounds for Estrada index of bipartite graphs[END_REF]120,245,250] line graphs [START_REF] Aleksi¢ | Estrada index of iterated line graphs[END_REF]208] strongly quotients [START_REF] Bozkurt | On the energy and Estrada index of strongly quotient graphs[END_REF] folded fullerenes [START_REF] Ashra | Bounds on the Estrada index of isr (4, 6)-fullerenes[END_REF] Möbius [START_REF] Fowler | Möbius systems and the Estrada index[END_REF] Table 4: Examples of studies reported in the literature for some classes of graphs.

Numerical analysis

We now do some calculations to show how close to the actual values of the Estrada index are some of the bounds studied in the previous sections. In particular, we consider the following ve bounds: Bound 1 (Theorem 5); Bound 2 (Theorem 6; Bound 3 (Theorem 7 using a = -λ 1 and b = -λn); Bound 4 (Theorem 7 using a = -kmax and b = kmax); when the maximum degree of the network is very high and not close to the spectral radius, which is the case for instance of Internet, but also of many real-world networks.

All in all, these results point out to the necessity of improving the bounds for the Estrada index of large graphs.

We then consider simple bounds based on the spectral radius of the adjacency matrix λ 1 . That is, In blue we illustrate the histogram for the lower and in red for the upper bounds. As usual for histograms, frequency stands for the number of graphs in each bin.

e λ1 < EE (G) < ne λ1 .

(5.13)

The results are given in Table 5. As can be seen the bounds are very close to the actual values of the Estrada index. This is a consequence of the relatively large values of the spectral radius and of the spectral gap observed in most of the real-world networks, which when exponentiated are signicantly enlarged. Notice that the largest deviation is obtained for powergrid, where the spectral radius is signicantly smaller than in the rest of the networks and the spectral gap is very small.

Random graphs

In the study of real-world networks it is desired to investigate how unique are their structural and dynamical properties in relation to some null model. For instance, suppose that we have found that certain network displays relatively large Estrada index in relation to other networks of the same size. Is this a characteristic feature of the topological organization of this network or just an artifact emerging from a random Table 5: Naive bounds based on the spectral radius of the adjacency matrix for the Estrada index of real-world networks.

interconnection of their nodes? A way to investigate this is by comparing the Estrada index of these networks with those of random realizations of such networks with the same number of nodes and edges. Then, the use of random graphs is frequent in the analysis of real-world networks [220]. Two classical models, although not the only ones, to do such studies are the Erd®s-Rényi random graphs [START_REF] Erdos | On the evolution of random graphs[END_REF] and the Barabási-Albert preferential attachment model [START_REF] Barabási | Emergence of scaling in random networks[END_REF]. For instance, the Estrada index of the network neurons studied here is EE (G real ) ≈ 1.3062 • 10 10 and that of an Erd®s-Rényi random graph with the same number of nodes and edges is EE (G ER ) ≈ 3.4688 • 10 6 , which indicates that the large Estrada index of this network is not due to a random interconnection of the neurons of C. elegans. However, the consideration of a Barabási-Albert network with the same number of nodes and edges than those in the network neurons gives EE (G BA ) ≈ 1.2131 • 10 10 , which clearly points out that the relatively large Estrada index of this network may be explained by its skewed degree distribution.

For the Estrada index of random graphs, only the Erd®s-Rényi model has been considered so far, indicating the necessity of extending these studied to other classes of random graphs such as the Barabási-Albert one. The following estimates were found for Erd®s-Rényi random graphs based on the number of nodes and the probability of connection. Lemma 4 [196] Let Gn,p be an Erd®s-Rényi random graph with n nodes and probability

ln n n ≪ p < 1 - ln n n .
( 5.14) Then, the Estrada index is

EE (Gn,p) = (1 + o (1)) e np , (5.15)
almost surely as n → ∞.

Theorem 16 [START_REF] Chen | Estrada index of random graphs[END_REF] Let Gn,p be e an Erd®s-Rényi random graph with n nodes and probability p. Then, the Estrada index is (5.16) almost surely (a.s.) if and only if limn→∞ n 2 /n 1 = 1.

EE (Gn,p) = e O( √ n) + o (1) e np ,
In the case of Erd®s-Rényi random bipartite graphs the author of [206] proved the following bounds for the Estrada index.

Theorem 17 Let Gn 1 ,n2,p be an Erd®s-Rényi random bipartite graph with n = n 1 +n 2 nodes, such that limn→∞ n 2 /n 1 := y ∈ (0, 1], and probability p. Then, the Estrada index is bounded as

e O( √ n) + o (1) e n2p ≤ EE (Gn,p) ≤ e O( √ n) + O (1) e n1p , a.s.
(5.17)

provided that y = 1.

Estrada index and statistical mechanics

The analogy of the Estrada index EE (G) = tr e A with the partition function of a quantum system Z = tr e -τ H (see further for denitions) is remarkable, and was noticed soon after the denition of this index [START_REF] Estrada | Statistical-mechanical approach to subgraph centrality in complex networks[END_REF]. The importance of establishing this connection is twofold. On the one hand, the index can be interpreted in a physical context which at the same time facilitates its interpretation in other contexts where it is applied. On the other hand, new tools and techniques from statistical mechanics can be used to enrich the theory behind this index. Here, we will describe the statistical mechanics interpretation of the Estrada index.

Let us consider a physical system S that can be represented by a graph G, such that the total energy E of S can be obtained by the time-independent Schrödinger equation: ĤΨ = EΨ , where Ψ is the wavefunction and Ĥ is the Hamiltonian describing the interactions between the elements of S. In certain approaches in physics and chemistry, it is customary to use an eective Hamiltonian which describes the interaction between nearest-neighbors (NN) in the system

ĤNN = αI + t N N A, (6.1)
where α is a self-energy parameter for the elements of S and t N N is the energy of the interaction between pairs of adjacent elements. In Chemistry this model is known as the Hückel Molecular Orbital (HMO) method [154,239], while in Physics it is better known as the tight-binding approach [184]. The parameter t N N is negative as it is supposed to be an attractive interaction. Therefore, it is common to set α = 0 and t N N = -1, such that Ĥ = -A. Therefore, the energy levels of the system are E j = -λ j and the wavefunctions correspond to the eigenvectors associated to the eigenvalues of A.

In the statistical mechanics framework [START_REF] Beaudin | A little statistical mechanics for the graph theorist[END_REF][START_REF] Essam | Graph theory and statistical physics[END_REF], the Boltzmann probability p j (τ ) of nding the system in a state with energy E j when the inverse temperature of the

system is τ = (k B T ) -1 > 0 with k B being a constant and T being the temperature 1 is p j (τ ) = e -τ Ej Z , (6.2)
where Z = tr e -τ ĤNN . Therefore, the Boltzmann probability of the system is given by

p j (τ ) = e τ λj EE (G, τ ) , (6.3)
where the Estrada index plays the role of the partition function of the graph.

We now can dene the entropy of the graph as [START_REF] Estrada | Statistical-mechanical approach to subgraph centrality in complex networks[END_REF] S (G, 6.4) which in general is bounded as follows.

τ ) = -k B j p j (τ ) ln p j (τ ) = - 1 T j (p j (τ ) λ j ) + k B ln EE (G, τ ) , (
1 τ is typically represented by β in statistical physics, but this letter is already reserved here for a dierent variable Lemma 5 Let G be a simple graph. Then, the free energy of G is bounded as

0 ≤ ln (exp (n) + n -1) - n exp (n) exp (n) + n -1 ≤ S (G, τ ) ≤ ln n, (6.5)
where the upper bound is attained for the null graph Kn and the lower bound is reached for the complete graph Kn.

From the general expression of the entropy one can obtain the graph enthalpy H (G, τ ) = j p j λ j and the graph free energy, which is sometimes named the natural connectivity of the network [START_REF] Estrada | Statistical-mechanical approach to subgraph centrality in complex networks[END_REF]:

F (G, τ ) = -τ -1 ln EE (G, τ ) . (6.6)
We can write the logarithm of the Estrada index as follows,

ln EE (G, τ ) = τ λ 1 + ln j e τ (λj-λ1) , (6.7)
which implies that

ln EE (G, τ ) ≤ τ λ 1 + ln 1 + e -τ △ , (6.8)
where △ = λ 1 -λ 2 is the spectral gap. Therefore, we have proved the following.

Lemma 6 Let G be a simple graph. Then, the free energy of G is bounded as

F (G, τ ) ≤ -λ 1 + τ -1 ln 1 + e -τ △ . (6.9)
More generally, the free energy of a graph can be bounded by using the many bounds obtained for the Estrada index which have been previously reported in the literature.

One important example is the following [START_REF] Estrada | Statistical-mechanical approach to subgraph centrality in complex networks[END_REF].

Lemma 7 Let G be a simple graph. Then, the free energy of G is bounded as 6.10) where the lower bound is obtained for the complete graph Kn and the upper bound for the null graph Kn.

(n -1) < 1 -τ -1 ln (e τ n + n -1) ≤ F (G, τ ) ≤ -τ -1 ln n, (

Numerical analysis

We consider here numerical experiments to illustrate some general characteristics of the indices described in the previous section. We report the change of the entropy, enthalpy and free energy of all connected graphs with the increase of the number of edges in the connected graphs with 8 nodes, i.e., its edge density. It can be seen in Fig. 6.1, as expected, that the three parameters decay with the increase in the edge density. However, it should be noticed that for graphs with exactly the same number of edges there is a wide variability in these parameters, particularly for the entropy.

The readers interested in more details about the implications of these parameters on the structure of graphs are referred to [START_REF] Estrada | Statistical-mechanical approach to subgraph centrality in complex networks[END_REF]. We then computed the three statistical mechanics parameters for the ve networks studied here. The results are in Table 6 where we also give the values of the edge density of these graphs: δ (G) = 2m/ (n (n -1)) where n and m are the number of nodes and edges of the graph. The most densely connected network, Stony, displays the lowest entropy and the least dense, powergrid, displays the largest one. However, as can be seen for the intermediate values of δ (G) this trend is not always followed as there are other structural factors inuencing these statistical mechanics parameters.

For instance, the network of Internet at AS displays the second smaller entropy of all the networks and the lowest free energy of all, although it is not very dense. 7 Marginal probability, walk entropy and walk regularity

S (G)

H (G) F (G) δ (G) Stony 4.
Having in mind the importance that the probability p j (τ ) has in the denition of sta- tistical mechanics properties of networks we propose to explore it further in this section.

That is, we consider here the role of the Estrada index in dening some probabilitybased measures for graphs. Let us start with two denitions from basic statistics (see for instance Ch. 2 [START_REF] Cox | Causal analytics for applied risk analysis[END_REF]).

Denition 9 The conditional probability P (A |B ) is the probability that the event A occurs given that the event B occurs.

Denition 10 The marginal probability is the unconditional probability of one event A. That is, the probability that A occurs regardless of whether B occurs or not.

To obtain the marginal probability of an event A one should sum all possible congurations of the other event to obtain a weighted average probability

P (A) = B P (A |B ) • P (B) . (7.1)
Let us then return to the time-independent Schrödinger equation:

Ĥψ j = E j ψ j , (7.2)
where E j are the energy levels of the system and ψ j are the corresponding eigenfunc-

tions. As usual, ψ j,v 2
represents the probability of nding a quantum particle at a given vertex v and time conditional to the system to be at the energy level described by the wave function ψ j . That is, ψ j,v 2 = P (v |j ) using the notation dened before.

On the other hand, p j (τ ) which was dened in the previous section accounts for the probability that the system is at the jth energy level for a given τ . Then, xing τ , p j (τ ) = P (j) . Therefore, the marginal probability that the node v is occupied by the quantum particle independently of the energy level in which the system is, is given by:

P (v) = j P (v |j ) • P (j) = j ψ j,v 2 • p j (τ ) , (7.3)
which can be expressed as [START_REF] Estrada | Walk entropies in graphs[END_REF]:

P (v, τ ) = j ψ 2 j,v e τ λj EE (G, τ ) = EEv (τ ) EE (G, τ ) . ( 7.4)
The corresponding entropy, known as the walk-entropy of the graph [START_REF] Estrada | Walk entropies in graphs[END_REF], is dened using Shannon formula:

S w (τ ) = - v P (v, τ ) ln P (v, τ ) . (7.5)
We now consider a graph property known as walk-regularity and the role that the walk entropy play in its characterization. Let us introduce the concept of walk regularity rst (see for instance [106]).

Denition 11 A graph is walk-regular if ∀i, j ∈ V and for every nonnegative integer

r, [A r ] ii = [A r ] jj .
The following conjecture was formulated in [START_REF] Estrada | Walk entropies in graphs[END_REF] as an extension of the conjecture related to the subgraph centrality which had been previously stated in [START_REF] Estrada | Subgraph centrality in complex networks[END_REF].

Conjecture 1 A graph is walk-regular if and only if S w (τ ) = ln n for all τ > 0.

Let us then introduce some necessary concepts for the further developments in the proof of this conjecture.

Denition 12 Two vertices i,

j of G are τ -subgraph equivalent if [e τ A ] ii = [e τ A ] jj .
Denition 13 A graph is τ -subgraph regular if all pairs of vertices are τ -subgraph equivalent.

The following result was a step forwards the proof of Conjecture 1.

Theorem 18 [START_REF] Benzi | A note on walk entropies in graphs[END_REF] A graph G is walk-regular if and only if G is τ -subgraph regular for all τ ∈ I ⊆ R, where I is any set of real numbers containing an accumulation point.

In the saga, in [151] the authors found some counterexamples to a new conjecture proposed in [START_REF] Benzi | A note on walk entropies in graphs[END_REF] and stated a new conjecture. The nal proof of Conjecture 1 came from an elegant Theorem in 2021 [START_REF] Ballini | Vertex distinction with subgraph centrality: A proof of Estrada's conjecture and some generalizations[END_REF] where the authors used results from the Lindemann-Weierstrass Theorem.

Theorem 19 [START_REF] Ballini | Vertex distinction with subgraph centrality: A proof of Estrada's conjecture and some generalizations[END_REF] Let τ > 0 be an algebraic number and let G be a connected undirected graph with adjacency matrix A.

1. G is τ -subgraph regular if and only if G is walk-regular. 2. If two vertices i, j are τ -subgraph equivalent, then the degree and eigenvector centralities of i and j are equal.

3. If G is τ -subgraph regular, then the degree and eigenvector centralities are also identical for all nodes.

Walk regular graphs can be constructed by using Kronecker product of the adjacency matrices of two walk-regular graphs [106]. That is, if G 1 and G 2 are walk regular graphs, then G 1 ⊗ G 2 is also walk regular. Therefore, we have the following result.

Proposition 1 [START_REF] Estrada | Walk entropies in graphs[END_REF] Let G 1 and G 2 be two simple graphs with n 1 and n 2 vertices, respectively. Then,

S w (G 1 ⊗ G 2 , τ ) = ln n 1 + ln n 2 , (7.6)
for all τ > 0 if G 1 and G 2 are walk-regular.

8 Bipartivity, signed graphs and Seidel Estrada index

A graph G = (V, E) is bipartite if its set of nodes V can be split into two subsets V 1 and V 2 such that there are edges only between the two sets but no edge connects vertices in neither V 1 nor V 2 . Therefore, a graph is or is not bipartite. However, in certain real-world situations a graph can be close to bipartite, meaning that by removing very few edges the graph become bipartite. This is the case, for instance, of human sexual contact networks and human romance or partnership networks as remarked in [130]. In 2003 the authors of [130] proposed to quantify the bipartivity of a graph.

The rst of their measures is dened by

b H = 1 - m f m , (8.1)
where m f is the number of edges that if removed the network becomes bipartite 2 .

The calculation of this index is computationally intractable as it is NP complete. The authors [130] then proposed another index in which m f is assessed computationally.

Here we will show how the use of the Estrada index of graphs allows the calculation of an index of bipartivity which depends only on the eigenvalues of the graph. The rst of these approaches was published in [START_REF] Estrada | Spectral measures of bipartivity in complex networks[END_REF] and will not be discussed here. Instead we will consider the index studied in [START_REF] Estrada | Network bipartivity and the transportation eciency of european passenger airlines[END_REF]. Another measure of bipartivity was also proposed in [180]. We will start with some basic denitions for the sake of completeness of this section.

A bipartite graph is characterized by the following result proved by Konig in 1916

[153] (see also [START_REF] Asratian | Bipartite graphs and their applications[END_REF]).

Theorem 20 A graph is bipartite if and only if G has no cycles of odd length.

Corollary 2 A graph G is bipartite if and only if it contains no closed walks of odd length.

The Estrada index of a graph can be expressed in terms of the hyperbolic matrix functions as

EE (G) = tr (cosh (A)) + tr (sinh (A)) . (8.2)
The tr (sinh (A)) counts the odd-length closed walks in the graph:

tr (sinh (A)) = ∞ k=0 1 (2k + 1)! tr A 2k+1 . (8.3)
Similarly, tr (cosh (A)) counts the even-length closed walks. An odd closed walk of any length in the graph exists if and only if the graph contains at least one odd-length cycle. Therefore, we can reformulate the previous Corollary as. Corollary 3 A graph G is bipartite if and only if tr (sinh (A)) = 0.

Based on this result the authors of [START_REF] Estrada | Network bipartivity and the transportation eciency of european passenger airlines[END_REF] proposed the following. Denition 14 The bipartivity of a graph is dened as the relative dierence between the number of closed walks of even and odd length,

b (G) = tr (cosh (A)) -tr (sinh (A)) tr (cosh (A)) + tr (sinh (A)) = tr (exp (-A)) tr (exp (A)) = EE G - EE (G)
, (8.4) where G -is the graph in which all the edges are weighted by -1.

It is easy to see that tr (exp (-A)) reaches its minimum for the complete graph, which is also the graph for which EE (G) is maximum (see an example in Fig. 8.1). In this gure the reader can also visualize how the bipartivity index changes monotonically with the increase of the number of edges frustrating the bipartition.

Then, we have the following result.

Lemma 8 Let G be a simple graph. Then, its bipartivity is bounded as

e 2-n ne n -e n + 1 e n + n -1 ≤ b (G) ≤ 1, (8.5)
where the upper bound is attained for any bipartite graph and the lower bound is reached

for G ∼ = Kn.
Therefore, we have that lim n→∞ b (Kn) = 0. Therefore, the numerator of b (G) counts the number of negative cycles in G, where a negative cycle is any cycle in which the product of the sign of its edges is negative. In a fully-negative graph, the negative cycles are the odd-length cycles, which are indeed those that break the bipartivity of the graph. In the theory of signed graphs we have the following important concept (for a list of references and some critical account see [START_REF] Estrada | Rethinking structural balance in signed social networks[END_REF]).

Denition 16 A signed graph G +-is balanced if all its cycles are positive.

Then, it is obvious that a fully-negative graph is balanced if and only if it is bipartite. In the general case of any signed graph the following result is well-known.

Theorem 21 A signed graph G +-is balanced if and only if its nodes can be separated into two mutually disjoint sets, such that positive edges joint nodes only inside the subsets and negative edges joint nodes from dierent subsets.

The adjacency matrix of a signed graph can be expressed as: A = A + -A -, where A + represents the adjacency between pairs of nodes connected by positive edges, and A -represents the adjacency between pairs of nodes connected by negative edges.

Denition 17 [START_REF] Estrada | Rethinking structural balance in signed social networks[END_REF][START_REF] Estrada | Walk-based measure of balance in signed networks: Detecting lack of balance in social networks[END_REF] The balance of a signed network with adjacency matrix A =

A + -A -can be quantied by

K G +-= tr exp A + -A - tr (exp (|A + -A -|)) = EE G +- EE (|G +-|) , (8.7)
where |•| represents the entrywise absolute of the corresponding matrix.

The following result was proved in 1980 [START_REF] Acharya | Spectral criterion for cycle balance in networks[END_REF].

Theorem 22 For any signed graph, the matrices A + -A -and A + -A -are isospectral (cospectral) if and only if the signed graph is balanced.

Then, we have the following.

Theorem 23 Let G +-be a signed graph with adjacency matrix A + -A -. Then,

e 2-n ne n -e n + 1 e n + n -1 ≤ K G +-≤ 1, (8.8)
where the upper bound is attained for any balanced graph and the lower bound is reached for a fully-negative complete graph.

Then, we also have that

lim n→∞ K K - n = 0, (8.9)
which is a maximally unbalanced graph.

Seidel Estrada index

Let us focus now on a particular kind of signed graph. Let J and I be the all-ones and identity matrices, respectively. The following matrix was introduced in [221] and it is nowadays known as the Seidel matrix. Denition 18 The Seidel matrix of a simple graph G with adjacency matrix A is dened as

S (G) = J -I -2A. (8.10)
Obviously, S (G) = A + -A -is the adjacency matrix of a signed graph G +-, where

A + =J -I -A and A -= -A. Therefore, we have the following result.

Theorem 24 Let G +-be a signed graph with adjacency matrix S (G). Then, G is balanced if and only if S (G) is isospectral to A (Kn).

Proof The balance index of a signed graph with adjacency matrix S (G) is

K G +-= tr (exp (J -I -2A)) tr (exp (J -I)) = tr (exp (S (G))) EE (Kn)
, (8.11) which immediately implies the result.

⊓ ⊔

Remark 3 The term tr (exp (S (G))) =: SEE (G) was denoted in [122] as the Seidel Estrada index of the graph. The name Seidel honors mathematician Johan Jacob Seidel 4 .

We can prove here the following result.

Theorem 25 Let Kn 1 ,n2 be a complete bipartite graph. Let S (Kn 1 ,n2 ) be the Seidel matrix of Kn 1 ,n2 . Then, S (Kn 1 ,n2 ) and A (K n1+n2 ) are cospectral.

Proof Using the structural balance theorem we can show that the signed graph whose adjacency matrix is S (Kn 1 ,n2 ) is balanced. That is, we can split the set of nodes into two disjoint sets containing n 1 and n 2 nodes, respectively, in which the inter-set edges are negative and all intra-set edges are positive. Then, using Theorem 24 we prove the result.

⊓ ⊔

Remark 4 The previous result implies that any signed graph with adjacency matrix

A = A (Kn 1 ) -J -J A (Kn 1 )
, (8.12) is balanced. Also that SEE (Kn

1 ,n2 ) = EE (K n1+n2 ) = exp (n) + (n -1) e -1 .
In [122] it was proved the following results for the Seidel Estrada index.

Theorem 26 Let G be a simple graph with n ≥ 2 nodes, m edges, t triangles and

Z = i k 2 i . Then, SEE (G) > n 3 n 3 -n + 12 Z + 4t -nm + 1 2 . ( 8.13)
Theorem 27 Let G be a simple k-regular graph. Then,

SEE (G) ≥ e n-1-2k + (n -1) exp 2k n -1 -1 . (8.14)
Theorem 28 Let G be a simple k-regular bipartite graph. Then, .15) In this subsection we have shown that although the so-called Seidel Estrada index was proposed and studied in a completely ad hoc way, it can be connected with the theory of signed graphs. This may facilitate further studies of this index, its extension to consider statistical mechanics parameters and its applications to the study of real-world signed graphs. Graphically, it corresponds to the slope of the curve of entropy versus energy at a given point. Therefore, as can be seen in Fig. 8.2 the inverse temperature can be negative. In a system at negative temperature the high-energy states are more occupied than low-energy states. Such systems have been created by physicists in the real-world [START_REF] Braun | Negative absolute temperature for motional degrees of freedom[END_REF]. From a graph-theory perspective what it means that the high-energy states are more occupied than low-energy states ? In the Section 6 we have considered that the Hamiltonian describing the graph as a quantum system is given by the negative of the adjacency matrix ĤNN = -A, such that the energy levels of the system are E j = -λ j and the wavefunctions are the eigenvectors associated to the eigenvalues of A. In this case the partition function of the graph is given by Z = n j=1 e τ λj with τ > 0. Therefore, for τ → ∞, we have that Z = e τ λ1 . In the current case, where τ < 0, we have that when τ → -∞, the partition function is: Z = e τ λn . This means that we have changed the importance given to the dierent eigenvalues in the Estrada index, giving now more weight to the contributions of the smallest ones. Because Lars Onsager (1903Onsager ( -1976) ) was the scientist who rst study the negative absolute temperatures in [178] we propose to name the following index in his honor

SEE (G) < e n-1-2k + 1 e EE (G) -e -k 2 . ( 8
OEE (Kn 1 ,n2 ) = EE (Kn 1 ,n2 ) = n 1 + n 2 -2 + 2 cosh ( √ n 1 n 2 ) ; OEE (Sn) = EE (Sn) = n -2 + 2 cosh √ n -1 ; limn→∞ EE (Cn) = nI 0 , n even, where I 0 = 1 π π 0 e 2 cos x dx; limn→∞ EE (Pn) = (n -1) -2 cosh (2).
Lemma 10 Let G be a simple graph and let λn be the least eigenvalue of A. Then, e -λn ≤ OEE (G) ≤ ne -λn .

(8.18)

The following result allows us to compare OEE (G) with EE (G) using Eq. (3.12).

Lemma 11 Let G be a simple graph. Then, the Onsager Estrada index of G is bounded as OEE (G) Here we compute the bipartivity index for all connected graphs with 8 nodes. We select two other network parameters to compare with the bipartivity. The rst is the edge density δ (G) = 2m/ (n (n -1)) where m is the number of edges. The reason for selecting this parameter is that as the density of the graph increases the number of cycles of any length will also increase. For instance, in Erd®s-Rényi random graphs we can nd that the number of triangles F 4 (see Fig. 3.1) is bounded as

F 4 ≥ 1 6 λ 3 1 ≥ 1 6 (np) 3 = 1 6 n 3 δ 3 . (8.20)
The second parameter is the clustering coecient C (G), which is dened as C (G) = 3F 4 /F 3 , where F 3 is the number of paths of length 2 in the graph (see [START_REF] Estrada | The structure of complex networks: theory and applications[END_REF]). Here again we would expect that the bipartivity and the clustering coecient are negatively correlated due to the fact that the increase in clustering means the relative increase in the number of triangles. However, bipartivity is also related to other odd-cycles in the graphs and we want to investigate their inuence of this network parameter.

In Fig. 8.3 we plot the results of the bipartivity vs. the clustering coecient where the points are colored according to the number of edges that the graph has. As can be seen the most dense graphs also have the highest clustering and lowest bipartivity, as expected. Although there is a decaying trend between the bipartivity and the clustering coecient, it is clear that even for these small graphs, the contribution of longer cycles to the bipartivity is very important. In

b (G) C (G) δ (G) Stony 6.3 • 10 -1 2.0 • 10 -2 1.3 • 10 -1 neurons 1.2 • 10 -5 1.9 • 10 -1 5.1 • 10 -2 yeast 4.9 • 10 -4 1.6 • 10 -1 2.8 • 10 -3 Internet 4.3 • 10 -3 1.5 • 10 -2 1.1 • 10 -3 Powergrid 7.2 • 10 -1 1.0 • 10 -1 5.4 • 10 -4
Table 7: Values of the bipartivity, clustering coecient and edge density of the ve real-world networks studied in this paper.

In the case of Stony we have obtained a bipartition of the network using a technique also based on matrix exponentials. The result is illustrated in Fig. 8.4 where the edges colored in red or in blue are those that frustrate the bipartition of the network, i.e., those that, if removed, make the graph bipartite. developed by [START_REF] Estrada | Network bipartivity and the transportation eciency of european passenger airlines[END_REF]. The dotted lines joints the two partitions and continuous lines connect vertices inside the same partition, i.e., they frustrate the bipartition of the network.

Gaussian Estrada indices

As we have seen in the previous analysis there are situations in which the Estrada index of a graph is mainly determined by the spectral radius of the adjacency matrix. That is, when λ 1 ≫ λ 2 ≫ 1 the sum j exp (λ j ) is approximated very well by exp (λ 1 ) . From the structural point of view, this means that most of the information contained in the eigenvalues λ j for j > 1 is making almost no contribution to the Estrada index. It is well-known that structural information encoded by some other eigenvalues other than λ 1 is very important for several kinds of problems [START_REF] Chung | Spectral graph theory[END_REF]5052,213,214]. For instance, the nullity of the graph (see [111] for a review), i.e., the multiplicity of the zero eigenvalue of the adjacency matrix, plays a fundamental role in explaining magnetic properties of materials [230]. In general, many real-world networks have large multiplicity of λ j = 0 (nullity) and of λ j = -1 which points to the fact that some important structural information on these networks is encoded in eigenvalues dierent from λ 1 .

In this section we investigate Estrada indices that give higher weights to the contribution of eigenvalues other than the spectral radius. In particular we use here a technique known as spectral folding [START_REF] Canning | Parallel empirical pseudopotential electronic structure calculations for million atom systems[END_REF]229] to produce Gaussian Estrada indices [START_REF] Alhomaidhi | Gaussianization of the spectra of graphs and networks. theory and applications[END_REF][START_REF] Estrada | Exploring the "middle earth" of network spectra via a gaussian matrix function[END_REF]. In the following let λ be a given reference eigenvalue, I (z) be the modied Bessel function of the rst kinds, erf (z) be the error function and erfc (z) = 1erf (z)

be the complimentary error function [START_REF] Alhomaidhi | Gaussianization of the spectra of graphs and networks. theory and applications[END_REF][START_REF] Estrada | Exploring the "middle earth" of network spectra via a gaussian matrix function[END_REF]. Denition 20 The Gaussian Estrada index of G is dened as

GEE λ (G) = tr exp -λI -A 2 . ( 9.1)
The idea behind this Gaussian Estrada index is explained graphically in Fig. 9.1.

The name Gaussian honors Carl Friedrich Gauss (1777-1855)

6 .

First we give a few general results for the Gaussian Estrada index (see [START_REF] Alhomaidhi | Gaussianization of the spectra of graphs and networks. theory and applications[END_REF][START_REF] Estrada | Exploring the "middle earth" of network spectra via a gaussian matrix function[END_REF]).

Lemma 12 Let G be any graph. Then,

GEE λ (G) = tr e -λ2 e 2 λA e -A 2 = e -λ2
tr e 2 λA e -A 2 .

(9.2)

Theorem 29 Let G be a graph with n nodes and m edges. Then,

GEE λ (G) ≤    EE Kn, λ if λ ref = 0, EE K 1,n-1 , λ if λ ref = -1, (9.3)
where k i is the degree of the node i in the graph G .

Lemma 13 Let Kn be the complete graph of n nodes. Then Lemma 15 Let Cn be a cycle having n nodes. Then, asymptotically as n → ∞ and for some c ∈ (0, π)

GEE λ (Kn) =      e -(n-1) 2 + n-1 e if λ = 0, e -n 2 + n -1 if λ = -1.
GEE λ (Cn) =    e -2 nI 0 (-2) if λ = 0, ne -3 e -4 cos c I 0 (-2) if λ = -1. (9.6)
Lemma 16 Let Kn 1 ,n2 be the complete bipartite graph of n 1 + n 2 nodes. Then

GEE λ (Kn 1 ,n2 ) =    2e -n1n2 + n 1 + n 2 -2 if λ = 0, e -1 e -n1n2 cosh(2 √ n 1 n 2 ) + n 1 + n 2 -2 if λ = -1. (9.7)
Corollary 4 Let K 1,n-1 be the star graph of n nodes. Then

GEE λ (K 1,n-1 ) =    2e 1-n + n -2 if λ = 0, e -1 e 1-n cosh(2 √ n -1) + n -2 if λ = -1. (9.8)
In [210] the authors studied several bounds for the Gaussian Estrada index when λ = 0 which are resumed below.

Theorem 30 Let G be a simple graph with n nodes and m ≤ n 2 edges and let λ = 0.

(G) = 2m/ (n (n -1)) is bounded as δ (G) ≤ 1 2 (n -1)
+ e -4m/n .

M = i k 2 i , then, GEE 0 (G) ≥ exp (-M/n) + (n -1) exp ((M/n -2m) / (n -1)) , (9.12)
with equality attained if and only if

G admits λ 1 = M/n , λ 2 = • • • = λ k = (n -2k + 1) -1 M/n and λ k+1 = • • • = λn = -(n -2k + 1) -1 M/n for some 1 ≤ k ≤ n 2 .

Random graphs

In this subsection we consider the estimation of the Gaussian Estrada indices of random graphs. The reasons for studying random graphs have been explained in Section 5.2.

Here we will consider both Erd®s-Rényi and Barabási-Albert random graphs.

Theorem 33 [START_REF] Alhomaidhi | Gaussianization of the spectra of graphs and networks. theory and applications[END_REF][START_REF] Estrada | Exploring the "middle earth" of network spectra via a gaussian matrix function[END_REF] For an Erd®s-Rényi random graph Gn,p with ln n n ≪ p for signicantly large r = 2 np (1 -p), we have

GEE λ (Gn,p) = n exp -r 2 2 I 0 r 2 2 + I 1 r 2 2 , (9.13)
if λ = 0, and

GEE λ (Gn,p) = 2n √ r 2 -1 r e r 2 erfc (r) (9.14) if λ = -1, as n → ∞.
Theorem 34 [START_REF] Alhomaidhi | Gaussianization of the spectra of graphs and networks. theory and applications[END_REF][START_REF] Estrada | Exploring the "middle earth" of network spectra via a gaussian matrix function[END_REF] Let G BA be a Barabási-Albert random graph and let r = 2 np (1 -p).

Then, when n → ∞,

GEE λ (G BA ) = n r 2 √ πrerf (r) + e -r 2 -1 , (9.15)
if λ = 0, and 9.16) if λ = -1.

GEE λ (G BA ) = √ π 2 ((1 -r) erf (1 -r) + (1 + r) erf (1 + r)) - √ πerf (1) -e -1 (

Double Gaussian Estrada index

Another important situation appearing in many molecular systems is the existence of two reference eigenvalues, typically located around the mid part of the spectrum, which are of great relevance for understanding the behavior of these systems. In 1952, Fukui et al. [START_REF] Fukui | A molecular orbital theory of reactivity in aromatic hydrocarbons[END_REF] calculated the chemical reactivity of molecules by using molecular orbital theory, but their method neglects all molecular orbitals except two, the occupied one of higher energy (HOMO) and the vacant one of lowest energy (LUMO). According to Fukui the HOMO gives a molecule a character of electron donor, whereas the LUMO acts as an electron acceptor. The theory was further applied by Woodward and Homann [234] in the interpretation of the stereochemistry of electrocyclic organic reactions. Both, the Frontiers Molecular Orbital (FMO) theory of Fukui and the Woodward-Homann rules are paradigmatic examples of success of theoretical approaches in Chemistry.

Both Fukui and Homann won the Nobel Prize in Chemistry for such works. Since then [START_REF] Fukui | The role of frontier orbitals in chemical reactions (nobel lecture)[END_REF], FMO is widely applied for studying chemical reactivity [176].

Let us consider here, for instance, molecular systems S where the energy E is obtained by the time-independent Schrödinger equation: (αI + t N N A) Ψ = EΨ , as described before. Then, when α = 0 and t N N = -1, the energy levels of the system are E j = -λ j . Typically, the states with energy levels E j < 0 are occupied by electrons, while those with energy E j ≥ 0 are empty. Then, the energy level just below E j = 0 is known as the highest occupied molecular orbital (HOMO) and the one just over E j = 0 is the lowest unoccuppied molecular orbital (LUMO). These two molecular orbitals are fundamental in understanding the chemical reactivity of these molecular systems [182]. They can be described in the current approach by the negative of two references eigenvalues λ1 and λ2 of the adjacency matrix. Then, we have the following 2 tr e 2( λ2

1 λ2+ λ1 λ2
2 )A e -( λ21 + λ2 2 +4 λ1 λ2)A 2 e 2( λ1+ λ2)A 3 e -A 4 .

(9.18)

Lemma 18 Let λ1 = -1 and λ2 = 1, such that EE (G, -1, 1) = tr exp -A 2 -I 2 .

Let Kn, Kn 1 ,n2 and K 1,n-1 be the complete, bicomplete and star graphs of n nodes, respectively. Then

DGEE -1,1 (Kn) = n -1 + e -n 2 (n-2) 2 , (9.19) DGEE -1,1 (Kn 1 ,n2 ) = n 1 + n 2 -2 e + 2e -(n1n2-1) 2 , (9.20) DGEE -1,1 (K 1,n-1 ) = n -2 e + 2e -(n-2) 2 . ( 9

Numerical analysis

We consider here the bounds given in Theorem 30 and in Theorem 32 for all connected graphs with 8 nodes. The bound given in Theorem 31 is not applicable in all the cases and we do not considered it for this general case. We show in Fig. 9.3 the histogram of the relative deviations for these two bounds in these small graphs. The mean relative deviations (in %) of the two bounds are, respectively 89.84 ± 2.51 and 66.51 ± 6.55, which points to the fact that the second bound is a better approximation than the rst one to the Gaussian Estrada index.

In Table 8 we give the values of the three bounds for the ve networks studied here as well as the values of the actual Gaussian Estrada index for λ = 0.

(t) = M u (t) , (10.1)
where M is a given graph matrix, with initial condition u (0) = u 0 . The solution of this system is given by u (t) = exp (tM ) u 0 . The case in which M = A is the adjacency matrix of the graph has been analyzed in the paper [172]. for the Gaussian Estrada index GEE 0 (G) of the ve real-world networks studied here.

The bound given in Theorem 31 is not applicable (NA) for most of the networks as they do not fulll the necessary condition on the edge density.

Let us consider that, instead of using the rst derivative of u (t) respect to time, we use a fractional derivative. Then we have a system of the form:

D α t u (t) = M u (t) , (10.2)
for 0 < α < 1, where the Caputo fractional derivative [START_REF] Caputo | Linear models of dissipation whose q is almost frequency independentii[END_REF] is given by (10.3) where f (k) represents the kth derivative of f and Γ (z) is the Euler gamma function:

D α t u (t) = 1 Γ (⌈α⌉ -α) t 0 u (⌈α⌉) (τ ) (t -τ ) α+1-⌈α⌉ dτ,
Γ (z) = x z-1 e -x dx, Re (z) > 0. (10.4)
The solution of this system is given by

u (t) = E α,1 (t α M ) u 0 , (10.5) where E α,1 (t α M ) = ∞ k=0 (t α M ) k Γ (αk + β)
, (10.6) which are the Mittag-Leer matrix functions (for properties of Mittag-Leer matrix function the reader is referred to [102,183])

To catch the analogy with the standard Estrada index of a graph we can write is as

EE (G) = tr ∞ k=0 A k Γ (k + 1) = tr (exp (A)) , (10.7)
due to the fact that Γ (k + 1) = k!,

Therefore we can generalize the Estrada index to account for a wider class of penalization functions, such that we write

EE α,β (G) = tr ∞ k=0 A k Γ (αk + β) . (10.8)
At the same time we keep in mind that EE α,β (G) is the solution of a system of equations of the form D α t u (t) = Au (t) as we will explore later. We propose the name Mittag-Leer Estrada index for EE α,β (G) in honor to the mathematician Gösta Mittag-Leer 7 . Some examples of closed formulas are illustrated in Table 9. One important aspect of these functions in general is that by controlling the parameters α and β we can penalize the walks of k length in dierent ways. For instance, if ((α -1) k + β) < 0 for all k, then the walks of any length are penalized less than in EE 1,1 (G). This is for instance, the case of EE 1/2,1 (G) (see Table 9). In those cases where ((α -1) k + β) > 0 for all k, the penalization of all walks is heavier than in the exponential, which are for instance the cases of EE α>1,β (G). There is a third case which occurs when (α -1) k + β is negative for 0 ≤ k ≤ kc and positive for k > kc,

α β function 1/2 1 exp A 2 (I + erf (A)) 1 1 exp (A) 2 1 cosh √ A 3 1 1 3 exp A 1/3 + 2 exp -A 1/3 cos √ 3 2 A 1/3 4 1 1 2 cos A 1/4 + cosh A 1/4
where kc is a given integer. This is the case, for instance, of the matrix functions where

kc < - β α -1 . Let us rst consider the Estrada index EE 1/2,1 (G) = tr exp A 2 (I + erf (A)) .
A similar index was dened and studied in the paper [START_REF] Estrada | Accounting for the role of long walks on networks via a new matrix function[END_REF] in the following form:

7 A biography of Gösta Mittag-Leer can be found at: https://mathshistory.st- .9) where k!! is the double factorial of k. The goal of dening such index was to account for less penalization of longer walks, which may play an important role in several applications (for some examples see [START_REF] Abadias | Fractional-order susceptible-infected model: denition and applications to the study of covid-19 main protease[END_REF][START_REF] Estrada | Accounting for the role of long walks on networks via a new matrix function[END_REF]) . For instance, if we compare the subgraph expansion of EE 1/2,1 (G) with that of EE 1,1 (G) (see Eq. ( 3.12)) we can clearly observe the dierences in the penalization of bigger subgraphs made by both indices. In the case of EE 1/2,1 (G) we have: .11) These indices were developed and studied in 2010 in the paper [START_REF] Estrada | Generalized walks-based centrality measures for complex biological networks[END_REF], as a way to penalize more heavily the longer walks than in the matrix exponential. The indices EE 1,β+1 (G) are also the trace of the so-called matrix Ψ functions:

andrews.ac.uk/Biographies/Mittag-Leer/ ∞ k=0 A k k!! = tr 1 2 exp A 2 2 2I + √ 2πerf A √ 2 , ( 10
EE 1/2,1 (G) ≈ F 1 + 10 3 F 2 + 4F
M T EE 1,β+1 (G) = tr ∞ k=0 A k Γ (k + β + 1) = tr ∞ k=0 A k (k + β)! , β = 1, 2, 3, • • • . ( 10
M T EE 1,β+1 (G) = trΨ β (A) , (10.12)
where

Ψγ (A) := 1 (β -1)! 1 0
e (1-t)A x t-1 dt, (10.13) which obey the following recurrence formula: .14) When the adjacency matrix is not singular we can represent these Estrada indices as follow

Ψ β (A) = AΨ β+1 (A) + 1 β! I. ( 10
M T EE 1,2 (G) = tr (Ψ 1 (A)) , (10.15) M T EE 1,3 (G) = tr (Ψ 2 (A)) , (10.16)
and so forth. Other Mittag-Leer matrix functions in the context of network theory have been recently studied in [START_REF] Arrigo | Mittag-leer functions and their applications in network science[END_REF].

Resolvent Estrada index

The context of Mittag-Leer Estrada indices also allow the consideration of other indices that were previously proposed in the literature. This is the case of an index proposed in 2010 in [START_REF] Estrada | Network properties revealed through matrix functions[END_REF]. The goal of introducing this index was to change the penalization of the dierent powers of the adjacency matrix from k! to (n -1) k to increase the contribution of walks of longer lengths. The index proposed in [START_REF] Estrada | Network properties revealed through matrix functions[END_REF] corresponds to the trace of the resolvent of the adjacency matrix:

REE (G) = tr ∞ k=0 A k (n -1) k = tr I - 1 n -1 A -1
, (10.17) which eventually was proposed in [START_REF] Benzi | Quadrature rule-based bounds for functions of adjacency matrices[END_REF] to be named as the resolvent Estrada index of the graph. It can be seen that the resolvent Estrada index is a particular case of Mittag-Leer Estrada index:

REE (G) = M T EE 0,1 (G) = tr ∞ k=0 (A/n) k Γ (αk + β) = tr I - A n -1
. (10.18) Remark 7 The use of the normalization c k = 1/ (n -1) in (c k A) k is just one of the many possibilities that exist. In reality this normalization is not a good one, because the corresponding Estrada index is very close to the number of nodes of the graph, as can be inferred from the bounds presented before. Then, other general choices of the type (ϱA) k where ϱ < (λ 1 ) -1 are more appropriate here.

A nice result relating the resolvent Estrada index and the characteristic polynomial of the adjacency matrix was proved by in [START_REF] Chen | On resolvent Estrada index[END_REF] and is given below.

Theorem 35 Let G any graph with n nodes and let P (G, x) be the characteristic polynomial of the adjacency matrix of G, aka its characteristic polynomial. Then,

EE 0,1 (G) = (n) P ′ (G, n) P (G, n)
, (10.19) where P ′ (G, n) is the rst derivative of P (G, x) evaluated at x = n.

To illustrate the previous result let us consider the three graphs in Fig. 10.1. Their characteristic polynomials are, respectively:

P (G I , x) = x 8 -9x 6 -2x 5 + 24x 4 + 8x 3 -19x 2 -8x, (10.20) P (G II , x) = x 8 -9x 6 + 22x 4 -16x 2 + 1, (10.21)
P (G III , x) = x 8 -9x 6 + 24x 4 -4x 3 -20x 2 + 8x, (10.22) which give EE 0,1 (G I ) = 4023/484,EE 0,1 (G II ) = 2980/359, and EE 0,1 (G III ) = 2191/264. That is, the dierence between the rst pair of graphs is only 0.13% and between the second pair is only 0.02%. This is a direct consequence of penalizing more heavily the longer walks than in the exponential matrix function.

Some other inequalities have been reported for the resolvent Estrada index in terms of the number of nodes, edges, maximum degree, etc.

Lemma 20 [START_REF] Chen | On resolvent Estrada index[END_REF] Let G be a simple graph with n nodes and m edges. Then,

REE (G) ≥ n 2 (n -1) 2 n (n -1) 2 -2m
, (10.23) with equality if and only if G ∼ = Kn. Lemma 21 [114] Let G be a simple noncomplete graph with n > 3 nodes and m edges.

Then, REE (G) ≤ n + 4m (n -1) 2 -2m
, (10.24) with equality if and only if G ∼ = Kn. Lemma 22 [175] Let G be a simple graph with n nodes, m edges and maximum degree

kmax ̸ = n -1. Then, REE (G) < n 1 + kmax (n -1) (n -1 -kmax) , (10.25) REE (G) < n + 2m (n -1) (n -1 -kmax)
. (10.26)

Estrada indices and network of oscillators

The study of vibrations on regular graphs, known as lattices, is standard in solid-state physics (see for instance Chapter 4 in [144]). The techniques of classical as well as of quantum mechanics are used in the analysis of such vibrational problems. In 2003 this analysis was extended to consider non-regular networks [146] where the vibrations where analyzed in the context of a quantum system. Here we investigate the connections existing between some of the Estrada indices and the network vibrations, used in a metaphorical sense. That is, although some physical systems represented by nonregular graphs can be analyzed using the techniques developed here we consider the current approach as an appropriate tool for giving a physical meaning to the indices involved.

Let us consider a system S consisting of ball of mass M which are connected by springs with the spring constant M ω 2 . Let us consider that the ball-spring system is submerged into a thermal bath at the temperature τ . Then the balls in the complex network oscillate under thermal disturbances. We will consider that every ball is tied to the ground by a spring which has spring constant satisfying K ≫ maxv kv (see Fig. 11.1). This guarantees that the system can oscillates but do not translate from a xed position. In this way we can analyze how a given ball can transmit small oscillations to the rest of the balls of the system. The general Hamiltonian of this system is written as (11.1) where the rst term represents the kinetic energy of the corresponding balls and the second term represents the potential energy of the system, with pv being the momentum and xv the coordinate of the ball v.

H = v p 2 v 2M + (K -kv) M ω 2 x 2 v 2 + M ω 2 2 i<j Avw (xv -xw) 2 ,

Quantum oscillators

In this setup we consider that the system obeys the laws of quantum mechanics. Then, the momenta pw and the coordinates xv are not independent variables but they are operators that satisfy the commutation relation: [xv, pw] = iℏδvw,where i = √ the Dirac constant and δvw is Dirac delta. Additionally we will use second quantization to express the creation and annihilation of oscillations at the given balls of the system.

That is, we use the boson creation and annihilation operators dened by [184]

a † v = 1 √ 2ℏ xv √ M Ω - i √ M Ω pv , (11.2) av = 1 √ 2ℏ xv √ M Ω + i √ M Ω
pv . (11.3) With the use of these operators, the Hamiltonian of a network of quantum harmonic oscillators is given by [START_REF] Estrada | The physics of communicability in complex networks[END_REF] Ĥ

(S) = v ℏΩ a † v av + 1 2 - ℏω 2 4Ω v,w a † v + av Avw a † w + aw .
( 11.4) where Ω = K/M ω and K is a constant such that K ≫ maxv kv.

Since A is symmetric, we can diagonalize it by means of an orthogonal matrix O as in (11.5) where Λ is the diagonal matrix with the eigenvalues λµ of (KI -A) on the diagonal. This generates a new set of boson creation and annihilation operators as

Λ = O (KI -A) O T ,
bµ = v Oµvav = v av O T vµ , (11.6) b † µ = v Oµva † v = i a † v O T vµ , (11.7)
We can then decouple the Hamiltonian as

Ĥ (S) = µ Hµ (S) , (11.8)
with

Hµ (S) ≡ ℏΩ b † µ bµ + 1 2 + ℏω 2 4Ω (λµ -K) b † µ + bµ 2 = ℏΩ 1 + ω 2 2Ω 2 (λµ -K) b † µ bµ + 1 2 + ℏω 2 4Ω (λµ -K) b † µ 2 + (bµ) 2 .
(11.9)

We now introduce an approximation in which each mode of oscillation does not get excited beyond the rst excited state. In other words, we restrict ourselves to the space spanned by the ground state (the vacuum) |vac⟩ and the rst excited states b † µ |vac⟩.

Then the second term in the last line of the Hamiltonian (11.9) equals zero and we have .10) Remark 8 This approximation is justied when the energy level spacing ℏΩ is much greater than the energy scale of external disturbances, (specically the temperature uctuation k B T = 1/τ ), as well as than the energy of the network springs ℏω, i.e. τ ℏΩ >> 1 and Ω >> ω. This happens when the mass of each oscillator is small, when the springs to the ground, M Ω 2 , are strong, and when the network springs M ω 2 are weak. Then an oscillation of tiny amplitude propagates over the network.

Hµ (S) = ℏΩ 1 + ω 2 2Ω 2 (λµ -K) b † µ bµ + 1 2 . ( 11
We are going to work in this limit hereafter. The thermal bath represents here an 'external situation' which aects all the links in the network at the same time, e.g., economic crisis, social agitation, extreme physiological conditions, etc. After equilibration, all links in the network are weighted by the parameter τ = (k B T ) -1 .

Let us now compute how much an excitation at the node p propagates throughout the network before coming back to the same node and being annihilated. This information is obtained through the diagonal thermal Green's function, which is given in the framework of quantum mechanics by

Gvv (S, τ ) = 1 Z ⟨vac| ave -τ Ĥ (S) a † v |vac⟩ , (11.11)
where the partition function is given by

Z (S) = µ exp - τ ℏΩ 2 1 + ω 2 2Ω 2 (λµ -K) .
(11.12)

The diagonal thermal Green's function can then be obtained as [START_REF] Estrada | The physics of communicability in complex networks[END_REF] Gvv (S, τ ) = 1

Z µ,ν O T vµ ⟨vac| bµe -τ Ĥ (S) b † ν |vac⟩ Oνv = 1 Z A µ   O T vµ O T vµ ⟨vac| bµe -τ Hµ b † µ |vac⟩ Oµv ν(̸ =µ) ⟨vac| e -τ Hν |vac⟩   = µ O T vµ ⟨vac| bµe -τ Hµ b † µ |vac⟩ ⟨vac| e -τ Hµ |vac⟩ Oµv = µ O T vµ exp -τ ℏΩ 1 + ω 2 2Ω 2 (λµ -K) Oµv = e -βℏΩ exp τ ℏω 2 2Ω 2 A vv (11.13)
where we have used the spectral decomposition of A in the last line.

Let us consider ℏ = 1 and K = 1 2 11.15) which indicates that the Estrada index represents the sum of the excitations started at every node of a graph, which propagate throughout the network before coming back to the same node and being annihilated in a network of quantum harmonic oscillators.

M ω 3 . Then, [84] Gvv (S, τ ) = e -τ √ 2ω (exp [τ A]) vv = e -τ √ 2ω Gvv (G, τ ) . (11.14) Remark 9 In [84] it is remarked that EE (G, τ ) = v Gvv (G, τ ) = e τ √ 2ω v Gvv (S, τ ) , (

Classical Oscillators

Here we consider a system S like the one described before but obeying the laws of classical mechanics. In this case we can write the Hamiltonian of the system by considering only the potential energy (for justication see [START_REF] Estrada | The physics of communicability in complex networks[END_REF]):

H = KM ω 2 2 v x 2 v - M ω 2 2 v,w xvAvwxw = M ω 2 2 x T (KI -A) x, (11.16)
where x = (x 1 , x 2 , • • • , xn) T and I is the n × n identity matrix.

We can now diagonalize A as before and by taking a suciently large value of the constant K, we can make all eigenvalues λµ positive. By dening a new set of variables yµ as y = Ox and x = O T y, we can transform the Hamiltonian in the form

H = M ω 2 2 y T Λy = M ω 2 2 µ y 2 µ + M ω 2 2 µ λµy 2 µ . (11.17)
Here again we focus of the quantication of those oscillations that start at a given ball of the system, navigates the whole system and return to the corresponding ball.

Namely,

Γvv (S, β) = x 2 v = 1 Z x 2 v e -τ H
w dxw, (11.18) where the partition function is given by

Z (S) = e -τ H v dxv = dx exp - τ M ω 2 2 x T (KI -A) x , (11.19)
where the integral is n-fold.

Now, because the Jacobian of the orthogonal matrix O is unity we have i dx i = µ dyµ. Therefore, the multi-fold integration in the partition function is decoupled to give

Z (S) = µ exp - τ M ω 2 2 λµy 2 µ dyµ = µ 2π τ M ω 2 λµ , (11.20)
which can be written in matrix form as

Z (S) = 2π τ M ω 2 n/2 1 det (KI -A)
. (11.21) Since we have made all the eigenvalues of (KI -A) positive, its determinant is positive. Similarly, we have

Γvv (S, τ ) = 1 Z σ O T vσ yσ 2 e -τ H µ dyµ, (11.22)
where σ is used simply to avoid the confusion with µ in the same equation for the subscript for the product.

In the integrand, odd functions with respect to yµ vanish. Therefore, only the terms of y 2 σ survive after integration in the expansion of the square parentheses in the integrand. This gives

Γvv (S, τ ) = 1 Z σ (Oσvyσ) 2 exp - τ M ω 2 2 ν λν y 2 ν µ dyµ = 1 Z σ Oσv y 2 σ exp - τ M ω 2 2 λσy 2 σ dyσ = µ(̸ =σ) exp - τ M ω 2 2 λµy 2 µ dyµ . (11.23)
Comparing this expression with that of the partition function we have [START_REF] Estrada | The physics of communicability in complex networks[END_REF] Γvv (S,

τ ) = σ O 2 σv y 2 σ e -τ M ω 2 λσy 2 σ /2 dyσ e -τ M ω 2 λσy 2 σ /2 dyσ = σ O 2 σv 2π [τ M ω 2 λσ] 3 2π τ M ω 2 λσ = σ O 2 σv τ M ω 2 λσ = 1 τ M ω 2 (KI -A) -1 vv = 1 τ KM ω 2 I - A K -1 vv . (11.24)
Remark 10 In [START_REF] Estrada | The physics of communicability in complex networks[END_REF] it is remarked that if K = n -1 then we have

REE (G, τ ) = v I - A n -1 -1 vv = τ (n -1) M ω 2 v
Γvv (S, τ ) , (11.25) which indicates that the resolvent Estrada index represents the sum of the excitations started at every node of a graph, which propagate throughout the network before coming back to the same node in a network of classical harmonic oscillators.

12 Estrada indices and epidemics on networks

In continuation with the previous line of research in which the Estrada index is derived from a given dynamical systems context we analyze here its connection with epidemiological models on networks. The eld of mathematical epidemiology has a long tradition in applied mathematics (see for instance [START_REF] Allen | Mathematical epidemiology[END_REF][START_REF] Brauer | Mathematical epidemiology: Past, present, and future[END_REF]169]. In 2001, the authors of the seminal work [179] discovered the tremendous inuence of network topology on epidemic spreadings. Since then, the use of network-theoretic approaches together with epidemiological models have become a necessary combination [143,149]. Here we will show that such networked epidemiological models have a clear connection with the Estrada index of a graph.

For that we will briey introduce the Susceptible/Infected (SI) model on networks.

The reader should be aware that this is a generalist model that can be used in many dierent scenarios, not only on the analysis of diseases propagating on a network. Let G be a graphs whose nodes can be in either of two states: either susceptible or infected

one. An infected node can transmit the infection to any other node in the graph to which it interacts with. Then, if ζ is the rate at which such infection is transmitted between nodes, and if sv (t) and xv (t) are the probabilities that the node v is susceptible or get perturbed at time t, respectively, we can write the dynamics [170]:

dxv (t) dt = ζ (1 -xv (t)) w∈N Avwxw (t) , t ≥ t 0 , (12.1)
where Avw are the entries of the adjacency matrix of the graph for the pair of nodes v and w, and N is the set of nearest neighbors of v. In matrix-vector form becomes

[170]:

dx (t) dt = ζ [I N -diag (x (t))] Ax (t) , (12.2)
with initial condition x (0) = x 0 .

The SI model can be rewritten as

1 1 -xv(t) dxv (t) dt = ζ w∈N Avw 1 -e -(-log(1-xw(t))) , (12.3) which is equivalent to dyv (t) dt = ζ w∈N Avwf (yw (t)) , (12.4)
where yv (t

) := g (xv (t)) = -log (1 -xv (t)) ∈ [0, ∞], f (y) := 1 -e -y = g -1 (y).
dŷ (t) dt = ζAdiag (1 -x (t 0 )) ŷ (t) + ζb (x (t 0 )) , (12.5)
where x (t) = f (ŷ (t)) in which x (t) is the approximate solution to the SI model, ŷ (t 0 ) = g (x (t 0 )) and b (x) := x + (1 -x) log (1 -x) . They have found that the solution to this linearized model is [155]:

ŷ (t) = e ζ(t-t0)Adiag(1-x(t0)) g (x (t 0 )) + ∞ k=0 (ζ (t -t 0 )) k+1 (k + 1)! [Adiag (1 -x (t 0 ))] k Ab (x (t 0 )) . (12.6)
When t 0 = 0, x i (0) = c/N , i = 1, 2, . . . , N for some c, the previous equation is transformed to

ŷ (t) = (1/γ -1) e γζtA ⃗ 1 -(1/γ -1 + log (γ)) ⃗ 1, (12.7)
where γ = 1 -c/N and ⃗ 1 is the all-ones vector. In [155] the authors proved that this solution is an upper bound to the exact solution of the SI model.

Therefore, if we take the sum of the entries of ŷ (t) at a given t we have

n v=1 ŷv (t) = C 1 tr e γζtA + tr (J -I) e γζtA -nC 2 , (12.8)
where C 1 = (1/γ -1) and C 2 = (1/γ -1 + log (γ)) . Obviously the rst term in the square bracket is the Estrada index of the graph in which edges are weighted by γζt.

This term represents the circulability of the infection around the nodes of the graph, while the term tr (J -I) e γζtA , where J is the all-ones matrix, accounts for the transmissibility of the disease between the nodes.

12.1 Fractional SI model on networks

In recent years there have been an explosion of works in which the classical derivatives used in the epidemiological models have been substituted by fractional ones [START_REF] Almeida | An epidemiological mseir model described by the caputo fractional derivative[END_REF][START_REF] Angstmann | A fractional order recovery sir model from a stochastic process[END_REF][START_REF] Arenas | Construction of nonstandard nite dierence schemes for the si and sir epidemic models of fractional order[END_REF]133,192]. There have been several reasons for adopting fractional epidemiological models. They include for instance 1. the fact that the fractional parameter can be tuned to adjust the output of the model to real data [START_REF] Almeida | An epidemiological mseir model described by the caputo fractional derivative[END_REF] and so they can be more accurate that models using standard derivatives;

2. the fact that a fractional dierential operators may be derived from epidemiological models whenever the recovery time from the disease is power-law distributed [START_REF] Angstmann | A fractional order recovery sir model from a stochastic process[END_REF];

3. the fact that fractional derivatives capture the history of the variable, that is, they have memory, and the eect of recent memory is more important than the eect of older memory [START_REF] Arenas | Construction of nonstandard nite dierence schemes for the si and sir epidemic models of fractional order[END_REF]192].

In general, fractional derivatives are nowadays widely used to model biological processes

[136] to incorporate dierent aspects of the dynamics in such systems. Here, we will describe a model which naturally gives rise to the Mittag-Leer Estrada index in the context of epidemiological models.

We proceed by considering fractional time-derivatives in the modied SI model proposed in [155]. That is, in [START_REF] Abadias | Fractional-order susceptible-infected model: denition and applications to the study of covid-19 main protease[END_REF] the authors considered the following linearized fractional SI equation

D α t ŷ (t) = ζ α Adiag (1 -x 0 ) ŷ (t) + ζ α Ab (x (0)) , (12.9)
where x (t) = f (ŷ (t)) in which x (t) is an approximate solution to the fractional SI model, ŷ is the solution of (12.9) with initial condition ŷ (0) = g (x (0)) and b (x

) := x + (1 -x) log (1 -x) .
Here D α t f (t) is the fractional time derivative in the Caputo formulation [START_REF] Caputo | Linear models of dissipation whose q is almost frequency independentii[END_REF], which was previously given in Eq. (10.3).

For convenience, we write Ω := diag (1 -x 0 ) , and  = AΩ. It was then proved that this solution is an upper bound to the exact fractional SI model.

Let us x the following notation. Let x and y be two vectors of the same length n. Then, we say that x ⪯ y is x i ≤ y i for all i = 1, . . . n. Let x(t) be the solution of the linearized fractional models of the form: D α t x(t) = ζAx(t), which is exponential unstable.

Theorem 36 [START_REF] Abadias | Fractional-order susceptible-infected model: denition and applications to the study of covid-19 main protease[END_REF] For any t ≥ 0, we have

x(t) ⪯ x(t) = f (ŷ(t)) ⪯ x(t),
under the same initial conditions x 0 := x(0) = x(0) = x(0), where the solution ŷ of (12.9) is given by

ŷ (t) = E α,1 (ζt) α Â g (x 0 ) + ∞ n=0 (ζt) α(n+1) Ân Ab (x 0 ) Γ (α (n + 1) + 1)
. (12.10) Furthermore, ∥x(t) -x(t)∥ → 0 and ∥x(t) -x(t)∥ → ∞ as t goes to innity.

Corollary 5 [START_REF] Abadias | Fractional-order susceptible-infected model: denition and applications to the study of covid-19 main protease[END_REF] Let

x 0 ⪯ 1, x 0 = c N where c ∈ R + , let γ = 1 -x 0 . Then ŷ (t) = 1 -γ γ E α,1 t α ζ α γA ⃗ 1 - 1 -γ γ + log γ ⃗ 1, (12.11)
where E α,1 . is the Mittag-Leer matrix function of the corresponding matrix.

Therefore, here again if we take the sum of the entries of ŷ (t) at a given t we have n v=1

ŷv (t) = C 1 tr E α,1 t α ζ α γA + tr (J -I) E α,1 t α ζ α γA -nC 2 ,
(12.12)

Thus, again the Mittag-Leer Estrada index, which is the rst term in the squared bracket, represents the circulability of the infection around the nodes of the graph in the fractional SI model, while the second term represents the transmissibility of the disease between the nodes. [START_REF] Arrigo | Mittag-leer functions and their applications in network science[END_REF] Estrada indices from piecewise walk penalization

In the same work [START_REF] Estrada | Generalized walks-based centrality measures for complex biological networks[END_REF] in which the author proposed the use of the matrix Ψ functions as a way to increase the penalization of longer walks in graphs, a dierent strategy was proposed to drop such penalization relative to the exponential matrix function. This strategy can be formulated as a piecewise penalization as follows. Suppose that we do not want to penalize the walks of lengths smaller than certain value t ∈ Z. Then, we dene the following stepwise function: (13.1) such that the piecewise Estrada index of the graph G is dened as:

f t (k) = 1 if k < t, k! if k ≥ t,
EE t (G) = tr ∞ k=0 A k f t (k) = tr t-1 k=0 A k + ∞ k=t A k k! . (13.2)
In the case that the adjacency matrix has no unity eigenvalue we can write this Estrada index as [START_REF] Estrada | Generalized walks-based centrality measures for complex biological networks[END_REF]: .3) For computational purposes this expression can be adapted for any network as follows. Let r be a constant suciently close to one, such that r ̸ = 1/λ for all λ, which are the eigenvalues of A. Then, EE t (G) ≈ tr (I -rA) -1 I -(rA) t I + e rA -rAe rA .

EE t (G) = tr (I -A) -1 I -A t I + e A -Ae A . ( 13
(13.4)

Nonlocal adjacency, Harary Estrada index and beyond

There are physical situations in which the entities of a system not only interact if they are nearest neighbors, but also through nonlocal interactions. These long-range interactions have been documented in physical, chemical and biological systems [START_REF] Ala-Nissila | Collective and single particle diusion on surfaces[END_REF][START_REF] Chen | Mathematical models for cell migration: a non-local perspective[END_REF]148,164,177,194,195,235,240]. In a physical context, like the tight-binding kind of models described before, these nonlocal interactions corresponds to the case where the Hamiltonian of the system describes not only NN interactions but also next-nearestneighbor (NNN) and other interactions beyond them [START_REF] Binder | Phase diagrams and critical behavior in ising square lattices with nearest-and next-nearest-neighbor interactions[END_REF]168,174,193]:

Ĥ = ĤNN + ĤNNN + • • • . (14.1)
In this framework we have that the system can be described by the weighted sum of higher-order adjacency matrices:

Ĥ = αI + t N N A + t N N N A 2 + • • • , (14.2)
where A 2 is a matrix with entries (A 2 ) ij equal to one if i and j are not adjacent and are separated by two edges or zero otherwise. We can extend this concept to any other separation, such that [START_REF] Estrada | Path laplacian matrices: introduction and application to the analysis of consensus in networks[END_REF] ( (14.3) where d ij is the length of the shortest path between the two nodes. The parameters t N N , t N N N , etc. are expected to decay with the length of the separation between the corresponding entities. That is, the strength of the interaction decays with a given law of their separation d, i.e., f (d). In this way we can write [72, 218] (14.4) where diam is the diameter of the graph. Let us see how we can construct Ĥ.

A d ) ij = 1 if d ij = d, 0 otherwise,
Ĥ = αI + t N N A + t N N N A 2 + • • • = αI + diam d=1 f (d) A d ,
Here we will use a min-plus algebra to dene what otherwise is the shortest path distance matrix of the graph. We do that because it is a mathematically elegant approach, which may also open some possibilities for studying other kinds of functions for graphs.

Let (R ∪ {+∞} , ⊕, ⊗) be the min tropical semiring with the operations [32, 131, 139]:

x ⊕ y := min {x, y} ,

x ⊗ y := x + y. (14.5) The identity element for ⊕ is +∞ and that for ⊗ is 0. Then, we can dene the tropical adjacency matrix power as

A ⊗k+1 = A ⊗k ⊗ A, (14.6)
where A ⊗0 = Î, which is the tropical identity matrix, i.e., a matrix with zeros in the main diagonal and ∞ outside it.

Let us x any α with 0 < α ≤ ∞ and let us dene the matrix M = [m ij ] : m ij ∈ (-α, α) for all i, j = 1, . . . , n. Let f be a real function on the open interval (-α, α) . We dene the pseudo-entrywise (pseudo-Hadamard) matrix function f (M ) as

f (M ) ij := f (m ij ) if m ij ̸ = 0 0 if m ij = 0 . ( 14.7)
Here, the function f could be an exponential, a trigonometric function or simply the power function. Let us hereafter focus only on the negative power function, such that (-s) represents the entrywise power. We can now write:

Ĥ = As = ∞ k=0 A ⊗k (-s)
.

(14.8)

The tropical sum is carried out up to innity as it converges in all cases where there are no negative cycles in the graph. A negative cycle is a cycle where the product of the weights of all its edges is negative. Typically, except for signed graphs, we consider positive edge weights, which always avoid such negative cycles. The innite sum ∞ k=0 A ⊗k is known as the Kleene star operator of A [START_REF] Bouillard | Deterministic Network Calculus: From Theory to Practical Implementation[END_REF]131,139]. Obviously,

As = [A ij (s)],
where [72, 218] A ij (s) :=

d -s ij if i ̸ = j, 0 if i = j, (14.9)
which are the entry-wise powers of all nondiagonal entries of the shortest path distance matrix of the graph. The parameter s accounts for the strength of the nonlocal interaction. Notice that lim s→0 As = A (Kn) .

Here again, in the statistical physics context, the partition function of the system containing nonlocal interactions is:

Z = tr e -τ Ĥ , (14.10) where τ is the inverse temperature as before. Because the parameters t N N , t N N N , etc., are negative we have that Z = tr e τ As =: EE (As, β) , (14.11) Then, using the same denitions as the ones given before we can dene the entropy, enthalpy and free energy of the system having local and nonlocal interactions.

It is important to notice that (14.12) which implies that lim s→∞ As = A (G) . Theorem 38 [138] Let G be a simple graph with n ≥ 2 vertices and let κ = 1 2 tr A 2 s=1 .

As = A + diam d=2 d -s A d ,
Then, the Harary Estrada index is bounded as

HEE (G) ≥ exp 2κ n (n -1) + (n -1) exp - 2κ n (n -1)
. (14.16) 8 A biography of Frank Harary can be found at: https://mathshistory.st- andrews.ac.uk/Biographies/Harary/ 14.1 Numerical analysis In Fig. 14.1 we illustrate the histograms of the relative deviations of the lower bounds given in Theorem 37 and in Theorem 38 as well as of the upper bound given in Theorem 37. We consider all connected graphs with 8 nodes.

For both lower bounds, the values obtained with these bounds are about times smaller than the actual values. The mean relative deviations are, respectively 93.16 ± 2.19 and 96.591 ± 1.52. The upper bound is as average 10 19 times bigger than the actual HEE (G) indices for these small graphs, which is an extremely poor performance of this bound. In Table 10 we give the values of the bounds previously considered for the ve real-world networks analyzed here as well as the actual values of HEE (G). analyzed in this paper. The actual values of HEE (G) of these networks are also given.

We have used very precise arithmetic (vpa) in Matlab for these calculations.

15 Laplacian Estrada index and backward diusion

In the study of graph properties, the function K (G) = e -tL , where L is the graph Laplacian, has found many applications [START_REF] Barlow | Random walks and heat kernels on graphs[END_REF][START_REF] Chung | The heat kernel as the pagerank of a graph[END_REF]150,236]. The name Laplacian honors mathematician Pierre-Simon Laplace (1749-1827) 9 . The function K (G) is known as the heat kernel of the graph [125,191] and appears naturally in the solution u (t) = exp (-tDL) u 0 of the diusion equation on graphs:

du (t) dt = -DLu (t) , u (0) = u 0 , (15.1)
where D is the diusivity (see Section 16). Therefore, the trace of the heat kernel would correspond to a sort of diusion Estrada index. However, in [START_REF] Fath-Tabar | Note on Estrada and l-Estrada indices of graphs[END_REF] the following index was proposed and named the Laplacian Estrada index of the graph

LEE (G) = tr e L = n j=1 e µj , (15.2)
where µ j are the corresponding eigenvalues of L. Therefore, what the authors of [START_REF] Fath-Tabar | Note on Estrada and l-Estrada indices of graphs[END_REF] have proposed can be though as an index related to the solution of the backward diusion equation, i.e., negative time, or as a diusion equation with negative diusivity D < 0 [START_REF] Dung | The equation of backward diusion and negative diusivity[END_REF]. There are physical situations in which such negative diusivity appears [START_REF] Corli | Wavefronts in trac ows and crowds dynamics[END_REF]140,173,225,226]. For instance, in the simultaneous diusion of boron and point defect in silicon, the diusivities of interstitial could be negative [225]. That is, the diusion process of interstitial or vacancy could be a backward diusion in silicon. In other scenarios, a backward diusive model is used to detect the potential location of sources in spreading processes.

In [START_REF] Fath-Tabar | Note on Estrada and l-Estrada indices of graphs[END_REF] the authors proved the following result.

Proposition 2 Let G be a simple graph with n nodes and m edges. Let Z = i k 2 i be the rst Zagreb index of G.

G) ≤ n -1 + 2m - √ Z + 2m + exp √ Z + 2m , (
with equality if and only

if G ∼ = K 2 ∪ Kn-2 or G ∼ = Kn.
G) ≥ n + k i k i + 1 e ki+1 -1 , (
with equality if and only if G is a vertex disjoint union of complete subgraphs.

Several bounds have been proposed on the basis of the maximum and minimum degrees of a graph. We resume some of them here.

Theorem 39 [160] Let G be a simple graph with n nodes and m edges. Let kmax and k min be the maximum and minimum node degrees of G. Then, LEE (G) ≥ e kmax+1-2m/n + (n -2) e 4m/n-kmax-1 1/(n-2) + e -2m/n , (15.8) with equality if and only if G ∼ = Kn or G ∼ = Sn.

Theorem 40 [START_REF] Chen | Some results on Laplacian Estrada index of graphs[END_REF] Let G be a simple graph with n nodes and m edges. Let kmax and k min be the maximum and minimum node degrees of G. Then, LEE (G) ≥ 1 + e kmax+1 + e kmin + (n -3) e (2m-k max-kmin -1)/(n-3) , (15.9) with equality if and only

if G ∼ = 2K 1 ∨ K n-2 or G ∼ = K 1,n-1 or G ∼ = K (n-1)/2 ∪ K (n-1)/2 (n is odd).
Theorem 41 [161] Let G be a simple graph with n nodes and m edges. Let kmax and k min be the maximum and minimum node degrees of G. Then, [START_REF] Bamdad | Lower bounds for Estrada index and Laplacian Estrada index[END_REF][START_REF] Deng | A note on the laplacian Estrada index of trees[END_REF][START_REF] Du | More on Laplacian Estrada indices of trees[END_REF][START_REF] Du | On the Estrada and Laplacian Estrada indices of graphs[END_REF]117,135,145,162,207,242,243,251].

n 2 + 4m ≤ LEE (G) ≤ n-1+exp 2m (kmax + k min + 1 -2m/n) -nk min kmax , ( 15
Remark 12 The normalized Laplacian Estrada index dened as

N LEE (G) = tr e K -1/2 LK -1/2 , (15.13)
where K is the diagonal matrix of node degree has been studied in [START_REF] Clemente | Novel bounds for the normalized Laplacian Estrada index and normalized Laplacian energy[END_REF]123,158,203,207].

Remark 13 The signless Laplacian Estrada index dened as SLEE (G) = tr e K+A , (15.14) has been also studied in [START_REF] Ayyaswamy | Signless laplacian Estrada index[END_REF]117,227].

Numerical analysis

In Fig. 15.1 we illustrate the histograms of the relative deviations (in %) of the lower bounds (Proposition 2), (Proposition 4) (Proposition 5), (Proposition 6), (Theorem 40) and (Theorem 41) for all connected graphs with 8 nodes. The best performance is obtained from the bound (Proposition 6) followed by (Proposition 5).

We also analyzed the upper bounds given in Proposition 2, Proposition 3, Theorem 41 and Theorem 42 for the same set of graphs. In these cases the best performances were obtained for Theorem 41 and Theorem 42, while 2 give very high upper bounds.

In Table 11 we give the lower bounds for the Laplacian Estrada index of ve realworld networks. In general, the bounds (Proposition 5), (Proposition 6) and (Theorem The results are given in Table 12. The following bounds based on the largest Laplacian eigenvalue µ 1 perform very well for the four real-world networks analyzed as can be seen in Table 13. The reason is that the largest eigenvalue of the Laplacian matrix dominates the spectrum of this matrix, i.e., it is very large and separated from the second largest eigenvalue.

Radius of gyration and distance Estrada index

When presenting the diusion equation on graphs, Eq. ( 15.1), we mentioned in passing the diusion coecient D, which appears in the equation and in its solution. The diusion coecient is related to the radius r of the spherical particle diusing on a medium of viscosity η by the Stokes-Einstein equation [START_REF] Edward | Molecular volumes and the stokes-einstein equation[END_REF]: where τ is the inverse temperature. In the case of small molecules like drugs, or macromolecular systems like proteins, the particles cannot longer be considered spherical. In these cases it is customary to replace the radius of the spherical particle by the radius of gyration of the corresponding molecule [START_REF] Fixman | Radius of gyration of polymer chains[END_REF]107,126,152,171]. The radius of gyration is dened as follows. Let S = (p 1 , • • • , pn) be a system formed by n particles or points p i , which are located in a given region of the three-dimensional Euclidean space. Let r ij be the Euclidean distance between the particles p i and p j . Then, the radius of gyration of S is dened as R 2 S = 1 2n 2 i,j r 2 ij [94]. However, it has been shown that even when the radius of gyration based on Euclidean distances is used, there are cases of undesired degeneration of the index for pairs of clusters [START_REF] Estrada | Point scattering: A new geometric invariant with applications from (nano) clusters to biomolecules[END_REF]. That is, there are pairs of nonisomorphic clusters which have the same radius of gyration. Some examples in 2-and in 3-dimensions are given in Fig. 16.1.

The radius of gyration is widely used in organic chemistry, polymer sciences, proteins, and RNA, in general, for the study of their compactness. Most of these molecular systems can be represented as graphs. For instance, molecules are typically represented by molecular graphs [217], proteins can be represented by protein residue networks [START_REF] Estrada | Universality in protein residue networks[END_REF]212], and the secondary structure of RNA is also represented by graphs [147].

Then, it is important to extend the concept of radius of gyration to graphs. Denition 22 Let G be a simple graph. Let d ij be the shortest path distance between the nodes i and j. The graph radius of gyration is dened as Several bound have been obtained for the distance Estrada index, some of which are resumed below. Theorem 44 [108] Let G be a simple graph with n nodes and m edges. Then, if the diameter is dmax, the distance Estrada index is bounded as n 2 + 4m ≤ DEE (G) ≤ (n -1) exp dmax n (n -1) , (16.7) where equalities are attained if and only if G ∼ = K 1 .

R 2 G = 1 2n 2 i,j
Theorem 45 [202] Let G be a simple graph with n nodes and m edges. Then, if dmax, G = ( i D i ) 1/n and W = ij d ij stand for the diameter, the geometric mean of the graph distances and the Wiener index of G, the distance Estrada index is bounded as

  4W 2 -nG 2 n (n -1)   + n -1 exp 1 n -1 4W 2 -nG 2 n (n -1)
≤ DEE (G) ≤ (n -1)+e √ 2dmaxW , (16.8) where upper bound is attained if and only if G ∼ = K 1 and the lower one if and only if G ∼ = Kn.

Theorem 46 [204] Let G be a simple graph with n nodes with maximum and second maximum degress kmax and kmax 2 and diameter dmax. Then, the distance Estrada index is bounded as DEE (G) ≥ e (2n-2-k max )(2n-2-k max 2 ) + (n -1) e Theorem 47 [204] Let G be a simple graph with n nodes and m edges, the distance Estrada index is bounded as DEE (G) ≥ e 2(n-1)-2m/n + e -(2(n-1)-2m/n) + n -2 (16.11) where equality is attained if and only if G ∼ = K 2 .

Random graphs

The distance Estrada index has been studied for random graphs where some bounds have been reported in [205,209].

Theorem 48 Let Gn,p be an Erd®s-Rényi random graph with n nodes and probability p. Then, the distance Estrada index is bounded as 4-3p , (16.12) almost surely (a.s).

Theorem 49 Let Gn 1 ,n2,p be an Erd®s-Rényi random bipartite graph with n = n 1 +n 2 nodes and probability p. If n 1 = Θ (n 2 ) , then the distance Estrada index is bounded as In Table 14 we give the values of the lower and upper bounds as well as the actual values calculated with very precise arithmetic (vpa) in Matlab for the ve real-world networks studied. As can be seen in the The results obtained for Erd®s-Rényi random graphs Gn,p with 1000 ≤ n ≤ 4000 and p = 0.5 are illustrated in Table 15,showing Finally, we have not considered many of the results obtained in the literature for specic classes of graphs, which would make this paper too long to be digested. We advice the reader that such bounds exist for several of the indices described in this paper and for several classes of graphs of importance in specic areas of applications.

F 8 = ki>2 t i (k i -2) , (17.7
)

F 9 = 1 4 i,j A 2 ij A ij A 2 ij • A ij -1 , (17.8)
F 10 = 1 10 tr A 5 -30F 4 -10F 8 , (17.9)

F 11 = 1 2 ki≥4 t i (k i -2) (k i -3) , (17.10)
F 12 = 1 2 ki>2 (k i -2) × i,j A 2 ij 2 -2F 9 , (17.11)
F 13 = (i,j)∈E A 2 ij (k i -2) (k j -2) -2F 9 , (17.12) 17.20)

F 14 = i t i   i̸ =j (A 2 ) ij   -6F 4 -2F 8 -4F

Fig. 3 . 1 :

 31 Fig. 3.1: Illustration of the small subgraphs appearing in the rst seven spectral moments of the adjacency matrix of simple graphs.

  G be a simple graph and let T be a tree with the same number of nodes as G. Then EE (T ) ≤ EE (G) .

  G be a simple graph with n nodes. Then EE ( Kn) ≤ EE (G) ≤ EE (Kn) .

Fig. 3 . 2 :

 32 Fig. 3.2: Histogram of the relative deviation of the bound given in Lemma 2 for all 11,117 connected graphs with 8 nodes.

Remark 2

 2 Two examples of the use of this bound are (i) considering a = -λ 1 and b = -λn; (b) considering a = -kmax and b = kmax.

Fig. 5 . 1 :

 51 Fig. 5.1: Histograms of the relative deviations in percentage for: (a) Bound 1 (Theorem 5), (b) Bound 2 (Theorem 6, (c) Bound 3 (Theorem 7 using a = -λ 1 and b = -λn), (d) Bound 4 (Theorem 7 using a = -kmax and b = kmax), (e) Bound 5 (Theorem 8).

Fig. 5 . 2 :

 52 Fig. 5.2: Plot of the estimates of the lower (blue circles) and upper (red squares) for the bounds: (1) (Theorem 5), (2) (Theorem 6, (3) (Theorem 7 using a = -λ 1 and b = -λn), (4) (Theorem 7 using a = -kmax and b = kmax), (5) (Theorem 8). The results are for (a) Stony, (b) neurons, (c) yeast, (d) internet and (e) powergrid. The dashed lines represents the exact value of the Estrada index for the networks. Very large values are obtained by using variable-precision oating-point arithmetic (vpa) in Matlab.

Fig. 6 . 1 :

 61 Fig. 6.1: Plots of the entropy (a), enthalpy (b) and free energy (c) versus the number of edges in all connected graphs with 8 nodes.

Fig. 8 . 1 :

 81 Fig. 8.1: Illustration of the change in the bipartivity index with the increase in the number of edges in a complete bipartite graph.

4 A

 4 biography of Johan Jacob Seidel can be found at: https://mathshistory.st- andrews.ac.uk/Biographies/Seidel_Jaap/8.3 Negative absolute temperatures and the Onsager Estrada indexIn the denition of the bipartivity index we have considered in the numerator of Eq.(8.4) the term EE G -=tr (exp (-A)) . In the context of statistical mechanics which we have analyzed in Section 6 this corresponds to consider the inverse temperature τ = -1. So far, we have considered the inverse temperature τ to be positive. So, what a negative inverse temperature could mean? Let us rst analyze what is the physical denition of τ . Let S be the statistical entropy, which is a function of the possible microstates of the system, and let E be the system's energy. Then, the absolute temperature is dened as:

Fig. 8 . 2 :

 82 Fig. 8.2: Sketch of the plot of entropy versus energy used to illustrate the denition of the inverse temperature which is given by the slope of the curve in a given point. The scale of inverse temperature is given on top of this plot.

5 .

 5 Denition 19 The Onsager Estrada index of G is dened asOEE (G) = tr [exp (-A)] .

( 8 . 17 )

 817 First let us consider some elementary results, which are presented here by the rst time. First, because tr [exp (-A)] = tr [cosh (A)] -tr [sinh (A)] , and due to the fact that a graph is bipartite if and only if it has no odd cycles, we have the following result.Lemma 9 Let G be a simple graph. Then, OEE (G) = tr [cosh (A)] if and only if G is bipartite. In this case OEE (G) = EE (G).

Remark 5

 5 Some graphs for which OEE (G) = EE (G) for which we can write explicitly the indices are

Fig. 8 . 3 :

 83 Fig. 8.3: Scatter plot of the bipartivity and the clustering coecient of all connected graphs with 8 nodes. The points in the plot are colored by the number of edges that the corresponding graph has.

Fig. 8 . 4 :

 84 Fig. 8.4: Illustration of a bipartition of the network of Stony stream using the method

  Fig. 9.1: Illustration of the gaussianized spectrum method. The eigenvalues of the adjacency matrix of the network are folded at λ into the spectrum of λI -A 2

  G be a simple graph with n ≥ 2 nodes and m ≤

2 .Fig. 9 . 2 :

 292 Fig. 9.2: Schematic illustration of the double Gaussianization of the graph spectra. The eigenvalues of the adjacency matrix are folded at two dierent reference eigenvalues and then exponentiated as illustrated in the right part of the gure.

. 21 )

 21 Lemma 19 Let G b be connected bipartite graph of n nodes, thenDGEE -1,1 (G b ) ≤ DGEE -1,1 (Kn) .

  G be any connected graph of n nodes, thenDGEE -1,1 (G) ≤ DGEE -1,1 (Kn) .

  a 2 b a!b! , and a, b are non negative integers.

  The bound given in Theorem 30 is extremely far away from the actual values and practically says the same as the trivial bound GEE 0 (G) > 0. The same happens for Theorem 32 in the cases of Stony and neurons, but it gives more decent estimations for the cases of the bigger networks of Internet and powergrid. 10 Mittag-Leer Estrada indices As we have seen in previous sections of this paper, the Estrada indices of a graph may arise as the solution of the linear dynamical system d dt u

Fig. 9 . 3 :

 93 Fig. 9.3: Histograms of the relative deviations in percentage of the bounds given in

  Let us show a practical example on how these dierent penalizations inuence the Estrada indices of cycle graphs. In Fig.10.1 we illustrate three graphs with 8 nodes but having dierent length of their main cycles. In G I there is a triangle and an heptagon, in G II a square and a hexagon, and in G III two pentagons. The index EE 1,1 (G) of the three graphs are:21.68, 20.64 and 20.38, respectively. That is, there is a dierence of 4.8% between G I and G II and of 1.25% between G II and G III . On the other hand, the index EE 1/2,1 (G) is 672.24, 540.58 and 507.13 for G I , G II and G III , respectively, which represent 19.6% of dierence between the rst pair and 6.2% between the second one.

Fig. 10 . 1 :

 101 Fig. 10.1: Examples of three graphs with 8 nodes and chordless cycles of dierent lengths: G I has a triangle and an heptagon; G II has a square and a hexagon; G III has two pentagons.

Fig. 11 . 1 :

 111 Fig. 11.1: Illustration of a system formed by three balls of mass M tied to the ground with springs of constant K connected by springs of constant M ω 2 .

  Lee et al. [155] have considered the following linearized version of the previous nonlinear equation

( 14 . 13 )

 1413 Let Ãs := diam d=2 d -s A d . Then, because A and Ãs do not commute in general, we have according to the Golden-Thompson inequality that EE (As, τ ) = tr e τ (A+ Ãs) ≤ tr e τ A e τ Ãs .(14.14) When s = 1, the corresponding matrix A s=1 is known in mathematical chemistry as the Harary matrix[137, 167, 181] in honor to mathematician Frank Harary (not many results about the HEE index. Hereafter we collect some of the existing ones for simple graphs [109], HEE (G) = EE (A s=1 , τ = 1) .

Fig. 14 . 1 :

 141 Fig. 14.1: Histogram of the relative deviations for the lower bounds Theorem 37 and Theorem 38 (in %) as well as of the upper bound Theorem 37 (as logarithm) for all 11,117 connected graphs with 8 nodes.

Fig. 15 . 1 :

 151 Fig. 15.1: Relative deviations (in %) of the lower bounds (Proposition 2), (Proposition 4) (Proposition 5), (Proposition 6), (Theorem 40) and (Theorem 41) for all connected graphs with 8 nodes.

3 Table 11 :

 311 Values of the lower bounds (Proposition 2), (Proposition 4) (Proposition 5), (Proposition 6), (Theorem 40) and (Theorem 41) for the ve real-world networks analyzed and well their actual values of LEE (G).40) perform very well, while (Proposition 2), (Proposition 4) and (Proposition 41) are several orders of magnitude below the actual values of the Laplacian Estrada indices of these networks. The case of the upper bound is much more contrasting with values several orders of magnitude over the actual values of the Laplacian Estrada indices of these ve networks. We have used variable-precision oating-point arithmetic (VPA) to evaluate each element of the symbolic input in Matlab for these calculations. It is used to evaluate symbolic inputs with variable-precision oating-point arithmetic, calculating values to 32 signicant digits.

Fig. 15 . 2 :

 152 Fig. 15.2: Relative deviation (in logarithmic scale) of the upper bounds given in Proposition 2, Proposition 3, Theorem 41 and Theorem 42 for all connected graphs with 8 nodes.

Fig. 16 . 1 : 2 G 2 G = 9 50 .

 1612250 Fig. 16.1: Examples of Euclidean objects in 2-(a and b) and 3-dimensions (c and d), which have the same radius of gyration: (a and b) R 2 S = 1 4 , (c and d) R 2 S = 3 16 . Every

( 16 . 5 )

 165 Let us include the term c 0 tr D 0 + c 1 tr D 1 (the rst is the weighted number of vertices and the second is zero in simple graphs) and let us consider c k = (k!) -1 .Then, we get the following index, rst dened in[108].

Fig. 16 . 2 Denition 23

 16223 Fig. 16.2

  attained if and only if G ∼ = K 2 .

( 1 +

 1 o (1))+e 2(n-1)-np-O( √ n) ≤ DEE (Gn,p) ≤ (1 + o (1))+e(n-1)

√

( 1 +

 1 o (1)) + e 5n2-2np-O( √ n) ≤ DEE (Gn,p) ≤ (1 + o (1)) + e 5n1+2n1p-O( (a.a.s.) which, when n 1 = n 2 becomes (1 + o (1)) + e n(5/2-p)-O( √ n) ≤ DEE (Gn,p) ≤ (1 + o (1)) + e n(5/2+p)-O( √n) , a.a.s.

Fig. 16 . 4 :

 164 Fig. 16.4: Relative deviations (in logarithmic scale) of the upper bounds given in Theorem 44, Theorem 45 and Theorem 46 for all connected graphs with 8 nodes.

Table 15 :

 15 good agreement between the actual values and those predicted by Theorem 48. The values were computed in[209] using variable-precision oating-point arithmetic (VPA) in Matlab.[START_REF] Baird | The seasonal dynamics of the chesapeake bay ecosystem[END_REF] ConclusionsWe presented an account of the many dierent facets of the Estrada indices of graphs.Starting from the classical Estrada index we give several interpretations of the index based on (i) combinatorics of subgraphs, (ii) statistical mechanics, (iii) marginal n Actual values for Erd®s-Rényi random graphs Gn,p as well as the lower and upper bounds found in[209].probability in a quantum system, (iv) oscillations models on networks, and (v) epidemiological models on networks. Then we move forward to the analysis of other kinds of Estrada indices. First we contextualize these indices originally introduced in an ad hoc way in the mathematical literature. For instance, the Seidel Estrada index is placed in the context of signed graphs, the theory of balance and the concept of network bipartivity. The resolvent Estrada index is analyzed as a case of Mittag-Leer Estrada indices which appear in the context of fractional epidemiological models on graphs. The Harary Estrada index is understood as a particular case of nonlocal operator on graphs.The Laplacian Estrada index is now pondered on the basis of the diusion equation with negative diusivity or a backward diusive process. Finally, the distance Estrada index is considered in the context of the radius of gyration of a graph, which can be connected to the diusion coecient of graphs via the Stokes-Einstein equation. In all cases we have provided numerical analysis of several of the bounds and estimations made for these indices. Such results have revealed the necessity of investigating more robust bounds, particularly upper bounds, for most of the indices studied. In many cases the bounds, although correct, are very far away from the actual values of the indices, which leaves large rooms for improvements. We encourage authors searching for new bounds to compare them with the existing ones with the challenge of improving them for general classes of graphs.

7 - 13 -14F 14 -

 71314 126F 4 -84F 8 -112F 9 -70F 10 -28F 11 -14F 56F 16 -14F 18 -84F 19 -28F 20 ) .

(

Table 2 .

 2

		n	m	kmax	dmax	ref.
	Stony	112	830	45	4	[17]
	neurons	280	1973	77	6	[232]
	yeast	2224	6829	65	11	[224]
	Internet	3015	5156	590	9	[90]
	Powergrid	4941	6594	19	46	[231]

Table 2 :

 2 General characteristics, number of nodes n, of edges m, the maximum degree of the nodes kmax, and the diameter dmax, of the ve real-world networks analyzed in this paper.The main goal of these numerical experiments is to show how close the bounds reported in the literature are to the actual values of the Estrada index. This is done because in most of the papers where these bounds are proposed there are no numerical experiments to illustrate this relation. When possible we will nd some connection between structural characteristics of the networks studied and the corresponding bounds analyzed to understand why are they close or far away the actual values of the Estrada index.First, we consider the deviation of the bound from the actual value as |EE exact -EE bound | /EE exact expressed as percentage. We do this calculation considering the bound given in Lemma 2 for all the connected graphs with 8 nodes. The histogram illustrating the number of graphs having a given relative deviation (frequency) among the 11,117 connected graphs with 8 nodes is illustrated in Fig.3.2. We should remark that we use here the terms good bound or refer to a bound as better than another just on the basis of the deviation of this bound relative to the actual value of the index. This is used only as a guide as for many cases there is large room for improvement as some of the bounds reported are orders of magnitude further from the real values of the indices.The mean deviation is 5.768 ± 4.169, which indicates that this bound is a good estimation of the Estrada index for these small graphs. The largest deviation is40.352 obtained for the complete graph K 8 . In general, the most densely connected graphs are richer in small subgraphs than the poorly dense ones, which increases the relative deviation of this bound for these graphs.

Table 3

 3 we illustrate the results for the ve real-world networks. The largest deviation occurs for the Internet at AS indicating that in this network there are many larger subgraphs with important contribution to the Estrada index. On the other hand, the bound is very close to the actual value for the power grid of western USA, which points out that the Estrada index of this network is well approximated by counting the number of the 21 subgraphs described by Lemma 2. These dierences point out clearly to the dierences in the subgraph richness contained in dierent networks, which is what the Estrada index characterizes at the structural level.

		Lemma 2	actual
	Stony	4.590 • 10 5	7.234 • 10 9
	neurons	1.095 • 10 6	1.306 • 10 10
	yeast	5.057 • 10 5	3.038 • 10 8
	Internet	7.142 • 10 6	6.174 • 10 13
	Powergrid	1.961 • 10 4	2.135 • 10 4

Table 3 :

 3 Values of the bound for the Estrada index in Lemma 2 and the actual values calculated with Matlab function expm for the ve real-world networks considered in this work.

  Denition 6 Let λ 1 , • • • , λs be the distinct eigenvalues of M and let and let n i be the order of the largest Jordan block in which λ i appears, which is called the index of λ i . The function f is dened on the spectrum of M if the values

  Let G be a simple graph with n nodes and m edges either without isolated vertices or having the property 2m/n > 1, then, the Estrada index of G is

	Theorem 10 [110] bounded as
		EE (G) ≥ n cosh	2m/n ,	(5.7)
	with equality if and only if G is a regular graph of degree 1.
				4 Q , (5.5)
	with equality attained if and only if G ∼ = Kn.
	Other bounds have been proposed, specially lower bounds, for the Estrada index. Some
	examples are given below.
	Theorem 9 [247] Let G be a simple graph with n nodes and let Z = n i=1 k 2 i . Then,
	the Estrada index of G is bounded as
	EE (G) ≥ exp	Z/n + (n -1) exp -	Z/n / (n -1) ,	(5.6)
	with equality attained if and only if G ∼ = Kn or G ∼ = Kn .

  447 • 10 -6

			-22.704	-22.704	0.134
	neurons	0.0011	-23.292	-23.293	0.0505
	yeast	0.227	-19.304	-19.532	0.0028
	Internet	1.149 • 10 -4	-31.754	-31.754	0.0011
	Powergrid	6.806	-3.162	-9.969	5.403 • 10 -4

Table 6 :

 6

Values of the entropy, enthalpy and free energy of the ve real-world networks analyzed here.

  Table 7 we give the values of the bipartivity for the ve networks studied in this work. The networks of Stony and powergrid have signicant bipartivity, while neurons and yeast are highly non-bipartite. As can be seen in the Table there is not a clear trend between bipartivity and edge density nor to the clustering coecient of these graphs.

network

  Theorem 31 Let G be a simple graph with n nodes and m ≤

	Then,
	GEE λ (G) ≥ n/2m,			(9.9)
	with equality if and only if G ∼ = Kn.
	n 4	+	n (n -1) 4	exp (-4m/n)

edges and let λ = 0. Then,

GEE λ (G) ≥ n -4m + n (n -1) exp (-4m/n),

(9.10) with equality if and only if G ∼ = Kn. Remark 6 The previous bound can only be applied for very sparse networks where the density δ

Table 8 :

 8 Theorem 30 and in Theorem 32 for all connected graphs with 8 nodes. Values of the bounds given inTheorem 30, Theorem 31 and in Theorem 32

	network	Theorem 30	Theorem 31	Theorem 32	GEE 0 (G)
	Stony	0.0675	NA	8.018 • 10 -4	41.360
	neurons	0.071	NA	6.260 • 10 -4	69.083
	yeast	0.163	NA	4.998	1135.731
	Internet	0.292	NA	109.2963	2148.635
	Powergrid	0.375	309.576	342.947	1907.307

Table 9 :

 9 Examples of Mittag-Leer functions of the adjacency matrix.

  Theorem 37 [109] Let G be a simple graph with n vertices and m edges. Then, the

	Harary Estrada index of G is bounded as
	n 2 + 2	3m 2	+	n (n -1) 4	≤ HEE (G) ≤ n -1 + exp	3m 2	+	n (n -1) 4
								(14.15)
	with equalities attained if and only if G ∼ = K1 .

Table 10 :

 10 Values of the lower bounds Theorem 37 and Theorem 38 as well as the upper bound Theorem 37 for the Harary Estrada index of the ve real-world networks

  Proposition 4 Let G be a simple graph with n nodes and m edges. Then, LEE (G) ≥ 2 + n (n -1) e 4m + 4 -3n -4m, Other bounds were obtained in[248] on the basis of the degree sequence of a graph. Proposition 5 Let G be a simple graph with n nodes and m edges. Let kmax, k 2 , • • • , k min be the nonincreasing ordering of the node degrees of G. Then, Proposition 6 Let G be a simple graph with n nodes and m edges. Let kmax, k 2 , • • • , k min be the nonincreasing ordering of the node degrees of G. Then,

			(15.5)
	with equality if and only if G ∼ = Kn.
	n-1
	LEE (G) ≥ e kmax+1 +	e ki + e kmin-1 ,	(15.6)
	i=2
	with equality if and only if G ∼ = Sn.
	LEE

  The following is an upper bound found in[163].Theorem 42 Let G be a simple graph with n nodes and m edges. Then,Theorem 43 Let Gn,p be an Erd®s-Rényi random graph with n nodes and probability p. Then, the Laplacian Estrada index is given by LEE (Gn,p) = e np (n -1) e o(1)n + o (1) , a.s.

	LEE (G) ≤	2m n	e n + n -	2m n	-1 + exp	2m -n	2m n	,	(15.11)
	with equality if and only if G ∼ = Kn or G ∼ = Kn -e.
	Finally, we present the estimation made in [100] for the Laplacian Estrada index
	of Erd®s-Rényi random graphs.
									(15.12)
	In [132] the authors nd estimations for the Laplacian Estrada index of random mul-
	tipartite graphs.
	Remark 11 Other bounds and estimations have been reported for the Laplacian Estrada
	index of specic graphs, or based on other graph parameters not considered here. Some
	non-exhaustive examples are:
									.10)
	with equality if and only if G ∼ = Kn.

Table 12 :

 12 Values of the upper bounds given in Proposition 2, Proposition 3, Theorem 41 and Theorem 42 for all connected graphs with 8 nodes for the ve real-world networks analyzed and well their actual values of LEE (G).

	Bound	Stony		neurons	yeast	Internet	Powergrid
	real	2.137 • 10 22		9.561 • 10 33	6.848 • 10 28	4.718 • 10 256	7.740 • 10 8
	2	4.482 • 10 720	5.321 • 10 1713	3.927 • 10 5931	2.784 • 10 4478	2.989 • 10 5727
	3	1.999 • 10 87		1.653 • 10 132	1.006 • 10 210	2.063 • 10 425	1.192 • 10 110
	41	3.323 • 10 95		2.170 • 10 210	7.351 • 10 356	3.852 • 10 899	1.006 • 10 167
	42	6.125 • 10 49		5.605 • 10 122	4.457 • 10 966	7.499 • 10 1309	2.989 • 10 2146
		network		exp (µ 1 )	real	n exp (µ 1 )
		Stony		2.1362 • 10 22	2.1370 • 10 22	2.3925 • 10 24
		neurons		9.121 • 10 33	9.561 • 10 33	2.554 • 10 36
		yeast		3.112 • 10 28	6.848 • 10 28	6.922 • 10 31
		Internet		4.717 • 10 256	4.718 • 10 256	1.422 • 10 260
		Powergrid	5.414 • 10 8	7.740 • 10 8	2.375 • 10 12

Table 13 :

 13 Values of lower and upper bounds based on µ 1 for LEE (G) of the ve real- world networks analyzed based on the spectral radius of the Laplacian matrix.

	D =	1 6τ πηr	,	(16.1)

Table 14 :

 14 Table 14 the bound given in Theorem 45 gives the best lower and upper estimates of the distance Estrada index. It is also interesting to remark that the network of the western USA power grid displays an extremely large value of DEE (G), indicating that it is a very poorly packed network. Indeed, this network is planar as the power stations are embedded in the landscape of the western Theorem 45 4.232 • 10 112 4.450 • 10 318 1.060 • 10 4225 5.479 • 10 4923 5.715 • 10 40739 Theorem 46 3.873 • 10 78 3.516 • 10 209 7.265 • 10 1902 5.592 • 10 2375 1.060 • 10 4282 Values of the lower and upper bounds for DEE (G) in the ve real-world networks analyzed in this paper.

	USA
	Bound	Stony	neurons	yeast	Internet	Powergrid
	Theorem 44	125.952	293.755	2.230 • 10 3	3.018 • 10 3	4.944 • 10 3
	Theorem47	9.473 • 10 89	1.644 • 10 236	1.608 • 10 1928	2.765 • 10 2616	4.681 • 10 4289
	real	2.932 • 10 115	1.356 • 10 324	2.705 • 10 4311	5.963 • 10 5065	1.990 • 10 41503
	Theorem 44	5.479 • 10 195	5.705 • 10 730	3.453 • 10 10625	1.275 • 10 11786	5.755 • 10 98702
	Theorem 45	1.043 • 10 118	1.464 • 10 482	8.313 • 10 6699	2.208 • 10 7617	2.059 • 10 63414
	Theorem 46	3.931 • 10 198	2.044 • 10 728	1.553 • 10 10622	4.229 • 10 11782	1.165 • 10 98599

  9F 4 -2F 8 -4F 9 , -2m -12F 3 -24F 4 -6F 5 -12F 6 -48F 7 -36F 9 -12F 12 -24F 15 , = A 5 ii -20t i -8t i (k i -2)-2 -2F 16 -6F 19 ,

								A 2	ij (k j -2)-2	t j -A 2	ij ,
							(i,j)∈E	(i,j)∈E
								(17.17)
					F 18 =	(i,j)∈E	A 2 3	ij	,	(17.18)
			F 19 =	i	t i •	i̸ =j	A 2 2	ij	-6F 9 (17.19)
								(17.13)
			F 15 =				A 3	ij A 2	ij -(17.14)
				(i,j)∈E
	F 16 =	1 12	tr A 6 (17.15)
					F 17 =	1 2

9 , ki>2 (k i -2) B i -2F

16 , (17.16) where B i

In the study of social signed networks, positive edges are used for friendship relations and negative ones for enmities.

A biography of Pierre-Simon Laplace can be found at: https://mathshistory.st- andrews.ac.uk/Biographies/Laplace/

Acknowledgements The author thanks nancial support from Ministerio de Ciencia, Innovacion y Universidades, Spain for the grant PID2019-107603GB-I00 Hubs-repelling/attracting Laplacian operators and related dynamics on graphs/networks. The author thanks the referees for exhaustive and construtive revision of the manuscript.

Numerical analysis

We analyze here the lower bounds in Theorem 44,Theorem 45,Theorem 46 and Theorem 47. The relative deviations (in %) are illustrated in Fig. 16 We also considered the upper bounds given in Theorem 44, Theorem 45 and Theorem 46 were we observe that these bounds are several order of magnitude over the actual values of DEE (G) even for small graphs like the ones studied here.

Appendix

The following result allows the calculation of the 21 dierent subgraphs which are used in the expressions of spectral moments of the adjacency matrix.

Theorem 50 Let k i and t i be the degree and the number of triangles at the node i.

Then, the number of subgraphs illustrated in Fig. 3.1 are obtained as follow: (17.1)