todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Distributed Set Reachability」で検索した結果

• Distributed Set Reachability
  Distributed Set Reachability Sairam Gurajada, Martin Theobald SIGMOD 2016 概要だけ S-T間で到達可能な頂点対を並列計算で頑張る 並列の意味…頂点集合の分割＋カット 並列到達可能性"s→t?"[Fang-Wang-Wu. VLDB 12] Master-Slave Slave (Giに入る)×(Giから出る)で到達可能な頂点対を計算 sやtがある場合 Master Slaveの情報とカット情報を元に判定 カットだけなるグラフは小さいはず 頑張った所 到達可能な意味で同じ部分をまとめる、とかして事前にいい感じのを作る 色々と微妙 SIGMOD ...
• 気になった論文
  ...lexity of Distributed ?-Approximations Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search FOCS 2015 Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP If the Current Clique Algorithms are Optimal, so is Valiant s Parser Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time Approximately Counting Trian...
• 論文一覧
  ...at Scale Distributed Computation of Complex Contagion in Networks KDD 2015 Outward Influence and Cascade Size Estimation in Billion-scale Networks SIGMETRICS 2017 RIS Maximizing Social Influence in Nearly Optimal Time SODA 2014 Influence Maximization Near-Optimal Time Complexity Meets Practical Efficiency SIGMOD 2014 Social Influence Spectrum with Guarantees Computin...
• BMC: An Efficient Method to Evaluate Probabilistic Reachability Queries
  BMC An Efficient Method to Evaluate Probabilistic Reachability Queries Ke Zhu, Wenjie Zhang, Gaoping Zhu, Ying Zhang, Xuemin Lin DASFAA 2011 概要 $$ \mathrm{rel}_{\mathcal{G}}(s,t) \theta? $$に答えたい 適当にrel(s,t)の上限を求める手法 駄目なら工夫したMonte-Carlo 提案手法 上限計算 out Pr[sから距離l以上遠くへ到達可能] in Pr[tへ距離m以上遠くへ到達可能] C B(s,l)とB(t,m)の間の「互いに素」なカットの集合 「カットが切られな...
• Learning Diffusion Probability based on Node Attributes in Social Networks
  Learning Diffusion Probability based on Node Attributes in Social Networks Kazumi Saito, Kouzou Ohara, Yuki Yamagishi, Masahiro Kimura, Hiroshi Motoda ISMIS 2011 概要 拡張した情報拡散モデル 時間遅延付き 頂点属性付き（新しい） パラメータ学習を提案 人口データで実験 上手くいった！ AsICモデル 実際の情報拡散は離散時間なワケがない p_uv 伝播確率 r_uv 遅延時間のパラメータ 遅延時間は指数分布 頂点属性 頂点vはJ個の属性を持つ，j番目はv...
• The Price of Stability for Undirected Broadcast Network Design with Fair ...
  The Price of Stability for Undirected Broadcast Network Design with Fair Cost Allocation is Constant Vittorio Bilò, Michele Flammini, Luca Moscardelli In FOCS 2013 ブロードキャストゲーム nプレイヤー s1,…sn 1ゴール t 各々はsi- tを目指す プレイヤーiのコスト Σ_e c(e)/(eを使った人数) 例えばケーブルだったら、皆でコストを等分配 各プレイヤーのコストの総和が社会的コスト このゲームにはNash均衡がある cost Nash均衡 / cost 社会的最適 Contri...
• 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)に従う 平均α/(α+β) 拡散の履歴から各α，βをインクリメントするだ...
• Latent Feature Independent Cascade Model for Social Propagation
  ...arallel Distributed Processing Techniques Applications 概要 頂点属性っぽいのがついたICモデル 特徴が潜在的なのがポイント Learning Diffusion Probability based on Node Attributes in Social Networksは明示的に与える と主張しているはず モデル 確率p_uvと遅延時間r_uv p_uv = 1/[1+exp(-x_u・y_v-γ)] シグモイド関数 x_uとy_uはK次元正規分布に従うとする 遅延時間は指数分布から これは全体で一定のパラメータr_uv=rをもつ パラメータ学習（略） ...
