The Sparse Group Log Ridge for the Selection of Variable Groups

In recent years, the sparse model is a research hotspot in the field of artificial intelligence. Since the Lasso model ignores the group structure among variables, and can only achieve the selection of scattered variables. Besides, Group Lasso can only select groups of variables. To address this problem, the Sparse Group Log Ridge model is proposed, which can select both groups of variables and variables in one group. Then the MM algorithm combined with the block coordinate descent algorithm can be used for solving. Finally, the advantages of the model in terms of variables selection and prediction are shown through the experiment.

Introduction
In fields such as artificial intelligence and machine learning, the space of explanatory variables in many problems of classification and regression tends to be very high-dimensional, or even ultra-highly dimensional. However, high-dimensional data can lead to overfitting in machine learning, thus resulting in poor generalization performance of statistical models. Therefore, variable space dimensionality reduction and variables selection are two problems to be solved. The objective of variable selection is twofold. One is to achieve accurate prediction and classification, and the other is to make the model more interpretable and reduce the complexity of statistical models. The so-called interpretability refers to the simplicity of the model. Obviously, the lower the dimensionality of the variable space is, the better the interpretability of the statistical model is. The Lasso [1] based on the L1-norm penalty proposed by Tibshirani can effectively reduce the dimension of variable space but can only achieve distributed variable selection. In many cases, there is a certain structure among variables. For example, in gene microarray analysis, there are often multiple variants in a gene. When identifying the genetic variant that is associated with the disease, it is more reasonable to divide the variants belonging to the same gene into one group. Given this, some scholars conduct variables selection by taking the structure among variables as a priori information. Group Lasso [2] is a sparse model that uses the group structure of variables as a priori information, which can achieve the selection of variable groups. Sparse models such as SCAD [3], MCP [4], and adaptive Lasso [5] improve the consistency in variables selection of the Lasso. Elastic Net [6] can select groups of highly correlated variables simultaneously. Models such as Lasso have also been applied to the field of support vector machines (SVMs) to constitute sparse SVMs [7][8][9][10][11]. Support vector machine (SVM) has good classification performance, which has been studied extensively in the past ten years. What is more, the standard L2-norm SVM classifier uses a ridge penalty function, so feature selection cannot be implemented. However, feature selection is very important in many situations. For example, selecting important genes is a very important issue in bio-informatics. In many cases, eliminating noise variables can improve the classification accuracy of the classifier. Therefore, how to achieve (1), respectively. From the image of the log penalty, it can be seen that the log penalty tends to the L1norm penalty when 0  a . As the absolute values of the coefficients increase, the log penalty gradually decreases, i.e., the degree to which the variable coefficients are compressed gradually decreases, which is similar to the principle of SCAD penalty and MC penalty. Also, this property can effectively reduce the bias of estimating regression coefficients.  is known, where β is the coefficient vector of 1  P -dimension, X is the design matrix of P n  order, and y is the output vector of 1  n -dimension.
The noise ε follows a Gaussian distribution.First, P variables are divided into J groups. j β is the coefficient vector of the j th variable group, j X is the sub-design matrix of the j th variable group, j d is the number of variables in the j th variable group, and Without loss of generality, we may assume that that the data is standardized, and x is the observation value of the p th variable in the j th variable group. Then the SGLR can be written in the following form: is the log penalty, and 1  , 2  , and a are adjustable parameters. The integration of the group structure of the penalty function and the L 1 -norm penalty enables the SGLR to achieve twolayer variables selection, that is, select both the objective variable group and the objective variables within the objective variable groups. The SGLR proposed in this paper is inspired by the hierarchical penalty function, and the penalty function of the hierarchical penalty function can be written d is the number of variables contained in the j th variable group. For SGLR, the function out f in the outer layer is the log penalty and the function in the inner layer is the L 1 -norm penalty.

Solution Algorithm of the SGLR model
In SGLR, solutions cannot be obtained by directly using the block coordinate descent algorithm due to the lack of an explicit solution for a single variable. In this paper, the solution of SGLR is obtained by using MM (Majorize-Minimization) algorithm combined with the block coordinate descent algorithm.
Since the log penalty is concave function in the range of    , 0 , the relationship between the log penalty and its first-order Taylor expansion at the current point  is the first-order partial derivative of the log penalty at the current point 1 j β . And since the equality in the above inequality holds at the current point can be used as the majorizing function with respect to    The reason why the above equality holds is that the elimination of the constant term does not affect the optimal solution to the optimization problem. Then the optimization problem for the th variable groups can be written as follow. (4) In fact, Eq. (4) is a Lasso problem, which can be solved by means of the block coordinate descent method. Since Eq. (4) is not differentiable at 0, sub-gradient and subdifferential are used to derive the optimal solution. The subdifferential of at zero is , where is the first-order partial derivative of the log penalty at the current point . Since the function is not differentiable at zero, it is necessary to use sub-gradient and subdifferential. The following derivation is carried out.The necessary and sufficient condition for the case that is the solution of Eq. (4) as follows.
where , that is, leads the following equation: For and , the following can be obtained: Then, it can be known that when . For , the following can be obtained: For , the following can be obtained: Then its explicit solution with respect to a single variable is as follows.
Once the explicit solution of SGLR with respect to a single variable is obtained, the block coordinate descent algorithm can be solved.The algorithm for solving the SGLR is given below.
(a) Input the response vector , the design matrix , and the initial value of the regression coefficient vector. (b) Repeat the following steps when .  (c) Get the regression coefficient vector after traversing all the groups once, and determine whether the predefined convergence condition or the number of iterations is satisfied. If not, go to step (b); otherwise, end. (d) Output the regression coefficient vector .

