Link Prediction in Complex Networks: A Survey

Linyuan LuTao Zhou

article2010Physica A2,859 citations

Systematizes link prediction methods across statistical physics and computer science, providing actionable algorithms for reconstructing missing connections and testing network evolution models.

Listen

The article addresses the challenge of predicting missing or future links in complex networks that represent social, biological, and information systems, where incomplete or noisy data hinders analysis of structure and function. This task matters now because accurate predictions can sharply cut experimental costs in areas like protein interactions while enabling better recommendations and mechanism evaluation in evolving networks. The article set out to survey recent link prediction algorithms, with emphasis on physical approaches such as random-walk-based methods and maximum likelihood estimation, while also covering applications and open challenges. It reviews the methods through classification into similarity-based indices, maximum likelihood techniques, and probabilistic models, then evaluates them on real networks using standard metrics of AUC and precision across training and probe sets obtained by random or cross-validation splits. Key findings show that local indices such as resource allocation outperform common-neighbor and preferential-attachment measures on most tested networks, quasi-local indices like the local-path method deliver competitive accuracy at far lower cost than global measures, Katz and random-walk-with-restart indices achieve the highest overall accuracy when full topology is available, and maximum-likelihood methods based on hierarchical or stochastic block models provide valuable structural insight even if they are slower and sometimes less accurate. These results indicate that algorithm choice should match network features such as clustering and average distance, directly affecting practical outcomes in cost reduction, network reconstruction, and model selection. The survey recommends developing hybrid ensemble predictors, extending methods to directed, weighted, and multi-dimensional networks, and incorporating temporal information and node attributes for better performance on dynamic or sparsely labeled data; additional work is required before strong decisions can be made on very large or rapidly changing systems. The main limitations are the focus on undirected unweighted networks and the dependence of relative performance on specific structural properties, so readers should treat the reported rankings as indicative rather than universal.

University of Electronic Science and Technology of China University of Fribourg University of Science and Technology of China University of Shanghai for Science and Technology classification complex networks link prediction Link Prediction Complex Network Node Similarity

arXiv: 1010.0725

Paper: The link prediction problem for social networks, David Liben-Nowell et al. (2003). This seminal paper formalized the topological link prediction problem and established the benchmark node proximity heuristics evaluated throughout the survey.
Paper: Hierarchical structure and the prediction of missing links in networks, Aaron Clauset et al. (2008). It introduces the hierarchical random graph and maximum likelihood estimation framework for predicting missing links, which forms a primary category of algorithms in the survey.
Paper: SimRank: a measure of structural-context similarity, Glen Jeh et al. (2002). It defines SimRank, a foundational global structural-context similarity metric based on random walks that is analyzed and compared in the survey.
Paper: Markov logic networks, Matthew Richardson et al. (2006). It establishes Markov logic networks, providing the core theoretical foundation for the probabilistic and relational modeling approaches reviewed in the survey.
Paper: Community detection in graphs, Santo Fortunato (2009). It provides a comprehensive treatment of community structure and graph partitioning, which underpins the block modeling and community-based link prediction methods examined in the survey.
Paper: Graphs over time: densification laws, shrinking diameters and possible explanations, J. Leskovec et al. (2005). It analyzes network evolution and densification patterns over time, providing empirical context for the dynamic and evolving network predictions surveyed.

Paper: Link Prediction Based on Graph Neural Networks, Muhan Zhang et al. (2018). It extends classical heuristic-based link prediction into modern deep learning by proving that high-order heuristics can be learned from enclosing subgraphs using graph neural networks.
Paper: Variational Graph Auto-Encoders, Thomas N. Kipf et al. (2016). It develops variational graph auto-encoders, formulating an unsupervised deep learning paradigm for link prediction that integrates both topology and node features.
Paper: node2vec: Scalable Feature Learning for Networks, Aditya Grover et al. (2016). It generalizes similarity and random-walk concepts to learn continuous node representations specifically optimized for downstream edge prediction.
Paper: A Three-Way Model for Collective Learning on Multi-Relational Data, Maximilian Nickel et al. (2011). It directly addresses the survey's call for link prediction on multi-relational graphs by formulating a scalable tensor factorization framework.
Paper: Modeling Relational Data with Graph Convolutional Networks, Michael Schlichtkrull et al. (2018). It advances link prediction to directed, multi-relational knowledge graphs using relational graph convolutional networks.
Paper: DeepWalk: online learning of social representations, Bryan Perozzi et al. (2014). It pioneers representation learning on graphs via random walks, transitioning network link analysis from explicit similarity metrics to continuous vector embeddings.
Paper: Structural Deep Network Embedding, Daixin Wang et al. (2016). It applies deep autoencoders to preserve both first-order and second-order network proximity for enhanced link reconstruction in sparse graphs.
Paper: Temporal Networks, Petter Holme et al. (2011). It expands link analysis into dynamic temporal systems, addressing the challenge highlighted in the survey regarding time-respecting paths and evolving contacts.
Paper: The structure and dynamics of multilayer networks, S. Boccaletti et al. (2014). It generalizes structural measures and connection dynamics to multilayer and multiplex networks, fulfilling a key future direction identified by the survey.
Paper: Neural Graph Collaborative Filtering, Xiang Wang et al. (2019). It applies graph convolutional message passing to bipartite user-item interaction graphs for high-order collaborative filtering and link recommendation.

Cover for Link Prediction in Complex Networks: A Survey

Abstract

Link prediction in complex networks has attracted increasing attention from both physical and computer science communities. The algorithms can be used to extract missing information, identify spurious interactions, evaluate network evolving mechanisms, and so on. This article summaries recent progress about link prediction algorithms, emphasizing on the contributions from physical perspectives and approaches, such as the random-walk-based methods and the maximum likelihood methods. We also introduce three typical applications: reconstruction of networks, evaluation of network evolving mechanism and classification of partially labelled networks. Finally, we introduce some applications and outline future challenges of link prediction algorithms.

Topics

classification complex networks link prediction maximum likelihood method network architecture random walk reconstruction social sciences

Keywords

Link Prediction Complex Network Node Similarity Maximum Likelihood Method Probabilistic Model Local Similarity Index Global Similarity Index Quasi‑Local Index Hierarchical Structure Model Stochastic Block Model

1 Introduction
2 Problem Description and Evaluation Metrics
3 Similarity-Based Algorithms
3.1 Local Similarity Indices
3.2 Global Similarity Indices
3.3 Quasi-Local Indices
4 Maximum Likelihood Methods
4.1 Hierarchical Structure Model
4.2 Stochastic Block Model
5 Probabilistic Models
5.1 Probabilistic Relational Models
5.2 Probabilistic Entity Relationship Models
5.3 Stochastic Relational Models
6 Applications
6.1 Reconstruction of Networks
6.2 Evaluation of Network Evolving Mechanisms
6.3 Classification of Partially Labeled Networks
7 Outlook
References

Knowls

Knowl 1 — Problem Formulation and Standard Evaluation Metrics for Link Prediction
definition
Let $G(V, E)$ be an unweighted, undirected network where $V$ is the set of vertices (nodes) and $E$ is the set of observed edges (links), with self-connections and multiple edges disallowed. Let $U$ be the universal set containing all $|V|(|V|-1)/2$ possible undirected node pairs. The set of nonexistent or non-observed links is $U \setminus E$ . To evaluate link prediction algorithms, the observed edge set $E$ is randomly partitioned into a training set $E^T$ and a probe (validation/testing) set $E^P$ such that $E^T \cup E^P = E$ and $E^T \cap E^P = \emptyset$ . Prediction algorithms use only the topological information in $E^T$ to assign a score $s_{xy}$ to every unobserved pair $(x, y) \in U \setminus E^T$ , quantifying its likelihood of existence.