• メニュー
  メニュー トップページ 論文一覧 気になった論文 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...
• More Effective Distributed ML via a Stale Synchronous Parallel Parameter Server
  More Effective Distributed ML via a Stale Synchronous Parallel Parameter Server 分散機械学習 理論と実用のトレードオフを実現したい 複数マシンでやる問題 ネットワークアクセスが重い マシン性能が固定でない 理論サイド アルゴリズムの正しさ・収束性 仮定が非現実的 実装サイド 動くけど正しいのか？ 既存アプローチはあるけれど… 無駄な待ち時間 提案手法SSP イテレーション回数の差に上限sを設ける 基本非同期、だけど離れすぎることは無い 理論的保証があるのが良い NIPS 2014-01-24 14 18 48 (Fri)
• iRoad: A Framework For Scalable Predictive Query Processing On Road Networks
  iRoad A Framework For Scalable Predictive Query Processing On Road Networks Abdeltawab M. Hendawi, Jie Bao, and Mohamed F. Mokbel In VLDB 2013 メモ 何となくこんなのも読んでみる ミネソタ大学の人々 概要 IRoad フレームワークというものを作った 動くオブジェクトの予測クエリ 予測クエリ 点予測 範囲予測 KNN予測 集団予測 データ構造reachability tree 時間T以内に到達可能なノードを保持（？） 仮定 オブジェクトは最短経路を通る 大体30分 ...
• 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...
• 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...
• Efficiently Anonymizing Social Networks with Reachability Preservation
  Efficiently Anonymizing Social Networks with Reachability Preservation Xiangyu Liu, Bin Wang, Xiaochun Yang CIKM 2013 概要 匿名化の話 Kleinbergのに考え方は似てる 目標 個人情報を隠しつつ、なんかのクエリ=到達可能性を処理する k-degree anonymous 敵がvを次数情報のみから頂点を特定できる確率は1/k以下 有向グラフだけど、in-degとout-degがそれぞれ等しい頂点はk個以上 Reachability Preserving Anonymization 問題設定 入力 G=(V,E), 整数k ...
