igraph-help
[Top][All Lists]

## Re: [igraph] S metric

 From: Tamás Nepusz Subject: Re: [igraph] S metric Date: Sat, 25 Feb 2012 20:28:00 +0100

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 d1 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