GENERATING A RELATIONSHIP VISUALIZATION FOR NONHOMOGENEOUS ENTITIES

• US 20130155068A1
• Filed: 12/16/2011
• Published: 06/20/2013
• 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
• Granted Patent: US 9,721,039 B2
• Time in Patent Office: Days
• US Class Current: 345/440
• 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 corresponding 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 a first request for a relationship visualization, wherein the request indicates a user and a non-person entity;

determining, from a multipartite graph, a first set of relationship paths coupling entity nodes for the user and the non-person entity, wherein a relationship path includes one or more entity nodes indicating contextual information for a relationship between the user and the non-person entity;

selecting, from the first set of relationship paths, a first group of entity nodes to represent the relationship between the user and the non-person entity; and

providing a first relationship visualization, which displays contextual information from the first group of entity nodes to illustrate the relationship between the user and the non-person 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 the request further indicates a date range for the relationship visualization;

and

wherein determining a relationship path comprises;

selecting a date-range entity node whose corresponding date range overlaps with the indicated date range; and

determining, from the multipartite graph, a relationship path that traverses the selected date-range entity node.

4. The method of claim 3, wherein providing the 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.

5. The method of claim 1, wherein determining a 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 non-person 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.

6. 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.

7. The method of claim 6, 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 non-person 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.

8. The method of claim 1, further comprising:

receiving a second request for a relationship visualization, wherein the second request indicates the non-person 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 non-person 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 non-person entity and the distal entity.

9. 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 indicates a user and a non-person entity;

determining, from a multipartite graph, a first set of relationship paths coupling entity nodes for the user and the non-person entity, wherein a relationship path includes one or more entity nodes indicating contextual information for a relationship between the user and the non-person entity;

selecting, from the first set of relationship paths, a first group of entity nodes to represent the relationship between the user and the non-person entity; and

providing a first relationship visualization, which displays contextual information from the first group of entity nodes to illustrate the relationship between the user and the non-person entity.

10. The computer-readable storage medium of claim 9, 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.

11. The computer-readable storage medium of claim 10, wherein the request further indicates a date range for the relationship visualization;

and

wherein determining a relationship path comprises;

selecting a date-range entity node whose corresponding date range overlaps with the indicated date range; and

determining, from the multipartite graph, a relationship path that traverses the selected date-range entity node.

12. The computer-readable storage medium of claim 11, wherein providing the 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.

13. The computer-readable storage medium of claim 9, wherein determining a 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 non-person 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.

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

15. The computer-readable storage medium of claim 14, 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 non-person 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.

16. The computer-readable storage medium of claim 9, further comprising:

receiving a second request for a relationship visualization, wherein the second request indicates the non-person 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 non-person 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 non-person entity and the distal entity.

17. An apparatus comprising:

a receiving module to receive a first request for a relationship visualization, wherein the request indicates a user and a non-person entity;

an analysis module to determine, from a multipartite graph, a first set of relationship paths coupling entity nodes for the user and the non-person entity, wherein a relationship path includes one or more entity nodes indicating contextual information for a relationship between the user and the non-person entity;

a node-selecting module to select, from the first set of relationship paths, a first group of entity nodes to represent the relationship between the user and the non-person entity; and

a display module to provide a first relationship visualization, which displays contextual information from the first group of entity nodes to illustrate the relationship between the user and the non-person entity.

18. The apparatus of claim 17, 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.

19. The apparatus of claim 18, wherein the request further indicates a date range for the relationship visualization;

and

wherein while determining a relationship path, the analysis module is further configured to;

select a date-range entity node whose corresponding date range overlaps with the indicated date range; and

determine, from the multipartite graph, a relationship path that traverses the selected date-range entity node.

20. The apparatus of claim 19, 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.

21. The apparatus of claim 17, wherein while determining a 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 non-person 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.

22. The apparatus of claim 17, 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.

23. The apparatus of claim 22, 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 non-person 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.