[Date Prev] [Date Next] [Thread Prev] [Thread Next] Indexes: Main | Date | Thread | Author

Re: [ba-ohs-talk] spring and force directed graphs

>There is a current implementation of the Spring algorithm for
>displaying document similarity matrices and other networks. It's not
>very featured, has a poor data representation, and is inefficient. It
>is being used to represent the similarity between documents discovered
>by latent semantic analysis. It only works for about 100 nodes or
>less.    (01)

Hi Chris,    (02)

So I take it that a similarity matrix has real numbers corresponding to the 
similarity between any of the two items.    (03)

This is actually quite a different problem then the one that TG's layout 
addresses.    (04)

Since similarity matrices are a pretty frequent occurrence, and are 
mathematically simple, I would assume that there are lots of publicly 
available algorithms for converting them into graphs.  What you would need 
is an algorithm that quickly finds an optimal layout, without displaying 
the intermediate results (like TouchGraph does).  I am sure that you could 
find something that lays out networks of over 1,000 nodes in under a 
minute.  Also, I know that both document visualization and social network 
analysis rely on similarity matrices, so you might want to check out how 
graphs are generated in both of these fields.    (05)

>Can people point me to information that has been helpful in their own
>investigations of designing, programming and using algorithms for
>drawing graphs? I'm especially interested in:
>- overviews of the reasoning used in designing these sorts of
>   algorithms    (06)

I think that if you are displaying a similarity matrices, then a Spring 
algorithm is Not the way to go.  There are lots of other ways to display 
them, for instance http://zing.ncsl.nist.gov/~cugini/uicd/viz.html is a 
link I found searching for "semantic document visualization" that displays 
some better techniques.  I would consider going for a 3d rather then 2d 
approach, since a lot of information would be lost by flattening the 
network out into 2d (unless you are interested in the degrees of similarity 
to a single document, in which case a radial graph is the way to go).    (07)

>What I'd like to have at the end of this is a system that allows for
>the display of similarity matrices and clustering in the same display.
>Clusters are displayed in the network and when selected can be zoomed
>for detail of  their contents.    (08)

Similarity matrices/clustering, huh?  Here is a paper that talks about 
this:  http://www.hpl.hp.com/techreports/2000/HPL-2000-160.pdf  I guess 
that this possibility could be further researched, but why would you not 
want to use maps instead?  Check out 
http://www.cybergeography.org/atlas/info_maps.html  Maps allow you to show 
"clusters" of information at a top level, which can then be zoomed in to in 
order to see the info in depth.    (09)

What do you think?
--Alex    (010)

>This is more math than I know at the moment, but I guess I'll be
>picking it up.
>Thanks for input.
>Chris Dent  <cdent@burningchrome.com>  http://www.burningchrome.com/~cdent/    (011)