Finding coordinates of nodes in a graph

175 Views Asked by At

I have a complete graph in which the edges represent the euclidean distance between the nodes which is known. Assuming a node to be (0,0), I want to find (approximately) the coordinates of other nodes. I read in a paper that we can use optimization for this. This is the equation in in the paper.

http://latex.codecogs.com/gif.latex?$$%5Cmin_%7Bx,y%7D%5Cleft%28%5Csum_%7Bi=1%7D%5E%7Bn%7D%5Csum_%7Bj=i+1%7D%5E%7Bn%7D%28x_%7Bi%7D-x_%7Bj%7D%29%5E%7B2%7D+%28y_%7Bi%7D-y_%7Bj%7D%29%5E%7B2%7D-d_%7Bij%7D%5E%7B2%7D%5Cright%29$$

$$ \min\limits_{x, y}\left(\sum_{i = 1}^n \sum_{j = i+1}^n (x_i - x_j)^2 + (y_i - y_j)^2 - d_{ij}^2\right) $$

(xi,yi) represent th relative positions of nodes separated by distance (dij). Looks like least squares but I do not know how to solve it. Can anyone please explain?