Granted Patent B2

US 12,199,828 · App. 17/485,937 · Granted Jan 14, 2025

Inventors: Charles John Scates (London, GB); Kilian David Joseph Collender (London, GB); Luke Taher (Heswall, GB); Jorge Alberto Diaz Garcia (London, GB)

Assignee: International Business Machines Corporation

H04L41/12

Abstract

Claims (77)

1. A system for generating an abstract graph of a network topology, the system comprising:

one or more computer processing circuits; and

one or more computer-readable storage media storing program instructions which, when executed by the one or more computer processing circuits, are configured to cause the one or more computer processing circuits to perform a method comprising:

for each of a plurality of vertices, generate a vertex weighting representative of a relative importance of a vertex within the network topology as a key resource in detecting an anomalous change to the network topology, the relative importance determined by at least in part on a frequency of appearance of the vertex in the network topology;

for each of one or more edges, generate an edge weighting representative of a relative importance of an edge within the network topology;

generate the abstract graph of the network topology based on a plurality of vertex weightings and one or more edge weightings;

obtain, at a point in time after initialization of the abstract graph, a live graph of the network topology, the live graph representing the plurality of vertices and the one or more edges currently present in the network topology; and

compare the live graph of the network topology to the abstract graph of the network topology to determine whether a change to the network topology is anomalous.

2. A method for generating an abstract graph of a network topology, the method comprising:

for each of a plurality of vertices, generating a vertex weighting representative of a relative importance of a vertex within the network topology as a key resource in detecting an anomalous change to the network topology;

for each of one or more edges, generating an edge weighting representative of a relative importance of an edge within the network topology, the relative importance determined by at least in part on a frequency of appearance of the vertex in the network topology;

generating the abstract graph of the network topology based on a plurality of vertex weightings and one or more edge weightings;

obtaining, at a point in time after initialization of the abstract graph, a live graph of the network topology, the live graph representing the plurality of vertices and the one or more edges currently present in the network topology; and

comparing the live graph of the network topology to the abstract graph of the network topology to determine whether a change to the network topology is anomalous.

3. The method of claim 2 , wherein the method further includes:

adjusting the plurality of vertex weightings based on the change to the network topology determined based on the comparison of the live graph to the abstract graph of the network topology; and

generating an updated abstract graph of the network topology based on the adjusted plurality of vertex weightings.

4. The method of claim 3 , wherein adjusting the plurality of vertex weightings includes:

determining whether a vertex present in the live graph is present in the abstract graph of the network topology:

in response to determining the vertex present in the live graph is present in the abstract graph of the network topology, adjusting the vertex weighting of the vertex; and

in response to determining the vertex present in the live graph is not present in the abstract graph of the network topology, generating a vertex weighting representative of a relative importance of the vertex within the network topology; and

determining whether a vertex present in the abstract graph of the network topology is absent in the live graph:

in response to determining the vertex present in the abstract graph of the network topology is absent in the live graph, adjusting the vertex weighting of the vertex.

5. The method of claim 4 , wherein, in response to the vertex being present in the abstract graph of the network topology and absent in the live graph, the method further includes:

comparing the vertex weighting of the vertex to an upper threshold value; and

in response to the vertex weighting being greater than the upper threshold value, generating an alert.

6. The method of claim 4 , wherein, in response to the vertex being present in the abstract graph of the network topology and the live graph, the method further includes:

comparing the vertex weighting of the vertex to a lower threshold value; and

in response to the vertex weighting being less than the lower threshold value, generating an alert.

7. The method of claim 4 , wherein, in response to the vertex being present in the abstract graph of the network topology and the live graph, adjusting the vertex weighting of the vertex includes increasing the vertex weighting.

8. The method of claim 4 , wherein, in response to determining that the vertex is absent in the live graph, adjusting the vertex weighting of the vertex includes decreasing the vertex weighting of the vertex.

9. The method of claim 3 , wherein the method further includes:

obtaining an identifying feature of each vertex;

generating a hash code for each vertex based on the identifying feature; and

assigning the vertex weighting of each vertex to the respective hash code as a hash weighting.

10. The method of claim 9 , wherein obtaining the live graph of the network topology includes, for each vertex present in the live graph:

