前置き
グラフ上のノードのラベルを推定する手法。
lp.pyはここを参考にして実装した。というかほとんどそのまま。
lp_original.pyは論文の２章を参考にして実装した。
lp_original.pyでは連立方程式を解かないで繰り返し繰り返し行列積を計算していく方法も実装した（lp_iter）。
実装
lp.py
# -*- coding: utf-8 -*-
import sys
from scipy.sparse import *
from scipy.sparse.linalg import spsolve
def load_adjucency(filename,n):
W = lil_matrix((n,n))
for line in open(filename, 'r'):
entries = line.rstrip().split(' ')
src = int(entries[0])
dst = int(entries[1])
W[src,dst] = 1
return W
def load_labels(filename,n):
y = lil_matrix((1,n))
for line in open(filename, 'r'):
entries = line.rstrip().split(' ')
nid = int(entries[0])
label = int(entries[1])
y[0,nid] = label
return y
n = int(sys.argv[1])
W = load_adjucency(sys.argv[2],n)
y = load_labels(sys.argv[3],n)
D = dia_matrix((W.sum(0),[0]), W.shape)
L = D - W
I = identity(W.shape[0])
lam = 1
f = spsolve((I + lam * L), y)
print f
lp_original.py
# -*- coding: utf-8 -*-
import sys
from scipy.sparse import *
from scipy.sparse.linalg import spsolve
from sklearn.preprocessing import normalize
def load_matrix(filename,n,m):
W = lil_matrix((n+m,n+m))
for line in open(filename, 'r'):
entries = line.rstrip().split(' ')
src = int(entries[0])
dst = int(entries[1])
W[src,dst] = 1
W = normalize(W,norm='l1',axis=1)
Wul = W[n:n+m,0:n]
Wuu = W[n:n+m,n:n+m]
return (Wuu,Wul)
def load_labels(filename,n):
y = lil_matrix((n,1))
i = 0
for line in open(filename, 'r'):
label = int(line.rstrip())
y[i,0] = label
i += 1
return y
def lp_solve(Wuu,Wul,y):
return spsolve((identity(m) + Wuu), Wul*y)
def lp_iter(Wuu,Wul,y,t=10):
i = 0
f = lil_matrix((Wuu.shape[0],1))
while True:
f = Wuu * f + Wul * y
if i > t:
break
i += 1
return f
""" # of labeled nodes """
n = int(sys.argv[1])
""" # of unlabeled nodes """
m = int(sys.argv[2])
""" propagation matrix (row normalized) """
Wuu,Wul = load_matrix(sys.argv[3],n,m)
""" labels of labeled nodes """
y = load_labels(sys.argv[4],n)
print lp_solve(Wuu,Wul,y)
print '============='
print lp_iter(Wuu,Wul,y)
使い方
lp.pyはノード数、エッジリストのファイルパス、ノードラベルのファイルパスの順で渡して実行する。
使ってるデータは参考にしたブログと同じもの。
lp.pyの実行例
$ cat edge_list
0 2
2 0
0 4
4 0
0 9
9 0
1 2
2 1
2 3
3 2
3 4
4 3
3 6
6 3
5 9
9 5
6 7
7 6
6 8
8 6
7 9
9 7
$ cat labels
0 1
2 1
4 1
5 -1
6 -1
7 -1
$ python lp.py 10 edge_list labels
[ 0.45966011 0.23023256 0.46046512 0.1519678 0.5372093 -0.57951699
-0.38980322 -0.51627907 -0.19490161 -0.15903399]
lp_original.pyはラベル付きノード数n、ラベル無しノード数m、エッジリストのファイルパス、エッジリストのファイルパスの順で渡して実行する。
ただし、ノード番号は0からn-1がラベル付きノード、nからn+mがラベル無しノードにしなくちゃいけない。
今回の例でlp.pyに渡すノード番号とlp_original.pyに渡すノード番号の対応は次のようになっている。
lp.py [0,1,2,3,4,5,6,7,8,9]
lp_original.py [0,6,1,7,2,3,4,5,8,9]
なので、ラベルファイルの各行には0からnのラベル付きノードのラベルが書かれている。
この実装の場合、ラベル無しノードからラベル付きノードへのエッジと、ラベル無しノードからラベル無しノードへのエッジしか使わずに済む。
lp_original.pyの実行例
$ cat edge_list_for_original
9 0
6 1
7 1
7 2
7 4
9 3
8 4
9 5
$ cat labels_for_original
1
1
1
-1
-1
-1
$ python lp_original.py 6 4 edge_list_for_original labels_for_original
[ 1. 0.33333333 -1. -0.33333333]
=============
(0, 0) 1.0
(1, 0) 0.333333333333
(2, 0) -1.0
(3, 0) -0.333333333333
結果はlp.pyと違うけど、傾向は同じ。