Agent Graphs/Networks

[ptheywood]

#1089 will add support for host-device accessible graph data structures, which can be constructed from the host, then iterated from the device. Edge/Vertex attributes can be mutated from the host, but the graph structure itself cannot (i.e. no new vertices or edges)

This supports the messages-on-network-edges (and vertices) approach fundamental for road network simulation performance.

However, the graphs are intended to be static - once created the structure cannot be modified from the host nor the device. This is not useful for other types of model (i.e. social networks or even more complex road network simulations).

There are two forms of mutability for graphs we should consider:

1. Mutable graphs for messages-on-network (Mutable graphs/networks for on-graph communication #1120)
2. Mutable graphs for relationships between agents (Agent Graphs/Networks #1121)

This issue is for Option 2: Mutable graphs for releationships between agents.

---

@todo - The following is not final / needs some refining / expansion / updating as #1089 changes

---

The alternative form of networks/graphs which would be useful for some models is for networks to be formed between agents, i.e. social networks.

In this case, agents are the vertex, and edges are the relationships between individuals.

As a real example, modelling by the CASCADE group (Robin Pursehouse, Charlotte Buckley, Joao Duro, et al) use a graph (within repast) to form the relationships between potential drinking buddies.

It has been mentioned previously that agents can store lists of others whom they consider friends, however this does not support part of the CASCADE models. E.g. Agents are more likely to become friends with one another (create an edge) if they have friends in common.

This could be done with bucket message lists, multiple agent functions and a lot of iteration, but would be a dense representation with fixed upper limits (agent array sizes) so would consume a lot of memory, and a lot of code written by the modeller to achieve this.

Instead, having a device-mutable graph data structure would allow the modeller to just call graph iteration methods to find the same data, which would be more efficient and user friendly.

For comparisons to other agent-agent networks in ABMs:

The Repast HPC tutorial shows how network connectisona re made in repast hpc. Repast4py provides a similar api, which wraps NetworkX graphs.

---

As we're doing this on the device, adding new vertices or edges is going to look something like messaging, where agents can output they wish to create a new edge/vertex with data written to a separate area of memory, which on completion of the agent function is post-processed and the graph is mutated.

For the social network case, if we were to limit this to be a graph made up of vertices where each vertex is an agent of the same type, and vertices do not have properties (although it might be useful, to avoid direct agent memory access being required), then the vertex IDs are just Agent IDs.

On agent birth, the new IDs are added to the graph's data.
On agent death, agents which have been removed would also need to be removed from teh graph, and a rebuild triggered. Edges which refer would also need removing.

This would need to be a sparse representation, as otherwise models which have a lot of birth and death would eventually become very wasteful.

---

Related:

#1037