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: 
I've found the following picture a good key for the difference between different measures (although undirected graphs are depicted, some apply to directed as well). Degree centrality [D] is straightforward: who has most in/out links. Eigenvector-centrality [C] captures the notion of indirect influence better. See [Centrality](https://en.wikipedia.org/wiki/Centrality) on wikipedia for the definitions and details. 

[![Undirected centrality measures](https://i.stack.imgur.com/tQeb6.png)](https://i.stack.imgur.com/tQeb6.png)
If it is not important which nodes connect to which, use a simple 2x2 matrix, which has a column for every node and a row that represent one node. each node that is connected get a value of 1 for the column. then add an extra column at the end of each row that counts the number of connections for that node. this does have huge over head up front but will get the most connected node and make node insertion and deletion easy if you know the size up front. If the size of the graph is dynamic then this will not work, works only for static graphs. Memory will also be an issue since you will have to use an array. But if finding the most connect node is the big issue this is a simple way to do it.