Post:RE: Plotting time
Author: Brian Junker 
Posted Date: January 15, 2014 9:10 PM
Status:Published

I think that most of the time is spent in the layout algorithm.  For
example, force-directed algorithms like Fruchterman-Reingold require
repeated calculation of the force between every pair of nodes, which
grows quadratically with the number of nodes in the graph.

http://en.wikipedia.org/wiki/Force-directed_graph_drawing ain't bad,
and contains references.

The following are interesting:

http://bioinformatics.oxfordjournals.org/content/19/15/1882.long -
improving the run-time of force-directed algorithms by "chunking" the
graph and locating chunks of nodes before you locate the nodes
themselves.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.13.8444&rep=rep1&type=pdf
- the original fruchterman-reingold paper

http://cs.brown.edu/~rt/gdhandbook/ - a handbook of methods for
drawing network graphs

Some subset of this literature might make an interesting class
presentation.

-BJ

=========

RE: Plotting time
Author: Momin Malik 
Posted Date: January 15, 2014 11:44 PM
Edited Date: January 15, 2014 11:47 PM

Many or even most people I know in network analysis use Gephi
(http://gephi.org/) to visualize networks. It includes a bunch of
algorithms from Yifan Hu, which usually have nice results. I've
attached his review paper on visualizing large networks.

Katy Börner's collection, the Atlas of Science
(http://scimaps.org/atlas/) has some gorgeous visualizations of
large-scale networks. I bring it up because one algorithm I didn't see
Hu mention is VxOrd
(http://www.cs.ubc.ca/~tmm/courses/cpsc533c-04-spr/readings/clusterstab.pdf),
which is used for several of the visualizations in the book (e.g.,
http://scimaps.org/maps/map/the_structure_of_sci_59/). It's
implemented in Gephi as OpenOrd
(https://gephi.org/2010/openord-new-layout-plugin-the-fastest-algorithm-so-far/,
https://marketplace.gephi.org/plugin/openord-layout/).

One other alternative I know of is Nees Jan van Eck and Ludo Waltman's
VOS Viewer (http://www.vosviewer.com/). VOS is "Visualization of
Similarities"
(http://link.springer.com/article/10.1007%2Fs11192-009-0146-3), an
algorithm that translates similarity into position by minimizing the
sum of the weighted Euclidean distances between each pair of nodes
(where the weight is the similarity), plus a constraint to prevent
trivial solutions. I.e., non-force-directed, plus it gives explicit
coordinates. I think I saw a paper of theirs that said VOS can handle
millions of nodes, but I don't see any examples on their site so I
might have misremembered.

Attachment: File Yifan Hu 2011 Algorithms for Visualizing Large
Networks.pdf (2.481 MB)