# US 2018/0322219 A1 · Simplification of large networks and graphs

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2018/0322219 A1
- Document ID: US20180322219A1
- Status: Published application
- Kind: A1
- Application number: 16/033,361
- Filed: 2018-07-12
- Published: 2018-11-08
- Earliest claimed: 2013-05-22
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Konstantinos Bekas; Alessandro Curioni
- Web page: https://patentgrep.com/patent/US20180322219A1

## CPC

- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 9/3001: {Arithmetic instructions}
- G06F 16/9027: {Trees}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

The computer-implemented method of claim 1, wherein the computing of the diagonal further comprises calculating the diagonal based on a formula Ds=SUM1s (vi.x F(A)vi) ./ SUM1s (vi.x vi), where D is a diagonal, vi 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.

### Claim 6 (depends on 5)

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 vi;
c) computing the product of the matrix and the random probe vector;
d) updating vector Q by calculating Q=Q+vi.x Z, where Z is the product of the matrix and the random probe vector;
e) updating vector W by calculating W=W+vi.x vi;
f) updating vector D by calculating D=D+Q ./ W; and
g) repeating operations b-f until a designated end condition is reached.

### Claim 7 (depends on 6)

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.

### Claim 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.

### Claim 9 (depends on 8)

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.

### Claim 10 (depends on 9)

The computer system of claim 9, wherein the first set of neighboring nodes and the second set of neighboring nodes are not pivot nodes.

### Claim 11 (depends on 8)

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.

### Claim 12 (depends on 8)

The computer system of claim 8, wherein the computing of the diagonal further comprises calculating the diagonal based on a formula Ds=SUM1s (vi .x F(A)vi) ×/ SUM1s (vi .x vi), where D is a diagonal, vi 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.

### Claim 13 (depends on 12)

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 vi;
c) computing the product of the matrix and the random probe vector;
d) updating vector Q by calculating Q=Q+vi.x Z, where Z is the product of the matrix and the random probe vector;
e) updating vector W by calculating W=W+vi.x vi;
f) updating vector D by calculating D=D+Q ./ W; and
g) repeating operations b-f until a designated end condition is reached.

### Claim 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.

### Claim 15 (depends on 14)

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.

### Claim 16 (depends on 15)

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.

### Claim 17 (depends on 14)

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.

### Claim 18 (depends on 14)

The computer program product of claim 14, wherein the computing of the diagonal further comprises calculating the diagonal based on a formula Ds=SUM1s (vi.x F(A)vi) ./ SUM1s (vi.x vi), where D is a diagonal, vi 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.

### Claim 19 (depends on 18)

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 vi;
c) computing the product of the matrix and the random probe vector;
d) updating vector Q by calculating Q=Q+vi.x Z, where Z is the product of the matrix and the random probe vector;
e) updating vector W by calculating W=W+vi.x vi;
f) updating vector D by calculating D=D+Q ./ W; and
g) repeating operations b-f until a designated end condition is reached.

### Claim 20 (depends on 19)

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.
