todo314 @ ウィキ
todo314 @ ウィキ

Accelerating Graph Adjacency Matrix Multiplications with Forest

todo314 @ ウィキ内検索 / 「Accelerating Graph Adjacency Matrix Multiplications with Forest」で検索した結果

検索 :
  • 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( ...
  • 論文一覧
    ...thods for Accelerating PageRank Computations FAST-PPR Scaling Personalized PageRank Estimation for Large Graphs 動的更新 Link Evolution Analysis and Algorithms Fast Incremental and Personalized PageRank PageRank on an Evolving Graph Efficient PageRank Tracking in Evolving Networks 私，前原貴憲，河原林健一 バックボタン The Effect of the Back Button in a Random Walk Applica...
  • 気になった論文
    理論計算機科学 ACM Symposium on Theory of Computing STOC 2000 Circuit minimization problem A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions Improved algorithms for submodular function minimization and submodular flow On dual minimum cost flow algorithms The small-world phenomenon an algorithm perspective A random graph model for mass...
  • 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$を求めたい！...
  • メニュー
    メニュー トップページ 論文一覧 気になった論文 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...
  • 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...
  • From Machu_Picchu to rafting the urubamba river: Anticipating information ...
    From Machu_Picchu to "rafting the urubamba river" Anticipating information needs via the Entity-Query Graph Ilaria Bordino, Gianmarco De Francisci Morales, Ingmar Weber, Francesco Bonchi WSDM 2013 概要 今見ているwebページの内容から非自明かつ偶察力を有する少数かつ多様な検索クエリを提示 手法 ページ内容をWikipediaエンティティで表現 エンティティとクエリからなるグラフ上でPersonalized PageRank PageRankスコアの高いクエリを出力 実験 提...
  • 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...
  • 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...
  • Accelerated k-means with adaptive distance bounds
    Accelerated k-means with adaptive distance bounds Jonathan Drake, Greg Hamerly In NIPS? 2012 概要 Lloyd s algoの高速化 ベクトル間の距離の計算を刈る ElkanとHamerlyを混ぜた パラメータで アルゴリズム lower boundについて、b next-closest centersをorderedで持っておく bの値 k/8からk/4の間で調整する 実験 次元の変化 ElkanとHamerlyの間くらい 微妙じゃね？ どちらかには大体負けている… 中位では勝ってたわ 実デ...
  • 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カットを構成→必ず到達不可能 良く分から...
  • 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で同じ計算時間 ...
  • 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ネットワークでの応用例...
  • StaticGreedy: Solving the Scalability-Accuracy Dilemma in Influence Maximization
    StaticGreedy Solving the Scalability-Accuracy Dilemma in Influence Maximization Suqi Cheng, Huawei Shen, Junming Huang, Guoqing Zhang, Xueqi Cheng In CIKM 2013 ArXiv 2012 概要 実は今までのMonte-Carloは間違っていた！ 毎回ランダムグラフを作っているのが問題 そのせいで莫大な試行回数が要求される 俺が最強のMonte-Carloアルゴリズムを提案するぜ！ ランダムグラフを使いまわす Rは1/100に減った StaticGreedy R回ループ 各辺を割り当てられた確率に応じて消す...
  • How to Partition a Billion-Node Graph
    How to Partition a Billion-Node Graph Lu Wang, Yanghua Xiao, Bin Shao, Haixun Wang MSR ICDE 2014 概要 分散メモリシステムにグラフを載せることを考える どうやって分割すればイイ？ 部分グラフのサイズ、辺カット、等が評価基準 提案手法 multi-level propagation G頂点のグラフでも数時間で処理できたよ！ 背景 Kerninghan-Lin メモリベース グラフを二分していく クラスタ間の頂点を辺カットが小さくなるように交換 METIS Graph Coarseningをする 先にある程...
  • A Fast and Practical Bit-Vector Algorithm for the Longest Common Subsequence ...
    A Fast and Practical Bit-Vector Algorithm for the Longest Common Subsequence Problem Maxime Crochemore, Costas S. Iliopoulos, Yoan J. Pinzon, James F. Reid IPL(Information Processing Letters) 2001 概要 bit vectorによる爆速LCS、正確にはその長さ 時間 O(nm/w) 空間 O(m/w) w ビット数 事前知識 Σ アルファベット s=|Σ| LCSの時間計算量の下界 Ω(nlogm) 最速 Σサイズ制限無 $$ O(n^2 \log \l...
  • COMMIT: A Scalable Approach to Mining Communication Motifs from Dynamic Networks
    COMMIT A Scalable Approach to Mining Communication Motifs from Dynamic Networks Saket Gurukar, Sayan Ranu, Balaraman Ravindran SIGMOD 2015 概要 テンポラルネットワーク上で頻出するモチーフを抽出したい 次数列に変換，部分列マイニングで絞る Frequent subgraph mining A- B(1)とB- C(2) A- B(2)とB- C(1) 違うお グラフ同型問題的なので，時間的関係を考慮するのはちょいやばめ？ マイニング的手法…厳密でない 定義 辺はある時刻に瞬間的に発生 $$ |t_i - t_...
  • 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の長さ 数十 ~ 数百 ...
  • 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...
  • CINEMA: Conformity-Aware Greedy Algorithm for Influence Maximization in ...
    CINEMA Conformity-Aware Greedy Algorithm for Influence Maximization in Online Social Networks Hui Li, Sourav S Bhowmick, Aixin Sun EDBT 2013 Contribution conformity-aware cascade model(c^2 model) の提案 mag-list というデータ構造 CINEMA (Conformity-aware INfluEnce MAximization) 部分グラフに分割する←a novel approach ??? 何が問題なの？ ぶっちゃけよく分からん とにかく普通のIC・LTモデルはダメでconfo...
  • From Dango to Japanese Cakes: Query Reformulation Models and Patterns
    From "Dango" to "Japanese Cakes" Query Reformulation Models and Patterns Paolo Boldi, Francesco Bonchi, Carlos Castillo, Sebastiano Vigna 概要 Reformulation model QRT(query reformulation type)の分類 学習結果は精度92% Reformulation strategies QRTの列からミッションを探してパターンを見つける 手動（小さいデータ）と一致するよ！ Query Flow GraphをQRTでアノテート レコメンドをQFG上のランダムウォークでやる ...
  • Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for ...
    Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems Yin Tat Lee, Aaron Sidford In FOCS 2013 リプシッツ連続、強凸関数の最小化 加速座標勾配法 逆条件数κ^-1が0に近いとヤバイ 収束しにくい 加速勾配法・座標勾配法のマージ 今まではupdateがO(n)で遅い これをO(1)にしたヨ！！！ 遅延評価っぽいことをする FOCS 2013-11-03 02 19 09 (Sun)
  • The Pursuit of a Good Possible World: Extracting Representative Instances of ...
    The Pursuit of a Good Possible World Extracting Representative Instances of Uncertain Graphs Panos Parchas, Francesco Gullo, Dimitris Papadias Francesco Bonchi SIGMOD 2014 概要 Uncertain graphsを扱うのは大変 サンプリングは標本数が多くなる 問題：最短経路長，パターンマイニング，部分グラフ探索 問題毎にアドホックに開発されている→既存の枠組みが無駄→辛い あるグラフで代表させたい 元の性質を保ったまま，決定的な代表的グラフを作るよ 元の性質=（今回は）期待頂点次数 平均次数リワイヤ(AD...
  • 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) 普通...
  • Sparsification of Influence Networks
    Sparsification of Influence Networks Michael Mathioudakis, Francesco Bonchi, Carlos Castillo, Aristides Gionis, Antti Ukkonen KDD 2011 概要 Yahoo! Research, Barcelonaの方々 尤度最大化という観点で辺をk本残す問題を提案 近似がNP-hard 最適解は頑張ってDPできる 貪欲アルゴリズムを提案（最適解に近い） 実験したら最強 influence maximizationにも使えるよ！ モデル とりあえず，トレースから確率を推定したい カスケードのトレースは頂点と時刻のペアの列とする (v,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)を求めないで頑...
  • The Effect of the Back Button in a Random Walk: Application for PageRank
    The Effect of the Back Button in a Random Walk Application for PageRank Fabien Mathieu, Mohamed Bouklit WWW 2004 概要 バックボタンを入れたPageRankを考える 計算も早そう Back Button Model Reversible Back バックボタンの効果 1つ前の「状態」に戻る 2回バックすると，今いるページに戻る 記憶領域は前の状態一つだけ どれかの辺をたどる確率とバックボタンの確率は同じ t+1ステップ目でwからvに遷移する確率 Pr[今wにいてwvを辿る]+Pr[vからwに移動した状態でバック] (wv∈E) Pr...
  • 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 = ...
  • Social Influence Spectrum with Guarantees: Computing More in Less Time
    Social Influence Spectrum with Guarantees Computing More in Less Time Dinh, Thang and Nguyen, Hung and Ghosh, Preetam and Mayo, Michael CSoNet 2015 概要 新しいアルゴリズムLISA $$k=1,\ldots,n$$について同時に解けるよ！ $$ O(\epsilon^{-2}\ln \frac{2}{\delta} (n+m)) $$時間だよ！ 提案手法 Linear-time Influence Spectrum Algorithm (LISA) 終了条件が重要 $$ \Upsilon_L = 1+4.6\epsilon^{-2}...
  • Predicting Japanese General Election in 2013 with Twitter: Considering ...
    Predicting Japanese General Election in 2013 with Twitter Considering Diffusion of Candidates Tweets Twitter における候補者の情報拡散に着目した国政選挙当選者予測 Nasuno Kaoru, Matsuo Yutaka JSAI 2014 関連研究 Twitterを使った選挙結果の予測 有権者に焦点 2010にうまおな論文が出たらしいが，2012年に否定されて，色々あって結局微妙っぽい 候補者に焦点 ほとんど無いっぽいよ！これやるよ！ アイデア 情報拡散の規模・多様度・候補者への忠誠度の指標 Twitterアカウントの状態の指標 をいれる...
  • Viral Marketing Meets Social Advertising: Ad Allocation with Minimum Regret
    Viral Marketing Meets Social Advertising Ad Allocation with Minimum Regret Çigdem Aslay, Wei Lu, Francesco Bonchi, Amit Goyal, Laks V. S. Lakshmanan VLDB 2015 概要 ソーシャルネットワーク上で広告マーケティングをしたい 今までのは伝播を未考慮 ホスト、広告主、ユーザの関係をうまく定式化 ホスト…自分の利益を最大化するように、ユーザに広告を配置 広告主…エンゲージメント毎にホストへ（予算の範囲で）金を支払う ユーザ…タイムラインに大量の広告が流れてくるとやだ 貪欲アルゴリズム…regretに関する保証 問題定式化 ...
  • Piggybacking on Social Networks
    Piggybacking on Social Networks Aristides Gionis, Flavio Junqueira, Vincent Leroy, Marco Serafini, Ingmar Weber In VLDB 2013 岩田さん Piggybacking? おんぶ 概要 巨大なSNS クラスタ係数を利用してスループット向上 ↑最適化問題 アルゴリズム O(log n)近似 Hadoop用のヒューリスティクス スループット とりあえず1ユーザに1台のサーバ 実際は1台が複数ユーザ 定式化 Social Dissemination Problem 辺 ...
  • Stochastic Submodular Maximization: The Case of Coverage Functions
    Stochastic Submodular Maximization The Case of Coverage Functions Mohammad Reza Karimi, Mario Lucic, Hamed Hassani, Andreas Krause NIPS 2017 概要 確率的劣モジュラ最大化のための新しい手法を提案 まずは、被覆関数から 連続拡張をさらに緩和した問題を直接解いてから元に戻す 問題 目的関数 $$ f(S) = \mathbb{E}_{\gamma \sim \Gamma}[f_\gamma(S)] $$ 影響最大化なら、影響グラフからサンプルしたグラフ上で到達可能な頂点数 線形連続拡張 $$ F(\bm{x}) = \mathbb{E}...
  • 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...
  • Triadic Measures on Graphs: The Power of Wedge Sampling
    Triadic Measures on Graphs The Power of Wedge Sampling C. Seshadhri, Ali Pinar, Tamara G. Kolda SDM 2013 概要 クラスタ係数、次数毎のとか、色々を統一的なフレームワークでもとめる wedgeを適当な重みでサンプリングしてtriangleを数えるだけ サンプルサイズがグラフのサイズに依存しないところがポイント シンプルにboundが出る 提案手法 サンプリングの方法 基本的にはwedgeをとってきて、それがtriangleを構成するか？を判定する global clustering coefficient choose(deg(v), 2)に比例する確率でv...
  • Extracting Analyzing and Visualizing Triangle K-Core Motifs within Networks
    Extracting Analyzing and Visualizing Triangle K-Core Motifs within Networks Yang Zhang, Srinivasan Parthasarathy ICDE 2012 概要 Triangle K-Core なる密グラフの概念を提案 かなり速く抽出できる しかも動的更新もできる template pattern cliquesをサポート 可視化とかイベント検出とか Triangle K-Core 部分グラフG がTriangle K-Core G 内の各辺がk個以上の三角形に含まれている 辺eのMaximum Triangle K-Core eを含む部分グラフG_eでTri...
  • 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はコスト高 ｰ すこしの頂点（アンカー）だけに設置 互いに距離が小さい所は通信 その距離が分からない場合...
  • 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(...
  • Approximation Algorithms for Regret-Bounded Vehicle Routing and Applications ...
    Approximation Algorithms for Regret-Bounded Vehicle Routing and Applications to Distance-Constrained Vehicle Routing Zachary Friggstad, Chaitanya Swamy STOC 2014 概要 Approximation Algorithms for Regret-Bounded Vehicle Routingについて 30.86近似アルゴリズム 今までO(log n)近似 RVRP 入力 完全グラフ 距離 三角不等式 始点r 整数R rを始点とするパスの集合で次を満たす 全頂点が少なくとも1つに被...
  • Anytime Influence Bounds and the Explosive Behavior of Continuous-Time ...
    Anytime Influence Bounds and the Explosive Behavior of Continuous-Time Diffusion Networks Kevin Scaman, Rémi Lemonnier, Nicolas Vayatis NIPS 2015 概要だけ Tight Bounds for Influence in Diffusion Networks and Application to Bond ...の続き Hazard matrixを拡張するために、Laplace変換を導入した定義をしている 証明しているもの ある時刻での影響拡散の上限 Critical time（いつ拡散がでかくなるか）の下限 特定の確率設定や、SIRモデルでの応用 先...
  • Robust Optimization for Non-Convex Objectives
    Robust Optimization for Non-Convex Objectives Robert Chen, Brendan Lucier, Yaron Singer, Vasilis Syrgkanis NIPS 2017 概要 シナリオごとの最適化をしたい→関数族の上で最悪時を扱います（ロバスト最適化） $$\alpha$$-近似ベイズ信託があれば良い 応用 ニューラルネットでの統計的学習…色んな損失関数をロバストに最適化 影響最大化…Robust Influence Maximizationを踏襲してるが、なんでも使える 問題定式化と提案手法 解きたい $$ \min_{x \in {\cal X}} \max_{i \in [m]} L_i(x) = \tau $...
  • CELF++: Optimizing the Greedy Algorithm for Influence Maximization in Social ...
    CELF++ Optimizing the Greedy Algorithm for Influence Maximization in Social Networks Amit Goyal, Wei Lu, Laks V.S. Lakshmanan 何かよく見るな名前 WWW 2011 CELF++ CELFを速くしたよ！！！ 頂点uは→を持つ u.mg1, u.prev_best, u.mg2, u.flag mg1 Sに対するマージン prev_best u以前に見た中でbest mg2 S+prev_bestに対するマージン flag 最後にmg1が更新された時刻 どうやって早くなるの？ とりあえず、↑の値を全部計算済みだとする 最後に...
  • Super mediator - A new centrality measure of node importance for information ...
    Super mediator - A new centrality measure of node importance for information diffusion over social network Kazumi Saito, Masahiro Kimura, Kouzou Ohara, Hiroshi Motoda Information Sciences 2015 メモ Uncorrected Proof 概要 影響最大化の解は影響力が高いが，影響力が強い頂点はそれだけではない super mediator 消すとσが下がる 色々な中心性との違いを実験的に見る 定義 Data-driven super mediator ある頂点の拡散過程を沢...
  • A Dual-tree Algorithm for Fast k-means Clustering with Large k
    ...eg-Moore. Accelerating exact k-means algorithms with geometric reasoning. KDD 99]というのが地味に強い まとめ 理論的な面では期待したほど良くなかった 意外と決定版は無い 反復回数はどれも同じだけど、複数反復をまとめてスキップ出来ないのだろうか SDM k-means クラスタリング 2017/04/11
  • Spectral Counting of Triangles in Power-Law Networks via Element-Wise ...
    Spectral Counting of Triangles in Power-Law Networks via Element-Wise Sparsification 概要 三角形の個数を早く求めたい 辺を確率1-pで削除 残った辺に重み1/pを割り振る 固有値で近似 何か速いよ！( (ﾟ∀ﾟ∩ 提案手法 まず，隣接行列を低ランクに近似 高固有値だけ計算する Lanczos methodというのを使い固有値を大きい順に求めていく 現在の固有値の三乗和に対する寄与がtot以下になったら打ち切り Eigen Triangle $$ \Delta(G) = \frac{1}{6}\sum_{i=1}^{n}\lambda_i^3 $$ でかい...
  • 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...
  • Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale ...
    Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale Social Networks Wei Chen, Chi Wang, Yajun Wang In KDD 2010 概要 MIAモデルというのを使ってinfluence maximizationを高速化 アルゴリズム maximum influence paths (MIP) v- uへの伝搬は最短経路だけを考える しきい値θ以下の伝搬は無視する Dijkstraの途中で打ち切る maximum influence arborescence model influence spreadを以下で近似 $$ ...
  • Information Diffusion and External Influence in Networks
    Information Diffusion and External Influence in Networks Seth Myers, Chenguang Zhu, Jure Leskovec In KDD 2012 メモ http //cs.stanford.edu/people/jure/pubs/ext-kdd12.pdf アブスト influence の始まりってどこ？ってのを考える influence の伝わり方は2パターンある ノード-ノードを伝って ネットワーク外から これに注目 新しいモデル フィッティングしやすいパラメータ Twitterに適用 完全なひと月のデータ 情報がネットワークをジャンプしている ...
  • 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} $$ ...
  • Efficient and Accurate Query Evaluation on Uncertain Graphs via Recursive ...
    Efficient and Accurate Query Evaluation on Uncertain Graphs via Recursive Stratified Sampling Rong-Hua Li, Jeffrey Xu Yu, Rui Mao, Tan Jin ICDE 2014 概要 よくある期待値クエリ評価と閾値クエリ評価を計算したい 愚直のMonte-Carloは分散が悪いので、 階層的な標本をする推定器を提案 影響力評価と期待信頼距離クエリに応用 解く問題 クエリ頂点q、何らかの評価関数φq(G) 期待値クエリ $$ \mathbf{E}_{G \sim \mathcal{G}}[\phi_q(G)] $$ 閾値クエリ $$ \mathbf{Pr}_{G ...
  • @wiki全体から「Accelerating Graph Adjacency Matrix Multiplications with Forest」で調べる

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