# Link Prediction Accuracy on Real-World Networks Under Non-Uniform Missing
Edge Patterns

Xie He, Amir Ghasemian, Eun Lee, Alice Schwarze,
Aaron Clauset, and Peter J. Mucha Xie He, Alice Schwarze, and Peter J. Mucha
are with the Department of Mathematics, Dartmouth College, Hanover, NH, 03755,
USA (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>peter.j.mucha@dartmouth.edu).Amir Ghasemian is with the Human Nature Lab, Yale
University, CT, 06520, and the Computational Social Science Lab at the
University of Pennsylvania, PA, 19104, USA.Eun Lee is with the Department of
Scientific Computing at Pukyong National University, Busan, Korea.Aaron
Clauset is with the Department of Computer Science and the BioFrontiers
Institute at the University of Colorado, Boulder, CO 80309, and the Santa Fe
Institute, Santa Fe, NM 87501.

###### Abstract

Real-world network datasets are typically obtained in ways that fail to
capture all links, and there are many different non-uniform ways in which real
data might be missing. Nevertheless, uniform missing data is a common
assumption made when no additional information is available about the
underlying “missingness function.” To investigate the impact of different
missingness patterns on link prediction accuracy, we employ 9 link prediction
algorithms from 4 different families to analyze 20 different missingness
functions categorized into 5 groups. By studying 250 real-world network
datasets, we illustrate that different prediction algorithms exhibit
significant differences in accuracy contingent upon both the dataset domain
and the nature of the missingness pattern. Our study thereby provides guidance
for selecting appropriate prediction algorithms when encountering diverse
patterns of missing data across various domains, emphasizing the importance of
considering the specific characteristics of the dataset for effective link
prediction.

##  1 Introduction

Link prediction is often used to speed up network data collection and impute
connections missed by data gathering. As such, link prediction is a common
procedure of network analysis across different disciplines, including the
study of social [34], biological [46], information [6], and epidemic [48]
networks. Over the years, various methods have been developed for link
prediction, such as local similarity indices [35, 56], network embedding [10,
32], matrix completion [25, 11], ensemble learning[15], and others [28, 37].

It is common for researchers to assume uniform missingness patterns [55] when
no information is available about the missingness patterns. For real-world
networks, however, missingness patterns are more likely to be non-uniform
either due to the nature of the underlying system or the sampling process used
to gather the data [38]. In cases where we have domain knowledge about the
nature of the missingness (e.g., when we know the sampling method used in the
data collection process), we expect to be able to achieve better link
prediction performance by selecting a suitable link prediction method that
works well with the missingness pattern in the dataset. For example, missing
data in social network analysis might result from survey non-response among a
closely connected group of individuals, rather than being randomly distributed
[23] or through egocentric sampling [33]. Moreover, missing friendship
relationships often occur among outliers within a group who are not closely
connected to the rest of the friends, unlike other nodes [19]. In protein-
protein interaction networks, the absence of a few proteins can lead to
missing edges related to all of them, thereby providing no information about
the relevant nodes [24]. Therefore, assuming uniform random missingness is not
always appropriate when evaluating link prediction algorithms for real-world
use.

Various efforts have been made to address the issue of non-uniform missingness
patterns in link prediction. A recent study proposed a computationally
efficient link prediction algorithm for egocentrically sampled networks [33].
However, systematic comparisons between missingness patterns and their effects
on link prediction algorithms are lacking. The majority of empirical
evaluations are conducted on relatively small numbers of networks, resulting
in limited knowledge about how various missingness patterns affect link
prediction accuracy on networks in different domains. This situation raises
questions about whether a selected prediction method is appropriate for a
missingness pattern and whether any methods consistently achieve good results
across different missingness patterns.

To address these questions, we conducted a study using 250 structurally
diverse real-world network datasets from ICON [8]. These networks originate
from $6$ different disciplines: biological ($47\%$), economic ($4\%$),
informational ($5\%$), social ($30\%$), technological ($10\%$), and
transportation ($4\%$). To simulate a diverse range of missing edge patterns
across various real-world scenarios, we applied 20 distinct missingness
functions grouped into 5 different categories: Node-Based, Edge-Based, DFS
(Depth-First Search), Neighbor-Based, and Node-Jump-Based methods. We then
assessed the effectiveness of 9 link prediction algorithms, encompassing 4
different families: local similarity measures, matrix factorization, embedding
methods, and ensemble learning.

Our findings emphasize the importance of considering specific dataset domains
and associated missing edge patterns (how the data was sampled) when selecting
suitable prediction algorithms. The impact of missingness patterns on
different link prediction algorithm families is significant, with no single
family consistently outperforming others. As such, a one-size-fits-all
approach may not capture the intricacies of real-world network data. Notably,
however, while there is no universally optimal link prediction method for all
missingness patterns, ensemble learning achieves the best results in over
$40\%$ of our cases studied. Our results shed new light on the predictability
of missing links under a wide variety of practical circumstances. We conclude
by discussing the limitations of our study and identifying opportunities for
further improvement in these results.

##  2 Methods

###  2.1 General Pipeline

To set up our experimental pipeline, we consider a given simple graph
$G=(V,E)$ with set $V$ of $n$ nodes and set $E$ of $m$ edges. For each of the
20 missingness functions considered, we use them to sample a subset of edges
$E^{\prime}\subset E$. Our task is to predict, using the sampled edges
$E^{\prime}$, which pairs of nodes not observed to be connected $X=V\times
V-E^{\prime}$ are actually missing links $Y=E-E^{\prime}$. We define each link
prediction algorithm as a score function over node pairs $i,j\in X$, where a
higher score indicates the algorithm asserts a higher likelihood of the node
pair being a true missing link [34].

All of the link prediction algorithms discussed in this work are supervised
methods, requiring separate training, validation, and testing sets. We divide
$E^{\prime}$ into training set $E_{\rm tr}$ and validation set $E_{\rm val}$,
while using $Y$ for the testing set. A major challenge in link prediction
using supervised methods is the lack of negative examples (true non-links)
when sampling to obtain $E^{\prime}$. Following the approach of Ghasemian et
al. [14], we consider all non-edges in $G$, which we notate $\tilde{E}=V\times
V-E$, as true negative examples. We sample from $\tilde{E}$ using the same
sampling function as used for $E^{\prime}$ to obtain the sampled negative node
pairs $\tilde{E}^{\prime}$. Similar to $E^{\prime}$, we separate
$\tilde{E}^{\prime}$ into training set $\tilde{E}_{\rm tr}$ and validation set
$\tilde{E}_{\rm val}$, and use $\tilde{Y}=\tilde{E}-\tilde{E}^{\prime}$ for
testing.

Due to the large number of node pairs in many real-world networks, after
selecting $E^{\prime}$ and $\tilde{E}^{\prime}$ we perform additional
resampling to ensure balanced classes (edge presence/absence) during training
and testing [13]. Specifically, we sample 10,000 edges uniformly at random
with replacement to form the positive class, and an equal number of non-edges
to form the negative class, of our train and test set. (All considered
networks have an edge density less than 0.5.)

