todo314 @ ウィキ
todo314 @ ウィキ

Privacy Preserving Estimation of Social Influence

todo314 @ ウィキ内検索 / 「Privacy Preserving Estimation of Social Influence」で検索した結果

検索 :
  • Privacy Preserving Estimation of Social Influence
    Privacy Preserving Estimation of Social Influence Tamir Tassa, Francesco Bonchi EDBT 2014 概要だけ 情報拡散モデルには辺確率の推定が必要 実際には，2種類の人がいる グラフを持っているホスト カスケードのログを持っているサービス提供者（複数） 互いに情報を教えたくない，サービス提供者同士でも 実験では，通信費用を見ている EDBT 情報拡散 秘匿性保護 2015/03/10 1 40
  • 論文一覧
    ...eries Privacy Preserving Estimation of Social Influence ✔Fast Reliability Search in Uncertain Graphs EDBT 2015 Identifying Converging Pairs of Nodes on a Budget International Conference on Database Systems for Advanced Applications DASFAA 2011 BMC An Efficient Method to Evaluate Probabilistic Reachability Queries DASFAA 2016 Triangle-Based Repre...
  • 気になった論文
    ...ferential Privacy Maximizing Acceptance Probability for Active Friending in On-Line Social Networks KDD 2014 ✔Representative Clustering of Uncertain Data 代表的クラスタリングの集合を出力、真のクラスタリング結果とそれ程離れないように Streamed Approximate Counting of Distinct Elements Min-countやHyperLogLogよりも強い異なり数 ✔Correlation clustering in MapReduce Ravi Kumar Improving the modifi...
  • 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にな...
  • 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して木っぽくパスを広げる（同じ頂点がいくつかある...
  • On the Approximability of Influence in Social Networks
    On the Approximability of Influence in Social Networks Ning Chen SODA 2008 メモ程度に モデル 無向グラフG 閾値1≦t(v)≦deg(v) 近傍の内t(v)以上が活性化したら自分も活性化 Target Set Selection 問題 ある割合の頂点数を活性化するためのシードサイズを最小化したい ちょっと違うけどまあ 結果 $$ O(2^{\log^{1-\epsilon}n}) $$で近似できない（仮定のもと） Majority Thresholds 半分以上で活性化 Small Thresholds 小さい定数 Unan...
  • On Approximation of Real-World Influence Spread
    On Approximation of Real-World Influence Spread Yu Yang, Enhong Chen, Qi Liu, Biao Xiang, Tong Xu, Shafqat Ali Shad 中国科学技術大学 In PKDD 2012 概要 influenceの計算を近似+反復計算で p_v~Σp_uv*p_u．これをガウスザイデル p_v=1-Π(1-p_u*p_uv)はちゃんとしてる 嘘でした これに加えてヒューリスティクスでちょっと収束速めている アルゴリズム SSSbyStep ↑に書いた式で近似 GSbyStep 線形系で近似 SSSの簡易版 行列で表されるので、ガウス...
  • Structure-Preserving Sparsification of Social Networks
    Structure-Preserving Sparsification of Social Networks Gerd Lindner, Christian L. Staudt, Michael Hamann, Henning Meyerhenke, Dorothea Wagner ASONAM 2015 概要 疎化したグラフの性質を調べたよ "Local Degree"なる単純な手法で実は充分良いよ 辺数が元の20%でも、大体保存される 比較手法 Random Edge (RE) 一様ランダムに辺を選んでいく Triangles 属する△の個数の多い辺を順に残す Local Similarity (LS) 得点 = J(N(u...
  • A Note on Maximizing the Spread of Influence in Social Networks
    A Note on Maximizing the Spread of Influence in Social Networks Eyal Even-Dar, Asaf Shapira WINE 2007 概要 投票者モデルで考えてみたよ 投票者モデルと問題定義 f_t(v) = 0/1 時刻tでのvの意見 f_t+1(v)…vの近傍uを等確率で選びf_t(u)に更新 入力 各頂点のコストc_v 予算B 目標時刻t 出力 頂点集合S Σ_v∈S c_v ≦ B E[Σf_t(v)]を最大化 時刻0にSの頂点を1にする 定理とか ランダムウォークに関連がある 近傍1つ選んで採択するんだ...
  • 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]...
  • 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...
  • 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...
  • 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種類あるので、最大の確率はかなり小さく、代表的とは...
  • 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)に従う 平均α/(α+β) 拡散の履歴から各α，βをインクリメントするだ...
  • Negative Influence Minimizing by Blocking Nodes in Social Networks
    Negative Influence Minimizing by Blocking Nodes in Social Networks Senzhang Wang, Xiaojian Zhao, Yan Chen, Zhoujun Li, Kai Zhang, Jiali Xia AAAI Workshop 2013 概要 ノードを取り除いて影響の拡散を抑えたい！ ウイルス，誤情報等 Negative Influence Minimization 感染シード(given) I ブロック S(|S|=k) 目標 minimize σ(I; V-S) Sは感染しない 手法 σが小さくなるノードを貪欲に選んでいく 実験 比較...
  • 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...
  • 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...
  • 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...
  • 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 ...
  • 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を...
  • Minimizing the expected complete influence time of a social network
    Minimizing the expected complete influence time of a social network Yaodong Ni, Lei Xie, Zhi-Qiang Liu Information Sciences 2010 概要 最終的に全員が活性化する MP3プレーヤーがカセットテープの上位互換，みたいに駆逐される設定 時間が勝負 incremental chance model 無向グラフ G=(V,E,w) jumping 1つ以上の活性頂点を近傍に持つ sleeping 近傍は全て非活性 時刻tで頂点jは $$ p_t^j = \frac{\sum_{i \in N(j) \mathrm{active}}w_{ij}...
  • 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 ...
  • 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がアクテ...
  • A user-centric model of voting intention from Social Media
    A user-centric model of voting intention from Social Media Vasileios Lampos, Daniel Preotiuc-Pietro, Trevor Cohn ACL 2013 株価，伝染病，地震の被害予測 世論調査 媒体 個別訪問，電話（ランダム），インターネット 媒体としてのTwitter 利点 低コスト，若者の意見を反映 欠点 ユーザの偏り（暇人ばっか），嘘 線形回帰モデル 目的変数=係数*説明変数+決定項 y=ax+c 正則化項の目的 パラメータがスパースになれるよ！ 提案モデル Bilinear Elastic Net(BEN) 単語頻度とユーザ...
  • 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に適用 完全なひと月のデータ 情報がネットワークをジャンプしている ...
  • 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する 予備知識みたいな...
  • 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 サイズが大きくなる...
  • 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)につい...
  • Uncovering the Temporal Dynamics of Diffusion Networks
    Uncovering the Temporal Dynamics of Diffusion Networks Manuel Gomez-Rodriguez, David Balduzzi, Bernhard Schölkopf ICML 2011 概要 遅延を含めた情報拡散モデル spatiotemporal 時空の カスケードだけから，辺とその情報を学習 関連 Inferring Networks of Diffusion and Influence On the Convexity of Latent Social Network Inference モチベーション whereとwhenはわかるがhowとwhyは分からない いつ誰が記事を投稿 / 病...
  • 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 他の時刻で辺があったらまた試行できる ...
  • 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...
  • The complexity of influence maximization problem in the deterministic linear ...
    The complexity of influence maximization problem in the deterministic linear threshold model Zaixin Lu, Wei Zhang, WeiliWu, Joonmo Kim, Bin Fu Journal of Combinatorial Optimization 2012 概要だけ linear threshold modelのしきい値を固定したバージョンを考える 近似の難しさ しきい値を固定するとσは多項式時間で求められる 当たり前。なぜO(n^2)で求めている？ 何でこんなことをしたのか若干謎
  • Importance Sketching of Influence Dynamics in Billion-scale Networks
    Importance Sketching of Influence Dynamics in Billion-scale Networks Hung T. Nguyen, Tri P. Nguyen, NhatHai Phan, Thang N. Dinh ICDM 2017 概要 RR集合のImportance sampling版を作った 既存のRISベースの手法に適用できますよ とても速いです 動機づけ 単一頂点からなるカスケードが良く発生する メモリ消費✘処理時間✘推定効率✘ 独立カスケードの場合 WCなら30%くらい、TRIなら90%くらいはsingular 枠組み$$\mathsf{SKIS}$$ と Importance Influence...
  • 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 スパム同士は結合...
  • 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...
  • 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モデルでの応用 先...
  • 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) ...
  • Efficient Estimation of Influence Functions for SIS Model on Social Networks
    Efficient Estimation of Influence Functions for SIS Model on Social Networks Masahiro Kimura, Kazumi Saito, Hiroshi Motoda IJCAI 2009 概要 SISモデルのシミュレートを高速化 ボンドパーコレーションと適当な枝刈り 精度には影響しない 実験で数百倍以上速い SISモデル 時刻は離散的 最初に頂点を活性化 活性頂点は非活性な頂点を与えられた確率で活性化 成功したら次の時刻に活性化 何も影響されなかった頂点は次の時刻に非活性化 求めたいもの σ(v,t) 時刻0でvを活性化したとき，時刻tで活性な頂点の数...
  • 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)| $$を最小化せよ ...
  • Influence Maximization with Viral Product Design
    Influence Maximization with Viral Product Design Nicola Barbieri, Francesco Bonchi SDM 2014 概要 製品設計も考えた情報拡散LTモデル 同じアイテムでも特徴が違うとσが変わる 頂点+特徴の選択が必要 提案モデルF-TMの学習手法 最適化アルゴリズムを頑張る share-of-choice (SoC)問題 u_{f,l}^i 人i，特徴f，レベルlについてその効果 負もありうる 各人iについて Σ_fΣ_l x_{f,l} u_{f,l}^i ≧ h_i ならiはこの製品を採用する x_{f,l}は0-1変数，これを決定するのが問題 fe...
  • 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上のランダムウォークでやる ...
  • 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ノードを一様サンプリングす...
  • 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 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)) つまり，遅延時間の分布が指数関数 他の関数でも使える 情報拡散過程は普通 ...
  • 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で高速化 定式化 ...
  • The Importance of Communities for Learning to Influence
    The Importance of Communities for Learning to Influence Eric Balkanski, Nicole Immorlica, Yaron Singer NIPS 2017 概要 The Power of Optimization from Samplesはcurvature制限時だった 今回は影響最大化をコミュニティ構造が明らかな場合、OPSの枠組みでなんとかするよ コミュニティの大きさを捉えられそうなアルゴリズムを提案 SBMの簡単な設定で近似比を証明 アルゴリズム COmmunity Pruning from Samples 設定 無向なので、基本的に連結成分の大きさ（の和）の期待値が影響力になる underlyingな...
  • Inferring Networks of Diffusion and Influence
    Inferring Networks of Diffusion and Influence Manuel Gomez-Rodriguez, Jure Leskovec, Andreas Krause In KDD 2010 よしださん 概要 ネットワークは明示的に得られない 薬物乱用者の注射針共有ネットワーク 分かるのは現象、結果だけ 結果からネットワークを推定できる？ 結果 O(n^2)時間でできる グラフの候補は2^n*n通り 拡散モデル 伝播時間 P(Δ)∝exp(Δ/α) or 1/Δ^α u- v の伝播の尤度を設定 外部からの伝播もあり 特定のカスケードに対して有向木Tの尤度を各辺について掛け合わせる ...
  • Influence analysis of information diffusion focusing on directed networks
    Influence analysis of information diffusion focusing on directed networks 有向ネットワークの構造が情報拡散に与える影響の分析 Shohei Usui, Fujio Toriumi, Takatsugu Hirayama, Kenji Mase JSAI 2014 概要だけ 有向グラフで色々なパラメータを変化させるとどうなるか？ パラメータ例 相互リンクの割合 到達可能な頂点数の総和 出次数と入次数の相関係数 次数のベキ指数 実験結果 AID Σ_v σ(v)/n 出次数と入次数の相関が高いとAIDが高い 解釈 情報発信能力と情報収集能力が共に高い頂点が多いと情報拡散能力の高いグラフ...
  • Simpath: An Efficient Algorithm for Influence Maximization under the Linear ...
    Simpath An Efficient Algorithm for Influence Maximization under the Linear Threshold Model Amit Goyal, Wei Lu, Laks V. S. Lakshmanan ICDM 2011 LTモデルの性質 $$ \sigma(S) = \sum_{v \in V} \Upsilon_{S,v} $$ Υ_S,v = Sがvを活性化させる確率 $$ \Upsilon_{s,t} = \sum_{\pi \in \text{Path}(s,t)} \Pr[\pi] $$ By definition of the ``live-edge model と簡単に言うが… ※結局はσ({s})はsを始点とす...
  • 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の同時分布は分かる...
  • @wiki全体から「Privacy Preserving Estimation of Social Influence」で調べる

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