CiteULike: AbnerCYH's stochastic

A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting,

Yoav Freund — 2008-05-15T01:39:48-00:00

Journal of Computer and System Sciences, Vol. 55, No. 1. (August 1997), pp. 119-139.

In the first part of the paper we consider the problem of dynamically apportioning resources among a set of options in a worst-case on-line framework. The model we study can be interpreted as a broad, abstract extension of the well-studied on-line prediction model to a general decision-theoretic setting. We show that the multiplicative weight-update Littlestone-Warmuth rule can be adapted to this model, yielding bounds that are slightly weaker in some cases, but applicable to a considerably more general class of learning problems. We show how the resulting learning algorithm can be applied to a variety of problems, including gambling, multiple-outcome prediction, repeated games, and prediction of points in n. In the second part of the paper we apply the multiplicative weight-update technique to derive a new boosting algorithm. This boosting algorithm does not require any prior knowledge about the performance of the weak learning algorithm. We also study generalizations of the new boosting algorithm to the problem of learning functions whose range, rather than being binary, is an arbitrary finite set or a bounded segment of the real line.

Complex networks: Lies, damned lies and statistics

Nunes — 2008-03-09T16:48:04-00:00

Nat Phys, Vol. 2, No. 2. (February 2006), pp. 75-76.

The support vector machine under test

David Meyer — 2008-05-09T19:40:26-00:00

Neurocomputing, Vol. 55, No. 1-2. (September 2003), pp. 169-186.

Support vector machines (SVMs) are rarely benchmarked against other classification or regression methods. We compare a popular SVM implementation (libsvm) to 16 classification methods and 9 regression methods--all accessible through the software --by the means of standard performance measures (classification error and mean squared error) which are also analyzed by the means of bias-variance decompositions. SVMs showed mostly good performances both on classification and regression tasks, but other methods proved to be very competitive.

The boosting approach to machine learning: An overview

R Schapire — 2005-11-30T08:57:07-00:00

(2001)

Boosting is a general method for improving the accuracy of any given learning algorithm. Focusing primarily on the AdaBoost algorithm, this chapter overviews some of the recent work on boosting including analyses of AdaBoost's training error and generalization error; boosting's connection to game theory and linear programming; the relationship between boosting and logistic regression; extensions of AdaBoost for multiclass classification problems; methods of incorporating human knowledge...

An introduction to ROC analysis

Tom Fawcett — 2006-08-29T01:24:20-00:00

Pattern Recognition Letters, Vol. 27, No. 8. (June 2006), pp. 861-874.

Receiver operating characteristics (ROC) graphs are useful for organizing classifiers and visualizing their performance. ROC graphs are commonly used in medical decision making, and in recent years have been used increasingly in machine learning and data mining research. Although ROC graphs are apparently simple, there are some common misconceptions and pitfalls when using them in practice. The purpose of this article is to serve as an introduction to ROC graphs and as a guide for using them in research.

Using AUC and accuracy in evaluating learning algorithms

Jin Huang — 2008-05-09T12:01:38-00:00

Knowledge and Data Engineering, IEEE Transactions on, Vol. 17, No. 3. (2005), pp. 299-310.

The area under the ROC (receiver operating characteristics) curve, or simply AUC, has been traditionally used in medical diagnosis since the 1970s. It has recently been proposed as an alternative single-number measure for evaluating the predictive ability of learning algorithms. However, no formal arguments were given as to why AUC should be preferred over accuracy. We establish formal criteria for comparing two different measures for learning algorithms and we show theoretically and empirically that AUC is a better measure (defined precisely) than accuracy. We then reevaluate well-established claims in machine learning based on accuracy using AUC and obtain interesting and surprising new results. For example, it has been well-established and accepted that Naive Bayes and decision trees are very similar in predictive accuracy. We show, however, that Naive Bayes is significantly better than decision trees in AUC. The conclusions drawn in this paper may make a significant impact on machine learning and data mining applications.

Analyzing Receiver Operating Characteristic Curves With SAS (Sas Press Series) (Sas Press Series)

Mithat Gonen — 2008-05-09T11:47:40-00:00

