Estrada index

Last updated January 30, 2023

In chemical graph theory, the Estrada index is a topological index of protein folding. The index was first defined by Ernesto Estrada as a measure of the degree of folding of a protein,^[1] which is represented as a path-graph weighted by the dihedral or torsional angles of the protein backbone. This index of degree of folding has found multiple applications in the study of protein functions and protein-ligand interactions.

The name "Estrada index" was introduced by de la Peña et al. in 2007.^[2]

Derivation

Let $G=(V,E)$ be a graph of size $|V|=n$ and let $\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}$ be a non-increasing ordering of the eigenvalues of its adjacency matrix $A$ . The Estrada index is defined as

\operatorname {EE} (G)=\sum _{j=1}^{n}e^{\lambda _{j}}

For a general graph, the index can be obtained as the sum of the subgraph centralities of all nodes in the graph. The subgraph centrality of node $i$ is defined as^[3]

\operatorname {EE} (i)=\sum _{k=0}^{\infty }{\frac {(A^{k})_{ii}}{k!}}

The subgraph centrality has the following closed form^[3]

\operatorname {EE} (i)=(e^{A})_{ii}=\sum _{j=1}^{n}[\varphi _{j}(i)]^{2}e^{\lambda _{j}}

where $\varphi _{j}(i)$ is the $i$ th entry of the $j$ th eigenvector associated with the eigenvalue $\lambda _{j}$ . It is straightforward to realise that^[3]

\operatorname {EE} (G)=\operatorname {tr} (e^{A})

Related Research Articles

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each internal vertex are equal to each other. A regular graph with vertices of degree $k$ is called a $k$ ‑regular graph or regular graph of degree $k$ . Also, from the handshaking lemma, a regular graph contains an even number of vertices with odd degree.

In linear algebra, the Cayley–Hamilton theorem states that every square matrix over a commutative ring satisfies its own characteristic equation.

In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The characteristic polynomial of an endomorphism of a finite-dimensional vector space is the characteristic polynomial of the matrix of that endomorphism over any base. The characteristic equation, also known as the determinantal equation, is the equation obtained by equating the characteristic polynomial to zero.

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

<span class="mw-page-title-main">Jensen's inequality</span> Theorem of convex functions

In mathematics, Jensen's inequality, named after the Danish mathematician Johan Jensen, relates the value of a convex function of an integral to the integral of the convex function. It was proved by Jensen in 1906, building on an earlier proof of the same inequality for doubly-differentiable functions by Otto Hölder in 1889. Given its generality, the inequality appears in many forms depending on the context, some of which are presented below. In its simplest form the inequality states that the convex transformation of a mean is less than or equal to the mean applied after convex transformation; it is a simple corollary that the opposite is true of concave transformations.

In mathematics, specifically functional analysis, Mercer's theorem is a representation of a symmetric positive-definite function on a square as a sum of a convergent sequence of product functions. This theorem, presented in, is one of the most notable results of the work of James Mercer (1883–1932). It is an important theoretical tool in the theory of integral equations; it is used in the Hilbert space theory of stochastic processes, for example the Karhunen–Loève theorem; and it is also used to characterize a symmetric positive semi-definite kernel.

In linear algebra and functional analysis, the min-max theorem, or variational theorem, or Courant–Fischer–Weyl min-max principle, is a result that gives a variational characterization of eigenvalues of compact Hermitian operators on Hilbert spaces. It can be viewed as the starting point of many results of similar nature.

In graph theory, the resistance distance between two vertices of a simple, connected graph, $G$ , is equal to the resistance between two equivalent points on an electrical network, constructed so as to correspond to $G$ , with each edge being replaced by a resistance of one ohm. It is a metric on graphs.

In the mathematical field of spectral graph theory, a Ramanujan graph is a regular graph whose spectral gap is almost as large as possible. Such graphs are excellent spectral expanders. As Murty's survey paper notes, Ramanujan graphs "fuse diverse branches of pure mathematics, namely, number theory, representation theory, and algebraic geometry". These graphs are indirectly named after Srinivasa Ramanujan; their name comes from the Ramanujan–Petersson conjecture, which was used in a construction of some of these graphs.

In probability theory, a compound Poisson distribution is the probability distribution of the sum of a number of independent identically-distributed random variables, where the number of terms to be added is itself a Poisson-distributed variable. The result can be either a continuous or a discrete distribution.

In mathematics, the Gauss–Kuzmin–Wirsing operator is the transfer operator of the Gauss map that takes a positive number to the fractional part of its reciprocal. It is named after Carl Gauss, Rodion Kuzmin, and Eduard Wirsing. It occurs in the study of continued fractions; it is also related to the Riemann zeta function.

<span class="mw-page-title-main">Strongly regular graph</span> Regular graph where all linked node pairs have same degree, as do all unlinked node pairs

