Efficient computation of distance labeling for decremental updates in large dynamic graphs

Since today’s real-world graphs, such as social network graphs, are evolving all the time, it is of great importance to perform graph computations and analysis in these dynamic graphs. Due to the fact that many applications such as social network link analysis with the existence of inactive users need to handle failed links or nodes, decremental computation and maintenance for graphs is considered a challenging problem. Shortest path computation is one of the most fundamental operations for managing and analyzing large graphs. A number of indexing methods have been proposed to answer distance queries in static graphs. Unfortunately, there is little work on answering such queries for dynamic graphs. In this paper, we focus on the problem of computing the shortest path distance in dynamic graphs, particularly on decremental updates (i.e., edge deletions). We propose maintenance algorithms based on distance labeling, which can handle decremental updates efficiently. By exploiting properties of distance labeling in original graphs, we are able to efficiently maintain distance labeling for new graphs. We experimentally evaluate our algorithms using eleven real-world large graphs and confirm the effectiveness and efficiency of our approach. More specifically, our method can speed up index re-computation by up to an order of magnitude compared with the state-of-the-art method, Pruned Landmark Labeling (PLL).     

Efficient aerodynamic shape optimization of transonic wings using a parallel infilling strategy and surrogate models

Surrogate models are used to dramatically improve the design efficiency of numerical aerodynamic shape optimization, where high-fidelity, expensive computational fluid dynamics (CFD) is often employed. Traditionally, in adaptation, only one single sample point is chosen to update the surrogate model during each updating cycle, after the initial surrogate model is built. To enable the selection of multiple new samples at each updating cycle, a few parallel infilling strategies have been developed in recent years, in order to reduce the optimization wall clock time. In this article, an alternative parallel infilling strategy for surrogate-based constrained optimization is presented and demonstrated by the aerodynamic shape optimization of transonic wings. Different from existing methods in which multiple sample points are chosen by a single infill criterion, this article uses a combination of multiple infill criteria, with each criterion choosing a different sample point. Constrained drag minimizations of the ONERA-M6 and DLR-F4 wings are exercised to demonstrate the proposed method, including low-dimensional (6 design variables) and higher-dimensional problems (up to 48 design variables). The results show that, for surrogate-based optimization of transonic wings, the proposed method is more effective than the existing parallel infilling strategies, when the number of initial sample points are in the range from N _v to 8N _v (N _v here denotes the number of design variables). Each case is repeated 50 times to eliminate the effect of randomness in our results.     

Nonlinear dynamic responses of electrostatically actuated microcantilevers containing internal fluid flow

A nonlinear theoretical model for electrostatically actuated microcantilevers containing internal fluid flow is developed in the present study, which takes into account the geometric and electrostatic nonlinearities. A four-degree-of-freedom and eight-dimensional analytical modeling is presented for investigating the stability mechanism and nonlinear dynamic responses near and away from the instability boundaries of the fluid-loaded cantilevered microbeam system. Firstly, the reliability of the theoretical model is examined by comparing the present results with previous experimental and numerical results. It is found that, with the increase in flow velocity, flutter instability, pull-in instability and the combination of both can occur in this dynamical system. It is also found that the instability boundary depends on the initial conditions significantly when the internal fluid is at low flow rate. Nextly, the phase portraits and time histories of the microbeam’s oscillations and bifurcation diagrams are established to show the existence of periodic, chaotic divergence and transient periodic-like motions.     

High dimensional model representation for hybrid reliability analysis with dependent interval variables constrained within ellipsoids

Random variables could be dependent, and so could interval variables. To accommodate dependent interval variables, this work develops an efficient hybrid reliability analysis method to handle both random and dependent interval input variables. Due to the dependent interval variables, the reliability analysis needs to perform the probability analysis for every combination of dependent interval variables. This involves a nested double-loop procedure and dramatically decreases the efficiency. The proposed method decomposes the nested double loops into sequential probability analysis (PA) loop and interval analysis (IA) loop. An efficient IA algorithm based on the cut-HDMR (High Dimensional Model Representation) expansion is developed and a sampling strategy with the leave-one-out technique without extra calls of the limit-state function is proposed. The proposed method has good accuracy and efficiency as demonstrated by two engineering examples.     

分类错误指导的分层B-CNN模型用于细粒度分类

目的 细粒度分类近年来受到了越来越多研究者的广泛关注,其难点是分类目标间的差异非常小。为此提出一种分类错误指导的分层双线性卷积神经网络模型。方法 该模型的核心思想是将双线性卷积神经网络算法（B-CNN）容易分错、混淆的类再分别进行重新训练和分类。首先,为得到易错类,提出分类错误指导的聚类算法。该算法基于受限拉普拉斯秩（CLR）聚类模型,其核心“关联矩阵”由“分类错误矩阵”构造。其次,以聚类结果为基础,构建了新的分层B-CNN模型。结果 用分类错误指导的分层B-CNN模型在CUB-200-2011、 FGVC-Aircraft-2013b和Stanford-cars 3个标准数据集上进行了实验,相比于单层的B-CNN模型,分类准确率分别由84.35%,83.56%,89.45%提高到了84.67%,84.11%,89.78%,验证了本文算法的有效性。结论 本文提出了用分类错误矩阵指导聚类从而进行重分类的方法,相对于基于特征相似度而构造的关联矩阵,分类错误矩阵直接针对分类问题,可以有效提高易混淆类的分类准确率。本文方法针对比较相近的目标,尤其是有非常相近的目标的情况,通过将容易分错、混淆的目标分组并进行再训练和重分类,使得分类效果更好,适用于细粒度分类问题。     