The primary measure we use for evaluating link prediction performance is the
area under the receiver operating characteristic curve (AUC), a standard
measure in this field [35]. AUC scores provide a context-agnostic measure of
method robustness, capable of distinguishing between a missing link $i,j\in Y$
(a true positive) and a non-edge $X-Y$ (a true negative) [7], while allowing
for easy comparison with existing link prediction literature. Although other
accuracy measures can offer insights into a predictor’s performance in
specific scenarios (e.g., precision and recall at certain thresholds), we
leave such investigation for future work. Unless otherwise stated, the
reported AUC scores in our results are averaged over 25 runs, from 5
randomized repeats of 5-fold cross-validation with the sampled training,
validation, and testing sets constituting 64%, 16%, and 20% of the original
network data, respectively (and then subject to the resampling described in
the previous paragraph).

###  2.2 Missingness Functions

We apply 20 different sampling methods from Little Ball of Fur [43], a Python
library for network sampling techniques that utilizes a single streamlined
framework of sampling functions to test different missingness patterns. These
20 different methods are grouped below into five different categories: (i)
Node-Based, (ii) Edge-Based, (iii) Depth First Search (DFS), (iv) Neighbor-
Based, and (v) Node-Jump-Based missingness patterns.

The selection of the five distinct categories is grounded in the
characteristics of the respective missingness patterns. Specifically, Edge-
Based missingness encompasses traditional uniform sampling methods and other
techniques that primarily focus on edges, representing common ideas found in
the current literature regarding edge missingness. In contrast, Node-Based
missingness directs attention toward individual node properties, such as
degree centrality and PageRank. This type of missingness could be relevant to
real-world scenarios where the focus is on individuals with either greater or
lesser influence. DFS is singled out due to its distinctive nature in
exploring neighborhoods, making it a suitable mimic for scenarios where data
is missing in a more linear pattern, such as in observation of criminal
activities. Neighbor-Based missingness patterns prioritize exploration based
on the neighborhood of the initial seed node, offering an idealized simulation
for scenarios like sociological surveys and disease contact tracing. Node-
Jump-Based missingness introduces a unique element by allowing jumps from one
node to another, potentially resulting in an unconnected graph in certain
instances. These methods could be applied in cases where random encounters
have led to a more disconnected missingness. These carefully defined
categories aim to capture diverse aspects of missing data patterns, thereby
enhancing the understanding of algorithmic performance across different
scenarios.

####  2.2.1 Edge-Based Missingness Patterns

The Random Edge Sampler from Krishnamurthy et al. [26] samples edges uniformly
at random. (We emphasize again that this method is the most commonly used
method in the literature for assessing link prediction methods.) The Random
Node-Edge Sampler from Krishnamurthy et al. [26] first samples nodes uniformly
at random; then for each sampled node, one of its edges is sampled (again
uniformly). The Hybrid Node-Edge Sampler from Krishnamurthy et al. [26]
combines and alternates between the above two methods, sampling some portion
of the edges uniformly at random and the rest sampled from the edges connected
to nodes that are sampled uniformly at random. The Random Edge Sampler with
Induction from Ahmed et al. [4] randomly samples edges with a fixed
probability (using the default $0.5$ here) and then edges between nodes which
are already in the sample are retained with an induction step, for which we
follow algorithm 1 in [4] and sample uniformly at random from all of the edges
between these nodes until we have the desired number of edges we are
targeting.

####  2.2.2 Node-Based Missingness Patterns

For each of the following methods, only the links between nodes that are both
sampled will be included. That is, the sampled edges $E_{\rm s}$ are those
that appear in the induced subgraph of the set of sampled nodes. The Degree
Based Node Sampler from Adamic et al. [1] samples nodes with probability
proportional to their degrees. The Random Node Sampler from Stumpf et al. [45]
samples nodes uniformly at random. Similarly, the PageRank Based Node Sampler
from Leskovec et al. [30] samples proportional to the PageRank scores of
nodes.

####  2.2.3 DFS Missingness Pattern

The Randomized Depth First Search (DFS) Sampler [12] performs node sampling
using depth-first search: starting from a randomly chosen node, neighbors are
added to the last-in-first-out queue after shuffling them randomly.

####  2.2.4 Neighbor-Based Missing Patterns

The following sampling methods include all nodes explored by a walker and all
the corresponding edges in the induced subgraph between these sampled nodes,
resulting in connected samples. The Diffusion Sampler [44] applies a simple
diffusion process on the network to sample an induced subgraph incrementally.
The Forest Fire Sampler [31] is a stochastic snowball sampling method where
the expansion is proportional to the burning probability, with a default
probability of $0.4$. The Non-Backtracking Random Walk Sampler [29] samples
nodes with a random walk in which the walker cannot backtrack. The Random Walk
Sampler [16] samples nodes with a simple random walker. The Random Walk With
Restart Sampler [30] uses a discrete random walk on nodes, with occasional
teleportation back to the starting node with a fixed probability. The
Metropolis Hastings Random Walk Sampler [22] uses a random walker with
probabilistic acceptance condition for adding new nodes to the sampled set,
which can be parameterized by the rejection constraint exponent. The
Circulated Neighbors Random Walk Sampler [57] simulates a random walker, and
after sampling all nodes in the vicinity of a node, the vertices are randomly
reshuffled to allow the walker to escape closely-knit communities. The
Randomized Breadth First Search (BFS) Sampler [12] performs node sampling
using breadth-first search: starting from a randomly chosen node, neighbors
are added to the queue after shuffling them randomly.

####  2.2.5 Node-Jump-Based Missing Patterns

Meanwhile, the following methods potentially result in a disconnected sample.
The Random Walk With Jump Sampler [42] is done through random walks with
occasional teleporting jumps. The Random Node-Neighbor Sampler [30] samples
nodes uniformly at random and then includes all neighboring nodes and the
edges connecting them as the induced subgraph. The Shortest Path Sampler [41]
samples pairs of nodes and chooses a random shortest path between them,
including the vertices and edges along the selected shortest path in the
induced subgraph.

Additionally, the Loop-Erased Random Walk Sampler [51] samples a fixed number
of nodes and then includes only edges that connect previously unconnected
nodes to the sampled set, resulting in an undirected tree.

###  2.3 Link Prediction Methods

We employ 9 different link prediction methods from various disciplines. These
link predictions are drawn from 4 popular families of algorithms: local
similarity indices [35, 56], network embedding [10, 32], matrix completion
[25, 11], and ensemble learning[15].

####  2.3.1 Network Embedding

The Node2Vec Dot Product approach utilizes a skip-gram-based method to learn
node embeddings from random walks in the graph. The dot product between the
embeddings of two nodes is used to represent the corresponding edge, which is
then used for training [17]. The Node2Vec Edge Embedding method also learns
node embeddings using skip-gram-based techniques; however, it additionally
incorporates bootstrapped edge embeddings and logistic regression to represent
the edges, enhancing the training process [17]. The Spectral Clustering
approach uses spectral embeddings to create node representations from an
adjacency matrix [27] [36] and then makes predictions with the embedded
feature vector.

####  2.3.2 Local Similarity Indices

One such method relies on the Adamic-Adar index, a local structured measure,
for link prediction [18]. Another approach utilizes Preferential Attachment,
another local structured measure, for link prediction [18]. The Jaccard
Coefficient can be similarly employed for link prediction [18].

####  2.3.3 Ensemble Learning