In graph theory, a strongly regular graph (SRG) is defined as follows. Let $G = (V, E)$ be a regular graph with $v$ vertices and degree $k$ . $G$ is said to be strongly regular if there are also integers $λ$ and $μ$ such that:

In graph theory, a graph is said to be a pseudorandom graph if it obeys certain properties that random graphs obey with high probability. There is no concrete definition of graph pseudorandomness, but there are many reasonable characterizations of pseudorandomness one can consider.

The expander mixing lemma intuitively states that the edges of certain $-regular graphs are evenly distributed throughout the graph. In particular, the number of edges between two vertex subsets and is always close to the expected number of edges between them in a random -regular graph, namely .$

In mathematics, there are many kinds of inequalities involving matrices and linear operators on Hilbert spaces. This article covers some important operator inequalities connected with traces of matrices.

Functional principal component analysis (FPCA) is a statistical method for investigating the dominant modes of variation of functional data. Using this method, a random function is represented in the eigenbasis, which is an orthonormal basis of the Hilbert space L² that consists of the eigenfunctions of the autocovariance operator. FPCA represents functional data in the most parsimonious way, in the sense that when using a fixed number of basis functions, the eigenfunction basis explains more variation than any other basis expansion. FPCA can be applied for representing random functions, or in functional regression and classification.

In the mathematical field of extremal graph theory, homomorphism density with respect to a graph $is a parameter that is associated to each graph in the following manner:$

Sidorenko's conjecture is a conjecture in the field of graph theory, posed by Alexander Sidorenko in 1986. Roughly speaking, the conjecture states that for any bipartite graph $and graph on vertices with average degree , there are at least labeled copies of in , up to a small error term. Formally, it provides an intuitive inequality about graph homomorphism densities in graphons. The conjectured inequality can be interpreted as a statement that the density of copies of in a graph is asymptotically minimized by a random graph, as one would expect a fraction of possible subgraphs to be a copy of if each edge exists with probability .$

In spectral graph theory, the Alon–Boppana bound provides a lower bound on the second-largest eigenvalue of the adjacency matrix of a $-regular graph, meaning a graph in which every vertex has degree . The reason for the interest in the second-largest eigenvalue is that the largest eigenvalue is guaranteed to be due to -regularity, with the all-ones vector being the associated eigenvector. The graphs that come close to meeting this bound are Ramanujan graphs, which are examples of the best possible expander graphs.$

In statistics, modes of variation are a continuously indexed set of vectors or functions that are centered at a mean and are used to depict the variation in a population or sample. Typically, variation patterns in the data can be decomposed in descending order of eigenvalues with the directions represented by the corresponding eigenvectors or eigenfunctions. Modes of variation provide a visualization of this decomposition and an efficient description of variation around the mean. Both in principal component analysis (PCA) and in functional principal component analysis (FPCA), modes of variation play an important role in visualizing and describing the variation in the data contributed by each eigencomponent. In real-world applications, the eigencomponents and associated modes of variation aid to interpret complex data, especially in exploratory data analysis (EDA).

References

↑ Estrada, E. (2000). "Characterization of 3D molecular structure". Chem. Phys. Lett. 319 (319): 713. Bibcode:2000CPL...319..713E. doi:10.1016/S0009-2614(00)00158-5.
↑ de la Peña, J. A.; Gutman, I.; Rada, J. (2007). "Estimating the Estrada index". Linear Algebra Appl. 427: 70–76. doi: 10.1016/j.laa.2007.06.020 .
1 2 3 Estrada, E.; Rodríguez-Velázquez, J.A. (2005). "Subgraph centrality in complex networks". Phys. Rev. E. 71 (5): 056103. arXiv: cond-mat/0504730 . Bibcode:2005PhRvE..71e6103E. doi:10.1103/PhysRevE.71.056103. PMID 16089598. S2CID 4512786.

Zhou, Bo; Gutman, Ivan (2009). "More on the Laplacian Estrada Index". Appl. Anal. Discrete Math. 3 (2): 371–378. doi: 10.2298/AADM0902371Z .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Estrada, E. (2000). "Characterization of 3D molecular structure". Chem. Phys. Lett. 319 (319): 713. Bibcode:2000CPL...319..713E. doi:10.1016/S0009-2614(00)00158-5.

[2] Peña, J. A.; Gutman, I.; Rada, J. (2007). "Estimating the Estrada index". Linear Algebra Appl. 427: 70–76. doi: 10.1016/j.laa.2007.06.020 .

[Estrada-3] 1 2 3 Estrada, E.; Rodríguez-Velázquez, J.A. (2005). "Subgraph centrality in complex networks". Phys. Rev. E. 71 (5): 056103. arXiv: cond-mat/0504730 . Bibcode:2005PhRvE..71e6103E. doi:10.1103/PhysRevE.71.056103. PMID 16089598. S2CID 4512786.

[1]

[2]

[3]