CiteULike: pdlug's library [285 articles]

Google's MapReduce programming model -- Revisited

Ralf Lammel — 2007-12-20T18:37:33-00:00

Science of Computer Programming, Vol. 70, No. 1. (1 January 2008), pp. 1-30.

Google's MapReduce programming model serves for processing large data sets in a massively parallel manner. We deliver the first rigorous description of the model including its advancement as Google's domain-specific language Sawzall. To this end, we reverse-engineer the seminal papers on MapReduce and Sawzall, and we capture our findings as an executable specification. We also identify and resolve some obscurities in the informal presentation given in the seminal papers. We use typed functional programming (specifically Haskell) as a tool for design recovery and executable specification. Our development comprises three components: (i) the basic program skeleton that underlies MapReduce computations; (ii) the opportunities for parallelism in executing MapReduce computations; (iii) the fundamental characteristics of Sawzall's aggregators as an advancement of the MapReduce approach. Our development does not formalize the more implementational aspects of an actual, distributed execution of MapReduce computations.

Semantic Analysis of Tag Similarity Measures in Collaborative Tagging Systems

Ciro Cattuto — 2008-05-15T12:58:21-00:00

(14 May 2008)

Social bookmarking systems allow users to organise collections of resources on the Web in a collaborative fashion. The increasing popularity of these systems as well as first insights into their emergent semantics have made them relevant to disciplines like knowledge extraction and ontology learning. The problem of devising methods to measure the semantic relatedness between tags and characterizing it semantically is still largely open. Here we analyze three measures of tag relatedness: tag co-occurrence, cosine similarity of co-occurrence distributions, and FolkRank, an adaptation of the PageRank algorithm to folksonomies. Each measure is computed on tags from a large-scale dataset crawled from the social bookmarking system del.icio.us. To provide a semantic grounding of our findings, a connection to WordNet (a semantic lexicon for the English language) is established by mapping tags into synonym sets of WordNet, and applying there well-known metrics of semantic similarity. Our results clearly expose different characteristics of the selected measures of relatedness, making them applicable to different subtasks of knowledge extraction such as synonym detection or discovery of concept hierarchies.

Learning Multiple Graphs for Document Recommendations

Ding Zhou — 2008-05-09T04:14:29-00:00

(21 April 2008)

The Web offers rich relational data with different semantics. In this paper, we address the problem of document recommendation in a digital library, where the documents in question are networked by citations and are associated with other entities by various relations. Due to the sparsity of a single graph and noise in graph construction, we propose a new method for combining multiple graphs to measure document similarities, where different factorization strategies are used based on the nature of different graphs. In particular, the new method seeks a single low-dimensional embedding of documents that captures their relative similarities in a latent space. Based on the obtained embedding, a new recommendation framework is developed using semi-supervised learning on graphs. In addition, we address the scalability issue and propose an incremental algorithm. The new incremental method significantly improves the efficiency by calculating the embedding for new incoming documents only. The new batch and incremental methods are evaluated on two real world datasets prepared from CiteSeer. Experiments demonstrate significant quality improvement for our batch method and significant efficiency improvement with tolerable quality loss for our incremental method.

Discrete Mathematics for Computer Science, Some Notes

Jean Gallier — 2008-05-06T06:30:10-00:00

(5 May 2008)

These are notes on discrete mathematics for computer scientists. The presentation is somewhat unconventional. Indeed I begin with a discussion of the basic rules of mathematical reasoning and of the notion of proof formalized in a natural deduction system “a la Prawitz”. The rest of the material is more or less traditional but I emphasize partial functions more than usual (after all, programs may not terminate for all input) and I provide a fairly complete account of the basic concepts of graph theory.

An Intelligent Statistical Arbitrage Trading System

NICK Kondakis — 2008-05-04T00:03:09-00:00

Social Science Research Network Working Paper Series

This paper proposes an intelligent combination of neural network theory and financial statistics for the detection of statistical arbitrage opportunities in specific pairs of stocks. The proposed intelligent methodology is based on a class of neural network-GARCH autoregressive models for the effective handling of the dynamics related to the statistical mispricing between relative stock prices. The performance of the proposed intelligent trading system is properly measured with the aid of profit & loss diagrams, for a number of different experimental settings (i.e. sampling frequencies). First results seem encouraging; nevertheless, further experimentation on the optimal sampling frequency, the forecasting horizon and the points of entry and exit is necessary, in order to achieve highest economic value when transaction costs are taken into account.

