Computing distance in the Facebook graph

Is there some nice algorithm for computing the distance between two nodes in a graph, that gracefully fails when they're far apart? I'm asking this prompted by this metafilter question on how to compute the distance between two individuals in the Facebook graph; it seems to me that if someone is at distance 5 versus 6 from me, for example, I don't really care which it is.

Dijkstra's algorithm, for example, runs in time proportional to the number of edges of the graph. (Well, O(E+V log V), but I'm guessing that log V is smaller than E/V.) This is the search algorithm I learned in an algorithms class once. And most algorithms that I've seen -- of course this isn't an area I know a huge amount about -- tend to run in time at least as large as the number of edges of the graph. (Of course this makes sense because one could have to actually look at all the edges of the graph -- such are the pitfalls of worst-case analysis.)

It seems like bidirectional search would work -- if my friends of friends overlap with your friends of friends, then we're at a distance of most 4, for example. (I didn't realize this had a name until just now; it just seems like an obvious idea to me.) But is there some reason I'm overlooking that this wouldn't be practical?

Constrained tourism

Does there exist a Hamiltonian tour of the graph whose vertices are the 48 contiguous United States and whose edges connect states which border each other? More geographically, can you drive through all of the lower 48 states passing through each exactly once? (From 360.)

Here's one possible solution, although I ignored the constraint implicit in the story that provoked the question, which required a start in Michigan. Note that you have to start or end the tour in Maine since it only borders one other state.

Eulerian beer

At mathlog: Jever Bierdeckel-Mathematik und die Brücken von Kaliningrad. That is, "Jever coaster mathematics and the bridges of Konigsberg." (Why this funny translation? Because you haven't heard of the bridges of Kaliningrad, even though that's what the city is called now.)

It includes a solution to the general problem of identifying graphs with Eulerian tours. In English, in the form of a poem.

And what do coasters have to do with this? Jever is a beer, and the problem of finding an Eulerian tour is on a coaster they distribute (in German).

Edit, 1:28 pm: In the comments, Wing says that he thought the post would be about Euler beer. Apparently there is a beer named Euler. Someone's auctioning off a coaster on ebay.

The five bridges of Kaliningrad

In 1736 Euler solved the following problem: the city of Königsberg is set on both sides of the Pregel river and on two islands between them. There are bridges connecting the various landmasses; is it possible to walk around the city in such a way that you cross each bridge exactly once? The answer is no; (the network of landmasses and bridges in) Königsberg didn't have an Eulerian path. In order to have an Eulerian path the graph corresponding to this network must have zero or two nodes of odd degree; that is, if we consider the number of bridges on each landmass, exactly zero or two of these numbers can be odd. In Königsberg all four degrees were odd.

But the bridges were bombed in World War II, the city was renamed Kaliningrad, and only five of them were rebuilt. These are bridges connecting each of the islands to each of the shores, and a brige connecting the two islands. As you can see, there are three bridges on each island and two on each shore of the river; two of these numbers are odd, so there exists an Eulerian path. It's still somewhat useless, because you have to start on one island and end on the other.

Here's a map of the route, from Microsiervos (in Spanish), and here are some pictures that some folks took when they were visiting Kaliningrad and actually doing this.

I also remember once seeing the analogous network for New York City (the relevant landmasses being Manhattan, Long Island, Staten Island, the Bronx, and New Jersey), which has a lot of bridges, with the question of whether that network had an Eulerian path. I don't remember the answer. I also think it wouldn't be as much fun; New York has lots of traffic and is much larger than Kaliningrad.

A political minimum spanning tree

This morning, Nate Silver of fivethirtyeight.com posted State Similarity Scores. For each pair of states, Silver reports a score that gives the political "distance" between the two states. (He actually reports only the three states closest to each state.)

These are based on an analysis of certain variables that appear to be important in US politics, weighted by their importance in determining state-by-state polling in the 2004 and 2008 presidential elections. As it turns out, the pair of states that are closest to each other in this metric are the Carolinas, followed by the Dakotas; Kentucky-Tennessee; Michigan-Ohio and Oregon-Washington.

It occurred to me that the minimum-weight spanning tree for this data might look interesting. And indeed it does. I'm having some trouble articulating why it's interesting, but I just wanted to post the tree. There may be a slight issue because I don't have the full set of similarity scores, but the tree generated from the subset of the data that I do have is probably pretty close to the "true" tree and is quite interesting to look at. (The weight for the edge between any two states is 100 minus Silver's similarity score for that pair of states; Silver's similarity scores have a theoretical maximum of 100.)

