Identification of user influence in social networks

Abstract

The ever increasing growth of social networks has given users the power to share content on a scale that was unimaginable a few years ago. Depending on the social influence of a user, shared this project proposes to come up with an algorithm that could parse the data in a social network and rank each individual user on how influential they are. Identification of influential users may be helpful to social network users that want to promote a message on the network. The aim is to find some similarity between the hyperlink structure found on the web and the structure found on social networks, such as the interconnectivity between users and other social aspects found in common social media applications, and then apply the same algorithm that search engines have been using to rank each individual page (PageRank). This can be done by representing each user as a node similar to how each webpage is a node and each friend connection represents a link from one user to another similar to hyperlinks on the World Wide Web. This will then be further enhanced by using the comments and likes data from a social network where each user would enhance his rank with the amount of comments and likes a user would get back. This would result in three individual PageRank vectors (friends connection, comments connections, likes connection), which would be later be processed to give a single PageRank which should give us an accurate (although subjective) result. Due to the huge structure of social networks, we will be building the main system to work with GPU computing using CUDA and another version working on the CPU to be used as a control. This can be done as the PageRank algorithm is an algorithm that can be easily be parallelised due the algorithms nature of repetitions. The differences that needed to be done to make the system work on a single instruction multiple data architecture will be further elaborated in this dissertation. The structure and statistical properties of social networks shall be elaborated, and examples as well as evaluation results will be presented for all the different implementations that where tried and tested. The implementation resulted in a rank vector which gave a percentage to each user, which represented how influential the user is in the web graph. When compared to the dataset given, and considering the variables that are used in the PageRank algorithm the resulting vector was quite promising. The correctness of the vector could not be formally proven due to the subjective nature of the topic (social influence), but using the assumption that social influence is related to how connected and how active the user is then results should be valid. Furthermore using the CUDA implementation some impressive speed ups where gained, which were over 800% of the single threaded implementation.