CESDAM: Centered subgraph data matrix for large graph representation

Abstract

In this chapter, a space efficient graph representation scheme is proposed. Unlike the classical approaches where entire graph is represented in single entities such as adjacency matrix or incidence matrix, the proposed approach represents subgraphs of the graph into multiple entities. An algorithm is designed to generate the proposed representation from the raw data where relationships among objects are identified as edges. The time complexity of the algorithm is bounded by the best case Θ(m) and worst case O(mk), where m is the number of edges in the graph and k is the number of subgraphs generated for the graph. The methodology is further extended for generating the proposed representation with already available edge list or adjacency matrix. Theoretical, as well as empirical analysis on eight real-world graphs, show efficiency of the proposed approach in terms of memory requirement over existing representations. © 2023 Elsevier Inc.