Here’s a graph of master / apprentice relationships for Jedi and Sith in the Star Wars movies. It’s not exhaustive, but it covers the main relationships in Episodes I through VI.

Here’s what you get if you add a dashed arrow for who killed whom.

Here’s the dot (GraphVis) code that created the diagrams.

digraph G {

    Vader [label="Anakin Skywalker/\nDarth Vader"];
    Dooku [label="Dooku/\nDarth Tyranus"];
    Luke  [label="Luke Skywalker"];
    Ben   [label="Obi-Wan Kenobi"];
    Liam  [label="Qui-Gon Jinn"];
    DS    [label="Palpatine/\nDarth Sidious"]
    DP    [label="Darth Plagueis"];
    DM    [label="Darth Maul"];

    Yoda  -> Dooku;
    Yoda  -> Luke;
    Dooku -> Liam;
    Liam  -> Ben;
    Liam  -> Vader;
    Ben   -> Vader;
    Ben   -> Luke;
    DS    -> Dooku;
    DS    -> Vader;
    DP    -> DS;
    DS    -> DM;
    
    Vader -> DS [style=dashed];
    Vader -> Dooku [style=dashed];
    Vader -> Ben [style=dashed];
    Ben   -> DM [style=dashed];    
    DM    -> Liam [style=dashed];
    DS    -> DP [style=dashed];
}

More network visualization posts

• Hand-drawn GraphViz diagrams
• Rook graphs and Paley graphs

An m by n rook graph is formed by associating a node with each square of an m by n chess board and connecting two nodes with an edge if a rook can legally move from one to the other. That is, two nodes are connected if they are either in the same row or in the same column.

A Paley graph of order q is a graph with q nodes where q is a prime power and congruent to 1 mod 4. Label each node with an element of the finite field F with q elements and connect two nodes with an edge if the difference between their labels is a quadratic residue. That is, for nodes labeled a and b, connect these nodes if there exist an x in F such that a – b = x².

We’ll look at a graph which is both a rook graph and a Paley graph: the 3 by 3 rook graph is the same as the Paley graph of order 9.

Rook graph 3 x 3

Constructing the rook graph is easy. If we number our 3 by 3 chess board as follows

    1 2 3
    4 5 6
    7 8 9

then we connect 1 to 2, 3, 4, and 7. We connect 2 to 1, 3, 5, and 8. Etc. This gives us the following graph.

(The graph was made with Sketchviz introduced here.)

Paley graph of order 9

They Paley graph is a little more complicated to construct. First we need to explain what a field with 9 elements is.

A field with 3 elements is just integers mod 3. We can think of the field with 9 elements as the analog of complex numbers: numbers of the form a + bi where a and b are integers mod 3. As with the complex numbers, i² = -1.

When we square each of the nine elements of our field, we get four distinct non-zero results: 1, 2, i, and 2i. For example, i is one of our squares because

(1 + 2i)(1 + 2i) = (1 – 4) + 4i = i

Here we used -3 = 0 mod 3 and 4 = 1 mod 3.

Since our squares are 1, 2, i, and 2i, that says 0 is connected to these four values. Then we connect 1 to 2, 0, 1 + i and 1 + 2i because each of these numbers minus 1 is a square. If we keep doing this for all nine nodes, we get the following graph.

Isomorphism

It’s clear that the two graphs above are relabelings of each other. We can see this explicitly by relabeling our chess board as follows:

    0    i    2i
    1  1+i  1+2i
    2  2+i  2+2i

Moving horizontally adds i, which is a square, and moving vertically adds 1, which is a square. So the Paley connections are rook connections.

Uniqueness

Are there more rook graphs that are isomorphic to Paley graphs? No, this is the only one.

Every pair of vertices in a rook graph that are not neighbors have two common. If the points with coordinates (a, b) and (c, d) are on different rows and columns, then both are connected to (a, d) and (c, b).

In a Paley graph of order q, every pair of nodes that aren’t neighbors have (q – 1)/4 common neighbors. For a Paley graph to be isomorphic to a rook graph, we must have (q – 1)/4 = 2, and so q = 9.

More on graphs

• Rook polynomials
• A knight tour magic square
• Random walk on an expander graph

