Generating a relationship visualization for nonhomogeneous entities

• US 9,721,039 B2
• Filed: 12/16/2011
• Issued: 08/01/2017
• Est. Priority Date: 12/16/2011
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Bier, Eric A., Brdiczka, Oliver
• Primary Examiner(s): Faulk, Devona
• Assistant Examiner(s): BEARD, CHARLES LLOYD
• Application Number:
  US13/328,989
• Publication Number:
  US 20130155068A1
• Time in Patent Office: 2,055 Days
• CPC Class Codes: G06F 16/901 Indexing; Data structures therefor; Storage structures for retrieval from the web G06F16/951
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

A relationship visualization system displays contextual information for a relationship between two entities of a document management system, such as for a user and a document. The system can receive a request for a relationship visualization from a user, such that the request indicates the user and a document. Then, the system determines, from a multipartite graph, a set of relationship paths coupling entity nodes that correspond to the user and the document. A relationship path can include one or more entity nodes indicating contextual information for the relationship between the user and the document. Then, the system selects a first group of entity nodes from the set of relationship paths to represent the relationship between the user and the document. The system then provides a relationship visualization that displays contextual information from the first group of entity nodes to illustrate the relationship between the user and the document.

Claims

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.