(10 October 2007)

As a diagnostic decision-making tool, receiver operating characteristic (ROC) curves provide a comprehensive and visually attractive way to summarize the accuracy of predictions. They are extensively used in medical diagnosis and increasingly in fields such as data mining, credit scoring, weather forecasting, and psychometry. In this example-driven book, author Mithat GÃ¶nen illustrates the many existing SAS procedures that can be tailored to produce ROC curves and expands upon further analyses using other SAS procedures and macros. Both parametric and nonparametric methods for analyzing ROC curves are covered in detail. Topics addressed include: <ul> <li>Appropriate methods for binary, ordinal, and continuous measures <li>Computations using PROC FREQ, PROC LOGISTIC, PROC NLMIXED, and macros <li>Comparing the ROC curves of several markers and adjusting them for covariates <li>ROC curves with censored data <li>Using the ROC curve for evaluating multivariable prediction models via bootstrap and cross-validation <li>ROC curves in SAS Enterprise Miner <li>And more! </ul> Written for any statistician interested in learning more about ROC curve methodology, the book assumes readers have a basic understanding of regression procedures and moderate familiarity with Base SAS and SAS/STAT. Some familiarity with SAS/GRAPH is helpful but not essential.

The use of receiver operating characteristic curves in biomedical informatics

Thomas Lasko — 2006-01-14T16:08:59-00:00

Journal of Biomedical Informatics, Vol. 38, No. 5. (October 2005), pp. 404-415.

Receiver operating characteristic (ROC) curves are frequently used in biomedical informatics research to evaluate classification and prediction models for decision support, diagnosis, and prognosis. ROC analysis investigates the accuracy of a model's ability to separate positive from negative cases (such as predicting the presence or absence of disease), and the results are independent of the prevalence of positive cases in the study population. It is especially useful in evaluating predictive models or other tests that produce output values over a continuous range, since it captures the trade-off between sensitivity and specificity over that range. There are many ways to conduct an ROC analysis. The best approach depends on the experiment; an inappropriate approach can easily lead to incorrect conclusions. In this article, we review the basic concepts of ROC analysis, illustrate their use with sample calculations, make recommendations drawn from the literature, and list readily available software.

Statistical Learning Theory

Vladimir Vapnik — 2005-02-28T20:55:16-00:00

(16 September 1998)

A comprehensive look at learning and generalization theory. The statistical theory of learning and generalization concerns the problem of choosing desired functions on the basis of empirical data. Highly applicable to a variety of computer science and robotics fields, this book offers lucid coverage of the theory as a whole. Presenting a method for determining the necessary and sufficient conditions for consistency of learning process, the author covers function estimates from small data pools, applying these estimations to real-life problems, and much more.

Geometric Discrepancy: An Illustrated Guide (Algorithms and Combinatorics)

Jiri Matousek — 2008-04-16T02:19:13-00:00

(15 July 1999)

What is the "most uniform" way of distributing n points in the unit square? How big is the "irregularity" necessarily present in any such distribution? Such questions are treated in geometric discrepancy theory. The book is an accessible and lively introduction to this area, with numerous exercises and illustrations. In separate, more specialized parts, it also provides a comprehensive guide to recent research. Including a wide variety of mathematical techniques (from harmonic analysis, combinatorics, algebra etc.) in action on non-trivial examples, the book is suitable for a "special topic" course for early graduates in mathematics and computer science. Besides professional mathematicians, it will be of interest to specialists in fields where a large collection of objects should be "uniformly" represented by a smaller sample (such as high-dimensional numerical integration in computational physics or financial mathematics, efficient divide-and-conquer algorithms in computer science, etc.).

An Introduction to Computational Learning Theory

Michael Kearns — 2006-04-18T12:41:53-00:00

(15 August 1994)

A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest

Seth Pettie — 2008-04-03T11:01:35-00:00

SIAM J. Comput., Vol. 31, No. 6. (2002), pp. 1879-1895.

Closed-loop control of cellular functions using combinatory drugs guided by a stochastic search algorithm

Pak Wong — 2008-04-02T00:15:21-00:00

