Graph Computation

What is Graph Computation?

A graph is an abstract data type meant to represent a collection of vertices or nodes that have connections between them often referred to as edges or links. This abstraction allows for computation of certain graph problems that may would be familiar with such as a breath or depth based search.

The Simudyne SDK maps it's agent and the connecting network of agents directly onto this graph data type. We do this because we want to create models that accurately represent people, companies, objects, etc. Many scientists agree that this is an accurate way of abstracting the real-world -- representing 'things existing' and 'things interacting with one another'.

While some might argue that representing agents as a graph isn't a novel idea in agent-based modelling, Simudyne's approach introduces the method for computing against this graph in a different manner than traditional ABM modelling tools. Most tools would represent a graph only as a resulting data set for ease in viewing and understanding agents in your model - whereas Simudyne makes usage of the graph as the method for handling it's computations. This is an important difference.

A short example to understand this would be to picture a city street. On it are different types of agents (people, buses, taxis, cars, trucks, birds, etc) these agents can be represented in multiple methods as a graph or a series of nodes existing in a space (let's assume physical). Rather than simply looping through everything and rigourously updating a singular world state like traditional ABMs, Simudyne's representation allows agents to make their own assumptions and observations of the world and through communciation with other agents within the world. Each agent has connections to other agents - this could be line of sight, hearing, etc or possibly other relations such as a man walking who's uncle is nearby in a taxi. When an agent does something it reaches out to it's connections of varying types so as to inform them of some change (I am walking forward - do I see if about to bump into someone?)

Therefore, rather than treating everything in the world in a massive list to iterate through and update a world state, we approach the problem from a bottom-up representation of the world where each agent can communicate via message passing between agents to create a world state that will inform their decisions. This also has precedent in the graph computation world as this more decentralized approach allows for different technologies that have been created to solve this type of problem.

What is Pregel?

Pregel is a framework designed for processing large-scale graphs. For more: http://www.dcs.bbk.ac.uk/~dell/teaching/cc/paper/sigmod10/p135-malewicz.pdf

"The high-level organization of Pregel programs is inspired by Valiant’s Bulk Synchronous Parallel model. Pregel computations consist of a sequence of iterations, called supersteps. During a superstep the framework invokes a user-defined function for each vertex, conceptually in parallel. The function specifies behavior at a single vertex V and a single superstep S. It can read messages sent to V in superstep S − 1, send messages to other vertices that will be received at superstep S + 1, and modify the state of V and its outgoing edges. Messages are typically sent along outgoing edges, but a message may be sent to any vertex whose identifier is known."

In short it is a way of taking the problem of processing a massive graph, chunking it to different cores, and then being able to process these supersteps in parallel. Simudyne makes usage of this approach behind the scenes in it's libraries so that when a developers creates something in the platform there is no need for them to change or rewrite code in order to work from a small testing laptop to a cluster of 100's of machines. As long as you configure your simulation with some easy to use settings, you can shift from development to large scale production with ease.

Simudyne's SDK makes usage of graph computation and a Pregel style approach for handling it's communications between agents for a few main reasons.

• The graph data structure is more analagous to real world ABMs
• Computing a large graph is a solved problem in distributed computation
• Usage of this approach allows users to scale their solutions without needing to redo their code