Online social networks have quickly become the most popular destination on the World Wide Web. These networks are still a fairly new form of online human interaction and have gained wide popularity only recently within the past three to four years. Few models or descriptions of the dynamics of these systems exist. This is largely due to the difficulty in gaining access to the data from these networks which is often viewed as very valuable. In these networks, members maintain list of friends with which they share content with by first uploading it to the social network service provider. The content is then distributed to members by the service provider who generates a feed for each member containing the content shared by all of the member's friends aggregated together. Direct access to dynamic linkage data for these large networks is especially difficult without a special relationship with the service provider. This makes it difficult for researchers to explore and better understand how humans interface with these systems. This dissertation examines an event driven sampling approach to acquire both dynamics link event data and blog content from the site known as LiveJournal. LiveJournal is one of the oldest online social networking sites whose features are very similar to sites such as Facebook and Myspace yet smaller in scale as to be practical for a research setting. The event driven sampling methodology and analysis of the resulting network model provide insights for other researchers interested in acquiring social network dynamics from LiveJournal or insight into what might be expected if an event driven sampling approach was applied to other online social networks. A detailed analysis of both the static structure and network dynamics of the resulting network model was performed. The analysis helped motivated work on a model of link prediction using both topological and content-based metrics. The relationship between topological and content-based metrics was explored. Factored into the link prediction analysis is the open nature of the social network data where new members are constantly joining and current members are leaving. The data used for the analysis spanned approximately two years.

No description available.

No description available.

A predição de links em redes é uma tarefa com aplicações em diversos cenários. Com a automatização de processos, as redes sociais, redes tecnológicas e outras cresceram muito em número de vértices e arestas. Portanto, a utilização de preditores de links em redes com alta complexidade estrutural não é trivial, mesmo considerando algoritmos de baixa complexidade computacional. A grande quantidade de operações necessárias para que os preditores possam escolher quais arestas são promissoras torna o processo de considerar a rede toda inviável na maioria dos casos. As abordagens existentes enfrentam essa característica de diversas formas, sendo que as mais populares são as que limitam o conjunto de pares de vértices que serão considerados para existência de arestas promissoras. Este projeto aborda a criação de uma estratégia que utiliza otimização multinível para contrair as redes, executar os algoritmos de predição de links nas redes contraídas e projetar os resultados de predição para a rede original, para reduzir o número de operações necessárias à predição de links. Os resultados mostram que a abordagem consegue reduzir o tempo necessário para predição, apesar de perdas esperadas na qualidade na predição. / Link prediction in networks is a task with applications in several scenarios. With the automation of processes, social networks, technological networks, and others have grown considerably in the number of vertices and edges. Therefore, the creation of systems for link prediction in networks of high structural complexity is not a trivial process, even considering low-complexity algorithms. The large number of operations required for predicting which edges are promising makes the considering of the whole network impracticable in many cases. The existing approaches face this characteristic in several ways, and the most popular are those that limit the set of vertex pairs that will be considered for the existence of promising edges. This project addresses a strategy that uses multilevel optimization to coarse networks, execute prediction algorithms on coarsened networks and project the results back to the original network, in order to reduce the number of operations for link prediction. The experiments show that the approach can reduce the time despite some expected losses of accuracy.

L'objectif de cette thèse est de développer des outils de prédiction d'interactions entre protéines qui puissent être appliqués en particulier sur le réseau d’interaction autour de la protéine CFTR, qui est impliquée dans la mucoviscidose. Le développement de méthodes de prédiction in silico peut s'avérer utile pour suggérer aux biologistes de nouvelles cibles d'interaction. Nous proposons une nouvelle méthode pour la prédiction de liens dans un réseau. Afin de bénéficier de l'information des données non étiquetées, nous nous plaçons dans le cadre de l'apprentissage semi-supervisé. Nous abordons ce problème de prédiction comme une tâche d'apprentissage d'un noyau de sortie. Un noyau de sortie est supposé coder les proximités existantes entres les nœuds du graphe et l'objectif est d'approcher ce noyau à partir de descriptions appropriées en entrée. L'utilisation de l'astuce du noyau dans l'ensemble de sortie permet de réduire le problème d'apprentissage à celui d'une fonction d'une seule variable à valeurs dans un espace de Hilbert. En choisissant les fonctions candidates pour la régression dans un espace de Hilbert à noyau reproduisant à valeur opérateur, nous développons, comme dans le cas de fonctions à valeurs scalaires, des outils de régularisation. Nous établissons en particulier des théorèmes de représentation, qui permettent de définir de nouveaux modèles de régression. Nous avons testé l'approche développée sur des données artificielles, des problèmes test ainsi que sur un réseau d'interaction chez la levure et obtenu de très bons résultats. Puis nous l'avons appliquée à la prédiction d'interactions entre protéines dans le cas d'un réseau construit autour de CFTR. / The aim of this thesis is to develop tools for predicting interactions between proteins that can be applied to the human proteins forming a network with the CFTR protein. This protein, when defective, is involved in cystic fibrosis. The development of in silico prediction methods can be useful for biologists to suggest new interaction targets. We propose a new method to solve the link prediction problem. To benefit from the information of unlabeled data, we place ourselves in the semi-supervised learning framework. Link prediction is addressed as an output kernel learning task, referred as Output Kernel Regression. An output kernel is assumed to encode the proximities of nodes in the target graph and the goal is to approximate this kernel by using appropriate input features. Using the kernel trick in the output space allows one to reduce the problem of learning from pairs to learning a single variable function with output values in a Hilbert space. By choosing candidates for regression functions in a reproducing kernel Hilbert space with operator valued kernels, we develop tools for regularization as for scalar-valued functions. We establish representer theorems in the supervised and semi-supervised cases and use them to define new regression models for different cost functions. We first tested the developed approach on transductive link prediction using artificial data, benchmark data as well as a protein-protein interaction network of the yeast and we obtained very good results. Then we applied it to the prediction of protein interactions in a network built around the CFTR protein.

A predição de links em redes é uma tarefa com aplicações em diversos cenários. Com a automatização de processos, as redes sociais, redes tecnológicas e outras cresceram muito em número de vértices e arestas. Portanto, a utilização de preditores de links em redes com alta complexidade estrutural não é trivial, mesmo considerando algoritmos de baixa complexidade computacional. A grande quantidade de operações necessárias para que os preditores possam escolher quais arestas são promissoras torna o processo de considerar a rede toda inviável na maioria dos casos. As abordagens existentes enfrentam essa característica de diversas formas, sendo que as mais populares são as que limitam o conjunto de pares de vértices que serão considerados para existência de arestas promissoras. Este projeto aborda a criação de uma estratégia que utiliza otimização multinível para contrair as redes, executar os algoritmos de predição de links nas redes contraídas e projetar os resultados de predição para a rede original, para reduzir o número de operações necessárias à predição de links. Os resultados mostram que a abordagem consegue reduzir o tempo necessário para predição, apesar de perdas esperadas na qualidade na predição. / Link prediction in networks is a task with applications in several scenarios. With the automation of processes, social networks, technological networks, and others have grown considerably in the number of vertices and edges. Therefore, the creation of systems for link prediction in networks of high structural complexity is not a trivial process, even considering low-complexity algorithms. The large number of operations required for predicting which edges are promising makes the considering of the whole network impracticable in many cases. The existing approaches face this characteristic in several ways, and the most popular are those that limit the set of vertex pairs that will be considered for the existence of promising edges. This project addresses a strategy that uses multilevel optimization to coarse networks, execute prediction algorithms on coarsened networks and project the results back to the original network, in order to reduce the number of operations for link prediction. The experiments show that the approach can reduce the time despite some expected losses of accuracy.

No description available.

No description available.

Master of Science / Department of Computing and Information Sciences / Doina Caragea / The idea of socializing with other people of different backgrounds and cultures excites the web surfers. Today, there are hundreds of Social Networking sites on the web with millions of users connected with relationships such as "friend", "follow", "fan", forming a huge graph structure. The amount of data associated with the users in these Social Networking sites has resulted in opportunities for interesting data mining problems including friendship link and interest predictions, tag recommendations among others. In this work, we consider the friendship link prediction problem and study a topic modeling approach to this problem. Topic models are among the most effective approaches to latent topic analysis and mining of text data. In particular, Probabilistic Topic models are based upon the idea that documents can be seen as mixtures of topics and topics can be seen as mixtures of words. Latent Dirichlet Allocation (LDA) is one such probabilistic model which is generative in nature and is used for collections of discrete data such as text corpora. For our link prediction problem, users in the dataset are treated as "documents" and their interests as the document contents. The topic probabilities obtained by modeling users and interests using LDA provide an explicit representation for each user. User pairs are treated as examples and are represented using a feature vector constructed from the topic probabilities obtained with LDA. This vector will only capture information contained in the interests expressed by the users. Another important source of information that is relevant to the link prediction task is given by the graph structure of the social network. Our assumption is that a user "A" might be a friend of user "B" if a) users "A" and "B" have common or similar interests b) users "A" and "B" have some common friends. While capturing similarity between interests is taken care by the topic modeling technique, we use the graph structure to find common friends. In the past, the graph structure underlying the network has proven to be a trustworthy source of information for predicting friendship links. We present a comparison of predictions from feature sets constructed using topic probabilities and the link graph separately, with a feature set constructed using both topic probabilities and link graph.

Master of Science / Department of Computing and Information Sciences / Doina Caragea / Recent advances in social network applications have resulted in millions of users joining such networks in the last few years. User data collected from social networks can be used for various data mining problems such as interest recommendations, friendship recommendations and many more. Social networks, in general, can be seen as a huge directed network graph representing users of the network (together with their information, e.g., user interests) and their interactions (also known as friendship links). Previous work [Hsu et al., 2007] on friendship link prediction has shown that graph features contain important predictive information. Furthermore, it has been shown that user interests can be used to improve link predictions, if they are organized into an explicitly or implicitly ontology [Haridas, 2009; Parimi, 2010]. However, the above mentioned previous studies have been performed using a small set of users in the social network LiveJournal. The goal of this work is to study the performance of the ontology based approach proposed in [Haridas, 2009], when number of users in the dataset is increased. More precisely, we study the performance of the approach in terms of performance for data sets consisting of 1000, 2000, 3000 and 4000 users. Our results show that the performance generally increases with the number of users. However, the problem becomes quickly intractable from a computation time point of view. As a part of our study, we also compare our results obtained using the ontology-based approach [Haridas, 2009] with results obtained with the LDA based approach in [Parimi, 2010], when such results are available.