| Social networks exist in many places throughout the world. A typical example of a social network captures a group of human beings and their associated interactions, with vertices representing human beings and links representing human interactions. Most social networks are dynamic, and they grow with both vertices and links. From the perspective of link analysis, link prediction is a fundamental task, because social network growth and development depend heavily on user interactions, and link prediction results can be easily applied to boost user interactions. Also, link prediction has a wide range of applications, such as recommendation systems. In this thesis, our research aims at developing effective link prediction models.;In the real world, most social networks are heterogeneous and have various types of links. However, current social network research often treat all links homogeneously. Such a simplification has negative implications for link prediction. Different types of links have different properties. We should be able identify such properties to design distinctive models to predict different links. Also, by identifying link types, we can focus on only those links that are under our interests, and break large social networks into small subnetworks to increase computational efficiency in link prediction. Thus, to facilitate link prediction, and to achieve a deeper understanding of social networks, we also need effective link classification models.;To conduct our research for link prediction, we design two recommender systems and test their effectiveness on data from a major U.S. online dating site. Online dating is a fast growing market in recent years, and most sites adopt recommender systems to suggest potential dates. We notice that, for most social networks, new links can be introduced in two ways. First, they can be added when new members join. Second, existing members can establish connections among themselves. As a result, we conduct two distinctive studies. In the first study, we aim to provide reciprocal online dating recommendation for new users. To accomplish this task, we take a hybrid approach. We analyze the preferences of existing users based on their activities, and cluster them into different communities. We then link new users to such communities in a probabilistic way and make recommendations for new users based on activities of communities formed by existing users. Compared with the baseline, our model achieves significant improvements across multiple evaluations. In the second study, we analyze interaction patterns for existing online dating users and design a new collaborative filtering algorithm to make recommendations for them. The algorithm considers both the taste and attractiveness of users. We apply these two considerations to two main design stages of collaborative filtering. When compared against two separate baselines, our algorithm achieves better results in both precision and recall, especially for those reciprocal connections.;Because links in online dating networks are homogeneous, we take another dataset for our research of link classification. We conduct a study on a cellphone network, where some of its user pairs are labeled with one of three relationship types. Cellphone networks are some of the largest social networks in the world, and they contain various types of links. To design an effective method of classifying user pairs, we extract three categories of features: network topology, communication, and co-location features. By applying several classification algorithms over these features, we successfully classify three types of links. We also find that communication features are very powerful in identifying family relationship, while co-location features provide best performance in identifying colleague relationships.;With this research, we hope to provide some insights about the origin, development, and nature of links in social networks. |
