Algorithms, Volume 13, Issue 11 (November 2020) – 41 articles

A Pseudo-Random Number Generator (PRNG) is any algorithm generating a sequence of numbers approximating properties of random numbers. These numbers are widely employed in mid-level cryptography and in software applications. Test suites are used to evaluate the quality of PRNGs by checking statistical properties of the generated sequences. These sequences are commonly represented bit by bit. This paper proposes a Reinforcement Learning (RL) approach to the task of generating PRNGs from scratch by learning a policy to solve a partially observable Markov Decision Process (MDP), where the full state is the period of the generated sequence, and the observation at each time-step is the last sequence of bits appended to such states. We use Long-Short Term Memory (LSTM) architecture to model the temporal relationship between observations at different time-steps by tasking the LSTM memory with the extraction of significant features of the hidden portion of the MDP’s states. We show that modeling a PRNG with a partially observable MDP and an LSTM architecture largely improves the results of the fully observable feedforward RL approach introduced in previous work. Full article

Given a Traveling Salesman Problem solution, the best 3-OPT move requires us to remove three edges and replace them with three new ones so as to shorten the tour as much as possible. No worst-case algorithm better than the $\mathsf{\Theta }\left(n^3\right)$ enumeration of all triples is likely to exist for this problem, but algorithms with average case $O\left(n^{3-ϵ}\right)$ are not ruled out. In this paper we describe a strategy for 3-OPT optimization which can find the best move by looking only at a fraction of all possible moves. We extend our approach also to some other types of cubic moves, such as some special 6-OPT and 5-OPT moves. Empirical evidence shows that our algorithm runs in average subcubic time (upper bounded by $O\left(n^{2.5}\right)$) on a wide class of random graphs as well as Traveling Salesman Problem Library (TSPLIB) instances. Full article

We provide numerical evidence that the nonlinear searching algorithm introduced by Wong and Meyer, rephrased in terms of quantum walks with effective nonlinear phase, can be extended to the finite 2-dimensional grid, keeping the same computational advantage with respect to the classical algorithms. For this purpose, we have considered the free lattice Hamiltonian, with linear dispersion relation introduced by Childs and Ge The numerical simulations showed that the walker finds the marked vertex in $O\left(N^{1/4}{log}^{3/4}N\right)$ steps, with probability $O(1/logN)$, for an overall complexity of $O\left(N^{1/4}{log}^{5/4}N\right)$, using amplitude amplification. We also proved that there exists an optimal choice of the walker parameters to avoid the time measurement precision affecting the complexity searching time of the algorithm. Full article

Here we study a short-sea feeder network design problem based on mother and daughter vessels. The main feature of the studied system is performing transshipment of cargo between mother and daughter vessels at appropriate locations at sea. This operation requires synchronization between both types of vessels as they have to meet at the same location at the same time. This paper studies the problem of designing a synchronized feeder network, explicitly accounting for the effect of uncertain travel times caused by harsh weather conditions. We propose an optimization-simulation framework to find robust solutions for the transportation system. The optimization model finds optimal routes that are then evaluated by a discrete-even simulation model to measure their robustness under uncertain weather conditions. This process of optimization simulation is repeated until a satisfactory condition is reached. To find even better solutions, we include different performance-improving strategies by adding robustness during route generation or exploiting flexibility in sailing speed to recover from delays. We apply the solution method to a case based on realistic data from a Norwegian shipping company. The results show that the method finds near-optimal solutions that offer robustness against schedule perturbations due to harsh weather. They also highlight the importance of considering uncertainty when designing a short-sea feeder network with transshipment at sea. Full article

We develop a family of three-step sixth order methods with generic weight functions employed in the second and third sub-steps for solving nonlinear systems. Theoretical and computational studies are of major concern for the convergence behavior with applications to special cases of rational weight functions. A number of numerical examples are illustrated to confirm the convergence behavior of local as well as global character of the proposed and existing methods viewed through the basins of attraction. Full article

