I need to perform value propagation with discounting on my graph, which I realize is similar to PageRank. However, I only need to do one pass in topological order and I need to use weights/values assigned to vertices instead of edges. Also, there is not a need to normalize values in my case. Is there already a method that does that? Would it be difficult to add something like that to igraph natively?
Actually, I believe this is not actually PageRank and I would need a custom solution. I am developing purely in Python and trying to avoid creating a wrapper, so if any of the igraph developers are willing to hear out my use case please let me know!
It is unclear what you are trying to do. Can you give a mathematically precise and unambiguous description of the problem, ideally with an example?
Problem Statement:
Given a directed acyclic graph (G) and an initial set of vertices (V’), disperse the value of each vertex to its neighboring vertices in topographical order for all vertices in G reachable from V’. If arcs are unweighted then values should be dispersed evenly amongst neighbors. If undiscounted then values are not discounted at each step. If V’ is an empty set then it should process all vertices in topographical order. NOTE: I am not sure this needs to be restricted to DAGs, but my case is a DAG so I framed it that way.
Input:
G - graph
r - vertex values
w - edge weigts
V’ - set of starting vertices
d - discount rate
Output:
propagated weight for all vertices in G
Example:
G = {(0, 1), (0, 2), (1, 3)}
r = [10, -4, 8, 4]
w = [1, 1, 1, 1]
V’ = {0}
d = 0.9
prop_weight[0] = 10
prop_weight[1] = (10 / 2) * 0.9 - 4 = 4.5 - 4 = 0.5
prop_weight[2] = (10 / 2) * 0.9 + 8 = 5.5 + 8 = 12.5
prop_weight[3] = (0.5 / 1) * 0.9 + 4 = 0.45 + 4 = 4.45
returns [10, 0.5, 12.5, 4.45]
Thoughts:
I think this is potentially like the community_label_propagation method but for continuous labels instead of categorical. It also seems similar to PageRank.
A quick-and-dirty solution:
from igraph import Graph
# Initial parameters
g = Graph([(0, 1), (0, 2), (1, 3)], directed=True)
r = [10, -4, 8, 4]
weights = [1, 1, 1]
start = {0}
d = 0.9
# Normalize weights
out_strengths = g.strength(weights=weights, mode="out")
weights = [weight / out_strengths[u] for weight, (u, _) in zip(weights, g.get_edgelist())]
# Do the calculation
for v in g.topological_sorting():
for u in g.predecessors(v):
eid = g.get_eid(u, v)
r[v] += weights[eid] * d * r[u]
print(repr(r))
Note that the set of starting vertices was not needed; it was implicitly determined by the DAG ordering.
I believe that a similar formulation could be obtained for non-DAG graphs with some kind of an eigenvector equation.
I’ve been using this quick and dirty solution for a few months now, but it is still quite slow. Is it not reasonable to add some kind of ordered value propagation to igraph that would be more performant? I’m surprised this isn’t a use case that has been covered, but I can’t seem to find many similar problems online either so I suppose it makes sense.