PaperlayerView exact revision on arXiv

Source-linked AI summary

Link Prediction in Social Networks: the State-of-the-Art

Peng Wang, Baowen Xu, Yurong Wu, Xiaoyu Zhou

arXiv:1411.5118v2cs.SIphysics.soc-ph

TL;DR

Link prediction addresses incomplete and evolving social networks by forecasting missing, added, or deleted links. This paper systematically surveys prediction techniques, problems, applications, and research groups, concluding with future challenges and directions.

  • Problem

    Social-network data are incomplete and dynamic, creating a need to predict missing current links and added or deleted future links.

  • Method

    The paper provides a systematic survey organized around link-prediction techniques and problems, covering metrics, learning methods, applications, research groups, and challenges.

  • Results

    The survey categorizes and discusses classical and emerging techniques, link-prediction problems, applications, active research groups, and future challenges.

  • Takeaways & Limitations

    Link prediction is presented as a broad social-network analysis task spanning topology-based, learning-based, probabilistic, heterogeneous, dynamic, and reciprocal-relationship settings.

  • Takeaways & Limitations

    SimRank has worst-case computation complexity O(n4), limiting its use for large-scale networks.

Abstract

from arXiv · show

In social networks, link prediction predicts missing links in current networks and new or dissolution links in future networks, is important for mining and analyzing the evolution of social networks. In the past decade, many works have been done about the link prediction in social networks. The goal of this paper is to comprehensively review, analyze and discuss the state-of-the-art of the link prediction in social networks. A systematical category for link prediction techniques and problems is presented. Then link prediction techniques and problems are analyzed and discussed. Typical applications of link prediction are also addressed. Achievements and roadmaps of some active research groups are introduced. Finally, some future challenges of the link prediction in social networks are discussed.

1 Introduction

Social networks are graph-structured but difficult to mine because collected data are incomplete and networks evolve dynamically. This paper surveys link prediction systematically, covering techniques, problems, applications, research groups, and future challenges.

  • Motivation: Social networks represent actors as nodes and their ties or interactions as edges, but collected data are often incomplete and networks change over time.These properties make mining and analyzing social-network data non-trivial.
  • Motivation: Link prediction seeks missing or unobserved links in current networks and newly added or deleted links in future networks.It supports both network completion and understanding network evolution.
  • Applications: Link prediction has applications in recommender systems, including finding friends, collaborators, experts, co-authors, and interesting shopping items.The cited examples span information retrieval, e-commerce, enterprise, academic, and other social networks.
  • Research landscape: Research on link prediction has grown substantially, with thousands of related papers appearing annually in recent years across ACM, IEEE, and Elsevier libraries.The paper selects about 130 studies published from 2000 to 2013, emphasizing prominent journals and conferences.
  • Paper scope: Existing surveys left coverage gaps, motivating this paper’s comprehensive and systematic review of techniques, problems, applications, and active research groups.The paper also discusses formal definitions, solution frameworks, evaluation metrics, and future directions.

2 Problem Statement

Link prediction estimates links that may appear or disappear over time and missing links in current social networks. The paper organizes solutions by techniques and problems, with similarity and learning approaches forming a generic framework.

  • Problem definition: Link prediction targets new, deleted, missing, or unobserved links between node pairs across current and future social networks.The formulation considers a network G(V, E) at time t and predicts link changes at a later time t′ > t.
  • Problem definition: The task determines formation or dissolution possibilities for all node pairs using similarities or relative ranks.
  • Generic framework: Similarity-based methods score non-connected node pairs by proximity, with higher scores indicating higher likelihood of new, missing, or unobserved links.
  • Category: The proposed category separates link prediction techniques from link prediction problems and treats applications independently because they use techniques and problems.
  • Evaluation: Evaluation uses fixed-threshold metrics such as top-N precision and recall, or threshold curves including ROC, precision-recall, and AUC.AUC is described as robust under imbalance and as the probability that a missing link outranks a nonexistent link.

3 Link Prediction Techniques

Link prediction methods range from simple metrics based on network information to more complex learning-based approaches. Learning methods build on basic-metric features and external information.

  • Basic metrics: Basic link prediction metrics calculate node-pair similarities using node information, topology, and social theory.
  • Learning-based methods: Learning-based methods are more complex than generic metrics and use features supplied by basic metrics together with external information.
  • Review scope: The paper presents a systematic review of link prediction metrics and methods.

