Graph visualization system based on gravitational forces due to path distance and betweenness centrality

• US 9,892,533 B1
• Filed: 12/16/2015
• Issued: 02/13/2018
• Est. Priority Date: 10/01/2015
• Status: Active Grant

• Current Assignee: HRL Laboratories LLC (The Boeing Co.)
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Tressler, Eric P., Jurgens, David A.
• Primary Examiner(s): Lett, Thomas
• Application Number:
  US14/972,067
• Time in Patent Office: 790 Days
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

The present invention relates to a system for graph visualization. The system includes a display and one or more processors with a memory. The processors perform several operations, including receiving as an input a graph G=(V,E), where V is a set of vertices and E is a set of edges between the vertices. The vertices are then randomly distributed through a unit square. The vertices are then arranged to generate an aesthetically pleasing graph, which is displayed on the display.

Claims

1. A system for graph visualization, the system comprising:

one or more processors and a memory, the memory having, executable instructions encoded on a non-transitory computer readable medium, such that upon execution of the instructions, the one or more processors performs operations of;

receiving as an input a graph G=(V,E), where V is a set of vertices and E is a set of edges between the vertices;

distributing vertices through a unit square;

arranging the vertices to generate a graph layout, where arrangement of the vertices reflects a betweenness centrality; and

displaying the graph layout on a display.

2. The system as set forth in claim 1, wherein arranging the vertices further comprises an operation of iteratively positioning two vertices v and v′

at distance GB(v, v′

);

=d(v,v′

)+g(v)+g(V′

) from each other, where d(v,v′

) is a path distance between vertices v and v′

, and g(v) is the betweenness centrality of v.

3. The system as set forth in claim 2, wherein in distributing vertices through a unit square, the vertices are randomly distributed.

4. The system as set forth in claim 3, wherein each vertice represents a user on a social network and each edge represents a relationship between the users.

5. The system as set forth in claim 1, wherein in distributing vertices through a unit square, the vertices are randomly distributed.

6. The system as set forth in claim 1, wherein arranging the vertices, the vertices are arranged using betweenness centrality in a force directed graph based on gravitational forces.

7. The system as set forth in claim 6, wherein arranging the vertices further comprises an operation of iteratively positioning two vertices v and t? at distance GB(v,v′

);

=d(v,v′

)+g(v)+g(v′

) from each other, where a mass of a vertex v is g(v) and a distance between v and v′

is a Euclidean distance r between them, minus GB(v,v′

) such that gravitational force between the two vertices is defined as

8. The system as set forth in claim 1, wherein each vertice represents a user on a social network and each edge represents a relationship between the users.

9. A method for graph visualization, the method comprising an act of:

causing one or more processors to execute instructions encoded on a non-transitory computer-readable medium, such that upon execution, the one or more processors perform operations of;

receiving as an input a graph G(V,E) where V is a set of vertices and E is a set of edges between the vertices;

distributing vertices through a unit square;

arranging the vertices to generate a graph layout, where arrangement of the vertices reflects a betweenness centrality; and

displaying the graph layout on a display.

10. The method as set forth in claim 9, wherein arranging the vertices further comprises an operation of iteratively positioning two vertices v and v′

at distance GB(v, v′

);

=d(v,v′

)+g(v)+g(v′

) from each other, where d(v,v′

) is a path distance between vertices v and v′

, and g(v) is the betweenness centrality of v.

11. The method as set forth in claim 10, wherein in distributing vertices through a unit square, the vertices are randomly distributed.

12. The method as set forth in claim 11, wherein each vertice represents a user on a social network and each edge represents a relationship between the users.

13. The method as set forth in claim 9, wherein in distributing vertices through a unit square, the vertices are randomly distributed.

14. The method as set forth in claim 9, wherein arranging the vertices, the vertices are arranged using betweenness centrality in a force directed graph based on gravitational forces.

15. The method as set forth in claim 14, wherein arranging the vertices further comprises art operation of iteratively positioning two vertices v and v′

and at distance GB(v,v′

);

=d(v, v′

)+g(v)+g(v′

) from each other, where a mass of a vertex v is g(v) and a distance between v and v′

is a Euclidean distance r between them, minus GB(v,v′

), such that gravitational force between the two vertices is defined as;

16. The method as set forth in claim 9, wherein each vertice represents a user on a social network and each edge represents a relationship between the users.

17. A computer program product for graph visualization, the computer program product comprising:

a non-transitory computer-readable medium having executable instructions encoded thereon, such that upon execution of the instructions by one or more processors, the one or more processors perform operations of;

receiving as an input a graph G=(V,E), where V is a set of vertices and E is a set of edges between the vertices;

distributing vertices through a unit square;

arranging the vertices to generate a graph, layout, where arrangement of the vertices reflects a betweenness centrality; and

displaying the graph layout on a display.

18. The computer program product as set forth in claim 17, wherein arranging the vertices further comprises an operation of iteratively positioning two vertices v and v′

at distance GB(v,v′

);

=d(v,v′

)+g(v)+g(v′

) from each other, where d (v,v′

) is a path distance between vertices v and v′

, and g(v) is the betweenness centrality of v.

19. The computer program product as set forth in claim 18, wherein in distributing vertices through a unit square, the vertices are randomly distributed.

20. The computer program product as set forth in claim 19, wherein each vertice represents a user on a social network and each edge represents a relationship between the users.

21. The computer program product as set forth in claim 17, wherein in distributing vertices through a unit square, the vertices are randomly distributed.

22. The computer program product as set forth in claim 17, wherein arranging the vertices, the vertices are arranged using betweenness centrality in a force directed graph based on gravitational forces.

23. The computer program product as set forth in claim 22, wherein arranging the vertices further comprises an operation of iteratively positioning two vertices v and v′

at distance GB(v,v′

);

=d(v,v′

)+g(v)+g(v′

) from each other, where a mass of a vertex v is g(v) and a distance between v and v′

is a Euclidean distance r between them, minus GB(v,v′

), such that gravitational force between the two vertices is defined as;

24. The computer program product as set forth in claim 17, wherein each vertice represents a user on a social network and each edge represents a relationship between the users.