Field of the Invention

The present invention relates to the generation of force-directed layouts for graphs.

Background to the Invention

Force-directed graph drawing algorithms can be used to generate a layout for displaying a graph to a user. That is to say, they can be used to position the vertices (or nodes) of the graph in either a two-dimensional or three-dimensional space to create a visualisation of the graph for displaying to a user.

Force-directed graph drawing algorithms work by specifying forces that act on the different components (i.e. vertices and/or edges) of a graph. These forces are typically (but not necessarily always) modelled as analogues of various physical forces that occur in the physical world. For example, spring forces modelled on Flooke’s law can be applied between pairs of vertices that are connected via an edge in the graph. Similarly, charge forces modelled on Coulomb’s law can be applied between each vertex and every other vertex in the graph. Other examples of physical forces that can also be used include, momentum, friction, gravity and magnetic fields. These forces are normally applied to the graph’s vertices, but may also be applied to its edges. A layout for the graph can then be generated by finding positions for the vertices of the graph in the two-dimensional or three- dimensional space in which the forces acting on the components of the graph are substantially in equilibrium. Layouts generated in this manner may also be referred to as force-directed layouts.

A force-directed layout of a graph can provide a useful visualisation of a graph’s structure that improves its cognitive ease, enabling a user to more quickly understand the graph’s structure. This is because they can generally achieve a relatively uniform layout of the graph with a relatively low number of crossing edges. Furthermore, such algorithms do not require knowledge of the semantic meaning of the graph being displayed and can operate generically on any given graph. Flowever, the generation of force-directed layouts for graphs is technically complex and computationally expensive. In particular, it can be difficult to generate layouts of complex graphs having a large number of vertices, especially when there is a time constraint, such as when real-time (or near real-time) visualisation of a system represented by a graph (such as a computer network) is required. In such situations, it may be impossible to generate a force-directed layout for a graph using conventional techniques. Summary of the Invention

According to a first aspect of the invention, there is provided a computer implemented method for generating a force-directed layout for a graph comprising a plurality of vertices, wherein the layout is dependent on a force exerted by each vertex on every other vertex, the method comprising: generating an initial layout of the plurality of vertices; determining an effect of global interactions based on the force between vertices by: grouping vertices based on their location in the initial layout; and determining an aggregate effect of each group of vertices as a whole; determining, for each vertex, an effect of local interactions based on the force with the vertices located in a region of the initial layout proximate to the vertex; determining an adjustment to the location of each vertex based, at least in part, on the combined effects of the global and local interactions on that vertex; and applying the determined adjustment to each vertex.

The global and the local interactions result from the effect of either a repulsive or an attractive force exerted by each vertex on every other vertex.

The adjustment of the location of at least some of the vertices may be further based on the effects of one or more additional forces acting on those vertices. The one or more additional forces may comprise one or more attractive forces acting between respective vertices of the graph. The one or more additional forces may comprise one or more repulsive forces acting between respective vertices of the graph.

The vertices may be grouped based on their location in the initial layout by: subdividing the initial layout into a plurality of subdivisions; and grouping any vertices that are located in the same subdivision. The plurality of subdivisions may be defined by a grid. Determining the effect of global interactions may comprise determining the aggregate effect of each group of vertices as a whole on each of the plurality of subdivisions.

Determining the effect of local interactions may comprise: subdividing the layout into a second plurality of subdivisions; grouping any vertices that are located in the same subdivision of the second plurality of subdivisions; and determining an aggregate effect of each group of vertices the subdivisions of the second plurality of subdivisions adjoining the subdivision in which the group is located. The second plurality of subdivisions may be defined by a second grid.

The global interactions may be determined at a lower resolution than the local interactions. The method may be performed iteratively until an equilibrium is substantially reached.

According to a second aspect of the invention, there is provided a computer system comprising a processor and a memory storing computer program code for performing a method according to the first aspect.

According to a third aspect of the invention, there is provided a computer program which, when executed by one or more processors, is arranged to carry out a method according to the first aspect.