3.1 Node-based Metrics

Node-based metrics use attributes and actions to estimate similarity between node pairs. They are useful when social-network user attributes and actions can be obtained.

  • Similarity principle: Node-based link prediction computes similarity between non-connected nodes, based on the idea that more similar pairs are more likely to link.
  • Node attributes: Node attributes such as online profiles, email names, and publication records can be used directly, often with text-based or string-based similarity metrics.
  • Examples: Profile-based approaches include keyword categorization, inferred missing profile values from mutual friends, and cosine similarity between users’ action vectors.The cited studies use keyword distances, majority voting, and action overlap represented as vectors.
  • Incomplete profiles: Most user profiles may be incomplete, motivating inference of missing values before similarity computation.One approach uses mutual-friend profile information and majority voting to infer part of a stranger’s profile.
  • Scope: Node-based metrics are useful when user attributes and actions are available because they reflect personal interests and social behaviors.

3.2 Topology-based Metrics

Topology-based metrics predict links from node neighborhoods, shared neighbors, paths, and random-walk structure. Their normalization, computational cost, and sensitivity to network characteristics shape practical metric selection.

  • Overview: Topology-based metrics compute node-pair similarity from graph structure, including neighborhoods, common neighbors, and paths.They are used even when networks lack node or edge attributes.
  • Neighbor-based Metrics: Parameter-Dependent (PD) interpolates among established metrics: λ = 0 gives CN, λ = 0.5 gives Salton, and λ = 1 gives LHN.PD is proposed to improve prediction for both popular and unpopular links.
  • Neighbor-based Metrics: Resource Allocation (RA) suppresses high-degree common neighbors more strongly than AA and performs better on networks with high average degrees.AA and RA have close results on networks with small average degrees.
  • Neighbor-based Metrics: Neighbor-based metrics differ in normalization, degree sensitivity, and computational complexity, so their scores are not universally interchangeable.CN, AA, PA, and RA are unnormalized; several intersection-based metrics require O(n^2), while PA requires O(2n).
  • Practical Selection: No neighbor-based metric dominates across datasets, so practical selection should follow the characteristics of the target social network.The comparison of normalization, complexity, and characteristics is intended to support suitable metric choice.
  • Path-based and Random Walk Metrics: Path-based metrics incorporate global path information, but longer paths are not always more useful and can increase computational cost.FriendLink reports degraded precision for higher path lengths, while SimRank has worst-case complexity O(n^4).
  • Random Walk-based Metrics: PropFlow uses a modified breadth-first search restricted to height l, avoiding walk restarts and convergence and making it faster than rooted PageRank and SimRank.Its pipeline sums PropFlow over shortest paths when nodes are indirectly linked.

3.3 Social Theory based Metrics

Social-theory-based metrics augment node and topology information with community, weak-tie, centrality, behavior, homophily, and balance information. The reviewed studies report improved prediction when these social signals capture interaction patterns or network growth.

  • Social Theory-based Metrics: Social-theory-based metrics incorporate community, triadic closure, ties, homophily, and structural balance beyond node and topology information.These theories are used to capture additional social interaction information, particularly in large-scale networks.
  • Community and Interest: Combining topology with community information, user interests, and behaviors efficiently improves link prediction in directed and asymmetric large-scale Twitter networks.The approach predicts future links using both structural and social information.
  • Weak Ties and Centrality: A weak-tie model weights common neighbors using degree, closeness, and betweenness centrality, with β controlling how centrality contributions are adjusted.For β > 1, larger centralities receive greater emphasis; for β < 0, larger centralities are restrained more strongly.
  • Centrality: Maximal-entropy-random-walk methods capture node centrality and outperform older methods without centrality.The underlying observation is that nodes prefer links not only to similar nodes but also to central nodes.
  • Behavior Evolution: Behavior-evolution-aware, event-driven locality and attachedness models characterize network growth and use node behavior to improve link prediction accuracy.The models also simulate important structures observed in real networks.
  • Homophily and Network Patterns: Homophily, degree distribution, social balance, and microscopic mechanisms provide signals for predicting links and identifying patterns across different social networks.Homophily is applied to links involving users, services, and users with common interests.

3.4 Learning-based Methods