Experiments with Synthetic Datasets
This section generates three different types of datasets: synthetic dataset 1, synthetic dataset 2, and synthetic dataset 3. Among them, synthetic dataset 1 is sparse both in the level of variable groups and variables, while synthetic dataset 2 is sparse only in the level of variable groups and synthetic dataset 3 is sparse both in the level of variable groups and variables, and extremely sparse in the level of variables within group. All three datasets are generated based on the linear regression model  150 300 3.00 0.00 3.00 0.0239 For the three synthetic datasets, the variables are randomly divided into two sub-datasets containing an equal number of samples, one of which is used as the training dataset and the other as the test dataset. The above division process is repeated for 30 times to obtain 30 experimental results, and the mean value of the 30 experimental results is taken as the final experimental result. The experimental results are shown in Table 1, Table 2, and Table 3. Where, n denotes the number of training samples, P denotes the total number of variables, Size denotes the total number of selected variables, Rel denotes the number of identified objective variables, Noi denotes the number of eliminated redundant variables, and MSE denotes the predicted mean square error. The experimental results of the three synthetic datasets show that SGLR performs well on prediction and variables selection in terms of accuracy.
To verify the capability for two-layer variables selection of SGLR, the first experiment of 30 experiments conducted for the synthetic data set 1 is selected, and the non-zero regression coefficients fitted for that experiment are included in Tables 4, 5 . By comparing the experimental results of Lasso and Group Lasso, it can be known that Lasso only achieves scattered variables selection, while Group Lasso only achieves the selection of variable groups, where the coefficients of the variables grouped into the same variable group are all zero or all non-zero.
The capability for within-group variables selection of SGLR can be seen by comparing its experimental results with those of Group Lasso. Group Lasso only achieves the selection of variable groups, where the coefficients of variables grouped into the same variable group are all zero or all non-zero, while SGLR achieves within-group variables selection, where the coefficients of variables within the same group are either zero or non-zero.
The capability for variable groups selection of SGLR can be seen by comparing its experimental results with those of Lasso. The true regression coefficient of V40 is 0.3, and V40 is the objective variable expected to be selected, and Lasso selected V40. But the regression coefficient value of V40 obtained in SGLR was 0, and V40 was not selected in SGLR. The reason is that V40 in SGLR was in the same variable group with V31-V39, which are other nine non-significant variables with a true regression coefficient of zero. The existence of a large number of non-significant variables enables the variable group to be a non-significant variable group. V40 is affected by these nine non-significant variables in the same group, resulting in V40 not being selected. In other words, 10 variables in the same group in SGLR are not selected at the same time, that is, the group sparsity and selection of variable groups are achieved. Therefore, the experimental results of Lasso, Group Lasso, and SGLR show that SGLR achieves the selection of both variable groups and within-group variables, that is, SGLR has the two-layer variable selection capability.


extfieldsofstudy:
Physics
Environmental Science

text:
Design of ice snow accident detection system based on Embedded System

Frequent accidents in ski resorts affect the development of skiing industry. In order to solve the problems faced by skiing industry, an ice snow accident detection system based on embedded system is designed. The system combines embedded system with image processing technology, and has high development value. This paper first introduces the hardware composition, function and hardware selection of the system, and then introduces the design of software. The software program is mainly realized by target detection, target tracking and collision detection algorithms. The design of the system provides ideas for the research of ice and snow accident detection, and has very important practical value.

Introduction
With the arrival of the 2022 Winter Olympic Games, the skiing industry is becoming more and more popular. As a new developing industry, the ice and snow industry has a wide range of development and plays an important role in accelerating the development of sports in China. At the same time, more and more people are involved. But skiing is a high-risk sport, especially for beginners without experience and skills. In recent years, skiing accidents occur frequently, which seriously harm the health of skiers and cause huge economic losses to ski resorts. According to statistics, there are many reasons for skiing accidents, among which skiers have the most injuries due to collisions. At present, there are many collision detection methods and equipment on the market, most of them are vehicle collision detection, and there is almost no ice snow collision accident detection.
In view of the current problems faced by the ski industry, the ski resort needs an intelligent monitoring system to accurately monitor the situation of the ski resort, so that the staff can grasp the situation of the ski resort in real time, so as to respond to emergencies in time.

Overall system design
Ice and snow accident detection system mainly includes the following modules: power module, video acquisition module, data transmission module, central control module, accident detection module, cloud service platform and alarm module. The overall structure of the system is shown in Figure 1. The specific implementation steps of the system are as follows： After system initialization, the video acquisition module transmits the collected image information to the central controller through the data transmission module;  The central controller forwards the data to the accident detection module and controls the system detection module to work;  In the system detection module, firstly, the target detection method based on Gaussian mixture model is used to detect skiers; secondly, the improved Kalman filter tracking algorithm is used to track the target; finally, the collision detection algorithm based on bounding box is used for collision detection;  When all videos from two perspectives are judged as suspected collision accident, the accident detection module sends the detection results to the central controller, which forwards the data to the cloud service platform;  The cloud service platform calculates the collision results to determine whether there are ice and snow accidents;  If there is an accident, the cloud service platform will feed back the results to the system and display the accident location and other information;  System alarm;

power supply module
The power module supplies power for the system, which is the basis of the normal operation of the whole system. Because the power module works in the low temperature environment of ice and snow, the selection of power supply is very important. The power supply uses rechargeable lithium battery to charge the single chip microcomputer chip, which can maintain 80% of the power in low temperature environment.

video capture module
A number of omni-directional monitoring cameras are set up on the skiing track to detect the condition of the ski track in real time through the monitoring video, and obtain the image information in the area to be detected, which provides the basis for the follow-up work. The video acquisition module uses 3 multiple HD webcams to monitor the condition of the ski resort in real time, and sends the image information of the ski resort to the central controller through the data transmission module.

data transmission module
The system uses two data transmission modules, one of which is used to transmit the image information collected by the video capture module to the central control module, and the other is used for data transmission between the central controller and the cloud service platform. The data transmission module includes two parts: data sending module and data receiving module. The data transmission module adopts WiFi data communication mode, which can realize the data sharing and timely communication between devices with short distance and low rate. The wireless transmission terminal connects the alarm information with the cloud platform of intelligent and safe power consumption hidden danger monitoring in real time through the Internet of things, which has the characteristics of high precision, high reliability, fast response and various communication modes.

