Markov Cluster Algorithm (MCL) - kwakita’s diary
Stein van Dongenの博士論文("Graph clustering by flow simulation")をぱらぱらと読んでいます。この論文のテーマは有向グラフをクラスタリングすることです。"Markov Clustering"の名称の由来は、グラフからクラスターを発見するのに、グラフ上のランダムウォークを利用したときに、グラフ上の遷移をMarkov過程としてモデルできるからです。グラフ上のランダムウォークとは、適当にノードを選択し、そこからエッジを無作為に選んで隣接するノードに向う移動を繰り返すことです。ランダムウォークを無限に繰り返したときに各ノードを訪問する遷移確率を利用してグラフからクラスターを発見するようです。 MCLの計算量はO(Nk2)です。ここでNはノード数、kはノードの平均次数。たぶん、O(Nk)の項は行列積を一回計算するのに必要な計算量で残ったO(k)は?
グラフの類似性を評価する - ryamadaの遺伝学・遺伝統計学メモ
はじめに 参考PDF グラフの同形性評価(graph isomorphism)と類似性評価 Graph isomorphismはグラフ構成要素であるノードの1対1対応とエッジの1対1対応によって定義されている。それに対して、類似性評価は同形性からのはずれの程度の評価であり、その尺度は定義に依存する グラフの類似度評価 評価の指標(グラフ間距離)に求められるもの Metric 同一グラフ間距離は0 グラフＡからグラフＢへの距離とグラフＢからグラフＡへの距離は同一(対象性 Symmetry) グラフＡからＢへの距離とグラフＢからＣへの距離の和はグラフＡからＣへの距離を越えない(Triangle inequality) 評価方法 Graph edit distance法 ２つのグラフを比較し、グラフに操作(ノードおよびエッジの削除・挿入・置換)を加えることで、両グラフを同一にするときに、その最小
グラフレイアウト - ryamadaの遺伝学・遺伝統計学メモ
数多くの要素について、要素をノードで、要素間の関係をエッジで表したものをグラフという。 グラフはこの定義からもわかるように、図示することが本質ではない。 本質ではないけれども、図示することで、「全体が持つ情報を的確に捕らえる」ことの手助けができることがある。 その「図示」は、『グラフレイアウト』と呼ばれる。 こちらのPDFによくまとまっている。ちなみに、このPDFシリーズの前後の章は"http://cgi.members.interq.or.jp/pacific/moto/shuron/Master_Thesis_k.pdf" のkに1,2,3,...を入れれば表示される。 先日も紹介した、VGJでは、Springという図示方法が選べるようになっているが、それは、Kamada and Kawai's spring algorithmと呼ばれるもので、すべてのノード間に、グラフ上の最短パスに
グラフ理論のサイトと書籍のご紹介 - salmonsnareの日記
はじめに [更新: 2013/4/22]いくつか更新しました。 [/更新] §1では、グラフ理論のWWW上の資料で「これは良かった。役に立った。」と思えるものをご紹介します。 どちらかというと、グラフアルゴリズムより数学としてのグラフ理論を意識した資料を選びました。 §2では、グラフアルゴリズム等を含むより専門的な書籍をご紹介します。 1. グラフ理論のサイト Reinhard Diestel, Graph Theory Electronic Edition http://diestel-graph-theory.com/basic.html ディーステル先生のグラフ理論のテキストのpdf版です。基礎から応用まで丁寧に書いてあります。 応用についてはほとんど書かれておりませんが、その分数学的な色彩が強い本です。 目次 1. The Basics: グラフの基礎です。次数やパス等の基本的な定
アルゴリズム設計 講義資料 2005
Algorithm Design Course Materials 2013 Oct 7: Introduction and Computational Complexity Oct 15: Search Trees Oct 21: Combinatorial Optimization Oct 28: Heuristic Search Nov 5: Text Search Nov 11: Data Compression Nov 18: Memory Management Nov 25: Graph Algorithms 1/2 Dec 2: Graph Algorithms 2/2 Dec 9: Computational Geometry Dec 16: Concurrency Control Jan 15: Canceled Jan 20: Clustering Course Pro
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
MCL - a cluster algorithm for graphs
A 3D spatial data model for terrain reasoning
neo4j open source nosql graph database
構造データからの機械学習 - データ解析技術