後輩が国内イベント（全国大会）に行ってみたいと言っていたので調べてリストアップしてみる．日程は目安として前回のもの． DEIM（データ工学と情報マネジメントに関するフォーラム（日本データベース学会年次大会）） http://db-event.jpn.org/deim2015/ …
厳密列挙アルゴリズム (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…
topic-aware IC model (ICDM'12) 情報と辺にベクトルがあって，内積で伝搬確立が決まる http://francescobonchi.com/icdm12.pdf 提案手法 1000 点ぐらい代表的なベクトルを作って，先に計算しておく クエリが来たら適当に混ぜて答えを作る 怪しい謎の努力が…
模倣と集合知 面白い実験 Goldon (1907) 牛を見せて，体重の推測値を考えさせる 専門家 1 人の推測よりも，大勢が投票した結果を平均した結果のほうが誤差が小さかった 集合知が形成されるための条件 意見の多様性 個人の判断の独立性 課題：多様性を保ちつ…
グラフ 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…
2.1 Scheduling jobs with deadlines on a single machine 問題：スケジューリング．max(締切を過ぎた時間) を最小化したい NP-hard (0 以下か否かの判定だけでも strongly NP-hard) 以下，d_i アルゴリズム：Greedy に締切が近いやつからやっていく 近似値…
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…
探索ノード数を得る 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 多分超有名？でも会議論…
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…
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…
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…
問題：匿名化 手法 random edge pertubation 一定確率 μ で辺の有無を入れ替える (perturbation probability) 特徴量の推定 特徴量は，変化してしまうが，推定ができる（最尤推定する） density, degree distribution, transitivity, modularity 独立でラン…
問題 ネットワーク上で拡散が起こる 一部の頂点のみを観測して，発信源を推定する モデル 最初は発信源だけが情報を持っている 隣接する頂点に情報を伝えるのにかかる時間は正規分布 一部の頂点はオブザーバで観測した時刻が分かる 推定アルゴリズム 最尤推…
田部井さんのスライドを見ればだいたい分かる http://www.slideshare.net/tbyasu/nips2013-scalable-kernels-for-graphs-with-continuous-attributes 問題 グラフ同士のカーネル しかもグラフの頂点には連続値ベクトルの属性がついている 辺には重み（長さ）…
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…
バラバシのグループ 論文事の非引用回数の時系列変化を予測する研究 引用ネットワークの入次数の変化 （論文の価値 ＝ 引用数） モデル BA に類似 論文本来の魅力×優先的選択×魅力の時間的減衰 結果 凄い！全部の論文をスケールしたら全部同じ累積分布に！
概要 グラフを考慮した進化シミュレーションで「第三者罰」が進化するかを検討 背景 罰を導入することで協力を促す 今回の罰：特別な形態の「第三者罰」というもの 普通のやつは損を被った人が直接非協力者を罰する 今回は，直接の被害者でない人が罰する 先…
MkECS の応用だ!!!! 概要 頂点に適当な ID を割り当てるだけの匿名化は不十分である （タイトルはロミオとジュリエットのセリフで名前をIDに置き換えている） 攻撃 b 頂点を特定したい active attack: 匿名化前にグラフを操作して，匿名化後，特定頂点のラベ…
問題 reachability を保って anonymize k-degree anonymous：各 v が k-1 頂点以上は同じ次数の頂点を持つ これは k 匿名性というやつの自然な拡張になっていて，匿名性をコレで定義するのは既存 辿りつける頂点ペアの集合をできるだけ本来に近づける アルゴ…
題材 個人の行動と集団の振る舞いを繋ぐす類モデル cascading behavior (噂・情報の伝搬) cascading behaviorの数理モデル threshold models global cascade が起こるか起こらないかの条件の解析 [Watts 02] epidemic models SRI, SIS, ... Stifler Model：周…
Siffocoemt conditions 頂点数３以上，すべての頂点の次数が n/2 位上ならハミルトニアン 頂点数３以上，α(G)≦κ(G) ならハミルトニアン α：最大独立集合，κ：連結性 頂点数３以上連結，任意の induced path uvw で d(u)+d(w)≧|N(u)∪N(v)∪N(w)| ならハミルト…
概要：SimRank を改良した SimRank* を提案 復習 SimRank 「似ているノードからリンクされているノードは似ている」 SimRank (別の書き方) ←対角成分が間違ってる 不満：同じ長さのパスが存在しないと影響が来ない！ 提案手法：g-SimRank*, e-SimRank* 実験 …
Quasilinear-time Algorithm ハイパーグラフの構築 各ノード「に」伝搬するノード集合を計算する（転置グラフを用いる） シードを１つランダムに選び逆向きシミュレート(BFS） 訪れたノード集合をハイパーエッジにする アクティブノードの総数がある程度大き…
s, t が与えられるので，k 本の最短路を計算する O(m + n log n + k) でできるよっていう論文 キーとなるアイディア t からの逆最短路木を T とする 例によって，ポテンシャルを使って辺の重みを変換する．T に含まれる辺の重みは 0 になる． パス p は，T …
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 とか．ユーザはプログラミングができないが，テーブルに対する作業を自動化したい． 例えば，いろんなフォーマットで書かれた電話番号たちを，統一したフォーマットに直す． 小数の例から，作業をプログラムとして学習し，自動化できないか？…