Feature Analysis has become a very critical task in data analysis and visualization. Graph structures are very flexible in terms of representation and may encode important information on features but are challenging in regards to layout being adequate for analysis tasks. In this study, we propose and develop similarity-based graph layouts with the purpose of locating relevant patterns in sets of features, thus supporting feature analysis and selection. We apply a tree layout in the first step of the strategy, to accomplish node placement and overview based on feature similarity. By drawing the remainder of the graph edges on demand, further grouping and relationships among features are revealed. We evaluate those groups and relationships in terms of their effectiveness in exploring feature sets for data analysis. Correlation of features with a target categorical attribute and feature ranking are added to support the task. Multidimensional projections are employed to plot the dataset based on selected attributes to reveal the effectiveness of the feature set. Our results have shown that the tree-graph layout framework allows for a number of observations that are very important in user-centric feature selection, and not easy to observe by any other available tool. They provide a way of finding relevant and irrelevant features, spurious sets of noisy features, groups of similar features, and opposite features, all of which are essential tasks in different scenarios of data analysis. Case studies in application areas centered on documents, images and sound data demonstrate the ability of the framework to quickly reach a satisfactory compact representation from a larger feature set. Full article

In view of difficulty in application of optical flow based human action recognition due to large amount of calculation, a human action recognition algorithm I3D-shufflenet model is proposed combining the advantages of I3D neural network and lightweight model shufflenet. The 5 × 5 convolution kernel of I3D is replaced by a double 3 × 3 convolution kernels, which reduces the amount of calculations. The shuffle layer is adopted to achieve feature exchange. The recognition and classification of human action is performed based on trained I3D-shufflenet model. The experimental results show that the shuffle layer improves the composition of features in each channel which can promote the utilization of useful information. The Histogram of Oriented Gradients (HOG) spatial-temporal features of the object are extracted for training, which can significantly improve the ability of human action expression and reduce the calculation of feature extraction. The I3D-shufflenet is testified on the UCF101 dataset, and compared with other models. The final result shows that the I3D-shufflenet has higher accuracy than the original I3D with an accuracy of 96.4%. Full article

Predicting groundwater availability is important to water sustainability and drought mitigation. Machine-learning tools have the potential to improve groundwater prediction, thus enabling resource planners to: (1) anticipate water quality in unsampled areas or depth zones; (2) design targeted monitoring programs; (3) inform groundwater protection strategies; and (4) evaluate the sustainability of groundwater sources of drinking water. This paper proposes a machine-learning approach to groundwater prediction with the following characteristics: (i) the use of a regression-based approach to predict full groundwater images based on sequences of monthly groundwater maps; (ii) strategic automatic feature selection (both local and global features) using extreme gradient boosting; and (iii) the use of a multiplicity of machine-learning techniques (extreme gradient boosting, multivariate linear regression, random forests, multilayer perceptron and support vector regression). Of these techniques, support vector regression consistently performed best in terms of minimizing root mean square error and mean absolute error. Furthermore, including a global feature obtained from a Gaussian Mixture Model produced models with lower error than the best which could be obtained with local geographical features. Full article

Associative classification (AC) is a mining technique that integrates classification and association rule mining to perform classification on unseen data instances. AC is one of the effective classification techniques that applies the generated rules to perform classification. In particular, the number of frequent ruleitems generated by AC is inherently designated by the degree of certain minimum supports. A low minimum support can potentially generate a large set of ruleitems. This can be one of the major drawbacks of AC when some of the ruleitems are not used in the classification stage, and thus (to reduce the rule-mapping time), they are required to be removed from the set. This pruning process can be a computational burden and massively consumes memory resources. In this paper, a new AC algorithm is proposed to directly discover a compact number of efficient rules for classification without the pruning process. A vertical data representation technique is implemented to avoid redundant rule generation and to reduce time used in the mining process. The experimental results show that the proposed algorithm archives in terms of accuracy a number of generated ruleitems, classifier building time, and memory consumption, especially when compared to the well-known algorithms, Classification-based Association (CBA), Classification based on Multiple Association Rules (CMAR), and Fast Associative Classification Algorithm (FACA). Full article

