2012年1月14日土曜日

fullsc2.cppに関して

UNICORNの実験で使われているクロネッカーグラフのSCALE*.txtを実験データに用いたところ、
処理が異常に早く終わり、λが0になってしまう。うまく動かない。
→次数が0の頂点が存在するため?
→or グラフが連結でないため?

対数正規分布グラフで実行したところ、正常に動いた。
必ず次数が1以上になるように生成している。
v=1000,e=37575(重複を除外)で、システムとの入出力時間も含めて
63.6秒かかった。

2011年11月27日日曜日

memo

LD_LIBRARY_PATH

2011年11月17日木曜日

ぐらふ

BFS前処理による計算範囲の限定 (original idea from Incremental PageRank)
→有向グラフ
→PageRank
収束判定に基づく計算範囲の限定 (original idea from Adaptive PageRank)
→有向グラフ、無向グラフ
→PageRank, RWR, SSSP

[new]名称未定 : Incremental Spectral Clustering のための通信
→無向グラフ
→I.SC

2011年11月4日金曜日

クラスタリングメモ、続き

*Parallel Incremental Graph Partitioning, Chao-Wei Ou and Sanjay Ranka, Member, IEEE
線形計画法(LP)によるインクリメンタルグラフパーティショニング
(古い論文 : Parallel Incremental Graph Partitioning Using Linear Programming)

===

実装・実験するもの
・Full SC (k=2)
・Incremental SC (k=2)
(・Incremental Partitioning with LP (k=2, 3, ...) : 実装間に合わないと思う)

実行時間、収束回数
分割結果の評価(頂点コスト、通信コストを評価する?)

(Incremental Partitioning with LPで、初期分割はどうするか?)

クロネッカーグラフ
頂点重み(1)と辺重み(1?)は固定

===

以下を並行して行っていく
・SC, Incremental SCの実装に関するppt作成、ラフに
→11月中旬、下旬まで
・実装
→12月上旬、中旬まで
・実験
→12月内に

===

他の参考文献・URL

glaros.dtc.umn.edu/gkhome/publications/gp
METISとか

www.sciencedirect.com/science/article/pii/S1574013707000020
Glaph Clustering, サーベイ論文

2011年10月19日水曜日

クラスタリングメモ

辺の追加・更新→類似度行列の拡大・更新
更新される要素 : w_{i,j} ( = w_{j,i} )
類似度行列を拡大するとき、要素の初期値は0

スペクトラルクラスタリングは必ずしもグラフを対象をしたクラスタリング手法ではないが、
全頂点対間の類似度を類似度行列として扱っているので、
類似度行列をグラフの隣接行列とみなせばグラフにも使える、ということかな?

他のグラフクラスタリング手法について調査

===

Incremental Spectral Clustering With Application to Monitoring of Evolving Blog Communities
関連研究よりメモ

[14]Ng et al. On spectral clustering: Analysis and an algorithm.
マルチウェイ(k=3クラスタ以上)のクラスタリング手法。
固有値の小さいものから順にk個固有ベクトルを取り出して(k次元の特徴量を抽出して)
n×k行列を作成。各行を頂点の値としてk-meansなどでクラスタリング。

Spectral Clustering以外のIncremental Methodsについて

[9]Gupta et al. A single pass generalized incremental algorithm for clustering.
ストリームは辺じゃなくて頂点、というかそもそもグラフが対象じゃない。
クラスタ中心と追加された頂点との比較ができないといけないので。
[8]k-medoids?頂点ストリームが対象?
[2]これも距離空間上の頂点ストリームが対象
[4][11]PageRankの話

===

遺伝的アルゴリズムを使ったグラフ分割

2011年10月4日火曜日

新しいigimvで

PageRankの再実装
Spectral Clusteringの実装
あと評価

現状、小さな密行列に対して疑似逆行列を計算する方法を考える必要がある

2011年9月14日水曜日

殴り書き

SSSPのような反復回数が多くなる(3桁以上)アルゴリズムには向かない