Node-Pair Feature Extraction for Link Prediction

In social networks, one of the most essential problems is predicting existence or formation of a link between nodes. Traditional structure based link predicting algorithms leverage node properties such as degree and centrality and relation between nodes such as common neighbors and paths. Most of these algorithms rely on visibility of the entire or significant portion of the network structure, node centrality and shortest distance between nodes often require global knowledge. This work uses a back propagation neural network to predict existence or emergence of a link between pairs of nodes using node pair properties such as reciprocity, transitivity and shared neighbors. A limited network visibility by individual nodes is assumed, hence the size of the node pair feature vector varies with the given visibility range. This approach is tested on a large social object centered trust network where visibility is limited to two hops, 828 accurate predictions out of 1000 pair of nodes is achieved.