# How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)

How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)? See details in the following.

Given a graph $$G = \{V,E\}$$, we have a distance matrix (the shortest path matrix of $$G$$)

$$$$\mathbf{D}_t=\{\theta_{u,v}|\forall v,u\in V\},$$$$ how to embed the graph $$G$$ into the $$(k,d)$$-kautz metric space, that is, optimize the coordinate $$x_v$$ of each node $$v$$ in the $$(k,d)$$-kautz metric space to minimize the difference between $$\rho(x_v,x_u)$$ and the distance matrix $$\mathbf{D}_t$$, as $$$$\label{eq:kautz_mds} \min_{\{x_v|\forall v \in V\}} \sum_{\forall v,u\in V} |\rho(x_v,x_u) - \theta_{u,v}| \ \ (1)$$$$ where the coordinate $$x_v$$ is a string of $$k$$ characters and $$\rho(x_v,x_u)$$ represents the distance between $$x_v$$ and $$x_u$$. In the coordinate string $$x_v$$, each character has $$d$$ choices, and the adjacent characters are different, which is formulated as $$\begin{equation*} \begin{split} &x_v = a_{1,v} a_{2,v} ...a_{2,v}...a_{k,v},\\ % \textrm{s.t.\ } &\textrm{where}\ \ \forall i\in[1,k-1], a_{i,v} \in [1,d], \ a_{i,v}\neq a_{i+1,v}. \end{split} \end{equation*}$$ The distance $$\rho(x_v,x_u)$$ is the length of the longest common prefix and suffix between $$x_v$$ and $$x_u$$, which is formulated as $$$$\rho(x_v,x_u)= k-\max(lcp(x_v,x_u), lcp(x_u,x_v))$$$$

$$$$lcp(x_v,x_u) = \max\ i,\ \ \textrm{s.t.}\ a_{1,v}... a_{i,v} = a_{k-i+1,u}... a_{k,u}$$$$ The optimization problem in Eq. (1) is equivalent to $$$$\label{eq:kautz_mds_transform} \min_{\hat V_s} \|\mathbf{D}_t-S(\mathbf{D}_s,\hat V_s)\|,\ \textrm{s.t.}\ \hat V_s \subset V_s, |\hat V_s| = |V| \ll |V_s|, (2)$$$$ where $$\mathbf{D}_s$$ is the distance matrix of all feasible coordinates in the $$(k,d)$$-kautz metric space, $$$$\mathbf{D}_s=\{\rho(x_v,x_u)|\forall v,u\in V_s\},\$$$$ $$V_s$$ is the set of all feasible coordinates in the $$(k,d)$$-kautz metric space, and $$S$$ is to select a sub-matrix $$S(\mathbf{D}_s,\hat V_s)$$ from $$\mathbf{D}_s$$, \ie the distance matrix of $$\hat V_s$$. The problem in Eq. (2) is to select some coordinates $$\hat V_s\subset V_s$$ as the coordinates of all nodes in the graph $$G$$ to minimize the difference between the target distance matrix $$\mathbf{D}_t$$ and the distance matrix $$S(\mathbf{D}_s,\hat V_s)$$ of $$\hat V_s$$.

• Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking.
– Community Bot
Apr 17, 2023 at 9:11
• Cross-posted: mathoverflow.net/questions/444941/… Apr 17, 2023 at 19:05