todo314 @ ウィキ
todo314 @ ウィキ

Efficient Discovery of Frequent Subgraph Patterns in Uncertain Graph Databases

todo314 @ ウィキ内検索 / 「Efficient Discovery of Frequent Subgraph Patterns in Uncertain Graph Databases」で検索した結果

検索 :
  • 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...
  • 気になった論文
    ... Oracles Efficient Dynamic Algorithms for the Steiner Tree. Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams. STOC 2016 Simpler Analysis and Enumeration of Parametric Minimum Cuts David Karger Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem Breaking the Logarithmic Barrier for Truthful Co...
  • 論文一覧
    ... 2011 Efficient Influence Maximization in Social Networks KDD 2009 StaticGreedy Solving the Scalability-Accuracy Dilemma in Influence Maximization CIKM 2013 UBLF An Upper Bound Based Approach to Discover Influential Nodes in Social ... ICDM 2013 An Upper Bound based Greedy Algorithm for Mining Top-k Influential Nodes in ... WWW 2014 Extracting Influential Nodes for Informa...
  • COMMIT: A Scalable Approach to Mining Communication Motifs from Dynamic Networks
    ...ニング Efficient Mining of Closed Repetitive Gapped Subsequences from a Sequence Database が使えるように頑張る SIGMOD モチーフ 2015/11/12
  • 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 動機付け・問題定義 グラフがデカイので抽出するのが目的 興味があるもの（遺伝子とか）に関連あるのだけで良い 入...
  • 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)| $$を最小化せよ ...
  • 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からパス部分集合を...
  • 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上のランダムウォークでやる ...
  • 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...
  • 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...
  • 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...
  • 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...
  • 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)は簡単な線形関係に...
  • 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は出てこない ...
  • 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ネットワークでの応用例...
  • Future Influence Ranking of Scientific Literature
    Future Influence Ranking of Scientific Literature Senzhang Wang, Sihong Xie, Xiaoming Zhang, Zhoujun Li, Philip S. Yu, Xinyu Shu SDM 2014 概要だけ 新しい論文や若手研究者の将来の影響力を知りたいよね？ 単語と単語共起を特徴として抽出 時間を入れた重み付きグラフ 何となく見てみたが特に興味なかった… SDM 2014-09-09 02 05 11 (Tue)
  • 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版ではない原稿を読んだのでちょっと違う イントロ 確率的グラフ 辺に確率が割り振られている センサや実験による雑音 不安定な通信 リンク予測 秘匿性のための摂動 気になること...
  • On the Streaming Complexity of Computing Local Clustering Coefficients
    On the Streaming Complexity of Computing Local Clustering Coefficients Konstantin Kutzkov, Rasmus Pagh WSDM 2013 概要 ワンパスでlocal clustering coefficientを求めたい ローカルなので、頂点ごと 辺リストが任意の順でもらえる 全く三角形が無い or 1/2以上のCCを持つ次数2d以上の頂点がある、かをある程度の確率でワンパスで判定するためにはΩ(m/d)ビット必要 ↑の限界にマッチした乱択アルゴリズムを考案 Lower bound Theorem 1 ワンパス乱択アルゴリズムが 次数2dの頂点はクラスタ係数0 ...
  • 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に適用 完全なひと月のデータ 情報がネットワークをジャンプしている ...
  • 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 ある頂点の拡散過程を沢...
  • 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| $$番...
  • ICWSM - A Great Catchy Name: Semi-Supervised Recognition of Sarcastic ...
    ICWSM - A Great Catchy Name Semi-Supervised Recognition of Sarcastic Sentences in Online Product Reviews Oren Tsur, Dmitry Davidov, Ari Rappoport ICWSM 2010 レビューが皮肉かどうか？ Greatとかあるとダルい 応用 意見抽出 要約 コーパス（データ） 1,2 皮肉でない 3,4,5 皮肉 これがアノテートされたコーパスで「教師つき学習」 普通はn-gramだけど今回はPhrase Patternを使う n-gramの一般拡張 語を変数で置換 変数は任意の語にマッチする ...
  • 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...
  • 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) ...
  • In Search of Influential Event Organizers in Online Social Networks
    In Search of Influential Event Organizers in Online Social Networks Kaiyu Feng, Gao Cong, Sourav S. Bhowmick, Shuai Ma SIGMOD 2014 概要 影響最大化 + 集合被覆のような問題 タイトルの通りイベント主催者を見つけるのが動機づけ 貪欲アルゴリズムと近似比2のアルゴリズムを提案 イントロ Plancast，Meetupというサービスが出てきている イベント主催者も影響力が有ったほうがいいね でも，分野横断とかだと色々な内容をカバーしてないと駄目だね this paper 問題定義 グラフ G = (V, E, w, A) ...
  • 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)$$-...
  • 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で辺を追...
  • 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 ...
  • Spheres of Influence for More Effective Viral Marketing
    Spheres of Influence for More Effective Viral Marketing Yasir Mehmood, Francesco Bonchi, David Garcia-Soriano SIGMOD 2016 概要 確率的な挙動の典型的なカスケードが欲しい 期待Jaccardを最小化する頂点集合を計算する問題 ありうるカスケード皆に程々に近い、安定性の指標でもある O(1)サンプルで定数倍近似 貪欲に勝った！ 動機づけ 「少数のスーパースター」よりも「多数の凡人」の方が信頼できる 個々の影響力は小さいけれど、クリティカルマス到達 最確カスケードは良くない カスケードは2^n種類あるので、最大の確率はかなり小さく、代表的とは...
  • 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(ε)...
  • Scalable and Parallelizable Processing of Influence Maximization for ...
    Scalable and Parallelizable Processing of Influence Maximization for Large-Scale Social Networks Jinha Kim, Seung-Keol Kim, Hwanjo Yu 浦項（ぽはん）工科大学校 In ICDE 2013 概要 並列化可能なアルゴリズム 競技相手はPMIA 質はCELF並、PMIAより良い 速度はPMIAより速い 提案手法 Independent Path Algorithm(IPA) 経路を指定したらそれを使う確率は全部かければ良い グラフがもらえた 有るノードからtraverseして木っぽくパスを広げる（同じ頂点がいくつかある...
  • Top-k Reliability Search on Uncertain Graphs
    Top-k Reliability Search on Uncertain Graphs Rong Zhu, Zhaonian Zou, Jianzhong Li ICDM 2015 概要 クエリ頂点sから連結する確率が上位kの頂点を返す問題 サンプリングしたグラフからのBFSをビット並列で高速化 サンプリングしたグラフはビットベクトルだけなので軽め 愚直な実装の10倍速い 問題定式化 入力 $$\mathcal{G}, s, k$$ 出力 $$ \textsf{Rel}_{\mathcal{G}}(s,v) $$が上位kの頂点 本当は"述語"があるがどうでもいいので割愛 Q. Fast Reliability Search in Unce...
  • 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がアクテ...
  • 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...
  • 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}...
  • Exact Computation of Influence Spread by Binary Decision Diagrams
    Exact Computation of Influence Spread by Binary Decision Diagrams Takanori Maehara, Hirofumi Suzuki, Masakazu Ishihata WWW 2017 概要 BDDで影響拡散を厳密計算する方法を提案 最大で100点くらいのグラフなら出来る！ 提案手法 到達可能性に関する情報を圧縮すれば良い もしBDDが構築できたら、後は任意の辺確率設定について、DAG上の動的計画法で計算できる 各頂点対(s,t)について構築できればOK；あとは併合すればいいので [sからtへ到達可能]を考えて、フロンティア法を実行 $$\texttt{isOneTerminal}$$ 今1の辺だけでsからt...
  • Community-based Greedy Algorithm for Mining Top-K Influential Nodes in ...
    Community-based Greedy Algorithm for Mining Top-K Influential Nodes in Mobile Social Networks Yu Wang, Gao Cong, Guojie Song, Kunqing Xie 焼きなましベースの人々と大体同じ KDD 2010 概要 NewGreedyIC（MixedGreedy）がstate-of-the-artだったころの話 どうしても時間がかかっちゃうので、コミュニティに分割することにした Community-based Greedy algorithm ちょっとおもしろい点 コミュニティ分割がICモデルのシミュレートで行われる ↑の後はDPする 予備知識みたいな...
  • 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}) $$を示した 実験的には数十倍速い 提案手法 設定 ...
  • 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ノードを一様サンプリングす...
  • Influence of the Dynamic Social Network Timeframe Type and Size on the Group ...
    Influence of the Dynamic Social Network Timeframe Type and Size on the Group Evolution Discovery Stanisław Saganowski, Piotr Bródka, Przemysław Kazienko ASONAM 2012 概要 GED (Group Evolution Discovery) 法のパラメータチューニングの解析 グループ発展 時間発展でコミュニティは変化していくが，それを下記に分類 Continuing(停滞) サイズに変化なし．頂点がちょっと変わるくらいならOK Shrinking サイズが小さくなる Growing サイズが大きくなる...
  • Maximizing the Extent of Spread in a Dynamic Network
    Maximizing the Extent of Spread in a Dynamic Network Habiba, Tanya Y. Berger-Wolf ? 2007 概要 動的ネットワークでinfluence maximizationやるお！ 問題定義 Dynamic Network G_t = (V_t, E_t)の列 特定の時点のものだから，辺は消えたりする Independent Cascade Modelの拡張 uが時刻tでactiveだったら(u_t, v_t)なv_tを伝播確率でactivate 成功したらvは時刻t+1でactiveになる 一旦activeになったらずっとactive 他の時刻で辺があったらまた試行できる ...
  • 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]...
  • 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の同時分布は分かる...
  • 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...
  • 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)) つまり，遅延時間の分布が指数関数 他の関数でも使える 情報拡散過程は普通 ...
  • Influence-based Network-oblivious Community Detection
    Influence-based Network-oblivious Community Detection Nicola Barbieri, Francesco Bonchi, Giuseppe Manco 最初の2人はYahoo Labs, Barcelona ICDM 2013 概要 ネットワークは与えられない 誰がいつ何かしたかのログが大量にある コミュニティ検出をしたい 情報拡散モデルをちょっと変えて検出させる 拡散具合はほぼコミュニティに依存するので、それを見積もろう Overview Q. ネットワークを再構築すればいいのでは？ A. 時間かかるので無理 例 Inferring Networks of Diffusion and Influe...
  • 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で高速化 定式化 ...
  • 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...
  • 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を...
  • 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)に従う 平均α/(α+β) 拡散の履歴から各α，βをインクリメントするだ...
  • @wiki全体から「Efficient Discovery of Frequent Subgraph Patterns in Uncertain Graph Databases」で調べる

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