Pervasive data have become a key source of information for mobility and transportation analyses. However, as a secondary source, it has a different methodological origin than travel survey data, usually relying on unsupervised algorithms, and so it requires to be assessed as a dataset. This assessment is challenging, because, in general, there is not a benchmark dataset or a ground truth scenario available, as travel surveys only represent a partial view of the phenomenon and suffer from their own biases. For this critical task, which involves urban planners and data scientists, we study the design space of the visualization of cross-origin, multivariate flow datasets. For this purpose, we introduce the Modalflow system, which incorporates and adapts different visualization techniques in a notebook-like setting, presenting novel visual encodings and interactions for flows with modal partition into scatterplots, flow maps, origin-destination matrices, and ternary plots. Using this system, we extract general insights on visual analysis of pervasive and survey data for urban mobility and assess a mobile phone network dataset for one metropolitan area. Full article

Pulse wave signal sensed over the radial artery on the wrist is a crucial physiological indicator in disease diagnosis. The sensor array composed of multiple sensors has the ability to collect abundant pulse wave information. As a result, it has gradually attracted the attention of practitioners. However, few practical methods are used to obtain a one-dimensional pulse wave from the sensor array’s spatial multi-dimensional signals. The current algorithm using pulse wave with the highest amplitude value as the significant data suffers from low consistency because the signal acquired each time differs significantly due to the sensor’s relative position shift to the test area. This paper proposes a processing method based on time series similarity, which can take full advantage of sensor arrays’ spatial multi-dimensional characteristics and effectively avoid the above factors’ influence. A pulse wave acquisition system (PWAS) containing a micro-electro-mechanical system (MEMS) sensor array is continuously extruded using a stable dynamic pressure input source to simulate the pulse wave acquisition process. Experiments are conducted at multiple test locations with multiple data acquisitions to evaluate the performance of the algorithm. The experimental results show that the newly proposed processing method using time series similarity as the criterion has better consistency and stability. Full article

Many modern statistically efficient methods come with tremendous computational challenges, often leading to large-scale optimisation problems. In this work, we examine such computational issues for recently developed estimation methods in nonparametric regression with a specific view on image denoising. We consider in particular certain variational multiscale estimators which are statistically optimal in minimax sense, yet computationally intensive. Such an estimator is computed as the minimiser of a smoothness functional (e.g., TV norm) over the class of all estimators such that none of its coefficients with respect to a given multiscale dictionary is statistically significant. The so obtained multiscale Nemirowski-Dantzig estimator (MIND) can incorporate any convex smoothness functional and combine it with a proper dictionary including wavelets, curvelets and shearlets. The computation of MIND in general requires to solve a high-dimensional constrained convex optimisation problem with a specific structure of the constraints induced by the statistical multiscale testing criterion. To solve this explicitly, we discuss three different algorithmic approaches: the Chambolle-Pock, ADMM and semismooth Newton algorithms. Algorithmic details and an explicit implementation is presented and the solutions are then compared numerically in a simulation study and on various test images. We thereby recommend the Chambolle-Pock algorithm in most cases for its fast convergence. We stress that our analysis can also be transferred to signal recovery and other denoising problems to recover more general objects whenever it is possible to borrow statistical strength from data patches of similar object structure. Full article

We propose and investigate two new methods to approximate $f\left(\mathbf{A}\right)\mathbf{b}$ for large, sparse, Hermitian matrices $\mathbf{A}$. Computations of this form play an important role in numerous signal processing and machine learning tasks. The main idea behind both methods is to first estimate the spectral density of $\mathbf{A}$, and then find polynomials of a fixed order that better approximate the function f on areas of the spectrum with a higher density of eigenvalues. Compared to state-of-the-art methods such as the Lanczos method and truncated Chebyshev expansion, the proposed methods tend to provide more accurate approximations of $f\left(\mathbf{A}\right)\mathbf{b}$ at lower polynomial orders, and for matrices $\mathbf{A}$ with a large number of distinct interior eigenvalues and a small spectral width. We also explore the application of these techniques to (i) fast estimation of the norms of localized graph spectral filter dictionary atoms, and (ii) fast filtering of time-vertex signals. Full article

