Networks and network types#
Reticula support static and temporal networks involving two (dyadic) or more (hypergraph) vertices in each event. The events can have an inherent directionality and possibly a time delay.
It is also built with extensibility in mind. Adding a custom network type is, in theory, as easy as introducing a new edge class in C++ that satisfies certain concepts and defines certain type traits.
In this section, we will discuss the properties of the different edge and network types.
General properties of networks#
All network types are immutable. This means that all functions operating or seemingly “modifying” networks actually return a modified copy of the input networks.
The network and edge types in python are based on statically typed C++ classes.
This imposes restrictions on the type of vertices or timestamps a network can
store. In C++, this is indicated by template instantiation, e.g., the class
undirected_network<std::int64_t>
indicates an undirected static
network with 64bit signed integer vertices. The Python API, which by necessity
has to carry the same information, simulates this in a form similar to the
existing type annotation syntax: undirected_network[int64]
.
Temporal networks also need to know about the time type that they should store.
For example undirected_temporal_network[int64, double]
marks a continuous time undirected temporal network with integer vertices.
If the type syntax looks verbose, remember that you can, and probably should, assign a humanreadable name to repeatedlyused types in your code. This way you can avoid repeating yourself without compromising on type safety:
import reticula as ret
network_type = ret.undirected_network[ret.int64]
edge_type = network_type.edge_type()
e1 = edge_type(1, 2)
e2 = edge_type(3, 4)
g1 = network_type(edges=[e1, e2], verts=[1, 2, 3, 4, 5])
Note
It’s probably a good idea to use more meaningful and specific
names than edge_type
and network_type
. For example, a study on
scientific citation temporal networks can use citation_event
for
temporal edges and citation_network
for the network type.
Construction#
Networks can be initialised empty, by a list of edges, or by a list of edges and vertices. In addition to explicitly stating a list of edge objects, you can use tuples that implicitly convert to the correct edge type:
import reticula as ret
g1 = ret.undirected_network[ret.int64]() # an empty network
g2 = ret.undirected_network[ret.int64](edges=[(1, 2), (2, 3)])
g3 = ret.undirected_network[ret.int64](
edges=[(1, 2), (2, 3)], verts=[1, 2, 3, 4, 5, 6])
This mimics the C++ brace initialisation syntax:
undirected_network<std::int64_t> g1; // an empty network
undirected_network<std::int64_t> g2({{1, 2}, {2, 3}});
undirected_network<std::int64_t> g3(
{{1, 2}, {2, 3}},
{1, 2, 3, 4, 5, 6});
The list of vertices is not required, but providing it can inform the network that a vertex of with that name exists, even if there are not edges connected to it.
Note
The Python binding implicit conversion from tuples to edge types is currently sensetive to mixing different numeric types, e.g., if it is expecting a 2tuple of double and you pass a 2tuple of integers, it cannot perform an implicit conversion. It is however okay to use a list instead of a tuple and vice versa.
Edges and vertices#
Edges and vertices are accessible through member functions of the same name.
g3.edges() # list of two edges
g3.vertices() # list six vertices
You can also get the network edges sorted by operator<
(operator.__lt__
in Python) or effect_lt()
(effect_lt()
) through functions edges_cause
and
edges_effect
member functions. In a temporal network the result of the
former will be sorted by cause time and the latter by effect time of the events.
In static networks they return the same output.
Incident edges#
Edges incident to a vertex can be accessed using the incident_edges
methods. For directed network types, methods out_edges
and in_edges
distinguish between inward and outward edges, while indicent_edges
does
not.
g3.incident_edges(3) # => [undirected_edge[int64](2, 3)]
g3.out_edges(3) # => same as above, as the network is undirected
g3.in_edges(3) # => same as above, as the network is undirected
Successors, predecessors and neighbours#
The set of neighbours of a vertex in the network can be achieved using the
method neighbours
. Methods successors
and predecessors
provide
directed network equivalents.
g3.neighbours(2) # => [3, 1]
g3.successors(2) # => same as above, as the network is undirected
g3.predecessors(2) # => same as above, as the network is undirected
Vertex degree#
There are multiple ways of defining the degrees for vertices depending on the type of network at hand. All network types have the following degree types defined:
Indegree referes to the number of edges where the vertex is a member of their outincident set of vertices, i.e., the cardinality of the set of edges that are incoming to that vertex.
Outdegree referes to the number of edges where the vertex is a member of their inincident set of vertices, i.e., the cardinality of the set of edges that are outgoing from that vertex.
Incidentdegree referes to the number of edges where the vertex is a member of their incident set of vertices, i.e., the set of edges that are incoming to or outgoing from that vertex. This should be the sum of in and outdegree of that vertex.
For undirected networks, degree of a vertex referes to the incidentdegree of that vertex. For directed networks, the word degree on its own is vaguelydefined and should be avoided.
ret.degree(g3, 2) # => 2
ret.incident_degree(g3, 2) # => same as above, as the network is undirected
ret.out_degree(g3, 2) # => same as above, as the network is undirected
ret.in_degree(g3, 2) # => same as above, as the network is undirected
See vertex degree algorithms for more information on these and other relevant functions.
Network types#

template<network_edge EdgeT>
class network<EdgeT>#
Undirected static networks#

template<network_vertex VertT>
class undirected_network<VertT>#
 class undirected_network[vertex_type]#