• Fast Reliability Search in Uncertain Graphs
  Fast Reliability Search in Uncertain Graphs Arijit Khan, Francesco Bonchi, Aristides Gionis, Francesco Gullo EDBT 2014 概要 信頼性検索…確率η以上でSから到達可能な頂点集合 索引RQ-tree 階層的クラスタリング クエリ評価 候補生成…最大流ベース 検証… 下界ベース 候補集合に関するサンプリング 精度 0.95、再現率 0.75で爆速 提案手法 RQ-tree…頂点集合の階層的分割 クエリ処理 候補生成 Rout(S,C) = Sから「Cの外の頂点」へ到達する確率 Rout(...
• A Data-Based Approach to Social Influence Maximization
  A Data-Based Approach to Social Influence Maximization Amit Goyal, Francesco Bonchi, Laks V. S. Lakshmanan VLDB 2012 概要 Data-Basedの意味：伝播確率をデータから推定するのではなく、直接σを推定する Credit Distribution Modelというモデルを提案 NP-hardでsubmodular σ_CDでの最大化が良いし速い！！ 何でこんなことになったのか いろんなモデルを使って実験してみよう weighted cascade model trivalency model uniform IC model EMアルゴリズ...
• Probabilistic Solutions of Influence Propagation on Networks
  Probabilistic Solutions of Influence Propagation on Networks Miao Zhang, Chunni Dai, Chris Ding, Enhong Chen 色々いるし名前を知らん CIKM 2013 概要 新しいinfluence spreadの計算方法 包除原理？ 実験もしてオリジナルより速くなったよ！ Exact influence spread n=3,4,5について、頑張ってinfluence spreadを厳密計算する 3頂点について 1がseed パターンを全部考えて、2、3がactiveになる確率を求めた でも、もっと簡単にできる 1から2がactiveにな...
• 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ネットワークでの応用例...
• Outward Influence and Cascade Size Estimation in Billion-scale Networks
  ...at Scale Distributed Computation of Complex Contagion in NetworksよりΩ(log^4 n)倍速いよ！ 定義・性質・予備知識 outward influenceの定義：$$ I_{o}(S) = I(S)-|S| $$ 劣モジュラだけど、非単調 常に$$X_i \leq b$$なら、$$ O(\frac{1}{\epsilon^2} \ln (\frac{2}{\delta}) \frac{b}{\mu_X}) $$回のサンプリングでいつもの近似を達成できる outwardは$$ \mu_X \approx 0 $$な時があり、やばお アルゴリズム importance sampling 条件付け＝Sの近傍の一つ...
• 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...
• Streaming Graph Partitioning for Large Distributed Graphs
  ...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 $$ を満たすようにする 目標 cross ...
• Minimizing Seed Set Selection with Probabilistic Coverage Guarantee in a ...
  Minimizing Seed Set Selection with Probabilistic Coverage Guarantee in a Social Network Peng Zhang, Wei Chen, Xiaoming Sun, Yajun Wang, Jialin Zhang KDD 2014 概要 大きいカスケードが「起こりやすい」ようにシードを選びたい 期待値の代わりに確率を議論するのがミソ この問題は劣モジュラでない 色々解析 動機付け トピックがある閾値まで広まって欲しい tipping point 当然シードセットは小さくしたい しかも確率保証つきで 問題定義 独立カスケードモデル Seed Mini...
• 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 スパム同士は結合...
• 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カットを構成→必ず到達不可能 良く分から...
• Catching the head, tail, and everything in between: a streaming algorithm ...
  Catching the head, tail, and everything in between a streaming algorithm for the degree distribution Olivia Simpson, C. Seshadhri, Andrew McGregor ICDM 2015 概要 ストリームで次数分布を求めたい 精確には累積分布 普通にやると，tail部分の精度が酷いことに（というか破滅）なる head／tailそれぞれに推定器を用意 Relative Hausdorff距離というナイスな距離を導入 実験では↑で評価→良 アルゴリズム 各辺が任意の順番にワンパスで来る n,mは知らない（というか不定） 辺削除／繰り返...
• 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に適用 完全なひと月のデータ 情報がネットワークをジャンプしている ...
• 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 ...
• Fast and Accurate k-means For Large Datasets
  Fast and Accurate k-means For Large Datasets Michael Shindler, Alex Wong, Adam Meyerson In NIPS 2011 メモ Shindlerはオレゴン州大学 WongはUC Los Angeles MeyersonはOnline Facility Locationの著者（単独）、でGoogle 概要 k-meansの爆速ストリームアルゴリズム Streaming k-means on Well-Clusterable Dataを簡易化して実装して実験しました、って感じ 理論がやばい（意味不 アルゴリズム 解の候補を高々O(klogn)個だけ保持しておく 入力点を新しく読む度...
• Control Profiles of Complex Networks
  Control Profiles of Complex Networks Justin Ruths, Derek Ruths Science 2014 概要 Network Controllabilityには次数分布が大事 特に重要なのはsourceとsinkの数 Network Controllability 微分方程式 dx(t)/dt = Ax(t)+Bu(t) A 隣接行列，B 入力行列 例 脳，人の意見，空港の利用客数 uをうまく設定してxを任意の状態にしたい 実際には… 辺の重みが分からん（ ＾ω＾）おっ Structural Controllability 辺の重みを（ゼロ以外に）定めてc...
• Diffusion Centrality in Social Networks
  Diffusion Centrality in Social Networks Chanhyun Kang, Cristian Molinaro, Sarit Kraus, Yuval Shavitt, V.S. Subrahmanian ASONAM 2012 概要（だけ） Degree, Betweenness, Stress, Closeness, Eigenvectorなどの中心性は何が伝わるかとかあんま考えていない そういうのを考慮した中心性 Diffusion Centrality 頂点・辺が述語（何が伝わるかみたいな）をもっている 色々性質があるので，何がどういう確率で伝わるかみたいなのをかなり細かく定義している 拡散過程の定義がもはや読んでない これで中心性を速く求める手法を作った...
• 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...
• Cost-effective Outbreak Detection in Networks
  Cost-effective Outbreak Detection in Networks Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, Natalie Glance KDD 2007 概要 outbreak detection問題を考える 色々あるけど目的関数はsubmodularになるのが多い 貪欲アルゴリズムで近似だ！ しかもsubmodularityを活かした高速化手法+online boundも考案 安定のLeskovecといったところか Outbreak detection モチベーション グラフ上でのカスケードを検知したい！ 水質汚染 ...
• 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) 普通...
• Computing Top-k Closeness Centrality Faster in Unweighted Graphs
  Computing Top-k Closeness Centrality Faster in Unweighted Graphs Elisabetta Bergamini, Michele Borassi, Pierluigi Crescenzi, Andrea Marino, Henning Meyerhenke ALENEX 2016 概要 近接中心性の上位k頂点を厳密に得たい 値が似通っているので，近似だと不十分 2種類の距離和の下限を使った簡単な枝刈り手法を提案 実験したら既存の枝刈り手法より探索辺数の意味で良かった 提案手法 戦略 各頂点からの距離和の下限を計算 下限の小さい順に見ていって遅延評価的にBFSをして確定させていく 最悪でn回BFSする ...