There are two reasons to have an efficient algorithm for identifying all right-maximal Lyndon substrings of a string: firstly, Bannai et al. introduced in 2015 a linear algorithm to compute all runs of a string that relies on knowing all right-maximal Lyndon substrings of the input string, and secondly, Franek et al. showed in 2017 a linear equivalence of sorting suffixes and sorting right-maximal Lyndon substrings of a string, inspired by a novel suffix sorting algorithm of Baier. In 2016, Franek et al. presented a brief overview of algorithms for computing the Lyndon array that encodes the knowledge of right-maximal Lyndon substrings of the input string. Among those presented were two well-known algorithms for computing the Lyndon array: a quadratic in-place algorithm based on the iterated Duval algorithm for Lyndon factorization and a linear algorithmic scheme based on linear suffix sorting, computing the inverse suffix array, and applying to it the next smaller value algorithm. Duval’s algorithm works for strings over any ordered alphabet, while for linear suffix sorting, a constant or an integer alphabet is required. The authors at that time were not aware of Baier’s algorithm. In 2017, our research group proposed a novel algorithm for the Lyndon array. Though the proposed algorithm is linear in the average case and has $O(nlog(n\left)\right)$ worst-case complexity, it is interesting as it emulates the fast Fourier algorithm’s recursive approach and introduces $\tau$-reduction, which might be of independent interest. In 2018, we presented a linear algorithm to compute the Lyndon array of a string inspired by Phase I of Baier’s algorithm for suffix sorting. This paper presents the theoretical analysis of these two algorithms and provides empirical comparisons of both of their C++ implementations with respect to the iterated Duval algorithm. Full article

In this work, a deep Gaussian process (DGP) based framework is proposed to improve the accuracy of predicting flight trajectory in air traffic research, which is further applied to implement a probabilistic conflict detection algorithm. The Gaussian distribution is applied to serve as the probabilistic representation for illustrating the transition patterns of the flight trajectory, based on which a stochastic process is generated to build the temporal correlations among flight positions, i.e., Gaussian process (GP). Furthermore, to deal with the flight maneuverability of performing controller’s instructions, a hierarchical neural network architecture is proposed to improve the modeling representation for nonlinear features. Thanks to the intrinsic mechanism of the GP regression, the DGP model has the ability of predicting both the deterministic nominal flight trajectory (NFT) and its confidence interval (CI), denoting by the mean and standard deviation of the prediction sequence, respectively. The CI subjects to a Gaussian distribution, which lays the data foundation of the probabilistic conflict detection. Experimental results on real data show that the proposed trajectory prediction approach achieves higher prediction accuracy compared to other baselines. Moreover, the conflict detection approach is also validated by a obtaining lower false alarm and more prewarning time. Full article

Stability of persistence diagrams under slight perturbations is a key characteristic behind the validity and growing popularity of topological data analysis in exploring real-world data. Central to this stability is the use of Bottleneck distance which entails matching points between diagrams. Instances of use of this metric in practical studies have, however, been few and sparingly far between because of the computational obstruction, especially in dimension zero where the computational cost explodes with the growth of data size. We present a novel efficient algorithm to compute dimension zero bottleneck distance between two persistent diagrams of a specific kind which runs significantly faster and provides significantly sharper approximates with respect to the output of the original algorithm than any other available algorithm. We bypass the overwhelming matching problem in previous implementations of the bottleneck distance, and prove that the zero dimensional bottleneck distance can be recovered from a very small number of matching cases. Partly in keeping with nomenclature traditions in this area of TDA, we name this algorithm Lumáwig as a nod to a deity in the northern Philippines, where the algorithm was developed. We show that Lumáwig generally enjoys linear complexity as shown by empirical tests. We also present an application that leverages dimension zero persistence diagrams and the bottleneck distance to produce features for classification tasks. Full article

