algorithms

Algorithmic functions that can be run on Raphtory graphs

Classes

Class	Description
Infected
Matching	A Matching (i.e., a set of edges that do not share any nodes)

Functions

Function	Description
`all_local_reciprocity`	Local reciprocity - measure of the symmetry of relationships associated with a node
`average_degree`	The average (undirected) degree of all nodes in the graph.
`balance`	Sums the weights of edges in the graph based on the specified direction.
`betweenness_centrality`	Computes the betweenness centrality for nodes in a given graph.
`cohesive_fruchterman_reingold`	Cohesive version of `fruchterman_reingold` that adds virtual edges between isolated nodes
`degree_centrality`	Computes the degree centrality of all nodes in the graph. The values are normalized
`dijkstra_single_source_shortest_paths`	Finds the shortest paths from a single source to multiple targets in a graph.
`directed_graph_density`	Graph density - measures how dense or sparse a graph is.
`fast_rp`	Computes embedding vectors for each vertex of an undirected/bidirectional graph according to the Fast RP algorithm.
`fruchterman_reingold`	Fruchterman Reingold layout algorithm
`global_clustering_coefficient`	Computes the global clustering coefficient of a graph. The global clustering coefficient is
`global_reciprocity`	Reciprocity - measure of the symmetry of relationships in a graph, the global reciprocity of
`global_temporal_three_node_motif`	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).
`global_temporal_three_node_motif_multi`	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.
`hits`	HITS (Hubs and Authority) Algorithm:
`in_component`	In component -- Finding the "in-component" of a node in a directed graph involves identifying all nodes that can be reached following only incoming edges.
`in_components`	In components -- Finding the "in-component" of a node in a directed graph involves identifying all nodes that can be reached following only incoming edges.
`k_core`	Determines which nodes are in the k-core for a given value of k
`label_propagation`	Computes components using a label propagation algorithm
`local_clustering_coefficient`	Local clustering coefficient - measures the degree to which nodes in a graph tend to cluster together.
`local_clustering_coefficient_batch`	Returns the Local clustering coefficient (batch, intersection) for each specified node in a graph. This measures the degree to which one or multiple nodes in a graph tend to cluster together.
`local_temporal_three_node_motifs`	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.
`local_triangle_count`	Implementations of various graph algorithms that can be run on a graph.
`louvain`	Louvain algorithm for community detection
`max_degree`	Returns the largest degree found in the graph
`max_in_degree`	The maximum in degree of any node in the graph.
`max_out_degree`	The maximum out degree of any node in the graph.
`max_weight_matching`	Compute a maximum-weighted matching in the general undirected weighted
`min_degree`	Returns the smallest degree found in the graph
`min_in_degree`	The minimum in degree of any node in the graph.
`min_out_degree`	The minimum out degree of any node in the graph.
`out_component`	Out component -- Finding the "out-component" of a node in a directed graph involves identifying all nodes that can be reached following only outgoing edges.
`out_components`	Out components -- Finding the "out-component" of a node in a directed graph involves identifying all nodes that can be reached following only outgoing edges.
`pagerank`	Pagerank -- pagerank centrality value of the nodes in a graph
`single_source_shortest_path`	Calculates the single source shortest paths from a given source node.
`strongly_connected_components`	Strongly connected components
`temporal_SEIR`	Simulate an SEIR dynamic on the network
`temporal_bipartite_graph_projection`	Projects a temporal bipartite graph into an undirected temporal graph over the pivot node type. Let `G` be a bipartite graph with node types `A` and `B`. Given `delta > 0`, the projection graph `G'` pivoting over type `B` nodes,
`temporally_reachable_nodes`	Temporally reachable nodes -- the nodes that are reachable by a time respecting path followed out from a set of seed nodes at a starting time.
`triplet_count`	Computes the number of connected triplets within a graph
`weakly_connected_components`	Weakly connected components -- partitions the graph into node sets which are mutually reachable by an undirected path

Function Details

all_local_reciprocity

Signature: all_local_reciprocity(graph)

Local reciprocity - measure of the symmetry of relationships associated with a node

This measures the proportion of a node's outgoing edges which are reciprocated with an incoming edge.

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	a directed Raphtory graph

Returns

Type	Description
NodeStateF64	Mapping of nodes to their reciprocity value.

average_degree

Signature: average_degree(graph)