Survey of graph database models

Renzo Angles — 2008-02-25T22:23:48-00:00

ACM Comput. Surv., Vol. 40, No. 1. (February 2008), pp. 1-39.

Understanding the Subprime Mortgage Crisis

Yuliya Demyanyk — 2008-04-28T23:25:08-00:00

Social Science Research Network Working Paper Series (29 February 2008)

Using loan-level data, we analyze the quality of subprime mortgage loans by adjusting their performance for differences in borrower characteristics, loan characteristics, and house price appreciation since origination. We find that the quality of loans deteriorated for six consecutive years before the crisis and that securitizers were, to some extent, aware of it. We provide evidence that the rise and fall of the subprime mortgage market follows a classic lending boom-bust scenario, in which unsustainable growth leads to the collapse of the market. Problems could have been detected long before the crisis, but they were masked by high house price appreciation between 2003 and 2005.

Overoptimism Among Founders: The Role of Information and Motivation

I Verheul — 2008-04-25T21:14:47-00:00

Social Science Research Network Working Paper Series

This study empirically investigates factors that influence overoptimism across nascent entrepreneurs. We distinguish between two main groups of determinants (information, motivation) and three types of overoptimism (income, psychological burden, leisure time). Findings indicate that entrepreneurs who have relevant business information are more realistic and that entrepreneurs with a high level of general knowledge, acquired through education or previous (unrelated) entrepreneurial experience, are more overoptimistic. External advice and business planning do not appear to limit subsequent overoptimism. Entrepreneurs are less overoptimistic about the pecuniary or non-pecuniary benefits of self-employment when these benefits are closely related to the initial motivation for starting up the business.

Google News Personalization: Scalable Online Collaborative Filtering

Abhinandan Das — 2008-04-25T21:00:08-00:00

(8 May 2007)

Several approaches to collaborative filtering have been studied but seldom have the studies been reported for large (several millions of users and items) and dynamic (the underlying item set is continually changing) settings. In this paper we describe our approach to collaborative filtering for generating personalized recommendations for users of Google News. We generate recommendations using three approaches: collaborative filtering using MinHash clustering, Probabilistic Latent Semantic Indexing (PLSI), and covisitation counts. We combine recommendations from different algorithms using a linear model. Our approach is content agnostic and consequently domain independent, making it easily adaptible for other applications and languages with minimal effort. This paper will describe our algorithms and system setup in detail, and report results of running the recommendations engine on Google News.

Asset Allocation: Management Style and Performance Measurement

William Sharpe — 2008-04-25T04:08:31-00:00

Journal of Portfolio Management, (1992), pp. 7-19.

It is widely agreed that asset allocation accounts for a large part of the variability in the return on a typical investor's portfolio. This is especially true if the overall portfolio is invested in multiple funds, each including a number of securities. Asset allocation is generally defined as the allocation of an investor's portfolio among a number of "major" asset classes. Clearly such a generalization cannot be made operational without defining such classes. Once a set of asset classes has been defined, it is important to determine the exposures of each component of an investor's overall portfolio to movements in their returns. Such information can be aggregated to determine the investor's overall effective asset mix. If it does not conform to the desired mix, appropriate alterations can then be made. Once a procedure for measuring exposures to variations in returns of major asset classes is in place, it is possible to determine how effectively individual fund managers have performed their functions and the extent (if any) to which value has been added through active management. Finally, the effectiveness of the investor's overall asset allocation can be compared with that of one or more benchmark asset mixes. An effective way to accomplish all these tasks is to use an asset class factor model. After describing the characteristics of such a model, we illustrate applications of a model with twelve asset classes to analyze the performance of a set of open-end mutual funds between 1985 and 1989.

Portfolio Optimization with Linear and Fixed Transaction Costs

M Lobo — 2008-04-25T04:06:02-00:00

Annals of Operations Research, Vol. 152, No. 1. (July 2007), pp. 376-394.

