Motifs#

raphtory.algorithms.global_temporal_three_node_motif(g, delta)#

Computes the number of three edge, up-to-three node delta-temporal motifs in the graph, using the algorithm of Paranjape et al, Motifs in Temporal Networks (2017). We point the reader to this reference for more information on the algorithm and background, but provide a short summary below.

Motifs included:

Stars

There are three classes (in the order they are outputted) of star motif on three nodes based on the switching behaviour of the edges between the two leaf nodes.

  • PRE: Stars of the form i<->j, i<->j, i<->k (ie two interactions with leaf j followed by one with leaf k)

  • MID: Stars of the form i<->j, i<->k, i<->j (ie switching interactions from leaf j to leaf k, back to j again)

  • POST: Stars of the form i<->j, i<->k, i<->k (ie one interaction with leaf j followed by two with leaf k)

Within each of these classes is 8 motifs depending on the direction of the first to the last edge – incoming “I” or outgoing “O”. These are enumerated in the order III, IIO, IOI, IOO, OII, OIO, OOI, OOO (like binary with “I”-0 and “O”-1).

Two node motifs:

Also included are two node motifs, of which there are 8 when counted from the perspective of each node. These are characterised by the direction of each edge, enumerated in the above order. Note that for the global graph counts, each motif is counted in both directions (a single III motif for one node is an OOO motif for the other node).

Triangles:

There are 8 triangle motifs:

  1. i –> j, k –> j, i –> k

  2. i –> j, k –> i, j –> k

  3. i –> j, j –> k, i –> k

  4. i –> j, i –> k, j –> k

  5. i –> j, k –> j, k –> i

  6. i –> j, k –> i, k –> j

  7. i –> j, j –> k, k –> i

  8. i –> j, i –> k, k –> j

Parameters:

  • g (raphtory graph) – A directed raphtory graph

  • delta (int) – Maximum time difference between the first and last edge of the motif. NB if time for edges was given as a UNIX epoch, this should be given in seconds, otherwise milliseconds should be used (if edge times were given as string)

Returns:

A 40 dimensional array with the counts of each motif, given in the same order as described above. Note that the two-node motif counts are symmetrical so it may be more useful just to consider the first four elements.

Return type:

list

Notes

This is achieved by calling the local motif counting algorithm, summing the resulting arrays and dealing with overcounted motifs: the triangles (by dividing each motif count by three) and two-node motifs (dividing by two).

raphtory.algorithms.global_temporal_three_node_motif_multi(g, deltas)#

Computes the global counts of three-edge up-to-three node temporal motifs for a range of timescales. See global_temporal_three_node_motif for an interpretation of each row returned.

Parameters:

  • g (raphtory graph) – A directed raphtory graph

  • deltas (list(int)) – A list of delta values to use.

Returns:

A list of 40d arrays, each array is the motif count for a particular value of delta, returned in the order that the deltas were given as input.

Return type:

list(list(int))

raphtory.algorithms.local_temporal_three_node_motifs(g, delta)#

Computes the number of each type of motif that each node participates in. See global_temporal_three_node_motifs for a summary of the motifs involved.

Parameters:

  • g (raphtory graph) – A directed raphtory graph

  • delta (int) – Maximum time difference between the first and last edge of the motif. NB if time for edges was given as a UNIX epoch, this should be given in seconds, otherwise milliseconds should be used (if edge times were given as string)

Returns:

A dictionary with node ids as keys and a 40d array of motif counts as values (in the same order as the global motif counts) with the number of each motif that node participates in.

Return type:

dict

Notes

For this local count, a node is counted as participating in a motif in the following way. For star motifs, only the centre node counts

the motif. For two node motifs, both constituent nodes count the motif. For triangles, all three constituent nodes count the motif.

raphtory.algorithms.local_triangle_count(g, v)#

Implementations of various graph algorithms that can be run on a graph.

To run an algorithm simply import the module and call the function with the graph as the argument

Local triangle count - calculates the number of triangles (a cycle of length 3) a node participates in.

This function returns the number of pairs of neighbours of a given node which are themselves connected.

Parameters:

  • g (Raphtory graph) – Raphtory graph, this can be directed or undirected but will be treated as undirected

  • v (int or str) – node id or name

Returns:

number of triangles associated with node v

Return type:

triangles(int)

raphtory.algorithms.triplet_count(g)#

Computes the number of connected triplets within a graph

A connected triplet (also known as a wedge, 2-hop path) is a pair of edges with one node in common. For example, the triangle made up of edges A-B, B-C, C-A is formed of three connected triplets.

Parameters:

g (Raphtory graph) – a Raphtory graph, treated as undirected

Returns:

the number of triplets in the graph

Return type:

int