The average (undirected) degree of all nodes in the graph.

Note that this treats the graph as simple and undirected and is equal to twice the number of undirected edges divided by the number of nodes.

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	a Raphtory graph

Returns

Type	Description
float	the average degree of the nodes in the graph

balance

Signature: balance(graph, name='weight', direction='both')

Sums the weights of edges in the graph based on the specified direction.

This function computes the sum of edge weights based on the direction provided, and can be executed in parallel using a given number of threads.

Parameters

Name	Type	Default	Description
`direction`	Direction, optional	`'both'`	Specifies the direction of the edges to be considered for summation. Defaults to "both". * "out": Only consider outgoing edges. * "in": Only consider incoming edges. * "both": Consider both outgoing and incoming edges. This is the default.
`graph`	GraphView	-	The graph view on which the operation is to be performed.
`name`	str, optional	`'weight'`	The name of the edge property used as the weight. Defaults to "weight".

Returns

Type	Description
NodeStateF64	Mapping of nodes to the computed sum of their associated edge weights.

betweenness_centrality

Signature: betweenness_centrality(graph, k=None, normalized=True)

Computes the betweenness centrality for nodes in a given graph.

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	A reference to the graph.
`k`	int, optional	`None`	Specifies the number of nodes to consider for the centrality computation. All nodes are considered by default.
`normalized`	bool, optional	`True`	Indicates whether to normalize the centrality values. Defaults to True.

Returns

Type	Description
NodeStateF64	Mapping from nodes to their betweenness centrality.

cohesive_fruchterman_reingold

Signature: cohesive_fruchterman_reingold(graph, iter_count=100, scale=1.0, node_start_size=1.0, cooloff_factor=0.95, dt=0.1)

Cohesive version of fruchterman_reingold that adds virtual edges between isolated nodes

Parameters

Name	Type	Default	Description
`cooloff_factor`	float, optional	`0.95`	Factor to reduce node movement in later iterations, helping stabilize the layout. Defaults to 0.95.
`dt`	float, optional	`0.1`	Time step or movement factor in each iteration. Defaults to 0.1.
`graph`	GraphView	-	A reference to the graph
`iter_count`	int, optional	`100`	The number of iterations to run. Defaults to 100.
`node_start_size`	float, optional	`1.0`	Initial size or movement range for nodes. Defaults to 1.0.
`scale`	float, optional	`1.0`	Global scaling factor to control the overall spread of the graph. Defaults to 1.0.

Returns

Type	Description
NodeLayout	A mapping from nodes to their [x, y] positions

degree_centrality

Signature: degree_centrality(graph)

Computes the degree centrality of all nodes in the graph. The values are normalized by dividing each result with the maximum possible degree. Graphs with self-loops can have values of centrality greater than 1.

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	The graph view on which the operation is to be performed.

Returns

Type	Description
NodeStateF64	Mapping of nodes to their associated degree centrality.

dijkstra_single_source_shortest_paths

Signature: dijkstra_single_source_shortest_paths(graph, source, targets, direction='both', weight='weight')

Finds the shortest paths from a single source to multiple targets in a graph.

Parameters

Name	Type	Default	Description
`direction`	Direction, optional	`'both'`	The direction of the edges to be considered for the shortest path. Defaults to "both".
`graph`	GraphView	-	The graph to search in.
`source`	NodeInput	-	The source node.
`targets`	list[NodeInput]	-	A list of target nodes.
`weight`	str, optional	`'weight'`	The name of the weight property for the edges. Defaults to "weight".

Returns

Type	Description
NodeStateWeightedSP	Mapping from nodes to a tuple containing the total cost and the nodes representing the shortest path.

directed_graph_density

Signature: directed_graph_density(graph)

Graph density - measures how dense or sparse a graph is.

The ratio of the number of directed edges in the graph to the total number of possible directed edges (given by N * (N-1) where N is the number of nodes).

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	a directed Raphtory graph

Returns

Type	Description
float	Directed graph density of graph.

fast_rp

Signature: fast_rp(graph, embedding_dim, normalization_strength, iter_weights, seed=None, threads=None)

Computes embedding vectors for each vertex of an undirected/bidirectional graph according to the Fast RP algorithm. Original Paper: https://doi.org/10.48550/arXiv.1908.11512

Parameters

