Links
Pajek
Pajek is excellent network analysis and visualization software written for Windows (but it runs in Wine under Linux as well). It can handle quite large (millions of vertices) graphs smoothly. Its main drawbacks are that (1) it is interactive, (2) closed source, (3) hard to extend.
UCINet
UCINet is a collection of graph analysis software, it also includes Pajek. It's intended audience is social scientists, and cannot handle large graphs well. It can be used freely for 30 days and it is closed source.
The Boost Graph Library
The Boost Graph Library is an impressive library written in C++ for manipulating graphs. It is quite fast, and can handle moderately large graphs. A good choice for anyone who likes programming in C++, but it also has interfaces to some higher level languages.
NetworkX
NetworkX is another nice piece of software written in Python.
SNA
SNA (Social Network Analysis) is an extension package to the GNU R system. It is useful for small graphs only, as it uses adjacency matrices.