Proceedings of the National Academy of Sciences, Vol. 105, No. 13. (1 April 2008), pp. 5105-5110.

A mixture of drugs is often more effective than using a single effector. However, it is extremely challenging to identify potent drug combinations by trial and error because of the large number of possible combinations and the inherent complexity of the underlying biological network. With a closed-loop optimization modality, we experimentally demonstrate effective searching for potent drug combinations for controlling cellular functions through a large parametric space. Only tens of iterations out of one hundred thousand possible trials were needed to determine a potent combination of drugs for inhibiting vesicular stomatitis virus infection of NIH 3T3 fibroblasts. In addition, the drug combination reduced the required dosage by approx10-fold compared with individual drugs. In another example, a potent mixture was identified in thirty iterations out of a possible million combinations of six cytokines that regulate the activity of nuclear factor kappa B in 293T cells. The closed-loop optimization approach possesses the potential of being an effective approach for manipulating a wide class of biological systems. 10.1073/pnas.0800823105

A theory of the learnable

LG Valiant — 2006-01-16T21:03:03-00:00

Commun. ACM, Vol. 27, No. 11. (November 1984), pp. 1134-1142.

The small-world phenomenon: an algorithm perspective

Jon Kleinberg — 2005-10-23T08:35:16-00:00

(2000), pp. 163-170.

The Web as a Graph

Ravi Kumar — 2005-11-07T12:18:38-00:00

(JanuaryMay--JanuaryJuly~ 2000), pp. 1-10.

The pages and hyperlinks of the World-Wide Web maybe viewed as nodes and edges in a directed graph. This graph has about a billion nodes today,several billion links, and appears to grow exponentially with time. There are many reasons---mathematical, sociological, and commercial---for studying the evolution of this graph. We first review a set of algorithms that operate on the Web graph, addressing problems from Web search, automatic community discovery, and classification. We then recall a...

Counting, Sampling and Integrating: Algorithms and Complexity (Lectures in Mathematics. ETH Zürich)

Mark Jerrum — 2008-03-14T09:12:21-00:00

(28 April 2003)

The subject of these notes is counting (of combinatorial structures) and related topics, viewed from a computational perspective. A major theme of the book is the idea of accumulating information about a set of combinatorial structures by performing a random walk (i.e., simulating a Markov chain) on those structures. These notes will be of value not only to teachers of postgraduate courses on these topics, but also to established researchers. For the first time this body of knowledge has been brought together in a single volume.

Could any graph be turned into a small-world?

Philippe Duchon — 2008-03-09T23:27:58-00:00

Theoretical Computer Science, Vol. 355, No. 1. (6 April 2006), pp. 96-103.

In addition to statistical graph properties (diameter, degree, clustering, etc.), Kleinberg [The small-world phenomenon: an algorithmic perspective, in: Proc. 32nd ACM Symp. on Theory of Computing (STOC), 2000, pp. 163-170] showed that a small-world can also be seen as a graph in which the routing task can be efficiently and easily done in spite of a lack of global knowledge. More precisely, in a lattice network augmented by extra random edges (but not chosen uniformly), a short path of polylogarithmic expected length can be found using a greedy algorithm with a local knowledge of the nodes. We call such a graph a navigable small-world since short paths exist and can be followed with partial knowledge of the network. In this paper, we show that a wide class of graphs can be augmented into navigable small-worlds.

Aspects of discrete mathematics and probability in the theory of machine learning

Martin Anthony — 2008-02-27T02:41:05-00:00

Discrete Applied Mathematics, Vol. 156, No. 6. (15 March 2008), pp. 883-902.

This paper discusses the applications of certain combinatorial and probabilistic techniques to the analysis of machine learning. Probabilistic models of learning initially addressed binary classification (or pattern classification). Subsequently, analysis was extended to regression problems, and to classification problems in which the classification is achieved by using real-valued functions (where the concept of a large margin has proven useful). Another development, important in obtaining more applicable models, has been the derivation of data-dependent bounds. Here, we discuss some of the key probabilistic and combinatorial techniques and results, focusing on those of most relevance to researchers in discrete applied mathematics.

On the testability and repair of hereditary hypergraph properties