The Top-Stacking method combines topological features of node pairs and trains
a random forest model for link prediction [14]. We note that our Top-Stacking
results here, on a subset of the networks considered in the original paper,
are slightly different because we have modified the percentages in the
training, validation, and testing sets to be consistent with the other
benchmarking methods used here.

####  2.3.4 Matrix Completion

The Modularity method for link prediction starts from Newman and Girvan’s
modularity maximization for community detection [39]. We then use the obtained
communities to measure the empirical densities between and within communities
and then predict the most likely missing links from these densities, similar
to [49, 14]. The MDL-DCSBM method starts by creating a minimum description
length, degree-corrected stochastic block model [40]. As with the Modularity
method, we then use the obtained block structure to predict the most likely
missing links in the manner used in [52, 14].

##  3 Results

###  3.1 Data

We use publicly available data listed on [9] and provided in clean form in the
Github repository for Ghasemian et al. [14]. To reduce the computational cost
of our simulation study, we consider a subset of the data that includes 119
biological networks, 9 economic networks, 12 informational networks, 74 social
networks, 26 technological networks, and 10 transportation networks. This
subset of 250 networks has a mean of $492$ nodes and $1110$ edges, with a mean
node degree of $5.28$. This diversity of network data, encompassing a wide
array of domains and collected through various methodologies, provides a
robust foundation for evaluating sampling methods and link prediction
algorithms. Assessing performance across this extensive dataset spectrum
affords us an opportunity to investigate how sampling and link prediction
relate to one another in different domains, compared to relying solely on a
limited set of networks or a single domain.

###  3.2 Domain and Algorithm Variability

To comprehensively assess the performance and variability of various link
prediction algorithms across missingness patterns and diverse domains, we
present detailed insights about the average AUC scores obtained through 5-fold
cross-validation over 5 runs in tables 1, 2, 3, 4, 5 and 6. Our results
include 120 distinct combinations of domains (6) and sampling methods (20), as
delineated in tables 1, 2, 3, 4, 5 and 6.

Among these combinations, it is evident that the Top-Stacking method
demonstrates the highest performance in 51 instances, followed by Adamic-Adar
in 29 instances. Modularity and MDL-DCSBM both achieve top performance in 14
combinations, Spectral Clustering in 11, and Preferential Attachment in 1.
This comprehensive overview sheds light on each algorithm’s varying strengths
across the many scenarios considered.

An immediate observation that can be drawn from these tables is that, within a
specific dataset domain, a particular link prediction method tends to
outperform others. Taking biological networks as an illustrative example,
which constitute the majority of the networks under consideration (119 out of
250), Spectral Clustering and Top-Stacking emerge as the primary methods
yielding the best AUC scores. MDL-DCSBM surpasses them only in isolated cases.
Similarly, MDL-DCSBM exhibits superior performance in informational networks,
and Top-Stacking and Spectral Clustering closely follow, with Top-Stacking
often outperforming Spectral Clustering. In the case of social networks, all
methods demonstrate commendable performance, with Adamic-Adar slightly
dominating. In transportation networks, Modularity emerges as the leading
algorithm, while Top-Stacking consistently secures the second-best position
and occasionally outperforms the leading method. In technological networks,
Top-Stacking consistently outperforms all other methods. Across these five
domains, Top-Stacking consistently proves to be either the best-performing
method or a close second to the leading method for each case.

Interestingly, in economic networks, Adamic-Adar stands out as the best
performer. Spectral Clustering and Top-Stacking achieve the best results in
some instances, but Preferential Attachment consistently secures the second
place, demonstrating performance close to Adamic-Adar. It is noteworthy that
both Adamic-Adar and Preferential Attachment, despite being simple topological
predictors, show strong predictive power in economic networks, even though
Preferential Attachment does not perform well in other domains, including
social networks. This suggests its specific efficacy in economic networks.

For social networks, most of the link prediction algorithms are able to
achieve highly accurate results, regardless of the missingness patterns, with
a relatively small standard deviation. The worst accuracies on social networks
in table 4 are obtained with Preferential Attachment, while all other methods
achieve at least an AUC score above $0.9$ across different missingness
patterns.

Figure 1: PCA scores (PC1 horizontal, PC2 vertical) to show distinct network
datasets from different domains. The full set of AUC scores (averaged over 5
randomized repeats of 5-fold cross-validation) across the different prediction
algorithms and sampling methods are taken as the feature vectors of each type
of network, marked with different colors and symbols to denote dataset domain
as indicated in the legend.

To explore this variation further, we perform Principal Component Analysis
(PCA) using the AUC scores across prediction algorithms and sampling functions
as features to characterize each network. That is, for each sampling method
and prediction algorithm, we use the AUC scores obtained for each individual
network as feature vectors for PCA. The results in fig. 1 are intuitively
consistent with the nice properties of social networks that positively affect
the ability to accurately predict missing edges, such as high clustering
coefficients and heavy-tailed degree distributions [5, 47]. These results not
only confirm the claim in Ghasemian et al. [14] that most link prediction
methods can achieve high link prediction performance on social networks, but
also show that the statement is true even under various missingness patterns.
We thus stress that the comparison of different link prediction algorithms
should focus on all types of real-world networks, rather than solely on social
networks.

###  3.3 Missingness Pattern Influences

As highlighted in the AUC tables, the aggregated values exhibit a smoother
trend compared to the individual dataset performances. Given the
impracticality of showcasing over 250 datasets individually, our focus shifts
towards capturing the general patterns across different groups of datasets
under various missingness patterns. To provide a more comprehensive
visualization, we displayed the performance for five different missingness
patterns (Figure 2). We have chosen the Degree-Based, Random Edge-Based, DFS
(noteworthy for standing out), Diffusion-Based, and Shortest Path-Based
methods as representatives from their respective categories, to better discern
and illustrate the differences and variance across various missingness
patterns. The complete array of boxplots for different methods is available in
the Appendix.

As shown in Figure 2, one observation that is consistent with our earlier
finding is the remarkable invariance for social networks under different
missingness patterns, in contrast to other dataset types. For instance, in
biological networks, the performance of Preferential Attachment experiences a
significant drop when transitioning from other types to DFS missingness. In
transportation networks, the variance of Top-Stacking surges when shifting
from random edge-based (uniform missingness) to degree-based missingness. For
transportation networks, Node2Vec Dot Product exhibits generally smaller
variance across other missingness types compared to Diffusion-Based
missingness. In economic networks, Adamic Adar’s variance increases for DFS,
while Node2Vec Edge Embedding’s variance decreases. For informational and
technological networks, the performance of all prediction methods remains
relatively consistent against different missingness patterns, albeit
exhibiting a slight dip in DFS missingness.

Even when aggregated over a boxplot, the variance differences are apparent,
underscoring the significant impact of missingness patterns in selecting
appropriate link prediction algorithms. This observation aligns with the
insights gleaned from tables 1, 2, 3, 4, 5 and 6. When facing uncertainty in
the missingness pattern, a prudent starting point could be the use of Top-
Stacking, given its consistent performance across different types of
missingness functions. Of course, such a decision should be informed by the
specific dataset domain under consideration. For instance, when using Top-
Stacking for transportation networks as a starting point, we should pay extra
attention to how the missingness pattern is for the dataset, as Node-Based
will result in a much smaller variance and slightly worse performance than the
other patterns. Another example here would be when applying Adamic-Adar for
economic networks, the variance for the DFS missingness pattern is much bigger
than the other patterns, and thus extra care must be taken here.

It’s worth noting that when employing DFS, regardless of the choice of link
prediction algorithms, we consistently observe slightly lower AUC scores in
comparison with alternative sampling techniques. To explore this further, we
generated PCA plots in Figure 5 of Appendix (details in the Appendix). The
results further emphasize DFS as an outlier, with DFS standing out in most of
the single-panel PCA plots. We hypothesize that this is due to inherent
structural features of DFS samples, determined by an initial node and
extending to a small portion of the nearby network [12]. But instead of
suggesting that users stop using DFS, we assert that these observations
actually make DFS samples more interesting to study. The missingness patterns
in real-world network data could very well be focused on the missing
information around one particular egocentric subgraph or along a particular
line of interactions, such as criminal and terrorist activities [50]. In
particular real-world cases, DFS may be much more suitable to mimic the
missingness pattern in the data, and would then be useful to study which link
prediction algorithms would be more stable and robust under such biased
samples of edges.

##  4 Conclusion

Our results, spanning 20 network sampling methods, 9 link prediction
algorithms, and 250 network data sets obtained from 6 different domains,
demonstrate that real-world networks exhibit diverse underlying patterns of
structural organization that lead to significant variations in the performance
of different link predictors under different network sampling settings.
Therefore, when one has a choice about how to sample a network, or knowledge
about how the network was sampled, the choice of link prediction method should
be tailored according to the expectations of performance in that sampling and
domain setting, with consideration for the extensive variation in missing
structure and in link prediction performances across different network types.

Our study establishes key principles for selecting link prediction algorithms
in scenarios where the missing edge pattern is pre-determined or known.
Specifically, for social and economic networks, we advocate for the use of
local similarity methods, such as Adamic-Adar, due to their simplicity,
reliability, and greater feature explainability. In the context of social
networks, nearly all the methods evaluated achieve a very good performance.
Importantly, this observation holds true across a range of missingness
patterns. This emphasizes the need for caution when comparing link prediction
algorithms, suggesting that such comparisons should extend beyond social
networks to include various network types. In the context of information and
transportation networks, matrix completion methods like MDL-DCSBM or
Modularity emerge as valuable choices, given their strong performance and
emphasis on network community structures. Top-Stacking stands out as an
exemplary choice for technological networks, showcasing robust performance. In
the case of intricate networks like biological networks, our observations
indicate that ensemble learning like Top-Stacking, and embedding methods like
Spectral Clustering generally outperform other methods.

However, it is very important to acknowledge that real-world data are
typically not obtained from an explicit sampling function, leading to an
unknown missingness pattern. While no single method universally excels across
all domains and missingness patterns, in scenarios where the missingness
pattern remains unknown, which is often the case in real-world applications,
Top-Stacking emerges as the most robust general predictor of the set
considered. It produces the best results for many combinations of networks and
missingness functions, and strong (but not the best) results in many other
cases. In cases where the network domain and missingness function class are
known, more specialized predictors will produce better results under certain
missingness patterns.

A notable limitation of the present study lies in the constraint of the
missingness functions utilized. The current work relies on sampling functions
available in the state-of-the-art package used here, and it is important to
acknowledge that these missingness functions serve as representations rather
than exact replicas of missingness patterns in real-world data. While we have
categorized them into different groups that aim to mimic genuine data loss
scenarios, it is crucial to recognize that these models are not perfect
replicas of actual patterns of missing data. Consequently, any assumptions or
conclusions made based on these representations should be approached with
caution.

A potentially promising avenue for future research would involve generalizing
our study to the effects of sampling on link prediction in multilayer networks
and temporal networks, given their increasing importance (see, e.g., [53, 21,
2, 3, 20] for various methods of link prediction in these settings). It might
be particularly important to explore the variability in sampling methods and
their impact on prediction accuracy as the amount of temporal information
increases. Additionally, it may be beneficial to establish theoretical
relationships between link predictability, different sampling settings, and
the influence of different network features on prediction outcomes.

(a) Edge-Based: Random Edge Missingness

(b) Node-Based: Degree Based Missingness

(c) DFS: Depth First Search Missingness

(d) Neighbor-Based: Diffusion Based Missingness

(e) Node-Jump-Based: Shortest Path Based Missingness

Figure 2: Boxplots for Different Families of Missingness Patterns Table 1:
Average 5 fold cross validated AUC scores over 5 runs for biological networks

Category Missingness Pattern (Sampler) Adamic-Adar Node2Vec Dot Product
Preferential Attachment Node2Vec Edge Embedding Jaccard Coefficient MDL-DCSBM
Modularity Spectral Clustering Top-Stacking Node-Based Random Node 0.729 0.641
0.75 0.684 0.729 0.803 0.684 0.812 0.798 Degree Based 0.732 0.648 0.744 0.683
0.733 0.796 0.696 0.786 0.82 PageRank Based 0.729 0.646 0.741 0.688 0.73 0.791
0.691 0.82 0.814 Edge-Based Random Edge 0.713 0.634 0.74 0.671 0.705 0.797
0.684 0.794 0.813 Random Node Edge 0.707 0.643 0.717 0.679 0.701 0.752 0.687
0.794 0.799 Hybrid Node Edge 0.703 0.642 0.721 0.673 0.703 0.801 0.687 0.813
0.816 Random Edge With Induction 0.716 0.632 0.75 0.68 0.717 0.804 0.697 0.812
0.835 DFS Depth First Search 0.651 0.64 0.632 0.654 0.656 0.756 0.692 0.814
0.807 Neighbor-Based Diffusion 0.731 0.645 0.753 0.687 0.728 0.796 0.689 0.81
0.833 Forest Fire 0.726 0.644 0.747 0.679 0.726 0.796 0.687 0.809 0.82
Nonbacktracking Random Walk 0.723 0.642 0.75 0.68 0.722 0.798 0.684 0.798
0.828 Random Walk 0.723 0.642 0.753 0.682 0.722 0.804 0.696 0.802 0.828 Random
Walk With Restart 0.723 0.648 0.753 0.683 0.726 0.801 0.693 0.755 0.815
Metropolis Hastings Random Walk 0.725 0.644 0.751 0.685 0.728 0.796 0.69 0.811
0.807 Circulated Neighbors Random Walk 0.726 0.64 0.756 0.678 0.725 0.797
0.686 0.792 0.807 Breadth First Search 0.704 0.692 0.75 0.704 0.697 0.799 0.68
0.803 0.802 Node-Jump-Based Loop Erased Random Walk 0.715 0.642 0.726 0.67
0.719 0.751 0.686 0.814 0.821 Random Walk With Jump 0.727 0.643 0.754 0.68
0.727 0.805 0.686 0.799 0.806 Random Node Neighbor 0.711 0.633 0.741 0.679
0.71 0.808 0.681 0.741 0.806 Shortest Path 0.725 0.651 0.751 0.695 0.726 0.793
0.679 0.813 0.799

Table 2: Average 5 fold cross validated AUC scores over 5 runs for economic
networks

