-
-
Notifications
You must be signed in to change notification settings - Fork 403
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Wishlist: value propagation method #2595
Comments
This needs some clarifications. It will also help to link some real use-cases (not just describe them, but link some references).
It seems to me that if this is done, it'd be useful to implement a generalized version where one can control how the update to a vertex depends on its neighbours. Then there are performance tradeoffs on the generality of this update function: can the user choose an arbitrary function (unclear if this can be faster than a high-level implementation) or just control the parameters of a fixed function? It'd be good to see a number of applications of such value propagation to be able to decide what level of generality makes sense. |
|
What is the feature or improvement you would like to see?
An igraph.Graph method called "value_propagation" that would take four parameters:
Given a vertex ordering, from beginning to end add each vertex value, divided by the number of neighbors then multiplied by the discount factor, to its neighbors' values along the outbound (or inbound) edges. This may also accept a weight parameter that specifies if the vertex value should be distributed unevenly to its neighbors based on the relative weights.
Input: igraph.Graph.value_propagation(order=('topo','vertex_attribute'), discount = 0.05, mode = c('in', 'out'))
Output: array of leaf vertices (vertex IDs), array of leaf vertex weights (signed floats)
Use cases for the feature
Value propagation is a useful heuristic for open-pit mining resource-constrained project scheduling problems. In these problems, blocks are represented by vertices and the precedence relationship between blocks is represented by edges. Values from all blocks beneath the surface are projected onto the surface via precedence edges, from bottom to top. The result is a set of weights for blocks at the surface (i.e., vertices with no outbound edges) that indicate which blocks lead to higher net present value, where the present value is derived from a provided discount factor.
References
igraph forum
The text was updated successfully, but these errors were encountered: