■

Maximizing the spread of influence through a social network
David Kempe，Jon Kleinberg，Éva Tardos
KDD '03 Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining　Pages 137-146 (2003)

査読している論文に引用されていた，有名な(被引用数1436件)情報カスケードのモデル論文．
どのノード(たち)に情報を与えると，効率よく拡散してくれるかを，調べるのに使えるモデルらしい．
実際には研究者の共同研究ネットワークで実験．
拡散モデルには大きく２つあって，1つはある閾値を超えると隣人にactivateされるThreshold Modelと，
もう1つは，ランダムな確率で隣人とのactivate確率が決まるIndependent Cascade Modelで，本論文は後者．
知っているようで，知らなかった単語がたくさん．勉強になりました．．．

• heuristic(ヒューリスティック)　：経験則的な．発見的な．→　職人の勘的な意味．

• NP-hard(困難)：Non-deterministic Polynomial time(非決定論的多項式時間)．

• deterministic：決定論的な．反対が確率論的なprobabilistic，polynomial：多項式

• Knapsack problem（ナップサック問題）：1つのナップサックに，複数の価値，容量の違うものを詰め込むとき，ナップサックの中の価値を最大化するには？というNP-hardの問題の1つ．他にも巡回セールスマン問題などもNP-hard．

• greedy algorithm（貪欲法）：NP-hard問題に対する解の与え方のアルゴリズムの1つ．具体的にナップサック問題なら，詰める品物の容積あたりの価値を計算して，その高いものから詰めて行く方法．