Proof of the Loebl–Komlós–Sós conjecture for large, dense graphs

The Loebl–Komlós–Sós conjecture states that for any integers k and n, if a graph G on n vertices has at least n/2 vertices of degree at least k, then G contains as subgraphs all trees on k+1 vertices. We prove this conjecture in the case when k is linear in n, and n is sufficiently large.     

A visual proof of a result of Knuth on spanning trees of Aztec diamonds in the case of odd order

The even Aztec diamond AD_n is known to have precisely four times more spanning trees than the odd Aztec diamond OD_n—this was conjectured by Stanley and first proved by Knuth. We present a short combinatorial proof of this fact in the case of odd n. Our proof works also for the more general case of odd-by-odd Aztec rectangles.     

An exact and polynomial distance-based algorithm to reconstruct single copy tandem duplication trees

The problem of reconstructing the duplication tree of a set of tandemly repeated sequences which are supposed to have arisen by unequal recombination, was first introduced by Fitch (1977), and has recently received a lot of attention. In this paper, we place ourselves in a distance framework and deal with the restricted problem of reconstructing single copy duplication trees. We describe an exact and polynomial distance based algorithm for solving this problem, the parsimony version of which has previously been shown to be NP-hard (like most evolutionary tree reconstruction problems). This algorithm is based on the minimum evolution principle, and thus involves selecting the shortest tree as being the correct duplication tree. After presenting the underlying mathematical concepts behind the minimum evolution principle, and some of its benefits (such as statistical consistency), we provide a new recurrence formula to estimate the tree length using ordinary least-squares, given a matrix of pairwise distances between the copies. We then show how this formula naturally forms the dynamic programming framework on which our algorithm is based, and provide an implementation in O(n³) time and O(n²) space, where n is the number of copies.     

Extension of multivariate regression trees to interval data. Application to electricity load profiling

Summary  Several data can be presented as interval curves where intervals reflect a within variability. In particular, this representation is well adapted for load profiles, which depict the electricity consumption of a class of customers. Electricity load profiling consists in assigning a daily load curve to a customer based on their characteristics such as energy requirement. Within the load profiling scope, this paper investigates the extension of multivariate regression trees to the case of interval dependent (or response) variables. The tree method aims at setting up simultaneously load profiles and their assignment rules based on independent variables. The extension of multivariate regression trees to interval responses is detailed and a global approach is defined. It consists in a first stage of a dimension reduction of the interval response variables. Thereafter, the extension of the tree method is applied to the first principal interval components. Outputs are the classes of the interval curves where each class is characterized both by an interval load profile (e.g. the class prototype) and an assignment rule based on the independent variables.     

Random field Ising model and community structure in complex networks

We propose a method to determine the community structure of a complex network. In this method the ground state problem of a ferromagnetic random field Ising model is considered on the network with the magnetic field B_s = +∞, B_t = -∞, and B_i≠s,t=0 for a node pair s and t. The ground state problem is equivalent to the so-called maximum flow problem, which can be solved exactly numerically with the help of a combinatorial optimization algorithm. The community structure is then identified from the ground state Ising spin domains for all pairs of s and t. Our method provides a criterion for the existence of the community structure, and is applicable equally well to unweighted and weighted networks. We demonstrate the performance of the method by applying it to the Barabási-Albert network, Zachary karate club network, the scientific collaboration network, and the stock price correlation network. (Ising, Potts, etc.)     

Drifted Laplace operators on homogeneous trees

We determine the spectrum and the resolvent operator of a drifted Laplace operator on a homogeneous tree, obtaining qualitatively different results according to the sign of the drift in the direction of a boundary point.

     

Fuzzy classifier identification using decision tree and multiobjective evolutionary algorithms

This paper presents a hybrid method for identification of Pareto-optimal fuzzy classifiers (FCs). In contrast to many existing methods, the initial population for multiobjective evolutionary algorithms (MOEAs) is neither created randomly nor a priori knowledge is required. Instead, it is created by the proposed two-step initialization method. First, a decision tree (DT) created by C4.5 algorithm is transformed into an FC. Therefore, relevant variables are selected and initial partition of input space is performed. Then, the rest of the population is created by randomly replacing some parameters of the initial FC, such that, the initial population is widely spread. That improves the convergence of MOEAs into the correct Pareto front. The initial population is optimized by NSGA-II algorithm and a set of Pareto-optimal FCs representing the trade-off between accuracy and interpretability is obtained. The method does not require any a priori knowledge of the number of fuzzy sets, distribution of fuzzy sets or the number of relevant variables. They are all determined by it. Performance of the obtained FCs is validated by six benchmark data sets from the literature. The obtained results are compared to a recently published paper [H. Ishibuchi, Y. Nojima, Analysis of interpretability-accuracy tradeoff of fuzzy systems by multiobjective fuzzy genetics-based machine learning, International Journal of Approximate Reasoning 44 (1) (2007) 4–31] and the benefits of our method are clearly shown.     

Bankruptcy prediction in banks and firms via statistical and intelligent techniques – A review

This paper presents a comprehensive review of the work done, during the 1968–2005, in the application of statistical and intelligent techniques to solve the bankruptcy prediction problem faced by banks and firms. The review is categorized by taking the type of technique applied to solve this problem as an important dimension. Accordingly, the papers are grouped in the following families of techniques: (i) statistical techniques, (ii) neural networks, (iii) case-based reasoning, (iv) decision trees, (iv) operational research, (v) evolutionary approaches, (vi) rough set based techniques, (vii) other techniques subsuming fuzzy logic, support vector machine and isotonic separation and (viii) soft computing subsuming seamless hybridization of all the above-mentioned techniques. Of particular significance is that in each paper, the review highlights the source of data sets, financial ratios used, country of origin, time line of study and the comparative performance of techniques in terms of prediction accuracy wherever available. The review also lists some important directions for future research.     

To ask or not to ask,that is the question

Applicants for credit have to provide information for the risk assessment process. In the current conditions of a saturated consumer lending market, and hence falling “take” rates, can such information be used to assess the probability of a customer accepting the offer?     

Efficiency of the Incomplete Enumeration Algorithm for Monte-Carlo Simulation of Linear and Branched Polymers

We study the efficiency of the incomplete enumeration algorithm for linear and branched polymers. There is a qualitative difference in the efficiency in these two cases. The average time to generate an independent sample of configuration of polymer with n monomers varies as n ² for linear polymers for large n, but as exp(cn ^α) for branched (undirected and directed) polymers, where 0<α<1. On the binary tree, our numerical studies for n of order 10⁴ gives α = 0.333±0.005. We argue that α =1/3 exactly in this case. An erratum to this article can be found at .