Abstract: Link prediction aims at estimating the likelihood of the existence of links between nodes. Thepredicting of existent yet unknown links is similar to the data mining process, while the predicting of future linksrelates to the network evolution. The traditional methods are based on Markov Chains and machine learning whichusually involve the node attributes information. Although these methods can give good prediction, the highcomputational complexity limits their applications in large-scale systems. The approaches based on maximumlikelihood approximation also suffer this shortcoming. Another group of methods is based on the node similaritythat is defined solely based on the network structure. Extensive experiments on many real networks show that thesimilarity-based methods can give good prediction while with lower computational complexity comparing with theabove two kinds of methods. This article introduces and compares many representative link prediction methods,and outlines some important open problems, which may be valuable for related research domains.