Finding most Important Node(s) in a Directed Graph

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 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 1

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 on wikipedia for the definitions and details.

Answer 2

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!

Answer 3

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.

Answer 4

Just by sketching this out on a piece of paper, I opted for the depth-first search. Why? Well, by using the idea mentioned above, of traversing the graph by following the directed edges, we can ideally keep track of how many times we visit a particular node by incrementing some stored integer. You could do it just as easily with breadth-first.

void search(node) {
    nodeInitial = pick a node
    for(nodeInitial:outgoingNodes as node) {
        node:visits++ // this is how you track in-edges
        if(node is unvisited) {
            search(node)
            node:visited = true
        }
    }
}

Part of the problem is that with a directed graph, you might have sub-graphs that are connected to themselves, but are not connected externally. Other parts of the graph might connect to these sub-graphs, but there may be no outgoing connections. Think of an island (or group of islands) that has 3 one-way inbound-only highways traveling towards it but no outgoing highways. I think this is the bigger challenge - how to go about selecting parts of the graph that are unvisited. The only way I can think to do this would be if the nodes themselves also keep track of what other nodes are pointing at them (incoming nodes). From there, you would need to modify the algorithm so that it chooses a new node from some incoming node after it's done a complete traversal of an entire sub-graph. Then hop over to that other sub-graph and traverse it until you need to jump to the next sub-graph, etc.

I think it would be easy enough to store the "most important" node with the most in-edges by simply creating a single, separate node object that would be updated as you traverse the graph.

Node mostImportant = null

void search(node) {
    nodeInitial = pick a node
    if(!mostImportant) {
        mostImportant = nodeInitial
    }

    for(nodeInitial:outgoingNodes as node) {
        node:visits++ // this is how you track in-edges

        if(node.visits > mostImportant.visits)
            mostImportant = node

        if(node is unvisited) {
            search(node)
            node:visited = true
        }
    }
}

Answer 5

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.

Answer 6

Algorithms typically try to optimize one thing or the other. Even NP problems are solvable, except that they require all possible combinations to be tried, which makes them computationally expensive. In the problem you are trying to solve, the question is what is it that you are trying to optimize: time, memory, or something else?

Given that it is 2 million nodes, it is unclear whether they are all read in memory at once, or if they reside on disk and thus memory management and minimization of I/O might be a factor.

Assuming that your entire graph is in memory, the question is who creates the graph? Can you keep a count of the edges for nodes in the graph during creation (or when reading from disk) and keep them in an ordered list?

The other thing is that sometimes a graph can have two or more completely disconnected parts in practical life (I have had to deal with one such graph). In such cases, I have found it more useful to iterate through all the nodes (no matter breadth first or depth first), and then count all the edges on every node -- in most cases, modern languages will keep all the edges in some sort of a collection and you will already have a property or method to get the length or count on that collection, thus saving iteration over all the edges).

The complexity for both these solutions can be O(n log n) where n is the no. of nodes.

Although time and memory is often of concern, but sometimes simplicity is more important than those attributes, so I keep that in my equation too. In many situations, such as this, I would consider complexity of implementation as yet another factor in my pro/con list before deciding what to implement.