Category Missingness Pattern (Sampler) Adamic-Adar Node2Vec Dot Product
Preferential Attachment Node2Vec Edge Embedding Jaccard Coefficient MDL-DCSBM
Modularity Spectral Clustering Top-Stacking Node-Based Random Node 0.808 0.614
0.805 0.715 0.773 0.766 0.618 0.81 0.775 Degree Based 0.811 0.634 0.8 0.709
0.775 0.742 0.634 0.756 0.752 PageRank Based 0.81 0.638 0.798 0.713 0.775 0.75
0.627 0.817 0.77 Edge-Based Random Edge 0.801 0.612 0.795 0.682 0.767 0.755
0.616 0.77 0.753 Random Node Edge 0.769 0.623 0.751 0.677 0.749 0.734 0.625
0.782 0.796 Hybrid Node Edge 0.771 0.62 0.762 0.685 0.747 0.767 0.619 0.81
0.82 Random Edge With Induction 0.827 0.616 0.824 0.705 0.788 0.764 0.63 0.809
0.795 DFS Depth First Search 0.645 0.588 0.614 0.606 0.639 0.707 0.618 0.809
0.769 Neighbor-Based Diffusion 0.811 0.627 0.807 0.699 0.776 0.741 0.62 0.808
0.787 Forest Fire 0.81 0.644 0.799 0.71 0.774 0.744 0.612 0.796 0.81
Nonbacktracking Random Walk 0.81 0.615 0.808 0.7 0.776 0.75 0.627 0.781 0.766
Random Walk 0.811 0.622 0.808 0.705 0.776 0.763 0.634 0.79 0.735 Random Walk
With Restart 0.811 0.617 0.808 0.712 0.776 0.763 0.627 0.731 0.78 Metropolis
Hastings Random Walk 0.81 0.605 0.807 0.706 0.775 0.745 0.637 0.808 0.8
Circulated Neighbors Random Walk 0.81 0.615 0.808 0.702 0.775 0.746 0.628
0.761 0.77 Breadth First Search 0.8 0.668 0.813 0.694 0.767 0.753 0.612 0.784
0.76 Node-Jump-Based Loop Erased Random Walk 0.768 0.628 0.761 0.692 0.742
0.724 0.627 0.808 0.821 Random Walk With Jump 0.81 0.635 0.798 0.71 0.775
0.766 0.625 0.786 0.753 Random Node Neighbor 0.81 0.623 0.803 0.707 0.775
0.769 0.611 0.73 0.788 Shortest Path 0.81 0.647 0.799 0.699 0.774 0.746 0.621
0.808 0.805

Table 3: Average 5 fold cross validated AUC scores over 5 runs for
informational networks

Category Missingness Pattern (Sampler) Adamic-Adar Node2Vec Dot Product
Preferential Attachment Node2Vec Edge Embedding Jaccard Coefficient MDL-DCSBM
Modularity Spectral Clustering Top-Stacking Node-Based Random Node 0.722 0.613
0.753 0.714 0.661 0̱.815 0.701 0.788 0.774 Degree Based 0.72 0.612 0.744 0.708
0.672 0.8 0.713 0.756 0.774 PageRank Based 0.72 0.603 0.742 0.704 0.671 0.799
0.709 0.796 0.769 Edge-Based Random Edge 0.715 0.621 0.737 0.701 0.674 0.807
0.706 0.763 0.739 Random Node Edge 0.703 0.609 0.717 0.688 0.652 0.749 0.705
0.766 0.774 Hybrid Node Edge 0.702 0.604 0.732 0.689 0.66 0.813 0.691 0.79
0.775 Random Edge With Induction 0.72 0.605 0.745 0.712 0.67 0.815 0.708 0.79
0.801 DFS Depth First Search 0.627 0.609 0.623 0.651 0.618 0.77 0.699 0.81
0.789 Neighbor-Based Diffusion 0.721 0.624 0.748 0.708 0.672 0.797 0.702 0.791
0.801 Forest Fire 0.721 0.62 0.745 0.707 0.673 0.801 0.696 0.789 0.77
Nonbacktracking Random Walk 0.719 0.609 0.746 0.701 0.656 0.805 0.695 0.771
0.791 Random Walk 0.719 0.609 0.745 0.705 0.655 0.814 0.705 0.771 0.78 Random
Walk With Restart 0.722 0.614 0.742 0.711 0.672 0.818 0.696 0.724 0.802
Metropolis Hastings Random Walk 0.723 0.618 0.743 0.707 0.674 0.803 0.687
0.797 0.744 Circulated Neighbors Random Walk 0.72 0.619 0.744 0.706 0.671
0.803 0.693 0.782 0.789 Breadth First Search 0.704 0.709 0.733 0.738 0.678
0.81 0.685 0.79 0.796 Node-Jump-Based Loop Erased Random Walk 0.702 0.622
0.724 0.692 0.648 0.763 0.687 0.791 0.755 Random Walk With Jump 0.719 0.621
0.749 0.71 0.671 0.819 0.691 0.789 0.793 Random Node Neighbor 0.717 0.607
0.741 0.705 0.669 0.821 0.682 0.724 0.783 Shortest Path 0.718 0.619 0.742 0.71
0.669 0.808 0.685 0.81 0.825

Table 4: Average 5 fold cross validated AUC scores over 5 runs for social
networks

Category Missingness Pattern (Sampler) Adamic-Adar Node2Vec Dot Product
Preferential Attachment Node2Vec Edge Embedding Jaccard Coefficient MDL-DCSBM
Modularity Spectral Clustering Top-Stacking Node-Based Random Node 0.961 0.908
0.746 0.95 0.955 0.915 0.9 0.923 0.9 Degree Based 0.962 0.906 0.75 0.953 0.957
0.911 0.903 0.906 0.928 PageRank Based 0.961 0.907 0.749 0.949 0.956 0.911
0.901 0.927 0.932 Edge-Based Random Edge 0.963 0.914 0.74 0.948 0.959 0.913
0.893 0.916 0.944 Random Node Edge 0.96 0.91 0.727 0.945 0.955 0.906 0.9 0.913
0.945 Hybrid Node Edge 0.961 0.91 0.732 0.945 0.954 0.914 0.903 0.923 0.934
Random Edge With Induction 0.961 0.913 0.757 0.953 0.957 0.914 0.905 0.922
0.954 DFS Depth First Search 0.869 0.896 0.667 0.929 0.867 0.905 0.903 0.925
0.96 Neighbor-Based Diffusion 0.96 0.906 0.751 0.951 0.954 0.908 0.901 0.923
0.958 Forest Fire 0.96 0.905 0.751 0.952 0.955 0.911 0.893 0.918 0.952
Nonbacktracking Random Walk 0.961 0.91 0.751 0.954 0.956 0.91 0.9 0.912 0.958
Random Walk 0.96 0.906 0.752 0.952 0.955 0.914 0.9 0.915 0.963 Random Walk
With Restart 0.96 0.905 0.75 0.948 0.955 0.912 0.898 0.897 0.96 Metropolis
Hastings Random Walk 0.96 0.909 0.75 0.951 0.955 0.906 0.893 0.923 0.961
Circulated Neighbors Random Walk 0.959 0.912 0.752 0.949 0.955 0.908 0.897
0.91 0.933 Breadth First Search 0.96 0.908 0.763 0.909 0.955 0.909 0.899 0.925
0.94 Node-Jump-Based Loop Erased Random Walk 0.958 0.909 0.718 0.943 0.954
0.902 0.896 0.924 0.97 Random Walk With Jump 0.962 0.905 0.749 0.949 0.956
0.911 0.899 0.917 0.959 Random Node Neighbor 0.961 0.906 0.746 0.952 0.956
0.916 0.893 0.897 0.958 Shortest Path 0.961 0.906 0.747 0.949 0.956 0.912
0.897 0.925 0.919