Brief Description of the Figures

In order that the present invention may be better understood, embodiments thereof will now be described, by way of example only, with reference to the accompanying drawings, in which:

Figure 1 is a block diagram of a computer system suitable for the operation of embodiments of the present invention;

Figure 2 is a flowchart illustrating a method for generating a force-directed layout for a graph according to the invention;

Figure 3 shows an exemplary initial layout for an exemplary graph;

Figure 4, which illustrates a grid overlaid over the area in which the initial layout of Figure 3 was generated;

Figure 5 provides a conceptual illustration of the aggregation of the effects of each group of vertices; and

Figure 6 illustrates another grid overlaid over the area in which the initial layout of Figure 3 was generated.

Detailed Description of Embodiments

Figure 1 is a block diagram of a computer system 100 suitable for the operation of embodiments of the present invention. The system 100 comprises: a storage 102, a processor 104 and an input/output (I/O) interface 106, which are all communicatively linked over one or more communication buses 108. The storage (or storage medium or memory) 102 can be any volatile read/write storage device such as a random access memory (RAM) or a non-volatile storage device such as a hard disk drive, magnetic disc, optical disc, ROM and so on. The storage 102 can be formed as a hierarchy of a plurality of different storage devices, including both volatile and non volatile storage devices, with the different storage devices in the hierarchy providing differing capacities and response time, as is well known in the art.

The processor 104 may be any processing unit, such as a central processing unit (CPU), which is suitable for executing one or more computer programs (or software or instructions or code). These computer programs may be stored in the storage 102. During operation of the system, the computer programs may be provided from the storage 102 to the processor 104 via the one or more buses 108 for execution. One or more of the stored computer programs which, when executed by the processor 104, cause the processor 104 to carry out a method according to an embodiment of the invention, as discussed below (and accordingly configure the system 100 to be a system 100 according to an embodiment of the invention).

The input/output (I/O) interface 106 provides interfaces to devices 110 for the input or output of data, or for both the input and output of data. The devices 110 may include user input interfaces, such as a keyboard 110a or mouse 110b as well as user output interfaces, such as a display 110c. Other devices, such a touch screen monitor (not shown) may provide means for both inputting and outputting data. The input/output (I/O) interface 106 may additionally or alternatively enable the computer system 100 to communicate with other computer systems via one or more networks 112. It will be appreciated that there are many different types of I/O interface that may be used with computer system 100 and that, in some cases, computer system 100, may include more than one I/O interface. Furthermore, there are many different types of device 100 that may be used with computer system 100. The devices 110 that interface with the computer system 100 may vary considerably depending on the nature of the computer system 100 and may include devices not explicitly mentioned above, as would be apparent to the skilled person. For example, in some cases, computer system 100 may be a server without any connected user input/output devices. Such a server may receive data via a network 112, carry out processing according to the received data and provide the results of the processing via a network 112.

It will be appreciated that the architecture of the system 100 illustrated in figure 1 and described above is merely exemplary and that other computer systems 100 with different architectures (such as those having fewer components, additional components and/or alternative components to those shown in figure 1) may be used in embodiments of the invention. As examples, the computer system 100 could comprise one or more of: a personal computer; a laptop; a tablet; a mobile telephone (or smartphone); a television set (or set top box); a games console; an augmented/virtual reality headset; a server; or indeed any other computing device with sufficient computing resources to carry out a method according to this invention.

Figure 2 is a flowchart illustrating a method 200 for generating a force-directed layout for a graph according to the invention. The method 200 may be performed by any suitable computer system 100 to create a visualisation of the graph for a user. In some cases, the layout may be generated by one computer system 100, whilst a visualisation based on the layout may be created and displayed to a user by another computer system 100. In other cases, the layout may be generated by the same computer system 100 which displays the visualisation to the user.

