Modeling graphs using dot product representations (Q626245)

A dimension reduction technique is proposed which allows to represent weighted graphs (or a set of graphs on a common vertex set) by a collection of vertexes in \(R^d\). The vectors \(x_1\),\dots,\(x_n\) corresponding to the vertexes of the graph are taken to minimize \(\sum_{i\not=j}(x_i\cdot x_j-a_{ij})^2\), where \(\cdot\) means the inner product in \(R^d\), and \(a_{ij}\) is the weight of the edge joining \(i\) and \(j\). An iterative algorithm is proposed solving this minimization problem. Since the solution is not unique the authors discuss a rotation technique for comparison of ``nearly the same'' graphs representations. A modification of the algorithm is considered allowing missing data. A vertices clustering technique is developed based on this vector representation.