todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Fast Single-Pair SimRank Computation」で検索した結果

• Fast Single-Pair SimRank Computation
  Fast Single-Pair SimRank Computation Pei Li, Hongyan Liu, Jeffrey Xu Yu, Jun He, Xiaoyong Du SDM 2010 概要 全点対間SimRankはあるけど、クエリしたいよねー ペアのSimRankを高速に計算するよ 精度を落とさずにやったね SimRank 一般的には下の式を収束するまで反復 $$ R_{k+1}(a,b) = \frac{C}{|I(a)||I(b)|}\sum_{i \in I(a)}\sum_{j \in I(b)}R_k(i,j) $$ 行列でも書ける Q. SimRankってそもそも何だ？ A. 2人が出会うまでのランダムウォーク M_k(a,b) k...
• 論文一覧
  ...works Fast Influence-based Coarsening for Large Networks 予測 Prediction of Information Diffusion Probabilities for Independent Cascade Model Learning Continuous-Time Information Diffusion Model for Social Behavioral ... Learning Influence Probabilities In Social Networks Learning Stochastic Models of Information Flow Predicting Information Diffusion on Social Net...
• 気になった論文
  ...raphs Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication Spectral Partitioning of Random Graphs FOCS 2002 Correlation Clustering Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems FOCS 2004 0(sqrt (log n)) Approximation to SPARSEST CUT in O(n2) Time Maximum Matchings via Gaussian Elimination A Simple Line...
