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)