Social account linking via weighted bipartite graph matching

摘要

Along with the increasing popularity of online social network (OSN), it is common that the same user holds many accounts among different OSNs (eg, Facebook, Twitter, WeChat, QQ). In this scenario, an interesting and challenging problem arises: how to link accounts among OSNs belonged to a natural person, which is also known as a graph matching problem. The solution helps understand user behaviors and offer better services. To solve the account linking problem, various techniques for OSNs have been proposed. However, most existing methods assume specific OSN features impractical in general OSNs and unscalable to large-scale OSNs. To address these shortcomings, in this paper, we remodel the account linking problem into maximum matching on weighted bipartite graphs and utilize the Kuhn-Munkres algorithm to solve it. In our solution, we capture user profile, user online time distribution, and user interest as features to describe user accounts and measure account similarity, which is used as weight of edge in bipartite graphs. Then, the maximum matching on weighted bipartite graphs is solved with the Kuhn-Munkres algorithm. The experiments conducted on the real datasets show that our solution outperforms the baseline methods with 11%, 17%, and 29% on average in precision, recall, and F1 score, respectively.