I have a series of spatial polygons on a 2D plane (Fig a). These polygons can be represented as a graph where neighbouring polygons are linked and the location of the nodes is dictated by the centroid of the polygon (e.g. Fig b).
I want to map each node to a point on a grid (e.g. Fig c) whilst maintaining as much topological similarity as possible. I.e. to find the graph (which will have the same number of nodes) that is most topologically similar to the existing graph but under two constraints:
By topologically similar I mean having the same neighbours and ideally having as similar as possible spatial relationships (e.g. polygons remain on similar sides of another).
I am aware that certain graph similarity methods could be used (e.g. https://wadsashika.wordpress.com/2014/09/19/measuring-graph-similarity-using-neighbor-matching/ and graph kernels can be understood to measure the similarity of graphs.
Is there any way of calculating / generating the graph that is most similar (optimal) given certain constraints (i.e. moving the nodes to a grid). I see it as an optimisation problem but I’m not aware of any formal algorithms that identify optimally similar graphs (when using topology as a metric).
Should any solutions exist i will be looking to implement them in R and thanks in advance for any insight!
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4