Prediction accuracy is evaluated using two primary metrics:
1. Area Under the Receiver Operating Characteristic Curve (AUC): Interpreted as the probability that a randomly chosen missing link (from $E^P$ ) receives a higher score than a randomly chosen nonexistent link (from $U \setminus E$ ). In an empirical implementation sampling $n$ independent comparisons between a probe edge and a nonexistent edge:
$\text{AUC} = \frac{n' + 0.5n''}{n}$
where $n'$ is the number of times the missing link has a higher score than the nonexistent link, and $n''$ is the number of times they share an identical score. A value of $\text{AUC} = 0.5$ corresponds to random chance, whereas $\text{AUC} = 1.0$ signifies perfect ranking.
1. Precision: The fraction of correctly predicted edges among the top- $L$ ranked candidate links in $U \setminus E^T$ . If $L_r$ of these top- $L$ candidates belong to the probe set $E^P$ , precision is defined as:
$\text{Precision} = \frac{L_r}{L}$
Knowl 2 — Local Node Similarity Indices
model/method
In similarity-based link prediction, each unobserved pair of nodes $x, y$ is assigned a score $s_{xy}$ directly measuring their topological proximity. Local similarity indices rely exclusively on the nearest-neighbor sets $\Gamma(x)$ and degrees $k_x = |\Gamma(x)|$ of the candidate nodes:
- Common Neighbors (CN): Counts shared adjacent nodes: $s_{xy}^{\text{CN}} = |\Gamma(x) \cap \Gamma(y)| = (A^2)_{xy}$ where $A$ is the adjacency matrix ( $A_{uv} = 1$ if $(u, v) \in E$ , $0$ otherwise).
- Salton Index (Cosine Similarity): Normalizes common neighbors by the geometric mean of degrees: $s_{xy}^{\text{Salton}} = \frac{|\Gamma(x) \cap \Gamma(y)|}{\sqrt{k_x \times k_y}}$
- Jaccard Index: Computes the Jaccard similarity coefficient of the neighborhood sets: $s_{xy}^{\text{Jaccard}} = \frac{|\Gamma(x) \cap \Gamma(y)|}{|\Gamma(x) \cup \Gamma(y)|}$
- Sørensen Index: Normalizes neighborhood overlap by the arithmetic mean of degrees: $s_{xy}^{\text{Sørensen}} = \frac{2|\Gamma(x) \cap \Gamma(y)|}{k_x + k_y}$
- Hub Promoted Index (HPI): Strongly promotes connections adjacent to network hubs: $s_{xy}^{\text{HPI}} = \frac{|\Gamma(x) \cap \Gamma(y)|}{\min\{k_x, k_y\}}$
- Hub Depressed Index (HDI): Penalizes connections adjacent to network hubs: $s_{xy}^{\text{HDI}} = \frac{|\Gamma(x) \cap \Gamma(y)|}{\max\{k_x, k_y\}}$
- Leicht-Holme-Newman Index 1 (LHN1): Normalizes CN by the expected number of shared neighbors in the configuration model: $s_{xy}^{\text{LHN1}} = \frac{|\Gamma(x) \cap \Gamma(y)|}{k_x \times k_y}$
- Preferential Attachment (PA): Models growth without neighborhood overlap using degree product: $s_{xy}^{\text{PA}} = k_x \times k_y$
- Adamic-Adar Index (AA): Assigns greater weight to common neighbors with lower degrees: $s_{xy}^{\text{AA}} = \sum_{z \in \Gamma(x) \cap \Gamma(y)} \frac{1}{\log k_z}$
- Resource Allocation Index (RA): Models resource transmission from $x$ to $y$ through common neighbors distributing unit resource equally among all adjacent nodes: $s_{xy}^{\text{RA}} = \sum_{z \in \Gamma(x) \cap \Gamma(y)} \frac{1}{k_z}$
Knowl 3 — Global Node Similarity Indices
model/method
Global similarity indices compute proximity scores by evaluating the complete topological structure of the network:
- Katz Index: Sums over all paths connecting $x$ and $y$ , exponentially damped by path length $l$ with damping parameter $\beta < 1/\lambda_1$ (where $\lambda_1$ is the largest eigenvalue of adjacency matrix $A$ ): $s_{xy}^{\text{Katz}} = \sum_{l=1}^\infty \beta^l (A^l)_{xy} \implies S^{\text{Katz}} = (I - \beta A)^{-1} - I$
- Leicht-Holme-Newman Global Index (LHN2): Normalizes path counts by their expected values under a random configuration model: $S^{\text{LHN2}} = 2M\lambda_1 D^{-1} \left(I - \frac{\phi}{\lambda_1} A\right)^{-1} D^{-1}$ where $M$ is the total edge count, $D = \text{diag}(k_x)$ , and $\phi \in (0, 1)$ is a free damping parameter.
- Average Commute Time (ACT): Based on the average number of random-walk steps $n(x, y) = m(x, y) + m(y, x)$ required to travel between $x$ and $y$ , calculated via the Moore-Penrose pseudoinverse $L^+$ of the graph Laplacian $L = D - A$ : $s_{xy}^{\text{ACT}} = \frac{1}{l^+_{xx} + l^+_{yy} - 2l^+_{xy}}$
- Cosine based on $L^+$ ( $\text{cos}^+$ ): Evaluates the cosine of Euclidean node embedding vectors derived from $L^+$ : $s_{xy}^{\text{cos}^+} = \frac{l^+_{xy}}{\sqrt{l^+_{xx} l^+_{yy}}}$
- Random Walk with Restart (RWR): Derived from the steady-state probability vector $\vec{q}_x$ of a random walker starting at $x$ who transitions to a neighbor with probability $c$ and restarts at $x$ with probability $1 - c$ : $\vec{q}_x = (1 - c)(I - c P^T)^{-1} \vec{e}_x, \quad s_{xy}^{\text{RWR}} = q_{xy} + q_{yx}$ where $P_{uv} = 1/k_u$ if $(u, v) \in E$ and $0$ otherwise.
- SimRank: A self-consistent measure where similarity satisfies: $s_{xy}^{\text{SimRank}} = C \sum_{z \in \Gamma(x)} \sum_{z' \in \Gamma(y)} \frac{s_{zz'}^{\text{SimRank}}}{k_x k_y} \quad (s_{xx} = 1)$ with decay factor $C \in [0, 1]$ .
- Matrix Forest Index (MFI): Measures the ratio of spanning rooted forests in which $x$ and $y$ belong to the same tree rooted at $x$ to all spanning forests: $S^{\text{MFI}} = (I + \alpha L)^{-1}, \quad \alpha > 0$
Knowl 4 — Quasi-Local Similarity Indices for Link Prediction
model/method
Quasi-local indices provide a computational and accuracy compromise between local and global methods by restricting path enumeration or random walks to local horizons:
- Local Path (LP) Index: Incorporates paths of length 2 and 3 weighted by a free parameter $\epsilon$ : $S^{\text{LP}} = A^2 + \epsilon A^3$ For an arbitrary maximum path order $n > 2$ : $S^{\text{LP}(n)} = A^2 + \epsilon A^3 + \epsilon^2 A^4 + \dots + \epsilon^{n-2} A^n$ The computational complexity on uncorrelated networks is $\mathcal{O}(N \langle k \rangle^n)$ . As $n \to \infty$ , $S^{\text{LP}(n)}$ converges to the Katz index.
- Local Random Walk (LRW): Traces an initial probability distribution $\vec{\pi}_x(0) = \vec{e}_x$ evolving as $\vec{\pi}_x(t+1) = P^T \vec{\pi}_x(t)$ for a small number of steps $t$ : $s_{xy}^{\text{LRW}}(t) = q_x \pi_{xy}(t) + q_y \pi_{yx}(t)$ where $q_x = k_x / M$ is the degree-proportional initial configuration weight and $M$ is total edge count.
- Superposed Random Walk (SRW): Continuously releases the random walker at the source node by summing LRW similarities over steps $\tau = 1, \dots, t$ : $s_{xy}^{\text{SRW}}(t) = \sum_{\tau=1}^t s_{xy}^{\text{LRW}}(\tau) = \sum_{\tau=1}^t [q_x \pi_{xy}(\tau) + q_y \pi_{yx}(\tau)]$
For LRW and SRW, the optimal step length $t$ is positively correlated with the average shortest path distance of the network. Because they require $\mathcal{O}(N \langle k \rangle^t)$ operations, they are orders of magnitude faster than matrix-inversion global measures on large, sparse graphs.

