A novel graph matrix representation: sequence of neighbourhood matrices with an application
- PDF / 3,208,300 Bytes
- 13 Pages / 595.276 x 790.866 pts Page_size
- 9 Downloads / 187 Views
A novel graph matrix representation: sequence of neighbourhood matrices with an application Sivakumar Karunakaran1 · Lavanya Selvaganesh2 Received: 31 October 2019 / Accepted: 30 March 2020 © Springer Nature Switzerland AG 2020
Abstract In the study of network optimization, finding the shortest path minimizing time/distance/cost from a source node to a destination node is one of the fundamental problems. Our focus here is to find the shortest path between any pair of nodes in a given undirected unweighted simple graph with the help of the sequence of powers of neighbourhood matrices. The authors recently introduced the concept of neighbourhood matrix as a novel representation of graphs using the neighbourhood sets of the vertices. In this article, an extension of the above work is presented by introducing a sequence of matrices, referred to as the sequence of powers of NM(G) . It is denoted it by NM{l} (G) = [𝜂ij{l} ], 1 ≤ l ≤ k(G) , where k(G) is called the iteration number, k(G) = ⌈log2 diameter(G)⌉ . As this sequence of matrices captures the distance between the nodes profoundly, we further develop the technique and present several characterizations. Based on the theoretical results, we present an algorithm to find the shortest path between any pair of nodes in a given graph. The proposed algorithm and the claims therein are formally validated through simulations on synthetic data and the real network data from Facebook. The empirical results are quite promising with our algorithm having best running time among all the existing well-known shortest path algorithms for the considered graph classes. Keywords Shortest path problem · Graph matrix · Neighbourhood matrix · Matrix multiplication · Complex network analysis Mathematics Subject Classification 05C50 · 05C62 · 05C82 · 05C85
1 Introduction With the advent of modern technology and electronic devices, the occurrence of large-scale networks is widespread and ubiquitous. Especially in the field of computer science, these networks are omnipresent in various forms such as communication networks and social networks. These networks require cooperation between a large number of individual components/parts. Major challenges in this field include predicting the behaviour
of the large-scale network, and information propagation within the network. For every large-scale network that arises in daily life, their understanding and mathematical description are crucial and achieved with the aid of an intricate graph representation that encodes the interaction between the network’s components. One of the fundamental problems in the study of network optimization is the shortest path problem that deals with finding a path with minimum distance, time or cost from the source to the destination. Most of the
A preliminary version of this article is also available in the arXiv with the identifier 1903.05377. * Lavanya Selvaganesh, [email protected]; Sivakumar Karunakaran, [email protected] | 1SRM Research Institute, SRM Institute of Science and Tech
Data Loading...
