読者です 読者をやめる 読者になる 読者になる

Reverse Top-k Search using Random Walk with Restart (VLDB'14)

RWR Bookmark Coloring Algorithm (BCA) 受け取って少し確定して残りを配るタイプのやつ ハブを活用 ハブの頂点は受け取っても配らないことにして,後でまとめて影響を計算 Reverse Top-K RWR Query 頂点 q と k → 頂点 u からのの RWR で q が top-k に入る…

国内学会の全国大会の大まかな日程

後輩が国内イベント(全国大会)に行ってみたいと言っていたので調べてリストアップしてみる.日程は目安として前回のもの. DEIM(データ工学と情報マネジメントに関するフォーラム(日本データベース学会年次大会)) http://db-event.jpn.org/deim2015/ …

Path Skyline の計算サーベイ

厳密列挙アルゴリズム (1984) On a multicriteria shortest path problem Martin's Algorithm (元祖 Label Setting Approach) (JACM'91) Multiobjective A* 最初に single source でなく point-to-point にして global domination を導入したっぽい (EJOR'92…

クラウドストレージを用いた個人データのバックアップ法の比較

クラウドストレージを使って,個人データの簡単かつ安心なバックアップを実現したい.現在の選択肢を調べてみた. 前提 自分がバックアップしたいデータは,写真が中心.現在 1TB 弱.(ただ,将来的には数 TB 行きそう.) Amazon S3/Glacier 有名なヤツ.1…

pixiv のタグ情報を用いた「ラブライブ! School idol project」のカップリングネットワークの構築

はじめに ネットワーク解析やグラフアルゴリズムの研究者がアルゴリズムを実装した際,動作確認のために最初に実行する toy example をどうするかというのは意外と悩ましい.パスグラフやグリッドグラフのような高い対称性を持つグラフや小さすぎるグラフで…

Online Topic-aware Influence Maximization Queries (EDBT'14)

topic-aware IC model (ICDM'12) 情報と辺にベクトルがあって,内積で伝搬確立が決まる http://francescobonchi.com/icdm12.pdf 提案手法 1000 点ぐらい代表的なベクトルを作って,先に計算しておく クエリが来たら適当に混ぜて答えを作る 怪しい謎の努力が…

Collaborative learning in networks (PNAS'12)

模倣と集合知 面白い実験 Goldon (1907) 牛を見せて,体重の推測値を考えさせる 専門家 1 人の推測よりも,大勢が投票した結果を平均した結果のほうが誤差が小さかった 集合知が形成されるための条件 意見の多様性 個人の判断の独立性 課題:多様性を保ちつ…

SIGMOD 2014

グラフ Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency Tripartite Graph Clustering for Dynamic Sentiment Analysis on Social Media Querying K-Truss Community in Large and Dynamic Graphs Reachability Queries o…

Greedy Algorithms and Local Search (Chapter 2, The Design of Approximation Algorithms)

2.1 Scheduling jobs with deadlines on a single machine 問題:スケジューリング.max(締切を過ぎた時間) を最小化したい NP-hard (0 以下か否かの判定だけでも strongly NP-hard) 以下,d_i アルゴリズム:Greedy に締切が近いやつからやっていく 近似値…

An Introduction to Approximation Algorithms (Chapter 1, The Design of Approximation Algorithms)

Set Cover 問題をひたすら扱う Deterministic LP rounding 要素の最大次数を f とする LP を解き,1/f 以上になっているやつを 1 にする f 近似 Deterministic dual LP rounding 相補性定理 Primal-dual を使うと簡単に Dual 解が求まる Greedy 「コスト/新…

関数ポインタと関数オブジェクトと仮想関数の速度比較

趣旨 アルゴリズム内の処理の一部を指定させる一般的な方法には以下がある. 関数ポインタを使う (qsort 等) 関数オブジェクトを使う (std::sort 等) 仮想関数を使う これらで性能がどう変化するかを測定した. 結果概要 wandbox にて実験した:http://melpo…

CPLEX 色々

探索ノード数を得る IloCplex cplex(model); ... cplex.solve(); cout << "Nodes: " << cplex.getNnodes() << endl; カット数を得る cout << "Cuts: " << cplex.getNcuts(IloCplex::CutClique) << endl; http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r4/i…

羽田の飛行機に乗るために間違えて成田に行ってしまった人の話

I 田さんが間違えて行ってしまったが起死回生したので有用なメモとしてその時の記録を残す 14:20 成田着 → 爆速でタクシーに乗る 15:20 羽田 国内線第二ターミナルに何故か降ろされる(ANA は国内線ですら第一なので完全に謎) → バスで移動 15:40 羽田 国際…

国際ジャーナル

そろそろジャーナルにも論文を出してみたいのですが,本当にどこがいいのか分からない……ダレカタスケテー DB 系 ランキング http://academic.research.microsoft.com/RankList?entitytype=4&topdomainid=2&subdomainid=18&last=10 ACM TODS 多分超有名?でも会議論…

SDM'14 Accepted Papers

VoG: Summarizing and Understanding Large Graphs Local Learning for Mining Outlier Subgraphs from Network Datasets Triangle counting in streamed graphs via small vertex covers Laplacian Spectral Properties of Graphs from Random Local Sample…

EDBT'14 Accepted Papers

http://www.edbticdt2014.gr/index.php/edbt-accepted-papersグラフかつとても興味がある 166 Renê R. Veloso, Loïc Cerf, Wagner Meira Junior and Mohammed J. Zaki Reachability Queries in Very Large Graphs: A Fast Refined Online Search Approach 26…

ICDE'14 Accepted Papers

http://ieee-icde2014.eecs.northwestern.edu/accepted.html特に気になるグラフ系 533 Fast Incremental SimRank on Link-Evolving Graphs 551 Fast Top-K Path-based Relevance Query on Massive Graphs 203 Efficient Top-K Closeness Centrality Search 2…

Delineating Social Network Data Anonymization via Random Edge Perturbation (CIKM'12)

問題:匿名化 手法 random edge pertubation 一定確率 μ で辺の有無を入れ替える (perturbation probability) 特徴量の推定 特徴量は,変化してしまうが,推定ができる(最尤推定する) density, degree distribution, transitivity, modularity 独立でラン…

Locating the Source of Diffusion in Large-Scale Network (PRL'12)

問題 ネットワーク上で拡散が起こる 一部の頂点のみを観測して,発信源を推定する モデル 最初は発信源だけが情報を持っている 隣接する頂点に情報を伝えるのにかかる時間は正規分布 一部の頂点はオブザーバで観測した時刻が分かる 推定アルゴリズム 最尤推…

Scalable kernels for graphs with continuous attributes (NIPS'13)

田部井さんのスライドを見ればだいたい分かる http://www.slideshare.net/tbyasu/nips2013-scalable-kernels-for-graphs-with-continuous-attributes 問題 グラフ同士のカーネル しかもグラフの頂点には連続値ベクトルの属性がついている 辺には重み(長さ)…

Random Graphs (Chapter 11, Graph Theory)

http://iwiwi.m12.coreserver.jp/iwi.tc/wiki/index.php?%E6%9B%B8%E7%B1%8D%2FGraph%20Theory%2F11.%20Random%20Graphs The notion of a random graph Erdos-Renyi model $G(n, p)$ $q = 1 - p$ とおく 独立集合 $ P[\alpha(G) \geq k] \leq {n \choose k}q…

Quantifying Long-Term Scientific Impact (Science 2013)

バラバシのグループ 論文事の非引用回数の時系列変化を予測する研究 引用ネットワークの入次数の変化 (論文の価値 = 引用数) モデル BA に類似 論文本来の魅力×優先的選択×魅力の時間的減衰 結果 凄い!全部の論文をスケールしたら全部同じ累積分布に!

High strength-of-ties and low mobility enable the evolution of third-party punishment (Proc. R. Soc. B 2013)

概要 グラフを考慮した進化シミュレーションで「第三者罰」が進化するかを検討 背景 罰を導入することで協力を促す 今回の罰:特別な形態の「第三者罰」というもの 普通のやつは損を被った人が直接非協力者を罰する 今回は,直接の被害者でない人が罰する 先…

Wherefore Art Thou R3579X?: Anonymized Social Networks, Hidden Patterns, and Structural Steganography (WWW'07)

MkECS の応用だ!!!! 概要 頂点に適当な ID を割り当てるだけの匿名化は不十分である (タイトルはロミオとジュリエットのセリフで名前をIDに置き換えている) 攻撃 b 頂点を特定したい active attack: 匿名化前にグラフを操作して,匿名化後,特定頂点のラベ…

Efficiently Anonymizing Social Networks with Reachability Preservation (CIKM'13)

問題 reachability を保って anonymize k-degree anonymous:各 v が k-1 頂点以上は同じ次数の頂点を持つ これは k 匿名性というやつの自然な拡張になっていて,匿名性をコレで定義するのは既存 辿りつける頂点ペアの集合をできるだけ本来に近づける アルゴ…

Cascading behaviour in complex socio-technical networks (Journal of Complex Networks 2013)

題材 個人の行動と集団の振る舞いを繋ぐす類モデル cascading behavior (噂・情報の伝搬) cascading behaviorの数理モデル threshold models global cascade が起こるか起こらないかの条件の解析 [Watts 02] epidemic models SRI, SIS, ... Stifler Model:周…

Hamilton Cycles (Graph Theory, Chapter 10)

Siffocoemt conditions 頂点数3以上,すべての頂点の次数が n/2 位上ならハミルトニアン 頂点数3以上,α(G)≦κ(G) ならハミルトニアン α:最大独立集合,κ:連結性 頂点数3以上連結,任意の induced path uvw で d(u)+d(w)≧|N(u)∪N(v)∪N(w)| ならハミルト…

More is Simpler: Effectively and Efficiently Assessing Node Pair Similarities Based on Hyperlinks (PVLDB 2013)

概要:SimRank を改良した SimRank* を提案 復習 SimRank 「似ているノードからリンクされているノードは似ている」 SimRank (別の書き方) ←対角成分が間違ってる 不満:同じ長さのパスが存在しないと影響が来ない! 提案手法:g-SimRank*, e-SimRank* 実験 …

Maximizing Social Influence in Nearly Optimal Time (SODA'13)

Quasilinear-time Algorithm ハイパーグラフの構築 各ノード「に」伝搬するノード集合を計算する(転置グラフを用いる) シードを1つランダムに選び逆向きシミュレート(BFS) 訪れたノード集合をハイパーエッジにする アクティブノードの総数がある程度大き…

Finding the k Shortest Paths (SICOMP'98)

s, t が与えられるので,k 本の最短路を計算する O(m + n log n + k) でできるよっていう論文 キーとなるアイディア t からの逆最短路木を T とする 例によって,ポテンシャルを使って辺の重みを変換する.T に含まれる辺の重みは 0 になる. パス p は,T …

Applied Numerical Linear Algebra

01. Introduction $x = Ab$ を解きましょう. 直接法は疎でも $O(n^2)$ はかかってしまうので,反復法が良さそう $k$ 回目の反復で得られた解を $x^k$,残差を $r^k = b - Ax^k$ とおく Jacobi 法,Gauss-Seidel 法 02. Krylov Subspaces and Arnoldi Iterat…

Spreadsheet Data Manipulation Using Examples (CACM'12)

問題設定 Excel とか.ユーザはプログラミングができないが,テーブルに対する作業を自動化したい. 例えば,いろんなフォーマットで書かれた電話番号たちを,統一したフォーマットに直す. 小数の例から,作業をプログラムとして学習し,自動化できないか?…

Flows (Grpah Theory, Chapter 6)

辺を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:始点終点 …

Coloring (Graph Theory, Chapter 5)

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

Connectivity (Graph Theory, Chapter 3)

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 なら,ある…

Matching, Covering and Packing (Graph Theory, Chapter 2)

k-factor = 全域部分グラフであって,全頂点の次数が k 2 部グラフのマッチング 2 部マッチングのサイズ = 頂点被覆のサイズ $|N(S)| \geq |S|$ for all $S \subseteq A$ stable matching は常に存在 一般グラフのマッチング G が 1-factor 持つ ⇔ $q(G-S) …

First Passage Time for Random Walks in Heterogeneous Networks (PRL'12)

概要 スケールフリーネットワーク上のランダムウォーク ある次数 k への到達のしやすさを 3 パターンに分ける 用語&既存の結果 スペクトル次元 スペクトル次元 d_s は ρ(λ) 〜 λ^{d_s / 2 - 1} ρ(λ) は固有値の分布(確率密度関数) RTO (return to the ori…

Online Search of Overlapping Communities (SIGMOD'13)

問題 頂点 v, k が与えられるので,v を含む k-clique percolation (的なもの) を即返す 前処理なし (この問題を考えたこと自体が貢献) 拡張した k-clique percolation (α, γ)-OCS: γ-quasi k-clique,α頂点共有なら枝を張る アルゴリズム 普通に探索する …

Efficient Ad-hoc Search for Personalized PageRank (SIGMOD'13)

問題 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…

Efficient Personalized PageRank with Accuracy Assurance (KDD'12)

問題 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 をスパースにする…

Quick Detection of Top-k Personalized PageRank Lists (WAW'11)

問題 PPR と言いつつ RWR 手法 アルゴリズム 1 MC End Point ランダムウォークを始点から実際にやりまくります 終点の至った分布を RWR アルゴリズム 2 MC Complete Path ランダムウォークを始点から実際にやりまくります 終点だけじゃなくて,途中でも,通…

Massive Graph Triangulation (SIGMOD'13)

問題:三角形を全列挙 M: size of memory, B: size of disk block, K: #triangles 既存手法 em-cf, em-ni, graph partition [james cheng] 提案手法:MGT 次数が小さいグラフに変換 次数が cM/2 より大きい頂点を発見 次数の大きさで順番づけ,DAG になる cM…

Network link prediction by global silencing of indirect correlations (Nature Biotechnology 2013)

問題 頂点間でどのぐらい相関があるかだけわかってて,グラフを復元する? 手法 saliencing transformation S_{ij} global response matrix G, local response matrix S S_{ij} を愚直に求めるのは O(n^2) の連立方程式なので NG 対角項を近似して,G_{ii}=1…

Piggybacking on Social Networks (VLDB'13)

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

Spectral Analysis of Communication Networks Using Dirichlet Eigenvalues (WWW'13)

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

Dynamic social networks promote cooperation in experiments with humans (PNAS'11)

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

malloc の旅 (glibc 編)

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 で読むより4倍ぐらい速い感じ 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, ZDD, フロンティア法, Graphillion

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

2-hop index のラベルサイズの下界

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