BACKGROUND

[0001] Bipartite graphs are used to model and evaluate reiationships between classes of entities. Bipartite graphs can be represented by structures such as adjacency matrices. Bipartite graphs can also be visually represented. Entities in a bipartite graph are often visually displayed by a representation of nodes linked by edges. In such a representation, entities are represented by nodes. Edges are used to join the related nodes together to indicate relationships between nodes.

BRIEF DESCRIPTION OF THE DRAWINGS

[0002] The accompanying drawings illustrate various examples and are a part of the specification. The illustrated examples are examples and do not limit the scope of the claims. Throughout the drawings, identical reference numbers designate similar, but not necessarily identical elements.

[0003] FIG. 1 is a block diagram illustrating a system for displaying a bipartite graph, according to various examples;

[0004] FIG. 2 is a flow diagram of a method of displaying a bipartite graph representation, according to various examples;

[0005] FIG. 3 is a block diagram of a system for displaying a bipartite graph according to various examples;

[0006] FIG. 4 is a graphical representation of a bipartite graph produced based on a technique executed by the system of FIG. 1 , according to various examples; [0007] FIG. 5 is a flow diagram of a method for displaying a bipartite graph according to various examples;

[0008] FIG. 6 is a flow diagram depicting steps of optimizing the visual appearance of edges of a graph to be displayed according to various examples; and,

[0009] FIG. 7 is a diagram of a user interface system according to various examples.

[0010] The same part numbers designate the same or similar parts throughout the figures.

DETAILED DESCRIPTION

[001 1] . A bipartite graph is a graph that does not contain any odd length cycle. Trees and grid graphs are examples of bipartite graphs. The nodes in a bipartite graph can be divided into two disjoint sets (for example U and V) such that every edge connects a node in set U to one in set V.

[0012] One problem with bipartite graphs and their representations is that there are often a high number of nodes to be represented. As the number of nodes increases, displaying them for meaningful viewing and analysis becomes increasingly difficult.

[0013] Databases have commonly been used to store and classify information. Keyword searches and other types of data mining can be used to identify themes and/or differences in data. However, due to the quantity and diversity of data that is often stored and the number and variety of variables, it can be difficult for a human to efficiently obtain information on the data. For example, data in a database may fit into a number of distinct classes or trends based on attributes of the data. However, looking at the raw data alone it typically is not possible for a human to perceive such classifications or trends. [0014] Bipartite graphs may be used to extract information and trends from databases. In certain systems, bipartite graphs are used to obtain and/or optimize solutions to problems. One difficulty with determining optimized solutions to problems is that as the number of nodes and their relationships that are to be optimized increases, providing a human understandable representation of the entities and their relationships becomes more difficult and time consuming.

[0015] In certain systems, polynomial algorithms are used for efficiently solving fundamental combinatorial optimization problems represented by bipartite graphs such as matching and assignment problems. One problem with using polynomial algorithms is that although the algorithms can handle large graphs very efficiently, an automated solution may not take into account ail factors associated with the optimization problem. For example, an assignment problem may include finding a minimum/maximum matching in weighted bipartite graphs, where each edge has an associated value. Computing these values automatically can be problematic in that they can include estimates or other values that represent relations that are hard to quantify like intuition, personal relations, psychological fit, etc. As a result, an automatic assignment that solely depends on these estimates without any human monitoring may produce a solution that is unusable yet is formally optimal from the system's perspective.

[0018] One problem with using bipartite graphs to represent entities and their relations is that producing a visual representation that effectively communicates the underlying bipartite graph is a challenging task. Bipartite graphs commonly include edge crossings and node occlusion and are generally non-planar. One problem with using naive drawings to represent a bipartite graph is that significant visual clutter is induced by the large amount of edge crossings and node-edge overlaps.

[0017] Bipartite graphs may be visually represented by nodes positioned on the surface of a sphere. A typical problem with such a representation is that determining where on the sphere to position nodes is a lengthy and processor- intensive activity. A further problem with such a representation is that visual clutter can often remain.

[0018] Accordingly, various examples described herein were developed to provide methods, computer-readable media, and systems for displaying bipartite graphs. One method for displaying a bipartite graph includes positioning each of a plurality of nodes within a display region according to simulated forces acting on each node. The simulated forces include: a repulsive force between nodes inversely proportional to the distance between the respective nodes; an attractive force between each node and a center of gravity position of the display region; and, a spring force between connected nodes. Each node represents a node of a bipartite graph and a connection between nodes corresponds to an edge of the bipartite graph. The positioned nodes are displayed on an electronic display. Edges between connected ones of the nodes are displayed on the electronic display.