Knowl 5 — Empirical Accuracy Comparison of Local Similarity Indices

data/table

Performance of ten local similarity indices across six disparate benchmark networks: a protein-protein interaction network (PPI), a co-authorship network of network scientists (NS), the western US electrical power grid (Grid), US political blogs (PB), a router-level Internet topology (INT), and the US air transportation system (USAir). Accuracy is quantified by AUC averaged over 10 independent random partitions (90% training set, 10% probe set).

Indices	PPI	NS	Grid	PB	INT	USAir
CN	0.889	0.933	0.590	0.925	0.559	0.937
Salton	0.869	0.911	0.585	0.874	0.552	0.898
Jaccard	0.888	0.933	0.590	0.882	0.559	0.901
Sørensen	0.888	0.933	0.590	0.881	0.559	0.902
HPI	0.868	0.911	0.585	0.852	0.552	0.857
HDI	0.888	0.933	0.590	0.877	0.559	0.895
LHN1	0.866	0.911	0.585	0.772	0.552	0.758
PA	0.828	0.623	0.446	0.907	0.464	0.886
AA	0.888	0.932	0.590	0.922	0.559	0.925
RA	0.890	0.933	0.590	0.931	0.559	0.955

The empirical data reveals:

The Resource Allocation (RA) index achieves the highest overall prediction accuracy across the datasets, followed by Common Neighbors (CN) and Adamic-Adar (AA).
Penalizing high-degree hubs by $1/k_z$ (in RA) provides superior discrimination compared to $1/\log k_z$ (in AA).
The Preferential Attachment (PA) index fails significantly on physical/spatial networks (Grid AUC 0.446, INT AUC 0.464, performing worse than pure chance at 0.5) because high-degree nodes in these networks are geographically separated and rarely connected directly.

Knowl 6 — Empirical Comparison of Local, Global, Quasi-Local, and Maximum Likelihood Methods

data/table

Comparison of link prediction accuracy across local (CN, RA), quasi-local (LP, LRW, SRW), global (ACT, RWR), and maximum likelihood (Hierarchical Structure Model, HSM) methods on five networks (USAir, NetScience, Power Grid, Yeast, C. elegans). Evaluations use 90% training links and 10% probe links averaged over 1000 implementations ( $\epsilon = 10^{-3}$ for LP, $c = 0.9$ for RWR, and 5000 dendrogram samples for HSM).

AUC	CN	RA	LP	ACT	RWR	HSM	LRW	SRW
USAir	0.954	0.972	0.952	0.901	0.977	0.904	0.972(2)	0.978(3)
NetScience	0.978	0.983	0.986	0.934	0.993	0.930	0.989(4)	0.992(3)
Power	0.626	0.626	0.697	0.895	0.760	0.503	0.953(16)	0.963(16)
Yeast	0.915	0.916	0.970	0.900	0.978	0.672	0.974(7)	0.980(8)
C.elegans	0.849	0.871	0.867	0.747	0.889	0.808	0.899(3)	0.906(3)
Precision ( $L=100$ )	CN	RA	LP	ACT	RWR	HSM	LRW	SRW
USAir	0.59	0.64	0.61	0.49	0.65	0.28	0.64(3)	0.67(3)
NetScience	0.26	0.54	0.30	0.19	0.55	0.25	0.54(2)	0.54(2)
Power	0.11	0.08	0.13	0.08	0.09	0.00	0.08(2)	0.11(3)
Yeast	0.67	0.49	0.68	0.57	0.52	0.84	0.86(3)	0.73(9)
C.elegans	0.12	0.13	0.14	0.07	0.13	0.08	0.14(3)	0.14(3)

Note: Integers in parentheses denote the optimal step parameter $t$ for LRW and SRW.

Key takeaways:

Superposed Random Walk (SRW) and Local Random Walk (LRW) consistently achieve the highest overall AUC and precision scores while maintaining low computational complexity ( $\mathcal{O}(N\langle k \rangle^t)$ ).
The optimal random walk step $t$ scales with the network's average shortest path distance: small-diameter networks (USAir, NetScience, C. elegans) peak at $t = 2\text{--}4$ , whereas the sparse, large-diameter Power Grid peaks at $t = 16$ .

Knowl 7 — Hierarchical Structure Model for Link Prediction
model/method
The Hierarchical Structure Model (HSM) infers hierarchical organization by representing a network $G(V, E)$ with $N = |V|$ nodes as a binary dendrogram $D$ containing $N$ leaves and $N-1$ internal nodes. Each internal node $r$ is associated with a connection probability $p_r$ . For any pair of leaves $i, j$ , their connecting probability is $p_r$ , where $r = \text{lca}(i, j)$ is the lowest common ancestor of $i$ and $j$ in $D$ .

Let $E_r$ denote the number of edges in $G$ whose endpoints have $r$ as their lowest common ancestor in $D$ , and let $L_r$ and $R_r$ be the number of leaves in the left and right subtrees rooted at $r$ . The likelihood of the observed network given dendrogram $D$ and parameters $\{p_r\}$ is:
$\mathcal{L}(D, \{p_r\}) = \prod_r p_r^{E_r} (1 - p_r)^{L_r R_r - E_r}$
Maximizing the likelihood for a fixed dendrogram yields:
$p_r^* = \frac{E_r}{L_r R_r}$
To predict missing links:
1. Markov Chain Monte Carlo (MCMC) sampling is applied to sample dendrograms with probability proportional to their maximized likelihood $\mathcal{L}(D)$ .
2. For each non-observed node pair $(i, j)$ , the connection probability is estimated as the ensemble average $\langle p_{ij} \rangle$ over all sampled dendrograms.
3. Non-observed pairs are ranked in descending order of $\langle p_{ij} \rangle$ .
Knowl 8 — Stochastic Block Model and Bayesian Link Reliability
model/method
In the Stochastic Block Model (SBM), nodes are partitioned into disjoint groups $\mathcal{M} = \{C_1, C_2, \dots, C_k\}$ . The probability that two nodes in groups $\alpha$ and $\beta$ are connected is governed solely by group affiliation via parameter $Q_{\alpha\beta}$ .