The force-directed layout that is to be generated is based on a physical model in which forces are modelled as acting on each vertex. The layout is generated by determining locations for each vertex of the graph in which the forces acting on each vertex are substantially in equilibrium. A substantial equilibrium may be considered to be present when the forces acting on any vertex would not cause that vertex to move by an amount that is less a pre-determined threshold. The physical model includes at least one type of force that creates a field. That is to say, a force which acts throughout the entire space in which the layout is being created and results in interactions between each vertex and every other vertex regardless of whether those vertices are connected via an edge in the graph. This force can be attractive or repulsive in nature. For example, a physical model may be defined in which each vertex is considered to have an electrical charge and exert a repulsive force on every other vertex based, at least in part, on a distance between that vertex and another vertex in the layout according to Coulomb’s law. Similarly, as a further example, a physical model may be defined in which each vertex is considered to generate a gravitational field that exerts an attractive force on every other vertex based, at least in part, on a distance between that vertex and another vertex in the layout according to Newton’s law. The physical model may include forces between vertices that result from many different types of forces. Some of these forces may be modelled as acting on specific vertices rather than as a field that affects all vertices in the graph layout. For example, an attractive force may be modelled between any pairs of vertices that are connected by an edge that is based on a spring according to Flooke’s law. Such forces would only (directly) affect the vertices associated with a particular edge. The layout may be determined within either a two- dimensional or three-dimensional space. As will be understood by the skilled person, where a three-dimensional layout is generated, a projection of the three-dimensional layout may be used to provide a visualisation of the graph. Similarly, although the forces included in the physical model for generating a force-directed are typically analogues of forces that occur in nature, this need not necessarily be the case. That is to say, artificial forces that are not directly based on any natural phenomenon, or which utilise a different relationship from their natural analogue may be used instead or in addition (e.g. some force-directed systems use ‘springs’ whose attractive force is logarithmic rather than linear).

For simplicity, the remainder of the examples in this description will consider a physical model in which each vertex is considered to have a charge and exerts a force on every other vertex that is based on Coulomb’s law, whilst each pair of vertices that are connected by an edge have an attractive force that is based on Hooke’s law. Layouts resulting from such a physical model may be called Force-Spring layouts. However, it will be appreciated that the described method can be applied to generate force-directed layouts for graphs based on the application of physical models involving any other suitable combinations of different forces, as would be readily apparent to the skilled person.

The method 200 begins at an operation 210. At operation 210, the method 200 generates an initial layout of the plurality of vertices. Figure 3 shows an exemplary initial layout 300 for an exemplary graph. The graph comprises a plurality of vertices (or nodes)

310(1 )-310(6), as well as a plurality of edges which each connect a respective pair of vertices, as will be readily recognised by those skilled in the art. Any suitable means that will be known to the skilled person may be used to generate the initial layout. For example, the vertices may be randomly placed in the two-dimensional or three-dimensional area within which the layout is to be created. As another example, the initial layout may be created by identifying the most connected vertex in the graph (or picking one at random, if there are multiple having the same level of connectivity) and placing that vertex in the middle. Having placed the centre, any first-order vertices that are directly connected to that vertex can be placed on a circle of pre-determined radius surrounding the vertex at an even spacing.

Then, any second-order vertices that are directly connected to a first-order vertex can be placed on a circle of twice the pre-determined radius surrounding the vertex at an even space. This can be repeated until all vertices have been placed. In any case, regardless of the technique used to generate the initial layout, the generation of the initial layout 300 should ideally be relatively fast by demanding relatively little processing resources. The initial layout 300 serves as the starting point which the method 200 improves upon by adjusting the locations of the vertices in the layout in a way which brings them closer to equilibrium, according to the forces and mechanics of the underlying physical model. Having generated an initial layout, the method 200 proceeds to an operation 220. At operation 220, the method 200 groups the vertices of their graph based on their current location in the layout (e.g. in the initial layout 300).