I just discovered the website Six Degrees of Wikipedia. It lets you enter two topics and it will show you how few hops it can take to get from one to the other.

Since the mathematical equivalent of Six Degrees of Kevin Bacon is Six degrees of Paul Erdős, I tried looking for the distance between Kevin Bacon and Paul Erdős and found this:

Kevin Bacon and Paul Erdős are both known for their prolific collaborations. Many actors have acted with Kevin Bacon, or acted with actors who have acted with him, etc. Many mathematicians wrote papers with Erdős, or have written papers with people who have written papers with him, etc. I’m four degrees of separation from Paul Erdős last I checked.  [1]

Here’s a more complex graph showing the three degrees of separation between Thomas Aquinas and Thomas the Tank Engine.

Note that the edges are directed, links from the starting page to pages that lead to the target page. If you reverse the starting and ending page, you get different results. For example, there are still three degrees of separation if we reverse our last example, going from Thomas the Tank Engine to Thomas Aquinas, but there are about twice as many possible paths.

More network posts

• Six degrees of Paul Erdős
• Spectral graph theory
• Complex networks

[1] Your Erdős number, the degrees of separation between your and Paul Erdős, can decrease over time because his collaborators are still writing papers. Even Erdős himself continued to publish posthumously because people who began papers with him finished them years later.

The latest episode of My Favorite theorem features John Urschel, former offensive lineman for the Baltimore Ravens and current math graduate student. His favorite theorem is a result on graph approximation: for every weighted graph, no matter how densely connected, it is possible to find a sparse graph whose Laplacian approximates that of the original graph. For details see Spectral Sparsification of Graphs by Dan Spielman and Shang-Hua Teng.

You could view this theorem as a positive result—it’s possible to find good sparse approximations—or a negative result—the Laplacian doesn’t capture very well how densely a graph is connected.

Related: Blog posts based on my interview with Dan Spielman at the 2014 Heidelberg Laureate Forum.

• Uses for orthogonal polynomials
• What is smoothed analysis?
• Studying algorithms to study problems

There are a couple ways to measure how well a graph remains connected when nodes are removed. One ways is to consider nodes dropping out randomly. Another way, the one we look at here, assumes an adversary is trying to remove the most well-connected nodes. This approach was defined by Schneider et al [1]. It is also described, a little more clearly, in [2].

The robustness of a graph is defined as

Then [2] explains that

N is the total number of nodes in the initial network and S(q) is the relative size of the largest connected component after removing q nodes with the highest degrees. The normalization factor 1/N ensures 1/N ≤ R ≤ 0.5. Two special cases exist: R = 1/N corresponds to star-like networks while R = 0.5 represents the case of the fully connected network.

Apparently “relative size” means relative to the size of the original network, not to the network with q nodes removed.

There is one difference between [1] and [2]. The former defines the sum up to N and the latter to N-1. But this doesn’t matter because S(N) = 0: when you remove N nodes from a graph with N nodes, there’s nothing left!

I have a couple reservations. One is that it’s not clear whether R is well defined.

Consider the phrase “removing q nodes with the highest degrees.” What if you have a choice of nodes with the highest degree? Maybe all nodes have degree no more than n and several have degree exactly n. It seems your choice of node to remove matters. Removing one node of degree n may give you a very different network than removing another node of the same degree.

Along the same lines, it’s not clear whether it matters how one removes more than one degree. For S(2), for example, does it matter whether I remove the two most connected nodes from the original graph at once, or remove the most connected node first, then the most connected node from what remains?

My second reservation is that I don’t think the formula above gives exactly the extreme values it says. Start with a star graph. Once you remove the center node, there are only isolated points left, and each point is 1/N of the original graph. So all the S(q) are equal to 1/N. Then R equals (N – 1)/ N², which is less than 1/N.

With the complete graph, removing a point leaves a complete graph of lower order. So S(q) = (N – q)/N. Then R equals (N – 1)/2N, which is less than 1/2.

***

[1] CM Schneider et al, Mitigation of malicious attacks on networks. P. Natl. Acad. March 8, 2011, vol. 108. no. 10

[2] Big Data of Complex Networks, CRC Press. Matthias Dehmer et al editors.