Game of Phones: Modeling Diffusion of Innovations With Neo4j

When we’re deciding whether to adopt a new technology or adopt a new pattern of behavior, it often makes sense to consider how many people in our networks are also using the new technology. When deciding whether or not my next phone should be an iPhone or Android device, I evaluate the pros and cons of the alternative operating system for my personal use. However, I also consider the benefit of using video chat and messaging apps that align with family members’ choices. There’s a benefit to having a similar device when called upon to give tech support at the family discount.

via Wikimedia Commons Rawpixel.com CC0

In chapter 19 of their book Networks, Crowds, and Markets, David Easley and Jon Kleinberg discuss the way that innovations spread across networks. They cite research describing how farmers decide to adopt new seed corn hybrids and the way that doctors decide to prescribe new therapies. The research shows that simply knowing about an innovation isn’t enough to prompt most people to adopt it. We take the plunge when we see that some proportion of the associates in our network are adopting the new technology.

As I reflect on my response to COVID-19, I recognize the influence of the people in my network. When I see people wearing masks at the grocery store, I feel more confident in my decision to wear one. If nobody in my network was wearing a mask, I would feel self-conscious about doing so myself despite the advice of from experts outside my personal circle.

Easley and Kleinberg present a simple model of diffusion through a network. It’s a version of a multi-player coordination game. In each round of the game, players can play either choice A or choice B. If they play A, they receive a reward of amount a for each neighbor who also plays A. If they play B, they receive a reward of amount b for each neighbor who also plays B. The players choose to play A or B based on which option will give them the maximum total payoff.

At the start of the game, most players are playing the incumbent choice B. We select a few early adopters to play the innovative choice A. Depending on the network structure and the size of rewards a and b, the A strategy may or may not diffuse through the network over time until all players have adopted strategy A.

We can simulate this game in a Neo4j sandbox. To follow along with the code below, sign in to the sandbox and select “New Project.” Choose “Graph Data Science” from the starter projects offered.

This sandbox comes loaded with a data set based on Game of Thrones, so let’s imagine that a new cell phone carrier has been introduced in Westeros. Which characters will be influenced to adopt the innovative technology?

Because the model we’re looking at explores diffusion from neighbor to neighbor, we need a connected graph. We can use the Graph Data Science library to find the largest connected component in the Game of Thrones graph. First, we load a graph holding the :INTERACTS relationships among our Person nodes.

//create interactions graph
CALL gds.graph.create('got-interactions', 'Person', {
  INTERACTS: {
    orientation: 'UNDIRECTED'
  }
})

Next, we find the weakly connected components, and write a property called interacts_wcc_partition back to the graph. (The graph already has a property called wcc_partition, but it is based on interactions within a culture. Run :play https://guides.neo4j.com/sandbox/graph-data-science for details on the wcc_partition property.)

//Calculate weakly connected components
CALL gds.wcc.write('got-interactions', 
     {writeProperty:"interacts_wcc_partition"})

Add an Interactor label to the people in the largest connected component.

//Add Interactor label
MATCH (p:Person)
WITH p.interacts_wcc_partition AS partition, 
     COLLECT(p) AS people, COUNT(p) AS personCount
     ORDER BY personCount DESC
LIMIT 1
UNWIND people AS person
SET person:Interactor
RETURN COUNT(*)

You should now have 795 people with an Interactors label.

Let’s set parameters designating the payoff for matching neighbors with A or B. For the first run of the simulation, matching A is worth 2 and matching B is worth 1.

:params {aReward:2, bReward:1}

Next, we’ll assign the B strategy to all of the players. This was the standard strategy before the A began to infiltrate the graph.

//Set everyone to B and remove A if it exists
MATCH (p:Interactor) 
SET p:B 
REMOVE p:A

Now we choose a couple of early adopters to play strategy A. I have to admit that I never watched the series or read the books, but Drogo and Doreah seem like good names to me.

//Set A inital adoptors
MATCH (p:Interactor)
WHERE p.name IN ["Drogo", "Doreah"]
REMOVE p:B
SET p:A
RETURN p

Now we find people who are playing B who have an A neighbor. We check to see if their payoff for switching to A is greater than sticking with B. If so, we switch them to the A strategy.

//switch B to A where total payoff is greater
MATCH (p:B)-[:INTERACTS]-(a:A)
WITH p
MATCH (p)-[:INTERACTS]-(n)
WITH DISTINCT p, n
WITH p, SUM(CASE WHEN "A" in labels(n) 
                 THEN $aReward 
            END) AS aRewardSum, 
        SUM(CASE WHEN "B" in labels(n) 
                 THEN $bReward 
                 END) AS bRewardSum
     WHERE aRewardSum >= bRewardSum
REMOVE p:B
SET p:A
RETURN p

You will see a handful of neighbors to our early adopters who have switched to playing A. Rerun the query multiple times and you can see the A strategy diffusing through the network. After a few iterations, no new neighbors are switching to A.

I used Neo4j Bloom to visualize how far the innovation made it into the network. From the blue nodes of Drogo and Doreah in the center, the innovation only traveled to a few other players who didn’t have very many connections in the network to influence them to stick with B.

Visualization of A (blue node) penetration

Easly and Kleinberg prove that the innovation stalls out before reaching all members of the network if and only if there is a densely connected cluster of nodes in the network. The density of the cluster required to block the diffusion of the innovation depends on the payoffs a and b that players get for matching A and B. If each node in the cluster has a fraction of at least b/(a+b) neighbors in the cluster, the innovation cannot penetrate the cluster.

With their diffusion stalled, the marketing team for team A has few options. One would be to improve their product so that the payoff for matching A relative to B increases. This will increase the density of a cluster required to block the diffusion. We can do that with this code.

:params {aReward:5, bReward:1}

Another option would be to persuade a few members of the dense clusters to switch from B to A and let the innovation cascade further from there.

Try changing the parameters as suggested above and rerun the code to switch players from B to A. If you prefer not to repeatedly rerun the same query to see the diffusion one step at a time, you can use the apoc.periodic.commit function to run the query iteratively until no new players are switched.

//Switch all B to A
CALL apoc.periodic.commit(
'MATCH (p:B)-[:INTERACTS]-(a:A)
WITH DISTINCT p
LIMIT 1000
MATCH (p)-[:INTERACTS]-(n)
WITH DISTINCT p, n
WITH p, SUM(CASE WHEN "A" in labels(n) 
                 THEN $aReward 
            END) AS aRewardSum, 
        SUM(CASE WHEN "B" in labels(n) 
                 THEN $bReward 
            END) AS bRewardSum
     WHERE aRewardSum >= bRewardSum
REMOVE p:B
SET p:A
RETURN count(*)', {aReward:$aReward, bReward:$bReward})

Run this query to see how many holdouts are still playing the B strategy.

MATCH (b:B) 
RETURN COUNT(b)

This model of network diffusion is a close cousin to the label propagation algorithm in the Graph Data Science library. The key difference is that in label propagation algorithm, weights are applied to the relationships between nodes. In the model discussed here, weights are applied based on the two node labels.

Easley and Kleinberg extend this model in several interesting ways in the rest of the chapter. I hope the code examples in this post will pique your curiosity to read further. The concepts might help you think about the ways our choices impact those closest to us.