Note that the positioning of the states in the drawing of the tree below is entirely irrelevant; I just attempted to draw the tree in such a way that people wouldn't be inclined to see edges that weren't actually there. In particular, Ohio is not somehow "unusual" even though the edges connecting it to adjacent states are long. (As a start, though, it does seem to be useful to think of Ohio as the center of the graph, in line with the conventional political wisdom that Ohio is at the political center of the US.) I thought about trying to make the distances in the drawing reflect the weights, but that was more trouble than I wanted to go to.

Also, some states that are close to each other in Silver's metric aren't close in the tree. There may be errors, since I did this by hand.

Here's the tree.

Nineteen proofs of Euler's formula

Nineteen proofs of Euler's Formula, from The Geometry Junkyard. (This is the one that says that if V, E, and F are the number of vertices, edges, and faces of a polyhedron, then V-E+F=2.)

This is something of an embarrassment of riches; I want one for my class tomorrow, because we're talking about regular polyhedra, and to talk about that without mentioning Euler's formula would be remiss.

I'll probably give "Proof #8: Sum of angles" from the page, which sums up the various angles involved in a drawing of the graph corresponding to a polyhedron, or the proof that Wikipedia attributes to Cauchy, which triangulates that graph (not changing V-E+F) and then removes edges one or two at a time (still not changing V-E+F). These seem the most accessible. (They're also the ones I managed to struggle in the general direction of while walking to the coffee house a couple hours ago.)

If I wanted to scare the hell out of my students (this class has no prerequisites), I'd give the "binary homology" proof.

A couple articles from the Princeton Companion to Mathematics

Differential forms and integration (10 pp.), from the forthcoming Princeton Companion to Mathematics. (From Terence Tao, who has also written other articles for the PCM. I think it would have been rather nice to receive such an article at the outset of the class in which I learned about this stuff, as it would have helped to give some context; although one can often get context from a textbook, it's difficult to do so because all the little explanatory bits are often mingled with the details. The PCM articles I've seen do not suffer from this flaw; indeed, one might describe a lot of them as what the preface of a textbook covering the same material should be.

In a less theoretical, and less general, vein, here's Frank Kelly's The Mathematics of Traffic in Networks, also from the PCM, which I learned about from a post from Tao last week. One thing this mentions is the paradox that under certain conditions, adding roads to a road network can make trips slower, even though each driver tries to minimize their own time spent on the road. (Fortunately, my life is arranged so that I walk almost everywhere; thus at the moment I only appreciate the weirdness of traffic on a theoretical level. But I know it won't always be like that.) I'd be interested to see if this paradox occurs in actual road networks or only in the contrived example that Kelly gives.

The PCM will sell for about $100, so I probably won't buy it when it comes out. But I suspect I will spend some time browsing it when our library gets it.

West's glossary and open problems in graph theory and combinatorics

Douglas West has a list of open problems in graph theory and combinatorics and a glossary of terms in combinatorics which may be of interest. The open problems are keyed to the four volumes of his The Art of Combinatorics, which is a series of four advanced graduate textbooks/reference books, on "Extremal Graph Theory", "Structure of Graphs", "Order and Optimization", and "Arrangements and Methods"; each is intended to be (I think) a semester or so worth of material. The series is in preparation; the title is, of course, a nod to Knuth. I can't vouch for the books being any good, because I haven't seen them.

There seem to be a lot of lists of open problems scattered about the Internet. Has anyone compiled a list of lists of open problems?

(I found the glossary while Googling for information about hook length of partitions; it didn't help for that, because I already know what hook length is.)

Three posts in one!

1. Literary style by the numbers. Apparently it's reasonably possible to distinguish among authors by just plotting the "average words per sentence" and the "number of complex words"; authors appear to be remarkably consistent on both these measures when looking at book-length samples of text. I wonder if this holds true for mathematical authors; it would be hard to measure for work that includes a lot of mathematical notation.

2. Graph Theory with Applications, J. A. Bondy and U. S. R. Murty (1976) -- out of print for a while, full text online. (Scanned, so it takes a while to load; you can also download it a chapter at a time.) From Anarchaia. (The same authors just finished a graduate text, to be published by Springer; read a blurb about it. I like the sound of the blurb. The book apparently also has a blog but the blog is empty.) Incidentally, I find it interesting that Springer's taxonomy of subdisciplines of mathematics includes "Number Theory and Combinatorics"; usually number theory seems to be classed with algebra.

Despite being an undergraduate book, the book includes a list of unsolved problems, which I think is a good practice; even if the intended reader is not expected to be able to solve these problems, it gives the interested student an idea of the sort of things that real mathematicians are interested in. (Of course, in some fields it wouldn't be practical to put such a list in a textbook; it needs to be possible for students to understand the statements of the problems.)

3. A combinatorial proof of the Rogers-Ramanujan and Schur identities, by Cilanne Boulet and Igor Pak. I haven't read it. (I came across it while looking for some other stuff on partitions.) The Rogers-Ramanujan identity is that the number of partitions of an integer n into parts that are congruent to 1 or 4 modulo 5 is equal to the number of partitions of n such that adjacent parts differ by at least 2.

For example, partitions of 12 counted by the first description are
11 + 1, 9 + 1 + 1 + 1, 6 + 6, 6 + 4 + 1 + 1, 6 + 1 + 1 + 1 + 1 + 1 + 1, 4 + 4 + 4, 4 + 4 + 1 + 1 + 1 + 1, 4 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
and by the second description,
11 + 1, 10 + 2, 9 + 3, 8 + 4, 8 + 3 + 1, 7 + 5, 7 + 4 + 1, 6 + 4 + 2
and there are eight in each list.

However, don't ask me which ones match up with which ones in the bijection! It's by no means obvious. This paper grabbed my interest because I knew there was no "nice" bijective proof, and the title led me to expect such a nice bijection. The authors lament:

Also, while our proof is mostly combinatorial it is by no means a direct bijection. The quest for a direct bijective proof is still under way, and as recently as this year Zeilberger lamented on the lack of such proof. The results in [23] seem to discourage any further work in this direction.

([23] is an in-preparation work of Pak, "Rogers-Ramanujan bijections are not geometric."; I'm kind of curious to see what it says.)

A heuristic look at the crossing number inequality

Terence Tao gives a (well-known) proof of the crossing number inequality. This inequality states that for a graph of average degree at least eight,

cr(G) ≥ E³/(64V²)

where V is the number of vertices of G, E is the number of edges of G, and cr(G) is the so-called "crossing number" -- the minimum number of crossings of edges in a drawing of the graph. (As is usual in the "probabilistic method", a fairly simple proof gets the same form as the best known proof but with weaker constants; a paper of Pach, Radiocic, Rados, Tardos, and Gabor¹ improves the constant to 31.08. (From a quick skim through the paper, it doesn't look too interesting, being mostly a bunch of messy computations.)

Why should the crossing number inequality have these exponents? Say that we expect a lower bound for cr(G) of the form cE^αV^β. (We have this, with c = 1/64, α = 3, β = -2.)

Say we replace G with two copies of G. Then we double its number of edges, its number of vertices, and its number of crossings. Our proposed lower bound now becomes c(2E)^α(2V)β, and we'd like this to equal twice the old bound. So we have

cE^αV^β = c(2E)^α(2V)β

and canceling what will cancel, we get α + β = 1. (Of course, this is all technically wrong, because I've been adding inequalities like they're equalities.) So if we can guess what either α or β will be, we win! (What do we win? A cup of bad coffee. Please go to any mathematics department to claim your prize.)

So now let's say we double the number of edges in a graph; we want to know why this should multiply the number of crossings by 2³ = 8. This seems not so promising. Imagine two graphs on the same vertex set, G and G', which we've smushed together to make a new graph. There is some number of crossings among edges of G, and some number among edges of G'; we want the total nubmer of crossings on this new graph to be eight times the number on either of the original graphs. So the number of crossings involving an edge of G and an edge of G' must be six times the crossing number of G or G'; this might be true but seems hopeless. (Throwing three graphs on top of each other only makes it worse; now we need twenty-seven times as many crossings on G + G' + G'' as we would on any of the three summands, and so we'll have to get eight times cr(G) crossings from each pair of summands. It only gets worse with more summands.

Okay... here's another idea. Hold V constant. Then the inequality says that the crossing number is at least proportional to the cube of the number of edges. This is strange, as it seems to imply somehow that a crossing is going to involve three edges. But now think about how many potential crossings there are in a graph with E edges. These are just pairs of edges, so there are about E²/2 of them. So the inequality is just saying that the probability of two edges crossing in a graph is proportional to the total number of edges!

But what makes things cross? Well, edges that are long are more likely to cross than edges that are short. (It's like how you find yourself maneuvering around fat people on the sidewalk, but not skinny people.) In particular, if we have two curves of length l¹ and l², their probability of crossing -- assuming they move around "randomly" -- will be proportional to the product of their lengths. But how long are the edges in a drawing of a graph? In order to minimize crossings, we probably want edges which are connected to be near each other. And the vertices are probably "evenly spaced" in the plane; say each one has an area of order 1 that is closer to it than to any other vertex. Let d = 2E/V be the average degree of our graph; then the optimal drawing of a graph should have the edges connected to any given vertex v within a circle of area ~d around that vertex... or a circle of radius ~d^1/2. Thus edge length is proportional to the square root of the average degree... and the probability of two edges crossing is proportional to the square of average edge length. So the probability of two edges crossing is proportional to average degree, which if we're holding V constant is proportional to the number of edges.

Just like we wanted.

Of course, there are a lot of places where this argument doesn't make sense; in particular I feel a bit wrong about my argument for the probability of random curves crossing being proportional to the product of their lengths. But it's still how I will understand why this result is true.

(There is a way to reinterpret the crossing number inequality, if for some reason that V in the denominator bothers you, as it did me at first We can interpret it in terms of the average degree d of a graph G, which is just 2E/V. Then we have

cr(G) ≥ Ed²/256

and this form seems clearer to me. Crossing number increases linearly with number of edges, which makes perfect sense -- if you take two disjoint copies of a graph, they each have the same number of crossings, so the total number of crossings should be twice what you started with. And it increases with the square of the average degree. None of this silly stuff with the number of vertices in the denominator. The problem with this, as I discovered, is that the average degree depends on the number of edges...)

1. Pach, János; Radoi\v ci\'c, Rado\v s; Tardos, Gábor; Tóth, Géza Improving the crossing lemma by finding more crossings in sparse graphs. Discrete Comput. Geom. 36 (2006), no. 4, 527--552. Available from Tardos' web site at http://www.renyi.hu/~tardos/crossinglemma.ps.

some links, primarily about the "social graph"

Brad Fitzgerald, formerly of livejournal, gives his Thoughts on the Social Graph. The social graph is, roughly, the graph whose vertices are individuals and whose edges connect pairs of people who know each other (for some definition of "know"); Fitzgerald advocates making the social graph a "community asset" that would be available to anyone who wanted it.

I see the term "social graph" is a bit misleading because it suggests that there is only one type of edge, i. e. one kind of way in which one can know other people. (Indeed, this is a perennial problem on a lot of social networking sites; there's often no way to indicate the difference between, say, a person that one met once at a party and one's spouse.) Fitzgerald acknowledges this:

It's recognized that users don't always want to auto-sync their social networks. People use different sites in different ways, and a "friend" on one site has a very different meaning of a "friend" on another. The goal is to just provide sites and users the raw data, and they can use it to implement whatever policies they want.

The next step in the analysis of social networks might be to take into account the "strength" of relationships, as currently most social networking sites I know of don't acknowledge that I am more interested in some of my friends than others. Also, to what extent can the strength of relationships be guessed just from looking at the social graph without this strength information? A person who I know quite well is likely to be someone with whom I have many friends in common.

Also, the social graph is in some important ways directed (the link goes to Good Math, Bad Math); for example, if edges connect X to Y if X reads Y's LiveJournal. (It wouldn't surprise me to learn that Fitzgerald has this example in mind.) The somewhat addictive tool LJ Connect, which finds the shortest path between two individuals with LiveJournals via their friends, explicitly acknowledges this.

Finally, some shadowy figures seem to be aggregating the mathematics blogging community, and various other blogging communities as well. Their in-house mathematician gives yet another example of using the formula 1+2+...+n = n(n+1)/2.

And some links:

Paul Graham writes about Holding a program in one's head; a lot of his ideas seem to have obvious analogues to mathematical research, which isn't surprising, as programming and mathematics are quite similar. I'll probably have more to say about this later.

There is a graphical formalism for quantum mechanics, which its authors call "kindergarten quantum mechanics"; this is said to be a very considerable extension of Dirac's notation, and gives short derivations of deep results concerning teleportation, quantum mechanics, and so on. If this is true (I'm not familiar enough with the results concerned to say), it's a good example of what Graham has to say about choosing appropriate notation.

Vlorbik asks us to please lie more carefully. He writes:

We were supposed to test the claim that a certain population proportion was 10% against a sample proportion of 13%, based on n= 57 data points (at some stated confidence level that I’ve forgotten). But wait a minute. You can’t get 13% from a sample of 57 subjects: 7/57 ~ .122807 (i.e., 12%) and 8/57 ~ .14035 (i.e., 14%).

This particular one isn't a big problem, but it's symptomatic of something more general -- that the "applications" problems in a lot of mathematics textbooks bear very little resemblance to reality, which only seems to frustrate the students. (Another complaint I have about such textbooks is that the calculus texts seem to assume the student is familiar with physics, which is often not a reasonable assumption to make, and so the instructor ends up teaching physics instead of calculus.)

In Nature's Casino, by Michael Lewis, from the New York Times, August 26, about the insurance market for catastrophic events.