D. Des Chene (goclenius) wrote,
D. Des Chene

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.
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.
From Infosthetics via 0xCD. If you like matrices, visit the Matrix Market at NIST.
Tags: combinatorics, graphs, mathematics, visualization
  • Post a new comment


    Comments allowed for friends only

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened