iBridge: Inferring bridge links that diffuse information across communities

摘要

While the accuracy of link prediction has been improved continuously, the utility of the inferred new links is rarely concerned especially when it comes to information diffusion. This paper defines the utility of links based on average shortest distance and more importantly defines a special type of links named bridge links based on community structure (overlapping or not) of the network. In sociology, bridge links are usually regarded as weak ties and play a more crucial role in information diffusion. Considering that the accuracy of previous link prediction methods is high in predicting strong ties but not much high in predicting weak ties, we propose a new link prediction method named iBridge, which aims to infer new bridge links using biased structural metrics in a PU (positive and unlabeled) learning framework. The experimental results in 3 real online social networks show that iBridge outperforms several comparative link prediction methods (based on supervised learning or PU learning) in inferring the bridge links and meantime, the overall performance of inferring bridge links and non-bridge links is not compromised, thus verifying its robustness in inferring all new links.