Node-centric analysis of dynamic networks

• US 10,142,198 B2
• Filed: 05/02/2016
• Issued: 11/27/2018
• Est. Priority Date: 03/07/2016
• Status: Active Grant

• Current Assignee: Autodesk, Inc.
• Original Assignee: Autodesk, Inc.
• Inventors: Zhao, Jian, Glueck, Michael, Khan, Azam
• Primary Examiner(s): Coulter, Kenneth R
• Application Number:
  US15/144,627
• Publication Number:
  US 20170257291A1
• Time in Patent Office: 939 Days
• Field of Search: 709224, 709223
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 43/045 for graphical visualisation of monitoring data
• CPC Class Codes: H04L 43/06 Generation of reports

Abstract

A network analysis engine is configured to generate a network timeline that represents time-varying connectivity between nodes of the network over a time interval. The network timeline includes a sequence of network snapshots that illustrate links between nodes at specific, sequential sub-intervals of time. The network analysis engine is configured to organize the network timeline in order to reveal certain characteristics of the nodes in the network and the network as a whole. Based on these characteristics, the network can be optimized to improve overall network operation.

Claims

1. A non-transitory computer-readable medium that, when executed by a processor, causes the processor to generate a network timeline for a network by performing the steps of:

generating a first network snapshot that depicts, for a first sub-interval of time, a first set of nodes included in the network and a first set of connections associated with the first set of nodes;

generating a second network snapshot that depicts, for a second sub-interval of time, a second set of nodes included in the network and a second set of connections associated with the second set of nodes;

generating a first node timeline included in the first network snapshot and the second network snapshot that is associated with a first node included in the network, wherein the first node timeline indicates one or more topological changes in the network between the first sub-interval of time and the second sub-interval of time;

identifying a first cluster of connected nodes within the network that includes the first node; and

displaying the first node timeline using one or more visual attributes that differ from one or more corresponding visual attributes used to display at least one other node timeline associated with at least one other node that is included within the network and is not included in the first cluster.

2. The non-transitory computer-readable medium of claim 1, further comprising:

causing the first network snapshot to indicate a first subset of connections between the first node and the first set of nodes during the first sub-interval time; and

causing the second network snapshot to indicate a second subset of connections between the first node and the second set of nodes during the second sub-interval time.

3. The non-transitory computer-readable medium of claim 1, wherein the first node has more connections to other nodes in the first cluster of nodes than connections to other nodes that are within the network, but are not included in the first cluster.

4. The non-transitory computer-readable medium of claim 1, further comprising grouping a set of node timelines associated with the first cluster of nodes within at least one of the first network snapshot and the second network snapshot.

5. The non-transitory computer-readable medium of claim 1, further comprising:

generating a second node timeline included in at least one of the first network snapshot and the second network snapshot that is associated with a second node included in the network; and

generating a connection sequence that indicates one or more connections between the first node and the second node.

6. The non-transitory computer-readable medium of claim 5, wherein the one or more connections include a direct connection between the first node and the second node, or a sequence of indirect connections between the first node, one or more intermediate nodes, and the second node.

7. The non-transitory computer-readable medium of claim 1, further comprising updating one or more visual attributes of each node timeline included in the network timeline to indicate a degree of betweenness for each node timeline included in the network timeline.

8. The non-transitory computer-readable medium of claim 7, wherein the degree of betweenness for a first node timeline included in the network timeline corresponds to a number of node clusters within the network that include a particular node associated with the first node timeline.

9. The non-transitory computer-readable medium of claim 1, further comprising generating a first envelope that includes a first set of node timelines associated with a first set of nodes within the network that have first-degree connections to the first node.

10. The non-transitory computer-readable medium of claim 1, further comprising:

generating a second node timeline associated with the first sub-interval of time and the second sub-interval of time and that is associated with a second node included in the network; and

adding the second node timeline to the first network snapshot and the second network snapshot to keep the first node timeline and the second node timeline packed closely together.

