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 64-bit 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 human-readable name to repeatedly-used 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 2-tuple of double and you pass a 2-tuple 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#

The degree of each vertex can be calculated using the method degree, in_degree and out_degree. For hypergraphs and hypergraph temporal networks, the degree refers to the number of unique edges, as opposed to the number of neighbours.

g3.degree(2) # => 2
g3.out_degree(2) # => same as above, as the network is undirected
g3.in_degree(2) # => same as above, as the network is undirected

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 hyper-networks#

template<network_vertex VertT>
class undirected_hypernetwork<VertT>#
class undirected_hypernetwork[vertex_type]#

Directed static hyper-networks#

template<network_vertex VertT>
class directed_hypernetwork<VertT>#
class directed_hypernetwork[vertex_type]#

Directed 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 hyper-networks#

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

Directed temporal hyper-networks#

template<network_vertex VertT, typename TimeT>
class directed_temporal_hypernetwork<VertT, TimeT>#
class directed_temporal_hypernetwork[vertex_type, time_type]#

Directed delayed temporal hyper-networks#

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 64-bit signed integers.

class string#

Corresponding to std::string.

class pair[type1, type2]#

Corresponding to std::pair<Type1, Type2>.

Higher-order networks#

In addition to the vertex types listed above, the Python binding supports one level of higher-order 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 higher-order 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 pre-defined types:

class double#

Corresponding to double double precision floating-point type, almost always an implementation of the IEEE-754 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 struct hash can be a network vertex.

template<typename T>
concept integer_vertex#

A network_vertex that is also an arithmetic integer type, i.e., trait std::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 both std::hash and hash, defines a VertexType member type and certain function members: mutated_verts(), mutator_verts(), is_incident(VertexType v), is_in_incident(VertexType v) and is_out_incident(VertexType v).

The type must also provide specialisations for effect_lt() and adjacent().

template<typename T>
concept temporal_edge#

A network_edge that carries time information, by defining member types TimeType which should be an arithmatic type and StaticProjectionType which should be a static_edge and member functions cause_time(), effect_time() and static_projection().

template<typename T>
concept static_edge#

A network_edge that does not carry time information by not defining member function effect_time().

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 out-degree 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 out-degree weigts for each vertex.