Method to predict edges in a non-cumulative graph
View Patent ↗To predict edges in a non-cumulative graph, based on a sequence of non-cumulative previous occurrences of the graph, the sequence of non-cumulative previous occurrences of the graph is obtained, and topological properties of each of the previous occurrences of the graph are extracted. Topological similarities between each of the previous occurrences of the graph are computed based on the topological properties. The edges of the graph are predicted by computing a score for each possible edge of the graph, based upon the topological similarities.
1. A method for predicting edges of a graph, based on a sequence of non-cumulative previous occurrences of said graph, said method comprising the steps of:
obtaining said sequence of non-cumulative previous occurrences of said graph, wherein obtaining said sequence of non-cumulative previous occurrences is carried out by a module executing on a hardware processor;
extracting topological properties of each of said previous occurrences of said graph, wherein extracting topological properties of each of said previous occurrences is carried out by a module executing on a hardware processor;
computing topological similarities between each of said previous occurrences of said graph, based on said topological properties, wherein computing topological similarities between each of said previous occurrences is carried out by a module executing on a hardware processor; and
predicting said edges of a future instance of said graph by computing a score for each possible edge of said graph, based upon said topological similarities, wherein the score comprises, for each edge, a probability of existing in the future instance and wherein each of said scores is weighted equally, and wherein predicting said edges of said graph by computing a score for each possible edge is carried out by a module executing on a hardware processor.
2. The method of claim 1 , wherein said probabilities for said possible edges indicate importance of a given one of said edges to the integrity of topology of a given occurrence of said graph.
3. The method of claim 2 , wherein said given occurrence of said graph comprises one of said previous occurrences of said graph.
4. The method of claim 2 , wherein said given occurrence of said graph comprises a predicted occurrence of said graph based upon said predicted edges.
5. The method of claim 1 , wherein each of said possible edges has a corresponding score and wherein at least some of said scores are weighted unequally.
6. The method of claim 1 , wherein said step of extracting topological properties of each of said previous occurrences of said graph comprises:
building a matrix corresponding to each of said previous occurrences of said graph;
finding a set of paths, if any, between every node in each of said matrices corresponding to each of said previous occurrences of said graph.