One way of grouping the vertices based on their location will now be discussed in conjunction with Figure 4, which illustrates a grid 400 overlaid over (i.e. covering) the area in which the initial layout of Figure 3 was being generated. This grid subdivides (or partitions) the layout area into a plurality of subdivisions (or portions), as defined by the squares of the grid. In this example, the grid defines 16 subdivisions, although of course any number of subdivisions may be defined depending on the size of the layout area and the desired resolution (i.e. size of portion), as will be discussed further below. All the vertices that are contained in a given subdivision may be grouped together into a single group. For example, in the example illustrated in Figure 4, the vertices 310(1 ), 310(2) and 310(3) all lie in the same grid square and so are grouped together in a first group, the vertex 310(4) is the only vertex in its grid square and so is placed in a second group on its own, meanwhile the vertices 310(5) and 310(6) both lie in the same grid square and so are grouped together in a third group.

It will be appreciated that there are many ways of grouping the vertices based on their location. Where a grid is used, as in the above example, the subdivisions defined by such a grid need not necessarily be square. Any tessellating shapes may be used. Equally the size of the subdivisions defined by the grid need not necessarily be uniform. For example, the subdivisions in one part of the layout area may be larger than in another part of the layout area. Indeed, a grid need not necessarily be used to partition the layout area into portions. Other techniques, such as clustering, may be used to group the vertices based on their location instead.

To summarise, operation 220 allocates each vertex to a group, such that each group contains vertices that are relatively close to each other in the layout (i.e. located in the same general area). It will be appreciated that any number of vertices may be included in a group, including one (which in general will relate to relatively isolated vertices in the layout). The method 200 then proceeds to an operation 230.

At operation 230, the method 200 determines an aggregate effect of each individual group of vertices as a whole. The aggregate effect is the combined effect of the group of vertices. The aggregate effect can be determined by summing the force-generating property of each vertex in the group. The group of vertices can then conceptually be considered to be a single vertex located at the centre of the group of vertices and have the combined force-generating abilities of the entire group. The centre of the group of vertices may be generated purely geometrically or may be weighted based on the comparative force generating capability of by each vertex (where each vertex may have a different force generating capability, such as having different electrostatic charges). For example, where each vertex is considered to have a charge, the charge being the force-generating property since it determines the force a vertex exerts on every other vertex according to Coulomb’s law, the charges for each vertex in the group are summed. The aggregate effect of the group of vertices may then be considered to be the same as a single vertex located at the centre of the group of vertices and having the same total charge as all of the vertices in the group. Alternatively, instead of conceptually locating the vertex at the centre of the vertices in the group, where the layout area is subdivided, such as by grid 400, the vertex may be conceptually located at the centre of the subdivision that defines the group.

Figure 5 provides a conceptual illustration of the aggregation of the effects of each group of vertices. In particular, the first group of vertices 310(1 ), 310(2) and 310(3) have conceptually been combined into a single vertex 510(1). This single vertex 510(1) is located in the centre of the grid square that contains 310(1), 310(2) and 310(3) and has the combined charge of all three vertices (as represented in Figure 5 by its size). The second group only included a single vertex 310(4) and has therefore conceptually been aggregated into a single vertex 510(2) having the same charge as that single vertex 310(4) and being located in the centre of the grid square that contained that vertex. Finally, the third group of vertices 310(5) and 310(6) has conceptually been combined into a single vertex 510(3) having the combined charge of both vertices and being located in the centre of the grid square that contained those vertices.

The aggregate effect of the groups of vertices can then be used to determine the effect of the global interactions between the vertices throughout the entire layout area. This can be determined for each vertex by assessing the total magnitude of the field caused by all the vertices in the graph at points either side of that vertex. The total magnitude of the field caused by all the vertices in the graph at those points can be determined by summing the fields caused by the aggregate effect of each group of vertices at those points. An overall force acting on the vertex as a result of the global interactions can then be derived by looking at the difference in the field on either side of the vertex along an axis for the vertex; this is repeated for a plurality of axes. The points around each vertex that are used for determining this overall force can be identified and evaluated individually for each vertex. That is to say, a point a predetermined distance either side of each vertex along predetermined axes may be identified and the total effect of all fields evaluated at those points to determine the effect of the global interactions on that vertex. A difference between the total fields either side of a vertex along an axis can be evaluated to determine a magnitude of the component of the force acting on that vertex along that axis. The total force can be determined by combining the components of the force acting along each axis that is evaluated, as will be readily understood by a person skilled in the art.

