線形代数（連続系アルゴリズムのノート）

  • LU 分解
    • 1+(n-1) の形に分解して立式して冷静になり，再帰的に分解すればよい
  • べき乗法
    • ランダムではじめる → 最大固有値のベクトルが求まる．
      • 初期値のベクトル x_0 = Σc_i u_i だと思うと，x_k = (Σλ_i^k c_i u_i) / 定数
    • だから初期値のベクトルがなんかサブスペースとか入ってたら最大のやつとは限らないのが求まるのかな
  • 逆反復法
    • (A-aI) の固有値は λ_i-a．(A-aI)^-1 の固有値は 1/(λ_i-a)
      • a に最も近い固有値が絶対値最大になる
    • a = x_k^T A x_k / (x_k^T x_k) としてやると A の固有値に近づけることができる
  • 条件数
    • K(A) = ||A|| ||A^-1||
    • 方程式 Ax=b の解 x の相対誤差は，最悪の場合，係数行列の相対誤差の条件数倍
    • 反復改良というのをやって近づけるということをやることもありえる
  • Householder 変換
    • H = I - 2v v^T
    • 鏡像変換である： y = Hx → y と x は v に垂直な平面に関して対称（計算すればすぐわかる）
  • QR 変換

なんか復習したいと思ったものがあまり出て来なかった．どこでやったんだろ・・・

大規模グラフの可視化の手法・ソフトウェア

面白そうなので気が向いた時に調べる．随時情報追加予定．

基礎

なんかのソフトウェアパッケージの論文より引用 http://www.necsi.edu/events/iccs6/papers/c1602a3c126ba822d0bc4293371c.pdf

Graph layouts The following layout generators are part of igraph:  simple
circle and sphere layouts, random layouts  Fruchterman-Reingold layout, 2D
and 3D [8]  Kamada-Kawai layout, 2D and 3D [9]  spring embedder layout 
LGL layout generator for large graphs [15]  Grid-based Fruchterman-Reingold
layout for large graphs  Reingold-Tilford layout [14] for trees.

このへんのキーワードも調べるか

手法のカテゴリ
Fruchterman-Reingold layout

T.M.J. Fruchterman and E.M. Reingold introduced a "global temperature" that controls the step width of node movements and the algorithm's termination. The step width is proportional to the temperature, so if the temperature is hot, the nodes move faster (i.e, a larger distance in each single step). This temperature is the same for all nodes, and cools down at each iteration. Once the nodes stop moving, the system terminates.

Kamada-Kawai Model

新しそうな気になるもの

Large Graph Layout

MST を使って順に頂点を増やしながら配置を行う．バネモデルだが，バケット法を使って計算量を減らしている．

SFDP

web-Google とかを可視化したとき，岩田が作ってた画像で出てきたような，大量のクリークみたいなのが全く写っていない．全頂点描画するとこうなってしまうものなんだろうか．

@tatsushi_do_ob さんのやつ

やっぱこういうの研究するのは物理系の人が強いんかなぁ．物理っぽいシミュレーションとかもろに関係しているわけだし．

その他

引っかかった論文

AAAI 2012

Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process

  • highly influential users を探したい
  • time-critical influence maximization
    • 締め切り付き
  • Independent Cascade model (IC)
    • 時間の遅延のモデルっぽい
  • submodularity → aproximate が greedy でできる
  • しかし、微妙なのでアルゴリズム作る
    • 1. DP
    • 2. 問題を変換し既存手法を適用
  • greedy algo より数桁早く、結果は近い

Search Algorithms for M Best Solutions for Graphical Models

  • 組合せ最適化問題
    • Best-First search, Branch-and-Bound search を使うもの
  • m 個の最良の解を見つける (m-best 問題)
  • 提案手法 m-A^*
    • A* を m-best 問題に拡張したもの
  • 適用先

Discovering Spammers in Social Networks

  • Renren という中国の SNS 企業の人が著者に入っている
  • 問題：スパマーを発見したい
  • 既存手法
    • プライバシーやリソースの関係で、全てのコンテンツや行動をモニターすることができなくなっている
    • したがって、topology-based や content-classification-based な手法は使えなくなってしまった
  • 提案手法
    • Supervised Matrix Factorization method with Social Regularization (SMFSR)
    • social activity と social relation を組み合わせる

Social Context-Aware Trust Network Discovery in Complex Contextual Social Networks

  • trust network (social networks)
  • context, contextual network とは？？
    • abstract だけじゃ分からない
  • Social Context-Aware trust Network discovery algorithm (SCAN)
    • Monte Carlo method
  • 性能がいいらしい

Dynamic Matching via Weighted Myopia with Application to Kidney Exchange

  • 肝臓を交換する、ドナー提供者と患者のマッチングっぽい
  • 既存のものは static だが、dynamic にやったほうがよいだろうという提案
  • 結構この肝臓ドナー特有の話っぽい、データがない？

Searching for Optimal Off-Line Exploration Paths in Grid Environments for a Robot with Limited Visibility

  • we present a method to calculate an approximation of the optimal (shortest) exploration path in an arbitrary environment
  • a mobile robot with limited visibility
  • 提案手法：A* 探索をする
  • ちょっと読んだだけでは、何がわかっていて何がわかってない状況なのかさっぱりわからない
    • on-line が標準的な設定らしいが、どう off-line なのか謎

Shortest paths in less than a millisecond

Rachit Agarwal, Matthew Caesar, Philip Brighten Godfrey, and Ben Y. Zhao. 2012. Shortest paths in less than a millisecond. In Proceedings of the 2012 ACM workshop on Workshop on online social networks (WOSN '12). ACM, New York, NY, USA, 37-42. DOI=10.1145/2342549.2342559 http://doi.acm.org/10.1145/2342549.2342559

Orkut (2 億 edges) で exact SPQ，ただしごく一部の点対には答えられない

続きを読む

On k-skip shortest paths

Yufei Tao, Cheng Sheng, and Jian Pei. 2011. On k-skip shortest paths. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data (SIGMOD '11). ACM, New York, NY, USA, 421-432. DOI=10.1145/1989323.1989368 http://doi.acm.org/10.1145/1989323.1989368

続きを読む