central control module
The central control module is the core of the system and the brain of the whole system. It connects the various modules of the system together. Its main functions are: to receive the video image information transmitted by the video acquisition module; to control the normal operation of the alarm module and accident detection module; to forward the two-way data. The embedded A8 ARM microprocessor is used in the central control module. The arm structure is superior in power consumption, price and performance, and can achieve high cost performance.

cloud service platform
The central control module and cloud service platform [1] are connected through 5G network for realtime two-way data transmission, so that the management personnel of the ski resort can grasp the location information of skiers in the ski resort in real time, and provide simple interpersonal interaction page. When an accident occurs, it can alarm and send the location information of the accident, which is convenient for rescue.

alarm module
When the accident occurs, the alarm module starts to realize the sound and light alarm.
The connection diagram of the system is shown in Figure 2.

Software design
The accident detection module in the system is mainly realized by software. The software includes image preprocessing, target detection, target tracking and collision detection. Software implementation process: firstly, the target detection model based on Gaussian mixture model is established, the foreground and target area are extracted, and the target area is refined by the fusion of multiple features (color, texture, edge and other features), so as to extract the accurate target, and obtain the position and size of the target in the image, and then Kalman filter combined with average drift tracking is used The algorithm can track the target, obtain the trajectory and state of the moving target, and finally realize the ice snow accident detection through the directed bounding box collision detection algorithm. The software workflow is shown in Figure 3.

target detection method
In order to achieve better detection results, it is necessary to preprocess the image data collected by the video capture terminal. Histogram equalization image enhancement method can be selected to increase the image contrast of skiers and snow fields, and improve the image quality information. Gaussian mixture model [2] is used to model the preprocessed image, and then morphological operation method [3] is used to process the motion saliency map obtained by statistical histogram to extract the rough information of the foreground target area. Through HSI color features, LBP texture features and edge features, the shadow part of the foreground target area is optimized to obtain the accurate foreground target.

target tracking method
In the target tracking part, an improved tracking algorithm combining Kalman filter and mean shift is adopted [4] . Firstly, the parameters of Kalman filter are initialized and the target position is predicted. Then, the iterative process of mean shift is started as the starting point until convergence, and the real target position is obtained, so as to update the Kalman filter. This is repeated until the position of the target in the next frame is found, and the parameters such as target velocity, acceleration and motion trajectory are obtained.

Collision detection
Collision detection uses a collision detection algorithm based on a directed bounding box [5] . Two surveillance cameras are set in the area to be detected to perform accident detection separately. If the same target in the two perspectives has a directed bounding box collision, can be preliminarily determined as a suspected collision accident; Then through the detection of the degree of collision to finally determine whether it is an accident that requires rescue. According to the relationship between momentum [6] and the degree of collision, the degree of collision is divided into three levels in advance: light collision, moderate collision and severe collision. When a minor collision is detected, the system does not deal with it. When a moderate or severe collision is detected, the system alarms. Rescuers can take different rescue measures according to the degree of collision. And when multiple accidents occur at the same time, the order of rescue is distinguished according to the degree of collision.
The specific implementation process: When the system detects a suspected collision accident, upload the speed, acceleration and other data obtained in the target tracking to the cloud service platform. The cloud service platform calculates the target momentum and matches it according to the pre-divided collision level to determine the degree of collision of the target. If a minor collision occurs, the system does not handle it. If a moderate or severe collision occurs, it means an ice and snow accident has occurred. The cloud service platform feeds back the results to the system, the system  Figure.4 Incident detection process

5.Conclusion
This paper designs an ice and snow accident detection system, introduces the composition of the system and the functions of each part in detail, expounds the design ideas of hardware and software, combines the embedded system with the computer vision field, and promotes the intelligent monitoring video. It avoids the disadvantages of slow manual detection and inaccurate detection, and also provides a new method for the research of ice and snow accident detection, which has very broad practical value.


Design of real-time cow behavior monitoring system based on wireless sensor networks and K-Mmeans clustering algorithm

Introduction: The present article is the product of the research whose code CS20.04, carried out during 2020. This work was supported by the Institute of Information Technology (IOIT), Vietnam Academy of Science and Technology (VAST).
Problem: Animal monitoring is a significant problem in the agricultural sector. The primary purpose is to monitor the health of animals regularly. Consequently, animal welfare and product quality could be improved, leading to an improvement in profit. Cow behavior recognition system was considered as the right solution for cow monitoring. The requirements for this kind of system are economical, high performance, and real-time.
Objective: The research objective is to design a real-time cow monitoring system based on wireless sensor networks and the K-means clustering algorithm.
Methodology: A wireless sensor node was designed to measure the collar-mounted acceleration data using an accelerometer. Firstly, the collected data were classified into three classes based on the VeDBA (Vector of Dynamic Body Acceleration) feature using the K-means algorithm. Then, the thresholds for VeDBA in the previous step were used to classify new data.
Results: Three behaviors (including feeding, lying, and standing) were classified in real-time with the accuracy of classification about 89%.

Conclusion: The proposed system could be adapted in monitoring cow in real-time, the behavior classification could be implemented on the microcontroller. The results confirmed the reliability of the proposed system.
Originality: The behavior classification could be implemented on the microcontroller for the first time in monitoring cow.
Limitations: Only three behaviors were classified in the experiment.

