Gephi: Interactive visualization and exploration platform for networks, graphs (gephi.github.io)

Gephi is really nice for smaller data sets, however just like most other widely available and free tools it becomes useless once you get to large graphs.

Part of it is just the complexity of graph algorithms. No getting away from O(n^2) and worse.

It's one of the most capable tools of its kind.

I've thrown hundreds of thousands of nodes and edges into it and it's worked great.

Cool test is importing a package dependency graph for all the ubuntu packages.