A Survey on Graphical Methods for Classification Predictive Performance Evaluation

Predictive performance evaluation is a fundamental issue in design, development, and deployment of classification systems. As predictive performance evaluation is a multidimensional problem, single scalar summaries such as error rate, although quite convenient due to its simplicity, can seldom evaluate all the aspects that a complete and reliable evaluation must consider. Due to this, various graphical performance evaluation methods are increasingly drawing the attention of machine learning, data mining, and pattern recognition communities. The main advantage of these types of methods resides in their ability to depict the trade-offs between evaluation aspects in a multidimensional space rather than reducing these aspects to an arbitrarily chosen (and often biased) single scalar measure. Furthermore, to appropriately select a suitable graphical method for a given task, it is crucial to identify its strengths and weaknesses. This paper surveys various graphical methods often used for predictive performance evaluation. By presenting these methods in the same framework, we hope this paper may shed some light on deciding which methods are more suitable to use in different situations.

Topological invariants of isolated complete intersection curve singularities

In this paper we present some formulae for topological invariants of projective complete intersection curves with isolated singularities in terms of the Milnor number, the Euler characteristic and the topological genus. We also present some conditions, involving the Milnor number and the degree of the curve, for the irreducibility of complete intersection curves.

X-ray spectrometry: a powerful tool for the measurement of complete fusion of weakly bound nuclei

We describe how the method of detection of delayed K x-rays produced by the electron capture decay of the residual nuclei can be a powerful tool in the investigation of the effect of the breakup process on the complete fusion (CF) cross-section of weakly bound nuclei at energies close to the Coulomb barrier. This is presently one of the most interesting subjects under investigation in the field of low-energy nuclear reactions, and the difficult experimental task of separating CF from the incomplete fusion (ICF) of one of the breakup fragments can be achieved by the x-ray spectrometry method. We present results for the fusion of the (9)Be + (144)Sm system. Copyright (c) 2008 John Wiley & Sons, Ltd.

Effect of Age on Outcome of Reduced-Intensity Hematopoietic Cell Transplantation for Older Patients With Acute Myeloid Leukemia in First Complete Remission or With Myelodysplastic Syndrome

Purpose Acute myelogenous leukemia (AML) and myelodysplastic syndrome (MDS) primarily afflict older individuals. Hematopoietic cell transplantation (HCT) is generally not offered because of concerns of excess morbidity and mortality. Reduced-intensity conditioning (RIC) regimens allow increased use of allogeneic HCT for older patients. To define prognostic factors impacting long-term outcomes of RIC regimens in patients older than age 40 years with AML in first complete remission or MDS and to determine the impact of age, we analyzed data from the Center for International Blood and Marrow Transplant Research (CIBMTR). Patients and Methods We reviewed data reported to the CIBMTR (1995 to 2005) on 1,080 patients undergoing RIC HCT. Outcomes analyzed included neutrophil recovery, incidence of acute or chronic graft-versus-host disease (GVHD), nonrelapse mortality (NRM), relapse, disease-free survival (DFS), and overall survival (OS). Results Univariate analyses demonstrated no age group differences in NRM, grade 2 to 4 acute GVHD, chronic GVHD, or relapse. Patients age 40 to 54, 55 to 59, 60 to 64, and >= 65 years had 2-year survival rates as follows: 44% (95% Cl, 37% to 52%), 50% (95% Cl, 41% to 59%), 34% (95% Cl, 25% to 43%), and 36% (95% Cl, 24% to 49%), respectively, for patients with AML (P = .06); and 42% (95% Cl, 35% to 49%), 35% (95% Cl, 27% to 43%), 45% (95% Cl, 36% to 54%), and 38% (95% Cl, 25% to 51%), respectively, for patients with MDS (P = .37). Multivariate analysis revealed no significant impact of age on NRM, relapse, DFS, or OS (all P>.3). Greater HLA disparity adversely affected 2-year NRM, DFS, and OS. Unfavorable cytogenetics adversely impacted relapse, DFS, and OS. Better pre-HCT performance status predicted improved 2-year OS. Conclusion With these similar outcomes observed in older patients, we conclude that older age alone should not be considered a contraindication to HCT.

Texture analysis using graphs generated by deterministic partially self-avoiding walks

Texture is one of the most important visual attributes for image analysis. It has been widely used in image analysis and pattern recognition. A partially self-avoiding deterministic walk has recently been proposed as an approach for texture analysis with promising results. This approach uses walkers (called tourists) to exploit the gray scale image contexts in several levels. Here, we present an approach to generate graphs out of the trajectories produced by the tourist walks. The generated graphs embody important characteristics related to tourist transitivity in the image. Computed from these graphs, the statistical position (degree mean) and dispersion (entropy of two vertices with the same degree) measures are used as texture descriptors. A comparison with traditional texture analysis methods is performed to illustrate the high performance of this novel approach. (C) 2011 Elsevier Ltd. All rights reserved.

Structural matching of 2D electrophoresis gels using deformed graphs

2D electrophoresis is a well-known method for protein separation which is extremely useful in the field of proteomics. Each spot in the image represents a protein accumulation and the goal is to perform a differential analysis between pairs of images to study changes in protein content. It is thus necessary to register two images by finding spot correspondences. Although it may seem a simple task, generally, the manual processing of this kind of images is very cumbersome, especially when strong variations between corresponding sets of spots are expected (e.g. strong non-linear deformations and outliers). In order to solve this problem, this paper proposes a new quadratic assignment formulation together with a correspondence estimation algorithm based on graph matching which takes into account the structural information between the detected spots. Each image is represented by a graph and the task is to find a maximum common subgraph. Successful experimental results using real data are presented, including an extensive comparative performance evaluation with ground-truth data. (C) 2010 Elsevier B.V. All rights reserved.

