Debuginfo

思考とアウトプット

Graph theory/グラフ理論

HITSアルゴリズムで@yapcasiaをランキングしてみる (+ 小ネタ::Perlスカウター)

以前のエントリーでyapcasiaのグラフを可視化してみました。はてぶもそこそこついたので調子にのって、第2弾をブログしてみます。温かい目でみてください^^;; グラフがあれば意外と色々な事ができます。HITSアルゴリズムというアルゴリズムがあります。これ…

@yapcasia をフォローしてる人のソーシャルグラフを可視化してみた 

ネットワークって面白いですよね。バラバシの新ネットワーク思考を読んでから、自然科学的好奇心をいつもくすぐる存在です。 で、今週末にGraph::D3というd3.js用のjsonを吐く単純なモジュールをMillaを使ってcpanにアップしたので、Net::Twitterを使ってyap…

グラフ理論::Similarity Flooding

今回はSimilarity Floodingというアルゴリズムの論文を読んでみました。Similarity Flooding : A Versatile Graph Matching Algorithm and its Application to Schema Matching論文を読んでいると、この方法には有向でラベル付きEdgeが必要のようです。イメ…

グラフ理論::Coupled node-edge scoring

注意:この記事は私の解釈です。間違っていたらつっこんでください。GED(Graph Edit Distance)はとりあえず置いといて、Coupled Node Edge Scoringにジャンル分けされている手法を勉強します。 (SimRankはどうやらInteractive Methodというらしい cf. Laura'…

GED (Graph Edit Distance) を調べてみる

グラフ間の編集距離。類似度に使われるわけだけど、ノードが増える度に指数上に計算量が増えるらしいのでいくつも論文がでているもよう。画像認識とかに使われているみたい。Bipartite Graph Matching for Computing the Edit Distance of Graphs http://vid…

グラフ理論::SimRank

グラフが関係するサービスを開発しようと考えているので、まずオーソリティな論文を読んでみた。 SimRank: A Measure of Structural-Context Similarity - Glen Jeh, Jeniffier Widom 肝はこれ。再帰で書けば答えがでるはず? と思って実装したら無限ループ…