determining whether a hash code exists for a vertex:

in response to determining the hash code exists for the vertex:

assigning the hash weighting of the hash code to the vertex as the vertex weighting; and

adjusting the hash weighting based on the change to the network topology; and

in response to determining the hash code does not exist for the vertex:

obtaining an identifying feature of the vertex;

generating a hash code for the vertex based on the identifying feature; and

assigning the vertex weighting of the vertex to the respective hash code as a hash weighting.

11. The method of claim 2 , wherein the method further includes:

adjusting the one or more edge weightings based on the change to the network topology determined based on the comparison of the live graph to the abstract graph of the network topology; and

generating an updated abstract graph of the network topology based on the adjusted edge weightings.

12. The method of claim 11 , wherein the method further includes:

determining whether an edge present in the live graph is present in the abstract graph of the network topology:

in response to determining the edge present in the live graph is present in the abstract graph of the network topology, adjusting the edge weighting of the edge; and

in response to determining the edge present in the live graph is not present in the abstract graph of the network topology, generating an edge weighting representative of a relative importance of the edge within the network topology; and

determining whether an edge that is present in the abstract graph of the network topology is absent in the live graph:

in response to determining the edge that is present in the abstract graph of the network topology is absent in the live graph, adjusting the edge weighting of the edge.

13. The method of claim 12 , wherein, in response to the edge being present in the abstract graph of the network topology and absent in the live graph, the method further includes:

comparing the edge weighting of the edge to an upper threshold value; and

in response to the edge weighting being greater than the upper threshold value, generating an alert.

14. The method of claim 12 , wherein, in response to the edge being present in the abstract graph of the network topology and the live graph, the method further includes:

comparing the edge weighting of the edge to a lower threshold value; and

in response to the edge weighting being less than the lower threshold value, generating an alert.

15. The method of claim 12 , wherein, in response to the edge being present in the abstract graph of the network topology and the live graph, adjusting the edge weighting of the edge includes increasing the edge weighting.

16. The method of claim 12 , wherein, in response to the edge being present in the abstract graph of the network topology and absent in the live graph, adjusting the edge weighting of the edge includes decreasing the edge weighting of the edge.

17. The method of claim 2 , wherein the vertex weightings and the edge weightings are fuzzy weightings having a value greater than or equal to zero and less than one.

18. A computer program product for generating an abstract graph of a network topology, the computer program product comprising one or more computer readable storage media, and program instructions collectively stored on the one or more computer readable storage media, the program instructions comprising instructions configured to cause one or more processors to perform a method comprising:

for each of a plurality of vertices, generating a vertex weighting representative of a relative importance of a vertex within the network topology as a key resource in detecting an anomalous change to the network topology, the relative importance determined by at least in part on a frequency of appearance of the vertex in the network topology;

for each of one or more edges, generating an edge weighting representative of a relative importance of an edge within the network topology;

generating the abstract graph of the network topology based on a plurality of vertex weightings and one or more edge weightings;

obtaining, at a point in time after initialization of the abstract graph, a live graph of the network topology, the live graph representing the plurality of vertices and the one or more edges currently present in the network topology; and

comparing the live graph of the network topology to the abstract graph of the network topology to determine whether a change to the network topology is anomalous.

19. The computer program product of claim 18 , wherein the method further includes:

adjusting the plurality of vertex weightings based on the change to the network topology determined based on the comparison of the live graph to the abstract graph of the network topology; and

generating an updated abstract graph of the network topology based on the adjusted vertex weightings.

20. The computer program product of claim 18 , wherein adjusting the plurality of vertex weightings includes:

determining whether a vertex present in the live graph is present in the abstract graph of the network topology:

in response to determining the vertex present in the live graph is present in the abstract graph of the network topology, adjusting the vertex weighting of the vertex; and

in response to determining the vertex present in the live graph is not present in the abstract graph of the network topology, generating a vertex weighting representative of a relative importance of the vertex within the network topology; and

determining whether a vertex that is present in the abstract graph of the network topology is absent in the live graph:

in response to determining the vertex is absent in the live graph, adjusting the vertex weighting of the vertex.

Assignments (1)

Continuity (1)

References Cited (28)