Graph visualization has been successfully applied in a wide range of problems and applications. Although different approaches are available to create visual representations, most of them suffer from clutter when faced with many nodes and/or edges. Among the techniques that address this problem, edge bundling has attained relative success in improving node-link layouts by bending and aggregating edges. Despite their success, most approaches perform the bundling based only on visual space information. There is no explicit connection between the produced bundled visual representation and the underlying data (edges or vertices attributes). In this paper, we present a novel edge bundling technique, called Similarity-Driven Edge Bundling (SDEB), to address this issue. Our method creates a similarity hierarchy based on a multilevel partition of the data, grouping edges considering the similarity between nodes to guide the bundling. The novel features introduced by SDEB are explored in different application scenarios, from dynamic graph visualization to multilevel exploration. Our results attest that SDEB produces layouts that consistently follow the similarity relationships found in the graph data, resulting in semantically richer presentations that are less cluttered than the state-of-the-art. Full article

The preservation of kidneys using normothermic machine perfusion (NMP) prior to transplantation has the potential for predictive evaluation of organ quality. Investigations concerning the quantitative assessment of physiological tissue parameters and their dependence on organ function lack in this context. In this study, hyperspectral imaging (HSI) in the wavelength range of 500–995 nm was conducted for the determination of tissue water content (TWC) in kidneys. The quantitative relationship between spectral data and the reference TWC values was established by partial least squares regression (PLSR). Different preprocessing methods were applied to investigate their influence on predicting the TWC of kidneys. In the full wavelength range, the best models for absorbance and reflectance spectra provided R_p² values of 0.968 and 0.963, as well as root-mean-square error of prediction (RMSEP) values of 2.016 and 2.155, respectively. Considering an optimal wavelength range (800–980 nm), the best model based on reflectance spectra (R_p² value of 0.941, RMSEP value of 3.202). Finally, the visualization of TWC distribution in all pixels of kidneys’ HSI image was implemented. The results show the feasibility of HSI for a non-invasively and accurate TWC prediction in kidneys, which could be used in the future to assess the quality of kidneys during the preservation period. Full article

The Wyoming Department of Transportation (WYDOT) initiated a project to optimize the heights of barriers that are not satisfying the barrier design criteria, while prioritizing them based on an ability to achieve higher monetary benefits. The equivalent property damage only (EPDO) was used in this study to account for both aspects of crash frequency and severity. Data of this type are known to have overdispersion, that is having a variance greater than the mean. Thus, a negative binomial model was implemented to address the over-dispersion issue of the dataset. Another challenge of the dataset used in this study was the heterogeneity of the dataset. The data heterogeneity resulted from various factors such as data being aggregated across two highway systems, and the presence of two barrier types in the whole state. Thus, it is not practical to assign a subjective hierarchy such as a highway system or barrier types to address the issue of severe heterogeneity in the dataset. Under these conditions, a finite mixture model (FMM) was implemented to find a best distribution parameter to characterize the observations. With this technique, after the optimum number of mixtures was identified, those clusters were assigned to various observations. However, previous studies mostly employed just the finite mixture model (FMM), with various distributions, to account for unobserved heterogeneity. The problem with the FMM approach is that it results in a loss of information: for instance, it would come up with N number of equations, where each result would use only part of the whole dataset. On the other hand, some studies used a subjective hierarchy to account for the heterogeneity in the dataset, such as the effect of seasonality or highway system; however, those subjective hierarchies might not account for the optimum heterogeneity in the dataset. Thus, we implement a new methodology, the Bayesian Hierarchical Finite Mixture (BHFMM) to employ the FMM without losing information, while also accounting for the heterogeneity in the dataset, by considering objective and unbiased hierarchies. As the Bayesian technique has the shortcoming of labeling the observations due to label switching; the FMM parameters were estimated by maximum likelihood technique. Results of the identified model were converted to an equation for implementation of machine learning techniques. The heights were optimized to an optimal value and the EPDO was predicted based on the changes. The results of the cost–benefit analysis indicated that after spending about 4 million dollars, the WYDOT would not only recover the expenses, but could also expect to save more than $4 million additional dollars through traffic barrier crash reduction. Full article

