Although more of a rhetorical device than an actual mathematical law, Godwin's Law remains a fascinating anomaly and seems to be relevant to the US election. Naturally, we will decide to explore the idea further using the graph theory. The first step is to broadcast our model back to the executors and parallelize our list of words. For each word, we output the top five synonyms and build an Edge object with word similarity as edge weight. Let's take a look:

val bModel = sc.broadcast(model)
val bDictionary = sc.broadcast(
  model.getVectors
    .keys
    .toList
    .zipWithIndex
    .map(l => (l._1, l._2.toLong + 1L))
    .toMap
)
 
import org.apache.spark.graphx._

val wordRDD = sc.parallelize(
  model.getVectors
    .keys
    .toSeq
    .filter(s => s.length > 3)
)

val word2EdgeRDD = wordRDD.mapPartitions { it =>
  val model = bModel.value
  val dictionary = bDictionary.value
  
  it.flatMap { from =>
    val synonyms = model.findSynonyms(from, 5)
    val tot = synonyms.map(_._2).sum
    synonyms.map { case (to, sim) =>
      val norm = sim / tot
      Edge(
           dictionary.get(from).get,
           dictionary.get(to).get,
           norm
         )
      }
   }
}

val word2Graph = Graph.fromEdges(word2EdgeRDD, 0L)

word2Graph.cache()
word2Graph.vertices.count()

To prove Godwin's law, we will have to prove that no matter the input node, we can always find a path from that node to the Godwin point. In mathematical terms, this assumes the graph to be ergodic. With more than one connected component, our graph cannot be ergodic as some nodes will never lead to the Godwin point. Therefore:

val cc = word2Graph
  .connectedComponents()
  .vertices
  .values
  .distinct
  .count

println(s"Do we still have faith in humanity? ${cc > 1L}")
// false

As we only have one connected component, the next step is to compute the shortest path for each node to that Godwin point:

import org.apache.spark.graphx.lib.ShortestPaths

val shortestPaths = ShortestPaths.run(graph, Seq(godwin))

The shortest path algorithm is quite simple and can be easily implemented with Pregel using the same techniques described in Chapter 7, Building Communities. The basic approach is to start Pregel on the target node (our Godwin point) and send a message back to its incoming edges, incrementing a counter at each hop. Each node will always keep the smallest possible counter and propagate this value downstream to its incoming edges. The algorithm stops when no further edge is found.

We normalize this distance using a Godwin depth of 16, calculated as the maximum of each of the shortest paths:

val depth = sc.broadcast(
  shortestPaths.vertices
    .values
    .filter(_.nonEmpty)
    .map(_.values.min)
    .max()
)

logInfo(s"Godwin depth is [${depth.value}]")
// 16
 
shortestPaths.vertices.map { case (vid, hops) =>
  if(hops.nonEmpty) {
    val godwin = Option(
      math.min(hops.values.min / depth.value.toDouble, 1.0)
    )
    (vid, godwin)
   } else {
     (vid, None: Option[Double])
   }
}
.filter(_._2.isDefined)
.map { case (vid, distance) =>
  (vid, distance.get)
}
.collectAsMap()

The following figure shows a depth of 4 - we normalize the scores of 0, 1, 2, 3, and 4 to 0.0, 0.25, 0.5, 0.75, and 1.0 respectively:

Figure 10: The normalized Godwin distance

Finally, we collect each vertex with its associated distance as a map. We can easily sort this collection from the most to the least-sensitive word, but we will not report our findings here (for obvious reasons!).

On November 7 and 8, 2016, this map contained all the words from our Twitter dictionary, implying a full ergodicity. According to Godwin's Law, any word, given enough time, can lead to the Godwin point. We will use this map later in the chapter when we build features from Twitter text content.

One way to simulate random walks through the Word2Vec algorithm is to treat the graph as a series of Markov chains. Assuming N random walks and a transition matrix T, we compute the transition matrix T^N. Given a state, S₁ (meaning a word w₁), we extract the probability distribution to jump from S₁ to an S_N state in N given transitions. In practice, given a dictionary of ~100k words, a dense representation of such a transition matrix will require around 50 GB to fit in memory. We can easily build a sparse representation of T using the IndexedRowMatrix class from MLlib:

val size = sc.broadcast(
  word2Graph
    .vertices
    .count()
    .toInt
)
 
val indexedRowRDD = word2Graph.edges
  .map { case edge =>
    (edge.srcId,(edge.dstId.toInt, edge.attr))
  }
  .groupByKey()
  .map { case (id, it) =>
    new IndexedRow(id, Vectors.sparse(size.value, it.toSeq))
  }
 
val m1 = new IndexedRowMatrix(indexedRowRDD)
val m3 = m1.multiply(m2)

Unfortunately, there is no built-in method in Spark to perform matrix multiplication with sparse support. Therefore, the m2 matrix needs to be dense and must fit in memory. A solution can be to decompose this matrix (using SVD) and play with the symmetric property of the word2vec matrix (if word w₁ is a synonym to w₂, then w₂ is a synonym to w₁) in order to simplify this process. Using simple matrix algebra, one can prove that given a matrix M:

and M symmetric, then

for even and odd value of n respectively. In theory, we only need to compute the multiplication of S that is a diagonal matrix. In practice, this requires lot of effort and is computationally expensive for no real value (all we want is to generate random word association). Instead, we generate random walks using our Word2Vec graph, the Pregel API, and a Monte Carlo simulation. This will generate word associations starting from a seed love. The algorithm stops after 100 iterations or when a path reaches our Godwin point. The detail of this algorithm can be found in our code repository.

Godwin.randomWalks(graph, "love", 100)