[0019] Examples described herein may enable visual representations to be generated automatically that effectively communicate information on a bipartite graph and allow human evaluation. The representation may not be restricted to a particular form and can be based upon different geometrical shapes.

[0020] In the representation, visual artefacts such as clutter can be minimized. Placement of nodes can be optimized for visual representation such that nodes that share many neighbours are positioned so as to reside substantially next to each other. Placement of nodes can be optimized for visual representation such that unrelated nodes (i.e., nodes with different neighbours) are positioned further away from each other than related nodes.

[0021] Placement of nodes and edges can be optimized for visual representation such that visual clutter of the edges is minimized by causing bundling together of edges that are in similar locations. Edges can be transformed from linear representations to curves to further reduce visual clutter. [0022] Representations of large and complex bipartite graphs can be automatically and quickly produced,

[0023] In the representations, related nodes may be clustered as a result of the optimization, even though the bipartite graph itself contains no cluster information.

[0024] FIG. 1 is a block diagram illustrating a system for displaying a bipartite graph according to various examples. FIG. 1 includes particular components, modules, etc. according to various examples. However, in different examples, more, fewer, and/or other components, modules, arrangements of components/modules, etc. may be used according to the teachings described herein. In addition, various components, modules, etc. described herein may be implemented as one or more electronic circuits, software modules, hardware modules, special purpose hardware (e.g., application specific hardware, application specific integrated circuits (ASICs), embedded controllers, hardwired circuitry, Field Programmable Gate Arrays (FPGA), etc.), or some combination of these.

[0025] As is shown in FIG. 1. the system 100 includes a computing device 120 and a display 130. In one example, the computing device 120 is one of a desktop computer, an all-in-one computing device, a notebook computer, a server computer, a handheld computing device, a smartphone, a tablet computer, a print server, a printer, a self-service print kiosk, a subcomponent of a system, machine or device. In one example, the computing device 120 includes a processor 121 and a memory 122. In one example, the processor 121 is a central processing unit (CPU) that executes commands stored in a memory, !n another example, the processor 121 is a semiconductor-based microprocessor that executes commands stored in the memory.

[0028] In one example, the processor 121 executes computer program code to execute a bipartite graph analyser 150 to display a plurality of nodes on an electronic display 130, each node representing a node of the bipartite graph. In one example, the processor 121 further executes computer program code to execute the bipartite graph analyser 150 to display, on the electronic display, an edge connecting certain of the nodes, the edge corresponding to an edge of the bipartite graph and indicating a relationship between the connected nodes.

[0027] In one example, the processor 121 executes computer program code to execute the bipartite graph analyser 150 to arrange the plurality of nodes within a display region on the electronic display 130 according to simulated forces acting on each node, the simulated forces including: a repulsive force between nodes inversely proportional to the distance therebetween; an attractive force between each node and a center of gravity position of the display region; and, a spring force between connected nodes. Node placement is discussed further with respect to FIG. 5 below.

[0028] In one example, the simulated forces are computed representations of physical forces that may be encountered if the nodes and edges of the bipartite graph were physical entities having a physical form and, in the case of edges, spring resistance.

[0029] FIG. 2 is a flow diagram of a method of displaying a bipartite graph according to various examples. The bipartite graph has a plurality of nodes, each node being linked by an edge to at least one other node to represent the relationship between nodes.

[0030] Starting at step 210, each of a plurality of nodes is positioned within a display region according to simulated forces acting on each node. In one example, the simulated forces include: a repulsive force between nodes inversely proportional to the distance between the respective nodes; an attractive force between each node and a center of gravity position of the display region: and, a spring force between connected nodes. In one example, each node represents a node of a bipartite graph and a connection between nodes corresponds to an edge of the bipartite graph. [0031] Ai step 220, the nodes as positioned within the display region are displayed on an electronic display.

[0032] At step 230, edges between connected ones of the nodes are displayed on the electronic display.

[0033] FIG. 3 is a block diagram illustrating a system for displaying a bipartite graph, according to various examples. FIG. 3 includes particular components, modules, etc. according to various examples. However, in different examples, more, fewer, and/or other components, modules, arrangements of components/modules, etc. may be used according to the teachings described herein. In addition, various components, modules, etc. described herein may be implemented as one or more electronic circuits, software modules, hardware modules, special purpose hardware (e.g., application specific hardware, application specific integrated circuits (ASICs), embedded controllers, hardwired circuitry, Field Programmable Gate Arrays (FPGA), etc.), or some combination of these.

