Systems and methods for discovering temporal patterns in time variant bipartite graphs

Patent metadata

Field	Value
Publication number	US-9760655-B2
Application number	US-201314016815-A
Country	US
Kind code	B2
Filing date	Sep 3, 2013
Priority date	Sep 3, 2013
Publication date	Sep 12, 2017
Grant date	Sep 12, 2017

Abstract

Systems and methods for identifying entities sharing a temporal pattern using bipartite graphs are described. In one embodiment, a method includes identifying a temporal pattern in a sequence of bipartite graphs for a sequence of records involving two entity types, where records of the sequence of bipartite graphs vary according to time. An embodiment may color code the edges between entity types in the sequence of bipartite graphs according to the at least one temporal pattern identified (e.g., increasing sales between a business representative and a customer). An embodiment may therefore identify a time-based relationship between at least two entities according to the coded edges. Given the identification of entities having a time-based relationships, groups of these entities may be identified and trends may be derived therefrom (e.g., increasing sales for business units of a particular geographic region).

First claim

What is claimed is:

1. A method of identifying entities sharing a temporal pattern using bipartite graphs, said method comprising:
utilizing at least one processor to execute computer code configured to perform the steps of:
accessing a sequence of records involving a plurality of entities, each of the entities belonging to one of two entity types;
creating a sequence of bipartite graphs for the sequence of records, wherein each of the bipartite graphs contained within the sequence of bipartite graphs comprises a bipartite graph corresponding to a relationship between at least two of the plurality of entities at a time period as compared to a comparison metric, wherein the time period of one bipartite graph is different than the time period of the other bipartite graphs in the sequence, based on the sequence of records, wherein the relationship is denoted by coded edges between the at least two of the plurality of entities; and
identifying at least one temporal pattern in the sequence of bipartite graphs for at least two of the plurality of entities, wherein the identifying at least one temporal pattern comprises identifying the coded edges having a predetermined pattern, grouping the predetermined patterns into groups of patterns, each group corresponding to patterns of a predetermined length, and assigning each of the coded edges to one of the groups based upon the predetermined pattern of the coded edges;
wherein the identifying at least one temporal pattern comprises subdividing each group subgroups, assigning each of the coded edges to one of the subgroups, discarding subgroups having a number of coded edges less than a predetermined threshold, and iteratively subdividing, assigning, and discarding until a predetermined number of subgroups remains.

2. The method of claim 1 , comprising coding edges between entities in the sequence of bipartite graphs.

3. The method of claim 1 , wherein said identifying comprises identifying a time-based relationship between at least two of the entities in the sequence of bipartite graphs.

4. The method of claim 3 , wherein said identifying of at least one temporal pattern comprises identifying at least one trend reflected by a plurality of time-based relationships between entities.

5. The method of claim 3 , wherein:
the at least two entities having the time-based relationship comprise nodes belonging to different entity types; and
the time-based relationship comprises a change in a quantity shared by the nodes belonging to different entity types.

6. The method of claim 5 , wherein said identifying of the time-based relationship comprises providing an indication distinguishing the time-based relationship comprising the change in quantity from at least one other time-based relationship between nodes.

7. The method of claim 1 , wherein said identifying comprises:
identifying a plurality of time-based relationships between a plurality of entities in the sequence of bipartite graphs according to the at least one temporal pattern; and
identifying at least one trend reflected by the plurality of time-based relationships.

8. The method of claim 7 , wherein said identifying of at least one trend comprises identifying via using entity attributes.

9. The method of claim 8 , wherein the entity attributes are selected from the group of attributes consisting of: geographic region, business unit, product type, and keyword.

10. The method of claim 9 , wherein:
said entity attributes comprise a keyword; and
said method comprises linking a keyword to at least one text document containing the keyword.

11. A computer program product for identifying entities sharing a temporal pattern using bipartite graphs, said computer program product comprising:
a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising:
computer readable program code configured to access a sequence of records involving a plurality of entities, each of the entities belonging to one of two entity types;
computer readable program code configured to create a sequence of bipartite graphs for the sequence of records, wherein each of the bipartite graphs contained within the sequence of bipartite graphs comprises a bipartite graph corresponding to a relationship between at least two of the plurality of entities at a time period as compared to a comparison metric, wherein the time period of one bipartite graph is different than the time period of the other bipartite graphs in the sequence, based on the sequence of records, wherein the relationship is denoted by coded edges between the at least two of the plurality of entities; and
computer readable program code configured to identify at least one temporal pattern in the sequence of bipartite graphs for at least two plurality of the entities, wherein the identifying at least one temporal pattern comprises identifying the coded edges having a predetermined pattern, grouping the predetermined patterns into groups of patterns, each group corresponding to patterns of a predetermined length, and assigning each of the coded edges to one of the groups based upon the predetermined pattern of the coded edges;
wherein the identifying at least one temporal pattern comprises subdividing each group subgroups, assigning each of the coded edges to one of the subgroups, discarding subgroups having a number of coded edges less than a predetermined threshold, and iteratively subdividing, assigning, and discarding until a predetermined number of subgroups remains.

12. The computer program product of claim 11 , wherein the computer readable program code comprises computer readable program code configured to code edges between entities in the sequence of bipartite graphs.

13. The computer program product of claim 11 , wherein the computer readable program code comprises computer readable program code configured to identify a time-based relationship between at least two of the entities in the sequence of bipartite graphs.

14. The computer program product of claim 13 , wherein the computer readable program code comprises computer readable program code configured to identify at least one trend reflected by a plurality of time-based relationships between entities.

15. The computer program product of claim 13 , wherein:
the at least two entities having the time-based relationship comprise nodes belonging to different entity types; and
the time-based relationship comprises a change in a quantity shared by the nodes belonging to different entity types.

16. The computer program product of claim 15 , wherein identifying the time-based relationship comprises providing an indication distinguishing the time-based relationship comprising the change in quantity from at least one other time-based relationship between nodes.

17. The computer program product of claim 11 , wherein the computer readable program code comprises computer readable program code configured to:
identify a plurality of time-based relationships between a plurality of entities in the sequence of bipartite graphs according to the at least one temporal pattern; and
identify at least one trend reflected by the plurality of time-based relationships.

18. The computer program product of claim 17 , wherein the at least one trend is identified using entity attributes.

19. The computer program product of claim 18 , wherein the entity attributes are selected from the group of attributes consisting of: geographic region, business unit, product type, and keyword.

20.

Assignees

• IBM

Inventors

• Agarwal Manoj Kumar
• Negi Sumit
• Subramaniam L Venkata
• Vogel Oliver Markus

Classifications

• G06F17/30268

  Physics · mapped topic

• G06F17/30265

  Physics · mapped topic

• G06F17/30958 Primary

  Physics · mapped topic

• G06F17/30864

  Physics · mapped topic

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title