Network graph evolution rule generation

Abstract

A network's evolution is characterized by graph evolution rules. A graph that represents an evolutionary network is mined to identify evolutional patterns of the network, and graph evolution rules are generated using identified evolutional patterns. The generated graph evolution rules represent the evolutional patterns of the network.

1 - 24 . (canceled) 
     
     
         25 . 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;   forming, by the at least one processing unit, one graph by merging the multiple graphs representing the multiple snapshots of the network;   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, by the at least one processing unit, a pattern from the identified patterns;   identifying, by the at least one processing unit, a child pattern of the selected pattern, the identified child pattern having a support that is at least equal to the support 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 selected pattern; and   assigning, by the at least one processing unit, a support to the graph evolution rule, the assigned support being equal to the support of the selected pattern.   
     
     
         26 . The method of  claim 25 , wherein the formed graph by merging the multiple graphs 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. 
     
     
         27 . The method of  claim 26 , wherein the child pattern missing a portion of the selected pattern, the missing portion of the selected pattern including at least one edge of the selected pattern. 
     
     
         28 . The method of  claim 27 , wherein the corresponding occurrence of the selected pattern being formed with the addition of the portion missing from the child pattern at a time indicated by a missing edge's temporal label. 
     
     
         29 . The method of  claim 26 , wherein the temporal label in the formed graph is absolute time and the missing edge's temporal label is relative time. 
     
     
         30 . The method of  claim 26 , wherein the temporal label of an initial edge of the selected pattern and the child pattern is a relative time of zero. 
     
     
         31 . The method of  claim 27 , wherein the at least one edge of the selected pattern of the missing portion of the selected pattern has a temporal label with the highest value in the selected pattern. 
     
     
         32 . The method of  claim 25 , wherein the support of the selected pattern is a minimum possible number of mappings of a node of the selected pattern in the formed graph. 
     
     
         33 . The method of  claim 25 , further comprising:
 assigning, by the at least one processing unit, a confidence to the graph evolution rule, the assigned confidence is equal to a ratio of the support of the selected pattern to the support of the child pattern.   
     
     
         34 . The method of  claim 26 , identifying the child pattern of the selected pattern further comprising:
 identifying, by the at least one processing unit, the child pattern of the selected pattern that includes all but one of the edges of the selected pattern, the missing edge having a temporal label that has the greatest value of the temporal labels assigned to edges of the selected pattern.   
     
     
         35 . 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; 
 forms one graph by merging the multiple graphs representing the multiple snapshots of the network; 
 mines the formed graph to identify multiple patterns, each pattern being a subgraph in the formed graph, each pattern having an associated support; 
 selects a pattern from the identified patterns; 
 identifies a child pattern of the selected pattern, the identified child pattern having a support that is at least equal to the support 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 selected pattern; and 
 assigns a support to the graph evolution rule, the assigned support being equal to the support of the selected pattern. 
   
     
     
         36 . The system of  claim 35 , wherein the formed graph by merging the multiple graphs 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. 
     
     
         37 . The system of  claim 36 , wherein the child pattern missing a portion of the selected pattern, the missing portion of the selected pattern including at least one edge of the selected pattern. 
     
     
         38 . The system of  claim 37 , wherein the corresponding occurrence of the selected pattern being formed with the addition of the portion missing from the child pattern at a time indicated by a missing edge's temporal label. 
     
     
         39 . The system of  claim 36 , wherein the temporal label in the formed graph is absolute time and the missing edge's temporal label is relative time. 
     
     
         40 . The system of  claim 36 , wherein the temporal label of an initial edge of the selected pattern and the child pattern is a relative time of zero. 
     
     
         41 . The system of  claim 37 , wherein the at least one edge of the selected pattern of the missing portion of the selected pattern has a temporal label with the highest value in the selected pattern. 
     
     
         42 . The system of  claim 35 , wherein the support of the selected pattern is a minimum possible number of mappings of a node of the selected pattern in the formed graph. 
     
     
         43 . The system of  claim 35 , 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 selected pattern to the support of the child pattern. 
     
     
         44 . The system of  claim 36 , the graph evolution rule generator identifies the child pattern of the selected pattern by identifying the child pattern of the selected pattern that includes all but one of the edges of the selected pattern, the missing edge having a temporal label that has the greatest value of the temporal labels assigned to edges of the selected pattern. 
     
     
         45 . 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 overtime, each graph representing a snapshot reflecting a state of the network;   forming one graph by merging the multiple graphs representing the multiple snapshots of the network;   mining 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 a child pattern of the selected pattern, the identified child pattern having a support that is at least equal to the support 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 selected pattern; and   assigning a support to the graph evolution rule, the assigned support being equal to the support of the selected pattern.