Pythonでラベル伝搬法を試してみる

ネットワークの構造を予測解析のタスクにはノード判別とリンク予測があります．ノード判別問題は，幾つかのノードについてクラスラベルが与えられているとき，残りのクラスラベルが未知のノードに対してクラスラベルを予測する問題です． ノード判別手法の最も簡単なもののひとつとしてラベル伝搬法という手法が知られています．ラベル伝搬法のアルゴリズムのひとつを文献1の801ページに基づいて実装してみました．なおラベル伝搬法については文献2の11章にまとまってました． 鹿島, グラフとネットワークの構造データマイニング, 電子情報通信学会誌 93(9), 797-802, 2010. Chapelle, O. et al., Semi-supervised learning, MIT Press, 2006. ラベル伝搬法は「ネットワーク上で隣り合ったノードは同じクラスに属する」と仮定して未知のノードにラベルを