Simplification of large networks and graphs

Abstract

Embodiments relate to simplifying large and complex networks and graphs using global connectivity information based on calculated node centralities. An aspect includes calculating node centralities of a graph until a designated number of central nodes are detected. A percentage of the central nodes are then selected as pivot nodes. The neighboring nodes to each of the pivot nodes are then collapsed until the graph shrinks to a predefined threshold of total nodes. Responsive to the number of total nodes reaching the predefined threshold, the simplified graph is outputted.

What is claimed is: 
     
         1 . A computer-implemented method for reducing a memory footprint of a network, the method comprising:
 utilizing an original network to model dynamics, wherein the original network has an original memory footprint in a computer system;   calculating node centralities of the original network until a designated number of central nodes are detected, wherein the calculating of the node centralities of the original network further comprises:
 approximating a product of a matrix exponential and a random probe vector of an adjacency matrix, the adjacency matrix representing the original network; and 
 computing a diagonal of the adjacency matrix based on the product of the matrix exponential and the random probe vector; 
   selecting a percentage of the central nodes as pivot nodes;   collapsing neighboring nodes to each pivot node of the original network to shrink the original network to generate a reduced network until the reduced network reaches a predefined threshold of total nodes; and   utilizing the reduced network to model the dynamics, wherein the reduced network has a reduced memory footprint in the computer system as compared to the original footprint.   
     
     
         2 . The computer-implemented method of  claim 1 , wherein the collapsing further comprises:
 acquiring a first set of neighboring nodes for each pivot node;   acquiring a second set of neighboring nodes for each node in the first set of neighboring nodes;   deleting the first set of neighboring nodes; and   establishing the second set of neighboring nodes as neighbors for a current pivot node.   
     
     
         3 . The computer-implemented method of  claim 2 , wherein the first set of neighboring nodes and the second set of neighboring nodes are not pivot nodes. 
     
     
         4 . The computer-implemented method of  claim 1 , wherein the approximating of the product of the matrix and the random probe vector further comprises:
 computing an orthogonal Krylov basis and tridiagonal matrix using a Lanczos algorithm;   computing a matrix exponential of the tridiagonal matrix; and   computing a current approximation of the product of the matrix exponential and the random probe vector.   
     
     
         5 . The computer-implemented method of  claim 1 , wherein the computing of the diagonal further comprises calculating the diagonal based on a formula D s =SUM 1   s  (v i .x F(A)v i ) ./ SUM 1   s  (v i. x v i ), where D is a diagonal, v i  is the random probe vector, s is the total number of required vectors, A is the adjacency matrix of size N, F(A) is the matrix exponential, .x symbolizes element-wise multiplication, and ./ symbolizes element-wise division. 
     
     
         6 . The computer-implemented method of  claim 5 , wherein the computing of the diagonal further comprises:
 a) initializing vectors Q, W, and D of length N to zero;   b) initializing the random probe vector v i ;   c) computing the product of the matrix and the random probe vector;   d) updating vector Q by calculating Q=Q+v i .x Z, where Z is the product of the matrix and the random probe vector;   e) updating vector W by calculating W=W+v i .x v i ;   f) updating vector D by calculating D=D+Q ./ W; and   g) repeating operations b-f until a designated end condition is reached.   
     
     
         7 . The computer-implemented method of  claim 6 , wherein the designated end condition comprises a selected one of a condition where the difference of a previously estimated diagonal and the estimated diagonal is smaller than a designated diagonal tolerance, a condition where the maximum number of steps s has been reached, and a condition where the percentage of nodes with highest centrality has converged. 
     
     
         8 . A computer system comprising:
 a memory having computer-readable instructions; and   one or more processors for executing the computer-readable instructions, the computer-readable instructions comprising:
 utilizing an original network to model dynamics, wherein the original network has an original memory footprint in a computer system; 
 calculating node centralities of the original network until a designated number of central nodes are detected, wherein the calculating of the node centralities of the original network further comprises:
 approximating a product of a matrix exponential and a random probe vector of an adjacency matrix, the adjacency matrix representing the original network; and 
 computing a diagonal of the adjacency matrix based on the product of the matrix exponential and the random probe vector; 
 
 selecting a percentage of the central nodes as pivot nodes; 
 collapsing neighboring nodes to each pivot node of the original network to shrink the original network to generate a reduced network until the reduced network reaches a predefined threshold of total nodes; and 
 utilizing the reduced network to model the dynamics, wherein the reduced network has a reduced memory footprint in the computer system as compared to the original footprint. 
   
     
     
         9 . The computer system of  claim 8 , wherein the collapsing further comprises:
 acquiring a first set of neighboring nodes for each pivot node;   acquiring a second set of neighboring nodes for each node in the first set of neighboring nodes;   deleting the first set of neighboring nodes; and   establishing the second set of neighboring nodes as neighbors for a current pivot node.   
     
     
         10 . The computer system of  claim 9 , wherein the first set of neighboring nodes and the second set of neighboring nodes are not pivot nodes. 
     
     
         11 . The computer system of  claim 8 , wherein the approximating of the product of the matrix and the random probe vector further comprises:
 computing an orthogonal Krylov basis and tridiagonal matrix using a Lanczos algorithm;   computing a matrix exponential of the tridiagonal matrix; and   computing a current approximation of the product of the matrix exponential and the random probe vector.   
     
     
         12 . The computer system of  claim 8 , wherein the computing of the diagonal further comprises calculating the diagonal based on a formula D s =SUM 1   s  (v i  .x F(A)v i ) ×/ SUM 1   s  (v i  .x v i ), where D is a diagonal, v i  is the random probe vector, s is the total number of required vectors, A is the adjacency matrix of size N, F(A) is the matrix exponential, .x symbolizes element-wise multiplication, and ./ symbolizes element-wise division. 
     
     
         13 . The computer system of  claim 12 , wherein the computing of the diagonal further comprises:
 a) initializing vectors Q, W, and D of length N to zero;   b) initializing the random probe vector v i ;   c) computing the product of the matrix and the random probe vector;   d) updating vector Q by calculating Q=Q+v i .x Z, where Z is the product of the matrix and the random probe vector;   e) updating vector W by calculating W=W+v i .x v i ;   f) updating vector D by calculating D=D+Q ./ W; and   g) repeating operations b-f until a designated end condition is reached.   
     
     
         14 . A computer program product for reducing a memory footprint of a network, the computer-program product comprising a computer-readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform a method comprising:
 utilizing an original network to model dynamics, wherein the original network has an original memory footprint in a computer system;   calculating node centralities of the original network until a designated number of central nodes are detected, wherein the calculating of the node centralities of the original network further comprises:
 approximating a product of a matrix exponential and a random probe vector of an adjacency matrix, the adjacency matrix representing the original network; and 
 computing a diagonal of the adjacency matrix based on the product of the matrix exponential and the random probe vector; 
   selecting a percentage of the central nodes as pivot nodes;   collapsing neighboring nodes to each pivot node of the original network to shrink the original network to generate a reduced network until the reduced network reaches a predefined threshold of total nodes; and   utilizing the reduced network to model the dynamics, wherein the reduced network has a reduced memory footprint in the computer system as compared to the original footprint.   
     
     
         15 . The computer program product of  claim 14 , wherein the collapsing further comprises:
 acquiring a first set of neighboring nodes for each pivot node;   acquiring a second set of neighboring nodes for each node in the first set of neighboring nodes;   deleting the first set of neighboring nodes; and   establishing the second set of neighboring nodes as neighbors for a current pivot node.   
     
     
         16 . The computer program product of  claim 15 , wherein the first set of neighboring nodes and the second set of neighboring nodes are not pivot nodes. 
     
     
         17 . The computer program product of  claim 14 , wherein the approximating of the product of the matrix and the random probe vector further comprises:
 computing an orthogonal Krylov basis and tridiagonal matrix using a Lanczos algorithm;   computing a matrix exponential of the tridiagonal matrix; and   computing a current approximation of the product of the matrix exponential and the random probe vector.   
     
     
         18 . The computer program product of  claim 14 , wherein the computing of the diagonal further comprises calculating the diagonal based on a formula D s =SUM 1   s  (v i .x F(A)v i ) ./ SUM 1   s  (v i .x v i ), where D is a diagonal, v i  is the random probe vector, s is the total number of required vectors, A is the adjacency matrix of size N, F(A) is the matrix exponential, .x symbolizes element-wise multiplication, and ./ symbolizes element-wise division. 
     
     
         19 . The computer program product of  claim 18 , wherein the computing of the diagonal further comprises:
 a) initializing vectors Q, W, and D of length N to zero;   b) initializing the random probe vector v i ;   c) computing the product of the matrix and the random probe vector;   d) updating vector Q by calculating Q=Q+v i .x Z, where Z is the product of the matrix and the random probe vector;   e) updating vector W by calculating W=W+v i .x v i ;   f) updating vector D by calculating D=D+Q ./ W; and   g) repeating operations b-f until a designated end condition is reached.   
     
     
         20 . The computer program product of  claim 19 , wherein the designated end condition comprises a selected one of a condition where the difference of a previously estimated diagonal and the estimated diagonal is smaller than a designated diagonal tolerance, a condition where the maximum number of steps s has been reached, and a condition where the percentage of nodes with highest centrality has converged.