Structure and evolution of missed collaborations in large networks

We study the nature of missed collaboration opportunities in evolving collaboration networks. We define a k-way missed collaboration as one in which every (k-1)-subset of the k persons has collaborated but the set of k has not. Representing a collaboration network as a simplicial complex, we model a missed collaboration as a Minimal Non Face (MNF). Focusing on 2-dimensional and 3-dimensional MNFs, equivalent to 3-way and 4-way missed collaborations respectively, we analyze the DBLP publication network and the IMDB movie network. Our key findings are as follows. A large number of missed collaborations arise, but only a few persist for long. Specifically, the persistence time appears to be exponentially distributed for both 2-MNFs and 3-MNFs. Nodes with higher degree centrality are more likely to be part of 2-MNFs but little correlation was found with 3-MNFs. Considering the network of missed collaborations, the number of components as of year 2013 appears to be power law distributed across MNF types and data sets, but its evolution shows a divergence between DBLP and IMDB. Our results can help in developing random generative models of collaboration networks, cue researchers in on potential fruitful collaborations, and predict new collaborations.