In the traditional link prediction problem, a snapshot of a so- cial network is used as a starting point to predict, by means of graph-theoretic measures, the links that are likely to ap- pear in the future. In this paper, we introduce cold start link prediction as the problem of predicting the structure of a social network when the network itself is totally missing while some other information regarding the nodes is avail- able. We propose a two-phase method based on the bootstrap probabilistic graph. The first phase generates an implicit so- cial network under the form of a probabilistic graph. The second phase applies probabilistic graph-based measures to produce the final prediction. We assess our method empiri- cally over a large data collection obtained from Flickr, using interest groups as the initial information. The experiments confirm the effectiveness of our approach.