We consider the problem of portfolio selection, with transaction costs and constraints on exposure to risk. Linear transaction costs, bounds on the variance of the return, and bounds on different shortfall probabilities are efficiently handled by convex optimization methods. For such problems, the globally optimal portfolio can be computed very rapidly. Portfolio optimization problems with transaction costs that include a fixed fee, or discount breakpoints, cannot be directly solved by convex optimization. We describe a relaxation method which yields an easily computable upper bound via convex optimization. We also describe a heuristic method for finding a suboptimal portfolio, which is based on solving a small number of convex optimization problems (and hence can be done efficiently). Thus, we produce a suboptimal solution, and also an upper bound on the optimal solution. Numerical experiments suggest that for practical problems the gap between the two is small, even for large problems involving hundreds of assets. The same approach can be used for related problems, such as that of tracking an index with a portfolio consisting of a small number of assets.

Information Resources in High-Energy Physics: Surveying the Present Landscape and Charting the Future Course

Anne Gentil-Beccot — 2008-04-18T21:48:45-00:00

(16 Apr 2008)

Access to previous results is of paramount importance in the scientific process. Recent progress in information management focuses on building e-infrastructures for the optimization of the research workflow, through both policy-driven and user-pulled dynamics. For decades, High-Energy Physics (HEP) has pioneered innovative solutions in the field of information management and dissemination. In light of a transforming information environment, it is important to assess the current usage of information resources by researchers and HEP provides a unique test-bed for this assessment. A survey of about 10% of practitioners in the field reveals usage trends and information needs. Community-based services, such as the pioneering arXiv and SPIRES systems, largely answer the need of the scientists, with a limited but increasing fraction of younger users relying on Google. Commercial services offered by publishers or database vendors are essentially unused in the field. The survey offers an insight into the most important features that users require to optimize their research workflow. These results inform the future evolution of information management in HEP and, as these researchers are traditionally “early adopters” of innovation in scholarly communication, can inspire developments of disciplinary repositories serving other communities.

Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data

John Lafferty — 2006-12-21T15:17:59-00:00

(2001), pp. 282-289.

We present conditional random elds, a framework for building probabilistic models to segment and label sequence data. Conditional random fields offer several advantages over hidden Markov models and stochastic grammars for such tasks, including the ability to relax strong independence assumptions made in those models. Conditional random fields also avoid a fundamental limitation of maximum entropy Markov models (MEMMs) and other discriminative Markov models based on directed...

On spectral clustering: Analysis and an algorithm

A Ng — 2007-03-14T05:03:05-00:00

(2001)

Despite many empirical successes of spectral clustering methods| algorithms that cluster points using eigenvectors of matrices derived from the data|there are several unresolved issues. First, there are a wide variety of algorithms that use the eigenvectors in slightly dierent ways. Second, many of these algorithms have no proof that they will actually compute a reasonable clustering.

Citation Counting, Citation Ranking, and h-Index of Human-Computer Interaction Researchers: A Comparison between Scopus and Web of Science

Lokman Meho — 2008-03-13T06:33:50-00:00

(12 Mar 2008)

This study examines the differences between Scopus and Web of Science in the citation counting, citation ranking, and h-index of 22 top human-computer interaction (HCI) researchers from EQUATOR--a large British Interdisciplinary Research Collaboration project. Results indicate that Scopus provides significantly more coverage of HCI literature than Web of Science, primarily due to coverage of relevant ACM and IEEE peer-reviewed conference proceedings. No significant differences exist between the two databases if citations in journals only are compared. Although broader coverage of the literature does not significantly alter the relative citation ranking of individual researchers, Scopus helps distinguish between the researchers in a more nuanced fashion than Web of Science in both citation counting and h-index. Scopus also generates significantly different maps of citation networks of individual scholars than those generated by Web of Science. The study also presents a comparison of h-index scores based on Google Scholar with those based on the union of Scopus and Web of Science. The study concludes that Scopus can be used as a sole data source for citation-based research and evaluation in HCI, especially if citations in conference proceedings are sought and that h scores should be manually calculated instead of relying on system calculations.

Usage patterns of collaborative tagging systems

Scott Golder — 2006-07-05T17:36:01-00:00

J. Inf. Sci., Vol. 32, No. 2. (April 2006), pp. 198-208.

Optimal Execution of Portfolio Transactions

