## September 21st, 2003

### 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.

### "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... :)