Evan A. Sultanik, Ph.D.

Political scientist Ed Burmila—sole remaining contributor to one of my favorite weblogs on the Internets, Gin and Tacos—just asked his readership,

What brought you here initially? Was I suggested by one of your friends? Did you arrive from a link on a different site – especially Crooks & Liars? Random internet search? Internet search specifically for gin and/or tacos? Saw a sticker on someone's car? Wrote three words in the search bar, hit ctrl-Enter, and hoped for the best?

I have been reading Gin and Tacos for almost its entire, decade-long existence. I didn't mean for that to sound so hipsterish, but there's not much other way to put it. I remember when I first stumbled on the site having entered "Robert Burnett" in my search bar, back in the days when G&T.com had more in common with its name than simply being awesome. I, like Ed, was a poor graduate student at the time, and I too had discovered the siren call of Sir Robert Burnett's London Dry Gin. (Perhaps I inherited this penchant from my advisor.)

Despite G&T.com's questionable Robert Burnett fan fiction, I was intrigued by Ed's, et al., historical sleuthing in trying to track down the truth behind the real Robert Burnett. Unfortunately, here is all they were able to conclude:

• Robert Burnett Jr. and Sir Robert Burnett were active in politics, however neither were mayor of London.
• The Burnett family was very active in military recruitment.
• Most importantly, that the Burnett family dealt in liquors.
• Finally, Sir Robert Burnett had a pretty damn nice estate.

Unfortunately, none of my research resulted in specific reference to gin. This is primarily due to the fact that the only available source to me was the Times of London, although there might have been advertisements for Burnett’s Gin in the Times, they did not come through on the search. Someone with more experience in alcohol oriented history could possibly do better.

I was no expert in history, however, like most Ph.D. students, I was a world renowned expert in procrastination. I therefore put everything else I needed to do on the back burner and took on the task. Here are my (now six year old) results:

• John Eamer, esq. and Robert Burnett, esq. Sheriffs of London, attending his Majesty to know his pleasure concerning the city address, were honoured with knighthood.

  The date that Sir Robert was knighted: Wednesday, April 15, 1795

• CHARLES LYNN. TRIED FOR MURDER. The following are the circumstances attending a murder committed at Whaddon Chase, Buckinghamshire, in the month of 1825, which at the time of its perpetration attracted a considerable portion of the public attention." ... "A coroner's inquest was held on the body of the deceased on the following day ; and then it appeared that the prisoner was the son of a respectable woman residing at No. 4, Morehall-place, Vauxhall, where she kept a confectioner's shop, and that he, as well as the deceased, had been employed in the vinegar manufactory of Sir Robert Burnett, at Vauxhall, as coopers.

  Sir Robert owned a vinegar factory. What's a common way to make white vinegar? Oxidation of distilled alcohol. I wonder where he got all of the distilled alcohol?

• Bond, Charles, late of Gravesend, * Kent, victualler, wine and spirit merchant, d.c. Surr. Dec. 18 and 28, and Jan. 22, at 12 each day.—Sols. Messrs. Saunders and Co. Upper Thames-street. Pet. Cred. John Fassett Burnett, Vauxhall, * Surrey distiller, and Robert Burnett, and Charles Fasset Burnett, his partners. Seal. Dec. 10.

  This page contains an excerpt from the London Gazette, December 11^th, 1824, listing recent local bankruptcies. I’m not sure what all of the abbreviations mean, but I assume “Pet. Cred.” means “Petitioning Creditors” (i.e., the creditors to Mr. Charles Bond that are petitioning for his bankruptcy for what I can only assume as defaulting on a loan). This means that Robert Burnett is a distiller who loaned some money to a spirit merchant. Now, why would a distiller (whom we have already established as probably being quite wealthy) waste his time giving a petty loan to a spirit merchant? Perhaps he had advanced Mr. Bond some product and wished compensation?

I also found numerous primary and secondary sources speaking of the Sir R. Burnett distillery in Vauxhall. There were a few mentions of gin, but they were in books that were not freely available online.

Is it true that everyone on earth is separated by at most six degrees? There's plenty of empirical evidence to support this claim already, so I am going to take a different, more theoretical approach.

