ぐらふすぺくとる

なぜしゅーろんが終わった今になって今更ぐらふすぺくとるの理論について調べているのか

書籍まで読むのは無理そうだけど

とりあえずS先生の講義資料を入手したのでそれを読む

はてなダイアリーより

d.hatena.ne.jp/smly/20080817/1218988549

Yale大のDan Spielman氏による講義資料 : Spectral Graph Theory and its Applications

http://www.cs.yale.edu/homes/spielman/eigs/

Fan R. K. Chung氏による書籍 : Spectral Graph Theory (Cbms Regional Conference Series in Mathematics)

http://www.amazon.co.jp/gp/product/0821803158

Wikipedia : Spectral graph theory

http://en.wikipedia.org/wiki/Spectral_graph_theory

スペクトラルクラスタリング、可視化

適当に1000頂点のツリーをランダムに作成、スペクトルを計算、Cytoscapeでスペクトルを基に色分けしてみた。

インクリメンタルグラフクラスタリング

インクリメンタルな更新をアニメーションで可視化してプレゼンテーションしたい

Cytoscape

graphviz -> 不適

fullsc2.cppに関して

UNICORNの実験で使われているクロネッカーグラフのSCALE*.txtを実験データに用いたところ、

処理が異常に早く終わり、λが0になってしまう。うまく動かない。

→次数が0の頂点が存在するため？

→or グラフが連結でないため？

対数正規分布グラフで実行したところ、正常に動いた。

必ず次数が1以上になるように生成している。

v=1000,e=37575(重複を除外)で、システムとの入出力時間も含めて

63.6秒かかった。

memo

LD_LIBRARY_PATH

ぐらふ

BFS前処理による計算範囲の限定 (original idea from Incremental PageRank)

→有向グラフ

→PageRank

収束判定に基づく計算範囲の限定 (original idea from Adaptive PageRank)

→有向グラフ、無向グラフ

→PageRank, RWR, SSSP

[new]名称未定 : Incremental Spectral Clustering のための通信

→無向グラフ

→I.SC

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

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