| With the increase of online social networking applications, rich social network data can be obtained from the Internet, including the friendship network and user-generated content (e.g., users opinions, comments, photos, etc.). Recently, mining such rich social network data has been attracted growing interesting. In this thesis, we investigate several important issues of social network mining which are link prediction, bias and prestige evaluation, ranking, and random walk domination. First, link prediction is a problem of predicting the probability of which two users create a connection in the near future based on the current friendship structure. Second, the bias and prestige evaluation problem aims at computing the bias and prestige of the individuals based on their opinions in a trust social network, where the links represent the trust relationships between the individuals. Third, the ranking problem in social network is a problem of ranking the users according to certain predefined scoring functions (e.g., personalized PageRank). In this research, we consider two types of ranking problems for network data: diversified ranking and reputation-based ranking. Unlike the traditional ranking, the scoring function of the diversified ranking captures both relevant and diversity, which requires the users in the top-k ranking list dissimilar to one another. The reputation-based ranking are tailored for bipartite rating networks, which includes two types of entities: users and objects. In such a network, users can give ratings to objects. The goal of the reputation-based ranking problem is to rank the objects based on users' reputation and ratings. Finally, the aim of the random walk domination problem is to target a small group of users in a network so that as many users as possible can be easily reachable to those targeted users by random walk.;The objective of this thesis is to develop effective and efficient algorithms for the above social network mining issues. Specifically, for the link prediction problem, we propose several maximal entropy random walk (MERW) based algorithms which incorporate the eigenvector centrality of the nodes in the random walk process. The main advantage of the MERW-based algorithms is that it captures, to some extent, the nature of the link formation process where the users prefer to link to the users with high centrality. For the bias and prestige evaluation problem, we present a general framework with provable convergence guarantee, which includes a rich family of algorithms. The proposed framework provides a general guideline to devise bias and prestige evaluation algorithm in trust social network. We also apply this framework to bipartite rating networks which results in a set of robust reputation-based ranking algorithms. For the diversified ranking problem, we present a new diversified ranking measure, and a scalable algorithm with near-optimal performance guarantee to optimize the measure. For the random walk domination problem, we are the first to formulate this problem and propose several effective and efficient algorithmic treatments. The algorithms proposed for this problem are not only scalable, but they are also with near-optimal performance guarantee. For all of the above problems, we conduct extensive experiments to evaluate the proposed algorithms, and the results demonstrate the effectiveness and efficiency of the algorithms. |
