Link Prediction

Link Prediction

1. What

   • Predict likelihood of a future association between two nodes
   • Inferring missing links

2. Link Prediction Context

   • Network
     • LP in Heterogeneous network
     • LP in Cross Network
     • LP in Temporal network
     • LP in Bipartite network
     • LP in Weighted Network
       • what
   • Link
     • LP for Multi-relation links
     • LP for Active/Unactive links
     • LP for Disappearing links
     • LP for Multi-Directed Links

3. How?

   • Approaches
     • Similarity-based
       • Local methods
         • JC
         • AA
         • RA
         • HPI
         • latest
           • CAR
           • CCLP
           • CA
       • Global methods
         • LHN2
       • Quasi-local methods
         • Local RW
         • Superposed RW
     • Probabilistic & Statistical
       • They build a model that fits the structure and estimate model parameters using statistical methods
       • Hierarchical Structure model
       • Stochastic Block model
       • Cycle Formation model
       • Local Co-Occurrence model
     • Algorithmic
       • Classifier-based methods
       • Metaheuristic-based methods
       • Factorization-based methods
     • Preprocessing
       • optimized methods
       • Low-Rank Approximation
       • Unseen Bigram
       • Filtering (or clustering)
     • Topological Structure
       • Similarity based
       • Maximum Likelihood Estimation based
         • methods can discover the hidden structures of networks
         • Hierarchical Structure model
         • Stochastic Block model
   • Structure/Techniques
     • Non-Learning based
       • Node Features
         • Node similarity
         • Text similarity
       • Topology Features
         • Neighbor
           • CN
           • JC
           • AA
           • LHN
           • PA
           • RA
         • Path
           • Katz, LP, RSS, Friend Link, VCP
         • Random Walk
           • SimRank, PropFlow, RPR, HT, CT, CST
           • Superposed Random Walk,
           • LHN2
       • Social Theory Features
         • Community
         • Triad
         • Structural Hole
         • Tie Strength
         • Homophily
     • Learning based
       • Feature-based classification
       • Kernel-based
       • Matrix factorization
       • Probabilistic model

4. Where?

   • Bioinformatics
     • used to find interactions between proteins
   • e-commerce
     • help build recommendation system of product
   • Security Domain
     • identifying hidden groups of terrorists or criminals
   • Co-authorship networks
     • used to accelerate a mutually beneficial professional or academic connection/collaborations that would have taken longer to form serendipitously
   • Social Networks

5. Cast to

   • Anomaly Detection
   • Recommender System
   • Network Allignment
   • Information Diffusion
   • Community Detection
   • Influence Analysis