Link Prediction based on Structural Properties of Online Social Networks

Question-Answering Bulletin Boards (QABB), such as Yahoo! Answers and Windows Live QnA, are gaining popularity recently. Questions are submitted on QABB and let somebody in the internet answer them. Communications on QABB connect users, and the overall connections can be regarded as a social network. If the evolution of social networks can be predicted, it is quite useful for encouraging communications among users. Link prediction on QABB can be used for recommendation to potential answerers. Previous approaches for link prediction based on structural properties do not take weights of links into account. This paper describes an improved method for predicting links based on weighted proximity measures of social networks. The method is based on an assumption that proximities between nodes can be estimated better by using both graph proximity measures and the weights of existing links in a social network. In order to show the effectiveness of our method, the data of Yahoo! Chiebukuro (Japanese Yahoo! Answers) are used for our experiments. The results show that our method outperforms previous approaches, especially when target social networks are sufficiently dense.

Exploiting User Interests to Characterize Navigational Patterns in Web Browsing Assistance

In order to be capable of exploiting context for pro-active information recommendation, agents need to extract and understand user activities based on their knowledge of the user interests. In this paper, we propose a novel approach for context-aware recommendation in browsing assistants based on the integration of user profiles, navigational patterns and contextual elements. In this approach, user profiles built using an unsupervised Web page clustering algorithm are used to characterize user ongoing activities and behavior patterns. Experimental evidence show that using longer-term interests to explain active browsing goals user assistance is effectively enhanced.

Numerical simulation of a nonlinearly coupled Schrödinger system: A linearly uncoupled finite difference scheme

This article describes a finite difference scheme which is linearly uncoupled in computation for a nonlinearly coupled Schrödinger system. This numerical scheme is proved to preserve the original conservative properties. Using the discrete energy analysis method, we also prove that the scheme is unconditionally stable and second-order convergent in discrete _L2$L_2$-norm based on some preliminary estimations. The results show that the new scheme is efficiency.     

Techniques for pipelined broadcast on ethernet switched clusters

By splitting a large broadcast message into segments and broadcasting the segments in a pipelined fashion, pipelined broadcast can achieve high performance in many systems. In this paper, we investigate techniques for efficient pipelined broadcast on clusters connected by multiple Ethernet switches. Specifically, we develop algorithms for computing various contention-free broadcast trees that are suitable for pipelined broadcast on Ethernet switched clusters, extend the parametrized LogP model for predicting appropriate segment sizes for pipelined broadcast, show that the segment sizes computed based on the model yield high performance, and evaluate various pipelined broadcast schemes through experimentation on Ethernet switched clusters with various topologies. The results demonstrate that our techniques are practical and efficient for contemporary fast Ethernet and Giga-bit Ethernet clusters.     

A Level-Set Method for Computing the Eigenvalues of Elliptic Operators Defined on Compact Hypersurfaces

We demonstrate, through separation of variables and estimates from the semi-classical analysis of the Schrödinger operator, that the eigenvalues of an elliptic operator defined on a compact hypersurface in ? ⁿ can be found by solving an elliptic eigenvalue problem in a bounded domain Ω?? ⁿ . The latter problem is solved using standard finite element methods on the Cartesian grid. We also discuss the application of these ideas to solving evolution equations on surfaces, including a new proof of a result due to Greer (J. Sci. Comput. 29(3):321–351, 2006).     

A Numerical Study of Diagonally Split Runge–Kutta Methods for PDEs with Discontinuities

Diagonally split Runge–Kutta (DSRK) time discretization methods are a class of implicit time-stepping schemes which offer both high-order convergence and a form of nonlinear stability known as unconditional contractivity. This combination is not possible within the classes of Runge–Kutta or linear multistep methods and therefore appears promising for the strong stability preserving (SSP) time-stepping community which is generally concerned with computing oscillation-free numerical solutions of PDEs. Using a variety of numerical test problems, we show that although second- and third-order unconditionally contractive DSRK methods do preserve the strong stability property for all time step-sizes, they suffer from order reduction at large step-sizes. Indeed, for time-steps larger than those typically chosen for explicit methods, these DSRK methods behave like first-order implicit methods. This is unfortunate, because it is precisely to allow a large time-step that we choose to use implicit methods. These results suggest that unconditionally contractive DSRK methods are limited in usefulness as they are unable to compete with either the first-order backward Euler method for large step-sizes or with Crank–Nicolson or high-order explicit SSP Runge–Kutta methods for smaller step-sizes. We also present stage order conditions for DSRK methods and show that the observed order reduction is associated with the necessarily low stage order of the unconditionally contractive DSRK methods. The work of C.B. Macdonald was partially supported by an NSERC Canada PGS-D scholarship, a grant from NSERC Canada, and a scholarship from the Pacific Institute for the Mathematical Sciences (PIMS). The work of S. Gottlieb was supported by AFOSR grant number FA9550-06-1-0255. The work of S.J. Ruuth was partially supported by a grant from NSERC Canada.     