Tim Austin — 2008-01-24T10:42:00-00:00

(14 Jan 2008)

Recent works of Alon-Shapira and Rödl-Schacht have demonstrated that every hereditary property of undirected graphs or hypergraphs is testable with one-sided error; informally, this means that if a graph or hypergraph satisfies that property “locally” with sufficiently high probability, then it can be perturbed (or “repaired”) into a graph or hypergraph which satisfies that property “globally”. In this paper we make some refinements to these results, some of which may be surprising. In the positive direction, we strengthen the results to cover hereditary properties of multiple directed polychromatic graphs and hypergraphs. In the case of undirected graphs, we extend the result to continuous graphs on probability spaces, and show that the repair algorithm is “local” in the sense that it only depends on a bounded amount of data; in particular, the graph can be repaired in a time linear in the number of edges. We also show that local repairability also holds for monotone or partite hypergraph properties (this latter result is also implicitly in work of Ishigami). In the negative direction, we show that local repairability breaks down for directed graphs, or for undirected 3-uniform hypergraphs. The reason for this contrast in behavior stems from (the limitations of) Ramsey theory.

Getting Started in Probabilistic Graphical Models

Edoardo Airoldi — 2007-12-07T19:30:55-00:00

PLoS Computational Biology, Vol. 3, No. 12. (1 December 2007), e252.

An information-theoretic framework for resolving community structure in complex networks

Martin Rosvall — 2007-05-01T17:50:37-00:00

PNAS, Vol. 104, No. 18. (1 May 2007), pp. 7327-7331.

To understand the structure of a large-scale biological, social, or technological network, it can be helpful to decompose the network into smaller subunits or modules. In this article, we develop an information-theoretic foundation for the concept of modularity in networks. We identify the modules of which the network is composed by finding an optimal compression of its topology, capitalizing on regularities in its structure. We explain the advantages of this approach and illustrate them by partitioning a number of real-world and model networks. 10.1073/pnas.0611034104

The mutual information: Detecting and evaluating dependencies between variables

R Steuer — 2007-11-26T13:36:33-00:00

Bioinformatics, Vol. 18 (2002), pp. S231-S240.

Motivation: Clustering co-expressed genes usually requires the definition of `distance' or `similarity' between measured datasets, the most common choices being Pearson correlation or Euclidean distance. With the size of available datasets steadily increasing, it has become feasible to consider other, more general, definitions as well. One alternative, based on information theory, is the mutual information, providing a general measure of dependencies between variables. While the use of mutual information in cluster analysis and visualization of large-scale gene expression data has been suggested previously, the earlier studies did not focus on comparing different algorithms to estimate the mutual information from finite data. Results: Here we describe and review several approaches to estimate the mutual information from finite datasets. Our findings show that the algorithms used so far may be quite substantially improved upon. In particular when dealing with small datasets, finite sample effects and other sources of potentially misleading results have to be taken into account.

The Strength of Weak Ties: A Network Theory Revisited

Mark Granovetter — 2005-03-29T00:45:33-00:00

Sociological Theory, Vol. 1 (1983), pp. 201-233.

In this chapter I review empirical studies directly testing the hypotheses of my 1973 paper "The Strength of Weak Ties" (hereafter "SWT") and work that elaborates those hypotheses theoretically or uses them to suggest new empirical research not discussed in my original formulation. Along the way, I will reconsider various aspects of the theoretical argument, attempt to plug some holes, and broaden its base.

The Strength of Weak Ties

Mark Granovetter — 2005-02-20T23:47:44-00:00

The American Journal of Sociology, Vol. 78, No. 6. (1973), pp. 1360-1380.

Analysis of social networks is suggested as a tool for linking micro and macro levels of sociological theory. The procedure is illustrated by elaboration of the macro implications of one aspect of small-scale interaction: the strength of dyadic ties. It is argued that the degree of overlap of two individuals' friendship networks varies directly with the strength of their tie to one another. The impact of this principle on diffusion of influence and information, mobility opportunity, and community organization is explored. Stress is laid on the cohesive power of weak ties. Most network models deal, implicitly, with strong ties, thus confining their applicability to small, well-defined groups. Emphasis on weak ties lends itself to discussion of relations between groups and to analysis of segments of social structure not easily defined in terms of primary groups.