Given partition $\mathcal{M}$ , let $l_{\alpha\beta}$ be the number of observed edges between groups $\alpha$ and $\beta$ , and let $r_{\alpha\beta}$ be the total number of possible node pairs between these groups ( $r_{\alpha\alpha} = |C_\alpha|(|C_\alpha|-1)/2$ and $r_{\alpha\beta} = |C_\alpha||C_\beta|$ for $\alpha \neq \beta$ ). The likelihood of the observed network adjacency matrix $A$ is:
$\mathcal{L}(A | \mathcal{M}) = \prod_{\alpha \le \beta} Q_{\alpha\beta}^{l_{\alpha\beta}} (1 - Q_{\alpha\beta})^{r_{\alpha\beta} - l_{\alpha\beta}}$
which is maximized at:
$Q_{\alpha\beta}^* = \frac{l_{\alpha\beta}}{r_{\alpha\beta}}$
Using Bayes' theorem over the space $\Omega$ of all possible partitions with uniform prior $p(\mathcal{M})$ , the reliability $R_{xy}$ of an individual link $(x, y)$ is defined as:
$R_{xy} = \mathcal{L}(A_{xy} = 1 | A) = \frac{\int_\Omega \mathcal{L}(A_{xy} = 1 | \mathcal{M}) \mathcal{L}(A | \mathcal{M}) p(\mathcal{M}) d\mathcal{M}}{\int_\Omega \mathcal{L}(A | \mathcal{M}') p(\mathcal{M}') d\mathcal{M}'}$
Link reliability $R_{xy}$ quantifies the true existence probability of a link given the observed network. Nonexistent pairs with the highest reliabilities are predicted as missing links, while existing edges with the lowest reliabilities are identified as spurious links.
Knowl 9 — Network Reconstruction Algorithm Based on Link Reliability Swapping
algorithm
To reconstruct the true network topology from a corrupted observation $A^O$ containing both missing and spurious edges, Guimerà and Sales-Pardo define the total network reliability $R(A)$ as:
$R(A) = \prod_{A_{xy}=1, x<y} R_{xy} = \prod_{A_{xy}=1, x<y} \mathcal{L}(A_{xy}=1 | A^O)$
where $R_{xy}$ is the individual link reliability calculated from the observed network $A^O$ under the stochastic block model.

The greedy reconstruction procedure proceeds as follows:
Input: Observed adjacency matrix $A^O$ , link reliabilities $R_{xy}$ for all node pairs
Output: Reconstructed adjacency matrix $A$
Initialize: $A \leftarrow A^O$
Initialize: consecutive_rejections $\leftarrow 0$
while consecutive_rejections $< 5$ do
    Select candidate edge $(u, v) \in A$ with the lowest $R_{uv}$ not yet evaluated in current trial
    Select candidate non-edge $(x, y) \notin A$ with the highest $R_{xy}$ not yet evaluated in current trial
    Construct candidate network $A' \leftarrow (A \setminus \{(u, v)\}) \cup \{(x, y)\}$
    Compute candidate reliability $R(A')$
    if $R(A') > R(A)$ then
         $A \leftarrow A'$
        consecutive_rejections $\leftarrow 0$
    else
        consecutive_rejections $\leftarrow$ consecutive_rejections $+ 1$
    end if
end while
return $A$
Reconstructed networks generated by this algorithm significantly improve estimates of fundamental macroscopic properties—including clustering coefficient, modularity, assortativity, transport congestability, synchronizability, and epidemic spreading threshold.
Knowl 10 — Evaluating Network Evolving Mechanisms via Link Prediction Accuracy
model/method
Because each proposed network evolving mechanism posits specific driving factors for link formation, any evolving model can be mapped directly to a similarity index $s_{xy}$ and evaluated using standard link prediction accuracy metrics.

In the Chinese city airline network ( $|V| = 121$ airport cities, $|E| = 1378$ direct airline routes), candidate evolving mechanisms are mapped to similarity indices:
1. Topological clustering mechanism (Common Neighbors): $s_{xy}^{\text{CN}} = |\Gamma(x) \cap \Gamma(y)|$
2. Geographical distance decay: $s_{xy}^{\text{DIS}} = \frac{1}{D_g(x, y)}$ where $D_g(x, y)$ is the geographical distance between cities $x$ and $y$ .
3. City population factor: $s_{xy}^{\text{POPU}} = P(x) \times P(y)$ where $P(x)$ is the population of city $x$ .
4. City economic output (GDP): $s_{xy}^{\text{GDP}} = G(x) \times G(y)$ where $G(x)$ is the gross domestic product of city $x$ .
5. Tertiary industry (service sector) output: $s_{xy}^{\text{TI}} = T(x) \times T(y)$ where $T(x)$ is the tertiary industry GDP of city $x$ .
Evaluating these mechanisms under leave-one-out cross-validation yields:
- $S^{\text{CN}}$ : $\text{AUC} = 0.898$
- $S^{\text{TI}}$ : $\text{AUC} = 0.881$
- $S^{\text{GDP}}$ : $\text{AUC} = 0.855$
- $S^{\text{POPU}}$ : $\text{AUC} = 0.745$
- $S^{\text{DIS}}$ : $\text{AUC} = 0.699$
A linear combination $S' = \lambda S^{\text{CN}} + (1 - \lambda) S^{\text{TI}}$ achieves an optimal $\text{AUC} = 0.928$ at $\lambda \approx 0.2$ , quantitatively confirming that the tertiary industry is the primary socio-economic factor driving airline network topology.
Knowl 11 — Semi-Supervised Node Classification in Partially Labeled Networks via Link Proximity
model/method
In a partially labeled network $G(V, E, L)$ , where $L = \{l_1, l_2, \dots, l_m\}$ denotes the set of class labels and unlabeled nodes are denoted by label $0$ , classification of unlabeled vertices can be performed by establishing virtual similarity edges between labeled and unlabeled vertices.

Given a similarity metric $s_{xy}$ (e.g., Common Neighbors or Resource Allocation), the probability that an unlabeled vertex $x$ belongs to class $l_i$ is computed as:
$p(l_i | x) = \frac{\sum_{\{y \mid y \neq x, \, \text{label}(y) = l_i\}} s_{xy}}{\sum_{\{y \mid y \neq x, \, \text{label}(y) \neq 0\}} s_{xy}}$
The predicted class label $\hat{l}(x)$ is chosen by maximum posterior probability:
$\hat{l}(x) = \arg\max_{l_i \in L} p(l_i | x)$
with ties broken uniformly at random. This similarity-based propagation mitigates label sparsity and structural inconsistency in partially labeled networks.
Knowl 12 — Probabilistic and Relational Models for Link Prediction
model/method
Probabilistic link prediction methods optimize a parameter set $\Theta$ to model the joint distribution of network topology and entity attributes, predicting links via conditional probability $P(A_{ij} = 1 | \Theta)$ :
1. Probabilistic Relational Models (PRMs): Formulate attribute dependencies across a data graph $G_D$ , model graph $G_M$ , and inference graph $G_I$ :
  - Relational Bayesian Networks (RBNs): Model dependencies as a directed acyclic graph over item types $T$ with conditional probability distributions (CPDs): $p(x) = \prod_{t \in T} \prod_{X_i^t \in X^t} \left[ \prod_{v: T(v)=t} p(x_{v_i}^t | \text{pa}_{x_{v_i}^t}) \prod_{e: T(e)=t} p(x_{e_i}^t | \text{pa}_{x_{e_i}^t}) \right]$
  - Relational Markov Networks (RMNs): Represent joint attribute distributions using undirected graphs and clique potentials $\Phi_c(x_c)$ : $p(x) = \frac{1}{Z} \prod_{c \in C} \Phi_c(x_c)$
  - Relational Dependency Networks (RDNs): Address cyclic dependencies using pseudo-likelihood and Gibbs sampling: $\text{PL}(G_D; \Theta) = \prod_{t \in T} \prod_{X_i^t \in X^t} \left[ \prod_{v: T(v)=t} p(x_{v_i}^t | \text{pa}_{x_{v_i}^t}; \Theta) \prod_{e: T(e)=t} p(x_{e_i}^t | \text{pa}_{x_{e_i}^t}; \Theta) \right]$
2. Directed Acyclic Probabilistic Entity-Relationship Models (DAPER): Treat relationships as first-class entities with explicit conditional probability arcs.
3. Stochastic Relational Models (SRMs): Model relationships via a tensor interaction of Gaussian Processes (GPs) defined over entity spaces $\mathcal{U}$ and $\mathcal{V}$ with hyperparameters $\Theta = \{\Theta_\Sigma, \Theta_\Omega\}$ : $p(R_I | \Theta) = \int \prod_{(i, j) \in I} p(r_{ij} | t_{ij}) p(t | \Theta) dt$ where $t: \mathcal{U} \times \mathcal{V} \to \mathbb{R}$ is a real-valued latent relation function.

Coverage note — Brief speculative outlook topics on future challenges (directed, signed, weighted, and multi-dimensional networks) were omitted as they discuss open problems rather than concrete models or experimental findings.

References

1.R. Albert, A.-L. Barabási, Statistical mechanics of complex networks, Rev. Modern Phys. 74 (2002) 47.
2.S.N. Dorogovtsev, J.F.F. Mendes, Evolution of networks, Adv. Phys. 51 (2002) 1079.
3.M.E.J. Newman, The structure and function of complex networks, SIAM Rev. 45 (2003) 167.
4.S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, D.-U. Huang, Complex networks: structure and dynamics, Phys. Rep. 424 (2006) 175.
5.L. da, F. Costa, F.A. Rodrigues, G. Travieso, P.R.U. Boas, Characterization of complex networks: a survey of measurements, Adv. Phys. 56 (2007) 167.
6.G. Salton, M.J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Auckland, 1983.
7.G. Salton, Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer, Addison-Wesley, Boston, 1989.
8.C.D. Manning, P. Raghavan, H. Schütze, Introduction to Information Retrieval, Cambridge University Press, New York, 2008.
9.L. Getoor, C.P. Diehl, Link mining: a survey, ACM SIGKDD Explor. Newsl. 7 (2005) 3.
10.H. Yu, et al., High-quality binary protein interaction map of the yeast interactome network, Science 322 (2008) 104.
11.M.P.H. Stumpf, T. Thorne, E. de Silva, R. Stewart, H.J. An, M. Lappe, C. Wiuf, Estimating the size of the human interactome, Proc. Natl. Acad. Sci. USA 105 (2008) 6959.
12.L.A.N. Amaral, A truer measure of our ignorance, Proc. Natl. Acad. Sci. USA 105 (2008) 6795.
13.L. Schafer, J.W. Graham, Missing data: our view of the state of the art, Psychol. Methods 7 (2002) 147.
14.G. Kossinets, Effects of missing data in social networks, Soc. Networks 28 (2006) 247.
15.J.W. Neal, ‘‘Kracking’’ the missing data problem: applying Krackhardt’s cognitive social structures to school-based social networks, Soc. Educ. 81 (2008) 140.
16.C. von Mering, R. Krause, B. Snel, M. Cornell, S.G. Oliver, S. Field, P. Bork, Comparative assessment of large-scale data sets of protein-protein interactions, Nature 417 (2002) 399.
17.C.T. Butts, Network inference, error, and information (in)accuracy: a Bayesian approach, Soc. Networks 25 (2003) 103.
18.R. Guimerà, M. Sales-Pardo, Missing and spurious interactions and the reconstruction of complex networks, Proc. Natl. Acad. Sci. USA 106 (2009) 22073.
19.S. Zhou, R.J. Mondragón, Accurately modeling the internet topology, Phys. Rev. E 70 (2004) 066108.
20.S. Carmi, S. Havlin, S. Kirkpatrick, Y. Shavitt, E. Shir, A model of Internet topology using k-shell decomposition, Proc. Natl. Acad. Sci. USA 104 (2007) 11150.
21.M. Sales-Pardo, R. Guimerà, L.A.N. Amaral, Extracting the hierarchical organization of complex systems, Proc. Natl. Acad. Sci. USA 104 (2007) 15224.
22.M. Girvan, M.E.J. Newman, Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA 99 (2002) 7821.
23.J. Shawe-Taylor, N. Cristianini, Kernels Methods for Pattern Analysis, Cambridge University Press, Cambridge, UK, 2004.
24.M.E.J. Newman, Analysis of weighted networks, Phys. Rev. E 70 (2004) 056131.
25.L. Breiman, P. Spector, Submodel selection and evaluation in regression: the x-random case, Int. Stat. Rev. 60 (1992) 291.
26.R. Kohavi, A study of cross-valisation and bootstrap for accuracy estimation and model selection, in: Proceedings of the International Joint Conference on Artificial Intelligence, Morgan Kaufmann Publisher, Quebec, Canada, 1995, pp. 1137–1143.
27.Y.-X. Zhu, L. Lü, Q.-M. Zhang, T. Zhou, Uncovering missing links with cold ends (unpublished).
28.F. Wilcoxon, Individual comparisons by ranking methods, Biom. Bull. 1 (1945) 80.
29.H.B. Mann, D.R. Whitney, On a test of whether one of two random variables is stochastically larger than the other, Ann. Math. Stat. 18 (1947) 50.
30.J.A. Hanely, B.J. McNeil, The meaning and use of the area under a receiver operating characteristic (ROC) curve, Radiology 143 (1982) 29.
31.S. Geisser, Predictive Inference: An Introduction, Chapman and Hall, New York, 1993.
32.J.L. Herlocker, J.A. Konstann, K. Terveen, J.T. Riedl, Evaluating collaborative filtering recommender systems, ACM Trans. Inf. Syst. 22 (2004) 5.
33.X. Su, T.M. Khoshgoftaar, A survey of collaborative filtering techniques, Adv. Artif. Intell. (2009) 421425.
34.Z. Huang, X. Li, H. Chen, Link prediction approach to collaborative filtering, in: Proceedings of the 5th ACM/IEEE-CS Joint Conference on Digital Libraries, ACM Press, New York, 2005.
35.D. Lin, An information-theoretic definition of similarity, in: Proceedings of the 15th International Conference on Machine Learning, Morgan Kaufman Publishers, San Francisco, 1998.
36.E.A. Leicht, P. Holme, M.E.J. Newman, Vertex similarity in networks, Phys. Rev. E 73 (2006) 026120.
37.D. Sun, T. Zhou, J.-G. Liu, R.-R. Liu, C.-X. Jia, B.-H. Wang, Information filtering based on transferring similarity, Phys. Rev. E 80 (2009) 017101.
38.D.R. White, K.P. Reitz, Graph and semigroup homomorphisms on networks of relations, Soc. Networks 5 (1983) 193.
39.P. Holme, M. Huss, Role-similarity based functional prediction in networked systems: application to the yeast proteome, J. R. Soc. Interface 2 (2005) 327.
40.M.E.J. Newman, Clustering and preferential attachment in growing networks, Phys. Rev. E 64 (2001) 025102.
41.P. Jaccard, Étude comparative de la distribution florale dans une portion des Alpes et des Jura, Bull. Soc. Vaud. Sci. Nat. 37 (1901) 547.
42.T. Sørensen, A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on Danish commons, Biol. Skr. 5 (1948) 1.
43.E. Ravasz, A.L. Somera, D.A. Mongru, Z.N. Oltvai, A.-L. Barabási, Hierarchical organization of modularity in metabolic networks, Science 297 (2002) 1551.
44.M. Molloy, B. Reed, A critical point for random graphs with a given degree sequence, Random Structures Algorithms 6 (1995) 161.
45.A.-L. Barabási, R. Albert, Emergence of scaling in random networks, Science 286 (1999) 509.
46.Y.-B. Xie, T. Zhou, B.-H. Wang, Scale-free networks without growth, Physica A 387 (2008) 1683.
47.P. Holme, B.J. Kim, C.N. Yoon, S.K. Han, Attack vulnerability of complex networks, Phys. Rev. E 65 (2002) 056109.
48.C.-Y. Yin, W.-X. Wang, G.-R. Chen, B.-H. Wang, Decoupling process for better synchronizability on scale-free networks, Phys. Rev. E 74 (2006) 047102.
49.G.-Q. Zhang, D. Wang, G.-J. Li, Enhancing the transmission efficiency by edge deletion in scale-free networks, Phys. Rev. E 76 (2007) 017101.
50.L.A. Adamic, E. Adar, Friends and neighbors on the web, Soc. Networks 25 (2003) 211.
51.T. Zhou, L. Lü, Y.-C. Zhang, Predicting missing links via local information, Eur. Phys. J. B 71 (2009) 623.
52.Q. Ou, Y.-D. Jin, T. Zhou, B.-H. Wang, B.-Q. Yin, Power-law strength-degree correlation from resource-allocation dynamics on weighted networks, Phys. Rev. E 75 (2007) 021102.
53.M.E.J. Newman, Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E 74 (2006) 036104.
54.D.J. Watts, S.H. Strogatz, Collective dynamics of ‘small-world’ networks, Nature 393 (1998) 440.
55.R. Ackland, Mapping the US political blogosphere: are conservative bloggers more prominent, in: Presentation to BlogTalk Downunder, Sydney, 2005, Available at: http://incsub.org/blogtalk/images/robertackland.pdf.
56.N. Spring, R. Mahajan, D. Wetherall, T. Anderson, IEEE/ACM Trans. Netw. 12 (2004) 2.
57.V. Batageli, A. Mrvar, Pajek datasets. Available at: http://vlado.fmf.uni-lj.si/pub/networks/data/default.htm.
58.D. Liben-Nowell, J. Kleinberg, The link-prediction problem for social networks, J. Am. Soc. Inf. Sci. Technol. 58 (2007) 1019.
59.M.T. Gastner, M.E.J. Newman, The spatial structure of networks, Eur. Phys. J. B 49 (2006) 247.
60.H.-K. Liu, T. Zhou, Empirical study of Chinese city airline network, Acta Phys. Sinica 56 (2007) 106.
61.S. Zhou, R.J. Mondragón, The rich-club phenomenon in the Internet topology, IEEE Commun. Lett. 8 (2004) 180.
62.V. Colizza, A. Flammini, M.A. Serrano, A. Vespignani, Detecting rich-club ordering in complex networks, Nat. Phys. 2 (2006) 110.
63.Y. Pan, D.-H. Li, J.-G. Liu, J.-Z. Liang, Detecting community structure in complex networks via node similarity, Physica A 389 (2010) 2849.
64.Y.-L. Wang, T. Zhou, J.-J. Shi, J. Wang, D.-R. He, Empirical analysis of dependence between stations in Chinese railway network, Physica A 388 (2009) 2949.
65.T. Zhou, J. Ren, M. Medo, Y.-C. Zhang, Bipartite network projection and personal recommendation, Phys. Rev. E 76 (2007) 046115.
66.L. Katz, A new status index derived from sociometric analysis, Psychmetrika 18 (1953) 39.
67.V.D. Blondel, A. Gajardo, M. Heymans, P. Senellart, P.V. Dooren, A measure of similarity between graph vertices: applications to synonym extraction and web searching, SIAM Rev. 46 (2004) 647.
68.E.H. Moore, On the reciprocal of the general algebraic matrix, Bull. Amer. Math. Soc. 26 (1920) 394.
69.R. Penrose, A generalized inverse for matrices, Proc. Cambridge Philos. Soc. 51 (1955) 406.
70.D.J. Klein, M. Randic, Resistance distance, J. Math. Chem. 12 (1993) 81.
71.F. Fouss, A. Pirotte, J.-M. Renders, M. Saerens, Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation, IEEE Trans. Knowl. Data. Eng. 19 (2007) 355.
72.S. Brin, L. Page, The anatomy of a large-scale hypertextual web search engine, Comput. Netw. ISDN Syst. 30 (1998) 107.
73.H. Tong, C. Faloutsos, J.-Y. Pan, Fast random walk with restart and its applications, in: Proceedings of the 6th International Conference on Data Mining, IEEE Press, Washington, DC, USA, 2006, pp. 613–622.
74.M.-S. Shang, L. Lü, T. Zhou, Y.-C. Zhang, Relevance is more significant than correlation: information filtering on sparse data, Europhys. Lett. 88 (2009) 68008.
75.G. Jeh, J. Widom, SimRank: a measure of structural-context similarity, in: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM Press, New York, 2002, pp. 271–279.
76.P. Chebotarev, E.V. Shamis, The matrix-forest theorem and measuring relations in small social groups, Autom. Remote Control 58 (1997) 1505.
77.F. Fouss, L. Yen, A. Pirotte, M. Saerens, An experimental investigation of graph kernels on a collaborative recommendation task, in: Proceedings of the 6th International Conference on Data Mining, IEEE Press, Washington, DC, USA, 2006, pp. 863–868.
78.L. Lü, C.-H. Jin, T. Zhou, Similarity index based on local paths for link prediction of complex networks, Phys. Rev. E 80 (2009) 046122.
79.W. Liu, L. Lü, Link prediction based on local random walk, Europhys. Lett. 89 (2010) 58007.
80.A. Clauset, C. Moore, M.E.J. Newman, Hierarchical structure and the prediction of missing links in networks, Nature 453 (2008) 98.
81.A. Mantrach, N. van Zeebroeck, P. Francq, M. Shimbo, H. Bersini, M. Saerens, Semi-supervised classification and betweenness computation on large, sparse, directed, networks (unpublished).
82.C. Zhou, L. Zemanová, G. Zamora, C.C. Hilgetag, J. Kurths, Hierarchical organization unveiled by functional connectivity in complex brain networks, Phys. Rev. Lett. 97 (2006) 238103.
83.S. Redner, Teasing out the missing links, Nature 453 (2008) 47.
84.G. Casella, R.L. Berger, Statistical Inference, Duxbury, Belmont, 2001.
85.M.E.J. Newman, G.T. Barkema, Monte Carlo Methods in Statistical Physics, Clarendon, Oxford, 1999.
86.V. Krebs, Mapping networks of terrorist cells, Connections 24 (2002) 43.
87.H.A. Dawah, B.A. Hawkins, M.F. Claridge, Structure of the parasitoid communities of grass-feeding chalcid wasps, J. Anim. Ecol. 64 (1995) 708.
88.M. Huss, P. Holme, Currency and commodity metabolites: their identification and relation to the modularity of metabolic networks, IET Syst. Biol. 1 (2007) 280.
89.E. Mossel, E. Vigoda, Phylogenetic MCMC are misleading on mixtures of trees, Science 309 (2005) 2207.
90.H.C. White, S.A. Boorman, R.L. Breiger, Social structure from multiple networks I: blockmodels of roles and positions, Am. J. Sociol. 81 (1976) 730.
91.P.W. Holland, K.B. Laskey, S. Leinhardt, Stochastic blockmodels: first steps, Soc. Networks 5 (1983) 109.
92.P. Dorelan, V. Batagelj, A. Ferligoj, Generalized Blockmodeling, Cambridge University Press, Cambridge, UK, 2005.
93.E.M. Airoldi, D.M. Blei, S.E. Fienberg, X.P. Xing, Mixed-membership stochastic blockmodels, J. Mach. Learn. Res. 9 (2008) 1981.
94.R. Guimerà, M. Sales-Pardo, L.A.N. Amaral, Classes of complex networks defined by role-to-role connectivity profiles, Nat. Phys. 3 (2007) 63.
95.J. Reichardt, D.R. White, Role models for complex networks, Eur. Phys. J. B 60 (2007) 217.
96.M.E.J. Newman, Assortative mixing in networks, Phys. Rev. Lett. 89 (2002) 208701.
97.M.E.J. Newman, Mixing patterns in networks, Phys. Rev. E 67 (2003) 026126.
98.R. Pastor-Satorras, A. Vázquez, A. Vespignani, Dynamical and correlation properties of the Internet, Phys. Rev. Lett. 87 (2001) 258701.
99.A. Vázquez, R. Pastor-Satorras, A. Vespignani, Large-scale topological and dynamical properties of the Internet, Phys. Rev. E 65 (2002) 066130.
100.T. Bayes, An essay towards solving a problem in the doctrine of chances, Philos. Trans. R. Soc. Lond. 53 (1763) 370.
101.M. Metropolis, A.W. Rosenbluth, A.H. Teller, E. Teller, Equations of state calculation by fast computing machines, J. Chem. Phys. 21 (1953) 1087.
102.W. Zachary, An information flow model for conflict and fission in small groups, J. Anthropol. Res. 33 (1977) 452.
103.D. Lusseau, et al., The bottlenose dolphin community of Doubtful sound features a large proportion of long-lasting associations, Behav. Ecol. Sociobiol. 54 (2003) 396.
104.R. Guimerà, S. Mossa, A. Turtschi, L.A.N. Amaral, The worldwide air transportation network: anomalous centrality, community structure, and cities’ global roles, Proc. Natl. Acad. Sci. USA 102 (2005) 7794.
105.J.G. White, E. Southgate, J.N. Thomson, S. Brenner, The structure of the nervous system of the nematode C. elegans, Philos. Trans. R. Soc. Lond. Ser. B 314 (1986) 1.
106.J.L. Reed, T.D. Vo, C.H. Schilling, B.Ø Palsson, An expanded genome-scale model of Escherichia coli K-12 (iJR904 GSM/GPR), Genome Biol. 4 (2003) R54.
107.N. Friedman, L. Getoor, D. Koller, A. Pfeffer, Learning probabilistic relational models, in: Proceedings of the 16th International Joint Conference on Artificial Intelligence, Stockholm, Sweden, 1999, p. 1300.
108.D. Heckerman, C. Meek, D. Koller, Probabilistic entity-relationship models, PRMS, and plate models, in: Proceedings of the 21st International Conference on Machine Learning, Banff, Canada, 2004, p. 55.
109.K. Yu, W. Chu, S. Yu, V. Tresp, Z. Xu, Stochastic relational models for discriminative link prediction, in: Proceedings of Neural Information Precessing Systems, MIT Press, Cambridge, MA, 2007, pp. 1553–1560.
110.J. Neville, Statistical models and analysis techniques for learning in relational data, Ph.D. Thesis, 2006.
111.D. Heckerman, C. Meek, D. Koller, Probabilistic models for relational data, Tech. Rep. MSR-TR-2004-30, Microsoft Research, 2004.
112.D. Heckerman, D. Geiger, D. Chickering, Learning Bayesian networks: the combination of knowledge and statistical data, Mach. Learn. 20 (1995) 197.
113.B. Taskar, P. Abbeel, D. Koller, Discriminative probabilistic models in relational data, in: Preceedings of the 18th Conference on Uncertainty in Artificial Intelligence, UAI02, Edmonton, Canada, 2002, p. 485.
114.B. Taskar, M.-F. Wong, P. Abbeel, D. Koller, Link prediction in relational data, in: Proceedings of Neural Information Precessing Systems, MIT Press, Cambridge, MA, 2004, p. 659.
115.D. Heckerman, D. Chickering, C. Meek, R. Rounthwaite, C. Kadie, Dependency networks for inference, collaborative filtering, and data visualization, J. Mach. Learn. Res. 1 (2000) 49.
116.J. Neville, D. Jensen, Relational dependency networks, J. Mach. Learn. Res. 8 (2007) 653.
117.G. Casella, E.I. George, Explaining the Gibbs sampler, Amer. Statist. 46 (3) (1992) 167.
118.Z. Xu, V. Tresp, K. Yu, S. Yu, H.-P. Kriegel, Dirichlet enhanced relational learning, in: Proceedings of the 22nd Internatonal Conference on Machine Learning, Bonn, Germany, 2005, p. 1004.
119.W. Buntine, Operations for learning with graphical models, J. Artificial Intelligence Res. 2 (1994) 159.
120.D. Spiegelhalter, Bayesian graphical modeling: a case-study in monitoring health outcomes, Appl. Stat. 47 (1998) 115.
121.K. Yu, W. Chu, Gaussian process models for link analysis and transfer learning, in: Proceedings of Neural Information Precessing Systems, MIT Press, Cambridge, MA, 2007, p. 1657.
122.W. Chu, V. Sindhwani, Z. Ghahramani, S.S. Keerthi, Relational learning with Gaussian processes, in: Proceedings of Neural Information Precessing Systems, MIT Press, Cambridge, MA, 2006, p. 289.
123.J. O’Madadhain, J. Hutchins, P. Smyth, Prediction and ranking algorithms for event-based network data, in: Proceedings of SIGKDD 2005, ACM Press, New York, 2005, p. 23.
124.M.-S. Shang, L. Lü, Y.-C. Zhang, T. Zhou, Empirical analysis of web-based user-object bipartite networks, Europhys. Lett. 90 (2010) 48006.
125.J. Kunegis, E.W. De Luca, S. Albayrak, The link predection problem in bipartite networks. arXiv:1006.5367.
126.T. Zhou, Z. Kuscsik, J.-G. Liu, M. Medo, J.R. Wakeling, Y.-C. Zhang, Solving the apparent diversity-accuracy dilemma of recommender systems, Proc. Natl. Acad. Sci. USA 107 (2010) 4511.
127.W. Zeng, M.-S. Shang, Q.-M. Zhang, L. Lü, T. Zhou, Can dissimilar users contribute to accuracy and diversity of personalized recommendation, Internat. J. Modern Phys. C 21 (2010) 1217.
128.Q.-M. Zhang, M.-S. Shang, W. Zeng, Y. Chen, L. Lü, Empirical comparison of local structural similarity indices for collaborative-filtering-based recommender systems, Physics Procedia 3 (2010) 1887.
129.J. Schafer, J. Konstan, J. Riedl, E-commerce recommendation applications, Data Min. Knowl. Discov. 5 (2001) 115.
130.Z. Huang, D.D. Zeng, A link prediction approach to anomalous email detection, in: Proceedings of 2006 IEEE International Conference on Systems, Man, and Cybernetics, Taipei, Taiwan, 2006, p. 1131.
131.B. Gallagher, H. Tong, T. Eliassi-Rad, C. Faloutsos, Using ghost edges for classification in sparsely labeled networks, in: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM Press, New York, 2008, p. 256.
132.K. Dasgupta, R. Singh, B. Viswanathan, D. Chakraborty, S. Mukherjea, A.A. Nanavati, A. Joshi, Social ties and their relevance to churn in mobile telecom networks, in: Proceedings of the 11th International Conference on Extending Database Technology: Advances in Database Technology, ACM Press, New York, 2008, p. 668.
133.M.E.J. Newman, M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E 69 (2004) 026113.
134.R. Guimerà, A. Díaz-Guilera, F. Vega-Redondo, A. Cabrales, A. Arenas, Optimal network topologies for local search with congestion, Phys. Rev. Lett. 89 (2002) 248701.
135.G. Yan, T. Zhou, B. Hu, Z.-Q. Fu, B.-H. Wang, Efficient routing on complex networks, Phys. Rev. E 73 (2006) 046108.
136.M. Barahona, L.M. Pecora, Synchronization in small-world systems, Phys. Rev. Lett. 89 (2002) 054101.
137.A. Arenas, A. Díza-Guilera, J. Kurths, Y. Moreno, C. Zhou, Phys. Rep. 469 (2008) 93.
138.R. Pastor-Satorras, A. Vespignani, Epidemics and immunization in scale-free networks, in: S. Bornholdt, H.G. Schuster (Eds.), Handbook of Graphs and Networks, Wiley-VCH, Berlin, 2003.
139.T. Zhou, Z.-Q. Fu, B.-H. Wang, Epidemic dynamics on complex networks, Prog. Nat. Sci. 16 (2006) 452.
140.G. Caldarelli, A. Capocci, P. De Los Rios, M.A. Muñoz, Scale-free networks from varying vertex intrinsic fitness, Phys. Rev. Lett. 89 (2002) 258702.
141.S. Valverde, R.F. Cancho, R.V. Solé, Scale-free networks from optimal design, Europhys. Lett. 60 (2002) 512.
142.M. Baiesi, S.S. Manna, Scale-free networks from a Hamiltonian dynamics, Phys. Rev. E 68 (2003) 047103.
143.B.J. Kim, A. Trusina, P. Minnhagen, K. Sneppen, Self organized scale-free networks from merging and regeneration, Eur. Phys. J. B 43 (2005) 369.
144.J.I. Perotti, O.V. Billoni, F.A. Tamarit, D.R. Chialvo, S.A. Cannas, Emergent self-organized complex network topology out of stability constraints, Phys. Rev. Lett. 103 (2009) 108701.
145.G. Bianconi, P. Pin, M. Marsili, Assessing the relevance of node features for network structure, Proc. Natl. Acad. Sci. USA 106 (2009) 11433.
146.H.-K. Liu, T. Zhou, Review on the studies of airline networks, Prog. Nat. Sci. 18 (2008) 601.
147.A.-X. Cui, Y. Fu, M.-S. Shang, D.-B. Chen, T. Zhou, Emergence of local structures in complex network: common neighborhood drives the network evolution, Acta Phys. Sinica 60 (2011) 30.
148.W.-K. Xiao, J. Ren, F. Qi, Z.-W. Song, M.-X. Zhu, H.-F. Yang, H.-Y. Jin, B.-H. Wang, T. Zhou, Emprical study on clique-degree distribution of networks, Phys. Rev. E 76 (2007) 037102.
149.R. Lambiotte, V.D. Blondel, C. de Kerchove, E. Huens, C. Prieur, Z. Smoreda, P. Van Dooren, Geographical dispersal of mobile communication networks, Physica A 387 (2008) 5317.
150.W.-S. Jung, F. Wang, H.E. Stanley, Gravity model in the Korean highway, Europhys. Lett. 81 (2008) 48005.
151.P. Kaluza, A. Koelzsch, M.T. Gastner, B. Blasius, The complex network of global cargo ship movements, J. R. Soc. Interface 7 (2010) 1093.
152.H.-K. Liu, X.-L. Zhang, L. Cao, B.-H. Wang, T. Zhou, Analysis on the connecting mechanism of Chinese city airline network, Sci. China Ser. G 39 (2009) 935.
153.C.W.J. Granger, Investigating causal relations by econometric models and cross-spectral methods, Econometrica 37 (1969) 424.
154.H.-K. Liu, X.-L. Zhang, T. Zhou, Structure and external factors of Chinese city airline network, Physics Procedia 3 (2010) 1781.
155.Q.-M. Zhang, M.-S. Shang, L. Lü, Similarity-based classification in partially labeled networks, Internat. J. Modern Phys. C 21 (2010) 813.
156.U. Alon, Network motifs: theory and experimental approaches, Nat. Rev. Genet. 8 (2007) 450.
157.A. Mantrach, L. Yen, J. Callut, K. Françoisse, M. Shimbo, M. Saerens, The sum-over-paths covariance kernel: a novel covariance measure between nodes of a directed graph, IEEE Trans. Pattern Anal. Mach. Intell. 32 (2010) 1112.
158.T. Murata, S. Moriyasu, Link prediction of social networks based on weighted proximity measure, in: Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence, ACM Press, New York, 2007.
159.L. Lü, T. Zhou, Link prediction in weighted networks: the role of weak ties, Europhys. Lett. 89 (2010) 18001.
160.H. Yin, S.C. Wong, J. Xu, C.K. Wong, Urban traffic flow prediction using a fuzzy-neural approach, Transp. Res. C 10 (2002) 85.
161.J. Kunegis, A. Lommatzsch, C. Bauckhage, The slashdot zoo: mining a social network with negative edges, in: Proceedings of WWW’2009, ACM Press, New York, 2009.
162.R.V. Guha, R. Kumar, P. Raghavan, A. Tomkins, Propagation of trust and distrust, in: Proceedings of WWW’2004, ACM Press, New York, 2004.
163.J. Leskovec, D. Huttenlocher, J. Kleinberg, Predicting positive and negative links in online social networks, in: Proceedings of WWW’2010, ACM Press, New York, 2010.
164.V.A. Traag, J. Bruggeman, Community detection in networks with positive and negative links, Phys. Rev. E 80 (2009) 036115.
165.S.A. Marvel, S.H. Strogatz, J.M. Kleinberg, Energy landscape of social balance, Phys. Rev. Lett. 103 (2009) 198701.
166.M. Szell, R. Lambiotte, S. Thurner, Multirelational organization of large-scale social networks in an online world, Proc. Natl. Acad. Sci. USA 107 (2010) 13636.
167.Z.-K. Zhang, T. Zhou, Y.-C. Zhang, Personalized recommendation via integrated diffusion on user–item–tag tripartite graphs, Physica A 389 (2010) 179.
168.Z.-K. Zhang, C. Liu, Y.-C. Zhang, T. Zhou, Solving the cold-start problem in recommender systems with social tags, Europhys. Lett. 92 (2010) 28002.
169.R. Burke, Hybrid recommender systems: survey and experiments, User Model. User-Adapt. Interact. 12 (2002) 331.
170.R. Polikar, Ensemble based systems in decision making, IEEE Circuits Syst. Mag. 6 (3) (2006) 21.
171.V. Leroy, B.B. Cambazoglu, F. Bonchi, Cold start link prediction, in: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM Press, New York, 2010, p. 393.
172.E. Zheleva, L. Getoor, J. Golbeck, Ugur Kuter, Using friendship ties and family circles for link prediction, in: Proceedings of the 2nd Workshop on Social Network Mining and Analysis, ACM Press, New York, 2008.
173.B. Cao, N.N. Liu, Q. Yang, Transfer learning for collective link prediction in multiple heterogenous domains, in: Proceedings of the 27th International Conference on Machine Learning, Haifa, Israel, 2010.
174.Z. Huang, D.K.J. Lin, The time-series link prediction problem with applications in communication surveillance, INFORMS J. Comput. 21 (2009) 286.
175.T. Tylenda, R. Angelova, S. Bedathur, Towards time-aware link prediction in evolving social networks, in: Proceedings of the 3rd Workshop on Social Network Mining and Analysis, ACM Press, New York, 2009.

Citation

MLA

Lü, L., and T. Zhou. “Link Prediction in Complex Networks: A Survey”. Physica A: Statistical Mechanics and Its Applications, vol. 390, no. 6, 2011, pp. 1150–70, https://doi.org/10.1016/j.physa.2010.11.027.

APA

Lü, L., & Zhou, T. (2011). Link prediction in complex networks: A survey. Physica A: Statistical Mechanics and Its Applications, 390(6), 1150–1170. https://doi.org/10.1016/j.physa.2010.11.027

Chicago

Lü, L., and T. Zhou. 2011. “Link Prediction in Complex Networks: A Survey”. Physica A: Statistical Mechanics and Its Applications 390 (6): 1150–70. https://doi.org/10.1016/j.physa.2010.11.027.

Harvard

Lü, L. and Zhou, T. (2011) “Link prediction in complex networks: A survey”, Physica A: Statistical Mechanics and its Applications, 390(6), pp. 1150–1170. Available at: https://doi.org/10.1016/j.physa.2010.11.027.

Vancouver

1. Lü L, Zhou T (2011) Link prediction in complex networks: A survey. Physica A: Statistical Mechanics and its Applications 390:1150–1170

BibTeX

@article{L__2011, title={Link prediction in complex networks: A survey}, volume={390}, ISSN={0378-4371}, url={http://dx.doi.org/10.1016/j.physa.2010.11.027}, DOI={10.1016/j.physa.2010.11.027}, number={6}, journal={Physica A: Statistical Mechanics and its Applications}, publisher={Elsevier BV}, author={Lü, Linyuan and Zhou, Tao}, year={2011}, month=Mar, pages={1150–1170} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

Link Prediction in Complex Networks: A Survey

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Problem Formulation and Standard Evaluation Metrics for Link Prediction

Knowl 2 — Local Node Similarity Indices

Knowl 3 — Global Node Similarity Indices

Knowl 4 — Quasi-Local Similarity Indices for Link Prediction

Knowl 5 — Empirical Accuracy Comparison of Local Similarity Indices

Knowl 6 — Empirical Comparison of Local, Global, Quasi-Local, and Maximum Likelihood Methods

Knowl 7 — Hierarchical Structure Model for Link Prediction

Knowl 8 — Stochastic Block Model and Bayesian Link Reliability

Knowl 9 — Network Reconstruction Algorithm Based on Link Reliability Swapping

Knowl 10 — Evaluating Network Evolving Mechanisms via Link Prediction Accuracy

Knowl 11 — Semi-Supervised Node Classification in Partially Labeled Networks via Link Proximity

Knowl 12 — Probabilistic and Relational Models for Link Prediction

References

Citation

BibTeX

Access the Paper