In this investigation, self-learning salp swarm optimization (SLSSO) based proportional- integral-derivative (PID) controllers are proposed for a Doha reverse osmosis desalination plant. Since the Doha reverse osmosis plant (DROP) is interacting with a two-input-two-output (TITO) system, a decoupler is designed to nullify the interaction dynamics. Once the decoupler is designed properly, two PID controllers are tuned for two non-interacting loops by minimizing the integral-square-error (ISE). The ISEs for two loops are obtained in terms of alpha and beta parameters to simplify the simulation. Thus designed ISEs are minimized using SLSSO algorithm. In order to show the effectiveness of the proposed algorithm, the controller tuning is also accomplished using some state-of-the-art algorithms. Further, statistical analysis is presented to prove the effectiveness of SLSSO. In addition, the time domain specifications are presented for different test cases. The step responses are also shown for fixed and variable reference inputs for two loops. The quantitative and qualitative results presented show the effectiveness of SLSSO for the DROP system. Full article

The analysis of many physical phenomena is reduced to the study of linear differential equations with polynomial coefficients. The present work establishes the necessary and sufficient conditions for the existence of polynomial solutions to linear differential equations with polynomial coefficients of degree n, $n-1$, and $n-2$ respectively. We show that for $n\ge 3$ the necessary condition is not enough to ensure the existence of the polynomial solutions. Applying Scheffé’s criteria to this differential equation we have extracted n generic equations that are analytically solvable by two-term recurrence formulas. We give the closed-form solutions of these generic equations in terms of the generalized hypergeometric functions. For arbitrary n, three elementary theorems and one algorithm were developed to construct the polynomial solutions explicitly along with the necessary and sufficient conditions. We demonstrate the validity of the algorithm by constructing the polynomial solutions for the case of $n=4$. We also demonstrate the simplicity and applicability of our constructive approach through applications to several important equations in theoretical physics such as Heun and Dirac equations. Full article

Process mining is a discipline which concerns the analysis of execution data of operational processes, the extraction of models from event data, the measurement of the conformance between event data and normative models, and the enhancement of all aspects of processes. Most approaches assume that event data is accurately captured behavior. However, this is not realistic in many applications: data can contain uncertainty, generated from errors in recording, imprecise measurements, and other factors. Recently, new methods have been developed to analyze event data containing uncertainty; these techniques prominently rely on representing uncertain event data by means of graph-based models explicitly capturing uncertainty. In this paper, we introduce a new approach to efficiently calculate a graph representation of the behavior contained in an uncertain process trace. We present our novel algorithm, prove its asymptotic time complexity, and show experimental results that highlight order-of-magnitude performance improvements for the behavior graph construction. Full article

A large amount of time series data is being generated every day in a wide range of sensor application domains. The symbolic aggregate approximation (SAX) is a well-known time series representation method, which has a lower bound to Euclidean distance and may discretize continuous time series. SAX has been widely used for applications in various domains, such as mobile data management, financial investment, and shape discovery. However, the SAX representation has a limitation: Symbols are mapped from the average values of segments, but SAX does not consider the boundary distance in the segments. Different segments with similar average values may be mapped to the same symbols, and the SAX distance between them is 0. In this paper, we propose a novel representation named SAX-BD (boundary distance) by integrating the SAX distance with a weighted boundary distance. The experimental results show that SAX-BD significantly outperforms the SAX representation, ESAX representation, and SAX-TD representation. Full article

