辺を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…

ツイッターみたいな購読ベースの SNS サービス 問題 有向グラフ＝購読関係，u->v := uの情報をvが購読 クエリ：Produce (発信)，Consume (最新情報取得) push edge と pull edge を決めておく push edge: 始点で produce が起きた瞬間，新データを全部伝搬 p…

主張 無限グラフの固有値に比べて，切り取ってできた有限グラフの固有値はよくない 境界を考慮して "Dirichlet 固有値" を使うことを提案 例 有限の木と無限の木は，全然違う 複雑ネットワークの構造 core-whisker 各ペアに流量 1 のフローを流すと，O(n^2) …

背景 「協力」という行動について．協力＝コストを払って他者に資源を与える行動 進化ゲーム理論．非協力行動より協力行動のほうが有利になるような原理を説明したい（むずい） 静的なネットワークでなく，動的なネットワークと思うと……？ 実験概要 N 人囚人…

malloc の動画 http://www.youtube.com/watch?v=0-vWT-t0UHg http://www.slideshare.net/kosaki55tea/glibc-malloc http://togetter.com/li/574262 すごい分かりやすかった K&R Malloc (first fit) 次の空き領域へのポインタを空き領域の先頭に置いておく fr…

ifstream で読むより４倍ぐらい速い感じ inline bool readeof(FILE *fp) { for (;;) { int c = getc(fp); if (c == EOF) { return true; } else if (isspace(c)) { continue; } else { ungetc(c, fp); return false; } } } inline int readint(FILE *fp) { i…

詳しい資料へのポインタを示しつつ，自分が読んで理解した範囲の簡潔なまとめを書きます． BDD 入門 湊先生の授業が詳しく分かりやすい． http://www-alg.ist.hokudai.ac.jp/~minato/alg2013.html 概念自体 図を一個見れば一発で理解できる DAG で，各中間ノ…

http://research.microsoft.com/en-us/people/goldberg/hl.pdfLabel Sizes一般の場合：$\Omega^*(n)$[Gavoille et al. 01]

Research Session 3: Big data frameworks #52 TurboGraph: A Fast Parallel Graph Engine Handling Billion-scale Graphs in a Single PC Research Session 4: Graph mining #583 Denser than the densest subgraph: extracting optimal quasi-cliques with…

モデル：Independent Cascade Model アルゴリズム IR 適当なDP的なのだと重複して数えてしまうけど，適当に定数をかけて調整して，見積もろう アルゴリズム IRIE かぶったところを選んでしまうのを防ごう 頂点vが，既に選んだSにより勝手にactivateされる確…

クラスター性，common neighbor の数 2 種類のネットワーク！ integrative networks: 重みが大きい → common neighbor が多い dispersive networks: 重みが大きくても common neighbor 多いとは限らない link clustering coefficient C_L = n_c / n_t excess…

イベントの発生だけを観測できる．流れのグラフ構造を推定したい． 手法の提案，検証，実データ（神経データ）への適用 手法 最初のシードは 1 点 1 つ前のタイムステップでのイベントのみが次のステップに影響 ベイズの法則．推定パラメータ p_{ij} (ノード…

spatial network のモデル ただし，木 モデル コスト N ノードが [0,L)*[0,L) 上にランダムに分布，1 つの頂点を根に選ぶ 各タイムステップ，木が 1 つずつ大きくなる 孤立点を，earning R が最大となる相手と接続する R_ij = B_ij - C_ij Expected traffic …

問題 複数台でグラフを分割して格納・処理 どのようにグラフを分割するか 頂点集合を分ける，サイズは |V|/K の (1+ε) 倍まで OK またがる辺の本数を最小化 ストリーミング；v が１つず渡されるので，その近傍の情報から答える ヒューリスティクス balanced:…

超簡単にファイルを並列で処理できる． ls archive/*.bz2 | parallel -j+0 "bzcat {} | ruby hoge.rb > out/{/.}.tsv" {} でファイル名，{/.} でファイル名のディレクトリ名とパスを取り除いた部分

交通ネットワークのモデル，数値シミュレーション 現実の道路ネットワークの特徴 リンク数とノード数：E ~ 1.44N リンクの長さの総和 vs ノード数：√n に比例 （実験がちょっと怪しい） セル面積：べき分布 セルの形状の非一様性：幅広い分布 モデル：成長ネ…

ターミナルで Alt+B, Alt+F が使えるように http://askubuntu.com/questions/140209/how-to-get-altb-and-altl-to-work-in-the-terminal Open the terminal window, go to "edit->keyboard shortcuts" and unselect the first check box "Enable menu access…

誤情報が拡散してしまった！ ソレを訂正する情報を流し，できるだけ多くの人に訂正情報を先に見せる モデル：Multi-campaign ICM 誤情報 C の拡散，訂正情報 L の拡散，早くついたほうが信じられる 状況：Eventual influence limitation problem (EIL) r タ…

hidden distance を取りれたモデル 手法概要 頂点間の hidden distance hidden distance に基づいたスケールフリーなネットワーク（power law, cluster coefficient) hidden distance に関する greedy search ネットワーク生成 hidden distance が小さいと結…

例 Erdos-Renyi グラフ G The Four Functions Theorem N: {1..n}, P(N): all subsets 4 つの関数があって，集合2つについてホゲ（∩, ∪）が満たされれば，冪集合２つに対してピヨ． 冪集合だけじゃなく，分配速を満たす束にも拡張可 Corollary: 分配速を満た…