Calculating node centralities in large networks and graphs
AssigneeInternational Business Machines Corporation
InventorsKonstantinos Bekas, Alessandro Curioni
Life of this patent
Estimating the term…
Abstract
Embodiments related to calculating node centralities in large and complex networks and graphs. An aspect includes approximating a product of a matrix exponential and a random probe vector of an adjacency matrix, wherein the adjacency matrix represents a graph. A diagonal of the adjacency matrix is computed based on the product of the matrix exponential and the random probe vector. The node centralities are then calculated based on the computed diagonal until a designated number of central nodes has been detected according to embodiments.
Claims13
A computer-implemented method, comprising:
- approximating, by a processing device, a product of a matrix exponential and a random probe vector of an adjacency matrix, the adjacency matrix representing a graph;
- computing a diagonal of the adjacency matrix based on the product of the matrix exponential and the random probe vector;
- and
- calculating node centralities based on the computed diagonal of the adjacency matrix until a designated number of central nodes are detected.
-12. (canceled)
A computer program product, comprising:
- a computer readable storage medium having program code embodied therewith, the program code executable by a processing device for:
- approximating a product of a matrix exponential and a random probe vector of an adjacency matrix, the adjacency matrix representing a graph;
- computing a diagonal of the adjacency matrix based on the product of the matrix exponential and the random probe vector;
- and
- calculating node centralities based on the computed diagonal of the adjacency matrix until a designated number of central nodes are detected.
Dependencies are inferred from the claim text.