todo314 @ ウィキ
todo314 @ ウィキ

Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph

todo314 @ ウィキ内検索 / 「Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph」で検索した結果

検索 :
  • Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph
    Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph Kiana Hajebi, Yasin Abbasi-Yadkori, Hossein Shahbazi, Hong Zhang In IJCAI 2011 メモ hatenaから引っ張ってきたのだからアレ 概要 k近傍グラフ上での山登り方による近似最近傍探索 Locality Sensitive Hashing、KD-木よりも速くて高速 問題 最近傍探索。d次元空間上の点集合Dと距離尺度ρが与えられる。各クエリQに対して、次を求める $$ X^{*} = ￥arg \min_{X \in D} \rho(X, Q) $$ 線形探索...
  • 気になった論文
    ...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...
  • 論文一覧
    ...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...
  • Fast Algorithm for the Lasso based L1-Graph Construction
    Fast Algorithm for the Lasso based L1-Graph Construction Yasuhiro Fujiwara, Yasutoshi Ida, Junya Arai, Mai Nishimura, Sotetsu Iwamura VLDB 2016 概要 L1-Graph + Lassoなグラフ構築手法がある とても遅いので高速化 基本アイデアは正重みな辺の事前計算＋反復の高速化 Lasso based L1-graph Least absolute shrinkage and selection operator $$ \min_{\mathbf{w}_p} \frac{1}{2M}\| \mathbf{x}_p - \mathbf{X} \mathb...
  • メニュー
    メニュー トップページ 論文一覧 気になった論文 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...
  • 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)を求めないで頑...
  • Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large ...
    Subgraph Frequencies Mapping the Empirical and Extremal Geography of Large Graph Collections Johan Ugander, Lars Backstrom, Jon Kleinberg In WWW 2013 メモ 岩田さん 概要 social networkを全体を見て解析するのではなく、密な部分ごとに見る 3-4頂点の部分グラフの出現頻度を見ると特徴がわかる 実験データ Facebook Lars BackstromがFacebookの人だからしょーがないね(´・ω・`) 抽出する部分グラフ Neighborhoods 友人 Groups...
  • k-Nearest Neighbors in Uncertain Graphs
    k-Nearest Neighbors in Uncertain Graphs Michalis Potamias, Francesco Bonchi, Aristides Gionis, George Kollios VLDB 2010 概要 k近傍クエリ 最短距離や酔歩に基づく尺度を拡張 厳密計算は難しい Monte-Carloサンプリングで近似アルゴリズム グラフ変形，枝刈り 実験：数十M辺 メモ VLDB版ではない原稿を読んだのでちょっと違う イントロ 確率的グラフ 辺に確率が割り振られている センサや実験による雑音 不安定な通信 リンク予測 秘匿性のための摂動 気になること...
  • 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-...
  • Vertex Neighborhoods, Low Conductance Cuts, and Good Seeds for Local ...
    Vertex Neighborhoods, Low Conductance Cuts, and Good Seeds for Local Community Methods David F. Gleich, Seshadhri Comandur せしゃどり In KDD 2012 (closed) vertex neighbor 距離1以内の頂点集合 これがそれなりに良いコミュニティ マジかよ 理論的に示す 実データも使う 目的関数 $$ vol(S) = \sum_{v \in S} \deg(v) $$ $$ cut(S,T) = \{ (u, v) \in E | u \in S, v \in T \} $$ コンダクタンス（これが目的関数） ...
  • Co-clustering documents and words using Bipartite Spectral Graph Partitioning
    Co-clustering documents and words using Bipartite Spectral Graph Partitioning Inderjit S. Dhillon KDD 2001 概要 文書と単語の共クラスタリング カット最小化として妥当な問題設定 スペクトラルグラフ理論の知見から固有ベクトル計算問題として緩和 後はk-meansすると大体上手い 問題設定 $$ G=({\cal D}, {\cal W}, E) $$ 文書と単語の二部グラフ 辺重みが謎… 単語・文書クラスタリングの関係 文書のクラスタが与えられた時、各単語は{最も重み和の大きい文書クラスタ}に対応する単語クラスタに属すると考える というわけで、k...
  • Minimum-Risk Maximum Clique Problem
    Minimum-Risk Maximum Clique Problem Maciej Rysz, Pavlo A. Krokhmal, and Eduardo L. Pasiliao Dynamics of Information Systems Algorithmic Approaches 2013 概要 最小危険最大クリーク問題 各頂点には費用／損失を表す確率変数 同時分布は既知 特定の危険尺度で危険最小のクリークを見つけたい 尺度の単調性から最適解は極大クリークになる Erdős–Rényiグラフで実験 導入 状況 頂点 が不確かさを持つ 危険回避グラフ理論的問題 Xi 頂点iに紐づく確率変数 Xiの同時分布は分かる...
  • On Triangulation-based Dense Neighborhood Graph Discovery
    On Triangulation-based Dense Neighborhood Graph Discovery Nan Wang, Jingbo Zhang, KianLee Tan, Anthony K. H. Tung VLDB 2011 概要 僕の考えた最強のdense graph 任意の2頂点が共有する近傍がλ個以上 そこそこいい性質を持っている（らしい） triangulationを上手く使って、検出 DN-graph λ(V ) 頂点対が共有する近傍の数の最小値 Dense Neighborhood graph G =(V ,E )について 任意の2頂点はλ個以上の近傍を共有している λ(V ∪{v}) λ, λ(V -{v})≦λ...
  • Top-K Nearest Keyword Search on Large Graphs
    Top-K Nearest Keyword Search on Large Graphs Miao Qiao, Lu Qin, Hong Cheng, Jeffrey Xu Yu, Wentao Tian In VLDB 2013 メモ Jeffrey Xu Yu!! 概要 top-k nearest keyword search 頂点 0個以上のキーワード 辺 長さ クエリ ノード、キーワード、k 出力 キーワードを含みノードに近いkノード top-k nearest keyword search に対するアルゴリズム 最短経路木 2つ提案 kが小さいよう 大きくてもOK 応用 Facebo...
  • 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...
  • On k-skip Shortest Paths
    On k-skip Shortest Paths Yufei Tao, Cheng Sheng, Jian Pei SIGMOD 2011 概要 k-skip coverを考えた 要はk-shortest pathのhitting set 色々使えそう 理論的な解析とそこそこ速そうなアルゴリズム 問題定義とか k-skip Shortest Paths SP(s,t)をs-t間の最短経路とし，その順番をv_1,v_2,…,v_lとする P*が以下を満たすならs-t間のk-skip shortest path ∀i P*∩{v_i,…,v_{i+k-1}}≠∅ つまり，どの連続するk頂点を選んでも，どれかひとつ以上はP*に含まれている k-s...
  • Denser than the Densest Subgraph: Extracting Optimal Quasi-Cliques with ...
    Denser than the Densest Subgraph Extracting Optimal Quasi-Cliques with Quality Guarantees Charalampos E. Tsourakakis, Francesco Bonchi, Aristides Gionis, Francesco Gullo, Maria A. Tsiarli In KDD 2013 http //www.math.cmu.edu/~ctsourak/kdd13.pptx 概要 quasi-clique の評価関数を変えた densest-graphの評価関数 $$ e[S]/|S| $$ はだめ！ 辺密度が低いし（グラフがでかいから）、直径もでかい 辺密度 $$ e[S]/{|S| \c...
  • Is Nearly-linear the Same in Theory and Practice? A Case Study with a ...
    Is Nearly-linear the Same in Theory and Practice? A Case Study with a Combinatorial Laplacian Solver Daniel Hoske, Dimitar Lukarski, Henning Meyerhenke, Michael Wegner SEA 2015 概要 A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Timeを実装してみました！ ほぼ線形時間の計算量だけど、定数が大きすぎて、全然遅いよ！残念！ low stretch保証のある手法よりも、単純な全域木のほうが良かったりしたよ！ 準備 基本的なソルバの...
  • 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}) -...
  • A Structural Smoothing Framework For Robust Graph-Comparison
    A Structural Smoothing Framework For Robust Graph-Comparison Pinar Yanardag, S. V. N. Vishwanathan NIPS 2015 概要だけ R-convolutionの問題 特徴空間がデカイと、自分以外とは類似しにくい（対角優位問題） 低次数部分構造（ちっちゃい部分グラフ）が分布を占めてしまう 部分構造は互いに関連しているけど、R-convolutionはEXACTを要求するので微妙 Deep Graph Kernelとはここが違うらしい 解決法 頻度ベクトルを平滑化する 色んな部分グラフを層っぽい感じに捉えて、関連性で平滑化 アイデア Maximum Likeliho...
  • Sampling Node Pairs Over Large Graphs
    Sampling Node Pairs Over Large Graphs Pinghui Wang, Junzhou Zhao, John C.S. Lui, Don Towsley, Xiaohong Guan In ICDE 2013 概要 ノードのペアに関する性質 平均距離とか サンプリングで求めるが 一様っぽいサンプリングは一様じゃない xを決める、u,vをxの近傍から決める [u,v]が選ばれる確率は$$ \sum_{u-x-v}{\deg(x) \choose 2}^{-1} $$に比例 biasがかかる 提案手法 weighted vertex sampling neighborhood random walk 問題 ...
  • 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...
  • An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting ...
    An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree Jochen Koenemann, Sina Sadeghian, Laura Sanità In FOCS 2013 ノード重みはキテるんですよ！！ Prize collecting node-weighted steiner tree w V→R+ p V→R+ min w(V(T)) + P(V-V(T)) s.t. Tはtree 左はスパンしている、右はしていない LMP Lagrangian multiplier preserving w(V(T))+αp(V-V(T))≦αw(V(...
  • Influence Blocking Maximization in Social Networks under the Competitive ...
    Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model Xinran He, Guojie Song, Wei Chen, Qingye Jiang SDM 2012 概要 Competitive Linear Threshold モデルを考えたよ 目的関数は自分の最大化じゃなくて，相手の最大化だよ そうするとこのモデルではsubmodularだよ 目的関数の計算が大変なのでPMIAっぽいものを作った Competitive Linear Threshold Model 各辺には2つの重みw+とw-がある 各頂点の閾値も2つθ+とθ- 状態はin...
  • Fast and Provably Good Seedings for k-Means
    Fast and Provably Good Seedings for k-Means Olivier Bachem, Mario Lucic, Hamed Hassani, Andreas Krause NIPS 2016 概要 Approximate K-Means++ in Sublinear Time K-MC^2の改善版 データに対する強い仮定があるという欠点有り 頂点の標本分布を「一様」から「k-means++の最初の反復っぽい奴」に変える 但し、一回の全点スキャンが必要 仮定無しで、MCMCの連鎖長をバウンドし、期待近似比を保証 実験したら提案手法AFK-MC^2はK-MC^2より実際かなり良い K-MC^2 Metropolis-Hastings ...
  • Topic-aware Social Influence Propagation Models
    Topic-aware Social Influence Propagation Models Topic-aware Social Influence Propagation Models Nicola Barbieri, Francesco Bonchi, Giuseppe Manco Yahoo! Research Barcelona ICDM 2012 概要 トピックを考慮したモデルにICとLTを拡張 期待値最大化でパラメータを見積もる 上のモデルは大変なので，ちょっとパラメータ数を減らしたモデルを考案 実験して普通のICより良かった Topic-awareモデル Topic-aware Independent Cascade Model (TIC) z...
  • The Power of Random Neighbors in Social Networks
    The Power of Random Neighbors in Social Networks Silvio Lattanzi, Yaron Singer WSDM 2015 概要 友達は友達が多い (friendship paradox) power-lawが十分条件では無い どういうモデルがparadoxを説明できるのか？ というわけで，モデルを提案 辺を張り替える 影響最大化への適用例 友達の逆説 friendship paradox 友達は友達が多い （頂点の近傍次数） （その頂点の近傍の平均次数） power-lawが十分条件では無い 実際にそういう例を作れる 極端な例 正則グラフ ☆ ...
  • Polynomial-Time Algorithm for Finding Densest Subgraphs in Uncertain Graphs
    Polynomial-Time Algorithm for Finding Densest Subgraphs in Uncertain Graphs Zhaonian Zou Workshop on Mining and Learning with Graphs 概要だけ Uncertain graphから期待密度最大の部分グラフ抽出 問題1 制約無し (期待密度)=(∑各辺の確率) 各辺の周辺確率が分かっていれば良い ただの最密部分グラフ $$ \mathcal{O}(nm\log(n^2/m)) $$時間 問題2 頂点集合Rを含む 別にUncertain graph特有の何かではない parametric maximum flowで同じ計算時間 ...
  • Parameterized Algorithms
    Parameterized Algorithms Introduction 頂点被覆 k人だけ消して競合を防ぐ→大きさのkの頂点被覆 NP完全 n=1000, k≦10 総当り 2^1000≒10^301 $$ {n \choose k} $$ {1000 c 10}≒10^23 ばか 観察1 ぼっちは消さなくて良い k人超過と競合する人は必ず消す そうでないと，その人の近傍を全て消す→k人超消すことになる 各頂点の次数∈[1,k]になる 辺数 k^2 →無理 $$ {2k^2 \choose k} $$ 観察2 次数1の頂点vがある→端点wを被覆に入れるのが最適 $$ {k^2 \choose k} $$ ...
  • Streaming k-means approximation
    Streaming k-means approximation Nir Ailon, Ragesh Jaiswal, Claire Monteleoni In NIPS 2009 メモ Google Researchとコロンビア大学の人々 概要 ストリーム k-means アルゴリズムの提案 O(log k)近似 アルゴリズム k-means # O(1)近似 ランダムにXの中から3 log k点選び，Cに追加 C ← Pから選んだ 3log k 点 k-1回繰り返す C ∪= Pからδ(x,C)に比例する確率で選んだ3log k点 本命 O(log k)近似 PをP1,…,Pl ...
  • Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free ...
    Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs Joseph Cheriyan, Laszlo A. Vegh In FOCS 2013 k-connectivity SNDP min v(F) s.t. (V,F)がk-connected 近似アルゴリズム O(log k log n/(n-k)) k=n-o(n)の時やばお O(k) n 3k-3 iterative rouding 6-近似 n≧k^3(k-1)+k ←かっこいい！！（この論文） Ω(k^3)（福永さん） 何でノードだとめんどいの？ ...
  • Rounded Dynamic Programming for Tree-Structured Stochastic Network Design
    Rounded Dynamic Programming for Tree-Structured Stochastic Network Design Xiaojian Wu, Daniel Sheldon, Shlomo Zilberstein AAAI 2014 Xiaojian WuにはAAAIでお会いした このグループはあくまでStochastic Network Designとして捉えているっぽい（影響最大化も） 概要 有向木上の確率的ネットワーク設計に対する丸め動的計画法 河のネットワークでの状況を想定できるらしい FPTASでO(n^2/ε^2)だけど実験的にはもう少し速い（し精度も良い） 動機付けとか リバーネットワーク(?)の階層的構造を木構造で表現 その応...
  • Maximizing the Spread of Cascades Using Network Design
    Maximizing the Spread of Cascades Using Network Design Daniel Sheldon, Bistra Dilkina, Adam N. Elmachtoub, Ryan Finseth, Ashish Sabharwal, Jon Conrad, Carla P. Gomes, David Shmoys, William Allen, Ole Amundsen, William Vaughan UAI 2010 We apply our model to a sustainability problem that is part of an ongoing collaboration with The Conservation Fund to optimize the conservation of ...
  • Threshold Models for Competitive Influence in Social Networks
    Threshold Models for Competitive Influence in Social Networks Allan Borodin, Yuval Filmus, Joel Oren WINE 2010 久しぶりの論文記事(ヽ´ω`) 概要 LTモデルを競合者付きモデルに拡張 劣モジュラどころか単調ですらないものもある Weight-Proportional Competitive Linear Threshold Model 頂点vはしきい値θ_vを持つ 活性近傍からの重みの和がθ_vになったら活性化 状態は3つ 非活性，活性A，活性B 活性Aの近傍の割合 活性Bの近傍の割合で確率的にAかBかに決まる S_B=∅なら元のLTモデルと同じ ...
  • Approximating the Spectrum of a Graph
    Approximating the Spectrum of a Graph David Cohen-Steiner, Weihao Kong, Christian Sohler, Gregory Valiant KDD 2018 概要 （正規化）Laplacianのスペクトラムが欲しい！ $$ \exp(O(1/\epsilon)) $$時間：定数！！！ $$ \| \tilde{\mathbf{\lambda}} - \mathbf{\lambda} \|_1 \leq \epsilon|V| $$ 性質検査的な話もあるよ！ 提案手法 定数時間にしたいので、出力は[0,2]上の離散分布 $$ \epsilon|V|, 2\epsilon|V|, 3\epsilon|V| $$番...
  • Random Warping Series: A Random Features Method for Time-Series Embedding
    Random Warping Series A Random Features Method for Time-Series Embedding Lingfei Wu, Ian En-Hsu Yen, Jinfeng Yi, Fangli Xu, Qi Lei, Michael Witbrock AISTATS 2018 概要 課題：Gram行列の対角優位と自乗時間 random features approximationを採用 DTW距離 2つの時系列$$x_i, x_j$$に対する任意のalignment $$a$$を考える 対応する各要素対のdissimilarityの和の最小が距離 $$ S(x,y) = \min_{a} \sum_{1 \leq t \leq |a|} \tau(x[a_...
  • Efficient Personalized PageRank with Accuracy Assurance
    .... VLDB 12]Fast and Exact Top-k Search for Random Walk with Restartの後続研究 PPRに関する3つの問題 $$\mathbf{x}$$が入力嗜好のPPR $$ \mathbf{x}_q $$の厳密計算 $$ \mathbf{x}_v $$が上位kの頂点v $$ \mathbf{x}_v \epsilon $$な頂点v QR分解による厳密計算サブルーチン＋上下限推定による枝刈り 既存手法よりも爆速 提案手法 QR分解 VLDB 12とほぼ同じ $$ \mathbf{x} = (1-\alpha)\mathbf{P}^\top (I-\alpha \mathbf{T} )\mathbf{Pv} $$ ...
  • 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}) $$を示した 実験的には数十倍速い 提案手法 設定 ...
  • 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はコスト高 ｰ すこしの頂点（アンカー）だけに設置 互いに距離が小さい所は通信 その距離が分からない場合...
  • Non-exhaustive, Overlapping k-means
    Non-exhaustive, Overlapping k-means Joyce Jiyoung Whang, Inderjit S. Dhillon, David F. Gleich SDM 2015 概要 既存のクラスタリング（特にk-means）手法は、外れ値の重複のどちらかだけだった NEO-K-Means (Non-Exhaustive Overlapping K-Means) を提案 重み付きカーネルk-meansとの互換性もある 外れ値 重複有りグラフクラスタリングに使える 定式化 $$ U=[u_{ij}]_{n \times k} $$ $$ \mathbf{x}_i $$がクラスタ$$j$$の属する 重複の具合の制約 $$ \mathrm{trace}(...
  • Computing and maximizing influence in linear threshold and triggering models
    Computing and maximizing influence in linear threshold and triggering models Justin T. Khim, Varun Jog, Po-Ling Loh NIPS 2016 概要 影響拡散の上下限を新たに作ったよ！ LTモデルとTriggeringモデル 下限は単調劣モジュラなので、最大化できて良い解になる 主結果 LTモデル 上限 $$ \leq |A| + \mathbf{b}_{\bar{A}}^\top (\mathbf{I}-\mathbf{B}_{\bar{A}\bar{A}})^{-1} \mathbf{1}_{\bar{A}} $$ An Upper Bound based Greed...
  • OSNAP: Faster numerical linear algebra algorithms via sparser subspace ...
    OSNAP Faster numerical linear algebra algorithms via sparser subspace embeddings Jelani Nelson, Huy L. Nguyen In FOCS 2013 線形空間の次元削減の話 問題 (1-eps)||x||≦||Πx||≦(1+eps)||x|| Π R^n→R^m Πはm×n行列上の確率分布Dに従う 設計したいのはD 応用 min ||Ax-b|| min ||ΠAx-Πb||にする m dなら解きやすい だけど、Πが疎じゃないと意味ない（行列演算が重くなる 結果 (i)既存の評価をimprove 非ゼロは各列1つだけ Π_...
  • Speedup Graph Processing by Graph Ordering
    ...ering for Fast Graph Analysis)との比較は如何に…？ SIGMOD グラフ処理 グラフ順序付け 2016/11/30
  • The query-flow graph: model and applications
    The query-flow graph model and applications Paolo Boldi, Francesco Bonchi, Carlos Castillo, Debora Donato, Aristides Gionis, Sebastiano Vigna CIKM 2008 概要 query-flow graph q_i→q_j 同セッションで計算されやすいよ！w(q_i,q_j)はその確率 問題 でかい、ノイズ、定式化、あいまい、疎、などつらぽよ 応用 logical session intertwined query chainsを見つける query recommendation Random walk with res...
  • 2.5K-Graphs: from Sampling to Generation
    2.5K-Graphs from Sampling to Generation Minas Gjoka, Maciej Kurant, Athina Markopoulou INFOCOM 2013 概要 2.5K-graph 次数kの頂点と次数lの頂点を結ぶ辺の個数の分布と、次数kの頂点のクラスタ係数の平均値を分布に着目 ソーシャルネットワークから↑を高速に見積もり、そういう分布になるグラフも生成する ↑以外の分布も結構一致する！ 問題 JDD(k,l) = 次数kの頂点と次数lの頂点を結ぶ辺の数 JDD = Joint Degree Distribution 2頂点の部分グラフの次数依存の分布 ‾c(k) = 次数kの頂点のクラスタ係数の平均値 dk...
  • Streaming Graph Partitioning for Large Distributed Graphs
    Streaming Graph Partitioning for Large Distributed Graphs Isabelle Stanton, Gabriel Kliot In KDD 2012 メモ セミナー K.Inabaさん 問題 巨大グラフを複数に分割したい ストリーミングアルゴリズムじゃないと意味ないお 入力 G(V,E) k マシン台数 ε アンバランス度 出力 V1, V2, …, Vk $$ |Vi| \leq \frac{(1+\epsilon)|V|}{k} $$ または $$ \sum \deg(V_i) \leq (1+\epsilon)\sum \deg(v)/k $$ を満たすよ...
  • Fast Random Walk with Restart and Its Applications
    Fast Random Walk with Restart and Its Applications Hanghang Tong, Christos Faloutsos, Jia-Yu Pan ICDM 2006 概要 ベストペーパー RWRを高速にクエリ計算した 提案手法 B_LIN グラフを（METISとかで）k分割する 確率遷移行列W（論文中では正規化Laplacianもどき）をW_1+W_2に分割する RWR行列は$$ (1-c)(I-cW)^{-1} $$ W_1：分割内だけ；diag(W_11, …, W_1k)な感じ W_2：分割間だけ； Q_1 = diag(Q_11, …, Q_1k) Q_1i = (I-cQ_1i)の逆行列 ...
  • Outlier Detection in Graph Streams
    Outlier Detection in Graph Streams Charu C. Aggarwal, Yuchen Zhao, Philip S. Yu AggarwalはIBM Research ICDE 2011 概要 タイトルのまんま 問題としては初出なので、ちゃんとした比較対象はない outlierって何？ 互いに異なるコミュニティに属する人々がつながった！ 異分野の人たちが共著するとか 興味深い！ グラフでかいし難しい！ ちょっとだけ持つよ！ モデリング ※辺がどんどんくるストリームモデルを想定 C = C_1,…C_kはVの分割 理想はコミュニティに分割 p_ij(C) C_iとC...
  • Modeling Information Diffusion in Implicit Networks
    Modeling Information Diffusion in Implicit Networks Jaewon Yang, Jure Leskovec ICDM 2010 概要 基本的にunderlyingなグラフは分からん グラフ構造っぽいのを使わずにモデリング Linear Influence Model Linear Influence Model 定式化 仮定 uがアクティブになった時刻 これだけ、リンク関係は謎 V(t) 時刻tに情報に言及した頂点の数 I_u(l) 頂点uが言及してから影響を受けてl時間後の言及した頂点の数 A(t) 時刻tまでにアクティブになった頂点の集合 M_u,k(t) 時刻tまでにuがアクテ...
  • Efficient Location-Aware Influence Maximization
    Efficient Location-Aware Influence Maximization Guoliang Li, Shuo Chen, Jianhua Feng, Kian-lee Tan, Wen-Syan Li SIGMOD 2014 概要 位置を考慮した影響最大化 Foursquareとか クエリは領域とk 2つの手法を提案 1-1/e近似 expansion-based assembly-based それでも遅いのでさらに2手法 ε(1-1/e)近似 bound-based hint-based 問題定式化 vの位置は二次元座標(x,y) 情報拡散モデルはICモデル クエリ Q=(R,...
  • @wiki全体から「Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph」で調べる

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