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.

Note

Unlike most Python classes and methods, Reticula type annotations are more often than not mandatory. This stems from the fact that, e.g., a undirected_network[int64] object is an instance of an inherently different C++ class compared to a undirected_network[string], with possibly different underlying memory layout.

For many of the methods we have elected to use an automatic dispatch method based on argument types whenever possible, similar to how C++ handles function overloading based on parameters. In a few cases, this has proved trickey.

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¶

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:

In-degree referes to the number of edges where the vertex is a member of their out-incident set of vertices, i.e., the cardinality of the set of edges that are incoming to that vertex.
Out-degree referes to the number of edges where the vertex is a member of their in-incident set of vertices, i.e., the cardinality of the set of edges that are outgoing from that vertex.
Incident-degree 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 out-degree of that vertex.

For undirected networks, degree of a vertex referes to the incident-degree of that vertex. For directed networks, the word degree on its own is vaguely-defined 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.

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. This includes an integral type, a string type and pairs of these types.

class int64¶: Corresponding to std::int64_t 64-bit signed integers.

class string¶: Corresponding to std::string.

type simple_vertex_type = int64 | string¶

class pair[type1, type2]¶: Corresponding to std::pair<Type1, Type2>.

type vertex_type = simple_vertex_type | pair[simple_vertex_type, simple_vertex_type] | first_order_edges¶

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.

type time_type = int64 | double¶

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]¶

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 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]¶

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_network_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 directed_network_edge¶: A network_edge that might have distinct in- and out-incident sets of vertices.

template<typename T> concept undirected_network_edge¶: A network_edge that cannot have distinct in- and out-incident sets of vertices, i.e., in- and out-incident vertices are always equal.

template<typename T> concept temporal_network_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 directed_temporal_network_edge¶: A temporal_network_edge that is also a directed_network_edge.

template<typename T> concept undirected_temporal_network_edge¶: A temporal_network_edge that is also a undirected_network_edge.

template<typename T> concept static_network_edge¶: A network_edge that does not carry time information by not defining member function effect_time().

template<typename T> concept directed_static_network_edge¶: A static_network_edge that is also a directed_network_edge.

template<typename T> concept undirected_static_network_edge¶: A static_network_edge that is also a undirected_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 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.