PARALLEL ALGORITHMS FOR MAXIMAL CLIQUES IN CIRCLE GRAPHS AND UNRESTRICTED DEPTH SEARCH

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of the subsequent maximal cliques this algorithm requires O(log p) communication rounds with O(m/p) local computation. The maximal cliques generation algorithm is based on generating all maximal paths in a directed acyclic graph, and we present an algorithm for this problem that uses O(log p) communication rounds with O(m/p) local computation for each maximal path. We also show that the presented algorithms can be extended to the CREW PRAM model.

Performance evaluation of routing protocols for MANETs with known connectivity patterns using evolving graphs

The assessment of routing protocols for mobile wireless networks is a difficult task, because of the networks` dynamic behavior and the absence of benchmarks. However, some of these networks, such as intermittent wireless sensors networks, periodic or cyclic networks, and some delay tolerant networks (DTNs), have more predictable dynamics, as the temporal variations in the network topology can be considered as deterministic, which may make them easier to study. Recently, a graph theoretic model-the evolving graphs-was proposed to help capture the dynamic behavior of such networks, in view of the construction of least cost routing and other algorithms. The algorithms and insights obtained through this model are theoretically very efficient and intriguing. However, there is no study about the use of such theoretical results into practical situations. Therefore, the objective of our work is to analyze the applicability of the evolving graph theory in the construction of efficient routing protocols in realistic scenarios. In this paper, we use the NS2 network simulator to first implement an evolving graph based routing protocol, and then to use it as a benchmark when comparing the four major ad hoc routing protocols (AODV, DSR, OLSR and DSDV). Interestingly, our experiments show that evolving graphs have the potential to be an effective and powerful tool in the development and analysis of algorithms for dynamic networks, with predictable dynamics at least. In order to make this model widely applicable, however, some practical issues still have to be addressed and incorporated into the model, like adaptive algorithms. We also discuss such issues in this paper, as a result of our experience.

Approximation algorithms and hardness results for the clique packing problem

For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F = {K(2)}. In this paper we provide new approximation algorithms and hardness results for the K(r)-packing problem where K(r) = {K(2), K(3,) . . . , K(r)}. We show that already for r = 3 the K(r)-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed r. For r = 3, 4, 5 we obtain better approximations. For r = 3 we obtain a simple 3/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldorsson. For r = 4, we obtain a (3/2 + epsilon)-approximation, and for r = 5 we obtain a (25/14 + epsilon)-approximation. (C) 2008 Elsevier B.V. All rights reserved.

Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width

Let M = (V, E, A) be a mixed graph with vertex set V, edge set E and arc set A. A cycle cover of M is a family C = {C(1), ... , C(k)} of cycles of M such that each edge/arc of M belongs to at least one cycle in C. The weight of C is Sigma(k)(i=1) vertical bar C(i)vertical bar. The minimum cycle cover problem is the following: given a strongly connected mixed graph M without bridges, find a cycle cover of M with weight as small as possible. The Chinese postman problem is: given a strongly connected mixed graph M, find a minimum length closed walk using all edges and arcs of M. These problems are NP-hard. We show that they can be solved in polynomial time if M has bounded tree-width. (C) 2008 Elsevier B.V. All rights reserved.

Algorithms for Maximum Independent Set in Convex Bipartite Graphs

A bipartite graph G = (V, W, E) is convex if there exists an ordering of the vertices of W such that, for each v. V, the neighbors of v are consecutive in W. We describe both a sequential and a BSP/CGM algorithm to find a maximum independent set in a convex bipartite graph. The sequential algorithm improves over the running time of the previously known algorithm and the BSP/CGM algorithm is a parallel version of the sequential one. The complexity of the algorithms does not depend on |W|.

Packing triangles in low degree graphs and indifference graphs

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2 + epsilon, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68-72]. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs. (C) 2007 Elsevier B.V. All rights reserved.

NEW CHARACTERIZATIONS OF COMPLETE SPACELIKE SUBMANIFOLDS IN SEMI-RIEMANNIAN SPACE FORMS

In this paper we study n-dimensional complete spacelike submanifolds with constant normalized scalar curvature immersed in semi-Riemannian space forms. By extending Cheng-Yau`s technique to these ambients, we obtain results to such submanifolds satisfying certain conditions on both the squared norm of the second fundamental form and the mean curvature. We also characterize compact non-negatively curved submanifolds in De Sitter space of index p.

Rigidity theorems for complete spacelike hypersurfaces with constant scalar curvature in De Sitter space

In this paper we give a partially affirmative answer to the following question posed by Haizhong Li: is a complete spacelike hypersurface in De Sitter space S(1)(n+1)(c), n >= 3, with constant normalized scalar curvature R satisfying n-2/nc <= R <= c totally umbilical? (C) 2008 Elsevier B.V. All rights reserved.

Geodesics and Almost Geodesic Cycles in Random Regular Graphs

A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance d(G)(u, v) is at least d(C)(u, v) - e(n). Let omega(n) be any function tending to infinity with n. We consider a random d-regular graph on n vertices. We show that almost all pairs of vertices belong to an almost geodesic cycle C with e(n)= log(d-1)log(d-1) n+omega(n) and vertical bar C vertical bar =2 log(d-1) n+O(omega(n)). Along the way, we obtain results on near-geodesic paths. We also give the limiting distribution of the number of geodesics between two random vertices in this random graph. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 66: 115-136, 2011