Table 5: Average 5 fold cross validated AUC scores over 5 runs for
technological networks

Category Missingness Pattern (Sampler) Adamic-Adar Node2Vec Dot Product
Preferential Attachment Node2Vec Edge Embedding Jaccard Coefficient MDL-DCSBM
Modularity Spectral Clustering Top-Stacking Node-Based Random Node 0.679 0.647
0.706 0.731 0.656 0.643 0.748 0.731 0.789 Degree Based 0.68 0.662 0.712 0.729
0.656 0.626 0.757 0.71 0.799 PageRank Based 0.683 0.643 0.705 0.733 0.659
0.631 0.753 0.736 0.773 Edge-Based Random Edge 0.688 0.647 0.697 0.721 0.664
0.632 0.751 0.719 0.797 Random Node Edge 0.67 0.639 0.7 0.711 0.649 0.643
0.746 0.72 0.803 Hybrid Node Edge 0.677 0.639 0.692 0.707 0.656 0.636 0.74
0.731 0.788 Random Edge With Induction 0.685 0.639 0.692 0.723 0.66 0.639
0.745 0.73 0.801 DFS Depth First Search 0.591 0.634 0.615 0.69 0.586 0.663
0.755 0.731 0.763 Neighbor-Based Diffusion 0.688 0.641 0.7 0.736 0.664 0.639
0.744 0.737 0.812 Forest Fire 0.684 0.649 0.701 0.73 0.66 0.621 0.746 0.738
0.774 Nonbacktracking Random Walk 0.68 0.646 0.691 0.724 0.656 0.645 0.739
0.735 0.801 Random Walk 0.683 0.632 0.703 0.725 0.659 0.655 0.744 0.732 0.825
Random Walk With Restart 0.684 0.657 0.701 0.724 0.66 0.646 0.738 0.705 0.777
Metropolis Hastings Random Walk 0.684 0.653 0.7 0.727 0.66 0.641 0.738 0.733
0.778 Circulated Neighbors Random Walk 0.68 0.66 0.71 0.732 0.656 0.647 0.731
0.714 0.781 Breadth First Search 0.681 0.698 0.759 0.711 0.665 0.657 0.746
0.721 0.774 Node-Jump-Based Loop Erased Random Walk 0.678 0.646 0.7 0.727
0.656 0.642 0.736 0.744 0.811 Random Walk With Jump 0.684 0.655 0.691 0.735
0.661 0.661 0.75 0.721 0.766 Random Node Neighbor 0.681 0.636 0.684 0.728
0.657 0.655 0.744 0.693 0.746 Shortest Path 0.683 0.64 0.698 0.726 0.659 0.637
0.743 0.731 0.809

Table 6: Average 5 fold cross validated AUC scores over 5 runs for
transportation networks

Category Missingness Pattern (Sampler) Adamic-Adar Node2Vec Dot Product
Preferential Attachment Node2Vec Edge Embedding Jaccard Coefficient MDL-DCSBM
Modularity Spectral Clustering Top-Stacking Node-Based Random Node 0.7 0.718
0.695 0.752 0.7 0.542 0.785 0.648 0.78 Degree Based 0.651 0.738 0.639 0.751
0.651 0.533 0.792 0.643 0.747 PageRank Based 0.683 0.727 0.617 0.741 0.683
0.538 0.785 0.644 0.761 Edge-Based Random Edge 0.642 0.701 0.624 0.728 0.642
0.548 0.785 0.644 0.758 Random Node Edge 0.644 0.684 0.63 0.72 0.644 0.602
0.774 0.645 0.751 Hybrid Node Edge 0.64 0.668 0.615 0.698 0.64 0.545 0.773
0.648 0.767 Random Edge With Induction 0.642 0.7 0.624 0.73 0.642 0.555 0.781
0.643 0.817 DFS Depth First Search 0.665 0.646 0.65 0.712 0.665 0.609 0.796
0.671 0.77 Neighbor-Based Diffusion 0.669 0.698 0.637 0.75 0.67 0.54 0.775
0.662 0.842 Forest Fire 0.674 0.68 0.631 0.761 0.674 0.551 0.782 0.714 0.81
Nonbacktracking Random Walk 0.676 0.702 0.637 0.766 0.676 0.556 0.762 0.723
0.805 Random Walk 0.668 0.692 0.637 0.751 0.668 0.564 0.793 0.697 0.685 Random
Walk With Restart 0.666 0.712 0.642 0.749 0.667 0.57 0.786 0.665 0.777
Metropolis Hastings Random Walk 0.655 0.683 0.638 0.73 0.656 0.563 0.783 0.683
0.79 Circulated Neighbors Random Walk 0.676 0.717 0.654 0.754 0.676 0.562
0.775 0.653 0.684 Breadth First Search 0.676 0.776 0.726 0.721 0.677 0.571
0.783 0.67 0.727 Node-Jump-Based Loop Erased Random Walk 0.669 0.718 0.64
0.715 0.669 0.62 0.794 0.722 0.751 Random Walk With Jump 0.655 0.72 0.641
0.748 0.656 0.569 0.781 0.675 0.729 Random Node Neighbor 0.641 0.67 0.62 0.722
0.641 0.556 0.796 0.642 0.773 Shortest Path 0.669 0.7 0.624 0.735 0.669 0.565
0.769 0.673 0.786

## Acknowledgments

We are grateful for the use of high performance computing clusters at
Dartmouth College (discovery7, doob). This work was supported in part by the
Army Research Office under MURI award W911NF-18-1-0244 (X.H. and P.J.M.), the
National Science Foundation under Grant No. 2030859 to the Computing Research
Association for the CIFellows Project (A.G.), and the National Research
Foundation of Korea (NRF) grant funded by the Korea government(MSIT) (No.
RS-2022-00165916) (E.L.). The content is solely the responsibility of the
authors and does not necessarily represent the official views of any agency
supporting this research.