Learning-based link prediction methods use network, node, social, and domain-specific features within classification, probabilistic graph, or matrix-factorization frameworks. These methods can improve prediction accuracy, but feature construction and computational cost remain central concerns.

  • Learning-based methods use previous link-prediction metrics, internal attributes, and external information, and include classification, probabilistic graph, and matrix-factorization approaches.
  • 3.4.1 Feature-based Classification: Feature extraction is crucial, combining node-based, topology-based, social-theory, and domain-specific attributes to improve classification.Examples include user demographics, interests, locations, and bibliographic semantics.
  • Specialized approaches address auxiliary networks, multi-relational links, hierarchical structure, signed networks, heterogeneous tasks, and evolving network structure.These include path-based features, link propagation, hierarchical random graphs, social-imbalance features, transfer learning, and Markov evolution models.
  • 3.4.1 Feature-based Classification: Supervised learning generally improves prediction performance, especially precision, while increasing feature-selection and model-training costs.
  • Link-prediction models can identify missing or spurious links, but some hierarchical approaches require substantial computation and cannot capture overlapping or hierarchical structure adequately.
  • 3.4.2 Probabilistic Graph Model: Probabilistic graph models usually modify established models such as random walks and factor graphs, improving accuracy over basic topology-based metrics.Some exploit global network information and scale to large networks, while others target hierarchical or incomplete networks.

3.5 Datasets and Tools

Open datasets and tools support reproducible comparison of link-prediction methods, but existing datasets are noisy, insufficiently diverse, and inconsistent across evaluations. Greater standardization and maintenance are therefore needed.

  • Datasets enable fair reproduction and comparison of link-prediction methods, but collecting and constructing them is time-consuming and not all are publicly available.
  • Existing datasets may contain noise, lack diversity in size and network type, and be unavailable for new or specialized link-prediction problems.Bibliographic networks, for example, face author-name disambiguation issues.
  • Performance rankings can vary substantially across datasets, limiting reliable analysis of method strengths and weaknesses and potentially causing method misuse.
  • Few methods release source code, forcing researchers to reimplement complex techniques and increasing evaluation effort.
  • An open API built around benchmark datasets, standardized outputs, and automatic evaluation could reduce repeated implementation and comparison work.

4 Link Prediction Problems

Link prediction problems extend beyond static missing-link inference to temporal evolution, heterogeneous relations, link activity, and link dissolution. The surveyed methods incorporate time, network structure, relation types, and evolving link strength to address these settings.

  • Six special problem categories include temporal, active/unactive, bipartite, heterogeneous, unfollow or disappearing links, and scalability prediction.
  • Temporal Link Prediction: Temporal link prediction represents evolving networks across time and predicts links at a later time, such as which researchers may publish together next year.A time-indexed network can be organized as a third-order tensor.
  • Temporal Link Prediction: Matrix- and tensor-based methods collapse temporal data, optionally weighting recent slices, or factorize tensors to extract temporal patterns for prediction.The collapsed weighted tensor gives greater weight to more recent links, while CP-based methods support heuristic and forecasting-based prediction.
  • Temporal Link Prediction: Temporal methods model interaction timing through time scores, triad-transition probabilities, event updates, and time-series forecasting, but time-score effectiveness depends on network and parameter settings.Time scores use recency and interaction gaps, whereas event-based scores reward formed or preserved links and penalize disconnected pairs.
  • Link Prediction in Heterogeneous Networks: Heterogeneous link prediction distinguishes relation types through multi-relational weighting schemes based on triad patterns and edge-type closure probabilities.
  • Link Prediction for Unfollow or Disappearing Links: Younger links are more informative than older links for predicting new link formation, and older links may be removed when studying network evolution.
  • Link Prediction for Unfollow or Disappearing Links: Link dissolution receives less attention than link formation despite both being fundamental processes of dynamic network evolution.

5 Link Prediction Applications