• Learning Influence Probabilities In Social Networks
  Learning Influence Probabilities In Social Networks Amit Goyal, Francesco Bonchi, Laks V.S. Lakshmanan WSDM 2010 概要 情報拡散の確率を学習したい 色々モデル提案 アクティブになる時刻も推定できるよ 問題定義 辺が作成されたタイムスタンプの考える (u, a, t_u)が一杯もらえる u ユーザー a 行動 t_u 時刻 (u,v)について，u,vの順に行動して，辺の作成時刻に矛盾が無ければ，uからvに伝搬した 各行動について，↑でありうる辺を取ってきた時の伝播グラフを考える 枠組み？ uの近傍のアクティブ...
• Influence Maximization in Continuous Time Diffusion Networks
  Influence Maximization in Continuous Time Diffusion Networks Manuel Gomez-Rodriguez, Bernhard Schölkopf ICML 2012 概要 Uncovering the Temporal Dynamics of Diffusion Networksの続き 連続時間モデル上の影響最大化を提案 影響拡散がシミュレーション以外の方法で効率的に求められる 1-1/e近似が可能 実験したよ 問題定式化 f(t_j | t_i; α_{i,j}) ∝ exp(-α_{i,j}(t_j-t_i)) つまり，遅延時間の分布が指数関数 他の関数でも使える 情報拡散過程は普通 ...
• 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版ではない原稿を読んだのでちょっと違う イントロ 確率的グラフ 辺に確率が割り振られている センサや実験による雑音 不安定な通信 リンク予測 秘匿性のための摂動 気になること...
• Discovering Frequent Subgraphs over Uncertain Graph Databases under ...
  Discovering Frequent Subgraphs over Uncertain Graph Databases under Probabilistic Semantics Zhaonian Zou, Hong Gao, Jianzhong Li KDD 2010 概要 Uncertain graphs上の頻出グラフマイニング $$\Pr [\{G_1, \ldots, G_n\}$$の$$\phi$$割合以上出現$$] \geq \tau$$な部分グラフを探す 例のごとく失敗確率δを与える 実験したら良さ気 動機付け等 Frequent Subgraph Pattern Mining on Uncertain Graph Dataは期待値（サポート） 期待値→構造パターン ...
• Overlapping Community Detection Using Seed Set Expansion
  Overlapping Community Detection Using Seed Set Expansion Joyce Jiyoung Whang, David F. Gleich, Inderjit S. Dhillon CIKM 2013 概要 コンダクタンスがいい感じになる重複コミュニティ検出手法を提案 提案手法 目標 全体をカバーしつつ、最大のコンダクタンスを小さくしたい Filtering whiskerを取り除きたいので、以下のような分解をする core=（ざっくりいうと）最大の2点連結成分 bridge=橋 whisker=残り Seeding 色々な手法でクラスタ中心を決める Graclus centers, Spr...