• More is Simpler: Effectively and Efficiently Assessing Node Pair ...
  More is Simpler Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks Weiren Yu, Xuemin Lin, Wenjie Zhang, Lijun Chang, Jian Pei VLDB 2014 概要 SimRankを改良 SimRank* 速い旨い SimRankの書き方 行列でシンプルに書けるともーじゃん？ S=C(QSQ^T)+(1-C)I_n 嘘であった(´・ω・`) この論文どうするんでしょう みんなまちがえている 提案手法 何が問題？ 2つのノードが類似しているためには、2つ...
• IMRank: Influence Maximization via Finding Self-Consistent Ranking
  IMRank Influence Maximization via Finding Self-Consistent Ranking Suqi Cheng, Huawei Shen, Junming Huang, Wei Chen, Xueqi Cheng SIGIR 2014 概要 貪欲アルゴリズムで選ぶと，ゲインは単調非増加 逆にゲインが単調なランキング（順列）は割りと良さそう？ 適当なランキングから初めて，並び替えを反復 ゲインの計算はヒューリスティック 提案手法 自己整合(self-consistent)な順列 以下を満たすランキング $$ r [n] \to V $$ $$ i j \Rightarrow M(i) \geq M(j) $$ $$ M(...
• メニュー
  メニュー トップページ 論文一覧 気になった論文 Parameterized Algorithms influence maximizati ICDM KDD AAAI k-means SCG SODA nearest neighbor IJCAI VLDB clustering coefficie random walk WWW STOC SIGMOD quasi-clique NIPS ICML SDM PNAS JMLR information diffusio triangle I/O-efficient algori Econometrica SCC streaming algorithm JEA ALENEX graph partitioning spectral clustering causality t...
• A Local Search Approximation Algorithm for k-Means Clustering
  A Local Search Approximation Algorithm for k-Means Clustering Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, Angela Y.Wu In SCG 2002 Symposium on Computational Geometry 概要 k-meansアルゴリズム 多項式時間で(9+ε)-近似 Single-Swap ヒューリスティクス 山登り法 初期状態から状態遷移していき、局所解を答えとする 状態 k個の施設 遷移 k個の施設の内1つを残りのn-k個と交換（だから、Single-...
• Structure-Preserving Sparsification of Social Networks
  Structure-Preserving Sparsification of Social Networks Gerd Lindner, Christian L. Staudt, Michael Hamann, Henning Meyerhenke, Dorothea Wagner ASONAM 2015 概要 疎化したグラフの性質を調べたよ "Local Degree"なる単純な手法で実は充分良いよ 辺数が元の20%でも、大体保存される 比較手法 Random Edge (RE) 一様ランダムに辺を選んでいく Triangles 属する△の個数の多い辺を順に残す Local Similarity (LS) 得点 = J(N(u...
• FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs
  FAST-PPR Scaling Personalized PageRank Estimation for Large Graphs Peter Lofgren, Siddhartha Banerjee, Ashish Goel, C. Seshadhri KDD 2014 概要 $$ \pi_s(t) \delta $$を$$ \mathcal{O}(\sqrt{d/\delta}) $$時間で近似計算 相対誤差が小さい 既存は$$ \Omega(1/\delta) $$時間で、$$ \delta=\Theta(1/n) $$にしたいので遅い□ 計算時間の下限$$ \Omega(1/\sqrt{\delta}) $$を示した 実験的には数十倍速い 提案手法 設定 ...
• Outward Influence and Cascade Size Estimation in Billion-scale Networks
  Outward Influence and Cascade Size Estimation in Billion-scale Networks]] Hung T. Nguyen, Tri P. Nguyen, Tam N. Vu, Thang N. Dinh SIGMETRICS 2017 （会議） Proceedings of the ACM on Measurement and Analysis of Computing Systems 2017 （ジャーナル） 概要 影響力推定の新しい指標outward influenceを作ったよ！…E[拡散サイズ]-|シードサイズ| 相対誤差を保証するのが難しい 高速アルゴリズムを作ったよ カスケードが小さくなり過ぎようにimportance samplingを...
• Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study
  Debunking the Myths of Influence Maximization An In-Depth Benchmarking Study SIGMOD 2017 概要だけ 提案されたきた影響最大化の手法は本当に効率的なのか？ 比較手法 CELF, CELF++, TIM+, IMM, PMC, StaticGreedy, LDAG, SIMPATH, EaSyIM, IRIE, IMRANK 徹底的な実験を決行 個々の論文の著者の主張は間違っている！！ • PMC [39] PMC establishes itself as the only technique that consistently provides high spread and scales for bot...
• Scalable Similarity Estimation in Social Networks: Closeness, Node Labels, ...
  Scalable Similarity Estimation in Social Networks Closeness, Node Labels, and Random Edge Lengths Edith Cohen, Daniel Delling, Fabian Fuchs, Andrew V. Goldberg, Moises Goldszmidt, Renato F. Werneck COSN 2013 背景 直径が小さいグラフで最短路を求める意味はあるのか？ そこを考えよう！ 概要 最短路ベースの頂点間関連性 RWR, SimRank, Resistance dsitance, … この論文 色々提案して、その計算、既存の関連性との比較 神か A...
• Distance Constraint Reachability Computation in Uncertain Graphs
  Distance Constraint Reachability Computation in Uncertain Graphs Ruoming Jin, Lin Liu, Bolin Ding, Haixun Wang VLDB 2011 概要 経路長に制限を入れた到達可能性確率計算クエリ 普通のシミュレーションは遅いので，頭のいい方法を考案 最大で1M辺規模で動く 問題定義と動機付け 距離制約到達可能性クエリ (Distance-constraint reachability) 入力 2頂点s,t, uncertainグラフ G, 閾値d 出力 s-t間の最短経路長がd以下である確率$$ R_{s,t}^d(\mathcal{G}) $$は？ P2Pネットワークでの応用例...
• Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph ...
  Path Sampling A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts Madhav Jha, C. Seshadhri, Ali Pinar WWW 2015 概要 数千万辺でも数十秒 誤差1%以下 Chernoff boundからエラーバーも出せる 問題定義 4-頂点部分グラフは6種類 3-star, 3-path, tailed-triangle 4-cycle, chordal-4-cycle, 4-clique C_i 誘導部分グラフにおけるi-th 部分グラフの出現個数 N_i i-th 部分グラフの出現個数 (C_i)と(N_i)は簡単な線形関係に...
• Counting Triangles in Large Graphs using Randomized Matrix Trace Estimation
  Counting Triangles in Large Graphs using Randomized Matrix Trace Estimation Haim Avron IBM Research（っぽい？） COSN 2013 概要 タイトルそのまんまの内容 トレースを愚直に求めるのは難しいので、ランダムベクトルで挟んでいっぱい計算して平均をとる サンプル数は結構多いけど、実験的にはO(log^2|V|)個でよい 実験は微妙… 既存手法とか 簡単なアルゴリズム Σdeg(v)^2で遅い 行列積とかで頑張る…O(|E|^1.41) 近似する場合…サンプリング Spectral counting $$ \Delta(G) = \fr...
• An Application of Boosting to Graph Classification
  An Application of Boosting to Graph Classification Taku Kudo, Eisaku Maeda, Yuji Matsumoto NIPS 2004 概要 グラフ分類にBoostingを応用する（最初期の論文？） 提案手法 概要 ラベル付きグラフがL個あります 決定株$$ h_{\langle t,y \rangle}(\mathbf{x}) $$ xについてある部分グラフyを含んでいたらyを返す ものすごく弱いので、Boosting(特にAdaBoost)を適用 決定株をK個用意する $$ \mathrm{gain}(\langle t,y \rangle) = \sum_{1 \leq i \leq L} ...
• I/O Efficient: Computing SCCs in Massive Graphs
  I/O Efficient Computing SCCs in Massive Graphs Zhiwei Zhang, Jeffrey Xu Yu, Lu Qin, Lijun Chang, Xuemin Lin In SIGMOD 2013 駒水（筑波大）さんの資料 概要 SCCしたい グラフがメモリに乗らない 既存手法 EM-SCC Contraction-based グラフを適当に分割する メモリ乗らないサイズのSCCは発見できない DFS-SCC semi-external DFS木を2回 逆グラフ作って…ってやつ よくやるSCCアルゴリズムだと思う多分 提案手法 木...
• Tracking the Random Surfer: Empirically Measured Teleportation Parameters in ...
  Tracking the Random Surfer Empirically Measured Teleportation Parameters in PageRank David F. Gleich, Paul G. Constantine, Abraham D. Flaxman, Asela Gunawardana WWW 2010 概要 PageRankのαの値は何なんだ？ 平均が0.3~0.7のβ分布に従う 分布の測定 人一人なら簡単 (リンククリックによる総閲覧ページ数) / (総閲覧ページ数) 複数人いると，平均とかいうわけにも行かない PageRankはαに対して非線形だから 代わりに，人毎にαを求め，グループ全体にフィットする分布を求める ↓の2...
• Efficient influence spread estimation for influence maximization under the ...
  Efficient influence spread estimation for influence maximization under the linear threshold model Zaixin Lu, Lidan Fan, Weili Wu, Bhavani Thuraisingham and Kai Yang Computational Social Networks 2014 概要 LTモデルの影響拡散を厳密or精度良く計算 4hop以内の影響について厳密計算 4hopはRandom walkで近似 性質 $$ \sigma(S) = \sum_{\pi \in P(S)} \prod_{e \in \pi} w(e) + |S| $$ P(S) = S内の頂点から出てる単...
• Resampling-based Predictive Simulation for Identifying Influential Nodes ...
  Resampling-based Predictive Simulation for Identifying Influential Nodes over Social Network 社会ネットワーク上の強影響度ノード同定のためのリサンプリングに基づく予測シミュレーション法の提案 Kouzou Ohara, Kazumi Saito, Masahiro Kimura, Hiroshi Motoda JSAI 2014 概要 ICモデルのシミュレーションは何回やればいいの？ 真の影響度との誤差を知りたいけれど，真値が分からない leave-N-out 交差検証 |S|回シミュレートした $$ \bar{A}_S(v) $$ 試行集合Sに対するvの影響度の平均値 パラメータNについて↓で...
• Triangle-Based Representative Possible Worlds of Uncertain Graphs
  Triangle-Based Representative Possible Worlds of Uncertain Graphs Shaoying Song, Zhaonian Zou, Kang Liu DASFAA 2016 概要 三角形次数を保存する決定的グラフを抽出するよ！ The Pursuit of a Good Possible World Extracting Representative Instances of ...の発展 やってることは簡単なヒューリスティクス 問題定義 $$ \sum_{v}|d_{G}(v)-\bar{d}_{\mathcal{G}}(v)| + \sum_{v}|t_{G}(v)-\bar{t}_{\mathcal{G}}(v)| $$を最小化せよ ...
• A practical bounding algorithm for computing two-terminal reliability based ...
  A practical bounding algorithm for computing two-terminal reliability based on decomposition technique Yi-feng Niu, Fang-Ming Shao Computers and Mathematics with Applications 2011 概要 2端子信頼性計算のアルゴリズム 実験なし （某イベントで知った） 提案手法 C 事象の集合 事象=各辺の状態 A1(C) Cでの状態が生の辺集合 A2(C) Cでの状態が死の辺集合 A1(C)がs-t経路を構成→必ず到達可能 A2(C)がs-tカットを構成→必ず到達不可能 良く分から...
• Computing Top-k Closeness Centrality Faster in Unweighted Graphs
  ...entrality Faster in Unweighted Graphs Elisabetta Bergamini, Michele Borassi, Pierluigi Crescenzi, Andrea Marino, Henning Meyerhenke ALENEX 2016 概要 近接中心性の上位k頂点を厳密に得たい 値が似通っているので，近似だと不十分 2種類の距離和の下限を使った簡単な枝刈り手法を提案 実験したら既存の枝刈り手法より探索辺数の意味で良かった 提案手法 戦略 各頂点からの距離和の下限を計算 下限の小さい順に見ていって遅延評価的にBFSをして確定させていく 最悪でn回BFSする 階層に基づく下限 どこかの頂点s...
• Extrapolation Methods for Accelerating PageRank Computations
  Extrapolation Methods for Accelerating PageRank Computations Sepandar D. Kamvar, Taher H. Haveliwala, Christopher D. Manning, Gene H. Golub WWW 2003 概要 PageRankのためのPower methodの高速化 25--300%速くなった メモ：イントロで… Dangling nodesからは一様に飛ぶとしている Aitken Extrapolation $$ x^{(k-2)} $$が上位2つの固有ベクトルの線形結合で表せるとする $$ x^{(k-2)}, x^{(k-1)}, x^{(k)} $$を使って$u_1$を求めたい！...
• Scalable Maximum Clique Computation Using MapReduce
  Scalable Maximum Clique Computation Using MapReduce Jingen Xiang, Cong Guo, Ashraf Aboulnaga ICDE 2013 概要 MapReduceを使った最大クリークアルゴリズム グラフの分割が味噌 Multi-depth Color-based (BMC) partitioning 分割した後は個々に解く この時も枝刈りをして早くする 実験は10^2~10^3オーダー頂点で密なグラフ 最大クリークアルゴリズム 分割後に使う最大クリークアルゴリズム MCRアルゴリズム（すでにある手法） 分枝限定法 ωを最大クリークのサイズとするとω(G)は下のどれか $$ \...
• Maximizing Submodular Set Function with Connectivity Constraint: Theory and ...
  Maximizing Submodular Set Function with Connectivity Constraint Theory and Application to Networks Tung-Wei Kuo, Kate Ching-Ju Lin, Ming-Jer Tsai Research Center for Information Technology Innovation（資訊科技創新研究中心） National Tsing Hua University（國立清華大學） INFOCOM 2013 概要 ワイヤレスネットワークのルーターの設置問題 submodular関数で表せる さらにルーターは連結であるという制約を追加 この設定でも近似アルゴリズムが設計できる 1...
• Simulated Annealing Based Influence Maximization in Social Networks
  Simulated Annealing Based Influence Maximization in Social Networks Qingye Jiang, Guojie Song, Cong Gao, Yu Wang, Wenjun Si, Kunqing Xie In AAAI 2011 概要 influence maximizationに対する初の焼きなましベースアルゴリズム influence spreadを高速に近似計算 アルゴリズム SA based 適当にseed setを変更するだけ SAEDV (Expected Diffusion Value) Aによりactivateされるノード数の期待値は $$ |A| + \sum_{v \in N^{o...
• Real-Time Influence Maximization on Dynamic Social Streams
  Real-Time Influence Maximization on Dynamic Social Streams Yanhao Wang, Qi Fan, Yuchen Li, Kian-Lee Tan VLDB 2017 概要 クエリ Stream Influence Maximization sliding windowモデルで考える Influential Checkpoints 途中途中で結果をとっておいて ε-近似 Sparse Influential Checkpoints チェックポイントの数が多すぎるので、対数個くらいにまで減らす (log N)/β個で、ε(1-β)/2-近似 問題定式化 行動 $$ a_t = \langle...
• Fast Algorithms for Top-k Personalized PageRank Queries
  Fast Algorithms for Top-k Personalized PageRank Queries Manish Gupta, Amit Pathak, Soumen Chakrabarti WWW 2008 概要だけ（で十分なので） PPR上位k頂点を抽出したい 基本的にはBookmark Coloring Algorithm (BCA) 途中で打ち切れる 初期 解, 残差 を$$ \langle \mathbf{0}, \mathbf{v} \rangle $$で始めると、 推定値≦真値≦推定値+||残差|| 扱いやすい範囲で、もう少し改善している この条件を使って枝刈り 出力したい頂点を限定した設定も考えているけどスルー 4倍速くなりました ...
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
  Online Node-weighted Steiner Forest and Extensions via Disk Paintings Mohammad Taghi Hajiaghayi, Vahid Liaghat, Debmalya Panigrahi In FOCS 2013 Online node-weighted steiner forest min w(U) s.t. G(U)は(s_1,t_1),…,(s_k,t_k)を連結にする ↑はオフライン、これを更にオンラインにする (s_i,t_i)が来た時には、1~iまでについて連結にする Online steiner tree ターミナルが順番に来る spider decompositionってのを考える MSTを作っ...
• Massive Graph Triangulation
  Massive Graph Triangulation Xiaocheng Hu, Yufei Tao, Chin-Wan Chung In SIGMOD 2013 塩川さん@NTT の発表資料より 目的 graph triangulation を高速に解く 全てのtriangleを列挙 貢献 CPU I/O efficient CPU $$ O(|E|\log |E| \frac{|E|^2}{M} + \alpha |E|) $$ I/O $$ O(\frac{|E|^2}{MB} + \frac{K}{B}) $$ worstではoptimal M メモリサイズ B ブロックサイズ K （発見した）△の数 ...
• Fast Robustness Estimation in Large Social Graphs: Communities and Anomaly ...
  Fast Robustness Estimation in Large Social Graphs Communities and Anomaly Detection Fragkiskos D. Malliaros, Vasileios Megalooikonomou, Christos Faloutsos SDM 2012 概要だけ 頂点は閉路の数が多いほど重要と考える 部分グラフ中心性（物理側から持ってきた） $$ \mathrm{SC}(v) = \sum_{i} u_{vi}^2 \sinh(\lambda_i) $$ i番目の固有ベクトルのv要素目 まとめると $$ \xi(G) = \sqrt{ \frac{1}{|V|}\sum_{v} \left\{ \log(u_{v1}) -...
• Estimating Clustering Coefficients and Size of Social Networks via Random Walk
  Estimating Clustering Coefficients and Size of Social Networks via Random Walk Stephen J. Hardiman, Liran Katzir In WWW 2013 メモ Liran KatzirはMSR Israel 概要 ランダムウォークでクラスタ係数と頂点数を見積もる 全体をとってくるのが厳しい用 ちょっとタイムリー 既存手法よりかなり良い 近似が指数関数的によくなる（ランダムウォークの長さの 頂点のIDと、隣接リスト（次数）さえわかれば良い しかも前と後の1つずつだけ覚えていれば計算可能 問題 global clustering coefficien...
• Finding Influential Nodes in a Social Network from Information Diffusion Data
  Finding Influential Nodes in a Social Network from Information Diffusion Data Masahiro Kimura, Kazumi Saito, Ryohei Nakano, Hiroshi Motoda SBP 2009 Social Computing and Behavioral Modeling 概要 ノードの影響力をカスケード情報からランキングしたい ICモデルで確率を見積もるよ！ ただし，確率の値は一様 実際のネットワークで実験してみる ヒューリスティクスより精度良い 手法 Prediction of Information Diffusion Probabilities ...
• Faster Random Walks By Rewiring Online Social Networks On-The-Fly
  Faster Random Walks By Rewiring Online Social Networks On-The-Fly Zhuojie Zhou, Nan Zhang, Zhiguo Gong, Gautam Das ICDE 2013 概要 ランダムウォークでサンプリングしたい！ Third party（全データが無いのでAPIとかでとってくる でも、変なところにはまりやすい（孤立したコミュニティっぽいところ 辺を消したり付け替えたりして、conductanceを大きくする ランダムウォークなので、今見てる頂点の近傍だけから操作を行う 定常状態に速く収束する！（mixing timeが小さい 貢献 グラフトポロジーを変化させ、サンプリングを効率的にする、という「問題...
• Random-walk domination in large graphs: problem definitions and fast solutions
  Random-walk domination in large graphs problem definitions and fast solutions Rong-Hua Li, Jeffrey Xu Yu, Xin Huang, Hong Cheng CoRR 多分KDDに出した？ 概要 2種類ランダムウォーク支配問題、というものを考えた ソーシャルネットワーク上にアイテムを配置したり、色々なアプリケーションがある どの頂点からも長さLのランダムウォークによるヒッティングタイムが短い 長さLのランダムウォークがターゲットノードに到達する確率が高い DPベースの貪欲アルゴリズム ちょっと遅い 評価関数をサンプリングで近似 グラフサイズの線形時間で...
• Approximate Convex Decomposition Based Localization in Wireless Sensor Networks
  Approximate Convex Decomposition Based Localization in Wireless Sensor Networks Wenping Liu, Dan Wang, Hongbo Jiang, Wenyu Liu, Chonggang Wang INFOCOM 2012 概要 Localization やばいのでヒューリスティクスばかり MDSって既存手法 凹だったり穴があるとやばい 凸図形に分割して気合 問題 2次元のWireless Sensor Netrwork 各頂点の位置が知りたい GPSはコスト高 ｰ すこしの頂点（アンカー）だけに設置 互いに距離が小さい所は通信 その距離が分からない場合...
• Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs
  Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs Liam Roditty, Virginia Vassilevska Williams In STOC 2013 メモ Y.Yano 直径2近似O(n+m) BFSして最大の高さ additive approximation Aingworth 2つの組み合わせ 2種類のBFS木の高さの最大値 $$ s \in [1,n] $$ O(ns^2 + (s+n/s)m) 論文の内容 ns^2の項を消したい ↑高々s頂点のBFS N_s^out(v)を求めないで頑...
• Accelerating Graph Adjacency Matrix Multiplications with Adjacency Forest
  Accelerating Graph Adjacency Matrix Multiplications with Adjacency Forest Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato, Masaaki Nagata SDM 2014 概要 AXみたいな行列計算を高速にしたい Aの列中の値が同じ（確率遷移行列とか）だと余分な計算を省ける さらにAを分解して個々に省略手法を適用できる 3倍位速くなった 提案手法 Single Tree Adjacency Forest(STAF) Column-scaled nonzeros property 行列の各列j中の値＝0 or cj こんなやつ $$ A = \left( ...
• Estimating Sizes of Social Networks via Biased Sampling
  Estimating Sizes of Social Networks via Biased Sampling Liran Katzir, Edo Liberty, Oren Somekh Yahoo! Labs, Israel WWW 2011 概要 ネットワークのサイズ=頂点数を見積もりたい どういうシチュエーション？ FacebookとかTwitterとか…隣接リストは辿れるけどexplicitに|V|が得られない ランダムウォークベースのアルゴリズム 一様サンプリングでなくて次数でバイアスがかかっているのがポイント 一様よりも高性能であることを実験で示した サンプリング 誕生日パラドックスに基づいた手法 rノードを一様サンプリングす...
• Assessing Attack Vulnerability in Networks with Uncertainty
  Assessing Attack Vulnerability in Networks with Uncertainty Thang N. Dinh, My T. Thai INFOCOM 2015 概要 ネットワーク脆弱性を「期待対連結性」で評価したい 「k頂点消すと期待対連結性はどれ位下がるか？」という離散最適化問題 提案手法は、LPによる緩和＋交換ヒューリスティクス 期待対連結性のFPRASを提案 期待対連結性 脆弱性の色々な尺度 最短経路長、代数的連結性、連結成分数・サイズ…はあまり良くない 対連結性 (pairwise connectivity)は結構良いらしい 致命的頂点検出問題 (critical node detection; CND) 普通...
• Memory Efficient Minimum Substring Partitioning
  Memory Efficient Minimum Substring Partitioning Yang Li, Pegah Kamousi, Fangqiu Han, Shengqi Yang, Xifeng Yan, Subhash Suri In VLDB 2013 アブスト 並列DNAシーケンス技術が進歩している Illumina, SOLiD Human Whole Genome Sequencingの値段 $3,750 数G個の断片をとってきて遺伝子全体の再構築 short read A,C,G,Tからなる短いシーケンス 既存手法 ランダムサンプリングして、重複があるreadを拾ってくる readの長さ 数十 ~ 数百 ...
• Streaming Algorithms for k-core Decomposition
  Streaming Algorithms for k-core Decomposition Ahmet Erdem Saríyüce, Buğra Gedik, Gabriela Jacques-Silva, Kun-Lung Wu, Ümit V. Çatalyürek VLBD 2013 概要 k-core decompositionあるよねー 実際は、辺が挿入されたり削除されたりするから、そういう走査サポートしたいよねー 作りました 実験しました 毎回batchするより断然良い k-core decomposition K(v) vが属せるk-coreのうち最大のk 基本的に、周りに1があって、中に2があって、その内側に3があって…ってなる アルゴリ...
• The matching polytope has exponential extension complexity
  The matching polytope has exponential extension complexity Thomas Rothvoss STOC 2014 概要 extension complexityって何？ LPで問題を表現した時の不等式の数 matching polytope マッチングを表現する超多面体 結果 matching polytopeをLPで表現するには「指数個の制約」が必要 マッチングはPなのに？！ ↑ここが驚くべきこと 今まで NP-hardな問題だけだった Extention Complexity TSP polytopeは対称な多項式個の制約式では表現できない LPで簡単には表現できない ...
• Cost-aware Targeted Viral Marketing in Billion-scale Networks
  Cost-aware Targeted Viral Marketing in Billion-scale Networks Hung T. Nguyen, Thang N. Dinh, My T. Thai INFOCOM 2016 概要 新しい問題 Cost-aware Targeted Viral Marketing ユーザ毎に最初の費用が違う ユーザ毎に影響させた事による効果が違う いい感じにすれば$$ 1-1/\sqrt{e} $$近似が可能 効率的アルゴリズム BCT：CTVMにもInfMaxにも適用可能 LISA [CSoNet 15]の後続 Cost-aware Targeted Viral Marketing 費用$$c(u)$$、利益$$b(u)$$、予算$...
• Learning with Local and Global Consistency
  Learning with Local and Global Consistency Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, Bernhard Schölkopf NIPS 2003 概要 半教師あり学習 滑らかにしたい 仮定 局所的：近くの点は同じラベルを持つ 大域的：同じ構造中の点同士は同じラベルを持ちやすい k-NNとかは前者だけで後者はあまり反映出来ていない ただのSVMでも微妙 提案アルゴリズム 自分のラベルを周りに伝播する感じ x1,…xlがラベル有り（y1,…,yl）、x{l+1},…,xnがラベル無し n×c行列F $$ y_i = ...
• Approximate Bayesian Image Interpretation using Generative Probabilistic ...
  Approximate Bayesian Image Interpretation using. Generative Probabilistic Graphics Programs 画像認識の新手法 応用 CAPTHA…これは文字ほげだ！ 道路認識 画像のシーンをシンボリックに 大きなコーパスが必要 トップダウンに考えるよ！ ボトムアップ 画像を要素に分解 それぞれを解釈 トップダウン 要素を仮定し画像を構成 その確率を出す モデル シーン…文字の種類とか 入力からこれを推定する レンダラを使った生成モデルで予測 Metropolis-Hastings 変数をちょっと動かしてほげ...
• Towards Context-Aware Search by Learning A Very Large Variable Length Hidden ...
  Towards Context-Aware Search by Learning A Very Large Variable Length Hidden Markov Model from Search Logs Huanhuan Cao, Daxin Jiang, Jian Pei, Enhong Chen, Hang Li MSRAとUniversity of Science and Technology of China WWW 2009 概要 たった今調べたクエリからURLを正しくレコメンドするのは無理 例 ホントは車のレビューサイトを見たい 検索クエリ Ford new cars → Toyota new cars 個々のクエリに着目するとautohome.comは出てこない ...
• Influence at Scale: Distributed Computation of Complex Contagion in Networks
  Influence at Scale Distributed Computation of Complex Contagion in Networks Brendan Lucier, Joel Oren, Yaron Singer KDD 2015 発表者はJoel Oren 概要 ICモデルでのσの推定 新しい標本 高確率・高精度で頂点集合の影響拡散を求める手法 MapReduceで分散も グラフはでかいので分割，クエリを打っていく Q. どのくらいのクエリが必要？ 適当な設定でクエリ計算量の下限 実験してMCより良い 予備知識 link-serverモデル [Bar-Yossef, Mashiach, CIKM 08]...
• Joint M-Best-Diverse Labelings as a Parametric Submodular Minimization
  Joint M-Best-Diverse Labelings as a Parametric Submodular Minimization Alexander Kirillov, Alexander Shekhovtsov, Carsten Rother, Bogdan Savchynskyy NIPS 2016 概要 Joint M-best-diverse labeling 問題をパラメトリック劣モジュラ最小化問題に帰着して解く 動機づけ・問題定式化 2値画像のノイズ除去・画像分割 エネルギー関数最小化として定式化 エネルギー関数 データ項= 「入力と出力の近さ」＋平滑化項=「出力の滑らかさ」 例 $$ E(y) = \sum_{v \in V}b_v [x_v \neq y_v] + ...
• @wiki全体から「Fast Single-Pair SimRank Computation」で調べる

更新順にページ一覧表示 | 作成順にページ一覧表示 | ページ名順にページ一覧表示 | wiki内検索