Graph Edge Prediction Algorithm: Difference between revisions
Jump to navigation
Jump to search
m (Text replacement - "** ..." to "** …") |
m (Text replacement - ". " to ". ") |
||
| Line 17: | Line 17: | ||
=== 2011 === | === 2011 === | ||
* ([[2011_LinkPredictioninComplexNetworks|Lü & Zhou, 2011]]) ⇒ [[Linyuan Lü]], and [[Tao Zhou]]. ([[2011]]). “[http://www.linkprediction.org/resource/pdf/%282010physica%20A%29Link%20prediction%20in%20complex%20networks-A%20survey.pdf Link Prediction in Complex Networks: A Survey].” In: Physica A: Statistical Mechanics and its Applications, 390(6). | * ([[2011_LinkPredictioninComplexNetworks|Lü & Zhou, 2011]]) ⇒ [[Linyuan Lü]], and [[Tao Zhou]]. ([[2011]]). “[http://www.linkprediction.org/resource/pdf/%282010physica%20A%29Link%20prediction%20in%20complex%20networks-A%20survey.pdf Link Prediction in Complex Networks: A Survey].” In: Physica A: Statistical Mechanics and its Applications, 390(6). | ||
** QUOTE: The [[Graph Edge Prediction Algorithm|algorithm]]s can be used to [[extract missing information]], [[identify spurious interactions]], [[evaluate network evolving mechanisms]], and so on. </s> [[This article]] summaries recent progress about [[Graph Edge Prediction Algorithm|link prediction algorithm]]s, emphasizing on the contributions from [[physical perspective]]s and [[supervised classification algorithm|approach]]es, such as the [[random-walk-based method]]s and the [[maximum likelihood method]]s. </s> … Finally, [[we]] introduce some applications and outline future challenges of [[Graph Edge Prediction Algorithm|link prediction algorithm]]s. </s> | ** QUOTE: The [[Graph Edge Prediction Algorithm|algorithm]]s can be used to [[extract missing information]], [[identify spurious interactions]], [[evaluate network evolving mechanisms]], and so on. </s> [[This article]] summaries recent progress about [[Graph Edge Prediction Algorithm|link prediction algorithm]]s, emphasizing on the contributions from [[physical perspective]]s and [[supervised classification algorithm|approach]]es, such as the [[random-walk-based method]]s and the [[maximum likelihood method]]s. </s> … Finally, [[we]] introduce some applications and outline future challenges of [[Graph Edge Prediction Algorithm|link prediction algorithm]]s. </s> | ||
| Line 25: | Line 25: | ||
=== 2006 === | === 2006 === | ||
* ([[2006_LinkPredictionUsignSupervisedLearning|Al Hasan et al., 2006]]) ⇒ [[Mohammad Al Hasan]], Vineet Chaoji, Saeed Salem, and [[Mohammed Zaki]]. ([[2006]]). “[http://www.cs.rpiscrews.us/~zaki/PS/LINK06.pdf Link Prediction Using Supervised Learning].” In: SDM’06: Workshop on Link Analysis, Counter-terrorism and Security. | * ([[2006_LinkPredictionUsignSupervisedLearning|Al Hasan et al., 2006]]) ⇒ [[Mohammad Al Hasan]], Vineet Chaoji, Saeed Salem, and [[Mohammed Zaki]]. ([[2006]]). “[http://www.cs.rpiscrews.us/~zaki/PS/LINK06.pdf Link Prediction Using Supervised Learning].” In: SDM’06: Workshop on Link Analysis, Counter-terrorism and Security. | ||
** [[Social Network Link Prediction Task|Link prediction in a social network]] is an important [[problem]] and it is very helpful in analyzing and understanding [[Community|social groups]]. | ** [[Social Network Link Prediction Task|Link prediction in a social network]] is an important [[problem]] and it is very helpful in analyzing and understanding [[Community|social groups]]. | ||
=== 2003 === | === 2003 === | ||
* ([[2003_TheLinkPredictionProblemforSoci|Liben-Nowell & Kleinberg. 2003]]) ⇒ David Liben-Nowell, and [[Jon Kleinberg]]. ([[2003]]). “[http://cs.carleton.edu/faculty/dlibenno/papers/link-prediction/link.pdf The Link Prediction Problem for Social Networks].” In: Proceedings of the twelfth International Conference on Information and knowledge management (CIKM 2003). [http://dx.doi.org/10.1145/956863.956972 doi:10.1145/956863.956972] | * ([[2003_TheLinkPredictionProblemforSoci|Liben-Nowell & Kleinberg. 2003]]) ⇒ David Liben-Nowell, and [[Jon Kleinberg]]. ([[2003]]). “[http://cs.carleton.edu/faculty/dlibenno/papers/link-prediction/link.pdf The Link Prediction Problem for Social Networks].” In: Proceedings of the twelfth International Conference on Information and knowledge management (CIKM 2003). [http://dx.doi.org/10.1145/956863.956972 doi:10.1145/956863.956972] | ||
* ([[2003_FriendsAndNeighbors|Adamic & Adar, 2003]]) ⇒ [[Lada A. Adamic]], and [[Eytan Adar]]. ([[2003]]). “[http://www.cond.org/fnn.pdf Friends and Neighbors on the Web].” In: [[Social Networks]], 25(3). [http://dx.doi.org/10.1016/S0378-8733(03)00009-1 doi:10.1016/S0378-8733(03)00009-1] | * ([[2003_FriendsAndNeighbors|Adamic & Adar, 2003]]) ⇒ [[Lada A. Adamic]], and [[Eytan Adar]]. ([[2003]]). “[http://www.cond.org/fnn.pdf Friends and Neighbors on the Web].” In: [[Social Networks]], 25(3). [http://dx.doi.org/10.1016/S0378-8733(03)00009-1 doi:10.1016/S0378-8733(03)00009-1] | ||
** QUOTE: … If we are trying to [[evaluate]] the [[likelihood]] that [[user]] A is [[linked]] to [[user]] B, we [[sum]] the [[number]] of [[item]]s the two [[user]]s have [[in common]]. | ** QUOTE: … If we are trying to [[evaluate]] the [[likelihood]] that [[user]] A is [[linked]] to [[user]] B, we [[sum]] the [[number]] of [[item]]s the two [[user]]s have [[in common]]. | ||
* ([[2003_LinkPredictionInRelData|Taskar et al., 2003]]) ⇒ [[Ben Taskar]], Ming-Fai Wong, [[Pieter Abbeel]] and [[Daphne Koller]]. ([[2003]]). “[http://www.seas.upenn.edu/~taskar/pubs/link.pdf Link Prediction in Relational Data].” In: Neural Information Processing Systems Conference ([[NIPS 2003]]) | * ([[2003_LinkPredictionInRelData|Taskar et al., 2003]]) ⇒ [[Ben Taskar]], Ming-Fai Wong, [[Pieter Abbeel]] and [[Daphne Koller]]. ([[2003]]). “[http://www.seas.upenn.edu/~taskar/pubs/link.pdf Link Prediction in Relational Data].” In: Neural Information Processing Systems Conference ([[NIPS 2003]]) | ||
** QUOTE: [[We]] apply the ''[[relational Markov network]]'' [[framework]] of [[Taskar]] ''et al''. to define a [[joint probabilistic model]] over the entire [[link graph]] — [[entity attributes]] and [[links]]. | ** QUOTE: [[We]] apply the ''[[relational Markov network]]'' [[framework]] of [[Taskar]] ''et al''. to define a [[joint probabilistic model]] over the entire [[link graph]] — [[entity attributes]] and [[links]]. | ||
Revision as of 18:55, 1 August 2022
A Graph Edge Prediction Algorithm is a multi-class classification algorithm that can be implemented into a graph edge prediction system (to solve a graph edge prediction task).
- AKA: Link Prediction Algorithm.
- Context:
- It can range from being a Heuristic Link Prediction Algorithm to being a Data-Driven Link Prediction Algorithm (such as a supervised link prediction algorithm).
- Example(s):
- Counter-Example(s):
- See: Markov Logic Network, Statistical Relational Learning
References
2011
- (Lü & Zhou, 2011) ⇒ Linyuan Lü, and Tao Zhou. (2011). “Link Prediction in Complex Networks: A Survey.” In: Physica A: Statistical Mechanics and its Applications, 390(6).
- QUOTE: 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. … Finally, we introduce some applications and outline future challenges of link prediction algorithms.
2009
- (Miller et al., 2009) ⇒ Kurt T. Miller, Thomas L. Griffiths, and Michael I. Jordan. (2009). “Nonparametric Latent Feature Models for Link Prediction..” In: Advances in Neural Information Processing Systems 22 (NIPS 2009).
2006
- (Al Hasan et al., 2006) ⇒ Mohammad Al Hasan, Vineet Chaoji, Saeed Salem, and Mohammed Zaki. (2006). “Link Prediction Using Supervised Learning.” In: SDM’06: Workshop on Link Analysis, Counter-terrorism and Security.
- Link prediction in a social network is an important problem and it is very helpful in analyzing and understanding social groups.
2003
- (Liben-Nowell & Kleinberg. 2003) ⇒ David Liben-Nowell, and Jon Kleinberg. (2003). “The Link Prediction Problem for Social Networks.” In: Proceedings of the twelfth International Conference on Information and knowledge management (CIKM 2003). doi:10.1145/956863.956972
- (Adamic & Adar, 2003) ⇒ Lada A. Adamic, and Eytan Adar. (2003). “Friends and Neighbors on the Web.” In: Social Networks, 25(3). doi:10.1016/S0378-8733(03)00009-1
- (Taskar et al., 2003) ⇒ Ben Taskar, Ming-Fai Wong, Pieter Abbeel and Daphne Koller. (2003). “Link Prediction in Relational Data.” In: Neural Information Processing Systems Conference (NIPS 2003)
- QUOTE: We apply the relational Markov network framework of Taskar et al. to define a joint probabilistic model over the entire link graph — entity attributes and links.