Paris Kanellakis Theory and Practice Award はコンピュータの世界に重要な実用的インパクトを引き起こした理論的研究成果に対して贈られる賞だそうです．賞金は $10,000．Paris Kanellakis 氏はデータベース分野の研究者でしたが，1995 年に飛行機事故に巻…

定義 uncertain graph 各辺に対し存在する確率が与えられる リンク予測の出力，影響，protein-interaction （ノイズ） (k, η)-core 極大部分グラフ H, [deg_H(v) ≧ k] ≧ η 計算 小さい方から剥ぎ取る 確率の計算がちょっと入るが簡単な DP 応用実験 影響最大…

http://id.fnshr.info/2014/12/17/stats-done-wrong-toc/知っている部分もあったが面白かった (1) はじめに 統計的処理がきちんと行われず誤った結論が導きだされている論文は半数以上かもしれないらしい（医学の話） (2) データ分析入門 「p値」 ＝ どれだ…

最近，やはり動画配信の時代だなと思う．どうせなら高画質で配信をしたい．その方法を調べる． 前提：Web カメラは NG Logicool C920(t) は Web カメラとしては評判が良い．これは俺も持っているし，ICPC 放送の時とかはチョクダイもこれを持ってくる．定番…

博論執筆の現実逃避で自分の latex 執筆環境の改善を少し試みる． omake OMake つかって LaTeX コンパイルしたら簡単すぎて身長が5cm伸びた - 日記を書く [・w・] はやみずさん omake -P 快適！ OMakefile LaTeX用のOMakefile - Qiita だいたいこれをベース…

２つソフトが見つかった．どっちもすぐにマトモに動作した． n2witter twitterをニコニコ風にするツール「n2witter」 – uinyan．com Twitter を使う．このご時世なのにアカウントのパスワードを入れないといけない．鍵アカからの投稿が表示されるか等，要検…

問題 グラフ G，クエリ：頂点 v, 整数 k v を含む k-truss community をすべて列挙 k-truss vs. clique percolation clique percolation: コミュニティと呼べない，パラメータが３つも，NP-Hard k-truss: コミュニティの直径が |C|/k，高枝連結度，パラメタ…

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

後輩が国内イベント（全国大会）に行ってみたいと言っていたので調べてリストアップしてみる．日程は目安として前回のもの． 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: 匿名化前にグラフを操作して，匿名化後，特定頂点のラベ…