[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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:


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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]