• Approximate Bayesian Image Interpretation using Generative Probabilistic ...
  Approximate Bayesian Image Interpretation using. Generative Probabilistic Graphics Programs 画像認識の新手法 応用 CAPTHA…これは文字ほげだ！ 道路認識 画像のシーンをシンボリックに 大きなコーパスが必要 トップダウンに考えるよ！ ボトムアップ 画像を要素に分解 それぞれを解釈 トップダウン 要素を仮定し画像を構成 その確率を出す モデル シーン…文字の種類とか 入力からこれを推定する レンダラを使った生成モデルで予測 Metropolis-Hastings 変数をちょっと動かしてほげ...
• 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...
• Scalable Influence Maximization in Social Networks under the Linear ...
  Scalable Influence Maximization in Social Networks under the Linear Threshold Model Wei Chen, Yifei Yuan, Li Zhang In ICDM 2010 概要 LTモデル用の高速アルゴリズム LTモデルでのσの計算は#P-hard DAGをとってきて、それの上で高速計算 #P-hardness 基本は単純経路の数え上げからの帰着 アルゴリズム LTモデルからlive-edge graphを考える eはw_eの確率で残ると書いてあるが、本当だろうか…？ Kempeのではもっと複雑なことをしていた こうすると、random graph上でのreacha...
• 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 \} $$ コンダクタンス（これが目的関数） ...
• Visual Analysis of Dynamic Networks using Change Centrality
  Visual Analysis of Dynamic Networks using Change Centrality Paolo Federico, Jürgen Pfeffer, Wolfgang Aigner, Silvia Miksch, Lukas Zenk ASONAM 2012 動的グラフに対する新しい中心性 $$ \frac{|N_{t_1}(i) \triangle N_{t_2}(i) |}{|N_{t_1}(i) \cup N_{t_2}(i)|} $$ N_t(i) 時刻tでのiからの距離が丁度1の頂点集合 分子は時刻t1からt2にかけて，追加/削除した辺の数 分母は時刻t1からt2にかけて，追加/削除/生存した辺の数 距離が1でなくてnの場合の一般ケース $$ r_{t_1,t_...
• Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms
  Truss Decomposition of Probabilistic Graphs Semantics and Algorithms Xin Huang, Wei Lu, Laks V.S. Lakshmanan SIGMOD 2016 概要 Core decomposition of uncertain graphsのk-trussへの拡張 局所的：部分グラフの各辺がk-2△に含まれる確率≧γ k-coreっぽく辺を取り除いていく 当該確率はDPで計算 大域的：部分グラフ全体がk-trussを含む≧γ 確率の厳密計算が#P-hard ランダムサンプリングして探索 実験しました 問題定式化 局所$$(k, \gamma)$$-...
• 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回ループ 各辺を割り当てられた確率に応じて消す...
• 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]...
• Algebraic Algorithms for b-Matching, Shortest Undirected Paths, and f-Factors
  Algebraic Algorithms for b-Matching, Shortest Undirected Paths, and f-Factors Harold N. Gabow, Pitor Sankowski In FOCS 2013 b-machingとf-factorのO(φ^ω)-time Algebraic Algorithm Algebraic Algorithm 行列演算で組み合わせ問題を乱択な感じで解く 例 二部グラフマッチング、マトロイド交差 最大マッチング 一般グラフのマッチング（Tutteの定理）を使ってみる Naiveなalgo. O(n^{ω+2}) G\ijがmax-matchingを持つか調べつつ辺を消していく ちょっと速いO(n^4...
• 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つに被...
• Make It or Break It: Manipulating Robustness in Large Networks
  Make It or Break It Manipulating Robustness in Large Networks Hau Chan, Leman Akoglu, Hanghang Tong SDM 2014 yamaguchiyutoさんのまとめ http //yamaguchiyuto.hatenablog.com/entry/2014/05/04/120705 概要 グラフの頑健性の研究 測定する 追跡する 操作する 比較する 色々な尺度 最大の連結成分の大きさ 逆最短経路長 代数的連結性 (algebraic connectivity) 理想は完全グラフ O(n^2)は現実的に無理 応用...
• @wiki全体から「Distributed Set Reachability」で調べる

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