R Almgren — 2007-08-29T15:23:06-00:00

(2001)

We consider the execution of portfolio transactions with the aim of minimizing a combination of volatility risk and transaction costs arising from permanent and temporary market impact. For a simple linear cost model, we explicitly construct the efficient frontier in the space of time-dependent liquidation strategies, which have minimum expected cost for a given level of uncertainty. This analysis yields a number we call the "half-life" of a trade, the natural time for execution in the absence...

Fractal and Multifractal Time Series

Jan Kantelhardt — 2008-04-07T04:10:29-00:00

(4 Apr 2008)

Data series generated by complex systems exhibit fluctuations on many time scales and/or broad distributions of the values. In both equilibrium and non-equilibrium situations, the natural fluctuations are often found to follow a scaling relation over several orders of magnitude, allowing for a characterisation of the data and the generating complex system by fractal (or multifractal) scaling exponents. In addition, fractal and multifractal approaches can be used for modelling time series and deriving predictions regarding extreme events. This review article describes and exemplifies several methods originating from Statistical Physics and Applied Mathematics, which have been used for fractal and multifractal time series analysis.

Elements of Linear and Real Analysis

Stephen Semmes — 2008-03-28T16:47:12-00:00

(18 Sep 2001)

This is a kind of introduction to some basic topics in analysis, some of which would be covered in standard graduate courses, and some not. However, an important difference is that not much in the way of prerequisites are needed, beyond linear algebra and beginning analysis. In particular, this should be accessible to undergraduates or readers whose main focus is not necessarily pure mathematics. One could easily accommodate Lebesgue integrals and so forth if one wanted to, but they are not really needed.

A beginner's guide to analysis on metric spaces

Stephen Semmes — 2008-03-28T16:59:20-00:00

(2 Aug 2004)

These informal notes briefly discuss some basic topics involving Lipschitz functions, connectedness, and Hausdorff content in particular.

Some remarks about metric spaces

Stephen Semmes — 2008-03-28T16:57:23-00:00

(29 Nov 2003)

The first section of this modest survey reviews some basic notions and describes some families of examples, and the second section briefly indicates some general aspects of analysis on metric spaces. The remaining three sections are concerned with some particular situations involving sub-Riemannian geometry, hyperbolic groups, and p-adic numbers.

Notes on matrices and calculus

Stephen Semmes — 2008-03-28T16:53:08-00:00

(11 Oct 2003)

These notes concern linear transformations on R^n and C^n, exponentials of linear transformations, and some related geometric questions.

Are Angels Preferred Venture Investors?

Brent Goldfarb — 2008-03-25T03:45:39-00:00

Social Science Research Network Working Paper Series (1 October 2007)

We examine the impact of business angels on 182 Series A financings and subsequent company outcomes. Our studied rounds have a varied mix of business angel and formal venture capital investors (VCs). We find that when only angels participate in a financing round and VCs are absent, control rights are more entrepreneur-friendly, legal expenses are lower, and investors are more geographically proximate to the company. Such angel-backed companies are less likely to fail and are more likely to have a successful liquidity event. We find that companies financed exclusively by VC investors also perform well, particularly when deals are large. Companies financed by both angels and VCs experience inferior outcomes. Our results suggest that entrepreneurs consider business angels to be preferred investors and VCs investing in small deals face adverse selection. For larger deals, where deeper-pocket VC participation is required, these roles reverse and angels face adverse selection when investing alongside powerful VC syndicates.

The Interval of Observation

BEN Jacobsen — 2008-03-20T20:14:54-00:00

Social Science Research Network Working Paper Series (November 2007)

We revisit Kendall's (1953) conclusion that "the interval of observation may be very important" for stock market return predictability tests. Researchers to date mostly ignore this conclusion and routinely regress monthly observations on monthly observations. This is surprising because information aggregation should not take too long in near-efficient markets. Therefore the current practice of predicting stock returns using monthly observations may overlook short-term predictability. We show how conclusions regarding return predictability vary drastically when intervals of observation vary. If Kendall's famous "Demon of Chance" had handed him slightly different intervals of observation, Kendall might have concluded that stock returns were predictable.

A comparison of string distance metrics for name-matching tasks

W Cohen — 2007-12-19T15:02:15-00:00

(2003)

