Small network completion using frequent subnetworks

Abstract

Prediction of missing or potential links and edges is currently the central theme in network analysis. Most of the work is focused on large unlabelled networks, with techniques based on global network models and, on a local level, on using patterns of temporal evolution. We define a problem of small network completion, which deals with sets of small networks, possibly with no recorded temporal dynamics. This problem requires a different set of methods and evaluation procedures. We present a method named Hyspan that extracts frequent patterns from small networks and uses them to predict missing vertices and edges in new networks. It ranks the predicted vertices and edges according to their likelihood estimated from the number and support of the patterns that suggest a particular missing part. Empirical evaluation on real and synthetic data sets shows that the method performs reasonably well. The quality of results depends upon the number and size of the used patterns; a larger number of patterns yields better results but requires longer – although still acceptable – running times.