Empirical Analysis of an Evolving Social Network

Gueorgi Kossinets — 2006-01-07T17:06:32-00:00

Science, Vol. 311, No. 5757. (6 January 2006), pp. 88-90.

Social networks evolve over time, driven by the shared activities and affiliations of their members, by similarity of individuals' attributes, and by the closure of short network cycles. We analyzed a dynamic social network comprising 43,553 students, faculty, and staff at a large university, in which interactions between individuals are inferred from time-stamped e-mail headers recorded over one academic year and are matched with affiliations and attributes. We found that network evolution is dominated by a combination of effects arising from network topology itself and the organizational structure in which the network is embedded. In the absence of global perturbations, average network properties appear to approach an equilibrium state, whereas individual properties are unstable.

Power-law distributions in empirical data

Aaron Clauset — 2007-06-13T16:25:35-00:00

(7 Jun 2007)

Power-law distributions occur in many situations of scientific interest and have significant consequences for our understanding of natural and man-made phenomena. Unfortunately, the empirical detection and characterization of power laws is made difficult by the large fluctuations that occur in the tail of the distribution. In particular, standard methods such as least-squares fitting are known to produce systematically biased estimates of parameters for power-law distributions and should not be used in most circumstances. Here we describe statistical techniques for making accurate parameter estimates for power-law data, based on maximum likelihood methods and the Kolmogorov-Smirnov statistic. We also show how to tell whether the data follow a power-law distribution at all, defining quantitative measures that indicate when the power law is a reasonable fit to the data and when it is not. We demonstrate these methods by applying them to twenty-four real-world data sets from a range of different disciplines. Each of the data sets has been conjectured previously to follow a power-law distribution. In some cases we find these conjectures to be consistent with the data while in others the power law is ruled out.

Characterization of complex networks: A survey of measurements

Luciano — 2005-10-17T16:49:02-00:00

(30 Jun 2005)

Each complex network (or class of networks) presents specific topological features which characterize its connectivity and highly influence the dynamics and function of processes executed on the network. The analysis, discrimination, and synthesis of complex networks therefore rely on the use of measurements capable of expressing the most relevant topological features. This article presents a survey of such measurements. It includes general considerations about complex network characterization, a brief review of the principal models, and the presentation of the main existing measurements organized into classes. Special attention is given to relating complex network analysis with the areas of pattern recognition and feature selection, as well as on surveying some concepts and measurements from traditional graph theory which are potentially useful for complex network research. Depending on the network and the analysis task one has in mind, a specific set of features may be chosen. It is hoped that the present survey will help the identification of suitable measurements.

Products and Help Bits in Decision Trees

Noam Nisan — 2007-10-23T09:15:36-00:00

SIAM Journal on Computing, Vol. 28, No. 3. (1998), pp. 1035-1050.

Pages 1035-1050,

Time-space trade-off lower bounds for randomized computation of decision problems

Paul Beame — 2005-12-04T17:14:42-00:00

J. ACM, Vol. 50, No. 2. (March 2003), pp. 154-195.

Sharpening the LYM inequality

Péter Erdős — 2007-10-19T14:23:37-00:00

Combinatorica, Vol. 12, No. 3. (1992), pp. 287-293.

The level sequence of a Sperner familyF is the sequencef(F)=fi(F), wherefi(F) is the number ofi element sets ofF . TheLYM inequality gives a necessary condition for an integer sequence to be the level sequence of a Sperner family on ann element set. Here we present an indexed family of inequalities that sharpen theLYM inequality.

Prisoner's dilemma and clusters on small-world networks

Xavier Thibert-Plante — 2007-10-12T10:44:20-00:00

Complexity, Vol. 12, No. 6. (2007), pp. 22-36.

The structure of interaction plays an important role in the outcome of evolutionary games. This study investigates the evolution of stochastic strategies of the prisoner's dilemma played on structures ranging from lattices to small world networks. Strategies and payoffs are analyzed as a function of the network characteristics of the node they are playing on. Nodes with lattice-like neighborhoods tend to perform better than the nodes modified during the rewiring process of the construction of the small-world network. © 2007 Wiley Periodicals, Inc. Complexity 12:22-36, 2006

