Granted Patent B2

US 9,721,039 · App. 13/328,989 · Granted Aug 1, 2017

Abstract

Claims (108)

1. A computer-implemented method comprising:

receiving, by a computing device, a first request for a relationship visualization, wherein the request includes a date range, a user, and a target entity;

selecting, from a multipartite graph, a first set of relationship paths that each includes an entity node representing the user at one end and an entity node representing the target entity at the opposite end, wherein a relationship path includes one or more internal entity nodes that represent a person, an organization, or a document;

selecting, from the first set of relationship paths, a date-range entity node whose corresponding date range overlaps with the included date range;

selecting, from the first set of relationship paths, a first group of entity nodes that form a relationship path between the user and the target entity and that traverses the selected date-range entity node;

obtaining contextual information associated with the first group of entity nodes in the first set of relationship paths; and

providing a first relationship visualization that displays the contextual information from the first group of entity nodes in the first set of relationship paths to illustrate a relationship between the user and the target entity.

2. The method of claim 1 , wherein an entity node of the multipartite graph corresponds to an entity type selected from the group consisting of:

a person;

a document;

a project;

a topic;

an activity;

a date range;

a company;

an address; and

a phone number.

3. The method of claim 2 , wherein providing the first relationship visualization comprises generating a date-centric relationship visualization by:

determining a visualization position for an entity node, which involves:

determining a position along a first axis for the entity node based on an entity type for the entity node; and

determining a position along a second axis for the entity node based on a date associated with the entity node; and

generating a visualization that displays contextual information for the entity node at the corresponding visualization position.

4. The method of claim 1 , wherein selecting the first set of relationship paths comprises:

determining a weighted value for each entity node and each edge in the multipartite graph; and

selecting one or more shortest paths between the user's entity node and the target entity's entity node, which involves computing a path's length by:

for each edge in the path, adding an inverse of the edge's weighted value to the path's length; and

subtracting, from the path's length, a weighted value for each entity node in the path.

5. The method of claim 1 , wherein selecting the group of entity nodes comprises selecting, from the relationship paths, an entity node based on a corresponding significance score.

6. The method of claim 5 , further comprising determining a significance score for an entity node by:

computing an initial flow through the relationship paths from the user's entity node to the target entity's entity node;

determining a reduced flow associated with the entity node, which involves computing a flow through the relationship paths without traversing the entity node; and

assigning a significance score to the entity node based on a difference between the initial flow and the reduced flow.

7. The method of claim 1 , further comprising:

receiving a second request for a relationship visualization, wherein the second request indicates the target entity of a first entity type and a distal entity of a second entity type;

determining, from the multipartite graph, a second set of relationship paths coupling entity nodes for the target entity and the distal entity;

selecting, from the second set of relationship paths, a second group of entity nodes; and

providing a second relationship visualization, which displays contextual information from the second group of entity nodes to illustrate the relationship between the target entity and the distal entity.

8. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method, the method comprising:

receiving a first request for a relationship visualization, wherein the request includes a date range, a user, and a target entity;

selecting, from a multipartite graph, a first set of relationship paths that each includes an entity node representing the user at one end and an entity node representing the target entity at the opposite end, wherein a relationship path includes one or more internal entity nodes that represent a person, an organization, or a document;

selecting, from the first set of relationship paths, a date-range entity node whose corresponding date range overlaps with the included date range;

selecting, from the first set of relationship paths, a first group of entity nodes that form a relationship path between the user and the target entity and that traverses the selected date-range entity node;

obtaining contextual information associated with the first group of entity nodes in the first set of relationship paths; and

providing a first relationship visualization that displays the contextual information from the first group of entity nodes in the first set of relationship paths to illustrate the relationship between the user and the target entity.

9. The computer-readable storage medium of claim 8 , wherein an entity node of the multipartite graph corresponds to an entity type selected from the group consisting of:

a person;

a document;

a project;

a topic;

an activity;

a date range;

a company;

an address; and

a phone number.

10. The computer-readable storage medium of claim 9 , wherein providing the first relationship visualization comprises generating a date-centric relationship visualization by:

determining a visualization position for an entity node, which involves:

