D. Des Chene (![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small} goclenius) wrote,@ 2008-06-17 01:44:00 |
|
| Entry tags: | combinatorics, graphs, mathematics, visualization |
Visualizing large graphs
Start with a set of nodes (picture them as dots). Suppose there are n nodes in all (say 3), numbered from 1 to n. Construct an n by n table (if there are 3 nodes, it will look like a blank tic-tac-toe board). Put a 1 in the entry in row i, column j to indicate that there is an edge from node i to node j. (Edges can be pictured as arrows connecting the dots.)
The result is called a directed graph, “directed” because each edge has a starting and an ending node. (In the case of 3 nodes, the table will look like a finished game of tic-tac-toe, with 1s for Xs and 0s for Os.) The table is called the “adjacency matrix” of the graph.
A sparse matrix is a matrix most of whose entries are zero. A sparse adjacency matrix corresponds to a graph with rather few edges. Airlines don’t schedule direct flights between every pair of cities they serve; instead relatively few cities are joined directly, so that in most cases to get from one city to another you’ll have to go through a “hub”. The adjacency matrix that corresponds to the airline graph will be sparse.
Source: Airline Route Maps
All this by way of introducing some striking images. A research group at AT&T (more research! less spying!) has put together a gallery of large graphs. The sparse matrices represented in the gallery come from the Sparse Matrix Collection at the University of Florida. The collection contains 1890 matrices from a wide range of projects: fluid dynamics, quantum chemistry, network analysis… The example below is described only as arising in connection with an optimization problem.
Yifan Hu, Gallery of large graphs
