  Link prediction can be used to extract missing information, identify spurious
interactions as well as forecast network evolution. Network embedding is a
methodology to assign coordinates to nodes in a low dimensional vector space.
By embedding nodes into vectors, the link prediction problem can be converted
into a similarity comparison task. Nodes with similar embedding vectors are
more likely to be connected. Classic network embedding algorithms are
random-walk-based. They sample trajectory paths via random walks and generate
node pairs from the trajectory paths. The node pair set is further used as the
input for a Skip-Gram model, a representative language model that embeds nodes
(which are regarded as words) into vectors. In the present study, we propose to
replace random walk processes by a spreading process, namely the
susceptible-infected (SI) model, to sample paths. Specifically, we propose two
SI-spreading-based algorithms, SINE and TSINE, to embed static and temporal
networks, respectively. The performance of our algorithms is evaluated by the
missing link prediction task in comparison with state-of-the-art static and
temporal network embedding algorithms. Results show that SINE and TSINE
outperform the baselines across all six empirical datasets. We further find
that the performance of SINE is mostly better than TSINE, suggesting that
temporal information does not necessarily improve the embedding for missing
link prediction. Moreover, we study the effect of the sampling size, quantified
as the total length of the trajectory paths, on the performance of the
embedding algorithms. The better performance of SINE and TSINE requires a
smaller sampling size in comparison with the baseline algorithms. Hence,
SI-spreading-based embedding tends to be more applicable to large-scale
networks.
