Network graph evolution rule generation

1. A method comprising:

collecting, by at least one processing unit, multiple graphs corresponding to a network, the network evolving over time, each graph representing a snapshot reflecting a state of the network at a time the snapshot was taken;

forming, by the at least one processing unit, one graph by merging the multiple graphs representing the multiple snapshots of the network, the formed graph comprising a set of nodes and a set of edges, each edge connecting two nodes from the set of nodes and having a temporal label;

mining, by the at least one processing unit, the formed graph to identify multiple patterns, each pattern being a subgraph in the formed graph, each pattern having an associated support;

selecting a pattern from the identified patterns;

identifying, by the at least one processing unit, a child pattern of the selected pattern, the child pattern of the pattern includes all but one of the edges of the pattern and the identified child pattern having a support that is at least equal to the support of the selected pattern in the formed graph and missing a portion of pattern, the missing portion of the pattern including at least one edge of the pattern wherein the missing edge has a temporal label that has a greatest value of the temporal labels assigned to edges of the selected pattern;

creating, by the at least one processing unit, a graph evolution rule, the rule indicating that any occurrence of the child pattern implies a corresponding occurrence of the pattern, the corresponding occurrence of the pattern being formed with the addition of the portion missing from the child pattern at a time indicated by the missing edge's temporal label.

2. The method of claim 1 , wherein the temporal label in the formed graph is absolute time and the missing edge's temporal label is relative time.

3. The method of claim 1 , wherein the temporal label of an initial edge of the pattern and child pattern is a relative time of zero.

4. The method of claim 3 , wherein the child pattern is missing one edge of the pattern, the missing edge has a temporal label with the highest value in the pattern.

5. The method of claim 1 , wherein the support of the pattern is a minimum possible number of mappings of a node of the pattern in the formed graph.

6. The method of claim 1 , further comprising:

assigning a support to the graph evolution rule, the assigned support is equal to the support of the pattern.

7. The method of claim 1 , further comprising:

assigning a confidence to the graph evolution rule, the assigned confidence is equal to a ratio of the support of the pattern to the support of the child pattern.

8. A system comprising:

at least one computing device, the at least one computing device comprising a processor and a non-transitory computer readable storage medium having stored thereon:

a graph merging component that:

collects multiple graphs corresponding to a network, the network evolving over time, each graph representing a snapshot reflecting a state of the network at a time the snapshot was taken;

forms one graph by merging the multiple graphs representing the multiple snapshots of the network, the formed graph comprising a set of nodes and a set of edges, each edge connecting two nodes from the set of nodes and having a temporal label;

a mining component that mines the formed graph to identify multiple patterns, each pattern being a subgraph in the formed graph, each pattern having an associated support;

a graph evolution rule generator that:

selects a pattern from the identified patterns;

identifies a child pattern of the selected pattern, the child pattern of the pattern includes all but one of the edges of the pattern and the identified child pattern having a support that is at least equal to the support of the selected pattern in the formed graph and missing a portion of pattern, the missing portion of the pattern including at least one edge of the pattern wherein the missing edge has a temporal label that has a greatest value of the temporal labels assigned to edges of the selected pattern;

creates a graph evolution rule, the rule indicating that any occurrence of the child pattern implies a corresponding occurrence of the pattern, the corresponding occurrence of the pattern being formed with the addition of the portion missing from the child pattern at a time indicated by the missing edge's temporal label.

9. The system of claim 8 , wherein the temporal label in the formed graph is absolute time and the missing edge's temporal label is relative time.

10. The system of claim 8 , wherein the temporal label of an initial edge of the pattern and child pattern is a relative time of zero.

11. The system of claim 10 , wherein the child pattern is missing one edge of the pattern, the missing edge has a temporal label with the highest value in the pattern.

12. The system of claim 8 , wherein the support of the pattern is a minimum possible number of mappings of a node of the pattern in the formed graph.

13. The system of claim 8 , wherein the graph evolution rule generator assigns a support to the graph evolution rule, the assigned support is equal to the support of the pattern.

14. The system of claim 8 , wherein the graph evolution rule generator assigns a confidence to the graph evolution rule, the assigned confidence is equal to a ratio of the support of the pattern to the support of the child pattern.

15. A non-transitory computer-readable medium tangibly storing thereon computer-executable process steps, the process steps comprising:

collecting multiple graphs corresponding to a network, the network evolving over time, each graph representing a snapshot reflecting a state of the network at a time the snapshot was taken;

forming one graph by merging the multiple graphs representing the multiple snapshots of the network, the formed graph comprising a set of nodes and a set of edges, each edge connecting two nodes from the set of nodes and having a temporal label;

mining the graph to identify multiple patterns, each pattern being a subgraph in the formed graph, each pattern having an associated support;

selecting a pattern from the identified patterns;

identifying a child pattern of the selected pattern, the child pattern of the pattern includes all but one of the edges of the pattern and the identified child pattern having a support that is at least equal to the support of the selected pattern in the formed graph and missing a portion of pattern, the missing portion of the pattern including at least one edge of the pattern wherein the missing edge has a temporal label that has a greatest value of the temporal labels assigned to edges of the selected pattern;

creating a graph evolution rule, the rule indicating that any occurrence of the child pattern implies a corresponding occurrence of the pattern, the corresponding occurrence of the pattern being formed with the addition of the portion missing from the child pattern at a time indicated by the missing edge's temporal label.

16. The medium of claim 15 , wherein the temporal label in the formed graph is absolute time and the missing edge's temporal label is relative time.

17. The medium of claim 15 , wherein the temporal label of an initial edge of the pattern and child pattern is a relative time of zero.

18. The medium of claim 17 , wherein the child pattern is missing one edge of the pattern, the missing edge has a temporal label with the highest value in the pattern.

19. The medium of claim 15 , wherein the support of the pattern is a minimum possible number of mappings of a node of the pattern in the formed graph.

20. The medium of claim 15 , the process steps further comprising: assigning a support to the graph evolution rule, the assigned support is equal to the support of the pattern.

21. The medium of claim 15 , the process steps further comprising: assigning a confidence to the graph evolution rule, the assigned confidence is equal to a ratio of the support of the pattern to the support of the child pattern.