Visualizing a graph with a million vertices
I also suggest Gephi software (https://gephi.github.io), which seems to be quite powerful. Some additional information on using Gephi with large networks can be found here and, more generally, here. Cytoscape (http://www.cytoscape.org) is an alternative to Gephi, being an another popular platform for complex network analysis and visualization.

If you'd like to work with networks programmatically (including visualization) in R, Python or C/C++, you can check igraph collection of libraries. Speaking of R, you may find interesting the following blog posts: on using R with Cytoscape (http://www.vesnam.com/Rblog/viznets1) and on using R with Gephi (http://www.vesnam.com/Rblog/viznets2).

For extensive lists of network analysis and visualization software, including some comparison and reviews, you might want to check the following pages: 1) http://wiki.cytoscape.org/Network_analysis_links; 2) http://www.kdnuggets.com/software/social-network-analysis.html; 3) http://www.activatenetworks.net/social-network-analysis-sna-software-review.