Using an open-source, Java toolkit of name-matching methods, we experimentally compare string distance metrics on the task of matching entity names. We investigate a number of different metrics proposed by different communities, including edit-distance metrics, fast heuristic string comparators , token-based distance metrics, and hybrid methods. Overall, the best-performing method is a hybrid scheme combining a TFIDF weighting scheme, which is widely used in information retrieval, with ...

Why We Have Never Used the Black-Scholes-Merton Option Pricing Formula (fourth version)

Espen Haug — 2008-02-04T21:24:40-00:00

Social Science Research Network Working Paper Series (January 2008)

Options traders use a pricing formula which they adapt by fudging and changing the tails and skewness by varying one parameter, the standard deviation of a Gaussian. Such formula is popularly called "Black-Scholes-Merton" owing to an attributed eponymous discovery (though changing the standard deviation parameter is in contradiction with it). However we have historical evidence that 1) Black, Scholes and Merton did not invent any formula, just found an argument to make a well known (and used) formula compatible with the economics establishment, by removing the "risk" parameter through "dynamic hedging", 2) Option traders use (and evidently have used since 1902) heuristics and tricks more compatible with the previous versions of the formula of Louis Bachelier and Edward O. Thorp (that allow a broad choice of probability distributions) and removed the risk parameter by using put-call parity. 3) Option traders did not use formulas after 1973 but continued their bottom-up heuristics. The Bachelier-Thorp approach is more robust (among other things) to the high impact rare event. The paper draws on historical trading methods and 19th and early 20th century references ignored by the finance literature. It is time to stop calling the formula by the wrong name.

Prices of Single Family Homes Since 1970: New Indexes for Four Cities

Karl Case — 2008-02-14T22:27:05-00:00

National Bureau of Economic Research Working Paper Series (September 1987), 2393.

Author contact info: Karl E. Case 125 Grove Street Wellesley, MA 02181 E-Mail: kcase@wellesley.edu Robert J. Shiller Yale University, Cowles Foundation Box 208281 30 Hillhouse Avenue, Room 23a New Haven, CT 06520-8281 Tel: 203/432-3708 Fax: 203/432-6167 E-Mail: robert.shiller@yale.edu This paper uses data on nearly a million homes sold in four metropolitan areas -- Atlanta, Chicago, Dallas and San Francisco -- to construct quarterly indexes of existing home prices between 1970 and 1986. We propose and apply a new method of constructing such indexes which we call the weighted repeat sales method (WRS). We believe the results give an accurate picture of the actual rate of appreciation in home prices in the four cities. The paper explains the construction of the index, discusses the results and compares them with the National Association of Realtors data on the median price of existing single family homes for the period 1981 - 1986.

Structure of growing social networks

Emily Jin — 2006-11-05T20:37:44-00:00

Physical Review E, Vol. 64, No. 4. (2001), 046132.

We propose some simple models of the growth of social networks; based on three general principles: (1) meetings take place between pairs of individuals at a rate that is high if a pair has one or more mutual friends and low otherwise; (2) acquaintances between pairs of individuals who rarely meet decay over time; (3) there is an upper limit on the number of friendships an individual can maintain. Using computer simulations; we find that models that incorporate all of these features reproduce many of the features of real social networks; including high levels of clustering or network transitivity and strong community structure in which individuals have more links to others within their community than to individuals from other communities.

Large Deviations for Heavy-Tailed Factor Models

Boualem Djehiche — 2007-12-21T15:22:45-00:00

(4 Dec 2007)

We study large deviation probabilities for a sum of dependent random variables from a heavy-tailed factor model, assuming that the components are regularly varying. We identify conditions where both the factor and the idiosyncratic terms contribute to the behaviour of the tail-probability of the sum. A simple conditional Monte Carlo algorithm is also provided together with a comparison between the simulations and the large deviation approximation. We also study large deviation probabilities for stochastic processes with factor structure. The processes involved are assumed to be Levy processes with regularly varying jump measures. Based on the results of the first part of the paper, we show that large deviations on a finite time interval are due to one large jump that can come from either the factor or the idiosyncratic part of the process.

Analysis of Kelly-optimal portfolios

Paolo Laureti — 2007-12-18T20:34:40-00:00

(17 Dec 2007)

