projects:twitterソーシャルグラフからのコミュニティ抽出 [ryogrid.net]
以下サイトでTwitterのソーシャルグラフが配布されている。 # 103万人分、2.8億エッジという驚愕の規模 http://d.hatena.ne.jp/code46/20110130/p1 今回、このデータを題材としたコミュニティ抽出のプログラムを書いたので、開発過程のいろいろをまとめておく。 一部、Amazon Elastic MapReduceでの分散処理などもやってみたので、MapReduceやCloudに興味を持つ人にも利益があるかもしれない。特に、実アプリ開発を題材とした事例紹介はWeb上でも少ないようなので、そういった位置づけでは価値があるのではないかと思う。 ソーシャルグラフ、コミュニティ抽出(≒クラスタリング?)の概要については以下が分かりやすい。 http://www.slideshare.net/komiyaatsushi/newman-6670300 実は、以前
大規模グラフ処理フレームワーク Pregel のオープンソース実装 Bagel とか - Standard ML of Yukkuri
ref: http://portal.acm.org/citation.cfm?id=1582723大規模グラフ処理フレームワーク Pregel の論文を読み, BSP (Bulk Synchronous Parallel) モデルで実装したいグラフのアルゴリズムがいくつかあったのでオープンソース実装を探してみた. GoldenOrb, Phoebus, HAMA (汎用的なBSP model), そして Bagel などいくつかの実装があるようで, GoldenOrb は Java, Phoebus は Erlang で実装されており, Bagel は Scala で書かれている. Bagel は Spark 上で動くシンプルな実装 (たったの 150 行程度) で, 大規模なタスクに対してもスケールする運用が可能に思えたので Bagel を使ってみることにした. (Phoebus は
Python でグラフ・(疎)行列計算するためのライブラリを紹介するよ - 武蔵野日記
PageRank とか HITS といったリンク解析ではグラフの計算が頻発するのだが、Python でそのあたり書くときの話をまとめてみる。グラフは行列で表現できる(ノード×ノード次元の行列 A を考えて、ノード i からノード j にエッジがあるとき、A[i,j] に値を入れておけばよい。無向グラフのときは A[i,j] = A[j,i] なので対称行列になる)ので、要は行列を手軽に扱えるライブラリの紹介である。 実は Python の行列演算ライブラリはどれも lapack/blas を内部的に呼んでいるので、C/C++ 等と比較してもそんなに遅くない。それどころか、自動的に並列化できるところは並列化してくれたりするので、まれに C より速いこともあるらしい。特に巨大なグラフを作る場合、ほとんどの処理は C などで書かれた関数に飛ぶので、速度的な問題は無視してもいいくらいである(逆に、
スペクトラルクラスタリングは次元圧縮しながらKmeansする手法 - 武蔵野日記
機械学習系のエントリを続けて書いてみる。クラスタリングについて知らない人は以下のエントリ読んでもちんぷんかんぷんだと思うので、クラスタリングという概念については知っているものとする。 それで、今日はスペクトラルクラスタリングの話。自然言語処理以外でも利用されているが、これはグラフのスペクトルに基づくクラスタリングの手法で、半教師あり学習への拡張がやりやすいのが利点。なにをするかというとクラスタリングをグラフの分割問題(疎であるエッジをカット)に帰着して解く手法で、どういうふうに分割するかによって Normalized cut (Ncut) とか Min-max cut (Mcut) とかいろいろある。 完全にグラフが分割できる場合はこれでめでたしめでたしなのだが、実世界のグラフはそんな簡単に切れないことが往々にしてある。それで近似してこのグラフ分割問題を解くのだが、Normalized c
完全2部グラフをGraphvizとPerlを使って簡単に書く方法 - salmonsnareの日記
[追記: 2010/08/18] id:ksmemoさんがGraphVizモジュールを使って書かれたコードの方がすっきりしているのでこちらを推奨します。 ケーズメモ, GraphVizを使ってPerlで簡単にGraphvizでグラフを書く方法, http://d.hatena.ne.jp/ksmemo/20090903/p1 CPAN, GraphViz, http://search.cpan.org/dist/GraphViz/ はじめに 「頂点数の大きな完全2部グラフを手で書くより、自動化した方がいいだろう。」 っていう動機で、 Graphvizのファイル形式である、dotを出力するためのPerlスクリプトを書きました。 Graphvizは、グラフ理論でいうグラフを簡単に描画するための便利なツールです。 導入の資料は、[1]に紹介したので参照してください。 完全2部グラフとは 2部グラ
グラフライブラリ
グラフを扱うためのオープンなクラスライブラリにはBGL(Boost Graph Library)を筆頭に優れたものがたくさんありますが，本ライブラリは 導入が容易：簡単な機能は簡単に記述できること． カスタマイズが容易：ソースコードの一覧性が高いこと． ソコソコの機能でソレナリのパフォーマンス という点を目標に作成しています．特徴は以下の通りです． ノードとエッジの追加（定数時間） ノードとエッジへのインデクスを用いたランダムアクセス（定数時間） 任意のノードとエッジの削除（定数時間） ノードに隣接するノード群とその接続を媒介するエッジ群へのランダムアクセス（定数時間） ノードに隣接する特定のノード，あるいはエッジの検索（線形時間） エッジの両端に接続するノードの検索（定数時間） 有向グラフとして動作（無向グラフとしての利用も可能） 自己ループエッジ（両端が同一ノードのエッジ）と多重エッジ
ダイクストラ法 - Bug's Groove
前回のアルゴリズムイントロダクション輪講の話題、単一始点最短路問題から。詳しくは アルゴリズムイントロダクション第24章 単一始点最短路問題 - naoyaのはてなダイアリー へ。その中で丁度前回 書いたプリム法と同じく、ダイクストラ法が最小優先度付きキューを使うので、ちょっといじったらかけるのでは？と思って書いてみました。(相変わらずの乱プログラムご容赦...)。対象のグラフは教科書通り。 実装的には、minheap クラスは前回のプリム法と全く一緒。MinPriorityQueue は前回と使い方が違うので一部実装し直し。(といっても relax の周り)。実行するとこんな感じになるはずです。 s -> y -> t (8) s -> y -> t -> x (9) s -> y (5) s -> y -> z (7) 教科書のヒープソート (6章) にもあったように、優先度付きキュー
アルゴリズムイントロダクション第24章 単一始点最短路問題 - naoyaのはてなダイアリー
アルゴリズムイントロダクションの輪講で、第24章の単一始点最短路問題を担当しました。発表に使った資料を以下にアップロードしました。 http://bloghackers.net/~naoya/ppt/090622_shortest_paths.ppt SlideShare はこちら。フォントの関係でグラフが崩れたりしているので、ppt で参照した方が見やすいかと思います。 Introduction to Algorithms#24 Shortest-Paths ProblemView more OpenOffice presentations from Naoya Ito. 単一始点最短路問題は、重み付き有向グラフの最短路木を求める問題です。各頂点に最短路重みを記録するのですが、はじめに各頂点の重みを∞として、「緩和」と呼ばれる操作により徐々に頂点の重みを最短路重みに近づけていく、というの
グラフ理論ライブラリのJGraphTを使ってみた - kaisehのブログ
JGraphT JGraphTは、Javaのグラフライブラリです。グラフの描画ではなく、グラフ理論のモデルとアルゴリズムの方にフォーカスしています。とても使いやすかったので、紹介してみます。 無向グラフ UndirectedGraph<String, DefaultEdge> g = new SimpleGraph<String, DefaultEdge>( DefaultEdge.class); g.addVertex("a"); g.addVertex("b"); g.addVertex("c"); g.addEdge("a", "b"); g.addEdge("b", "c"); System.out.println(g.vertexSet()); System.out.println(g.edgeSet()); System.out.println(g.edgesOf("c"));
グラフ理論のサイトと書籍のご紹介 - 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: グラフの基礎です。次数やパス等の基本的な定
東京を走る路線のデータを使って、最短経路問題をダイクストラ法で解く - imHo
ダイクストラ法が小さなサンプルデータで動いたら、実際のデータを使ってみたくなるのが人情。東京を走る地下鉄のデータでやってみたいと思った。 JavaScriptとPrototype.jsとGoogleMapsAPIとすったもんだしたあげく、なんとか動くものができた。 502 Bad Gateway テストアプリはこちら JavaScriptのソースはここのhtmlに 駅や路線のデータは駅データ．ｊｐのものを使わせてもらいました。 使ったのは東京メトロ＋都営＋山手線 駅（ノード）の数は、同じ駅でも路線ごとで別にカウントして 322 駅同士をつなぐ線路（エッジ）の数は、徒歩や乗換えを含め 912 体感もっさり感じるけど、経路の検索以外のところがかなりかかってる Tips Prototype.js Array.without は超重い、使うな！ Hash.keys で返ってくるキーはすべて文字列に
ニコニコ動画の大規模なデータに対するタグ付けとリンク解析 - 武蔵野日記
ニコニコ動画データ分析研究発表会というのが開催されていたようだ。 タイトルや説明文はノイジーなので、動画につけられたタグを使うと割ときれいなデータとして可視化したりできる、という話は、はてなブックマークの関連エントリー機能のときも聞いたような話で、基本的にはインターネットユーザに無料でデータのタグ付けをしてもらっている、という話なんだろうな、と思う。以前紹介したRion Snow の論文 (彼は2005年に Microsoft Research でインターンし、2006年に Powerset (現在は Microsoft に買収済み)、2007年には Google でインターンした人物。ACL という自然言語処理のトップカンファレンスで2006年にベストペーパー受賞)で、 今年の Rion Snow のトークは、Amazon Mechanical Turkというシステムを使って、非常に安価
自然言語処理における類似度学習(機械学習における距離学習)について - 武蔵野日記
Twitter でグラフ理論に関する話題が上がっていたので、最近調べている距離学習(distance metric learning)について少しまとめてみる。カーネルとか距離(類似度)とかを学習するという話(カーネルというのは2点間の近さを測る関数だと思ってもらえれば)。 この分野では Liu Yang によるA comprehensive survey on distance metric learning (2005) が包括的なサーベイ論文として有名なようだが、それのアップデート(かつ簡略)版として同じ著者によるAn overview of distance metric learning (2007) が出ているので、それをさらに簡略化してお届けする(元論文自体本文は3ページしかないし、引用文献のあとに表が2ページあって、それぞれ相違点と共通点がまとまっているので、これを見ると非
Link Analysis and Related Topics - Home
2008年度 先端情報科学特論 II & IV リンク解析と周辺の話題 担当 新保 仁 shimbo@is.naist.jp 日時 2008/11/10, 11/17, 12/1, 12/8 (全 4 回) - 4限 15:10-16:40 場所 情報棟 L3 講義室 リンク解析は, グラフ (ネットワーク) データの構造から有用な情報を抽出するための, データマイニングの一研究分野です. この講義ではまず, リンク解析が取り扱う 2 種類の尺度 (重要度と関連度) について述べ, それぞれの代表的な計算手法を紹介します. 後半では, 近年機械学習分野で盛んに研究されているカーネルのうち, グラフ上の節点に対して定義されたカーネル (グラフカーネル) と, そのリンク解析への応用について紹介します. 第1回 11月10日 スライド 第2回 11月17日 スライド 第3回 12月1日
NAIST マニアック講義録: リンク解析と周辺の話題 - 武蔵野日記
紹介するのを忘れていたが、NAIST は冬学期になるといろいろとマニアックな講義が開講される。そのうち今年は shimbo さんのリンク解析と周辺の話題を紹介(それぞれに PDF がある)。 リンク解析は, グラフ (ネットワーク) データの構造から有用な情報を抽出するための, データマイニングの一研究分野です. この講義ではまず, リンク解析が取り扱う 2 種類の尺度 (重要度と関連度) について述べ, それぞれの代表的な計算手法を紹介します. 後半では, 近年機械学習分野で盛んに研究されているカーネルのうち, グラフ上の節点に対して定義されたカーネルと, そのリンク解析への応用について紹介します. ということで、いろいろなカーネルについて取り上げており、コンパクトにまとまっているので、このあたりに興味ある人にお薦め。 もう少し書くと、まずリンク解析とはなにか述べ、重要度と関連度について
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Draw figures with gnuplot
Amazon.co.jp: Graphs, Dioids and Semirings (Operations Research/Computer Science Interfaces Series, 41): Gondran, Michel, Minoux, Michel: 本
How Breadth First Search uses Queue - agwの日記
Algo 23 MSTP
PRoxy Diary(2009-02-04) - [研究室] STOCの論文の内容