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

*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, サーベイ論文

クラスタリングメモ

辺の追加・更新→類似度行列の拡大・更新

更新される要素 : 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の話

===

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

新しいigimvで

PageRankの再実装

Spectral Clusteringの実装

あと評価

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

殴り書き

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

ぱーてぃしょにんぐ、しらべもの

Spectral Clusteringについて

Data Similarity Graphというグラフを定義し、そのグラフを対象とした話。

密行列なのでBSPやGIM-Vに向かない？

他のGraph Partitioningアルゴリズムを考えるべきかも。

勘違いしてるかも。

参考文献、URL

・d.hatena.ne.jp/mamoruk/20090128/p1

・Qianjun Xu, Marie desJardins and Kiri L. Wagstaff. Active Constrained Clustering by Examining Spectral Eigenvectors. Proc of Discovery Science 2005.

・・(2章)

今後

調べるアルゴリズム（アプリケーション）

・最短経路問題

・中心性解析 (Between Centrality)

・Random Walk with Restart

・Spectral Clustering (Graph Partitioning)

モデルとして、GIM-Vでなければならなかった理由？

・特になし。しいて言えば、PEGASUSがオープンソースだったから。

・Pregel,BagelなどのBSPでもいいと思う。実装コストはともかく

個別ミーティング

TODO in short term:

GIM-V on System S と PEGASUS の性能比較

TODO in long term:

Incremental Algorithm の調査、Stream化