As an alternative to identifying and evaluating points individually for each vertex, where the layout area has been subdivided, such as through the overlaid grid illustrated in Figures 4 and 5, the points may be the centre points of each (or at least some) of the surrounding subdivisions. This means that the effect on the first group of vertices 310(1), 310(2) and 310(3) can be determined based on the total magnitude of the field caused by each group of vertices at the centre of each of the surrounding subdivisions (as indicated by the dashed line 520 in Figure 5). The components of the total force resulting from global interactions on the first group of vertices may then be calculated along the North-South, East-West, North East-South West and North West-South East axes (although, of course, fewer axes may be used). Accordingly, the net force on each of the vertices 310(1 ), 310(2) and 310(3) in the first group resulting from the effect of the global interactions may be considered to be the same. Using this technique, the net force of the global interactions may effectively be determined for each group of vertices, rather than for each vertex individually.

In any case, having determined an effect of global interactions between the vertices of the graph in the layout, the method 200 proceeds to an operation 240.

At operation 240, the method 200 determines an effect of local interactions with the vertices located in a region of the layout proximate to the vertex. That is to say, a local (or localised) area surrounding each vertex is defined and the effects of the interactions with any vertices located in that local area on the vertex is evaluated. The effect of local interactions is determined in the same way as the global interactions discussed in operations 220 and 230, with the exception that interactions with any vertices located outside the local area are not evaluated when determining the effect of local interactions.

A different respective local area may be individually defined for each vertex, for example, by specifying that the local area of a vertex is an area of a predetermined size centred on that vertex. Alternatively, the local areas may also be defined by subdividing the grid into a plurality of subdivisions (or portions), again in a similar manner to that discussed above in relation to operations 220 and 230. As discussed in relation to operations 220 and 230, a grid may be defined to subdivide the layout area. Figure 6 illustrates another grid 600 overlaid over the area in which the initial layout of Figure 3 was generated. This grid 600 is a separate grid from the grid 400 which may be defined for performing operation 220 and 230 and provides a higher resolution (i.e.it subdivides the area into a greater number of smaller subdivisions). The local area for a vertex can then be determined as being a predetermined number of grid squares in each direction surrounding the grid square that a vertex is located in. This means that any vertices located in the same subdivision will have the same local area defined. For example, the dotted line illustrates a local area 610 for vertex 310(1) that is defined as being one grid square in each direction of the grid 600 (thereby to define a three-by-three grid). Therefore, in this example, the effect local interactions resulting from the forces exerted by vertices 310(2) and 310(3) will be evaluated as these vertices are located inside the local area 610 if vertex 310(1), whilst any effects of vertices 310(4) 310(5) and 310(6) will not be included as they are located outside the local area 610.

Similarly, the effect of the local interactions on a particular vertex, such as vertex 310(1), may be determined individually for each vertex within the local area 610. However, where the layout is subdivided, such as through the definition of grid 600, a similar technique of aggregating the effect of all the vertices located in each subdivision as used for operations 220 and 230 may be used, albeit at a higher resolution than was used during those operations. Indeed, it will be appreciated that since the local interactions are only determined within an area proximate to each vertex, the grid 600 used for determining the local interactions can be a much higher resolution than that used for determining the global interactions (where one is used), without a commensurate significant increase in processing requirements. Following this aggregation approach means that the effect of the local interactions on all vertices in a particular subdivision of the grid 600 may be considered to be the same.

Although operation 240 is shown following operations 220 and 230 in the flowchart illustrating the method 200 in figure 2, it will be appreciated that these two sets of operations are independent of each other and may be carried out in any order. Indeed, these sets of operations can also be carried out in parallel. In any case, having determined the effects of the local and global interactions on each vertex following completion of operations 220-240, the method 200 proceeds to an operation 250.

