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

*To*: ba-ohs-talk@bootstrap.org*From*: Alex Shapiro <alex@touchgraph.com>*Date*: Fri, 08 Mar 2002 15:15:07 -0500*Message-id*: <5.1.0.14.0.20020308135743.02b2b340@touchgraph.com>

>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)

**Follow-Ups**:**Re: [ba-ohs-talk] spring and force directed graphs***From:*<cdent@burningchrome.com>

**References**:**[ba-ohs-talk] spring and force directed graphs***From:*<cdent@burningchrome.com>

- Prev by Date:
**Re: [ba-ohs-talk] spring and force directed graphs** - Next by Date:
**Re: [ba-ohs-talk] FW: PARC Forum March 7 - Robert Wilensky** - Previous by thread:
**Re: [ba-ohs-talk] spring and force directed graphs** - Next by thread:
**Re: [ba-ohs-talk] spring and force directed graphs** - Indexes: Date | Thread | Author