determining a position along a first axis for the entity node based on an entity type for the entity node; and

determining a position along a second axis for the entity node based on a date associated with the entity node; and

generating a visualization that displays contextual information for the entity node at the corresponding visualization position.

11. The computer-readable storage medium of claim 8 , wherein selecting the first set of relationship paths comprises:

determining a weighted value for each entity node and each edge in the multipartite graph; and

selecting one or more shortest paths between the user's entity node and the target entity's entity node, which involves computing a path's length by:

for each edge in the path, adding an inverse of the edge's weighted value to the path's length; and

subtracting, from the path's length, a weighted value for each entity node in the path.

12. The computer-readable storage medium of claim 8 , wherein selecting the group of entity nodes comprises selecting, from the relationship paths, an entity node based on a corresponding significance score.

13. The computer-readable storage medium of claim 12 , further comprising determining a significance score for an entity node by:

computing an initial flow through the relationship paths from the user's entity node to the target entity's entity node;

determining a reduced flow associated with the entity node, which involves computing a flow through the relationship paths without traversing the entity node; and

assigning a significance score to the entity node based on a difference between the initial flow and the reduced flow.

14. The computer-readable storage medium of claim 8 , further comprising:

receiving a second request for a relationship visualization, wherein the second request indicates the target entity of a first entity type and a distal entity of a second entity type;

determining, from the multipartite graph, a second set of relationship paths coupling entity nodes for the target entity and the distal entity;

selecting, from the second set of relationship paths, a second group of entity nodes; and

providing a second relationship visualization, which displays contextual information from the second group of entity nodes to illustrate the relationship between the target entity and the distal entity.

15. An apparatus comprising:

a processor;

a memory;

a receiving module to receive a first request for a relationship visualization, wherein the request includes a date range, a user and a target entity;

an analysis module to select, from a multipartite graph, a first set of relationship paths that each includes an entity node representing the user at one end and an entity node representing the target entity at the opposite end, wherein a relationship path includes one or more internal entity nodes that represent a person, an organization or a document;

a date-range selection module to select, from the first set of relationship paths, a date-range entity node whose corresponding date range overlaps with the included date range;

a node-selecting module to select, from the first set of relationship paths, a first group of entity nodes that form a relationship path between the user and the target entity and that traverses the selected date-range entity node;

a contextual information obtaining module to obtain contextual information associated with the first group of entity nodes in the first set of relationship paths; and

a display module to provide a first relationship visualization which displays contextual information from the first group of entity nodes in the first set of relationship paths to illustrate the relationship between the user and the target entity.

16. The apparatus of claim 15 , wherein an entity node of the multipartite graph corresponds to an entity type selected from the group consisting of:

a person;

a document;

a project;

a topic;

an activity;

a date range;

a company;

an address; and

a phone number.

17. The apparatus of claim 16 , wherein the display module is further configured to generate a date-centric relationship visualization by:

determining a visualization position for an entity node, which involves:

determining a position along a first axis for the entity node based on an entity type for the entity node; and

determining a position along a second axis for the entity node based on a date associated with the entity node; and

generating a visualization that displays contextual information for the entity node at the corresponding visualization position.

18. The apparatus of claim 15 , wherein while selecting the first set of relationship paths, the analysis module is further configured to:

determine a weighted value for each entity node and each edge in the multipartite graph; and

select one or more shortest paths between the user's entity node and the target entity's entity node, which involves computing a path's length by:

for each edge in the path, adding an inverse of the edge's weighted value to the path's length; and

subtracting, from the path's length, a weighted value for each entity node in the path.

19. The apparatus of claim 15 , wherein while selecting the group of entity nodes, the node-selecting module is further configured to select, from the relationship paths, an entity node based on a corresponding significance score.

20. The apparatus of claim 19 , wherein the node-selecting module is further configured to determine a significance score for an entity node by:

computing an initial flow through the relationship paths from the user's entity node to the target entity's entity node;

determining a reduced flow associated with the entity node, which involves computing a flow through the relationship paths without traversing the entity node; and

assigning a significance score to the entity node based on a difference between the initial flow and the reduced flow.

Assignments (9)