Name	Type	Default	Description
`embedding_dim`	int	-	The size (dimension) of the generated embeddings.
`graph`	GraphView	-	The graph view on which embeddings are generated.
`iter_weights`	list[float]	-	The scalar weights to apply to the results of each iteration
`normalization_strength`	float	-	The extent to which high-degree vertices should be discounted (range: 1-0)
`seed`	int, optional	`None`	The seed for initialisation of random vectors
`threads`	int, optional	`None`	The number of threads to be used for parallel execution.

Returns

Type	Description
NodeStateListF64	Mapping from nodes to embedding vectors.

fruchterman_reingold

Signature: fruchterman_reingold(graph, iterations=100, scale=1.0, node_start_size=1.0, cooloff_factor=0.95, dt=0.1)

Fruchterman Reingold layout algorithm

Parameters

Name	Type	Default	Description
`cooloff_factor`	float \| None, optional	`0.95`	the cool off factor for the algorithm. Defaults to 0.95.
`dt`	float \| None, optional	`0.1`	the time increment between iterations. Defaults to 0.1.
`graph`	GraphView	-	the graph view
`iterations`	int \| None, optional	`100`	the number of iterations to run. Defaults to 100.
`node_start_size`	float \| None, optional	`1.0`	the start node size to assign random positions. Defaults to 1.0.
`scale`	float \| None, optional	`1.0`	the scale to apply. Defaults to 1.0.

Returns

Type	Description
NodeLayout	A mapping from nodes to their [x, y] positions

global_clustering_coefficient

Signature: global_clustering_coefficient(graph)

Computes the global clustering coefficient of a graph. The global clustering coefficient is defined as the number of triangles in the graph divided by the number of triplets in the graph.

Note that this is also known as transitivity and is different to the average clustering coefficient.

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	a Raphtory graph, treated as undirected

Returns

Type	Description
float	the global clustering coefficient of the graph

global_reciprocity

Signature: global_reciprocity(graph)

Reciprocity - measure of the symmetry of relationships in a graph, the global reciprocity of the entire graph. This calculates the number of reciprocal connections (edges that go in both directions) in a graph and normalizes it by the total number of directed edges.

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	a directed Raphtory graph

Returns

Type	Description
float	reciprocity of the graph between 0 and 1.

global_temporal_three_node_motif

Signature: global_temporal_three_node_motif(graph, delta, threads=None)

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:

i → j, k → j, i → k
i → j, k → j, k → i
i → j, j → k, i → k
i → j, j → k, k → i
i → j, k → i, j → k
i → j, k → i, k → j
i → j, i → k, j → k
i → j, i → k, k → j

Parameters