We investigate the use of Kelly's strategy in the construction of an optimal portfolio of assets. With asset prices undergoing a multiplicative random process, we derive approximate analytical results for the optimal investment fractions under various constraints. We show that, when returns and volatilities of the assets are small and borrowing is forbidden, the Kelly-optimal portfolio lies on Markowitz Efficient Frontier. When short positions are also forbidden, only a small fraction of the available assets is included in the Kelly-optimal portfolio. This phenomenon, that we call condensation, is explored in detail.

Robust Portfolio Management

E Erdogan — 2007-12-10T21:35:04-00:00

In this paper we present robust models for index tracking and active portfolio management. The goal of these models is to control the e#ect of statistical errors in estimating market parameters on the performance of the portfolio. The proposed models allow one to impose additional side constraints such as bounds on the portfolio holdings, constraints on the portfolio beta, limits on cash exposure, etc. The optimal portfolios are computed by solving second-order cone programs. Since the...

Simrank++: Query rewriting through link analysis of the click graph

Ioannis Antonellis — 2007-12-07T22:25:43-00:00

(29 October 2007)

We focus on the problem of query rewriting for sponsored search. We base rewrites on a historical click graph that records the ads that have been clicked on in response to past user queries. Given a query q, we first consider Simrank as a way to identify queries similar to q, i.e., queries whose ads a user may be interested in. We argue that Simrank fails to properly identify query similarities in our application, and we present two enhanced version of Simrank: one that exploits weights on click graph edges and another that exploits “evidence.” We experimentally evaluate our new schemes against Simrank, using actual click graphs and queries form Yahoo!, and using a variety of metrics. Our results show that the enhanced methods can yield more and better query rewrites.

Robust portfolio selection problems

G Iyengar — 2006-05-13T09:26:08-00:00

In this paper we show how to formulate and solve robust portfolio selection problems. The objective of these robust formulations is to systematically combat the sensitivity of the optimal portfolio to statistical and modeling errors in the estimates of the relevant market parameters. We introduce "uncertainty structures" for the market parameters and show that the robust portfolio selection problems corresponding to these uncertainty structures can be reformulated as second-order cone programs...

Tagging Practices on Research Oriented Social Bookmarking Sites

Margaret Kipp — 2007-09-25T08:31:12-00:00

Improving Tag-Clouds as Visual Information Retrieval Interfaces

Y Hassan-Montero — 2007-12-02T19:32:59-00:00

(2006)

Tagging-based systems enable users to categorize web resources by means of tags (freely chosen keywords), in order to re-finding these resources later. Tagging is implicitly also a social indexing process, since users share their tags and resources, constructing a social tag index, so-called folksonomy. At the same time of tagging-based system, has been popularised an interface model for visual information retrieval known as Tag-Cloud. In this model, the most frequently used tags are displayed in alphabetical order. This paper presents a novel approach to Tag-Cloud’s tags selection, and proposes the use of clustering algorithms for visual layout, with the aim of improve browsing experience. The results suggest that presented approach reduces the semantic density of tag set, and improves the visual consistency of Tag-Cloud layout.

Robust optimization - A comprehensive survey

Hans-Georg Beyer — 2007-08-01T16:01:00-00:00

Computer Methods in Applied Mechanics and Engineering, Vol. 196, No. 33-34. (1 July 2007), pp. 3190-3218.

This paper reviews the state-of-the-art in robust design optimization - the search for designs and solutions which are immune with respect to production tolerances, parameter drifts during operation time, model sensitivities and others. Starting with a short glimps of Taguchi's robust design methodology, a detailed survey of approaches to robust optimization is presented. This includes a detailed discussion on how to account for design uncertainties and how to measure robustness (i.e., how to evaluate robustness). The main focus will be on the different approaches to perform robust optimization in practice including the methods of mathematical programming, deterministic nonlinear optimization, and direct search methods such as stochastic approximation and evolutionary computation. It discusses the strengths and weaknesses of the different methods, thus, providing a basis for guiding the engineer to the most appropriate techniques. It also addresses performance aspects and test scenarios for direct robust optimization techniques.

Volatility: A hidden Markov process in financial time series

Zoltán Eisler — 2007-12-04T18:24:27-00:00

Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), Vol. 76, No. 5. (2007)

