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 vertex. 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 vertex is an OOO motif for the other vertex).
Triangles:
There are 8 triangle motifs:
i –> j, k –> j, i –> k
i –> j, k –> i, j –> k
i –> j, j –> k, i –> k
i –> j, i –> k, j –> k
i –> j, k –> j, k –> i
i –> j, k –> i, k –> j
i –> j, j –> k, k –> i
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)#
- 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:
An AlgorithmResult with node ids as keys and a 40d array of motif counts (in the same order as the global motif counts) with the number of each motif that node participates in.
- Return type:
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)#
Local triangle count - calculates the number of triangles (a cycle of length 3) a vertex 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) – vertex id or name
- Returns:
number of triangles associated with vertex 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