Graph algorithm to compute node values based on neighbouring nodes

6
votes

I would like to make a graph algorithm that updates/computes the value of a node f(n) as a function of each of the f(n) values of neighboring nodes.

  • The graph is directed.
  • Each node has as initial f(n) value.
  • Each edge has NO cost (0).
  • The value of each node is the maximum of its current value and the value of each neighboring nodes (directed graph, so neighbors are the ones from where the node has incoming edges).

More formally,

f(n) = max(f(n),max_i(f(n_i))), where i from neighbor 1 to neighbor k.

I can visualize a few ways of doing so, however I do not know to what extend they are optimal.

Can anyone please give suggestions and commentaries (whether do you think your suggestion is optimal) or suggest any existent graph algorithm I can adapt?

1
algorithmgraphgraph-theorygraph-algorithm
Are you familiar with Page Rank and its matrix implementation? - amit
Also: Are the values guaranteed to converge? (Page rank takes care for it using the "random jump", which makes the graph apply the conditions of Perron–Frobenius theorem). - amit
Fleshing out amit's comment: Do you intend to run this algorithm repeatedly, until it converges (no f(n) values change)? - j_random_hacker
Thanks very much for your very useful comments. I'm not very familiar with pagerank matrix implementation but following your hint i'm looking into it. As for convergence, I guess the use of the max function (without any sum function) guarantees convergence... the highest value of each node in the network will always be less or equal to the highest (initial node value plus edge value) combination. I intend to run this algorithm every time an app starts or-if used in a server-on a regular basis (eg one time per second on a graph of 1 hundred nodes).. but I want to run until the values are exact. - user1528976
@user1528976 note that the max() has a summation inside of it. I am not sure I understand what c(n,n_i) is (I think it is a weight for edge) - but if could make the function not converge. Have a look on the graph: a<-1->b (two nodes, with an edge of cost 1 from a to b and an edge of cost 1 from b to a). Regardless of the initial cost of a and b, the function f(a) and f(b) will go to infinity, because every iteration is adding 1. - amit

1 Answers

6
votes

Claims:

  1. In each Strongly Connected Component V in the graph, the values of all vertices in this SCC have the same final score.
    "Proof" (guideline): by doing propogation in this SCC, you can iteratively set all the scores to the maximal value found in this SCC.

  2. In a DAG, the value of each vertex is max{v,parent(v) | for all parents of v} (definition) and the score can be found within a single iteration from the start to the end.
    "Proof" (guideline): There are no "back edges", so if you know the final values of all parents, you know the final value of each vertex. By induction (base is all sources) - you can get to the fact that a single iteration is enough to determine the final score.

  3. Also, it is known that the graph G' representing the SCC of a graph g is a DAG.

From the above we can derive a simple algorithm:

  1. Fing maximal SCCs in the graphs (can be done with Tarjan algorithm), and create the SCC graph. Let it be G'. Note that G' is a DAG.
  2. For each SCC V: set f'(V) = max{v | v in V} (intuitively - set the value of each SCC as the max value in this SCC).
  3. Topological sort the graph G'.
  4. Do a single traversal according to the topological sort found in (3) - and calculate the f'(V) for each vertex in G' according to its parents.
  5. Set f(v) = f'(V) (where v is in the SCC V)

Complexity:

  1. Tarjan and creating G' is O(V+E)
  2. Finding f' is also linear in the size of the graph - O(V+E)
  3. Topological sort runs in O(V+E)
  4. Single traversal - linear: O(V+E)
  5. Giving final scores: linear!

So the above algorithm is linear in the size of the graph - O(V+E)