A combinatorial approach to correlation inequalities

Graham Brightwell — 2007-10-09T07:12:37-00:00

Discrete Mathematics, Vol. 257, No. 2-3. (28 November 2002), pp. 311-327.

In this paper, we initiate a combinatorial approach to proving correlation inequalities for finite partially ordered sets. A new proof is provided for the strong form of the XYZ theorem, due to Fishburn. We also use our method to give a new proof of a related correlation result of Shepp involving two sets of relations. Our arguments are entirely combinatorial in the sense that they do not make use of the Ahlswede/Daykin theorem or any of its relatives.

On Random Intersection Graphs: The Subgraph Problem

Micha\l Karonski — 2007-10-08T18:09:22-00:00

Comb. Probab. Comput., Vol. 8, No. 1-2. (1999), pp. 131-159.

Why social networks are different from other types of networks

MEJ Newman — 2005-01-24T07:55:07-00:00

(26 May 2003)

We argue that social networks differ from most other types of networks, including technological and biological networks, in two important ways. First, they have non-trivial clustering or network transitivity, and second, they show positive correlations, also called assortative mixing, between the degrees of adjacent vertices. Social networks are often divided into groups or communities, and it has recently been suggested that this division could account for the observed clustering. We demonstrate that group structure in networks can also account for degree correlations. We show using a simple model that we should expect assortative mixing in such networks whenever there is variation in the sizes of the groups and that the predicted level of assortative mixing compares well with that observed in real-world networks.

Analysis of weighted networks

MEJ Newman — 2004-11-22T00:17:30-00:00

(20 July 2004)

The connections in many networks are not merely binary entities, either present or not, but have associated weights that record their strengths relative to one another. Recent studies of networks have, by and large, steered clear of such weighted networks, which are often perceived as being harder to analyze than their unweighted counterparts. Here we point out that weighted networks can in many cases be analyzed using a simple mapping from a weighted network to an unweighted multigraph, allowing us to apply standard techniques for unweighted graphs to weighted ones as well. We give a number of examples of the method, including an algorithm for detecting community structure in weighted networks and a new and simple proof of the max-flow/min-cut theorem.

Property Testing of Regular Tree Languages

Frédéric Magniez — 2007-09-19T13:12:38-00:00

Algorithmica

Abstract We consider the edit distance with moves on the class of words and the class of ordered trees. We first exhibit a simple tester for the class of regular languages on words and generalize it to the class of ranked and unranked regular trees. We also show that this distance problem is -complete on ordered trees.

Balls and bins: A study in negative dependence

Devdatt Dubhashi — 2007-09-06T20:42:27-00:00

Random Structures and Algorithms, Vol. 13, No. 2. (1998), pp. 99-124.

This paper investigates the notion of negative dependence amongst random variables and attempts to advocate its use as a simple and unifying paradigm for the analysis of random structures and algorithms

Combining Pattern Classifiers: Methods and Algorithms

Ludmila Kuncheva — 2006-09-02T17:12:18-00:00

(01 July 2004)

Covering pattern classification methods, Combining Classifiers: Ideas and Methods focuses on the important and widely studied issue of how to combine several classifiers together in order to achieve improved recognition performance. It is one of the first books to provide unified, coherent, and expansive coverage of the topic and as such will be welcomed by those involved in the area. With case studies that bring the text alive and demonstrate 'real-world' applications it is destined to become essential reading. Covering pattern classification methods, Combining Classifiers: Ideas and Methods focuses on the important and widely studied issue of how to combine several classifiers together in order to achieve improved recognition performance. It is one of the first books to provide unified, coherent, and expansive coverage of the topic and as such will be welcomed by those involved in the area. With case studies that bring the text alive and demonstrate 'real-world' applications it is destined to become essential reading.

Generating quasi-random sequences from semi-random sources

Miklos Santha — 2005-12-12T21:20:41-00:00

