Simplification of large networks and graphs
AssigneeInternational Business Machines Corporation
InventorsKonstantinos Bekas, Alessandro Curioni
Life of this patent
Estimating the term…
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.
Claims15
A computer-implemented method, comprising:
- calculating, by a processing device, node centralities of a graph until a designated number of central nodes are detected;
- selecting a percentage of the central nodes as pivot nodes;
- collapsing neighboring nodes to each pivot node until the graph shrinks to a predefined threshold of total nodes;
- and
- outputting the graph responsive to reaching the predefined threshold.
-14. (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:
- calculating node centralities of a graph until a designated number of central nodes are detected;
- selecting a percentage of the central nodes as pivot nodes;
- collapsing neighboring nodes to each pivot node until the graph shrinks to a predefined threshold of total nodes;
- and
- outputting the graph responsive to reaching the predefined threshold.
Dependencies are inferred from the claim text.