The Link Prediction Problem in Social Networks
by Lucas Dohmen
A seminar paper providing an overview on algorithms, use-cases and research oppurtunities.
In a social network there can be many different kind of links or edges between the nodes. Those could for example be social contacts, hyper-references or phone-calls. When social networks are analyzed, there are certain information about the linkage between the nodes that are not known or not known at a given point of time: Link Prediction is the problem of detecting edges that either don't yet exist at the given time t or exist, but have not been discovered or tracked.
This seminar paper will provide an overview of important algorithms for that problem, they will be presented and compared to each other. Furthermore the analyzed papers feature test runs on huge data sets that will be reviewed and compared.
Structure
- The Link Prediction Problem
- Usecases
- Algorithm Classifications
- Node Neighborhood
- Common Neighbors
- Preferential Attachment
- Jaccard’s coefficient and Adamic/Adar
- Weighted Alternatives
- Comparison
- Path Based Algorithms
- Katz
- SimRank
- Hitting Time
- PageRank
- PropFlow
- Supervised Random Walks
- Comparison
- Meta Approaches
- Low-rank approximation
- Unseen bigrams
- Clustering
- Comparison
- Bayesian Probabilistic Models
- Getoor et. al
- Kashima/Abe
- Comparison
- Linear Algebraic Method
- Other Algorithms
- Comparison, Conclusion, Future Research Opportunities
Feedback
- Paper: Excellent review paper. All methods are there. Clear classification of approaches. Formulas are presented and explained in detail. The comparison is very good with suggestions for further research.
- Presentation: Excellent presentation, but many, many slides, good discussion
- Final Grade: 1,0
License
Copyright by Lucas Dohmen
Author
Lucas Dohmen (moonglum@moonbeamlabs.com)
Download
You can download it in PDF Format.