Nowadays, large collections of photos are tagged with GPS coordinates. The modelling of such large geo-tagged corpora is an important problem in data mining and information retrieval, and involves the use of geographical information to detect topics with a spatial component. In this paper, we propose a novel geographical topic model which captures dependencies between geographical regions to support the detection of topics with complex, non-Gaussian distributed spatial structures. The model is based on a multi-Dirichlet process (MDP), a novel generalisation of the hierarchical Dirichlet process extended to support multiple base distributions. Our method thus is called the MDP-based geographical topic model (MGTM). We show how to use a MDP to dynamically smooth topic distributions between groups of spatially adjacent documents. In systematic quantitative and qualitative evaluations using independent datasets from prior related work, we show that such a model can exploit the adjacency of regions and leads to a significant improvement in the quality of topics compared to the state of the art in geographical topic modelling.

This paper presents a technique for analysis of dynamic contact networks aimed at extracting periods of time during which the network changes behaviour. The technique is based on tracking the eigenvectors of the contact network in time (efficiently) using a technique called Joint Diagonalisation (JD). Repeated application of JD then shows that real-world networks naturally break into several modes of operation which are time dependent and in one real-world case, even periodic. This shows that a view of real-world contact networks as realisations from a single underlying static graph is mistaken. However, the analysis also shows that a small finite set of underlying static graphs can approximate the dynamic contact graphs studied. We also provide the means by which these underlying approximate graphs can be constructed.

We investigate the "negative link" feature of social networks that allows users to tag other users as foes or as distrusted in addition to the usual friend and trusted links. To answer the question whether negative links have an added value for an online social network, we investigate the machine learning problem of predicting the negative links of such a network using only the positive links as a basis, with the idea that if this problem can be solved with high accuracy, then the "negative link" feature is redundant. In doing so, we also present a general methodology for assessing the added value of any new link type in online social networks. Our evaluation is performed on two social networks that allow negative links: The technology news website Slashdot and the product review site Epinions. In experiments with these two datasets, we come to the conclusion that a combination of centrality-based and proximity-based link prediction functions can be used to predict the negative edges in the networks we analyse. We explain this result by an application of the models of preferential attachment and balance theory to our learning problem, and show that the "negative link" feature has a small but measurable added value for these social networks.

We present a method for trust prediction based on no diagonal decompositions of the asymmetric adjacency matrix of a directed network. The method we propose is based on a no diagonal decomposition into directed components (DEDICOM), which we use to learn the coefficients of a matrix polynomial of the network's adjacency matrix. We show that our method can be used to compute better low-rank approximations to a polynomial of a network's adjacency matrix than using the singular value decomposition, and that a higher precision can be achieved at the task of predicting directed links than by undirected or bipartite methods.

Two of the main challenges in retrieval on microblogs are the inherent sparsity of the documents and difficulties in assessing their quality. The feature sparsity is immanent to the restriction of the medium to short texts. Quality assessment is necessary as the microblog documents range from spam over trivia and personal chatter to news broadcasts, information dissemination and reports of current hot topics. In this paper we analyze how these challenges can influence standard retrieval models and propose methods to overcome the problems they pose. We consider the sparsity's effect on document length normalization and introduce "interestingness" as static quality measure. Our results show that deliberately ignoring length normalization yields better retrieval results in general and that interestingness improves retrieval for underspecified queries.

We introduce and study the spectral evolution model, which characterizes the growth of large networks in terms of the eigenvalue decomposition of their adjacency matrices: In large networks, changes over time result in a change of a graph's spectrum, leaving the eigenvectors unchanged. We validate this hypothesis for several large social, collaboration, authorship, rating, citation, communication and tagging networks, covering unipartite, bipartite, signed and unsigned graphs. Following these observations, we introduce a link prediction algorithm based on the extrapolation of a network's spectral evolution. This new link prediction method generalizes several common graph kernels that can be expressed as spectral transformations. In contrast to these graph kernels, the spectral extrapolation algorithm does not make assumptions about specific growth patterns beyond the spectral evolution model. We thus show that it performs particularly well for networks with irregular, but spectral, growth patterns.