INTRODUCTION
Livestock production is an essential source within the food supply chain, and animal monitoring is a significant problem in livestock. The primary purpose is to monitor the health of animals regularly. Consequently, animal welfare and product quality could be improved, leading to improved profit [1]. system was considered one of the promising solutions for cow monitoring [4][5][6][7][8][9][10]. The requirements for this kind of system are that it should be economical, high performance, and provide real-time data. Increased performance means the system could detect and classify cow behaviors accurately.
Due to its small size, low cost, and low power consumption, the sensor is convenient for measuring a variety of information and is widely used in modern agriculture.
In this paper, a wireless sensor node was designed to measure the collar-mounted acceleration data of a cow using an accelerometer. Firstly, the collected data were classified into three classes based on the VeDBA (Vector of Dynamic Body Acceleration) feature using the K-means algorithm. Then, the thresholds for VeDBA in the previous step were used to classify new data. The proposed system, using wireless sensor networks, could be adapted to cow monitoring in real-time; the behavior classification could be implemented on the microcontroller with the accuracy of classification in the region of 89%. Three behaviors could be classified using the proposed system, including feeding, lying, and standing.

Construction of wireless sensor networks for livestock behavior monitoring
The proposed system uses two wireless sensor networks. The first one is a 2.4GHz    The DS1307 real-time module connects to Arduino Mega via I2C protocol. Using the pulse signal taken from Arduino Mega, it is reasonable to increase the synchronization between the internal counter in the Arduino and the counter of the module, which increases timing accuracy and reduces the workload for Arduino.
An EEPROM is connected to the Arduino via I2C interface; the Arduino can control the signal pulse through the SCL pin, so that the data, when converted to EEPROM for writing, is more synchronous, more stable, thereby ensuring the most stable data possible.
The power block maintains the power source for the entire collar device. It has components to protect the device, such as avoiding upstream current or overcharging the battery, causing a battery explosion that could cause injury. The power block has a design to add a charging port to charge the battery, making the device rechargeable without removing the outer shell.

Classification of cow behavior using the K-means clustering algorithm
There are three behaviors of the cow in the experiment: • Feeding: The animal is eating in the eating area.
• Lying: The animal is in a lying down position.
• Standing: The animal stands on its four legs.
The collar device ( Figure 2) collected accumulated acceleration data based on the accelerometer sensor. Figure 4 shows the accelerometer data samples under three axes corresponding to three behaviors: standing, lying, and feeding.  The K-means algorithm is suitable for distinguishing cow behavior data because each data point (record) in this case represents only one behavior (in other words, there is only one label for a data point). The K-means algorithm conforms to a certain idea of behavior recognition in real-time and is simple to implement. Moreover, this algorithm guarantees convergence and easily adapts to new behavior data.
The main ideas are: • Collecting acceleration data.
• Generating a number of clusters; 3 in this case for three behaviors.
• Finding centroids and grouping objects (acceleration data) to its closet clusters.
• Finding centroids and grouping objects based on the use of VeDBA.
The Constant threshold A for VeDBA was calculated; if the VeDBA value is greater than threshold A, it means acceleration data of high activity (feeding), the inverse corresponds to low activity.
Low activity behavior is lying or standing. We calculated threshold B for the static acceleration component of the y-axis (SCAY: Static Component of the Acceleration in the Y-axis). If the value is greater than threshold B, the behavior is determined to be standing; with the inverse being lying down.
To calculate VeDBA, we need the DBA (Dynamic Body Acceleration). The DBA represents the energy consumed by cattle in one direction. (1) where: • i = x, y, z represent the acceleration axes.
• i A is the static sensor value.
• * i A is the value of acceleration data.
• t i µ is the average value of acceleration data and is calculated by (2). (2)

Source: own work
Information about SCAY characteristics is described in Figure 7. With SCAY, three behaviors show some differences in values. Figure 8 shows the relationship between SCAY and VeDBA (horizontal axis) before using K-means. Figure 9 shows the relationship between SCAY and and VeDBA using K-means to find three different clusters. The three cluster centers are defined by: Source: own work Figure 10 shows the calculation of the VeDBA feature with the test data as (5). Figure 11 shows the relationship between SCAY and VeDBA before using K-means to find three different clusters. The three cluster centers, defined by a training process, would be used to estimate three behaviors.    Figure 12. Estimated (up) and actual (down) behavior index (3 is feeding, 2 is standing, and 1 is lying).

Source: own work
Thus, we proposed the system to classify behavior on the microcontroller in real-time as follows: • Step 1: Collect acceleration data under three axes every second (1 frame data obtained).
• Step 3: Calculate the distance to 3 center clusters (values of cluster centers in the space < VeDBA; SCAY> have been pre-loaded with the microcontroller).
• Step 4: Determine the minimum distance value (closet to the center of cluster), label the corresponding behavior.
• Step 5: Send classification results to the gateway.

DISCUSSION AND CONCLUSIONS
Wang et al. [10] classified various cow behaviors based on the AdaBoost algorithm.
The data in their work are leg-mounted acceleration data, sampled at 1 Hz. The average accuracy of their system for predictions of cow behaviors was about 86%, lower compared to this work's 89%. However, our system currently classifies three behaviors, less than Wang et al. [10] with seven behaviors. If we extend the number of behaviors to classify, the overall performance might change as well.
Phung et al. [13] re-used a dataset from [10]. They proposed a system using a Gradient Boosted Decision Tree algorithm to classify seven behaviors with an overall accuracy of about 96%, higher than our result. The performance of our work was also not better than [3,13,14]. As compensation, the advantage of our work compared to [10,13] is cow behavior can be classified on the microcontroller to classify behavior in real-time. The trade-off is the lower performance of classification. Fortunately, the difference is not significant since we reached 89% accuracy. Our results in predicting three behaviors can be applied in real-time systems such as the proposal of [18,19].
To ensure the node's long-term operation, the node's design should consider maintaining a constant input voltage and reducing energy consumption as much as possible. The node's size should be as small as possible and easy to install to minimize interference to the animals. In terms of communication, all nodes in the network use the same frequency to transmit and receive, which will cause channel competition and cause transmission failure to reduce the probability of successful transmission.
Therefore, the capacity problem of wireless sensor network transmission with a single frequency is more prominent.
Energy management is equally important in software design. Energy consumption is required for sensor reading, data transmission and data processing. However, each link's energy consumption is different, so it is necessary to consider efficient programming to further reduce energy consumption comprehensively. Dynamic node management should also be implemented; when old nodes fail, new nodes join to ensure the orderly progress of the dynamic process. Additionally wireless network reprogramming should be supported to perform node remote control updates, and ensure a single node failure will not affect the reliability of the entire network.
Sensor installation problems need to be further improved. Sensor nodes may be used in extremely harsh environments (such as direct sunlight, rain, water mist, animal friction damage, etc.). Packaging and protection are essential.
This paper has proposed a real-time cow monitoring system based on wireless sensor networks and the K-means clustering algorithm to monitor three cow behaviors, including feeding, lying, and standing. The system is designed using the wireless sensor is based on an accelerometer and K-means algorithm with a classification accuracy of about 89%. In the future, we will classify more behaviors within our systems.


