Hybrid force-directed algorithms
Heuristic approaches have been employed in several research to increase the performance of force-directed algorithms and minimize execution time, allowing the algorithms to efficiently visualize huge and complicated networks. The multilevel approach, for example, uses network abstraction procedures to simplify networks. Parallel computing and hardware acceleration are used in distributed force-directed algorithms to minimize the time it takes to parse vast networks. The multidimensional scaling technique can be used to visualize the meaningful underlying dimensions of networks. In the next sections, state-of-the-art investigations of these heuristics are described and summarized.
Parallel and hardware accelerated force-directed algorithms
Parallel computing is based on the idea of solving a computer issue with numerous resources at the same time. The following are the steps involved in parallel computing in general:
1. A computational issue is first broken down into smaller executable components that can be solved in parallel.
2. Each item of executable content will be broken down further into a set of instructions for the central processing unit (CPU) or graphics processing unit (GPU) (GPU).
3. On various CPUs or GPUs, instructions from each piece of executable material are executed at the same time.
4. The usage of a overall coordinating mechanism is employed. Before transmitting the result to the receiving task, a task sends an acknowledgement to the coordinator after completing the execution of instructions.
Multilevel force-directed algorithms
The multilevel methodology for force-directed algorithms uses network abstraction notions and can be broken down into two steps. The original network is broken into a series of coarse networks with decreasing sizes in the first phase, known as ‘coarsening.’ By picking coalescent pairs of nearby nodes to form a new network, the network’s combinatorial structure is simplified. To abstract a sequence of such coarse networks, the selection process is repeated recursively. The energy optimization (minimization) procedure is then applied to these coarse networks, with the global properties of the original network being used to optimize them.
The refining phase, which comprises consecutive drawings of fine networks computed from the smallest coarse networks, is the second phase. The locally determined parameters from the linked coarse network are used to optimize finer networks. As a result, because the energy-minimization algorithm only evaluates a small number of neighborhoods at a time, it can reduce running time. For force-directed algorithms, the multilevel approach has been proposed in a number of research. There have also been research that apply the multilevel method to traditional force-directed algorithms like the multilevel KK and FR algorithms.
Force-directed algorithms with multidimensional scaling
Instead of a large number of duplicated records, high-dimensional data usually has a big number of variables. In force-directed algorithms for high-dimensional data reduction, the multidimensional scaling technique is commonly utilized. The goal of the multidimensional scaling methodology is to identify significant underlying dimensions so that observable network similarities and differences may be clearly understood. Torgerson invented the multidimensional scaling principle, which employs the distance between edges as a measure. The nodes are projected onto a smaller space that meets the metric limit (the distance of edges).
For force-directed algorithms to visualize high-dimensional data in which the distances between pairs of data are retained, many studies have used multidimensional scaling. Multidimensional scaling helps improve the layout of networks with high-degree nodes, which is useful for energy function minimization modelling.
