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)は?
「第一回真の闇プログラマ認定プログラミングコンテスト」開催 | スラド
12月25日から来年2月1日にかけて、「第一回真の闇プログラマ認定プログラミングコンテスト」なるものが開催されるらしい(ATNDでの告知、コンテストページ)。 概要は下記のとおり。 近年、C++闇の軍団というC++0x原理主義者が地下活動から私のテリトリーであるグラフ理論のUStream配信を行っているという情報を得た。 (中略) よって、どっかの中二病者がのたまっている闇プログラマーではなく、C++闇の軍団に抵抗しうる真の闇プログラマを養成し、ゆくゆくはC++闇の軍団の対抗勢力となりうる真の闇プログラマの部隊を創設する予定である。 その部隊の志願者や適合者を選別するのが今回のプログラミングコンテストの真意である。奮って参加をして欲しい。
2010-06-02
今日が締切だということに気づいていなかったので忘れるところだった．なんとか提出． 全然進まない．査読者のいってることが分からなくもないけど，よく分からない． グラフ理論―連結構造とその応用 (基礎数理講座) 作者: 茨木俊秀,石井利昌,永持仁出版社/メーカー: 朝倉書店発売日: 2010/04/01メディア: 単行本購入: 1人 クリック: 90回この商品を含むブログ (1件) を見る 「グラフ理論」というタイトルだけども，内容は「グラフ・アルゴリズム」である．しかも，フロー，カット，連結度に焦点を絞ったもので，かなりマニアック (褒め言葉) である．こういう高度な内容のものが日本語で読めるということは嬉しいことだと思う．中身はちゃんとしてる気がするので，第1章をうまく読み飛ばせば，セミナーの輪講にあってるのではないかと思う．
グラフ理論
グラフ理論における「グラフ」というのはいくつかの点をいくつかの線でつないだモノである。 普通はどの点とどの点が結ばれてるかのみに着目しどのように結ばれているかは問わないことが多いが、幾何学的グラフ理論では点集合としての（位相的）図形として結ばれ方も重視する。 この２つの見方 ― 「システム」としての見方と「図形」としての見方 ― が可能なことからグラフは一見単純ではあるが奥深い数学的な対象となっている。 グラフ理論は身近に存在する。 たとえば我々はいたるところで「植木算」のお世話になっているが、植木算の中にグラフ理論の主要な考えの発端が見られる。 この講義ではグラフ理論の応用数学的な側面よりも純粋数学的な側面に焦点を絞った。 形式的な記述でわかりにくい部分も図を見ればわかってしまうことが多いように図をたくさん入れておいた。 予備知識はほとんど不要であるが、ベクトル空間やポセッ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
2005年度 グラフ理論講義ノート : HUSCAP
2004年度 グラフ理論講義ノート : HUSCAP
