Graph theory: graph types and edge properties

Networks can represent many different types of data. The nodes represent different entities (e.g. proteins or genes in biological networks), and edges convey information about the links between the nodes. First we will concentrate on the edges. Depending on the nature of underlying edge information, different types of analysis can be performed. For this reason, it is useful to highlight the main types of edges that can be found in a network (Figure 3).

Types of network edges

Undirected edges

This type of edge is found in protein-protein interaction networks (PPINs). The relationship between the nodes is a simple connection, without a given ‘flow’ implied, since the evidence behind the relationship only tells us that A binds B.

Directed edges 

This is the kind of connection found, for example, in metabolic or gene regulation networks. There is a clear flow of signal implied and the network can be organised hierarchically.

Weighted edges 

Directed or undirected edges can also have weight or a quantitative value associated with them. This is used to depict concepts such a reliability of an interaction, the quantitative expression change that a gene induces over another or even how closely related two genes are in terms of sequence similarity. Edges can also be weighted by their centrality values or several other topological parameters.

Graph types by edge type

Figure 3 The main types of edges found in a network.