We study the application of spectral clustering, prediction and visualization methods to graphs with negatively weighted edges. We show that several characteristic matrices of graphs can be extended to graphs with positively and negatively weighted edges, giving signed spectral clustering methods, signed graph kernels and network visualization methods that apply to signed graphs. In particular, we review a signed variant of the graph Laplacian. We derive our results by considering random walks, graph clustering, graph drawing and electrical networks, showing that they all result in the same formalism for handling negatively weighted edges. We illustrate our methods using examples from social networks with negative edges and bipartite rating graphs.

We present a unified framework for learning link prediction and edge weight prediction functions in large networks, based on the transformation of a graph's algebraic spectrum. Our approach generalizes several graph kernels and dimensionality reduction methods and provides a method to estimate their parameters efficiently. We show how the parameters of these prediction functions can be learned by reducing the problem to a one-dimensional regression problem whose runtime only depends on the method's reduced rank and that can be inspected visually. We derive variants that apply to undirected, weighted, unweighted, unipartite and bipartite graphs. We evaluate our method experimentally using examples from social networks, collaborative filtering, trust networks, citation networks, authorship graphs and hyperlink networks.

We analyse the corpus of user relationships of the Slashdot technology news site. The data was collected from the Slashdot Zoo feature where users of the website can tag other users as friends and foes, providing positive and negative endorsements. We adapt social network analysis techniques to the problem of negative edge weights. In particular, we consider signed variants of global network characteristics such as the clustering coefficient, node-level characteristics such as centrality and popularity measures, and link-level characteristics such as distances and similarity measures. We evaluate these measures on the task of identifying unpopular users, as well as on the task of predicting the sign of links and show that the network exhibits multiplicative transitivity which allows algebraic methods based on matrix multiplication to be used. We compare our methods to traditional methods which are only suitable for positively weighted edges.

We extend the resistance distance kernel to the domain of signed dissimilarity values, and show how it can be applied to collaborative rating prediction. The resistance distance is a graph kernel inspired by electrical network models where edges of a graph are interpreted as electrical resistances. We model the similarity between users of a large collaborative rating database using this signed resistance distance, generalizing the previously known regular resistance distance kernel which is limited to nonnegative values. We show that the signed resistance distance kernel can be computed effectively using the Moore-Penrose pseudoinverse of the Laplacian matrix of the bipartite rating graph, leading to fast computation based on the eigenvalue decomposition of the Laplacian matrix. We apply this technique to collaborative rating prediction on the Netflix Prize corpus, and show how our new kernel can replace the traditional Pearson correlation for rating prediction.

Given a bipartite graph of collaborative ratings, the task of recommendation and rating prediction can be modeled with graph kernels. We interpret these graph kernels as the inverted squared Euclidean distance in a space defined by the underlying graph and show that this inverted squared Euclidean similarity function can be replaced by other similarity functions. We evaluate several such similarity functions in the context of collaborative item recommendation and rating prediction, using the exponential diffusion kernel, the von Neumann kernel, and the random forest kernel as a basis. We find that the performance of graph kernels for these tasks can be increased by using these alternative similarity functions.

Some of the established approaches to evaluating text clustering algorithms for information retrieval show theoretical flaws. In this paper, we analyze these flaws and introduce a new evaluation measure to overcome them. Based on a simple yet rigorous mathematical analysis of the effect of certain parameters in cluster based retrieval, we show that certain conclusions drawn in the recent literature must be taken with a grain of salt. Our new measure, in contrast, accounts for statistical biases that have to be expected according to our analysis. A series of experiments and a comparison with results reported recently underlines that this measure is a more suitable performance indicator that allows for more meaningful interpretations.

The Internet is a vast resource of information. Unfortunately, finding and accessing this information is often a very cumbersome task even with existing information platforms. Searching on the WWW suffers from the fact that almost every word is ambiguous to a certain degree in the information-rich environment of the Internet. Clustering search results is a way to solve this problem. This paper demonstrates how to employ novel Information Retrieval measures to derive optimal parametrizations for a cluster algorithm.