Network Adjacency Matrix Blocked-compressive Sensing: A Novel Algorithm for Link Prediction

Received: 8 December 2018 Accepted: 3 February 2019 Link prediction for complex networks is a research hotspot. The main purpose is to predict the unknown edge according to the structure of the existing network. However, the edges in realworld networks are often sparsely distributed, and the number of unobserved edges is usually far greater than that of observed ones. Considering the weak performance of traditional link prediction algorithms under the above situation, this paper puts forward a novel link prediction algorithm called network adjacency matrix blocked-compressive sensing (BCS). Firstly, the diagonal blocks were subjected to sparse transformation with the network adjacency matrix; Next, the measurement matrix was rearranged into a new measurement matrix using the sorting operator; Finally, the subspace pursuit (SP) algorithm was introduced to solve the proposed algorithm. Experiments on ten real networks show that the proposed method achieved higher accuracy and consumed less time than the baseline methods.