Systems and methods for full history dynamic network analysis
Provided herein are methods and systems for determining a historical state of a dynamic network. The methods may comprise continuously obtaining data associated with a system from a plurality of different data sources; constructing a full history dynamic network (FHDN) of the system using the data; and providing a state of the system for a historical time instance in response to a query of the FHDN for the historical time instance.
1. A computer-implemented method of determining a historical state of a system, the method comprising:
obtaining data about the system from a plurality of different data sources over a period of time;
constructing, by a network graphing component, a full history dynamic network (FHDN) using the data, wherein the FHDN comprises a graph representing the system over the period of time, wherein the graph comprises:
(1) a plurality of nodes that represent elements of the system during the period of time, wherein the plurality of nodes are capable of dynamically changing over the period of time;
(2) a plurality of edges connecting the nodes, wherein each edge of the plurality of edges represents a relationship between a pair of nodes over the period of time, and wherein the plurality of edges are capable of dynamically changing over the period of time;
(3) first time series associated with each of the plurality of nodes; and
(4) second time series data associated with each of the plurality of edges,
wherein the first time series indicate changes in state of the plurality of nodes over the period of time and the second time series data indicate changes in the state of the plurality of edges over the period of time; and
generating a graphical representation of an operational state of the system at a historical time instance within the period of time in response to a query of the first time series and the second time series data of the FHDN.
2. The method of claim 1 , wherein the graphical representation of the operational state of the system comprises an exact graphical representation of the state of the system, in an as-operated state, at the historical time instance.
3. The method of claim 1 , wherein the graphical representation of an operational state of the system comprises an exact graphical state for a subset of the system at the historical time instance.
4. The method of claim 1 , further comprising determining a historical dynamic behavior of the FHDN based on the first time series and the second time series data without analyzing a sequence of snapshots of the system captured at different points in time.
5. The method of claim 1 , further comprising searching, based on the query of the FHDN for the historical time instance, a subset of the first time series, a subset of the second time series data, or a subset of both the first time series and the second time series data, wherein the FHDN permits the query for the historical time instance to be answered without requiring full system instantiation at said historical time instance.
6. The method of claim 1 , wherein the plurality of nodes and edges of the graph comprises (1) all nodes and edges that previously existed but no longer exist in the system, and (2) all nodes and edges that presently exist in the system.
7. The method of claim 1 , wherein the first time series for a selected node comprises times of additions or removals of the selected node in the system, wherein the second time series data for a selected edge comprises times of additions or removals of the selected edge in the-system.
8. The method of claim 1 , wherein the first time series are based on events or changes occurring at a selected node, and wherein the second time series data are based on events or changes occurring at a selected edge.
9. The method of claim 1 , wherein the state of the system at the historical time instance is obtained by using the query and a search algorithm that iterates over the plurality of nodes and searches through the first time series and the second time series data.
10. The method of claim 9 , wherein the search algorithm comprises an iterative graph search algorithm that is configured to only check a status of selected nodes or edges on an as-needed basis.
11. The method of claim 9 , wherein the query comprises an information request about a subset of nodes at a given time instance, and wherein the search algorithm is configured to query the subset of nodes only and directly, without querying nodes outside the subset of nodes.
12. The method of claim 1 , further comprising utilizing a blocking technique to cache entire connected graphical regions of the FHDN in memory for any given instance in time.
13. The method of claim 12 , wherein the connected graphical regions of the FHDN contain no unreachable nodes.
14. The method of claim 12 , wherein the blocking technique comprises standard blocking, token blocking, or attribute-clustering blocking.
15. The method of claim 13 , wherein the caching of the entire connected graphical regions in memory allows searches to be carried out more quickly compared to conventional network graphing techniques.
16. The method of claim 1 , wherein the use of the FHDN allows memory/storage savings of at least three orders of magnitude compared to conventional network graphing techniques.
17. The method of claim 1 , wherein the FHDN is stored in a two-dimensional matrix comprising a plurality of rows and columns, wherein each row of the plurality of rows represents one of the plurality of nodes, wherein each column of the plurality of columns represents one of the plurality of edges, and wherein an entry at a row and a column in the two-dimensional matrix indicates whether the edge represented by the column is connected to the node represented by the row.
18. The method of claim 17 , wherein the entry is a portion of the first time series, the second time series data, or both.
19. The method of claim 1 , wherein the FHDN is stored in a graph database.
20. The method of claim 19 , wherein the graph database comprises a plurality of pointers between the plurality of nodes, wherein each pointer represents one of the plurality of edges.
21. The method of claim 20 , wherein the plurality of pointers comprises a pointer that is bidirectional.
22. The method of claim 20 , wherein the plurality of pointers comprises a pointer that is unidirectional.
23. The method of claim 1 , wherein the plurality of nodes and the plurality of edges comprise tags or properties.
24. The method of claim 1 , wherein the plurality of edges comprises weights that indicate strength of connections or relationships between nodes.
25. The method of claim 1 , wherein the system comprises a Bill of Materials for a manufacturing company.
26. The method of claim 1 , wherein the FHDN is constructed without requiring periodic capturing and storing of snapshots of the system at different points in time.
27. The method of claim 1 , wherein constructing the FHDN of the system comprises generating data objects that represent the plurality of nodes, the plurality of edges, the first time series, and the second time series data.
28. A system for determining a historical state of a system, the system comprising:
a data aggregation component for continuously obtaining data about a system from a plurality of different data sources over a period of time; and
a network graphing component configured to:
construct a full history dynamic network (FHDN) of the system using the data, wherein the FHDN comprises a graph representing the system over the period of time, wherein the graph comprises:
(1) a plurality of nodes that represent elements of the system during the period of time, wherein the plurality of nodes are capable of dynamically changing over the period of time;
(2) a plurality of edges connecting the nodes, wherein each edge of the plurality of edges represents a relationship between a pair of nodes over the period of time, and wherein the plurality of edges are capable of dynamically changing over the period of time;
(3) first time series associated with each of the plurality of nodes; and
(4) second time series associated with each of the plurality of edges,
wherein the first time series indicate changes in a state of the plurality of nodes over the period of time and the second time series indicate changes in a state of the plurality of edges over the period of time, and wherein the FHDN is constructed without requiring periodic capturing and storing of snapshots of the system at different points in time; and
generate a graphical representation of an operational state of the system at a historical time instance within the period of time in response to a query of the FHDN.