2013-11-01から1ヶ月間の記事一覧
01. Introduction $x = Ab$ を解きましょう． 直接法は疎でも $O(n^2)$ はかかってしまうので，反復法が良さそう $k$ 回目の反復で得られた解を $x^k$，残差を $r^k = b - Ax^k$ とおく Jacobi 法，Gauss-Seidel 法 02. Krylov Subspaces and Arnoldi Iterat…
問題設定 Excel とか．ユーザはプログラミングができないが，テーブルに対する作業を自動化したい． 例えば，いろんなフォーマットで書かれた電話番号たちを，統一したフォーマットに直す． 小数の例から，作業をプログラムとして学習し，自動化できないか？…
辺を2方向の向きで区別するため，e=xy の時，f(e, x, y) と f(e, y, x) という書き方をする Circulations circulation：f(e, x, y) = -f(e, y, x) で f(v, V) = 0 bridge なら流量 0 Flows in networks network：グラフ＋capacity function, flow：始点終点 …
-vertex coloring, chromatic number $\chi(G)$ edge coloring, chromatic index (=edge chromatic number) $\chi'(G)$ $χ'(G)$ は $\Delta(G)$ or $\Delta(G) + 1$ Coloring maps and planar graphs 4 色定理（5 色なら証明簡単） triangle-free -> 3-colo…
vertex connectivity, edge connectivity cut vertex (=articulation point), bridge block (= maximal 2-connected subgraphs) 2-connected 任意の 2-connected graph はパスの付加を繰り返すことで構成できる 3-connected 3-connected で |V|>4 なら，ある…
k-factor = 全域部分グラフであって，全頂点の次数が k 2 部グラフのマッチング 2 部マッチングのサイズ ＝ 頂点被覆のサイズ $|N(S)| \geq |S|$ for all $S \subseteq A$ stable matching は常に存在 一般グラフのマッチング G が 1-factor 持つ ⇔ $q(G-S) …
概要 スケールフリーネットワーク上のランダムウォーク ある次数 k への到達のしやすさを 3 パターンに分ける 用語＆既存の結果 スペクトル次元 スペクトル次元 d_s は ρ(λ) 〜 λ^{d_s / 2 - 1} ρ(λ) は固有値の分布（確率密度関数） RTO (return to the ori…
問題 頂点 v, k が与えられるので，v を含む k-clique percolation (的なもの) を即返す 前処理なし （この問題を考えたこと自体が貢献） 拡張した k-clique percolation (α, γ)-OCS: γ-quasi k-clique，α頂点共有なら枝を張る アルゴリズム 普通に探索する …
問題 PPR の top-k を前処理なしで高速に求める similarity は求めない，top-k の順序を exact に求める 提案手法 (Castanet) 4.2 Similarity estimation 長さ i の RW (jump なし) での分布 R_i[u] から lower bound と upper bound が得られる 4.3 Subgrap…
問題 p2p PPR top-k PPR threshold PPR （しきい値以上を取得） 提案手法 3.2.1 行列． s = c{I-(1-c)A}^{-1} d なので，I-(1-c)A を QR 分解する クエリは，cR^(-1) の v 行と Q^T d の内積 cR^(-1) と Q^T を覚えておくっぽい 3.2.2 Q, R をスパースにする…
問題 PPR と言いつつ RWR 手法 アルゴリズム 1 MC End Point ランダムウォークを始点から実際にやりまくります 終点の至った分布を RWR アルゴリズム 2 MC Complete Path ランダムウォークを始点から実際にやりまくります 終点だけじゃなくて，途中でも，通…
問題：三角形を全列挙 M: size of memory, B: size of disk block, K: #triangles 既存手法 em-cf, em-ni, graph partition [james cheng] 提案手法：MGT 次数が小さいグラフに変換 次数が cM/2 より大きい頂点を発見 次数の大きさで順番づけ，DAG になる cM…
問題 頂点間でどのぐらい相関があるかだけわかってて，グラフを復元する？ 手法 saliencing transformation S_{ij} global response matrix G, local response matrix S S_{ij} を愚直に求めるのは O(n^2) の連立方程式なので NG 対角項を近似して，G_{ii}=1…
