2.4. mpolishing 一般グラフの研磨¶
一般グラフデータを入力として、密度の高い部分グラフの中でエッジが張られていないノードペアに枝を張る。 逆に、密度の低い部分グラフのエッジを削除する。 新たに張られる枝や刈られる枝の程度は、sim=とth=で与えた値によって変わる。
パラメータ¶
ei= : 型=str , 必須
エッジデータファイル名を指定する。
ef= : 型=str , 任意(default=node1,node2)
エッジデータ上の2つのノード項目名を指定する。
ni= : 型=str , 任意(default=エッジファイル上のノードのみを対象にする)
ノードデータファイル名を指定する。
nf= : 型=str , 任意(default=node)
ノードデータ上のノード項目名
eo= : 型=str , 必須
データ研磨後のエッジデータファイル名を指定する。
no= : 型=str , 任意(default=ノードデータを出力しない)
データ研磨後のノードデータファイル
sim= : 型=str , 任意(default=R)
ノードa,bに張られたエッジ集合を、それぞれA,Bとしたとき、ノードa,bに枝を張るために用いる類似度を指定する。* i: inclusion* I: both-inclusion* S: \(|A \cap B| / max(|A|,|B|)\)* s: \(|A \cap B| / min(|A|,|B|)\)* T (intersection): find pairs having common [threshld] items* R (resemblance): find pairs s.t. \(|A \cap B| / |A \cup B| >= [threshld]\)* P (PMI): find pairs s.t. log ( \(|A \cap B| * |all| / (|A|*|B|)) >= [threshld]\)* C (cosine distance): find pairs s.t. inner product of their normalized vectors >= [threshld]
th= : 型=float , 必須
sim=で指定された類似度について、ここで指定された値以上の節点間に枝を張る。
sup= : 型=int , 任意(default=0)
類似度計算において、 \(|A∩B|>=sup\) の条件を加える。
indirect= : 型=bool , 任意(default=False)
上記類似度計算における隣接節点集合から直接の関係を除外する。すなわち、 \(A=A-b, B=B-a\) として類似度を計算する。
iter= : 型=int , 任意(default=30)
データ研磨の最大繰り返し数を指定する。
log= : 型=str , 任意(default=ログを出力しない)
パラメータの設定値や収束回数等をkey-value形式のCSVで保存するファイル名を指定する。
T= : 型=str , 任意(default=/tmp)
ワークディレクトリ名を指定する。
O= : 型=str , 任意(default=研磨過程を出力しない)
デバッグモード時、データ研磨過程のグラフを保存するディレクトリ名を指定する。
利用例¶
入力データの準備
1with open('dat1.csv','w') as f: 2 f.write( 3'''node1,node2 4a,b 5a,c 6a,e 7b,c 8b,e 9b,g 10c,d 11c,g 12d,e 13e,f 14''')
基本例
類似度をresemblance(sim=R)とし、th=0.4で枝を張り直してグラフ研磨する。
log1.csv
を見ると、グラフ情報の表示が繰り返されておりそれが
5回目(dens4など)で終わっており、研磨回数は5回で収束していることがわかる。
1import nysol.take as nt 2from nysol.take import graph as ng 3gi=ng.graph(edgeFile="dat1.csv",title1="node1",title2="node2") 4go=nt.mpolishing(gi=gi,sim="R",th=0.4,log="log.csv").run() 5e=go.edges().run() 6print(e) 7# [['a', 'b'], ['a', 'c'], ['a', 'e'], ['a', 'g'], ['b', 'c'], ['b', 'e'], ['b', 'g'], ['c', 'e'], ['c', 'g'], ['e', 'g']] 8n=go.nodes().run() 9print(n) 10# [['a'], ['b'], ['c'], ['d'], ['e'], ['f'], ['g']] 11### log.csv の内容 12# key,value 13# iter,30 14# outDir,None 15# th,0.4 16# indirect,False 17# measure,R 18# minSupp,0 19# logFile,log.csv 20# outDir,None 21# time,0:00:00.245431 22# nSize0,7.0 23# eSize0,10 24# dens0,0.47619047619047616 25# nSize1,7.0 26# eSize1,11 27# dens1,0.5238095238095238 28# nSize2,6.0 29# eSize2,11 30# dens2,0.7333333333333333 31# nSize3,5.0 32# eSize3,10 33# dens3,1.0 34# nSize4,5.0 35# eSize4,10 36# dens4,1.0
PMIによる研磨
類似度をnormalized PMI(sim=P)とし、th=0.2で枝を張り直して得られた研磨グラフ。
1import nysol.take as nt 2from nysol.take import graph as ng 3gi=ng.graph(edgeFile="dat1.csv",title1="node1",title2="node2") 4go=nt.mpolishing(gi=gi,sim="P",th=0.2).run() 5e=go.edges().run() 6print(e) 7# [['a', 'b'], ['b', 'c'], ['b', 'g'], ['c', 'g'], ['e', 'f']] 8### の内容
intersectionで1回の研磨
類似度をintersection(sim=T)とし、2件以上(th=2)で枝を張り直し 直接の接続を考慮に入れる例。研磨回数は1回のみ(iter=1)。
1import nysol.take as nt 2from nysol.take import graph as ng 3gi=ng.graph(edgeFile="dat1.csv",title1="node1",title2="node2") 4go=nt.mpolishing(gi=gi,sim="T",th=2,iter=1).run() 5e=go.edges().run() 6print(e) 7# [['a', 'b'], ['a', 'c'], ['a', 'd'], ['a', 'e'], ['a', 'g'], ['b', 'c'], ['b', 'd'], ['b', 'e'], ['b', 'g'], ['c', 'd'], ['c', 'e'], ['c', 'g'], ['d', 'e'], ['e', 'f']] 8### result.csv の内容
直接の接続を考慮しない例
indirect
オプションを指定することで、類似度の計算で直接の接続は無視される。
出力結果では、枝が全て消えるため、研磨後の枝データは出力されない。
1import nysol.take as nt 2from nysol.take import graph as ng 3gi=ng.graph(edgeFile="dat1.csv",title1="node1",title2="node2") 4go=nt.mpolishing(gi=gi,sim="T",th=2,indirect=True).run() 5e=go.edges().run() 6print(e) 7# [] 8### result.csv の内容
関連メソッド¶
mbipolish 2部グラフの研磨 : 2部グラフの研磨