Shortest path based potential common friend recommendation in social networks

Friend recommendation is a very popular application in online social network(OSN) services to help users make new friends and expand their social circle. Much of the existing research is based on either topological structure of OSN or user profiles to recommend new friends, while research based on both topological structure and user profiles to recommend potentially common friends between two undirectly connected users is still lacking. Recommending potentially common friends is useful in practical applications such as finding potential partners between two business groups in commercial social network in order to expand their business range or to reach potential customers, finding common bus stops between two specified bus stops on traffic network etc. In this paper we propose a novel shortest path based common friends recommendation approach in OSN to find and recommend potential common friends between two users. Our approach consists of the improved Floyd-Warshall algorithm and the Extended Longest Common Subsequence(ELCS) algorithm on both the topological structures of OSN and the partial profiles of users. The experiment results show that our approach can help users find the potential common friends efficiently and effectively.