Chapter Six Processing large graphs with an alternative representation

This chapter investigates the processing of large graphs with a novel graph representation scheme, the centered subgraph data matrix (CESDAM). The graph is represented in multiple CESDAMs, each containing subgraphs of the graph. Processing time and memory requirement are the two major issues while dealing with the processing of large graphs. The representation of graph is crucial for handling both these issues. The efficiency of CESDAM scheme in terms of time requirement is analyzed by incorporating the breadth-first searching, which is the backbone of most graph processing algorithms. The analysis shows, breadth-first searching on CESDAM requires time O(n × B × m 2), where n is the number of nodes in the graph, B is the branching factor of the meta-graph prepared on top of CESDAM ids, and m is the size of each CESDAM. The widely used adjacency matrix is becoming inefficient with enormously growing sizes of modern-day graphs, which requires very large amount of space for such graphs. Representation of graph in parts with CESDAM reduces the memory requirement significantly in contrast to adjacency matrix, which requires space O(k × m 2) only, where k is the number of CESDAMs.