11. The non-transitory computer-readable medium of claim 1, wherein the first node timeline indicates one or more changes within the network between the first sub-interval of time and the second sub-interval of time.

12. The non-transitory computer-readable medium of claim 1, wherein the one or more visual attributes comprise at least one of a color, a pattern, and an outline.

13. The non-transitory computer-readable medium of claim 1, wherein the first cluster of nodes comprises a plurality of nodes within the network, and further comprising displaying each node timeline associated with each node in the first cluster using the one or more visual attributes for displaying the first node timeline.

14. A computer-implemented method for generating a network timeline for a network, the method comprising:

generating a first network snapshot that depicts, for a first sub-interval of time, a first set of nodes included in the network and a first set of connections associated with the first set of nodes;

generating a second network snapshot that depicts, for a second sub-interval of time, a second set of nodes included in the network and a second set of connections associated with the second set of nodes;

generating a first node timeline included in the first network snapshot and the second network snapshot that is associated with a first node included in the network, wherein the first node timeline indicates one or more topological changes in the network between the first sub-interval of time and the second sub-interval of time;

identifying a first cluster of connected nodes within the network that includes the first node; and

displaying the first node timeline using one or more visual attributes that differ from one or more corresponding visual attributes used to display at least one other node timeline associated with at least one other node that is included within the network and is not included in the first cluster.

15. The computer-implemented method of claim 14, further comprising:

causing the first network snapshot to indicate a first subset of connections between the first node and the first set of nodes during the first sub- interval time; and

causing the second network snapshot to indicate a second subset of connections between the first node and the second set of nodes during the second sub-interval time.

16. The computer-implemented method of claim 14, further comprising:

identifying a first cluster of nodes within the network that includes the first node and is associated with at least one of the first sub-interval of time and the second sub-interval of time; and

causing one or more visual attributes of the first node timeline to differ from one or more corresponding visual attributes of at least one other node timeline associated with at least one other node that is included within the network, but is not included in the first cluster.

17. The computer-implemented method of claim 16, wherein the first node has more connections to other nodes in the first cluster of nodes than connections to other nodes that are within the network, but are not included in the first cluster, and further comprising grouping a set of node timelines associated with the first cluster of nodes within at least one of the first network snapshot and the second network snapshot.

18. The computer-implemented method of claim 14, further comprising:

generating a second node timeline included in at least one of the first network snapshot and the second network snapshot that is associated with a second node included in the network; and

generating a connection sequence that indicates one or more connections between the first node and the second node,

wherein the one or more connections include a direct connection between the first node and the second node, or a sequence of indirect connections between the first node, one or more intermediate nodes, and the second node.

19. The computer-implemented method of claim 14, further comprising:

generating a second node timeline associated with the first sub-interval of time and the second sub-interval of time and that is associated with a second node included in the network; and

adding the second node timeline to the first network snapshot and the second network snapshot to keep the first node timeline and the second node timeline packed closely together.

20. The computer-implemented method of claim 14, further comprising generating a set of statistics that indicate, across the first sub-interval of time and the second sub-interval of time, a number of vertices associated with the first node, a number of edges associated with the first node, and an edge-to-vertex ratio associated with the first node.

21. A system for generating a network timeline for a network, comprising:

a memory storing a software application; and

a processor that, when executing the software application, is configured to;

generate a first network snapshot that depicts, for a first sub-interval of time, a first set of nodes included in the network and a first set of connections associated with the first set of nodes;

generate a second network snapshot that depicts, for a second sub- interval of time, a second set of nodes included in the network and a second set of connections associated with the second set of nodes;

generate a first node timeline included in the first network snapshot and the second network snapshot that is associated with a first node included in the network, wherein the first node timeline indicates one or more topological changes in the network between the first sub-interval of time and the second sub-interval of time;

identify a first cluster of connected nodes within the network that includes the first node; and

display the first node timeline using one or more visual attributes that differ from one or more corresponding visual attributes used to display at least one other node timeline associated with at least one other node that is included within the network and is not included in the first cluster.