## References

  * [1] Lada A Adamic, Rajan M Lukose, Amit R Puniyani, and Bernardo A Huberman.  Search in power-law networks.  Physical review E, 64(4):046135, 2001.
  * [2] Nahla Mohamed Ahmed, Ling Chen, Yulong Wang, Bin Li, Yun Li, and Wei Liu.  Sampling-based algorithm for link prediction in temporal networks.  Information Sciences, 374:1–14, 2016.
  * [3] Nesreen K Ahmed, Nick Duffield, and Ryan A Rossi.  Online sampling of temporal networks.  ACM Transactions on Knowledge Discovery from Data (TKDD), 15(4):1–27, 2021.
  * [4] Nesreen K Ahmed, Jennifer Neville, and Ramana Kompella.  Network sampling: From static to streaming graphs.  ACM Transactions on Knowledge Discovery from Data (TKDD), 8(2):1–56, 2013.
  * [5] Yong-Yeol Ahn, Seungyeop Han, Haewoon Kwak, Sue Moon, and Hawoong Jeong.  Analysis of topological characteristics of huge online social networking services.  In Proceedings of the 16th international conference on World Wide Web, pages 835–844, 2007.
  * [6] Xiaohuan Cao, Yuyan Zheng, Chuan Shi, Jingzhi Li, and Bin Wu.  Link prediction in schema-rich heterogeneous information network.  In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 449–460. Springer, 2016.
  * [7] Aaron Clauset, Cristopher Moore, and Mark EJ Newman.  Hierarchical structure and the prediction of missing links in networks.  Nature, 453(7191):98–101, 2008.
  * [8] Aaron Clauset, Ellen Tucker, and Matthias Sainz.  The colorado index of complex networks.  Retrieved July, 20(2018):22, 2016.
  * [9] Aaron Clauset, Ellen Tucker, and Matthias Sainz.  ”The Colorado Index of Complex Networks .”.  https://icon.colorado.edu/, 2016.
  * [10] Peng Cui, Xiao Wang, Jian Pei, and Wenwu Zhu.  A survey on network embedding.  IEEE transactions on knowledge and data engineering, 31(5):833–852, 2018.
  * [11] Caterina De Bacco, Eleanor A Power, Daniel B Larremore, and Cristopher Moore.  Community detection, link prediction, and layer interdependence in multilayer networks.  Physical Review E, 95(4):042317, 2017.
  * [12] Christian Doerr and Norbert Blenn.  Metric convergence in social network sampling.  In Proceedings of the 5th ACM workshop on HotPlanet, pages 45–50, 2013.
  * [13] Andrew Estabrooks, Taeho Jo, and Nathalie Japkowicz.  A multiple resampling method for learning from imbalanced data sets.  Computational Intelligence, 20(1):18–36, 2004.
  * [14] Amir Ghasemian, Homa Hosseinmardi, Aram Galstyan, Edoardo M Airoldi, and Aaron Clauset.  Stacking models for nearly optimal link prediction in complex networks.  Proceedings of the National Academy of Sciences, 117(38):23393–23400, 2020.
  * [15] Amir Ghasemian, Pan Zhang, Aaron Clauset, Cristopher Moore, and Leto Peel.  Detectability thresholds and optimal algorithms for community structure in dynamic networks.  Physical Review X, 6(3):031005, 2016.
  * [16] Minas Gjoka, Maciej Kurant, Carter T Butts, and Athina Markopoulou.  Walking in facebook: A case study of unbiased sampling of osns.  In 2010 Proceedings IEEE Infocom, pages 1–9. Ieee, 2010.
  * [17] Aditya Grover and Jure Leskovec.  node2vec: Scalable feature learning for networks.  In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855–864, 2016.
  * [18] Aric Hagberg, Pieter Swart, and Daniel S Chult.  Exploring network structure, dynamics, and function using networkx.  Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 2008.
  * [19] Mark S Handcock and Krista Gile.  Modeling social networks with sampled or missing data.  Center for Statistics in the Social Sciences, Univ. Washington. Available at http://www. csss. washington. edu/Papers, 2007.
  * [20] Xie He, Amir Ghasemian, Eun Lee, Aaron Clauset, and Peter Mucha.  Sequential stacking link prediction algorithms for temporal networks.  2023\.
  * [21] Desislava Hristova, Anastasios Noulas, Chloë Brown, Mirco Musolesi, and Cecilia Mascolo.  A multilayer approach to multiplexity and link prediction in online geo-social networks.  EPJ Data Science, 5:1–17, 2016.
  * [22] Christian Hübler, Hans-Peter Kriegel, Karsten Borgwardt, and Zoubin Ghahramani.  Metropolis algorithms for representative subgraph sampling.  In 2008 Eighth IEEE International Conference on Data Mining, pages 283–292. IEEE, 2008.
  * [23] Terrence D Jorgensen, K Jean Forney, Jeffrey A Hall, and Steven M Giles.  Using modern methods for missing data analysis with the social relations model: A bridge to social network analysis.  Social networks, 54:26–40, 2018.
  * [24] Weijia Kong, Bertrand Jern Han Wong, Huanhuan Gao, Tiannan Guo, Xianming Liu, Xiaoxian Du, Limsoon Wong, and Wilson Wen Bin Goh.  Protrec: A probability-based approach for recovering missing proteins based on biological networks.  Journal of Proteomics, 250:104392, 2022.
  * [25] Yehuda Koren, Robert Bell, and Chris Volinsky.  Matrix factorization techniques for recommender systems.  Computer, 42(8):30–37, 2009.
  * [26] Vaishnavi Krishnamurthy, Michalis Faloutsos, Marek Chrobak, Li Lao, J-H Cui, and Allon G Percus.  Reducing large internet topologies for faster simulations.  In International Conference on Research in Networking, pages 328–341. Springer, 2005.
  * [27] Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, and Pan Zhang.  Spectral redemption in clustering sparse networks.  Proceedings of the National Academy of Sciences, 110(52):20935–20940, 2013.
  * [28] Ajay Kumar, Shashank Sheshar Singh, Kuldeep Singh, and Bhaskar Biswas.  Link prediction techniques, applications, and performance: A survey.  Physica A: Statistical Mechanics and its Applications, 553:124289, 2020.
  * [29] Chul-Ho Lee, Xin Xu, and Do Young Eun.  Beyond random walk and metropolis-hastings samplers: why you should not backtrack for unbiased graph sampling.  ACM SIGMETRICS Performance evaluation review, 40(1):319–330, 2012\.
  * [30] Jure Leskovec and Christos Faloutsos.  Sampling from large graphs.  In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 631–636, 2006.
  * [31] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos.  Graphs over time: densification laws, shrinking diameters and possible explanations.  In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pages 177–187, 2005.
  * [32] Taisong Li, Jiawei Zhang, S Yu Philip, Yan Zhang, and Yonghong Yan.  Deep dynamic network embedding for link prediction.  IEEE Access, 6:29219–29230, 2018.
  * [33] Tianxi Li, Yun-Jhong Wu, Elizaveta Levina, and Ji Zhu.  Link prediction for egocentrically sampled networks.  Journal of Computational and Graphical Statistics, pages 1–24, 2023\.
  * [34] David Liben-Nowell and Jon Kleinberg.  The link-prediction problem for social networks.  Journal of the American Society for Information Science and Technology, 58(7):1019–1031, 2007.
  * [35] Linyuan Lü and Tao Zhou.  Link prediction in complex networks: A survey.  Physica A, 390(6):1150–1170, 2011.
  * [36] Gökçen Eraslan Lucas Hu, Thomas Kipf.  Link prediction experiments.  2018\.
  * [37] Víctor Martínez, Fernando Berzal, and Juan-Carlos Cubero.  A survey of link prediction in complex networks.  ACM computing surveys (CSUR), 49(4):1–33, 2016.
  * [38] Farokh Marvasti.  Nonuniform sampling: theory and practice.  Springer Science & Business Media, 2012.
  * [39] Mark EJ Newman.  Community detection in networks: Modularity optimization and maximum likelihood are equivalent.  arXiv preprint arXiv:1606.02319, 2016.
  * [40] Tiago P Peixoto.  Parsimonious module inference in large networks.  Physical review letters, 110(14):148701, 2013.
  * [41] Alireza Rezvanian and Mohammad Reza Meybodi.  Sampling social networks using shortest paths.  Physica A: Statistical Mechanics and its Applications, 424:254–268, 2015.
  * [42] Bruno Ribeiro and Don Towsley.  Estimating and sampling graphs with multidimensional random walks.  In Proceedings of the 10th ACM SIGCOMM conference on Internet measurement, pages 390–403, 2010.
  * [43] Benedek Rozemberczki, Oliver Kiss, and Rik Sarkar.  Little Ball of Fur: a python library for graph sampling.  In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 3133–3140, 2020.
  * [44] Benedek Rozemberczki and Rik Sarkar.  Fast sequence-based embedding with diffusion graphs.  In International Workshop on Complex Networks, pages 99–107. Springer, 2018.
  * [45] Michael PH Stumpf, Carsten Wiuf, and Robert M May.  Subnets of scale-free networks are not scale-free: sampling properties of networks.  Proceedings of the National Academy of Sciences, 102(12):4221–4224, 2005.
  * [46] Sadegh Sulaimany, Mohammad Khansari, and Ali Masoudi-Nejad.  Link prediction potentials for biological networks.  International Journal of Data Mining and Bioinformatics, 20(2):161–184, 2018.
  * [47] Riitta Toivonen, Jukka-Pekka Onnela, Jari Saramäki, Jörkki Hyvönen, and Kimmo Kaski.  A model for social networks.  Physica A: Statistical Mechanics and its Applications, 371(2):851–860, 2006.
  * [48] Zoltán Toroczkai and Hasan Guclu.  Proximity networks and epidemics.  Physica A, 378(1):68–75, 2007.
  * [49] Toni Vallès-Català, Tiago P Peixoto, Marta Sales-Pardo, and Roger Guimerà.  Consistencies and inconsistencies between model selection and link prediction in networks.  Physical Review E, 97(6):062316, 2018.
  * [50] Klaus Von Lampe and Per Ole Johansen.  Organized crime and trust:: On the conceptualization and empirical relevance of trust in the context of criminal networks.  Global Crime, 6(2):159–184, 2004.
  * [51] David Bruce Wilson.  Generating random spanning trees more quickly than the cover time.  In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 296–303, 1996.
  * [52] Jiehua Wu, Guoji Zhang, and Yazhou Ren.  A balanced modularity maximization link prediction model in social networks.  Information Processing & Management, 53(1):295–307, 2017.
  * [53] Yasser Yasami and Farshad Safaei.  A novel multilayer model for missing link prediction and future link forecasting in dynamic complex networks.  Physica A, 492:2166–2197, 2018.
  * [54] Wayne W Zachary.  An information flow model for conflict and fission in small groups.  Journal of anthropological research, 33(4):452–473, 1977.
  * [55] Tao Zhou.  Progresses and challenges in link prediction.  Iscience, 24(11):103217, 2021.
  * [56] Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang.  Predicting missing links via local information.  The European Physical Journal B, 71(4):623–630, 2009.
  * [57] Zhuojie Zhou, Nan Zhang, and Gautam Das.  Leveraging history for faster sampling of online social networks.  arXiv preprint arXiv:1505.00079, 2015.