[0034] As is shown in FIG. 3, the system 100 includes a computing device 120 and a display 130. In one example, the computing device 120 is one of a desktop computer, an ail-in-one computing device, a notebook computer, a server computer, a handheld computing device, a smartphone, a tablet computer, a print server, a printer, a self-service print kiosk, a subcomponent of a system, machine or device. In one example, the computing device 120 includes a processor 121 , a memory 122, an input unit 123 and an output port 124. In one example, the processor 121 is a central processing unit (CPU) that executes commands stored in the memory. In another example, the processor 121 is a semiconductor-based microprocessor that executes commands stored in the memory. In one example, the memory 122 includes any one of or a combination of volatile memory elements (e.g., RAM modules) and non-volatile memory elements (e.g., hard disk, ROM modules, etc.). In one example, the input unit 123 includes one or more of a user input device, an I/O port for connection to a data storage device, and/or a network port for communicating with remote systems over a network.

[0035] In one example, the processor 121 executes computer program code from the memory 122 to execute a bipartite graph analyser 150 to determine an optimal representation of the bipartite graph and output the representation to the display 130.

[0036] In one example, the network port of the input unit 123 is connectable to a data communications network to receive a bipartite graph. The data communications network may be wired, wireless or a combination of wired and wireless networks. In another example, the I/O port provides a connection between the computing device 120 and a data repository which may be wired or wireless. In one example, the connection is a bus, USB, IEEE 1394 type, serial, parallel, IEEE 802.1 1 type, TCP/IP, Ethernet, Radio Frequency, fiber-optic or other type link and the client computing device includes a corresponding USB, IEEE 1394, serial, parallel, IEEE 802.1 1 , TCP/IP, Ethernet, Radio Frequency, fiber-optic interface device, component, port or module.

[0037] In one example, the processor 121 executes computer program code from the memory 122 to execute a bipartite graph analyser 150 to determine, from a received bipartite graph, an optimal representation of the bipartite graph. In one example, the bipartite graph is received in the form of an adjacency matrix 180 in which nodes and edges are defined by values in a matrix, an edge between node ^! n' and node 'm' being represented by a value such as a Ύ in position intersecting row 'n' and column ^! m' in the matrix and in the position intersecting row 'm' and column 'n' in the matrix.

[0038] In one example, the bipartite graph analyser 150 iteratively processes a bipartite graph to determine an arrangement of nodes and edges that is an optimal visual representation of the bipartite graph. In one example, in each iteration the bipartite graph simulates the influence of physical forces on nodes of the bipartite graph to determine the optimal visual representation. In one example, the distance between nodes in the optimal visual representation is determined from forces acting upon the nodes. Node placement is discussed further with respect to FIG.

5 below.

[0039] In one example, upon the bipartite graph analyser determining an arrangement of nodes and edges that is an optimal visual representation, the processor 121 executes computer program code from the memory 122 to execute a rendering engine 180 to generate a graphical representation in the form of a 2- Dimensional (2D) or a 3-Dimensional (3D) rendering of the optimal visual representation. In one example, the rendering engine 160 projects the nodes and edges in the optimal visual representation onto the surface of a 3D object to generate the 3D rendering. In this manner, groups of nodes are positioned to appear to substantially sit upon the surface of the 3D object and the edges linking to connected nodes are positioned such that proximate edges group or bunch together. In another example, the optimal visual representation is displayed as a 2D display.

[0040] In one example, the visual representation is further optimized prior to being displayed to optimize the shape and position of edges between selected nodes. In one example, the further optimization is based upon a simulation of spring and Lorentz physical forces which is discussed further with respect to FIG.

6 below.

[0041] In one example, the rendering engine 180 outputs the 2D or 3D rendering to the display 130.

[0042] In one example, the processor 121 executes computer program code from the memory 122 to execute a graphical user interface 170 to enable a user to interact with the 2D or 3D rendering. An example graphical user interface is discussed below with reference to FIG. 7.

[0043] In one example, the nodes of the bipartite graph are visually represented in the 2D or 3D rendering and can be zoomed in or out or selected (e.g., by clicking on, touching via a touch screen, entry of a designated label on a keyboard) to provide additional information concerning the node and its links,