At operation 250, the method 200 adjusts the location of each vertex based, at least in part, on the combined effects of the global and local interactions acting on that vertex. That is to say, the forces resulting from the effects of all the vertices as well as those located in the local area of the vertex as determined in operation 230 and 240 respectively are combined and used to determine a new position for the vertex in the layout area according the mechanics of the underlying physical model. The underlying physical model may include other additional forces that act on at least some of the vertices, in which case, the adjustment of the location of those vertices may also take such additional forces into account. For example, in the graph 300 illustrated in figure 3, spring forces may be considered to act between pairs of vertices that are connected via an edge. As will be appreciated such forces may be attractive in nature and therefore serve to counterbalance (at least partially) some of the repulsive forces that each vertex experiences. Of course, any other type of forces, including momentum, friction, gravity, magnetic fields any others may be included in the physical model as forces that are additionally taken into account when determining the new locations for vertices in the layout. Having adjusted the location of the vertices in the layout based on the combined global and local interactions occurring within the graph layout, the method 200 proceeds to an operation 260.

At operation 260, the method 200 optionally determines whether an equilibrium has been reached between all the forces acting on each vertex according to the underlying physical model. If so, the method 200 ends. Otherwise, the method 200 may repeat (or reiterate) operations 220, 230, 240 and 250 to further refine the layout of the graph until equilibrium has been substantially reached. A substantial equilibrium may be considered to be present when the forces acting on any vertex would not cause that vertex to move by an amount that is less a pre-determined threshold. Of course, it will be appreciated that with each iteration of the method 200, the layout may be improved. Accordingly, the force-directed layout that is provided by a single pass of method 200 may be considered sufficient. Alternatively, the method 200 may re-iterate as many times as possible within a certain amount of processing time that has been allocated to the generation of the force-directed layout.

By separating out the consideration of the long-range global interactions between vertices in the graph from the consideration of the short-range local interactions between vertices, the invention enables a force-directed graph layout to be generated more efficiently. In particular, the long-range interactions can be determined globally at a low resolution, with the effects of proximate vertices being amalgamated, whilst the short-range interactions can be determined locally at a higher resolution. As a result, the generation of a force-directed layout can be achieved with a computational complexity that has a linear relationship with the number of vertices in the graph (rather than exponential). This makes it possible to generate layouts for visualising graphs containing a much higher numbers of vertices in real time (or near real-time).

Insofar as embodiments of the invention described are implementable, at least in part, using a software-controlled programmable processing device, such as a microprocessor, digital signal processor or other processing device, data processing apparatus or system, it will be appreciated that a computer program for configuring a programmable device, apparatus or system to implement the foregoing described methods is envisaged as an aspect of the present invention. The computer program may be embodied as source code or undergo compilation for implementation on a processing device, apparatus or system or may be embodied as object code, for example. Suitably, the computer program is stored on a carrier medium in machine or device readable form, for example in solid-state memory, magnetic memory such as disk or tape, optically or magneto-optically readable memory such as compact disk or digital versatile disk etc., and the processing device utilises the program or a part thereof to configure it for operation. The computer program may be supplied from a remote source embodied in a communications medium such as an electronic signal, radio frequency carrier wave or optical carrier wave. Such carrier media are also envisaged as aspects of the present invention. It will be understood by those skilled in the art that, although the present invention has been described in relation to the above described example embodiments, the invention is not limited thereto and that there are many possible variations and modifications which fall within the scope of the invention. The scope of the present invention includes any novel features or combination of features disclosed herein. The applicant hereby gives notice that new claims may be formulated to such features or combination of features during prosecution of this application or of any such further applications derived therefrom. In particular, with reference to the appended claims, features from dependent claims may be combined with those of the independent claims and features from respective independent claims may be combined in any appropriate manner and not merely in the specific combinations enumerated in the claims.