Research On Link Prediction And Community Mining Based On Social Network

With the booming of social era, more attention has been attracted to research fields those base on social networks, such as social recommendation system and community detection. Brand new information has been brought to these fields by social networks. Researchers hope that more reasonable results could be achieved via mining social networks. In this way, people can get more help when they make decision. This thesis has done some research on construction of social networks recommender and community detection, and brings some algorithms accordingly.As to social networks recommender, this thesis proposes an algorithm framework of collaborative filtering based on trust relationship to make it work, which combines trustworthiness of user and traditional rating similarity organically. In this way, the recommender can produce sound recommendation for users. We believe that modern recommendation system should take account of the role playing by social factors, and trust relationship between users is definitely one of the most important factors. Due to sparse trust network, we cluster it into classes, and assign a class-level trustworthiness value to each user. Experiment on Epinions dataset has proved that taking advantage of trust factor can improve recommendation quality evidently and alleviate the cold-start problem for recommender.Thanks to the advantage of computation complexity, label propagation algorithm has showed significant potential in solving community detection problem of large scalable network. Inspired by the idea of label propagation, this thesis proposes a novel label propagation algorithm to handle the same problem in social networks. Firstly, we presume that each node in network should have a different influence and introduce a formula to calculate their influence. And then, we adopt a hierarchical propagation fashion to iterate the propagation course, which make sure that large influence node propagates its label first. This fashion integrates the synchronous updating strategy with the asynchronous one, which brings algorithm to convergence earlier and also a stable community partition. Experiments on several datasets have indicated that the proposed algorithm can divide social networks into separate and overlapping communities, and assure the dependency of small communities. Our algorithm effectively solves the unstable partition problem of previous label propagation type methods. Comparison between our result and the COPRA algorithm’s has prove the effectiveness of the proposed algorithm.