Menu
I'm looking for a one-pass algorithm (or ideas of how to write it myself) that can calculate the two or three dimensional coordinates for a directed, unweighted graph. The only metadata the vertices have are title and category.
I need to implement this algorithm in a way that vertices can be added/removed without recalculating the entire graph structure.
This algorithm has to be applied to a large (5gb) dataset which is constantly changing.
My Google skills have led me to n-pass algorithms which are not what what I am looking for.
209
In their review, force-directed algorithms were categorised based on spring and electrical forces, barycenter method, forces simulating graphs theoretic distance, energy functions and magnetic fields.
The Fruchterman-Reingold layout is a force-directed layout algorithm which treats edges like springs that move vertexes closer or further from each other in an attempt to find an equilibrium that minimizes the energy of the system.
The Yifan Hu Multilevel layout algorithm is an algorithm that brings together the good parts of force-directed algorithms and a multilevel algorithm to reduce algorithm complexity. This is one of the algorithms that works really well with large networks.
It calculates the layout of the graph based solely on the information contained in the graph structure rather than relying on domain-specific knowledge. The nodes are represented by points that repel each other like magnets. Borders connect these points by simulating a spring force to attract adjacent nodes.
I guess your question might still be an open issue. I know a research project called Tulip (http://tulip.labri.fr/TulipDrupal/) which is a (large-scale) graph viewer. A paper on the method is available at http://dept-info.labri.fr/~auber/documents/publi/auberChapterTulipGDSBook.pdf and surely you can find more algorithms browsing the personal web page of D. Auber and his colleagues.
122
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