Volatility characterizes the amplitude of price return fluctuations. It is a central magnitude in finance closely related to the risk of holding a certain asset. Despite its popularity on trading floors, volatility is unobservable and only the price is known. Diffusion theory has many common points with the research on volatility, the key of the analogy being that volatility is a time-dependent diffusion coefficient of the random walk for the price return. We present a formal procedure to extract volatility from price data by assuming that it is described by a hidden Markov process which together with the price forms a two-dimensional diffusion process. We derive a maximum-likelihood estimate of the volatility path valid for a wide class of two-dimensional diffusion processes. The choice of the exponential Ornstein-Uhlenbeck (expOU) stochastic volatility model performs remarkably well in inferring the hidden state of volatility. The formalism is applied to the Dow Jones index. The main results are that (i) the distribution of estimated volatility is lognormal, which is consistent with the expOU model, (ii) the estimated volatility is related to trading volume by a power law of the form V0.55, and (iii) future returns are proportional to the current volatility, which suggests some degree of predictability for the size of future returns.

Random graph models of social networks.

ME Newman — 2006-06-09T21:06:22-00:00

Proc Natl Acad Sci U S A, Vol. 99 Suppl 1 (19 February 2002), pp. 2566-2572.

We describe some new exactly solvable models of the structure of social networks, based on random graphs with arbitrary degree distributions. We give models both for simple unipartite networks, such as acquaintance networks, and bipartite networks, such as affiliation networks. We compare the predictions of our models to data for a number of real-world social networks and find that in some cases, the models are in remarkable agreement with the data, whereas in others the agreement is poorer, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.

Covariance and PCA for Categorical Variables

Hirotaka Niitsuma — 2007-11-29T23:01:33-00:00

(28 Nov 2007)

Covariances from categorical variables are defined using a regular simplex expression for categories. The method follows the variance definition by Gini, and it gives the covariance as a solution of simultaneous equations. The calculated results give reasonable values for test data. A method of principal component analysis (RS-PCA) is also proposed using regular simplex expressions, which allows easy interpretation of the principal components. The proposed methods apply to variable selection problem of categorical data USCensus1990 data. The proposed methods give appropriate criterion for the variable selection problem of categorical

Patterns of influence in a recommendation network

J Leskovec — 2007-04-09T15:40:22-00:00

(2005)

Information cascades are phenomena in which individuals adopt a new action or idea due to influence by others. As such a process spreads through an underlying social network, it can result in widespread adoption overall. We consider information cascades in the context of recommendations, and in particular study the patterns of cascading recommendations that arise in large social networks. We investigate a large person-to-person recommendation network, consisting of four million people...

Protection of New York City Urban Fabric With Low-Cost Textile Storm Surge Barriers

Alexander Bolonkin — 2007-11-06T15:18:23-00:00

(1 Oct 2007)

Textile storm surge barriers, sited at multiple locations, are literally extensions of the city world famous urban fabric - another manifestation of the dominance of the City over local Nature. Textile Storm Surge Barriers (TSSB) are intended to preserve the City from North Atlantic Ocean hurricanes that cause sea waves impacting the densely populated and high-value real estate, instigating catastrophic, and possibly long-term, infrastructure and monetary losses. Complicating TSSB installation macroproject planning is the presence of the Hudson and other rivers, several small tidal straits, future climate change and other factors. We conclude that TSSB installations made of homogeneous construction materials are worthwhile investigating because they may be less expensive to build, and more easily replaced following any failure, than concrete and steel storm surge barriers, which are also made of homogeneous materials. We suppose the best macroproject outcome will develop in the perfect Macro-engineering planning way and at the optimum time-of-need during the very early 21st Century by, among other groups, the Port Authority of New York and New Jersey. TSSB technology is a practical advance over wartime harbor anti-submarine/anti-torpedo steel nets and rocky Churchill Barriers.

Statistical physics of social dynamics

Claudio Castellano — 2007-10-18T16:28:55-00:00

(17 Oct 2007)