In this study, a new parameter control scheme is proposed for the differential evolution algorithm. The developed linear bias reduction scheme controls the Lehmer mean parameter value depending on the optimization stage, allowing the algorithm to improve the exploration properties at the beginning of the search and speed up the exploitation at the end of the search. As a basic algorithm, the L-SHADE approach is considered, as well as its modifications, namely the jSO and DISH algorithms. The experiments are performed on the CEC 2017 and 2020 bound-constrained benchmark problems, and the performed statistical comparison of the results demonstrates that the linear bias reduction allows significant improvement of the differential evolution performance for various types of optimization problems. Full article

Nonsmooth optimization refers to the general problem of minimizing (or maximizing) functions that have discontinuous gradients. This Special Issue contains six research articles that collect together the most recent techniques and applications in the area of nonsmooth optimization. These include novel techniques utilizing some decomposable structures in nonsmooth problems—for instance, the difference-of-convex (DC) structure—and interesting important practical problems, like multiple instance learning, hydrothermal unit-commitment problem, and scheduling the disposal of nuclear waste. Full article

The study considers the usage of a probabilistic optimization method called Cross-Entropy (CE). This is the version of the Monte Carlo method created by Reuven Rubinstein (1997). It was developed in the context of determining rare events. Here we will present the way in which the CE method can be used for problems of optimization of epidemiological models, and more specifically the optimization of the Susceptible–Infectious–Recovered–Cross-immune (SIRC) model based on the functions supervising the care of specific groups in the model. With the help of weighted sampling, an attempt was made to find the fastest and most accurate version of the algorithm. Full article

The real world contains many kinds of complex network. Using influence nodes in complex networks can promote or inhibit the spread of information. Identifying influential nodes has become a hot topic around the world. Most of the existing algorithms used for influential node identification are based on the structure of the network such as the degree of the nodes. However, the attribute information of nodes also affects the ranking of nodes’ influence. In this paper, we consider both the attribute information between nodes and the structure of networks. Therefore, the similarity ratio, based on attribute information, and the degree ratio, based on structure derived from trust-value, are proposed. The trust–PageRank (TPR) algorithm is proposed to identify influential nodes in complex networks. Finally, several real networks from different fields are selected for experiments. Compared with some existing algorithms, the results suggest that TPR more rationally and effectively identifies the influential nodes in networks. Full article

Since their introduction, process trees have been frequently used as a process modeling formalism in many process mining algorithms. A process tree is a (mathematical) tree-based model of a process, in which internal vertices represent behavioral control-flow relations and leaves represent process activities. Translation of a process tree into a sound workflow net is trivial. However, the reverse is not the case. Simultaneously, an algorithm that translates a WF-net into a process tree is of great interest, e.g., the explicit knowledge of the control-flow hierarchy in a WF-net allows one to reason on its behavior more easily. Hence, in this paper, we present such an algorithm, i.e., it detects whether a WF-net corresponds to a process tree, and, if so, constructs it. We prove that, if the algorithm finds a process tree, the language of the process tree is equal to the language of the original WF-net. The experiments conducted show that the algorithm’s corresponding implementation has a quadratic time complexity in the size of the WF-net. Furthermore, the experiments show strong evidence of process tree rediscoverability. Full article

Bifurcations in dynamical systems characterize qualitative changes in the system behavior. Therefore, their detection is important because they can signal the transition from normal system operation to imminent failure. In an experimental setting, this transition could lead to incorrect data or damage to the entire experiment. While standard persistent homology has been used in this setting, it usually requires analyzing a collection of persistence diagrams, which in turn drives up the computational cost considerably. Using zigzag persistence, we can capture topological changes in the state space of the dynamical system in only one persistence diagram. Here, we present Bifurcations using ZigZag (BuZZ), a one-step method to study and detect bifurcations using zigzag persistence. The BuZZ method is successfully able to detect this type of behavior in two synthetic examples as well as an example dynamical system. Full article