Small network completion using frequent subnetworks

Article type: Research Article

Authors: Polajnar, Matija | Demšar, Janez^{; *}

Affiliations: Faculty of Computer and Information Science, University of Ljubljana, Tržaška, Ljubljana, Slovenia

Correspondence: [*] Corresponding author: Janez Demšar, Faculty of Computer and Information Science, University of Ljubljana, Tržaška 25, SI-1000 Ljubljana, Slovenia. Tel.: +386 1 4768 813; E-mail: janez.demsar@fri.uni-lj.si.

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.

Keywords: Network analysis, prediction, frequent patterns

DOI: 10.3233/IDA-140698

Journal: Intelligent Data Analysis, vol. 19, no. 1, pp. 89-108, 2015