Hacker News Reader

Comment by theoh | Hacker News Reader

Sometimes the matrix, like for example the adjacency matrix for Wikipedia internal links, will be very sparse. Another reason to use relations rather than an inefficient, mostly empty implicit data structure.

That Wikipedia adjacency matrix would be interesting to visualize, though. There are tools out there for visualizing sparse matrices as graphs:

http://yifanhu.net/GALLERY/GRAPHS/

View on HN

I've never seen a visualization of a graph at the scale of Wikipedia that conveys anything useful in the visualization. You just get a big hairball.

Yeah, actually that page has a Wikipedia graph on it which looks exactly like a spiky sun.

I'd like to see more work like the paper from a few years ago which ran PageRank and HITS on Wikipedia to discover the most central pages. The PageRank result indicated church hierarchy and nation states were important, while HITS had things like "television" "animal" as the most authoritative/central pages.

There is so much structure there to be investigated.

The best you can usually do is clustering, but at that point you can just as well render clusters as single nodes and significantly lessen the strain on the visualization or the layout. I'm always astonished when customers ask about visualizing graphs with tens of thousands to millions of nodes. Thy usually have never thought about the UX implications of that (let alone the time needed to calculate a layout which results in an image so large that each node is smaller than a pixel anyway).

This is a very good point. In the early days of Graphviz we put a lot of effort into making very readable diagrams of fairly small graphs, mainly in drawing directed graphs (dot). We aimed at graphs with under a hundred objects. We agree with the viewpoint that it is better to apply some sort of analysis to reduce a larger graph to a smaller one that can be read and understood. People still want to draw much larger networks. In fact it is valid to want an overview of all the data, it's just not clear how to do this with many thousands of random connections. Graphviz sfdp (based on Yifan Hu's earlier work) and recent work on Maxent (which has a decent theoretical justification) and from Ulrik Brandes group are good examples. One reason graphviz neato does not make such great layouts of large graphs out of the box is that it is straight statistical multidimensional scaling, and we just drop shapes on top of the points, so they can overlap badly. We felt since people are relying on it for data visualization we did not want to post process the MDS layouts by default in a way that could be misleading. But you can turn on overlap removal (neato or sfdp -Goverlap=false). We really should document all this in one place that is easier to find and understand.

About the external shape loader issue - this code is somewhat centralized in graphviz/lib/gvc/gvusershape.c and in gvrender.c which calls it, and I thought it could be disabled at compile time (because we did address the security concerns at one point) and there's a lot of other machinery to control compile time features. Maybe John Ellson can comment here. Kudos to John for recognizing the problems with the shape loader as soon as I proposed it but apparently that didn't stop us at the time. Stephen North

"using relations" or a particular data structure wasn't at all the point of this particular discussion.

The point was that, for a simple directed graph, the edges represent a binary relationship. While for a weighted directed graph, it represents a relationship-matrix. For the graph being non-directed this would mean, that the relationship(-matrix) is symmetric.

Meaning that any algebra, algorithm, proof, etc. on graphs of that type can be applied for the other interpretation as well.

Implementation is a different question. "Most" binary relations we happen upon (less-than as the obvious) have an infinite domain and infinite cardinality (when represented as a set of tuples), making it very hard to "visualize" as a graph.

Your last sentence is pretty much a summary of my attempt to understand the amplituhedron, and as far as I've gottan

Reply on news.ycombinator.com