[0044] FIG. 4 is a graphical representation of a bipartite graph. In one example, the nodes have been positioned based on a technique executed by the system of FIG. 1. The system positioned the nodes within a display region (in this instance a rectangle) and calculated simulated forces acting on each node. The calculated simulated forces were used to determine the illustrated arrangement of nodes and edges. The simulated forces caused nodes 4, 7, 8 and 1 1 to be grouped together due to their relationship with node 1 . Likewise, nodes 6 and 10 and 5 and 9 have been grouped together. Nodes 3 and 12 have been pushed away from the other nodes due to the simulated repulsive force between nodes and the absence of a simulated spring force that would have resulted from an edge connecting them to the other nodes. However, the simulated attractive force from the display region's center of gravity has kept them within the display region 20.

[0045] FIG. 5 is a flow diagram of operation in a method for displaying a bipartite graph according to various examples. In discussing FIG. 5, reference may be made to the diagrams of FIGS. 1 , 2, 3 and 4 to provide contextual examples. Implementation, however, is not limited to those examples.

[0046] Starting at step 200, a representation of a bipartite graph is received. In one example, the representation is received in the form of an adjacency matrix. In one example, the representation is received via a data communications network. In another example, the representation is received as a result of user inputs to a user interface.

[0047] Continuing at step 210, each node of the bipartite graph is positioned in a predetermined display region. In one example, the position of each node within the display region is randomly selected. In one example, the display region may be user or system selected dependent on a 3D visual representation. For example, for a spherical 3D visual representation the display region would be a circle and for a tubular visual representation, the display region would be a rectangle. In another example, a 2D visual representation may be displayed, the display region corresponding to the 2D representation.

[0048] For each node, steps 220 to 260 are performed. In steps 220 to 240, which are described below in more detail, forces corresponding to a simulated physical system are calculated for the node. At step 250, the calculated forces are resolved by combining their respective components and directions to determine an overall force exerted on the node and at step 260 the respective node is moved within the predetermined display region in dependence on the overall force. In one example, the overall force is a force vector having a direction component and a magnitude component. In one example, each node in each iteration is moved 50% of the magnitude of the overall force in the direction of the overall force.

[0049] At step 220, an electrostatic repulsive force exerted on the node by other nodes in the graph is calculated using Coulomb's law:

Where ke = Coulomb's constant = 8.9875517873881764*10 ⁹ N-m ² /C ² r = distance between nodes

The repulsive force is inversely proportional to the distance, r, between nodes.

[0050] At step 230, an attractive gravitational force exerted on the node is calculated:

771-, 777 ·>

F = G—^-

Where: G, rrn and rm are system parameters associated with the display region; and, r = distance from the node to a center of gravity position for the display region.

The gravitational force between the node and the center of gravity position is used to keep the locations of nodes and/or clusters of nodes around the center of gravity.

[0051] At step 240, a spring force exerted on the node by edges connecting to the node is calculated:

F =—kx

Where: k = spring constant x = distance between node and the corresponding node linked by the edge.

In one example, k = 1.

The spring force is dependent on the distance between nodes and penalizes nodes that share a link by affecting their distance in the layout.

[0052] In one example, steps 220 to 280 are performed iteratively, looping in step 270 until the simulated forces have been applied to all nodes which forms one iteration. In one example, the steps are iterated until the system is determined to reach a substantial mechanical equilibrium in step 280. in one example, substantial mechanical equilibrium is determined to have been reached in step 280 once the relative position of nodes does not substantially change from one iteration to the next. In one example, a gradient descent algorithm is performed on the system of nodes to determine the state of mechanical equilibrium in which the system of nodes has a state with minimal energy induced by the simulated inter- node forces. At step 290, the representation corresponding to the arrangement of nodes and edges is output for display. [0053] The functions and operations described with respect to, for example, the bipartite graph analyser may be implemented as a computer-readable storage medium containing instructions executed by a processor and stored in a memory. Processor may represent generally any instruction execution system, such as a computer/processor based system or an ASIC (Application Specific Integrated Circuit), a Field Programmable Gate Array (FPGA), a computer, or other system that can fetch or obtain instructions or Iogic stored in memory and execute the instructions or Iogic contained therein. Memory represents generally any memory configured to store program instructions and other data.