Béla Bollobá;s, who is famous for having studied the properties of random graphs/networks with Paul Erdős (who is himself famous, among other things, for his degrees of separation from other mathematicians), discovered loose bounds on the diameter of random regular graphs. He proved the following:

In our case, $n$ would be the world population, which we can estimate at 6.93x10⁹. The parameter $r$ would be the minimum number of connections per person, which I think we can estimate at 130 (based on statistics from Facebook). Plugging in those values and solving for $d$ we get

This bound strictly increases as $\epsilon \rightarrow \infty$, so taking the limit as $\epsilon \rightarrow 0$ gives us the least $d$ that satisfies Theorem 1:

Therefore, by Theorem 1, the diameter of a graph on 6.93x10⁹ vertices with degrees at least 130 almost surely has a diameter of at most 8.

According to Bollobá;s, this bound could even be sharpened (meaning that it is likely the actual value is lower than 8). The bound will of course also be tighter if people actually have more than 130 connections. Also note that this is a bound on the maximum degree of separation between people; the average degree would likely be much lower.

In summary, in a population of 6.93x10⁹ in which each person is connected to at least 130 others, it can be said with extremely high confidence that the largest degree of separation between any two people is at most 8.

Now, at this point you might be saying to yourself: The real world social network is not a random graph! While Bollobás’s analysis does make the explicit assumption that the graph is random (which is a common tool in combinatorics), he only assumes that all graphs are equiprobable in the space of all $r$-regular graphs. That assumption is ultimately rendered moot by the strength of his result that almost all $r$-regular graphs—regardless of whether or not they are random—have this bounded diameter. The beauty is that Bollobás’s theorem applies to all (well, to be technical, “almost every”) $r$-regular graphs, not just ones that conform to the Erdős–Rényi model. In other words, we aren’t making any assumptions on the topology of the network other than its minimum degree. But there are certainly some tribal cultures that still exist that have little or no contact with the rest of the world, right? Well, let’s assume, conservatively, that there are at least 6 billion people in the population’s largest connected component. Then the bound on the degrees of separation for that largest component is still 8.

---

Now, on to the punchline.

If we assume that the number of connections per person, $r$, remains constant at 130, then we can set $d$ to 9 and solve for $n$ to get an estimate on the size of the population when the maximum degree of separation will increase. This will happen when the population is just under 10 Trillion. Assuming our current rate of population growth remains constant at about 1.14% per year, our population should reach 10 Trillion in about 640 years. Therefore, I conjecture that in the year 2651 we will have to create the "Seven Degrees of Separation Game"!

So, I’ve gotten rid of MediaWiki and switched back to Drupal (now in version 7). The old version of this site is still available here. I’ll be posting another blog entry in the coming days explaining why I’ve chosen to abandon MediaWiki. I’ve already migrated most of the content from my old website, but there is still some to go. The address for my old RSS feed still works, however, Google Reader seems to be ordering the entries non-chronologically and I am not sure why.

I’m currently teaching a class and receive all of the homework submissions digitally (in the form of PDFs). Printing out the submissions seems like a waste, so I devised a workflow for efficiently grading the assignments digitally by annotating the PDFs. My method relies solely on free, open-source tools.

Here’s the general process:

1. Import the PDF into GIMP. GIMP will automatically create one layer of the image for each page of the PDF.
2. Add an additional transparent layer on top of each page layer.
3. Use the transparent layer to make grading annotations on the underlying page. One can progress through the pages simply by hiding the upper layers.
4. Save the image as an XCF (i.e., GIMP format) file.
5. Use my gimplayers2pngs script (see below) to export the layers of the XCF file into independent PNG image files.
6. Use the composite function of ImageMagick to overlay the annotation layers with the underlying page layers, converting to an output PDF.

Below is the code for my xcflayers2pngs script. It is a Scheme Script-Fu script embedded in a Bash script that exports each layer of the XCF to a PNG file.

#!/bin/bash
{
cat < i 0)
        (set! bottom-to-top (append bottom-to-top (cons (aref all-layers (- i 1)) '())))
        (set! i (- i 1))
        )
      (reverse bottom-to-top)
      )
    )

(define (format-number base-string n min-length)
  (let* (
	 (s (string-append base-string (number->string n)))
	 )
    (if (< (string-length s) min-length)
	(format-number (string-append base-string "0") n min-length)
	s)))

