16  Agent-Based Modeling on Networks

The Model Class

To specify an ABM in Mesa we need to define two classes: a class describing the model and a class describing each individual agent. The main responsibilities of the model class are to describe:

• How the model is initialized, via the __init__() method. This includes:
  • Creating any agents needed.
  • Placing those agents on the grid and placing them in the schedule.
  • Defining any data collection tools.
• What happens in a single time-step of the model, via the step() method.

The model class actually has a lot more functionality than this. Fortunately, we don’t usually need to define this functionality, because the model class we create inherits the needed functionality from mesa.Model (which we imported above). Here’s our SRWModel class. The syntax can look a little complicated whenever we work with a new package, but what’s going on is fundamentally pretty simple. We’ve added annotations next to the most important lines of code; other lines are also necessary for correct functioning but are more boilerplate than informative.

class RWModel(Model):

    # model setup
1    def __init__(self, G, agent_class, **kwargs):
        
        super().__init__()
2        self.grid     = NetworkGrid(G)
        
3        agent = agent_class(self, **kwargs)
        node = self.random.choice(list(G.nodes))                  
4        self.grid.place_agent(agent, node)

5        self.collector = DataCollector(
            agent_reporters = {
                "node" : lambda a: a.pos
            }
        )

6    def step(self):
        self.agents.do("step") 
        self.collector.collect(self)

The Agent Class

Now we’re ready to define what the agent is supposed to do! In the SRW, the agent looks at all nodes adjacent to theirs, chooses one of them uniformly at random, and moves to it. We need to implement this behavior in the step() method. While there are some more mesa functions involved that you may not have seen before, the approach is very simple.

class SRWAgent(Agent):
    def __init__(self, model):
        super().__init__(model)
1        self.unique_id = "Anakin Graphwalker"

    def step(self):

        # find all possible next steps
        # include_center determines whether or not we count the 
        # current position as a possibility
2        options = self.model.grid.get_neighborhood(self.pos,
                                                include_center = False) 

        # pick a random one and go there
        new_node = self.random.choice(options)
3        self.model.grid.move_agent(self, new_node)

Note that, in order to get information about the possible locations, and to move the agent, we needed to use the grid attribute of the SRWModel that we defined above. More generally, the grid handles all “spatial” operations that we usually need to do.

Variation: PageRank

The reason that we parameterized the RWModel class with the argument agent_class is that we can now implement other random walks, like PageRank, just by modifying the agent behavior. Let’s now make a new kind of agent that does the PageRank step. In a PageRank step:

• With probability \(\alpha\), the agent teleports to a random node.
• With probability \(1 - \alpha\), the agent chooses a neighbor instead does a simple random walk step.

class PageRankAgent(Agent):

    def __init__(self, model, alpha):
        super().__init__(model)
        self.alpha = alpha

    def step(self):
1        if np.random.rand() < self.alpha:
            options = list(self.model.grid.G.nodes.keys())
2        else:
            options = self.model.grid.get_neighborhood(self.pos, 
                                                include_center = False)

        # pick a random one and go there
        new_node = np.random.choice(options)
        self.model.grid.move_agent(self, new_node)

That’s all we need to do in order to implement PageRank. Let’s go ahead and run:

pagerank_model = RWModel(G, PageRankAgent, alpha = 0.15)

for i in range(100000):
    pagerank_model.step()

That’s it! Now we could check the match with the stationary distribution like we did last time. Instead, let’s simply draw the graph.

walk_report = pagerank_model.collector.get_agent_vars_dataframe()

counts = walk_report.groupby("node").size()
freqs  = counts / np.sum(counts)

plot_kwargs = {
    "with_labels": True,
    "font_size": 8,
    "edge_color": "gray",
    "edgecolors": "white",
    "width" : 0.3, 
    "node_color": "steelblue",
}

g = nx.draw(G, 
        node_size = [10000*freqs[i] for i in G.nodes], 
        **plot_kwargs)

The simulation-based version of PageRank is actually similar to Google’s original implementation of PageRank: rather than solving a linear system, it was sufficient to simply let a webcrawler randomly follow links (with occasional teleportation) and then simply report how often it visited each website. The theory of random walks guarantees that the results will be close to the theoretical PageRank values provided that the number of steps is sufficiently large.