Data visualization through graph drawing (Q1861627)

Let there be \(n\) objects \(v_i\), \(i=1,\dots,n\), and the adjacency matrix \(A=\{a_{ij}\}_{i,j=1}^n\) where \(a_{ij}\in\{0,1\}\), and \(a_{ij}=1\) means that \(v_i\) and \(v_j\) are adjacent (connected). The problem is to represent \(v_j\) by points \(z_j\in R^s\) such that \[ \sigma_\phi(Z)=\sum_{i,j=1}^n a_{ij}\phi(d(z_i,z_j))\to\min, \] where \(d\) is a distance in \(R^s\) (e.g., \(l_p\)-distance) and \(\phi\) is a fixed increasing function. A minimization algorithm is proposed in the case where \(\phi(d(z_i,z_j))\) is the squared \(l_2\)-distance. An iterative procedure using minimization of surrogate functions at each step is considered for more general cases. Applications to bipartite graphs and parallel coordinate plots are considered.