Using custom edge weights when computing graph statistics

[duhaime]

It looks like right now all edges have a weight of one, at least in the eccentricity score computation. Have you given any thought to allowing users to specify custom edge weight accessors to compute the eccentricities of weighted graphs?

[anvaka]

I haven't thought about it, but I think this is totally valid request. I can give it a try later this or next week, unless anyone else wants to give it a shot

// CC @AVermeij

[duhaime]

@anvaka I was thinking of updating the method signature of eccentricity like so:

function eccentricity(graph, oriented, weight)

where weight would be an attribute accessor that would pull the weight from the data associated with a given link add add that value rather than 1 in line 59 of eccentricity. If you think this should be done differently I'm happy to go that way instead.

While implementing this change, however, I found that my directed links were not identified by graph.forEachLinkedNode() in a predictable fashion--in the callback to that function the source node was sometimes v and sometimes w, so one would need to try catch when attempting to access the weight attribute via a getLink(source, target) call. Is there a method that returns only those nodes that are a target of a given node?

[AVermeij]

In the betweenness, closeness and eccentricity calculations, we're currently using an SSSP function which does not take into account edge weights. When working with weighted graphs, the usual thing to do would be to use Dijkstra shortest path algorithm instead (see https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm).

For further inspiration, there's an implementation of this available in the JSNetworkX: https://github.com/fkling/JSNetworkX/blob/master/src/algorithms/shortestPaths/weighted.js

I unfortunately don't have time on my hands to implement this, but I definitely think it's worth a shot!

[duhaime]

Thanks @anvaka that's very helpful. I currently need to compute graph diameter for a directed, weighted graph, so am happy to implement something along those lines. I'm nearly done with Floyd-Warshall, but it seems the complexity of Djikstra's algorithm is better, so I'll try that out next...

[anvaka]

function eccentricity(graph, oriented, weight)

I think we can make two last options into one:

/**
 * @param {ngraph.graph} graph
 * @param {Object} options
 * @param {Boolean} options.directed - whether graph should be considered directed
 * @param {Function(link)} option.weight - a function that returns weight for a given link
 * If not specified, the weight is assumed to be 1 for all edges.
 */
function eccentricity(graph, options)

Or something along these lines - that way we can extend this further in future.

As for graph.forEachLinkedNode() - can you give me a small example, so that I can reproduce this?

By the way, you guys might like this new module (not published to npm yet, but will be done later this week): ngraph.path - it implements A path finding, and has very good performance (I'm using proper priority queue there). For A, if you don't pass any arguments - it would be equivalent to Dijkstra. Repository has an example how to run weighted calculation as well.

It feels like if we can pass it as a pathfinder into this module, we'd be able to extend range and speed of possible centrality calculations.