Link prediction supports recommendation, network completion, collaboration discovery, and social-tie analysis. Applications combine structural, content, temporal, and relational information to infer useful or missing connections.

  • Typical applications include recommendation in social networks, network completion, and social-tie prediction.
  • Recommendation in Social Network: Recommendation systems predict partners, friends, followees, and followers using factor graphs, network structure, user content, location, and learned friendship patterns.
  • Reciprocal Relationship Prediction: A semi-supervised Triad Factor Graph model accurately inferred 90% of reciprocal relationships in a large Twitter network.The framework incorporates social theories and provides evidence of structural balance among reciprocal relationships.
  • Network Completion: Network completion infers missing nodes and edges from the observed portion of an incomplete social network using an Expectation Maximization framework.
  • Social Ties Prediction: Academic-network applications build collaboration predictors from structural attributes, while cross-domain collaboration prediction addresses rare relationships and differing expertise patterns.
  • Social Ties Prediction: PathPredict predicts co-author relationships in heterogeneous bibliographic networks by extracting meta-path features and learning their weights with a supervised model.
  • Social Ties Prediction: Social-tie strength models quantify evolving relationships from communication records and reciprocity, extending related findings toward link prediction.

6 Active Research Groups

Active research groups have advanced link prediction through supervised walks, triad-based reciprocal modeling, temporal latent spaces, heterogeneous-network flow methods, and topology-based metrics. Their work also addresses bias, weak ties, attributes, semantics, and scalability.

  • Supervised random walks combine network structure with node and edge features to favor destinations likely to receive future links.
  • Hopcroft and Tang’s team predicts reciprocal relationships with Triad Factor Graphs incorporating structural balance and homophily into semi-supervised learning.
  • Kashima et al. model network evolution with a copy-and-paste mechanism and extend prediction across time frames through low-dimensional latent features.
  • Lichtenwalter et al. developed localized PropFlow and a probabilistically weighted Adamic-Adar extension for heterogeneous networks.
  • UESTC researchers proposed topology-based RA and LP metrics, with LP using next-nearest-neighbor information and remaining efficient for large networks.
  • Local Naive Bayes assigns different predictive roles to common neighbors, allowing equal-count node pairs to receive different connection likelihoods.
  • Experiments found weak ties significantly improve prediction accuracy, while weighted similarity measures performed worse and most studies remained static.
  • A biased probe-set construction favoring less-popular missing links made LHN perform best and motivated a parameter-dependent metric that can reduce to CN, SI, or LHN.

7 Future Directions and Challenges

The paper identifies future challenges spanning link-dissolution mechanisms, changing network membership, data imbalance, theory integration, heterogeneous networks, and fair evaluation. These challenges reflect practical departures from assumptions and datasets underlying many existing methods.

  • Disappearing link prediction: Disappearing-link prediction requires modeling dissolution mechanisms because link disappearance is not simply the inverse of link formation.Methods based only on low similarity cannot be directly reused for predicting disappearing links.
  • Link prediction under dynamic nodes: Dynamic-node prediction must account for users joining or leaving networks, including inactive users and fake users whose activity resembles that of real users.Inactive users should not be treated as future participants, while malicious fake users can negatively influence prediction.
  • Overcoming imbalance: Extreme class imbalance and sparse datasets make model construction, evaluation, and prediction-confidence quantification difficult.The number of observed links is often far smaller than the number of absent links, and sparse data produce small prior link probabilities.
  • Incorporating social theories: Future methods should incorporate social theories rather than relying mainly on topology and attributes, because theories can explain mechanisms of social activity.The paper characterizes many existing approaches as traditional data-mining or learning solutions independent of social-network theory.
  • Link prediction in heterogeneous social networks: Link prediction must extend beyond homogeneous graphs to heterogeneous networks with multiple node and relation types, including links across networks.Examples include bibliographic networks containing publications, authors, venues, and relations such as co-authorship, citation, and work affiliation.
  • Fair evaluation and benchmark datasets: Fair comparison requires stronger evaluation practices and benchmark datasets because dataset variation and selective reporting can obscure method limitations.Existing datasets differ substantially in network size and features, so a model may perform well on some datasets but poorly on others.

8 Conclusions

The paper systematically organizes research on social-network link prediction and reviews its methods, problems, applications, and research communities. It emphasizes topology-based metrics and learning-based methods while identifying future directions.

  • Contributions: The paper proposes a systematic category for link-prediction techniques and problems in social networks.It aims to summarize typical research across the field.
  • Coverage: It discusses topology-based metrics and learning-based methods, along with link-prediction problems and applications.The review covers multiple methodological and application-oriented aspects of the topic.
  • Future directions: The paper introduces active research groups and presents future directions and challenges for social-network link prediction.These components extend the review beyond methods to research activity and open problems.
Loading 1411.5118v2…