A generation probability based percolation network alignment method

With the rapid growth of Internet industry, online social networks have become an indivisible part of our lives. To enjoy different kinds of services, people prefer to take part in multiple online social networks rather than only one. Therefore, identifying the same user across networks, formally named as social network alignment, has become a hot research topic. In this paper, we use social network structure to solve this problem. Firstly, inspired by the aligned network model (a mathematical model to formalize the real-world aligned networks), we present a novel assumption for network alignment. We suppose that the real-world aligned networks can be seen as generated from many different underlying social networks, depending on the matching between users, and the correctly aligned networks ought to own the maximum generation probability. Secondly, a Generation probability based Percolation Network Alignment method (GPNA) is presented. In GPNA, only the candidates, which can increase the generation probability, are regarded as the matched users. At last, a series of experiments are conducted to demonstrate the good performance of GPNA on both synthetic networks and real-world networks.