September 21st, 2003

  • evan

graphing, social networks

The SNA Package
This is a fully documented collection of R routines for social network analysis; utilities included range from hierarchical Bayesian modeling of informant accuracy to logistic network regression (with QAP and CUG tests). Quite a few low-level utilities for plotting and transforming networks are available as well, along with many of the usual centrality and distance measures.

I keep trying to learn R, but I think I am missing some crucial intuition for making everything fit together. (Here’s a hint: they use the period in function names in the way they use underscores in other languages, as a spacer and *not* as a “member-of” operator.)

I want to graph the data I’ve been collecting on LiveJournal. I have unix timestamps and the time it took to load the LJ front page at that time. The hurdles are:
  1. I don’t have data for every time point, so I cannot simply plot load times and I must use the unix times for the x axis.
  2. I need to convert the unix times to real times upon display, but I need them as unix times (ie, plain integers) for graphing/comparison.
  3. The data is really bumpy and needs smoothing, and I don’t even know how to begin to approach that.
  • evan

"Cloneproof Schwartzian Sequential Dropping"

Dear Martin,

you wrote:
> Condorcet voting lets you rank the options. I imagine the
> poll code could share the option-reording javascript from
> picpix (if Brad would agree to relicense it as GPL to work
> on LJ, which I can’t see why not). I’m really uncomfortable
> using Perl, especially in knowing when to use references and
> when not to. (You can laugh at my code here. Feedback would
> be welcome. I’m especially concerned about the potential O(n^4)
> algorithm for the, uh, “cloneproof Schwartz Sequential Dropping”
> / “Beatpath Winner”.)

Actually, there is an O(n^3) algorithm.

I have attached the paper “A New Monotonic and Clone-Independent
Single-Winner Election Method.” This paper has been accepted for
publication in “Voting Matters.”

Markus Schulze
His paper is apparently on the method known elsewhere as Beatpath Winner or Cloneproof Schwartzian Sequential Dropping, which is what I tried to implement for LiveJournal. But, as the introduction observes:
...most implementations I have seen were inefficient because the programmers have not understood the Floyd algorithm so that the implementations had a runtime of O(N^5) although the winners of this method can be calculated in a runtime of O(N^3), where N is the number of candidates.
But taking a step back, I really hope we never have an election where N is large enough that the difference between N^3 and N^5 matters... :)