For completeness, we include the results of all 20 sampling methods by
plotting out the results from tables 1, 2, 3, 4, 5 and 6 and the AUC results
with the variance in Figure 4.

To better understand the variation behind the sampling methods and their
effect on the link prediction algorithms for datasets across various domains,
we perform Principal Component Analysis (PCA) using the AUC scores as features
to characterize each of the 20 sampling methods, with PCA performed separately
for each of the 6 data domains and 9 link prediction algorithms. That is, for
each sampling method and prediction algorithm, we use the AUC scores obtained
(averaged over 5 randomized repeats of 5-fold cross-validation) from the
different networks in that domain as the feature vector. We then perform PCA
on the set of feature vectors across different sampling methods, performed
separately for each prediction algorithm in each data domain. For example, the
top left corner panel visualizes the first two principal component scores of
the 20 sampling methods obtained from the AUCs of Adamic-Adar on the 119
biological networks — i.e., the feature vector of a sampling method includes
the 119 AUC scores (averaged over 5 randomized repeats of 5-fold cross-
validation) stacked together.

The PCA outcomes for simple local methods like Adamic-Adar and Jaccard
Coefficient are consistent with our observations in Figure 4, where we find
most of the sampling methods cluster closely with each other, except for
transportation networks. This difference may be due to greater structural
diversity in transportation networks; for instance, airport networks might
have drastically different structures from bus networks.

(a) Edge-Based Missingness Patterns (b) Node-Based Missingness Patterns

(c) DFS Missingness Pattern (d) Neighbor-Based Missingness Patterns

(e) Node-Jump-Based Missingness Patterns

Figure 3: Realized samples of the Zachary Karate Club [54] by various Edge-
Based sampling methods. Sampled edges and nodes are marked in orange. The not
selected edges are marked black and not selected nodes marked blue. Figure 4:
AUC scores over 5 randomized repeats of 5-fold cross validation for 8 link
prediction algorithms on samples obtained by 20 methods. The 250 different
networks are grouping into 6 domains (arranged vertically). Symbols indicate
mean AUCs, with standard Errors shown by vertical bars. The sampling methods
are listed along the bottom of the figure. The prediction methods are marked
with different colors, as indicated in the legend. Figure 5: PCA scores (PC1
horizontal, PC2 vertical) for different sampling methods under different
prediction algorithms for different dataset domains. Each panel considers a
single link prediction method within a single dataset domain, taking as
features the full set of AUC scores (averaged over 5 randomized repeats of
5-fold cross-validation) of that prediction method across the networks in that
domain for each sampling method, marked with different colors and symbols as
indicated in the legend.

(a) Edge-Based Missingness Pattern

(b) Node-Based Missingness Pattern

(c) DFS Missingness Pattern

Figure 6:

(d) Neighbor-Based Missingness Pattern

(e) Node-Jump-Based Missingness Pattern

Figure 6: The overall averaged results for different types of missingness
pattern.

(a) Random Node Sampler

(b) PageRank Based Sampler

Figure 7: Node-Based Missingness Patterns

(a) Random Node Edge Sampler

(b) Hybrid Node Edge Sampler

(c) Random Edge Sampler With Induction

Figure 8: Edge-Based Missingness Patterns

(a) Forest Fire Sampler

(b) Nonbacktracking Random Walk Sampler

(c) Random Walk Sampler

Figure 9:

(d) Random Walk With Restart Sampler

(e) Metropolis Hastings Random Walk Sampler

(f) Circulated Neighbors Random Walk Sampler

Figure 9:  (g) Breadth First Search Sampler Figure 9: Neighbor-Based
Missingness Patterns

(a) Loop Erased Random Walk Sampler

(b) Random Walk With Jump Sampler

(c) Random Node Neighbor Sampler

Figure 10: Node-Jump-Based Missingess Patterns