todo314 @ ウィキ
todo314 @ ウィキ

Learning Sums of Independent Integer Random Variables

todo314 @ ウィキ内検索 / 「Learning Sums of Independent Integer Random Variables」で検索した結果

検索 :
  • Learning Sums of Independent Integer Random Variables
    Learning Sums of Independent Integer Random Variables In FOCS 2013 「離散」変数に対する中心極限定理のようなもの S = Σi X_i X_i∈{0,…k-1} 各X_iは独立かつiid性が「無い」 それぞれ分布が違う 何個Sからドローすれば良い？ k=2の時 簡単らしい、正規分布で近似 k=3の時 偶奇性が出る、やべえ ランダムなのに周期性が出る 結果 (i)構造定理 S \approx c*離散正規分布 + {1,…c}値をとる確率変数 c∈{0,…,k-1} (ii)学習定理 poly(k,1/ε)個ドロー！！ X_...
  • 論文一覧
    ...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 Networks with Partial Knowledge Latent Feature Independent Cascade Model for Social Propagation Learning Diffusion Probability based on Node Attri...
  • 気になった論文
    ...ernel for Learning on Graphs Discovering Value from Community Activity on Focused Question-Answering Sites A Case Study of Stack Overflow Efficient Personalized PageRank with Accuracy Assurance Fast Algorithms for Maximal Clique Enumeration with Limited Memory Feature Grouping and Selection Over an Undirected Graph KDD 2013 Efficient Single-Source Shortest Path and...
  • Towards Context-Aware Search by Learning A Very Large Variable Length Hidden ...
    ...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は出てこない クエリ全体を見ると分かる→conte...
  • Learning Stochastic Models of Information Flow
    Learning Stochastic Models of Information Flow Luke Dickens, Ian Molloy, Jorge Lobo, Pau-Chen Cheng, Alessandra Russo ICDE 2012 概要 ICモデルの確率予測 Metropolis-Hastingsアルゴリズム attributed 影響の親が分かる unattributed 親が分からん 両方について実験 Attributedの場合 シード集合，活性頂点集合，拡散の履歴が分かる βICモデル 各辺の確率 ベータ分布(α_e,β_e)に従う 平均α/(α+β) 拡散の履歴から各α，βをインクリメントするだ...
  • Learnability of Influence in Networks
    Learnability of Influence in Networks Harikrishna Narasimhan, David C. Parkes, Yaron Singer NIPS 2015 概要だけ 様々な拡散モデルのPAC学習性 辺のパラメータそのものより、影響関数値の方が大事 Linear threshold 多層NN分類器っぽみ、VC次元 部分観測×、完全観測○ Independent cascade Covering numberで考えられる 完全観測○ Voter 線形回帰に帰着 部分観測○、完全観測○ 推定したいもの 影響関数$$ F 2^V \to [0,1]^n $$ シード集合に対して、各頂点...
  • 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の同時分布は分かる...
  • 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 Dango to Japanese Cakes: Query Reformulation Models and Patterns
    ...ve Learning a Query Reformulation Model 訓練データ 約1000個の(q,q ) 手でラベル付（←死ぬだろ…） 特徴量 27個 セッション長、セッション内の位置、(q,q )間の平均時間、類似度、等… モデリング isG?→isS?→isC?→isP?→ファッ！？ dango→japanese cakesは汎化 Empirical Study of Query Reformulations 超でかいデータに適用しよう！！ データセット Yahoo! UK Yahoo! US 長さ1のミッションには消えてもらう 分布を見てみる Pが多いね ...
  • 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...
  • 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...
  • Efficient Discovery of Frequent Subgraph Patterns in Uncertain Graph Databases
    Efficient Discovery of Frequent Subgraph Patterns in Uncertain Graph Databases Odysseas Papapetrou, Ekaterini Ioannou, Dimitrios Skoutas EDBT 2011 概要 MUSEFrequent Subgraph Pattern Mining on Uncertain Graph Dataの高速化 期待頻度の推定とかの，基本は同じ ↑をしない色々な上限見積もりで枝刈りをする subgraph isomorphismがかなり減って速くなる 提案手法 Edge index 各$$ (L_u, L_v, L_{uv}) $$について以下を保存 $$ L(u...
  • 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_...
  • 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 ...
  • Fast Discovery of Reliable k-terminal Subgraphs
    Fast Discovery of Reliable k-terminal Subgraphs Melissa Kasari, Hannu Toivonen, Petteri Hintsanen PAKDD 2010 概要 Uncertain graphがもらえるので、 クエリ頂点集合の連結確率を最大化する辺数に制限のついた部分グラフが欲しい 謎ヒューリスティクス提案 Path coveringを元に [Hintsanen-Toivonen-Sevon Fast discovery of reliable subnetworks]多分ASONAM 動機付け・問題定義 グラフがデカイので抽出するのが目的 興味があるもの（遺伝子とか）に関連あるのだけで良い 入...
  • Limiting the Spread of Misinformation in Social Networks
    Limiting the Spread of Misinformation in Social Networks Ceren Budak, Divyakant Agrawal, Amr El Abbadi In WWW 2011 概要 誤情報に対する訂正情報をイイ感じに流して誤情報の伝播を減らしたい submodular ってからのヒューリスティクス 問題 Multi-Campaign Independent Cascade Model 誤情報と訂正情報はそれぞれ辺ごとに異なる確率をとる 同時なら訂正優先 一度情報を受け取ったら以後変化しない 到達時間が大事 定式化 既に誤情報はいくらか伝わっている rターンたっている k...
  • 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版ではない原稿を読んだのでちょっと違う イントロ 確率的グラフ 辺に確率が割り振られている センサや実験による雑音 不安定な通信 リンク予測 秘匿性のための摂動 気になること...
  • 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}...
  • 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に適用 完全なひと月のデータ 情報がネットワークをジャンプしている ...
  • 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...
  • 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...
  • 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...
  • 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)だけど実験的にはもう少し速い（し精度も良い） 動機付けとか リバーネットワーク(?)の階層的構造を木構造で表現 その応...
  • 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がアクテ...
  • 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...
  • 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...
  • Revenue Maximization in Incentivized Social Advertising
    Revenue Maximization in Incentivized Social Advertising Çigdem Aslay, Francesco Bonchi, Laks V. S. Lakshmanan, Wei Lu VLDB 2017 概要 Viral Marketing Meets Social Advertising Ad Allocation with Minimum Regret VLDB 15の続き感 Incentivized ユーザにも収入の分け前を上げる設定 単調劣モジュラ最大化 with 分割マトロイド制約 (for 広告-シード配置) and 劣モジュラナップサック制約 (for 各広告主の予算) 2つの近似手法を提案して、RISで高速化 定式化 ...
  • 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}) $$を示した 実験的には数十倍速い 提案手法 設定 ...
  • 4chan and /b/: An Analysis of Anonymity and Ephemerality in a Large Online ...
    4chan and /b/ An Analysis of Anonymity and Ephemerality in a Large Online Community Michael S. Bernstein, Andrés Monroy-hernández, Drew Harry, Paul André, Katrina Panovich, Greg Vargas ICWSM 2011 概要 anonymity（匿名性）とephemerality（短命であること）の面から4chanを理解する 4chanと/b/ /b/はランダム掲示板 4chan全体の30%のトラフィック リプライしたりすると最初のページに浮上 15ページ目の最下層に行くと消されて`Page Not Found ...
  • 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 ...
  • 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)は簡単な線形関係に...
  • Analyzing Spammer's Social Networks for Fun and Profit
    Analyzing Spammer s Social Networks for Fun and Profit -- A Case Study of Cyber Criminal Ecosystem on Twitter Chao Yang, Robert Harkreader, Jialong Zhang, Seungwon Shin, Guofei Gu Texas A M Universityの人々 In WWW 2012 参考 http //www.slideshare.net/KuoE0/www2012-analyzing-spammers-social-networks-for-fun-and-profit 概要 Twitterのスパムに関するcase study スパム同士は結合...
  • Prediction of Information Diffusion Probabilities for Independent Cascade Model
    Prediction of Information Diffusion Probabilities for Independent Cascade Model Kazumi Saito, Ryohei Nakano, and Masahiro Kimura KES 2008 概要 ICモデルの辺の伝搬確率を沢山のカスケードから予測したい 頂点uが時刻tにアクティブになった情報 u,t が分かる 尤度を設定して期待値最大化 人工的なネットワークで実験するとそれなりに良い 問題 カスケードが与えられたとして vが時刻t+1でアクティブになる確率は↓ $$ P_v(t+1) = 1 - \prod_{u \in A_t}(1 - p_{uv}) $$ 伝搬確率p_uvを...
  • Lazy Walks Versus Walks with Backstep: Flavor of PageRank
    Lazy Walks Versus Walks with Backstep Flavor of PageRank Mieczysław A. Kłopotek, Sławomir T. Wierzcho´n, Krzysztof Ciesielski, Dariusz Czerski, Michał Drami´nski WI-IAT 2014 概要だけ PageRankの色々な変種を考える でも，PageRankで表現できる Lazy Random Walk x = (1-α)(0.5I+0.5P)x + αb 確率(1-α)/2 Random walk 確率(1-α)/2 留まる (lazy) 確率α Random jump Generalized Lazy Rando...
  • 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を...
  • 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 ある頂点の拡散過程を沢...
  • 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]...
  • On k-Path Covers and their Applications
    On k-Path Covers and their Applications Stefan Funke, André Nusser, Sabine Storandt VLDB 2014 best paper award スライド見てね 概要 Minimum k-All Path Cover (k-APC) 入力 有向グラフ G=(V,E) 整数k 出力 C⊆V であって，任意の長さkの単純経路πについて，C∩π≠∅ minimize |C| Minimum k-Shortest-Path Cover (k-SPC) [Tao, Sheng, Pei. SIGMOD 11] 入力 有向グラフ G=(V,E,c) ...
  • 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)| $$を最小化せよ ...
  • 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| $$番...
  • Fast Discovery of Reliable Subnetworks
    Fast Discovery of Reliable Subnetworks Petteri Hintsanen, Hannu Toivonen, Petteri Sevon ASONAM 2010 概要 The Most Reliable Subgraph Problemの2端子版のアルゴリズム ヒューリスティクス 提案手法 基本はランダムグラフのサンプリング Phase1 パスサンプリング s-tパスの候補集合を集める パスPを候補Cに足した時，Pr[C∨P]=Pr[C]+Pr[\bar{C}∧P]を最大化したい 怪しい感じ（保証等なし）に右項を近似計算する Phase2 部分グラフの構築 Pr[∨P]が最大となるようにCからパス部分集合を...
  • 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)を求めないで頑...
  • Minimizing the Spread of Contamination by Blocking Links in a Network
    Minimizing the Spread of Contamination by Blocking Links in a Network Masahiro Kimura, Kazumi Saito, Hiroshi Motoda AAAI 2008 概要 タイトルまんまの論文 汚染最小化問題 目的関数は各頂点のσの平均 既存の研究（Kempe依然）では，出次数の大きい順に頂点を消していけば大体良いとしてた 今回は辺を消す 問題定義 min 1/|V|Σσ(v) Eからk辺取り除ける 提案手法 最も目的関数が小さい辺を選ぶ貪欲アルゴリズム σの計算がやばい この著者らが考えたBond Percolationで高速化 実験 ...
  • Sensitivity of Diffusion Dynamics to Network Uncertainty
    Sensitivity of Diffusion Dynamics to Network Uncertainty Abhijin Adiga, Chris Kuhlman, Henning S. Mortveit, Anil Kumar S. Vullikanti ネットワークダイナミクスとかの研究所 AAAI 2013 概要 IC/LTモデルについて考える グラフに辺をちょっと足したら、influence spreadはどうなるか？がメイン アクティブノード数の期待値について適当な仮定をおいて解析 モデルとか ノイズモデル G=(V, E) 元のグラフ R(ε)=(V, E(ε)) (u, v)∈E(ε) wp ε/n G =G ⊕ R(ε)...
  • k-means++: The Advantages of Careful Seeding
    ...I Machine Learning Repositoryから 点数：1024, 494019, 4601 次元数：10, 35, 58 実験設定 kの値：10, 25, 50 各設定の試行回数：20 測定基準 最小コスト 平均コスト 計算時間の中央値 実験結果 k-means++の圧勝。コストも計算時間もk-meansに比べて優れている。 戯言 この論文の意義は、元のk-meansアルゴリズムには近似比保証が無いにも関わらず、初期値をイイ感じに選択するだけで、（期待値が）Θ(log k)近似になることを証明できることだと思う（そのまんまか…）。 SODA k-means 2013-10-07 16 00 46 (Mon...
  • 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 $$ でかい...
  • On the Hardness of Graph Anonymization
    On the Hardness of Graph Anonymization Charu C. Aggarwal, Yao Li, Philip S. Yu ICDM 2011 概要 匿名化手法は色々あるけど、ランダムに辺を追加削除するだけはヤバイ！ これを理論的に示す 特にソーシャルネットワークはmassiveかるsparseでこれが効いてくるらしい perturbation（摂動）に対してロバストなパラメータがある ↑を元にした手法を作り実験 Linkage Covariance $$ LinkCov(p,q) = \sum_{i}x_{pi}x_{qi}/n - \sum_{i}x_{pi}/n \sum_{j}x_{qj}/N $$ ロバスト性 確率f_aで辺を追...
  • Inferring the Underlying Structure of Information Cascades
    Inferring the Underlying Structure of Information Cascades Bo Zong, Yinghui Wu, Ambuj K. Singh, Xifeng Yan ICDM 2012 概要 ICモデルのカスケードが部分的に与えられる 時刻tにuがアクティブになったみたいな どういう経路を辿ったかの木を知りたい 時刻が厳密に一致する場合とそうでない場合の問題を定式化 難しいけど頑張って解く 実験したらいい感じ 問題定式化 カスケードC 根付き木で時刻がある bounded consistent tree 木上での根sから頂点v_iまでの距離が観測時刻t_i以下 d(s,v_i)≦t_i...
  • Recommendations to Boost Content Spread in Social Networks
    Recommendations to Boost Content Spread in Social Networks Vineet Chaoji, Sayan Ranu, Rajeev Rastogi, Rushi Bhatt WWW 2012 概要 コンテンツ共有は強力 どういう広がるかは連結関係が大事 共通近傍とか，類似度じゃなくて，コンテンツの量を考慮したい 辺を次数制約のもと挿入する 劣モジュラじゃないので，色々と改造する 近似アルゴリズム コンテンツ最大化問題 各頂点iについて $$ p_i $$ iが各近傍と共有する確率（独立） $$ c_i $$ iの作った／発見したコンテンツ $$ N_i $$ iと相性が良い頂点集合 ...
  • A General Framework of Hybrid Graph Sampling for Complex Network Analysis
    A General Framework of Hybrid Graph Sampling for Complex Network Analysis Xin Xu, Chul-Ho Lee, Do Young Eun INFOCOM 2014 概要 グラフをサンプリングしたい どっちかっていうとΣf(v)を近似したい ランダムウォークとかランダムジャンプとかある ランダムジャンプはたまに失敗する ↑を統合したのを考えて解析 分散（小さいと良）がランダムジャンプ確率に対して凸 既存手法 ランダムウォーク Simple Random Walk (SRW) with Re-weighting Metropolis-Hastings Random Walk ...
  • @wiki全体から「Learning Sums of Independent Integer Random Variables」で調べる

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