Node overlap removal in clustered directed acyclic graphs

Graph drawing and visualization represent structural information as diagrams of abstract graphs and networks. An important subset of graphs is directed acyclic graphs (DAGs). This paper presents a new E-Spring algorithm, extended from the popular spring embedder model, which eliminates node overlaps in clustered DAGs. In this framework, nodes are modeled as non-uniform charged particles with weights, and a final drawing is derived by adjusting the positions of the nodes according to a combination of spring forces and repulsive forces derived from electrostatic forces between the nodes. The drawing process needs to reach a stable state when the average distances of separation between nodes are near optimal. We introduce a stopping condition for such a stable state, which reduces equilibrium distances between nodes and therefore results in a significantly reduced area for DAG visualization. It imposes an upper bound on the repulsive forces between nodes based on graph geometry. The algorithm employs node interleaving to eliminate any residual node overlaps. These new techniques have been validated by visualizing eBay buyer–seller relationships and has resulted in overall area reductions in the range of 45–79%.     

An approach to the parallel solution of a high-dimensional basic flow problem

The body of mathematics of modified systems of algorithmic algebras (SAA-M) is used to formalize the Edmonds–Karp algorithm of finding the maximum flow in a network. With allowance made for the distributed system features that are usually used for solving complicated problems, optimization criteria are formulated and used to obtain parallel SAA-M-schemes. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 146–152, March–April 2009.     

Neuronet data processing algorithms in laser interferometer circuit at detecting object’s low oscillations and vibrations

A neuronet algorithm of interferometer data processing was developed for detection of microoscillations of the object. The algorithm parameters analysis has been carried out and sensitivity of the technique has been evaluated using experiment and simulation data. The article is published in the original.     

A method for numerical solution of a multidimensional convection-diffusion problem

We propose a modification of the additive splitting algorithm to solve the convection-diffusion problem using an efficient finite-difference scheme. The modification decreases the number of data exchanges and their amount during the numerical solution of a system of multidimensional equations. Approximation, stability, and convergence are considered. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 100–107, January–February 2009.     

Choosing the parameter of a modified additive-averaged splitting algorithm

The problem-solving time and the solution accuracy are expressed as functions of a parameter. An optimization problem of choosing the parameter using a “time cost–solution accuracy” criterion is considered. A Pareto-optimal set of solutions is obtained. The best value of the parameter is chosen by the ideal-point method. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 98–105, July–August 2009.     

Credit scoring using support vector machines with direct search for parameters selection

Support vector machines (SVM) is an effective tool for building good credit scoring models. However, the performance of the model depends on its parameters’ setting. In this study, we use direct search method to optimize the SVM-based credit scoring model and compare it with other three parameters optimization methods, such as grid search, method based on design of experiment (DOE) and genetic algorithm (GA). Two real-world credit datasets are selected to demonstrate the effectiveness and feasibility of the method. The results show that the direct search method can find the effective model with high classification accuracy and good robustness and keep less dependency on the initial search space or point setting.     

A hybrid clustering and graph based algorithm for tagSNP selection

TagSNP selection, which aims to select a small subset of informative single nucleotide polymorphisms (SNPs) to represent the whole large SNP set, has played an important role in current genomic research. Not only can this cut down the cost of genotyping by filtering a large number of redundant SNPs, but also it can accelerate the study of genome-wide disease association. In this paper, we propose a new hybrid method called CMDStagger that combines the ideas of the clustering and the graph algorithm, to find the minimum set of tagSNPs. The proposed algorithm uses the information of the linkage disequilibrium association and the haplotype diversity to reduce the information loss in tagSNP selection, and has no limit of block partition. The approach is tested on eight benchmark datasets from Hapmap and chromosome 5q31. Experimental results show that the algorithm in this paper can reduce the selection time and obtain less tagSNPs with high prediction accuracy. It indicates that this method has better performance than previous ones.     

A multi-objective strategy in genetic algorithms for gene selection of gene expression data

A microarray machine offers the capacity to measure the expression levels of thousands of genes simultaneously. It is used to collect information from tissue and cell samples regarding gene expression differences that could be useful for cancer classification. However, the urgent problems in the use of gene expression data are the availability of a huge number of genes relative to the small number of available samples, and the fact that many of the genes are not relevant to the classification. It has been shown that selecting a small subset of genes can lead to improved accuracy in the classification. Hence, this paper proposes a solution to the problems by using a multiobjective strategy in a genetic algorithm. This approach was tried on two benchmark gene expression data sets. It obtained encouraging results on those data sets as compared with an approach that used a single-objective strategy in a genetic algorithm. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

On the Black-Box Complexity of Sperner’s Lemma

We present several results on the complexity of various forms of Sperner’s Lemma in the black-box model of computing. We give a deterministic algorithm for Sperner problems over pseudo-manifolds of arbitrary dimension. The query complexity of our algorithm is linear in the separation number of the skeleton graph of the manifold and the size of its boundary. As a corollary we get an deterministic query algorithm for the black-box version of the problem 2D-SPERNER, a well studied member of Papadimitriou’s complexity class PPAD. This upper bound matches the deterministic lower bound of Crescenzi and Silvestri. The tightness of this bound was not known before. In another result we prove for the same problem an lower bound for its probabilistic, and an lower bound for its quantum query complexity, showing that all these measures are polynomially related. Research supported by the European Commission IST Integrated Project Qubit Application (QAP) 015848, the OTKA grants T42559 and T46234, and by the ANR Blanc AlgoQP grant of the French Research Ministry.     

Selecting informative genes from microarray data by using hybrid methods for cancer classification

Gene expression technology, namely microarrays, offers the ability to measure the expression levels of thousands of genes simultaneously in biological organisms. Microarray data are expected to be of significant help in the development of an efficient cancer diagnosis and classification platform. A major problem in these data is that the number of genes greatly exceeds the number of tissue samples. These data also have noisy genes. It has been shown in literature reviews that selecting a small subset of informative genes can lead to improved classification accuracy. Therefore, this paper aims to select a small subset of informative genes that are most relevant for cancer classification. To achieve this aim, an approach using two hybrid methods has been proposed. This approach is assessed and evaluated on two well-known microarray data sets, showing competitive results. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008