Feature selection via sensitivity analysis of SVM probabilistic outputs

Feature selection is an important aspect of solving data-mining and machine-learning problems. This paper proposes a feature-selection method for the Support Vector Machine (SVM) learning. Like most feature-selection methods, the proposed method ranks all features in decreasing order of importance so that more relevant features can be identified. It uses a novel criterion based on the probabilistic outputs of SVM. This criterion, termed Feature-based Sensitivity of Posterior Probabilities (FSPP), evaluates the importance of a specific feature by computing the aggregate value, over the feature space, of the absolute difference of the probabilistic outputs of SVM with and without the feature. The exact form of this criterion is not easily computable and approximation is needed. Four approximations, FSPP1-FSPP4, are proposed for this purpose. The first two approximations evaluate the criterion by randomly permuting the values of the feature among samples of the training data. They differ in their choices of the mapping function from standard SVM output to its probabilistic output: FSPP1 uses a simple threshold function while FSPP2 uses a sigmoid function. The second two directly approximate the criterion but differ in the smoothness assumptions of criterion with respect to the features. The performance of these approximations, used in an overall feature-selection scheme, is then evaluated on various artificial problems and real-world problems, including datasets from the recent Neural Information Processing Systems (NIPS) feature selection competition. FSPP1-3 show good performance consistently with FSPP2 being the best overall by a slight margin. The performance of FSPP2 is competitive with some of the best performing feature-selection methods in the literature on the datasets that we have tested. Its associated computations are modest and hence it is suitable as a feature-selection method for SVM applications. Editor: Risto Miikkulainen.     

The Impact of Speculative Execution on SMT Processors

By executing two or more threads concurrently, Simultaneous MultiThreading (SMT) architectures are able to exploit both Instruction-Level Parallelism (ILP) and Thread-Level Parallelism (TLP) from the increased number of in-flight instructions that are fetched from multiple threads. However, due to incorrect control speculations, a significant number of these in-flight instructions are discarded from the pipelines of SMT processors (which is a direct consequence of these pipelines getting wider and deeper). Although increasing the accuracy of branch predictors may reduce the number of instructions so discarded from the pipelines, the prediction accuracy cannot be easily scaled up since aggressive branch prediction schemes strongly depend on the particular predictability inherently to the application programs. In this paper, we present an efficient thread scheduling mechanism for SMT processors, called SAFE-T (Speculation-Aware Front-End Throttling): it is easy to implement and allows an SMT processor to selectively perform speculative execution of threads according to the confidence level on branch predictions, hence preventing wrong-path instructions from being fetched. SAFE-T provides an average reduction of 57.9% in the number of discarded instructions and improves the instructions per cycle (IPC) performance by 14.7% on average over the ICOUNT policy across the multi-programmed workloads we simulate. This paper is an extended version of the paper, “Speculation Control for Simultaneous Multithreading,” which appeared in the Proceedings of the 18th International Parallel and Distributed Processing Symposium, Santa Fe, New Mexico, April 2004.     

Boosted Bayesian network classifiers

The use of Bayesian networks for classification problems has received a significant amount of recent attention. Although computationally efficient, the standard maximum likelihood learning method tends to be suboptimal due to the mismatch between its optimization criteria (data likelihood) and the actual goal of classification (label prediction accuracy). Recent approaches to optimizing classification performance during parameter or structure learning show promise, but lack the favorable computational properties of maximum likelihood learning. In this paper we present boosted Bayesian network classifiers, a framework to combine discriminative data-weighting with generative training of intermediate models. We show that boosted Bayesian network classifiers encompass the basic generative models in isolation, but improve their classification performance when the model structure is suboptimal. We also demonstrate that structure learning is beneficial in the construction of boosted Bayesian network classifiers. On a large suite of benchmark data-sets, this approach outperforms generative graphical models such as naive Bayes and TAN in classification accuracy. Boosted Bayesian network classifiers have comparable or better performance in comparison to other discriminatively trained graphical models including ELR and BNC. Furthermore, boosted Bayesian networks require significantly less training time than the ELR and BNC algorithms.