Name	Type	Default	Description
`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)
`graph`	GraphView	-	A directed raphtory graph
`threads`	int, optional	`None`	The number of threads to use when running the algorithm.

Returns

Type	Description
list[int]	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.

global_temporal_three_node_motif_multi

Signature: global_temporal_three_node_motif_multi(graph, deltas, threads=None)

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

Name	Type	Default	Description
`deltas`	list[int]	-	A list of delta values to use.
`graph`	GraphView	-	A directed raphtory graph
`threads`	int, optional	`None`	The number of threads to use.

Returns

Type	Description
list[list[int]]	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.

hits

Signature: hits(graph, iter_count=20, threads=None)

HITS (Hubs and Authority) Algorithm:

AuthScore of a node (A) = Sum of HubScore of all nodes pointing at node (A) from previous iteration / Sum of HubScore of all nodes in the current iteration

HubScore of a node (A) = Sum of AuthScore of all nodes pointing away from node (A) from previous iteration / Sum of AuthScore of all nodes in the current iteration

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	Graph to run the algorithm on
`iter_count`	int, optional	`20`	How many iterations to run the algorithm. Defaults to 20.
`threads`	int, optional	`None`	Number of threads to use

Returns

Type	Description
NodeStateHits	A mapping from nodes their hub and authority scores

in_component

Signature: in_component(node, filter=None)

In component -- Finding the "in-component" of a node in a directed graph involves identifying all nodes that can be reached following only incoming edges.

Parameters

Name	Type	Default	Description
`filter`	`filter.FilterExpr`, optional	`None`	Optional filter
`node`	Node	-	The node whose in-component we wish to calculate

Returns

Type	Description
NodeStateUsize	Mapping of nodes in the in-component to the distance from the starting node.

in_components

Signature: in_components(graph, filter=None)

In components -- Finding the "in-component" of a node in a directed graph involves identifying all nodes that can be reached following only incoming edges.

Parameters

Name	Type	Default	Description
`filter`	`filter.FilterExpr`, optional	`None`	Optional filter
`graph`	GraphView	-	Raphtory graph

Returns

Type	Description
NodeStateNodes	Mapping of nodes to the nodes in their 'in-component'

k_core

Signature: k_core(graph, k, iter_count, threads=None)

Determines which nodes are in the k-core for a given value of k

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	A reference to the graph
`iter_count`	int	-	The number of iterations to run
`k`	int	-	Value of k such that the returned nodes have degree > k (recursively)
`threads`	int, optional	`None`	number of threads to run on

Returns

Type	Description
list[Node]	A list of nodes in the k core

label_propagation

Signature: label_propagation(graph, seed=None)

Computes components using a label propagation algorithm

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	A reference to the graph
`seed`	bytes, optional	`None`	Array of 32 bytes of u8 which is set as the rng seed

Returns

Type	Description
list[set]	A list of sets each containing nodes that have been grouped

local_clustering_coefficient

Signature: local_clustering_coefficient(graph, v)

Local clustering coefficient - measures the degree to which nodes in a graph tend to cluster together.

The proportion of pairs of neighbours of a node who are themselves connected.

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	Raphtory graph, can be directed or undirected but will be treated as undirected.
`v`	NodeInput	-	node id or name

Returns

Type	Description
float	the local clustering coefficient of node v in graph.

local_clustering_coefficient_batch

Signature: local_clustering_coefficient_batch(graph, v)

Returns the Local clustering coefficient (batch, intersection) for each specified node in a graph. This measures the degree to which one or multiple nodes in a graph tend to cluster together.

Uses path-counting for its triangle-counting step.

Parameters

Name	Type	Default	Description
`graph`	Any	-
`v`	Any	-

Returns

Type	Description
dict

local_temporal_three_node_motifs

Signature: local_temporal_three_node_motifs(graph, delta, threads=None)

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

Name	Type	Default	Description
`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)
`graph`	GraphView	-	A directed raphtory graph
`threads`	optional	`None`

Returns

Type	Description
NodeStateMotifs	A mapping from nodes to lists of motif counts (40 counts in the same order as the global motif counts) with the number of each motif that node participates in.

local_triangle_count

