Efficient Complex Network Representation Using Prime Numbers

In this work, we propose a novel representation of complex networks, which is compact and enables very efficient network analysis. Multi-relational networks capture complex data relationships and have a wide range of applications. As they get to be used with ever larger quantities of data, it is crucial to find efficient ways to represent and analyse them. This paper introduces the concept of Prime Adjacency Matrices (PAMs), which utilize prime numbers, to represent the relations of the network. Due to the Fundamental Theorem of Arithmetic, this allows for a lossless, compact representation of a complete multi-relational graph, using a single adjacency matrix. Moreover, this representation enables the fast computation of multi-hop adjacency matrices, which can be useful for a variety of downstream tasks. We illustrate the benefits of using the proposed approach through various network analysis tasks.