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$)

\begin{equation} \mathbf{D}_t=\{\theta_{u,v}|\forall v,u\in V\}, \end{equation} 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 \begin{equation} \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) \end{equation} 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 \begin{equation} \rho(x_v,x_u)= k-\max(lcp(x_v,x_u), lcp(x_u,x_v)) \end{equation}

\begin{equation} lcp(x_v,x_u) = \max\ i,\ \ \textrm{s.t.}\ a_{1,v}... a_{i,v} = a_{k-i+1,u}... a_{k,u} \end{equation} The optimization problem in Eq. (1) is equivalent to \begin{equation} \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) \end{equation} where $\mathbf{D}_s$ is the distance matrix of all feasible coordinates in the $(k,d)$-kautz metric space, \begin{equation} \mathbf{D}_s=\{\rho(x_v,x_u)|\forall v,u\in V_s\},\ \end{equation} $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$.

  • $\begingroup$ 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. $\endgroup$
    – Community Bot
    Apr 17, 2023 at 9:11
  • $\begingroup$ Cross-posted: mathoverflow.net/questions/444941/… $\endgroup$
    – RobPratt
    Apr 17, 2023 at 19:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.