Search for: All records

Triangles and squares count are widely-used graph analytic metrics providing insights into the connectivity of a graph. While the literature has focused on algorithms for global counts in simple graphs, this paper presents parallel algorithms for global and per-node triangle and square counts in large multigraphs. The algorithms have linear improvements in computational complexity as the number of cores increases. The triangle count algorithm has the same complexity as the best-known algorithm in the literature. The squares count algorithm has a lower execution time than previous methods. The proposed algorithms are evaluated on six real-world graphs and multigraphs, including protein-protein interaction graphs, knowledge graphs and large web graphs. 

Global sensitivity analysis (GSA) is a method to quantify the effect of the input parameters on outputs of physics-based systems. Performing GSA can be challenging due to the combined effect of the high computational cost of each individual physics-based model, a large number of input parameters, and the need to perform repetitive model evaluations. To reduce this cost, neural networks (NNs) are used to replace the expensive physics-based model in this work. This introduces the additional challenge of finding the minimum number of training data samples required to train the NNs accurately. In this work, a new method is introduced to accurately quantify the GSA values by iterating over both the number of samples required to train the NNs, terminated using an outer-loop sensitivity convergence criteria, and the number of model responses required to calculate the GSA, terminated with an inner-loop sensitivity convergence criteria. The iterative surrogate-based GSA guarantees converged values for the Sobol’ indices and, at the same time, alleviates the specification of arbitrary accuracy metrics for the surrogate model. The proposed method is demonstrated in two cases, namely, an eight-variable borehole function and a three-variable nondestructive testing (NDT) case. For the borehole function, both the first- and total-order Sobol’ indices required 200 and 105 data points to terminate on the outer- and inner-loop sensitivity convergence criteria, respectively. For the NDT case, these values were 100 for both first- and total-order indices for the outer-loop sensitivity convergence, and 106 and 103 for the inner-loop sensitivity convergence, respectively, for the first- and total-order indices, on the inner-loop sensitivity convergence. The differences of the proposed method with GSA on the true functions are less than 3% in the analytical case and less than 10% in the physics-based case (where the large error comes from small Sobol’ indices).