Re: [igraph] S metric

[Tamás Nepusz]

I'm trying to calculate Doyle et al (2005)'s S metric (rather than

their s-metric). It's explained here in equations 1) and 2) on Page 2:

http://nguyendangbinh.org/Proceedings/IPCV08/Papers/MSV4869.pdf

This isn't implemented in iGraph is it?

No, it isn't implemented yet. If you happen to implement it in C, feel free to contribute a patch. R and Python versions are also welcome - they will be added to the wiki at http://igraph.wikidot.com.

 

> The s-metric is easy enough to implement but I don't understand what smax(w(G)) means in Equation 2, to calculate S.

I think s_max is attained if you construct the graph using the Havel-Hakimi algorithm as follows (see http://en.wikipedia.org/wiki/Degree_(graph_theory)):

1. Begin with a graph with no edges.
2. Maintain a list of vertices whose degree requirement has not yet been met in non-increasing order of residual degree requirement.
3. Connect the first vertex to the next d₁ vertices in this list, and then remove it from the list. Re-sort the list and repeat until all degree requirements are met. 

Hope this helps.

Cheers,

Tamas