A unique and novel graph matrix for efficient extraction of structural information of networks

Abstract

In this article, we propose a new type of square matrix associated with an undirected graph by trading off the natural embedded symmetry in them. The proposed matrix is defined using the neighbourhood sets of the vertices,  called as neighbourhood matrix NM(G).  The proposed matrix also exhibits a  bijection between the product of the two graph matrices, namely the adjacency matrix and the graph Laplacian. Alternatively, we define this matrix by using the breadth-first search traversals from every vertex, and the subgraph induced by the first two levels in the level decomposition from that vertex. The two levels in the level decomposition of the graph give us more information about the neighbours along with the neighbours-of-neighbour of a vertex. This insight is required and is found useful in studying the impact of broadcasting on social networks, in particular, and complex networks, in general. We establish several properties of NM(G). Additionally, we also show how to reconstruct a graph G, given an  NM(G). The proposed matrix also solves many graph-theoretic problems using less time complexity in comparison to the existing algorithms.