Friend Recommendation in Online Social Networks: Perspective of Social Influence Maximization

In online social networks, people may want to make new friends to maximize their social influences. For example, business page owners on Facebook want to influence as many people as possible for commercial advantages. Hence, we study a friend recommendation strategy with the perspective of social influence maximization. For the system provider (e.g., Facebook), the objective is to recommend a fixed number of new friends to a given user, such that the given user can maximize his/her social influence through making new friends. Our problem is proved to be NP-hard. A greedy friend recommendation algorithm with an approximation ratio of 1 - 1/∈ is proposed, according to the submodular property. It involves a sub-problem of computing the influence spread. A novel method, which considers the multipath effect, is proposed to compute the influence spread. Experiments demonstrate the efficiency and effectiveness of our algorithms.