Question: I have a large (≈ 20 million nodes) directed Graph with in-edges & out-edges. I want to figure out which parts of of the graph deserve the most attention. Often most of the graph is boring, or at least it is already well understood. The way I am defining "attention" is by the concept of "connectedness" i.e. How can i find the most connected node(s) in the graph?

In what follows, One can assume that nodes by themselves have no score, the edges have no weight & they are either connected or not. 

[This website suggest](http://skillicorn.wordpress.com/2010/02/11/a-gentle-introduction-to-finding-the-most-important-node-in-graph-connected-data/) some pretty complicated procedures like n-dimensional space, Eigen Vectors, graph centrality concepts, pageRank etc. Is this problem that complex?

Can I not do a simple Breadth-First Traversal of the entire graph where at each node I figure out a way to find the number of in-edges. The node with most in-edges is the most important node in the graph. Am I missing something here?

Answer: 
Not knowing the real problem your graph solves or the details of your graph, this may not be relevant. But, I suspect your basic solution will be inaccurate in two ways: tie-breaking and what I might call "megalomaniacs." In other words, if you're just counting inbound connections, you'll likely run into nodes with the "same" importance; but, I suspect the intention is that one should be more important. And, in some cases, you may have "islands" of nodes that are all highly interconnected amongst themselves, but loosely so with the majority, yielding nodes that appear much more important than they are (megalomaniacs).

The solution? Well ... Something like pagerank, I imagine!
I assume that you want to calculate only 1st-order connectedness (i.e. counting how many edges link directly to the node).

I'll further assume you already have a list of all nodes with some place to store node weights and a list of all edges.

You'll need:

1. A list of all nodes, and a place to store the calculated weight for each node.
2. A list of all edges. As you proposed, any full traversal technique (such as breadth- or depth-first) should work as long as the graph is connected (although you may need additional space to track the exploration status of each node).

The algorithm is simple: iterate over each edge, and increment the weights of the From and To nodes referenced to by that edge.

Interpretation of the results to find "interesting" nodes is going to depend on the data-set. For example, web pages may be interesting if they have a high ratio of incoming to outgoing edges, but a graph of airports and flights might just look at the total traffic.