Edge Vector representation

Edge Vector representation is a novel method of representing graphs. It was introduced in [1]. The advantage of this representation is the minimum requirement in memory usage, in comparison to competition. Also encoding a graph in Edge Vector or decoding the graph elements from the representation is efficient with polynomial complexity.

Use Edge Vector online Coder-Decoder here.

In the libraries there are coders / decoders implemented in Java and Javascript. Also included a Javascript library for converting files from Dimacs format to Edge Vector which is used as a benchmark.

In the randographs folder there is a web application for generating randomgraphs.

In the DIMACS folder there are graphs from the Second DIMACS Implementation Challenge, they may be used as benchmark.

Edge Vector for undirected graphs

Let \(s\) be a vector that represents undirected graph \(G(V, E)\), consisting of \(v\) nodes. We further enumerate the elements of \(s\) in the range \([0, e)\), where \(e = v(v-1) / 2\) is the maximum possible number of edges in \(G\). The symbol in position \(q\) of \(s\) is \(w\), if nodes \(a\) and \(b\) are adjacent and 0 if they are not adjacent, where

(eq. 1) \(q=a+\sum_{x=0}^{b-1}x\) , for \(a < b\) and \(a, b \in [0, v)\).

The value of \(w\) is set to 1 for non-weighted graphs, whereas for weighted graphs the respective value corresponds to the weight of the edge \((a, b)\).

Edge vector for directed graphs

For directed graph \(G\) the Edge Vector representation only differs on value \(w\). On non-weighted graphs, \(w=1\) for \(a \to b\), \(w=2\) for \(b \gets a\) and \(w=3\) for \(a \leftrightarrow b\). For weighted graphs we form additional vector \(s_w\) so that in position \(p\) of \(s_w\) we assign the weight of the edge denoted in position \(p\) of \(s\). In the special case of bidirectinal edge \((a, b)\) in which different weights apply in each direction, \(s_w\) is formatted as \(w_1 | w_2\) where \(w_1\) is the weight for \((a, b)\) and \(w_2\) the weight for \((b, a)\).

Edge Vector Index

Let \(i\) be the array (or the tuple) that indexes the Edge Vector representation of graph \(G\). For any edge \(e(a,b) \in E\) we place in \(i\) value \(q\) as defined in eq. 1. On this way, the index that is produced does not contain redundant information about nonadjacent nodes. The order in which we index the edges in \(i\) is not restrictive, we can use any indexing order that is appropriate for the problem under study.

An example of a small NN representation in Edge Vector Index is illustrated in next figure. figure.1

Directed edges are represented by array \(i_{dir}\) so that in position \(p\) of \(i_{dir}\) we assign value 1, 2 or 3 as defined above that denotes the direction of the edge indexed in position \(p\) of index \(i\). Edge weights are denoted in array \(i_w\) so that in position \(p\) of \(i_w\) we assign the weight of the edge denoted in position \(p\) of \(i\).

In the case of graph \(G\) with weighted nodes, the node weights are stored in a Node Weight Vector. Therefore, in vector \(k:\langle w_0, w_1, …, w_v \rangle\) the value \(w_n\) represents the weight of node \(n\).

[1] P. Rodis and P. Papadimitriou, “Intelligent Network Service Embedding using Genetic Algorithms,” 2021 IEEE Symposium on Computers and Communications (ISCC), 2021, pp. 1-7, doi: 10.1109/ISCC53001.2021.9631456. pdf.