Visualizing Evolving Trees

Evolving trees arise in many real-life scenarios from computer file systems and dynamic call graphs, to fake news propagation and disease spread. Most layout algorithms for static trees do not work well in an evolving setting (e.g., they are not designed to be stable between time steps). Dynamic graph layout algorithms are better suited to this task, although they often introduce unnecessary edge crossings. With this in mind we propose two methods for visualizing evolving trees that guarantee no edge crossings, while optimizing (1) desired edge length realization, (2) layout compactness, and (3) stability. We evaluate the two new methods, along with five prior approaches (three static and two dynamic), on real-world datasets using quantitative metrics: stress, desired edge length realization, layout compactness, stability, and running time. The new methods are fully functional and available on github.

Introduction
Dynamic graph visualization is used in many fields including social networks [28], bibliometric networks [48], software engineering [14], and pandemic modeling [7]; see the survey by Beck et al. [10]. Here we focus on a special case, evolving trees. In evolving trees the dynamics are captured only by growth (whereas in general dynamic graphs, nodes and edges can also disappear). While this is a significant restriction of the general dynamic graph model, evolving trees are common in many domains including the Tree of Life [36] and the Mathematics Genealogy Graph [35]. An evolving tree can also model disease spread, where nodes correspond to infected individuals and a new node v is added along with an edge to existing node u if u infected v. Visualizing this process can help us see how the infection spreads, the rate of infection, and to identify "super-spreaders." There are several methods and tools that can be used to visualize evolving trees [2,15,16,38], however, most of them have limitations that can impact their usability in this domain. Some represent nodes only as points ignoring labels [15,16], which makes them less useful in real-life applications where it is important to see what each node represents. Others utilize the level-by-level approach for drawing hierarchical graphs [27,40], which does not capture the underlying graph structure well. Force-directed algorithms tend to better capture the underlying graph structure [31], although they may introduce unnecessary edge crossings. With this in mind, we propose two methods for drawing crossingfree evolving trees that optimize the following desirable properties: 1. Desired edge length realization: The Euclidean distance between two nodes u and v in the layout should realize the corresponding pre-specified edge length l(u, v), or be uniform when no additional information is given. This is important in several domains, e.g., when visualizing phylogenetic trees [6], where the edge length represents evolutionary distance between two species. 2. Layout compactness: The drawing area should be proportional to the total area needed for all the labels. A good visualization should have the labeled graph drawn in a compact way [39]. This prevents the trivial solution of scaling the layout until all overlaps and crossings are removed, which can create vast empty spaces in the visualization. 3. Stability: Between time steps, nodes should move as little as possible. This helps the viewer maintain a mental map of the graph [37]. If the graph moves around too much, it is difficult to see where new nodes and edges are added and we lose the context of the new node's relation to the rest of the graph.
We propose two force-directed methods that ensure no edge crossings and optimize desired edge length, compactness and stability. Minimizing edge crossings is important in graph readability [42], and since we work with trees, a layout without edge crossings is possible and desirable. We use two trees extracted from Tree of Life [36] and the Mathematics Genealogy [35] projects to demonstrate the new methods and quantitatively evaluate their performance, measuring desired edge length realization, compactness, stability, stress, crossings, and running time. We also evaluate the performance of five earlier methods, showing the two proposed methods perform well overall; see

