Browse Prior Art Database

Non-Newtonian Dynamic Graph Layout Algorithm

IP.com Disclosure Number: IPCOM000247079D
Publication Date: 2016-Aug-02
Document File: 3 page(s) / 96K

Publishing Venue

The IP.com Prior Art Database

Abstract

We describe a new technique for dynamic graph layout subject to constraints. Compared to previous techniques the proposed method is faster, and more stable on large graphs which change over time.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 55% of the total text.

Page 01 of 3

Non-Newtonian Dynamic Graph Layout Algorithm

Most network (i.e. a graph of nodes and edges) layout algorithms are designed to visualise networks in an aesthetically pleasing way. They work principally by arranging nodes connected to one another close together, in a way which keeps each edge in the network at roughly the same length. The Force-directed graph layout algorithms are the most commonly used family of algorithms to achieve this.

    The force-directed algorithms are heuristics that model the network as one or more physical systems, iteratively attracting and repelling nodes from one another until a kind of global-equilibrium or global-minima is found.

    This invention builds upon work presented previously in US application number 14/731837 (Force Directed Graphs), in which a new kind of instability measure is introduced, and used to dynamically cool (remove energy from) regions of the network in subsequent iterations of the algorithm. This method of regional cooling improves run-time performance, as well as other important considerations. Limitations of Existing Approach (node cooling)

    An important aspect of visual graph analysis is the temporal analysis of the interacting nodes of a network. One way to visualize this is by changing a graph's structure (mutation ) dynamically, by adding/removing nodes and edges over time.

    A layout algorithm in such a dynamic environment can be evaluated by how much adjustment (of nodes and edges) is necessary to accommodate structural changes in the network, and the total time taken for this reconfiguration.

    If many structural changes occur simultaneously in a 'cool' region of the graph - cool because it is naturally unstable - it can take a substantial length of time for the region to reheat, accommodate for the change, and cool down again.

    In the previous invention, the warming of a vertex was set to be disproportionately slower than the cooling process; the intended effect being that nodes spend most of their time in a stable state. This isn't ideal during a mutation phase.

Possible Solution(s)

    One approach is to inject energy around the mutation area, so that nodes rapidly readjust and subsequently cool down in a new configuration. This is acceptable for trivial mutations (e.g. removing a single node and edge from the network) however it is difficult to determine the correct range of energy to inject for more complex mutations that occur in rapid succession; the adjustment of nodes can easily become chaotic.

New Approach (node cooling + viscosity)

    Currently graph algorithms are modelled much like a gas with attractive forces or constraints, where the nodes are charged particles and edges apply

proximity constraints between particle pair...