Force-directed algorithms for schematic drawings and placement: A survey

Force-directed algorithms have been developed over the last 50 years and used in many application fields, including information visualisation, biological network visualisation, sensor networks, routing algorithms, scheduling, graph drawing, etc. Our survey provides a comprehensive summary of developments and a full roadmap for state-of-the-art force-directed algorithms in schematic drawings and placement.

(more…)

Snapshot Visualization of Complex Graphs with Force-directed Algorithms

Force-directed algorithms are widely used for visualizing graphs. However, these algorithms are computationally expensive in producing good quality layouts for complex graphs. The layout quality is largely influenced by execution time and methods’ input parameters especially for large complex graphs. The snapshots of visualization generated from these algorithms are useful in presenting the current view or a past state of an information on timeslices. Therefore, researchers often need to make a trade-off between the quality of visualization and the selection of appropriate force-directed algorithms.

(more…)

CWBound: boundary node detection algorithm for complex non-convex mobile ad hoc networks

Efficient message forwarding in mobile ad hoc network in disaster scenarios is challenging because location information on the boundary and interior nodes is often unavailable. Information related to boundary nodes can be used to design efficient routing protocols as well as to prolong the battery power of devices along the boundary of an ad hoc network. In this article, we developed an algorithm, CWBound, which discovers boundary nodes in a complex non-convex mobile ad hoc (CNCAH) networks.

(more…)

Design and Implementation of Lifeline Emergency Ad Hoc Network

There are real cases where mobile phones have been contributed for successful rescues in recent catastrophic disasters. Examples of such cases have been reported in history.

(more…)

Architecture of Force-directed Algorithms

A graph layout problem, or visualization problem, refers to a set of nodes and a set of relationships (edges) built on top of this set of nodes, calculating the position of the nodes and drawing each edge as a line or curve.

One of the most important research directions in the visualization technology of graphs is the study of graph layout algorithms. The core content of the graph layout algorithm research is to study how to display the graph structure in a better way. E.g. force-directed algorithms.

The comprehensive workflow for basic force-directed algorithms are summarized below:

  1. Kamada-Kawai Algorithm
  2. Fruchterman Reingold Algorithm
  3. ForceAtlas2 Algorithm
  4. LinLog Algorithm
  5. Davidson and Harel Algorithm

(more…)

CNCAHNetGenerator – CNCAH Network Generator

CNCAHNetGenerator is written in Java 7, to enable the creation of CNCAH networks of arbitrary node and edge types. (more…)

Dataset of CNCAH Network

CNCAH shapes generated by the CNCAHNetGenerator. You can download the dataset from here. (more…)

Boundary node detection and unfolding of complex non-convex ad hoc networks

Complex non-convex ad hoc networks (CNCAH) contain intersecting polygons and edges. In many instances, the layouts of these networks are also not entirely convex in shape. In this paper, we propose a Kamada-Kawai based algorithm called W-KK-MS for boundary node detection problem, which is capable of aligning node positions while achieving high sensitivity, specificity and accuracy in producing a visual drawing from the input network topology. The algorithm put forward in this paper selects and assigns weights to top-k nodes in each iteration in order to speed up the updating process of nodes. We also propose a novel approach to detect and unfold stacked regions in CNCAH networks. Experimental results show that the proposed algorithms can achieve fast convergence on boundary node detection in CNCAH networks and are able to successfully unfold stacked regions. The design and implementation of a prototype system called ELnet for analyzing CNCAH networks is also described in this paper. The ELnet system is capable of generating synthetic networks for testing, integrating with force-directed algorithms, and visualizing and analyzing of algorithms’ outcomes.

The author’s version of a work that was accepted for publication can be downloaded from http://eric.lostcity-studio.com/wp-content/uploads/2019/08/Boundary-node-detection-and-unfolding-of-complex-non-convex-ad-hoc-networks.pdf.
Se-Hang Cheong, and Yain-Whar Si. "Boundary node detection and unfolding of complex non-convex ad hoc networks" ACM Transactions on Sensor Networks (TOSN) 14.1 (2017): 1.

Accelerating the Kamada-Kawai algorithm for boundary detection in a mobile ad hoc network

Force-directed algorithms such as the Kamada-Kawai algorithm have shown promising results for solving the boundary detection problem in a mobile ad hoc network. However, the classical Kamada-Kawai algorithm does not scale well when it is used in networks with large numbers of nodes. It also produces poor results in non-convex networks. To address these problems, this paper proposes an improved version of the Kamada-Kawai algorithm. The proposed extension includes novel heuristics and algorithms that achieve a faster energy level reduction. Our experimental results show that the improved algorithm can significantly shorten the processing time and detect boundary nodes with an acceptable level of accuracy.

The author’s version of a work that was accepted for publication can be downloaded from Accelerating Kamada-Kawai for boundary detection in Mobile Ad-Hoc network.

Se-Hang Cheong, and Yain-Whar Si. "Accelerating the Kamada-Kawai algorithm for boundary detection in a mobile ad hoc network." ACM Transactions on Sensor Networks (TOSN) 13.1 (2016): 3.

A layered approach to link analysis and visualization of event data

A layered approach to analysis and visualization of associations from events can provide different levels of abstraction for aggregating and analyzing events from heterogeneous data sources by using lists and customizable functions.

Si, Yain-Whar, Se-Hang Cheong, Simon Fong, Robert P. Biuk-Aghai, and Tat-Man Cheong. "A layered approach to link analysis and visualization of event data." In Digital Information Management (ICDIM), 2012 Seventh International Conference on, pp. 181-185. IEEE, 2012.

The author’s version of a work that was accepted for publication can be downloaded from http://eric.lostcity-studio.com/wp-content/uploads/2019/08/ICDIM2012-AuthorCopy.pdf.