Related Work
Dynamic graph drawing has a long history [11,46] and two broad categories: offline and online. In the easier offline setting we assume that all the data about the dynamics is known in advance. Algorithms for offline dynamic visualization use different approaches including combining all time-slice instances into a single supergraph [18][19][20], connecting the same node in consecutive time-slices and optimizing them simultaneously [22][23][24], providing animation [4], and showing small multiples type visualization [3]. DynNoSlice by Simonetto et al. [44] is one of the most recent approaches for this setting and is different from the prior methods as it does not rely on discrete time-slices.
Online dynamic graph drawing deals with the harder problem -when we do not know in advance what changes will occur. One can optimize the current view, DynNoSlice [44] DynaGraph [40] Dagre [27] Radial [49] ImPrEd [ given what has happened in the past, but cannot look into the future, as the information is not available. Cohen et al. [15,16] and Workman et al. [50] describe algorithms for dynamic drawing of trees that place nodes that are equidistant from the root on the same level (same y coordinate). These algorithms do not take edge lengths into consideration, and the hierarchical nature of the layout can lead to exponential differences between the shortest and longest edges.
DynaDAG is an online graph drawing method for drawing dynamic directed acyclic graphs as hierarchies [40]. This method moves nodes between adjacent ranks based on the median sort. It was not specifically developed 5 for trees and may introduce crossings; see Fig. 2. Other approaches for online dynamic graph drawing have maintained the horizontal and vertical position of nodes [37], used node aging methods [29], and adapted multilevel approaches [17] (using FM 3 [30]). Online approaches have also been implemented on the GPU [25]. However, these methods do not guarantee crossing-free layouts for trees and do not take into account desired edge lengths.  Dagre is a multi-phase algorithm for drawing directed graphs based on [27]. The initial phase finds an optimal rank assignment using the network simplex algorithm. Then it sets the node order within ranks by an iterative heuristic incorporating a weight function and local transpositions to reduce crossings (via the barycenter heuristic) [32]. However, since Dagre draws graphs in a hierarchical structure, the edge lengths may vary arbitrarily; see Fig. 2.
The radial layout implemented in yFiles [49] displays each biconnected component in a circular fashion 6 . Radial layouts were introduced by Kar et al. [33] for static graphs. Dougrusoz et al. [21] described an interactive tool for dynamic graph visualization based on the radial layout. Six and Tollis [45] adapted the radial idea to circular drawings of static biconnected graphs and experimentally showed that their layout has fewer edge crossings. Kaufmann et al. [34] extended this model to handle dynamic graphs, providing the basis of the yFiles radial implementation. Pavlo et al. [41] adapted the idea to make the radial layout computation parallelizable. Bachmaier [5] further improved the radial layout algorithm for static graphs by adapting the hierarchical approach [47] to minimize edge crossings. Radial layout methods have more freedom than the traditional level-by-level tree layout methods. Nevertheless, they are still constrained and can result in unstable visualization for dynamic graphs in general and evolving trees in particular; see Fig. 3.
Force-directed algorithms [18-20, 43, 44] underlie many static and dynamic graph visualization methods. Unlike hierarchical and radial approaches, forcedirected algorithms place nodes at arbitrary positions, and so tend to generate more compact layouts that better realize desired edge lengths. By adjusting forces appropriately, one can also generate stable layouts by this approach. In particular, ImPrEd, by Simonetto et al. [43], provides a force-directed approach to improve a given initial layout, without introducing new edge crossings. To the best of our knowledge, there are no force-directed methods for evolving trees.  Fig. 3: A radial layout of a 400-node evolving tree of life (a) and the layout after adding 100 nodes (b). As most of the growth occurred on the right side, it is easy to see the instability -a lot of movement was needed to accommodate it. Also, nodes are too close to each other if labeled.

Algorithms for Visualizing Evolving Trees
Here, we describe two force-directed algorithms for evolving tree visualization, DynaCola and DynaSafe, that realize desired edge lengths without creating crossings, and optimize compactness and stability. DynaCola avoids edge crossings by creating and maintaining a "collision region" for each edge. While collision detection/prevention is usually applied to nodes, by carefully applying it to the edges we can prevent all edge crossings. DynaSafe prevents edge crossings with a "safe" coordinate update at every step of the algorithm. Before updating a coordinate, it first checks whether the update will introduce a crossing and then limits the update magnitude to avoid the crossing.

DynaCola
DynaCola stands for Dynamic Collision, as the algorithm uses the collision forces to prevent edge crossings. This is a force-directed algorithm, augmented with edge-regions used to prevent crossings; see Algorithm 1 in the Appendix. Recall that we are gradually growing a tree, one node at a time, while maintaining a crossing-free layout and optimizing desirable properties (desired edge lengths, compactness, stability). The DynaCola force-directed algorithm relies on the following forces and is implemented in d3.js [12]: -A force f E for each edge, to realize the desired edge length. The strength of this force is proportional to the difference between the edge distance in the layout and the desired edge length.
-A general repulsive force f R defined for all pairs of nodes and implemented with the Barnes-Hut quad-tree data structure [8]. This helps realize the global structure of the underlying tree. -A collision force f C for each edge, described in details below. This force prevents edge crossings.
-A gravitational force f G that attracts all nodes to the center of mass. This force draws the nodes closer together and improves compactness.
To ensure that no edges cross during an update, we define a collision region around each edge: if any edge/node moves too close to another edge, it will be pushed away. To create a collision region for an edge e = (u, v), we can create collision circles with diameter equal to the length of e for both u and v. Then every point of e will be either inside the collision region of u or v. However, the sum of all collision regions for all nodes will be unnecessarily large and the layout will not be compact. With the help of subdivision nodes along the edges, we can reduce the sum of all collision regions. Let e = (u, v) be an edge in the graph. We use a set of subdivision nodes V s = {v 1 , v 2 , · · · , v k } and replace the edge We assign the desired edge length of an edge in E s equal to l(u, v)/|E s |, where l(u, v) is the desired edge length. In general, the number of subdivision nodes per edge should be a small constant n s (by default n s = 1), since the complexity of the algorithm increases as n s increases. Also, note that n s determines the number of bends per edge (no bends when n s = 0, one bend when n s = 1, and so on). Note that, the collision force does not follow any hard constraint, even after having a collision region edge crossings may happen. If existing edges introduce crossings, then we roll back to previous crossing-free coordinates.
When a new node is added to the tree, a new edge also is added, with one of its endpoints already placed. To place the new node, we randomly sample a set of 100 nearby points at a distance equal to the desired edge length, trying to find a crossing-free position. If we cannot find such a suitable point, we gradually reduce the distance and repeat the search until we find a crossing free position. Once the new node has been placed, we subdivide its adjacent edge as described above.

DynaSafe
DynaSafe stands for Dynamic Safety, as the algorithm prioritizes safe moves and will not make a move if it introduces an edge crossing, see Algorithm 2 in Appendix. DynaSafe is also a force-directed algorithm, however, it differs from DynaCola as it draws straight-line edges (rather than edges with bends). The algorithm utilizes the following forces and is implemented in d3.js [12] -A force f E for each edge that is similar to DynaCola.
-A stress-minimizing force f S on every pair of nodes not connected by an edge, used to improve global structure. The desired distance is the shortest-path distance between the pair, and the magnitude of the force is proportional to the difference between the realized and desired distance.
-A repulsive force that is similar to DynaCola.
-A gravitational force that is similar to DynaCola.
DynaSafe prevents edge crossings from occuring at any time by updating the coordinates safely: if the proposed new coordinate of a node introduces crossings, we gradually reduce the magnitude of the movement until the crossing is avoided. To place the new node, we randomly sample a set of 100 nearby points to find a crossing-free position for its adjacent edge. If we cannot find a crossing free position using the sample points, we continuously reduce the edge length until we find a crossing free position. Once the node is added, an iteration of forcedirected algorithm optimizes the layout (again without introducing crossings).
By the nature of force-directed algorithms, after one phase of force computations each node has a proposed new position. Before moving any node to its proposed new position, we check that the move is "safe," i.e., it does not introduce a crossing. If the movement of a node introduces any crossings, then the magnitude of the move is set to p% of the original movement. This is repeated (if needed) at most q times, and if the crossing is still unavoidable then the node is not moved in this phase. By default p = 0.8 and q = 12.

Experimental Evaluation
We evaluate DynaCola and DynaSafe, along with five earlier methods: Dyn-NoSlice, DynaGraph, Dagre, Radial, and ImPrEd. We use two evolving trees to visually compare the results, as well quantitatively evaluate the desired properties.

Datasets
We use two real-world datasets to extract evolving trees for our experiments.
The Tree of Life: captures the evolutionary progression of life on Earth [36]. The underlying data is a tree structure with a natural time component. As a new species evolves, a new node in the tree is added. The edges give the parent-child relation of the nodes, where the parent is the original species, and the child is the new species. We use a subset of this graph with 500 nodes. The maximum node degree of this tree is 5, and the radius is 24.
The Mathematics Genealogy: shows advisor-advisee relationships in the world of mathematics, stretching back to the middle ages [35]. The dataset includes the thesis titles, students, advisors, dates, and number of descendants. The total number of nodes is around 260,000 and is continuously updated. While this data is not quite a tree (or even connected, or planar), we extract a subset to create a tree with 500 nodes. The maximum node degree of this tree is 5 and the radius is 14.

Evaluation Metrics
We use standard metrics for each of our desired properties: desired edge length preservation, compactness, and stability. Additionally, we compute the stress of the drawing and the number of crossings. This gives a total of five quantitative measures. For each of these measures we define a loss function as follows: Desired Edge Length (DEL): To measure how close the realized edge lengths are to the desired edge lengths, we find the mean squared error between these two values. Given the desired edge lengths {l ij : (i, j) ∈ E} and coordinates of the nodes X in the computed layout, we evaluate with the following formula: This measures the root mean square of the relative error as in [1], producing a non-negative number, with 0 corresponding to a perfect realization. For DynaCola we subdivide the edges, to compute DEL, we set the length of the subdivided edges such that the summation of the length of the subdivided edges is equal to the length of the original edge.
Compactness: To measure the compactness of each layout, we use the ratio between the drawing area and the sum of the areas for all labels [9]. We assume that a label is at most 16 characters, as we abbreviate longer labels. The sum of the areas for all labels gives the minimum possible area needed to draw all labels without overlaps (ignoring any space needed for edges). The area of the actual drawing is given by the smallest bounding rectangle, once the drawing has been scaled up until there are no overlapping labels. Once we have this scaled drawing, we find the positions of the nodes with the largest and smallest x and y values (X max,0 , X min,0 , X max,1 and X min,1 ). Using these values we calculate the area of the bounding rectangle.

Compactness loss
This formula produces a non-negative number; the ideal value for this measure is 1 and corresponds to a perfect space utilization.
Stability: To measure stability, we consider how much each of the nodes moved after adding a new node. We then sum the movements of all nodes over all time steps. Since different algorithms use different amounts of drawing areas, we divide the value by the drawing area to normalize the results. This measure is similar to that used in DynNoSlice [44], but since DynNoSlice does not use time slices, it is closer to the measure found in [13]: Here, T is the maximum time (500 in our two datasets). This formula produces a non-negative number; the ideal value is 0 and corresponds to a perfectly stable layout (no movement of any already placed nodes).
Stress: This measure evaluates the global quality of the layout, looking at the differences between the realized distance between any pair of nodes and the actual distance between them. This measure is used in a variety of graph drawing algorithms [13,26,44]: Here, D i,j is the shortest path distance in the graph. This formula produces a non-negative number; the ideal value is 0 and corresponds to a perfect embedding (that captures all graph distances by the realized Euclidean distances).
Edge Crossings: Finally, we measure the number of edge crossings in each of the outputs. Note that our algorithms DynaSafe and DynaCola enforce "no edge crossings" as a hard constraint. However, DynNoSlice and DynaGraph do not have such a constraint and so can and indeed do, introduce crossings. Therefore we include the number of edge crossings for a complete comparison.

Experimental Setup
We compare these algorithms to five previous algorithms: DynNoSlice, Dyna-Graph, Dagre, Radial, and ImPrEd. We note that while Dagre, Radial, and ImPrEd are not specifically designed for dynamic graphs, they can be modified for this purpose. Specifically, we can use the layout of a tree at step i to initialize the layout of the tree at step i + 1, add the new edge, and update the layout.
We consider the simplest case for the desired edge length by using a uniform length of 100 for all edges. This is a necessary parameter for our algorithms DynaCola and DynaSafe, but only needed in the other four algorithms in order to compute the desired edge length measure. To be able to compare our methods to the other four (that do not take desired edge length into account), we set the desired edge length equal to the average edge length obtained in the layout. We then normalize these values for a fair comparison.
The performance of DynNoSlice depends heavily on two parameters, τ and δ that must be tuned. With the help of the authors, we found τ = 16 and δ = 4 worked well for our 500-node trees. The performance of ImPrEd depends on two parameters: repulsion force and the number of iterations. The default values of repulsion force and the number of iterations are equal to one and 200 respectively. We have used the default values. The larger the number of iterations is, the better the output of ImPrEd is. However, the running time increases as the number of iterations increases. We keep the number of iterations equal to 200 since it already takes more than 4 hours to compute the 500-node trees. The performance of DynaCola depends on the number of subdivision nodes n s ; we use n s = 1 for the experiments. For the radial layout algorithm, we have used the default settings in the yFiles [49] implementation. The other algorithms are also used with their default settings. We have implemented our algorithms in d3.js [12]. For other algorithms, we have used the default API. All experiments are conducted in a machine that has macOS 11.3.1 operating system, a 2.3 GHz 8-core Intel core i9 processor, and 32 GB 2667 MHz DDR4 memory.

Results
Both the visual and quantitative results indicate that the two new methods perform well overall; see Fig. 4.

Desired Edge Lengths:
The quantitative results are shown in Table 1. We use green to show the best results and yellow for the second best and indicate that DynNoSlice, DynaCola, and ImPrEd perform well. For the math genealogy 500node tree, ImPrEd is the best. However, both DynNoSlice and ImPrEd have significantly larger running times (measured in hours, rather than minutes or seconds) as discussed below. Moreover, while ImPrEd does well on the math genealogy graph, it does not do well on the tree of life graph. For the math genealogy 500-node tree, DynaCola is the second best and DynNoSlice is third. For the tree of life dataset, DynaCola is the best, DynNoSlice is the second best and DynaSafe is third. DynaGraph has the worst performance -not surprising given that it is a hierarchical layout, which is forced to use some very long edges near the root.  Table 1: Desired edge lengths of math genealogy tree (MG) and tree of life (TOL).

Compactness:
The quantitative results are shown in Table 2 and indicate that DynNoSlice outperforms the rest of the algorithms. DynaCola is second best and DynaSafe is third. Here, Dagre has the worst performance. Although DynNoSlice performs well, it introduces many edge crossings as discussed later. DynaCola layouts have higher compactness than DynaSafe. The absence of stress-related force allows placing nodes closer even if the graph theoretic distance is higher. Consider a path, the layout will be a straight line if stress is minimized. However, a zig-zag layout will provide better compactness.

Stability:
The quantitative results are shown in Table 3 and idicate that Dyna-Cola does best. DynaGraph is second, and DynaSafe is third. The radial layout performs worse in this metric because it rotates the subtrees as more edges are added.

Stress:
The quantitative results are shown in Table 4. In general, DynaSafe does much better on this measure than the rest. Again, ImPrEd performs well       methods are not as fast as the Radial algorithm and not as slow as DynNoSlice, taking about 5 minutes on the 500-node trees.Due to space limitations, we provide more details of running time in the Appendix.

Discussion and Limitations
While there are many algorithms and tools for drawing static trees, only a few can handle dynamic trees well. Among those, even fewer takes edge labels into account while also preventing edge crossings. With this in mind, we described two methods that give better, readable layouts for evolving trees. We compared these two algorithms with others that have been set up for dynamic trees. With respect to the criteria that we have put forward, our algorithms match or exceed each of these algorithms. Fully functional prototypes and videos showing them in action are available online https://ryngray.github.io/dynamic-trees/. Source code and all experimental data can be found on github https://github.com/ abureyanahmed/evolving_tree.
Naturally, our work comes with several limitations that could be addressed in future work.
Anticipating the Future: Currently, the two new methods, DynaCola and DynaSafe perform well for evolving trees, where growth is the only type of change. A natural question is whether these algorithms can be generalized to the more challenging problems of online dynamic tree visualization. Answering such question may need more precise modeling of the graph dynamics. Even though online dynamic graph drawing assumes no knowledge about the actual changes to the graph in the future, some prior knowledge of the graph may be available or predictable in advance. For example, knowing the expected depth or size of a tree or maximum degree of nodes (e.g., from domain knowledge about the specific type of graph) may help the layout algorithm reserve enough space for growth. In general, we anticipate that if one can model the evolving dynamics of the graph (e.g., probabilistically), incorporating knowledge of such dynamics into the drawing algorithm may help improve the resultant drawing; conversely, carefully defining compatible graph dynamics for a particular drawing algorithm will also allow us to identify the limitations of the given algorithm.
Multi-level Label Display: For simplicity, in this work we assume labels to be always shown in the drawing in a fixed font size. In practice, however, labels may come with different levels of importance and different desired font size. In that case, one might prefer to see only important labels displayed first in a zoomed out view of the graph, and later see more labels when zooming in. Incorporate such multi-level label display into the node placement strategy seems like an interesting and relevant problem.
Finding Desired Properties: We have proposed two different algorithms to solve the same evolving tree visualization problem, and each is associated with different benefits. Finding a continuous spectrum of algorithms with tunable parameters to balance the multiple desired properties would provide more flexibility. On the other hand, a careful human-subjects study may also help prioritize existing properties of the drawing, or help identify new desired properties from the specific tasks.
Considering More Dynamic Datasets: The datasets we considered are evolving in nature. For example, in the math genealogy dataset, once an advisee gets related to an advisor, the relationship remains forever. Although we considered only evolving trees, our ideas can be applied to datasets where the elements may get deleted. Applying the algorithms on more dynamic datasets remains future work. Fig. 1 shows a small evolving tree with labels, as obtained by the seven algorithms: DynNoSlice, DynaGraph, Dagre, Radial, ImPrEd, DynaCola, and DynaSafe. Fig. 5 shows the same layouts without the labels, allowing us to see the structure a bit better. Fig. 4 shows the layouts of the tree of life, obtained by DynNoSlice, Dy-naGraph, Dagre, Radial, ImPrEd, DynaCola and DynaSafe. Fig. 6 shows the layouts of math genealogy tree, obtained by DynNoSlice, DynaGraph, Dagre, Radial, ImPrEd, DynaCola and DynaSafe.
DynaCola performs slightly better compared to DynaSafe. However, Dyna-Cola layouts introduce bends. DynaCola layouts may be suitable where compact layouts are preferred. Since Dynasafe has better stress and does not create bends,