J. Comput. Syst. Sci., Vol. 33, No. 1. (August 1986), pp. 75-87.

Heuristics for Semirandom Graph Problems

Uriel Feige — 2007-09-02T16:10:03-00:00

Journal of Computer and System Sciences, Vol. 63, No. 4. (December 2001), pp. 639-671.

We consider semirandom graph models for finding large independent sets, colorings, and bisections in graphs. These models generate problem instances by blending random and adversarial decisions. To generate semirandom independent set problems, an independent set S of [alpha]n vertices is randomly chosen. Each edge connecting S with S is chosen with probability p, and an adversary is then allowed to add new edges arbitrarily, provided that S remains an independent set. The smaller p is, the greater the control the adversary has over the semirandom graph. We give a heuristic that with high probability recovers an independent set of size [alpha]n whenever p> (1+[var epsilon]) ln n/[alpha]n, for any constant [var epsilon]>0. We show that when p<(1-[var epsilon]) ln n /[alpha]n, an independent set of size S cannot be recovered, unless NP[subset of or equal to]BPP. We use our result for maximum independent sets to obtain greatly improved heuristics for the model of k-colorable semirandom graphs introduced by Blum and Spencer. For constant k, our results are optimal up to constant factors in the edge probabilities. In the semirandom model for graph bisection, a random bisection (S, S) of the vertices is chosen. Each edge (u, v)[set membership, variant]SxS is independently chosen with probability q and each edge (u, v)[negated set membership]SxS is independently chosen with probability p>q. The adversary may then arbitrarily remove edges in SxS and add edges not in SxS. Extending the work of Boppana, we give a heuristic that recovers this bisection with high probability when p-q[greater-or-equal, slanted]c , for c a sufficiently large constant.

Coloring Random and Semi-Random k-Colorable Graphs

A Blum — 2007-09-02T15:56:57-00:00

Journal of Algorithms, Vol. 19, No. 2. (September 1995), pp. 204-234.

The problem of coloring a graph with the minimum number of colors is well known to be NP-hard, even restricted to k-colorable graphs for constant k >= 3. On the other hand, it is known that random k-colorable graphs are easy to k-color. The algorithms for coloring random k-colorable graphs require fairly high edge densities, however. In this paper we present algorithms that color randomly generated k-colorable graphs for much lower edge densities than previous approaches. In addition, to study a wider variety of graph distributions, we also present a model of graphs generated by the semi-random source of Santha and Vazirani (M. Santha and U. V. Vazirani, J. Comput. System Sci.33 (1986), 75-87) that provides a smooth transition between the worst-case and random models. In this model, the graph is generated by a "noisy adversary"-an adversary whose decisions (whether or not to insert a particular edge) have some small (random) probability of being reversed. We show that even for quite low noise rates, semi-random k-colorable graphs can be optimally colored with high probability.

On Orthogonal Double Covers of Graphs

Hans-Dietrich Gronau — 2007-08-28T06:52:42-00:00

Designs, Codes and Cryptography, Vol. 27, No. 1. (1 October 2002), pp. 49-91.

An orthogonal double cover (ODC) is a collection of n spanning subgraphs(pages) of the complete graph Kn such that they cover every edge of the completegraph twice and the intersection of any two of them contains exactly one edge. If all the pages are isomorphic tosome graph G, we speak of an ODC by G. ODCs have been studied for almost 25 years, and existenceresults have been derived for many graph classes. We present an overview of the current state of research alongwith some new results and generalizations. As will be obvious, progress made in the last 10 years is in many waysrelated to the work of Ron Mullin. So it is natural and with pleasure that we dedicate this article to Ron, on theoccasion of his 65th birthday.

Hamiltonian Cycles on a Random Three-coordinate Lattice

B Eynard — 2007-08-23T13:45:04-00:00

(20 May 1998)

Consider a random three-coordinate lattice of spherical topology having 2v vertices and being densely covered by a single closed, self-avoiding walk, i.e. being equipped with a Hamiltonian cycle. We determine the number of such objects as a function of v. Furthermore we express the partition function of the corresponding statistical model as an elliptic integral.

Correlation search in graph databases