Statistical physics has proven to be a very fruitful framework to describe phenomena outside the realm of traditional physics. The last years have witnessed the attempt by physicists to study collective phenomena emerging from the interactions of individuals as elementary units in social structures. Here we review the state of the art by focusing on three major research lines i.e., opinion, cultural and language dynamics. In addition we discuss other social phenomena, such as crowd behavior, hierarchy formation, human dynamics, social spreading. We highlight the connections between these problems and other, more traditional, topics of statistical physics. We also emphasize the comparison of model results with empirical data from social systems.

Tagging, Folksonomy & Co - Renaissance of Manual Indexing?

Jakob Voss — 2007-01-29T14:34:58-00:00

(26 Jan 2007)

This paper gives an overview of current trends in manual indexing on the Web. Along with a general rise of user generated content there are more and more tagging systems that allow users to annotate digital resources with tags (keywords) and share their annotations with other users. Tagging is frequently seen in contrast to traditional knowledge organization systems or as something completely new. This paper shows that tagging should better be seen as a popular form of manual indexing on the Web. Difference between controlled and free indexing blurs with sufficient feedback mechanisms. A revised typology of tagging systems is presented that includes different user roles and knowledge organization systems with hierarchical relationships and vocabulary control. A detailed bibliography of current research in collaborative tagging is included.

Folksonomies and clustering in the collaborative system CiteULike

Andrea Capocci — 2007-10-16T18:24:15-00:00

(15 Oct 2007)

We analyze CiteULike, an online collaborative tagging system where users bookmark and annotate scientific papers. Such a system can be naturally represented as a tripartite graph whose nodes represent papers, users and tags connected by individual tag assignments. The semantics of tags is studied here, in order to uncover the hidden relationships between tags. We find that the clustering coefficient reflects the semantical patterns among tags, providing useful ideas for the designing of more efficient methods of data classification and spam detection.

Programming distributed erlang applications: pitfalls and recipes

Hans Svensson — 2007-10-11T22:59:07-00:00

(2007), pp. 37-42.

Plagiarism Detection in arXiv

Daria Sorokina — 2007-10-10T17:34:20-00:00

(1 Feb 2007)

We describe a large-scale application of methods for finding plagiarism in research document collections. The methods are applied to a collection of 284,834 documents collected by arXiv.org over a 14 year period, covering a few different research disciplines. The methodology efficiently detects a variety of problematic author behaviors, and heuristics are developed to reduce the number of false positives. The methods are also efficient enough to implement as a real-time submission screen for a collection many times larger.

Winnowing: local algorithms for document fingerprinting

S Schleimer — 2007-10-10T17:31:45-00:00

(2003)

Digital content is for copying: quotation, revision, plagiarism, and file sharing all create copies. Document fingerprinting is concerned with accurately identifying copying, including small partial copies, within large sets of documents.

Probabilistic principal component analysis

M Tipping — 2006-02-20T12:43:23-00:00

(1997)

Principal component analysis (PCA) is a ubiquitous technique for data analysis and processing, but one which is not based upon a probability model. In this paper we demonstrate how the principal axes of a set of observed data vectors may be determined through maximum-likelihood estimation of parameters in a latent variable model closely related to factor analysis. We consider the properties of the associated likelihood function, giving an EM algorithm for estimating the principal subspace...

Singular Value Decomposition and Principal Component Analysis

Michael Wall — 2005-10-17T02:36:40-00:00

(3 Mar 2003), pp. 91-109.

This chapter describes gene expression analysis by Singular Value Decomposition (SVD), emphasizing initial characterization of the data. We describe SVD methods for visualization of gene expression data, representation of the data using a smaller number of variables, and detection of patterns in noisy gene expression data. In addition, we describe the precise relation between SVD analysis and Principal Component Analysis (PCA) when PCA is calculated using the covariance matrix, enabling our descriptions to apply equally well to either method. Our aim is to provide definitions, interpretations, examples, and references that will serve as resources for understanding and extending the application of SVD and PCA to gene expression analysis.

Singular value decomposition - a primer

S Leach — 2006-02-05T15:49:39-00:00

Introduction The singular value decomposition (SVD) is a powerful technique in many matrix computations and analyses. Using the SVD of a matrix in computations, rather than the original matrix, has the advantage of being more robust to numerical error. Additionally, the SVD exposes the geometric structure of a matrix, an important aspect of many matrix calculations. A matrix can be described as a tranformation from one vector space to another. The components of the SVD quantify the resulting...