Elastic energy of graph embedding into a multidimensional space

Elastic energy of a graph is a special type of penalty of embedding a graph into a multi-dimensional space. It combines the following fees:

1. U_E - total 'length' of the graph, i.e. total sum of the graph's edge squared lengths;
2. U_R - deviation from harmonic embedding, where harmonicity assumes that the center of each graph's star is the mean point of this star's leaves.

More precisely, let us have a graph G with a set of vertices V and a set of edges E. Let us associate a set of stars of the graph simply by using its structure (each node i having k>1 neighbours, adds to the set a k-star with the center in node i). Let E(i)⁽⁰⁾, E(i)⁽¹⁾ denote two vertices of the graph edge E(i); and Sk^(j)(0),..., Sk^(j)(k) denote vertices of the k-star Sk^(j) (where Sk^(j)(0) is the central vertex to which all other vertices are connected). Let us consider a map φ:V→R^m which describes an embedding of the graph into a multidimensional space R^m. The elastic energy of the graph embedding in the Euclidean space is defined as

Read the complete bibliography on elastic principal graphs and manifolds for more details.