基于Isolation Forest的并行化异常探测设计

异常探测具有广泛的应用,受到了工业界和学术界的共同关注。在众多异常探测方法中,Isolation Forest算法具有执行效率高、探测准确度好的特点,获得了众多应用。但是,传统Isolation Forest算法难以处理大规模数据。为解决此问题,设计了一种基于云计算平台的算法。具体地,使用Hadoop分布式存储系统和MapReduce分布式计算框架设计并实现了基于Isolation Forest的并行化异常探测算法PIFH。通过将探测模型构建和数据异常评价的过程并行化,提升了PIFH算法探测异常的执行效率,扩展了其应用范围。利用真实世界数据集验证了所提算法的执行效率和可扩展性。     

“不确定性决策及智能算法”课程的教学改革与实践

针对“不确定性决策及智能算法”课程的特点,从教学内容、教学方法等方面对该课程进行研究,合理安排理论教学和实验教学内容.通过启发式教学、示例式教学、仿真模拟等多种教学手段,培养学生对不确定信息进行处理和决策的能力,以及设计智能算法求解的能力,取得了较好的教学效果.     

Direct generation of extended STL file from unorganized point data

An extended STL file format is presented in this paper. Differing with existing solutions, it proposes a new format to produce and store triangles. The format uses a cluster unit composed of several triangles. The main advantages of the format are that it contains both geometry and topological information and has improved storage capability. Direct generation of the extended STL from the scanned data has a great advantage in that it can reduce the time and error in modeling process. In order to obtain the format from unorganized point cloud, a new triangulation algorithm was introduced. The algorithm is based on reconstructing the relative Delaunay triangulation of the sample points on the surface. Other advantages of the extended STL format were also presented in this paper.     

S-states of helium-like ions

A simple Mathematica (version 7) code for computing S-state energies and wave functions of two-electron (helium-like) ions is presented. The elegant technique derived from the classical papers of Pekeris (1958, 1959, 1962, 1965, 1971) [1], [2] and [3] is applied. The basis functions are composed of the Laguerre functions. The method is based on the perimetric coordinates and specific properties of the Laguerre polynomials. Direct solution of the generalized eigenvalues and eigenvectors problem is used, distinct from the Pekeris works. No special subroutines were used, only built-in objects supported by Mathematica. The accuracy of the results and computation times depend on the basis size. The ground state and the lowest triplet state energies can be computed with a precision of 12 and 14 significant figures, respectively. The accuracy of the higher excited states calculations is slightly worse. The resultant wave functions have a simple analytical form, that enables calculation of expectation values for arbitrary physical operators without any difficulties. Only three natural parameters are required in the input.The above Mathematica code is simpler than the earlier version (Liverts and Barnea, 2010 [4]). At the same time, it is faster and more accurate.

Program summary

Program title: TwoElAtomSL(SH)Catalogue identifier: AEHY_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEHY_v1_0.htmlProgram obtainable from: CPC Program Library, Queen?s University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 11 434No. of bytes in distributed program, including test data, etc.: 540 063Distribution format: tar.gzProgramming language: Mathematica 7.0Computer: Any PCOperating system: Any which supports Mathematica; tested under Microsoft Windows XP and Linux SUSE 11.0RAM:?¹⁰⁹ bytesClassification: 2.1, 2.2, 2.7, 2.9Nature of problem: The Schrödinger equation for atoms (ions) with more than one electron has not been solved analytically. Approximate methods must be applied in order to obtain the wave functions or another physical attributes from quantum mechanical calculations.Solution method: The S-wave function is expanded into a triple set of basis functions which are composed of the exponentials combined with the Laguerre polynomials in the perimetric coordinates. Using specific properties of the Laguerre polynomials, solution of the two-electron Schrödinger equation reduces to solving the generalized eigenvalues and eigenvector problem for the proper Hamiltonian. The unknown exponential parameter is determined by means of minimization of the corresponding eigenvalue (energy).Restrictions: First, the too large length of expansion (basis size) takes the too large computation time and operative memory giving no perceptible improvement in accuracy. Second, the number of shells Ω in the wave function expansion enables one to calculate the excited nS-states up to n=Ω+1 inclusive.Running time: 2–60 minutes (depends on basis size and computer speed).     

A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem

In this paper, a discrete artificial bee colony (DABC) algorithm is proposed to solve the lot-streaming flow shop scheduling problem with the criterion of total weighted earliness and tardiness penalties under both the idling and no-idling cases. Unlike the original ABC algorithm, the proposed DABC algorithm represents a food source as a discrete job permutation and applies discrete operators to generate new neighboring food sources for the employed bees, onlookers and scouts. An efficient initialization scheme, which is based on the earliest due date (EDD), the smallest slack time on the last machine (LSL) and the smallest overall slack time (OSL) rules, is presented to construct the initial population with certain quality and diversity. In addition, a self adaptive strategy for generating neighboring food sources based on insert and swap operators is developed to enable the DABC algorithm to work on discrete/combinatorial spaces. Furthermore, a simple but effective local search approach is embedded in the proposed DABC algorithm to enhance the local intensification capability. Through the analysis of experimental results, the highly effective performance of the proposed DABC algorithm is shown against the best performing algorithms from the literature.