BlueStar

In this project our aim was to develop a system using a flexible in/outdoor location management scheme that allows for only the end-user to be aware of their location, while still enabling them to access location-relevant information from a centralised source. In such a system the user can choose the level of granularity with which they provide or publish their location details in contrast to systems in which a fixed network is used to track the user. BlueStar addresses the need for a scalable user-centric end-to-end solution in which end-user privacy is protected. Many existing indoor tracking systems rely on special purpose receivers (badges) and transmitters in conjunction with a costly site radio survey, neither of which is necessary in the BlueStar model. See: BlueStar, a privacy centric location aware system,  IEEE Position Location and Navigation Symposium, 2004 (PLANS 2004).

FADE: What is a Force Directed Algorithm (Spring Algorithm)?

Force directed algorithms view the graph as a virtual physical system, where the nodes of the graph are bodies of thesystem. These bodies have forces acting on or between them. Often the forces are physics-based, and therefore have a natural analogy, such as magnetic repulsion or gravitational attraction.

The general idea behind force directed layouts is explained here but we focus on the use of force directed algorithms for drawing large graphs. Unlike the original algorithm which is order N squared per time step, FADE algorithms are order N log N per time step. (this means you can layout large graphs interactively using this algorithm, rather than waiting hours or days for the layout to compute)

Te edges can be modeled as gravitational attraction and all nodes have an electrical repulsion between them. It is also possible for thesystem to simulate unnatural forces acting on the bodies, whichhave no direct physical analogy, for example the use of alogarithmic distance measure rather than Euclidean [1].

Regardless of the exact nature of the forces in the virtual physical system, force directed algorithms aim to compute a locally minimum energy layout of the nodes. This is usually achieved by computing the forces on each node and iterating the system in discrete time steps. The forces are applied to each node and the positions are updated accordingly. Force-directed algorithms are often used in graph drawing due totheir flexibility, ease of implementation, and the aesthetically pleasant drawings they produce. However, classical force directed algorithms are unable to handle larger graphs due the inherent N squared cost at each time step, where N is the number of bodies in the system. This is a common problem and has prohibited the practical use of force directed algorithms for even moderately sized graphs of a few hundred nodes. The FADE layout paradigm, overcomes this computational limitation to allow large graphs to be drawn and abstractly represented.

Background

The simulation of a virtual physical system for object placement pre-dates the development of force directed algorithms for graph drawing (Quinn 79). Given that it is NP-hard to draw a graph so that all edge lengths are the same, Eades first proposed a heuristic algorithm for drawing undirected graphs in two dimensions, based on simulating a virtual physical model [1]. This model is now referred to as the “”spring model”, since each node is modeled as a steel ring with springs replacing the edges. In this model non-adjacent nodes repel each other according to an inverse square law. Given an initial random layout, the springs and the repulsive forces move the system to alocally minimal energy state, that is, an equilibrium configuration, which is then drawn. Eades noted that in such an equilibrium configuration, all the edges typically have relatively uniform length and nodes not connected by an edge are drawn far apart.

FADE Paradigm

A Spring Algorithm for the large scale layout and multi-level viewing of graphs

The main idea of the FADE paradigm is thefollowing. Given an initial layout method, such as random placement, a graph can be assigned geometric attributes.  Thisprocess creates a graph layout, which can be then be rendered toproduce a graph drawing. This is the classical graph drawing””pipe-line”.

In the FADE paradigm, we take the graph layout andperform a geometric clustering (typically by recursive spacedecomposition) of the locations of the nodes. This process, alongwith implied edge creation, forms a hierarchical compound graph.

The hierarchical compound graph, which includes the decomposition tree, allows us to approximate the nonedge forces in our force directed graph drawing algorithms. Using the decomposition tree, FADE  computes forces; the nonedge forces may be approximately computed. After computing the forces, the underlying graph layout is updated, and this in turn requires there computation of the hierarchical compound graph, which was formed on the previous locations. This process, if iterated, is calledthe progressive cycle where as the graph drawing improves, so does the quality of the hierarchical compound graph.

Roughly speaking, the progressive cycle of FADE proceeds as therepeat loop in the following:

1. Compute Initial Layout
2. REPEAT
   1. Compute Edge Forces
   2. Construct Geometric Clustering
   3. FOR each node V
      • Compute Approximate Nonedge Forces on V (walk the decomposition tree testing if each internal node is “far enough” away to be considered an approximation for the graph nodes it represents)
3. ENDFOR
4. Move Nodes
5. Update Bounding Area/Volume

UNTIL Stopping Condition
END

Performance Improvement

The performance improvement in the FADE paradigm comes from computing forces using a recursive decomposition of the locations of the nodes of a graph drawing, rather than all the nodes directly. Different decompositions generate recursive geometric clusterings of the nodes of the graph. The recursive clustering, represented as sub-trees, does not directly produce ahigh quality geometric clustering of the node positions, nor isit necessarily a high quality graph theoretic clustering. However the clustering does facilitate a dramatic improvement in the performance of force directed algorithms. Further, it allows for multi-level viewing ofhuge graphs at various levels of abstraction. Finally, as the quality of the drawing improves (as it reaches a lower energy state of the force system), the quality of clustering, exhibited by the decomposition tree, improves to a reasonable amount. This clustering, if it is of sufficient quality is appropriate for visual abstraction.