Signature: local_triangle_count(graph, 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

Name	Type	Default	Description
`graph`	GraphView	-	Raphtory graph, this can be directed or undirected but will be treated as undirected
`v`	NodeInput	-	node id or name

Returns

Type	Description
int	number of triangles associated with node v

louvain

Signature: louvain(graph, resolution=1.0, weight_prop=None, tol=None)

Louvain algorithm for community detection

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	the graph view
`resolution`	float, optional	`1.0`	the resolution parameter for modularity. Defaults to 1.0.
`tol`	None \| float, optional	`None`	the floating point tolerance for deciding if improvements are significant (default: 1e-8)
`weight_prop`	str \| None, optional	`None`	the edge property to use for weights (has to be float)

Returns

Type	Description
NodeStateUsize	Mapping of nodes to their community assignment

max_degree

Signature: max_degree(graph)

Returns the largest degree found in the graph

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	The graph view on which the operation is to be performed.

Returns

Type	Description
int	The largest degree

max_in_degree

Signature: max_in_degree(graph)

The maximum in degree of any node in the graph.

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	a directed Raphtory graph

Returns

Type	Description
int	value of the largest indegree

max_out_degree

Signature: max_out_degree(graph)

The maximum out degree of any node in the graph.

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	a directed Raphtory graph

Returns

Type	Description
int	value of the largest outdegree

max_weight_matching

Signature: max_weight_matching(graph, weight_prop=None, max_cardinality=True, verify_optimum_flag=False)

Compute a maximum-weighted matching in the general undirected weighted graph given by "edges". If max_cardinality is true, only maximum-cardinality matchings are considered as solutions.

The algorithm is based on "Efficient Algorithms for Finding Maximum Matching in Graphs" by Zvi Galil, ACM Computing Surveys, 1986.

Based on networkx implementation https://github.com/networkx/networkx/blob/3351206a3ce5b3a39bb2fc451e93ef545b96c95b/networkx/algorithms/matching.py

With reference to the standalone protoype implementation from: http://jorisvr.nl/article/maximum-matching

http://jorisvr.nl/files/graphmatching/20130407/mwmatching.py

The function takes time O(n**3)

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	The graph to compute the maximum weight matching for
`max_cardinality`	bool, optional	`True`	If set to True, consider only maximum-cardinality matchings. Defaults to True. If True, finds the maximum-cardinality matching with maximum weight among all maximum-cardinality matchings, otherwise, finds the maximum weight matching irrespective of cardinality.
`verify_optimum_flag`	bool, optional	`False`	Whether the optimum should be verified. Defaults to False. If true prior to returning, an additional routine to verify the optimal solution was found will be run after computing the maximum weight matching. If it's true and the found matching is not an optimal solution this function will panic. This option should normally be only set true during testing.
`weight_prop`	str, optional	`None`	The property on the edge to use for the weight. If not provided,

Returns

Type	Description
Matching	The matching

min_degree

Signature: min_degree(graph)

Returns the smallest degree found in the graph

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	The graph view on which the operation is to be performed.

Returns

Type	Description
int	The smallest degree found

min_in_degree

Signature: min_in_degree(graph)

The minimum in degree of any node in the graph.

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	a directed Raphtory graph

Returns

Type	Description
int	value of the smallest indegree

min_out_degree

Signature: min_out_degree(graph)

The minimum out degree of any node in the graph.

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	a directed Raphtory graph

Returns

Type	Description
int	value of the smallest outdegree

out_component

Signature: out_component(node, filter=None)

Out component -- Finding the "out-component" of a node in a directed graph involves identifying all nodes that can be reached following only outgoing edges.

Parameters

Name	Type	Default	Description
`filter`	`filter.FilterExpr`, optional	`None`	Optional filter
`node`	Node	-	The node whose out-component we wish to calculate

Returns

Type	Description
NodeStateUsize	A NodeState mapping the nodes in the out-component to their distance from the starting node.

out_components

Signature: out_components(graph, filter=None)

Out components -- Finding the "out-component" of a node in a directed graph involves identifying all nodes that can be reached following only outgoing edges.

Parameters

Name	Type	Default	Description
`filter`	`filter.FilterExpr`, optional	`None`	Optional filter
`graph`	GraphView	-	Raphtory graph

Returns

Type	Description
NodeStateNodes	Mapping of nodes to the nodes within their 'out-component'

pagerank

Signature: pagerank(graph, iter_count=20, max_diff=None, use_l2_norm=True, damping_factor=0.85)

Pagerank -- pagerank centrality value of the nodes in a graph

This function calculates the Pagerank value of each node in a graph. See https://en.wikipedia.org/wiki/PageRank for more information on PageRank centrality. A default damping factor of 0.85 is used. This is an iterative algorithm which terminates if the sum of the absolute difference in pagerank values between iterations is less than the max diff value given.

Parameters

Name	Type	Default	Description
`damping_factor`	float, optional	`0.85`	The damping factor for the PageRank calculation. Defaults to 0.85.
`graph`	GraphView	-	Raphtory graph
`iter_count`	int, optional	`20`	Maximum number of iterations to run. Note that this will terminate early if convergence is reached. Defaults to 20.
`max_diff`	float, optional	`None`	Optional parameter providing an alternative stopping condition. The algorithm will terminate if the sum of the absolute difference in pagerank values between iterations is less than the max diff value given.
`use_l2_norm`	bool, optional	`True`	Flag for choosing the norm to use for convergence checks, True for l2 norm, False for l1 norm. Defaults to True.

Returns

Type	Description
NodeStateF64	Mapping of nodes to their pagerank value.

single_source_shortest_path

Signature: single_source_shortest_path(graph, source, cutoff=None)

Calculates the single source shortest paths from a given source node.

Parameters

Name	Type	Default	Description
`cutoff`	int, optional	`None`	An optional cutoff level. The algorithm will stop if this level is reached.
`graph`	GraphView	-	A reference to the graph. Must implement `GraphViewOps`.
`source`	NodeInput	-	The source node.

Returns

Type	Description
NodeStateNodes	Mapping from end node to shortest path from the source node.

strongly_connected_components

Signature: strongly_connected_components(graph)

Strongly connected components

Partitions the graph into node sets which are mutually reachable by an directed path

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	Raphtory graph

Returns

Type	Description
NodeStateUsize	Mapping of nodes to their component ids

temporal_SEIR

Signature: temporal_SEIR(graph, seeds, infection_prob, initial_infection, recovery_rate=None, incubation_rate=None, rng_seed=None)

Simulate an SEIR dynamic on the network

The algorithm uses the event-based sampling strategy from https://doi.org/10.1371/journal.pone.0246961

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	the graph view
`incubation_rate`	float \| None, optional	`None`	optional incubation rate (if None, simulates SI or SIR dynamics where infected nodes are infectious at the next time step) the actual incubation time is sampled from an exponential distribution with this rate
`infection_prob`	float	-	the probability for a contact between infected and susceptible nodes to lead to a transmission
`initial_infection`	int \| str \| datetime	-	the time of the initial infection
`recovery_rate`	float \| None, optional	`None`	optional recovery rate (if None, simulates SEI dynamic where nodes never recover) the actual recovery time is sampled from an exponential distribution with this rate
`rng_seed`	int \| None, optional	`None`	optional seed for the random number generator
`seeds`	int \| float \| list[NodeInput]	-	the seeding strategy to use for the initial infection (if `int`, choose fixed number of nodes at random, if `float` infect each node with this probability, if `list` initially infect the specified nodes

Returns

Type	Description
NodeStateSEIR	Mapping from nodes to `Infected` objects for each infected node with attributes `infected`: the time stamp of the infection event `active`: the time stamp at which the node actively starts spreading the infection (i.e., the end of the incubation period) `recovered`: the time stamp at which the node recovered (i.e., stopped spreading the infection)

temporal_bipartite_graph_projection

Signature: temporal_bipartite_graph_projection(graph, delta, pivot_type)

Projects a temporal bipartite graph into an undirected temporal graph over the pivot node type. Let G be a bipartite graph with node types A and B. Given delta > 0, the projection graph G' pivoting over type B nodes, will make a connection between nodes n1 and n2 (of type A) at time (t1 + t2)/2 if they respectively have an edge at time t1, t2 with the same node of type B in G, and |t2-t1| < delta.

Parameters

Name	Type	Default	Description
`delta`	int	-	Time period
`graph`	GraphView	-	A directed raphtory graph
`pivot_type`	str	-	node type to pivot over. If a bipartite graph has types `A` and `B`, and `B` is the pivot type, the new graph will consist of type `A` nodes.

Returns

Type	Description
Graph	Projected (unipartite) temporal graph.

temporally_reachable_nodes

Signature: temporally_reachable_nodes(graph, max_hops, start_time, seed_nodes, stop_nodes=None)

Temporally reachable nodes -- the nodes that are reachable by a time respecting path followed out from a set of seed nodes at a starting time.

This function starts at a set of seed nodes and follows all time respecting paths until either a) a maximum number of hops is reached, b) one of a set of stop nodes is reached, or c) no further time respecting edges exist. A time respecting path is a sequence of nodes v_1, v_2, ... , v_k such that there exists a sequence of edges (v_i, v_i+1, t_i) with t_i < t_i+1 for i = 1, ... , k - 1.

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	directed Raphtory graph
`max_hops`	int	-	maximum number of hops to propagate out
`seed_nodes`	list[NodeInput]	-	list of node names or ids which should be the starting nodes
`start_time`	int	-	time at which to start the path (such that t_1 > start_time for any path starting from these seed nodes)
`stop_nodes`	list[NodeInput], optional	`None`	nodes at which a path shouldn't go any further

Returns

Type	Description
NodeStateReachability	Mapping of nodes to their reachability history.

triplet_count

Signature: triplet_count(graph)

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

Name	Type	Default	Description
`graph`	GraphView	-	a Raphtory graph, treated as undirected

Returns

Type	Description
int	the number of triplets in the graph

weakly_connected_components

Signature: weakly_connected_components(graph)

Weakly connected components -- partitions the graph into node sets which are mutually reachable by an undirected path

This function assigns a component id to each node such that nodes with the same component id are mutually reachable by an undirected path.

Parameters

Name	Type	Default	Description
`graph`	GraphView	-	Raphtory graph

Returns

Type	Description
NodeStateUsize	Mapping of nodes to their component ids.