(define (get-full-name outfile i)
  (string-append outfile (format-number "" i 4) ".png")
  )

(define (save-layers image layers outfile layer)
  (let* (
	 (name (get-full-name outfile layer))
	 )
    (file-png-save RUN-NONINTERACTIVE image (car layers) name name 0 9 1 1 1 1 1)
    (if (> (length layers) 1)
	(save-layers image (cdr layers) outfile (+ layer 1)))
    ))

(define (convert-xcf-to-png filename outfile)
  (let* (
	 (image (car (gimp-file-load RUN-NONINTERACTIVE filename filename)))
	 (layers (get-all-layers image))
	 )
    (save-layers image layers outfile 0)
    (gimp-image-delete image)
    )
  )

(gimp-message-set-handler 1) ; Send all of the messages to STDOUT
EOF

echo "(convert-xcf-to-png \"$1\" \"$2\")"

echo "(gimp-quit 0)"
} | gimp -i -b -

Running xcflayers2pngs file.xcf output will create output0000.png, output0001.png, output0002.png, ..., one for each layer of file.xcf. Each even-numbered PNG file will correspond to an annotation layer, while each odd PNG file will correspond to a page of the submission. We can then zip the even pages with their associated odd pages using the following ImageMagick trickery:

convert output???[13579].png null: output???[02468].png -layers composite output.pdf

We can automate this process by creating a Makefile rule to convert a graded assignment in the form of an XCF into a PDF:

%.pdf : %.xcf
        rm -f $**.png
        ./xcflayers2pngs $< $*
        convert $*???[13579].png null: $*???[02468].png -layers composite $@
        rm -f $**.png

There is a lot that has happened since last August. I successfully defended my Ph.D., for one. I could give a report on our post-defense trip to Spain. I could talk about some interesting work I'm now doing. Instead, I'm going to devote this blog entry to gender inequity.

This all started in November of last year in response to one of Dave's blog posts. Long-story-short, he was blogging about a girl he had met; in an effort to conceal her identity (lest she discover the blog entry about herself), he replaced her name with its MD5 hash. Curious, I decided to brute force the hash to retrieve her actual name. This was very simple in Perl:

#!/usr/bin/perl -w
use Digest::MD5 qw(md5_hex);
my $s = $ARGV[0] or die("Usage: crackname MD5SUM\n\n");
system("wget http://www.census.gov/genealogy/names/dist.female.first") unless(-e 'dist.female.first');
open(NAMES, 'dist.female.first') or die("Error opening dist.female.first for reading!\n");
while() {
   if($_ =~ m/^\s*(\w+)/) {
       my $name = lc($1);
       if(md5_hex(ucfirst($name)) eq $s || md5_hex($name) eq $s ||
md5_hex(ucfirst($name) . "\n") eq $s || md5_hex($name . "\n") eq $s) {
           print ucfirst($name) . "\n";
           exit(0);
       }
   }
}
close(NAMES);
exit(1);

Note that I am using a file called dist.female.first, which is freely available from the US Census Bureau. This file contains the most common female first names in the United States, sorted by popularity, according to the most recent census.

This script was able to crack Dave's MD5 hash in about 10 milliseconds.

This got me thinking: For what else could this census data be used?

My first idea was also inspired by Dave. You see, he was writing a novel at the time. Wouldn't it be great if I could create a tool to automatically generate plausible character names for stories?

