Evolution of Node Behavior in Link Prediction(pdf)
内容
リンク予測に関して3つの実データで検証.問題設定が通常のlink predictionと異なっていて,networkがtime periodで変化する,例えば各stepごとにリンクが繋がったり切れたりしてる時にある時間tにおいてのデータからt + 1でのlink predictionをする,という感じ.
手法
大体リンク予測というと前にも少し書いた(IJCNN Social Network Challengeの勝者が取った手法(deanonymize)は許されるか? - 糞ネット弁慶)ようにAdamic/AdarとかKatzとかBetweennessといったtopologicalなfeatureを使って判別するみたいな話が多い.
今回は3つのアルゴリズム(+ 提案手法)が試されている.
- New Perspectives and Methods in Link Prediction(KDD 2010)
- Temporality in link prediction: Understanding social complexity
- staticなfeatureに咥えてrecencyと呼ばれる特徴量が導入されている.これは最後にそのノードにリンクが繋がってからの経過時間.これが長いノードはアクティブじゃなさそうなのでこれから先も繋がらなさそう,という考え方.予測はrandom forest.
- The Time-Series Link Prediction Problem with Applications in Communication Surveillance(INFORMS)
- こちらはactivenessという特徴量が導入されている.これは最新のstepつまりtにおいてそのノードがどれぐらいの数のノードと繋がったか,というもの.これが大きいノードは次のステップもで繋がりやすいだろう,という考え方.予測はrandom forest.
- 提案手法
- Interplayなる特徴量を導入.AとBのjoint likelihoodを求めるみたいな話をしてるけどちょっと言葉足りなくてわかってない.