Yiping Ke — 2007-08-21T13:19:17-00:00

(2007), pp. 390-399.

Graph mining: Laws, generators, and algorithms

Deepayan Chakrabarti — 2006-07-21T13:00:13-00:00

ACM Comput. Surv., Vol. 38, No. 1. (2006)

The Elements of Statistical Learning

T Hastie — 2005-04-15T14:57:05-00:00

(09 August 2001)

During the past decade there has been an explosion in computation and information technology. With it has come vast amounts of data in a variety of fields such as medicine, biology, finance, and marketing. The challenge of understanding these data has led to the development of new tools in the field of statistics, and spawned new areas such as data mining, machine learning, and bioinformatics. Many of these tools have common underpinnings but are often expressed with different terminology. This book descibes theimprtant ideas in these areas ina common conceptual framework. While the approach is statistical, the emphasis is on concepts rather than mathematics. Many examples are given, with a liberal use of color graphics. It should be a vluable resource for statisticians and anyone interested in data mining in science or industry. The book's coverage is broad, from supervised learing (prediction) to unsupervised learning. The many topics include neural networks, support vector machines, classification trees and boosting--the first comprehensive treatment of this topic in any book. Trevor Hastie, Robert Tibshirani, and Jerome Friedman are professors of statistics at Stanford University. They are prominent researchers in this area: Hastie and Tibshirani developed generalized additive models and wrote a popular book of that title. Hastie wrote much of the statistical modeling software in S-PLUS and invented principal curves and surfaces. Tibshirani proposed the Lasso and is co-author of the very successful An Introduction to the Bootstrap. Friedman is the co-inventor of many data-mining tools including CART, MARS, and projection pursuit.

Statistical mechanical systems on complete graphs, infinite exchangeability, finite extensions and a discrete finite moment problem

Thomas Liggett — 2007-07-31T10:09:20-00:00

(30 Jul 2007)

We show that a large collection of statistical mechanical systems with quadratically represented Hamiltonians on the complete graph can be extended to infinite exchangeable processes. This extends a known result for the ferromagnetic Curie--Weiss Ising model and includes as well all ferromagnetic Curie--Weiss Potts and Curie--Weiss Heisenberg models. By de Finetti's theorem, this is equivalent to showing that these probability measures can be expressed as averages of product measures. We provide examples showing that “ferromagnetism” is not however in itself sufficient and also study in some detail the Curie--Weiss Ising model with an additional 3-body interaction. Finally, we study the question of how much the antiferromagnetic Curie--Weiss Ising model can be extended. In this direction, we obtain sharp asymptotic results via a solution to a new moment problem. We also obtain a “formula” for the extension which is valid in many cases.

Randomized Computations on Large Data Sets: Tight Lower Bounds

Martin Grohe — 2007-03-16T20:10:39-00:00

(15 Mar 2007)

We study the randomized version of a computation model (introduced by Grohe, Koch, and Schweikardt (ICALP'05); Grohe and Schweikardt (PODS'05)) that restricts random access to external memory and internal memory space. Essentially, this model can be viewed as a powerful version of a data stream model that puts no cost on sequential scans of external memory (as other models for data streams) and, in addition, (like other external memory models, but unlike streaming models), admits several large external memory devices that can be read and written to in parallel. We obtain tight lower bounds for the decision problems set equality, multiset equality, and checksort. More precisely, we show that any randomized one-sided-error bounded Monte Carlo algorithm for these problems must perform Omega(log N) random accesses to external memory devices, provided that the internal memory size is at most O(N^(1/4)/log N), where N denotes the size of the input data. From the lower bound on the set equality problem we can infer lower bounds on the worst case data complexity of query evaluation for the languages XQuery, XPath, and relational algebra on streaming data. More precisely, we show that there exist queries in XQuery, XPath, and relational algebra, such that any (randomized) Las Vegas algorithm that evaluates these queries must perform Omega(log N) random accesses to external memory devices, provided that the internal memory size is at most O(N^(1/4)/log N).

Randomized rounding without solving the linear program

Neal Young — 2007-03-27T11:08:02-00:00

(1995), pp. 170-178.