Directed static networks#

template<network_vertex VertT>
class directed_network<VertT>#
 class directed_network[vertex_type]#
Undirected static hypernetworks#

template<network_vertex VertT>
class undirected_hypernetwork<VertT>#
 class undirected_hypernetwork[vertex_type]#
Directed static hypernetworks#

template<network_vertex VertT>
class directed_hypernetwork<VertT>#
 class directed_hypernetwork[vertex_type]#
Undirected temporal networks#

template<network_vertex VertT, typename TimeT>
class undirected_temporal_network<VertT, TimeT>#
 class undirected_temporal_network[vertex_type, time_type]#
Directed temporal networks#

template<network_vertex VertT, typename TimeT>
class directed_temporal_network<VertT, TimeT>#
 class directed_temporal_network[vertex_type, time_type]#
Directed delayed temporal networks#

template<network_vertex VertT, typename TimeT>
class directed_delayed_temporal_network<VertT, TimeT>#
 class directed_delayed_temporal_network[vertex_type, time_type]#
Undirected temporal hypernetworks#

template<network_vertex VertT, typename TimeT>
class undirected_temporal_hypernetwork<VertT, TimeT>#
 class undirected_temporal_hypernetwork[vertex_type, time_type]#
Directed temporal hypernetworks#

template<network_vertex VertT, typename TimeT>
class directed_temporal_hypernetwork<VertT, TimeT>#
 class directed_temporal_hypernetwork[vertex_type, time_type]#
Directed delayed temporal hypernetworks#

template<network_vertex VertT, typename TimeT>
class directed_delayed_temporal_hypernetwork<VertT, TimeT>#
 class directed_delayed_temporal_hypernetwork[vertex_type, time_type]#
Vertex types#
Simple types#
The only requirement for a valid vertex type in C++ is to satisfy
network_vertex
. This means that the numeric types,
std::string
, std::pair
, std::tuple
and all standard library
ordered containers are accepted. On the other hand the python implementation
requires a predefined list of types at compile time, meaning that we have to
make a choice as to what vertex types would be available. At the moment certain
fundamental types are defined
 class int64#
Corresponding to
std::int64_t
64bit signed integers.
 class string#
Corresponding to
std::string
.
 class pair[type1, type2]#
Corresponding to
std::pair<Type1, Type2>
.
Higherorder networks#
In addition to the vertex types listed above, the Python binding supports one level of higherorder network, where vertices of the network can be any of the defined edge types as long as that edge type uses one of the above “simple” vertex types. The C++ library supports any level of higherorder networks.
Time Types#
In C++ it is possible to use any arithmetic type for timestamps. In the Python
binding, in addition to the previously mentioned int64
integer type
you can use one of the following predefined types:
 class double#
Corresponding to
double
double precision floatingpoint type, almost always an implementation of the IEEE754 binary64 format.
Concepts#
Vertices#

template<typename T>
concept network_vertex# Any type that is totally ordered (satisfies
std::totally_ordered<T>
) and hashable with the structhash
can be a network vertex.

template<typename T>
concept integer_network_vertex# A
network_vertex
that is also an arithmetic integer type, i.e., traitstd::numeric_limits<T>::is_integer
should have a true value for that type.
Edges#

template<typename T>
concept network_edge# Any type can be a network edge if it is totally ordered (satisfies
std::totally_ordered<T>
), hashable with bothstd::hash
andhash
, defines aVertexType
member type and certain function members:mutated_verts()
,mutator_verts()
,is_incident(VertexType v)
,is_in_incident(VertexType v)
andis_out_incident(VertexType v)
.The type must also provide specialisations for
effect_lt()
andadjacent()
.

template<typename T>
concept directed_network_edge# A
network_edge
that might have distinct in and outincident sets of vertices.

template<typename T>
concept undirected_network_edge# A
network_edge
that cannot have distinct in and outincident sets of vertices, i.e., in and outincident vertices are always equal.

template<typename T>
concept temporal_network_edge# A
network_edge
that carries time information, by defining member typesTimeType
which should be an arithmatic type andStaticProjectionType
which should be astatic_edge
and member functionscause_time()
,effect_time()
andstatic_projection()
.

template<typename T>
concept directed_temporal_network_edge# A
temporal_network_edge
that is also adirected_network_edge
.

template<typename T>
concept undirected_temporal_network_edge# A
temporal_network_edge
that is also aundirected_network_edge
.

template<typename T>
concept static_network_edge# A
network_edge
that does not carry time information by not defining member functioneffect_time()
.

template<typename T>
concept directed_static_network_edge# A
static_network_edge
that is also adirected_network_edge
.

template<typename T>
concept undirected_static_network_edge# A
static_network_edge
that is also aundirected_network_edge
.
Degree/weight ranges#

template<typename T>
concept degree_range# A range (i.e., satisfies
std::ranges::range
) with integer values.

template<typename T>
concept degree_pair_range# A range (i.e., satisfies
std::ranges::range
) with pairs of integers as values, representing in and outdegree of each vertex.

template<typename T>
concept weight_range# A range (i.e., satisfies
std::ranges::range
) with arithmetic values.

template<typename T>
concept weight_pair_range# A range (i.e., satisfies
std::ranges::range
) with pairs of arithmetic values, Corresponding to in and outdegree weigts for each vertex.