#!/usr/bin/perl -w
use Cwd 'abs_path';
use File::Basename;
my($scriptfile, $scriptdir) = fileparse(abs_path($0));
my $prob;
$prob = $ARGV[0] or $prob = rand();
system("cd $scriptdir ; wget http://www.census.gov/genealogy/names/dist.all.last") unless(-e $scriptdir . 'dist.all.last');
system("cd $scriptdir ; wget http://www.census.gov/genealogy/names/dist.male.first") unless(-e $scriptdir . 'dist.male.first');
system("cd $scriptdir ; wget http://www.census.gov/genealogy/names/dist.female.first") unless(-e $scriptdir . 'dist.female.first');
sub get_rand {
    my($filename, $percent) = @_;

    open(NAMES, $filename) or die("Error opening $filename for reading!\n");
    $percent *= 100.0;
    my $nameval = -1;
    my @names;
    my $lastname;
    while() {
        if($_ =~ m/^\s*(\w+)\s+([^\s]+)\s+([^\s]+)/) {
            $lastname = ucfirst(lc($1));
            if($3 >= $percent) {
                last if($nameval >= $percent && $3 > $nameval);
                $nameval = $3;
                push(@names, $lastname);
            }
        }
    }
    close(NAMES);
    return $lastname if($#names < 0);
    return $names[int(rand($#names + 1))];
}
sub random_name {
    my($male, $p) = @_;
    my $firstnameprob;
    my $lastnameprob;
    do {
        $firstnameprob = rand($p);
        $lastnameprob = $p - $firstnameprob;
    } while($lastnameprob > 1.0);
    return &get_rand($male ? 'dist.male.first' : 'dist.female.first', $firstnameprob) . " " . &get_rand('dist.all.last', $lastnameprob);
}
sub flushall {
    my $old_fh = select(STDERR);
    $| = 1;
    select(STDOUT);
    $| = 1;
    select($old_fh);
}
print STDERR "Male: ";
&flushall();
print &random_name(1, $prob) . "\t";
&flushall();
print STDERR "\nFemale: ";
&flushall();
print &random_name(0, $prob) . "\n";

This script does just that. Given a real number between 0 and 1 representing the scarcity of the name, this script randomly generates a name according to the distribution of names in the United States according to the census. Values closer to zero produce more common names, and values closer to one produce more rare names. The parameter can be thought of as the scarcity percentile of the name; a value of $x$ means that the name is less common than $x$% of the other names. Note, though, that I'm not actually calculating the joint probability distribution between first and last names (for efficiency reasons), so the value you input doesn't necessarily correlate to the probability that a given first/last name combination occurs in the US population.

$ ./randomname 0.0000001
Male: James Smith
Female: Mary Smith
$ ./randomname 0.5
Male: Robert Shepard
Female: Shannon Jones
$ ./randomname 0.99999
Male: Kendall Narvaiz
Female: Roxanne Lambetr

The "Male" and "Female" portions are actually printed to STDERR. This allows you to use this in scripting without having to parse the output:

$ ./randomname 0.75 2>/dev/null
Gerald Castillo Christine Aaron

But I didn't stop there. Here's the punchline of this Shandy-esque recount:
Inspired by Randall Munroe style Google result frequency charts, I became interested in seeing how the frequency of names in the US correlates to the frequency of names on the Internet. I therefore quickly patched my script to retrieve Google search query result counts using the Google Search API. I generated 60 random names (half male, half female) for increasing scarcity values (in increments of 0.01). The results are pretty surprising:

Note that the $y$-axis is on a logarithmic scale.

As expected, the number of Google search results is exponentially correlated to the scarcity of the name. What is unexpected is the disparity between representation of male names on the Internet versus female names on the Internet. On average, a male name of a certain scarcity will have over 6.6 times more Google results than a female name of equal scarcity!

I have a problem. I admit it. I have a problem deleting files. In the “good times”—vi&., when I have gigabytes to spare on my hard drive—I simply don’t bother deleting temporary files. That video I encoded/compressed to MPEG? Sure, I’ll keep the raw original! Why not? Just in case I ever need to re-encode it at a higher bitrate, you see.

Inevitably, I run low on disk space months later, at which point I’ve forgotten where all of those pesky large files are living.

Enter my script, which I simply call biggest. This script will conveniently print the $n$ biggest files that are rooted at a given directory. Here’s an example:

It is available on GitHub, here:

Through my many years of coding, I have come to this realization:

The so-called "Ballmer Peak", as it is currently understood, is but a two dimensional projection of what in reality is a higher dimensional space, vi&.,

If you've been keeping up, you know that I was attending the Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS) last week in Toronto, Canada. The conference went really well, as did the two workshops I also attended:

1. The Third International Workshop on Optimisation in Multi-Agent Systems (OptMAS); and
2. The Twelfth International Workshop on Distributed Constraint Reasoning (DCR), which Rob and I co-chaired.

I presented my paper on distributedly solving art gallery and dominating set problems on Thursday. AAMAS also allows for full papers to additionally present a poster for the work. This was my first time making a poster purely in LaTeX, and it was a very smooth experience. I created a poster template for the Drexel CS department which can be downloaded here. You can view and download the presentation slides and poster for my paper here.