[0054] FIG. 8 is a flow diagram of operation in a method of optimizing the visual appearance of edges of a graph to be displayed according to various examples. In discussing FIG. 8, reference may be made to the diagrams of FIGS. 1 , 2, 3, 4 and 5 to provide contextual examples. Implementation, however, is not limited to those examples.

[0055] Starting at step 300, edges of a bipartite graph that has been arranged for visual representation, for example according to the method of FIG.2 or FIG. 5 are subdivided into segments. For each segment of each respective edge, steps 310, 320 and 330 are then performed. In one example, the number of segments an edge is divided into is a controllable system parameter. In one example, each edge is divided into 4 segments.

[0056] In steps 310-330, described in more detail below, forces corresponding to a simulated physical system are calculated for each segment of each edge.

[0057] In step 310, a spring force is calculated for each pair of consecutive edge segments of an edge:

F = -kx

Where: k = spring constant x = Euclidean distance between node and the corresponding node linked by the edge.

This has the effect of limiting length of edges. In one example, k is a programmable system parameter. In one example, there is a spring force where there are two consecutive segments. For example, if the edge is constituted by the segments (a,b,c,d), then there is a spring force between a and b, a spring force between b and c and between c and d.

[0058] At step 320, Lorenfz force is calculated between the edge segment and all other edge segments not sharing the respective edge:

1

2πτ

Where: r = distance between segments

This has the effect of causing edge segments in similar locations to be bundled together.

[0059] At step 330, the calculated forces are resolved by combining their components and directions to determine an overall force exerted on the segment and at step 340, the respective segment is moved within the predetermined display region in dependence on the overall force. At step 350, the method loops back to step 310 if there are more segments to be considered for this iteration.

[0060] At step 380, the change in edge segments is evaluated and steps 310 to 350 are repeated if substantial mechanical equilibrium of edge positioning under the influence of the simulated forces has not yet been reached. In one example, steps 310 to 350 are repeated under a gradient descent algorithm so as to reach a state of substantial mechanical equilibrium. In one example, the simulated forces are applied, and moving the edge positions until the gradient descent algorithm determined that the edge positions result in a state with minimal energy induced by the simulated forces. [0061] If substantial mechanical equilibrium has been reached, in one example at step 385 the edge segments for each respective edge are transformed into a curved edge by identifying a cubic Bezier curve parameterized in the [0,1] domain for the edge segments. Each curved edge is displayed on the electronic display at step 370.

[0082] FIG. 7 is a diagram of a user interface system, according to various examples. FIG. 7 includes particular components, modules, etc. according to various examples. However, in different examples, more, fewer, and/or other components, modules, arrangements of components/modules, etc. may be used according to the teachings described herein. In addition, various components, modules, etc. described herein may be implemented as one or more electronic circuits, software modules, hardware modules, special purpose hardware (e.g., application specific hardware, application specific integrated circuits (ASICs), embedded controllers, hardwired circuitry, Field Programmable Gate Arrays (FPGA), etc.), or some combination of these.

[0063] FIG. 7 Illustrates a user interface providing a visual representation of a bipartite graph according to various examples. The optimized visual representation 400 is displayed on a graphical user interface (GUI) 440 of a computing device, which may be a portion of a computing system, including at least one processor executing instructions to generate and display the graphical user interface 170.

[0064] In one example, the graphical user interface 440 displays the representation 400 as well as groupings of nodes 420 identified by group labels 410. In one example, the groupings correspond to the physical groupings shown in the visual representation. In the illustrated example, various groups of nodes can be seen on the surface of the cylinder. The nodes have arrived at these positions under the influence of the simulated forces described above. Where a node is spaced apart from others, it will be in a different (or its own) group. In one example, details on the node are listed in the grouping 420 to enable the user to view detail about a particular node. In one example, each node 430 is listed in its respective group as well as being shown in the representation 400, In one example, the graphical user interface is responsive to user actions such as mouse clicks. In one example, a user clicking on a node in the representation 400 or group 420 causes highlighting of the corresponding node in the other of the group 420 or representation 400. In one example, a user clicking on an edge causes the linked nodes to be highlighted.

[0085] In one example, the graphical user interface includes controls for zooming in and out. In one example, the graphical user interface is responsive to user inputs dragging nodes in the representation 400. In one example, a user dragging a node to a different location causes recalculation of positions of the nodes with the dragged node in its new position.

[0066] Various modifications may be made to the disclosed examples and implementations without departing from their scope. Therefore, the illustrations and examples herein should be construed in an illustrative, and not a restrictive, sense.