todo314 @ ウィキ
todo314 @ ウィキ

Topic-aware Social Influence Propagation Models

todo314 @ ウィキ内検索 / 「Topic-aware Social Influence Propagation Models」で検索した結果

検索 :
  • Topic-aware Social Influence Propagation Models
    Topic-aware Social Influence Propagation Models Topic-aware Social Influence Propagation Models Nicola Barbieri, Francesco Bonchi, Giuseppe Manco Yahoo! Research Barcelona ICDM 2012 概要 トピックを考慮したモデルにICとLTを拡張 期待値最大化でパラメータを見積もる 上のモデルは大変なので，ちょっとパラメータ数を減らしたモデルを考案 実験して普通のICより良かった Topic-awareモデル Topic-aware Independent Cascade Model (TIC) z...
  • 論文一覧
    ...works Topic-aware Social Influence Propagation Models Uncovering the Temporal Dynamics of Diffusion Networks モデリング 時間 A Data-Based Approach to Social Influence Maximization Time-Critical Influence Maximization in Social Networks with Time-Delayed ... Time Constrained Influence Maximization in Social Networks Uncovering the Temporal Dynamics of Diffusion Net...
  • 気になった論文
    理論計算機科学 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...
  • Influence Spread in Large-Scale Social Networks - A Belief Propagation Approach
    Influence Spread in Large-Scale Social Networks - A Belief Propagation Approach Huy Nguyen, Rong Zheng ECML PKDD 2012 概要だけ 大体PMIAの拡張みたいなもん DAGに変換して信念伝播法っぽいことをする ECMLPKDD 影響最大化 2014/12/11
  • Latent Feature Independent Cascade Model for Social Propagation
    Latent Feature Independent Cascade Model for Social Propagation Yuya Yoshikawa, Tomoharu Iwata, Hiroshi Sawada PDPTA 2013 International Conference on Parallel Distributed Processing Techniques Applications 概要 頂点属性っぽいのがついたICモデル 特徴が潜在的なのがポイント Learning Diffusion Probability based on Node Attributes in Social Networksは明示的に与える と主張しているはず モデル ...
  • Linear Computation for Independent Social Influence
    Linear Computation for Independent Social Influence Qi Liu, Biao Xiang, Lei Zhang, Enhong Chen, Chang Tan, Ji Chen ICDM 2013 概要だけ 何か頂点集合を取り除いた後の各頂点の影響力が知りたいらしい ここのモチベーションが分からん… linear social influence modelなるものを提案 簡単に言うと集合の影響力が各頂点の影響力の和 だから，行列で全て簡単に書ける 応用 頂点のランキング Top-k抽出 和なので，もっと簡単 まとめ 微妙… ICDM 情報拡散 情報拡散モデル ...
  • 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)に従う 平均α/(α+β) 拡散の履歴から各α，βをインクリメントするだ...
  • Influence and Correlation in Social Networks
    Influence and Correlation in Social Networks Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian KDD 2008 概要 社会的な繋がりは大事ですよ 相関（似た行動）を引き起こすのは、「社会影響」の所為？ 同類性とか他の色々な要素があって紛らわしい 単純なテストを考案 Flickrで調べたら、相関はあるけど影響の所為ではない 導入とか 既存研究「Flickrで友達同士のタグの語彙が似ている」 相関の源は？ influence 友達の最近の行動に引き起こされる homophily 同じゲームを持っている人は友達になりやすい e...
  • Threshold Models for Competitive Influence in Social Networks
    Threshold Models for Competitive Influence in Social Networks Allan Borodin, Yuval Filmus, Joel Oren WINE 2010 久しぶりの論文記事(ヽ´ω`) 概要 LTモデルを競合者付きモデルに拡張 劣モジュラどころか単調ですらないものもある Weight-Proportional Competitive Linear Threshold Model 頂点vはしきい値θ_vを持つ 活性近傍からの重みの和がθ_vになったら活性化 状態は3つ 非活性，活性A，活性B 活性Aの近傍の割合 活性Bの近傍の割合で確率的にAかBかに決まる S_B=∅なら元のLTモデルと同じ ...
  • On Influential Node Discovery in Dynamic Social Networks
    On Influential Node Discovery in Dynamic Social Networks Charu Aggarwal, Shuyang Lin, Philip S. Yu SDM 2012 概要 SN上のやりとりは瞬間的 その確率は瞬間を表す時間の関数 globally optimized forward trace approach locally optimized backward approach 動的モデル 頂点・辺はある時間帯に存在するみたいな感じ f_ij(δt) = a(1-exp(-λ_ij*δt)) δtの時間だけ辺ijが出現する時の伝播確率 (t1, t2)の間に辺(i, j)があるとする (t1, t2)をm分割してδt_iとす...
  • A Novel and Model Independent Approach for Efficient Influence Maximization ...
    A Novel and Model Independent Approach for Efficient Influence Maximization in Social Networks Hemank Lamba, Ramasuri Narayanam WISE 2013 概要 influence maximizationの手法は大体はモデルに強く依存する(・A・)ｲｸﾅｲ!! sparsificationするよ！ 精度を落とさずに数倍高速化 提案手法 ある頂点の近傍のスコアを出す スコアの出し方 色々な基準を大量に持ってくる 適当に重みを計算して足し合わせる スコアの大きい近傍をdeg(i)^eだけ残す 0 =e =1 実験 ...
  • Time-Critical Influence Maximization in Social Networks with Time-Delayed ...
    Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process Wei Chen, Wei Lu, Ning Zhang AAAI 2012 概要 ICモデルは時間制限を設けないからダメ 締切＋時間の遅延付きモデルを考案 高速(?)アルゴリズムも提案して実験 Independent Cascade with Meeting events 遭遇確率 m(u,v) 伝搬確率 p(u,v) 各ステップtで、アクティブな頂点uは非アクティブな頂点に確率m(u,v)で遭遇する 一回目の遭遇において確率p(u,v)でアクティベーションが成功する これは一回だけ ...
  • Dynamic Social Influence Analysis through Time-dependent Factor Graphs
    Dynamic Social Influence Analysis through Time-dependent Factor Graphs Chi Wang, Jie Tang, Jimeng Sun, Jiawei Han ASONAM 2011 概要 Pairwise Factor Graph (PFG) model Dynamic Factor Graph (DFG) model 問題設定 各時刻で重み付き辺が有ったり無かったり Pairwise influence μ_ij Dynamic social influence μ^t_ij G =(V,E,Ω)が欲しい Ωは時刻毎のμ_ij これって問題って言うのか？？？ ...
  • Efficient influence spread estimation for influence maximization under the ...
    Efficient influence spread estimation for influence maximization under the linear threshold model Zaixin Lu, Lidan Fan, Weili Wu, Bhavani Thuraisingham and Kai Yang Computational Social Networks 2014 概要 LTモデルの影響拡散を厳密or精度良く計算 4hop以内の影響について厳密計算 4hopはRandom walkで近似 性質 $$ \sigma(S) = \sum_{\pi \in P(S)} \prod_{e \in \pi} w(e) + |S| $$ P(S) = S内の頂点から出てる単...
  • 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...
  • Optimizing Budget Allocation Among Channels and Influencers
    Optimizing Budget Allocation Among Channels and Influencers Noga Alon, Iftah Gamzu, Moshe Tennenholtz WWW 2012 概要 最適予算配分問題の定式化 二部グラフ的な広告マーケティングを広告媒体視点と顧客視点のそれぞれでモデル化 ポイント 予算の配分という概念，今までは頂点を選ぶだけだった 影響の伝播は扱わない，予算の配分が主眼だから hardnessを解析 影響モデル G=(S,T,E) Sはソース，Tはターゲット，Eは辺集合 c_s (s∈S) 整数容量 B 予算 各ソースsに0以上c_s以下の整数予算b_sを割り当てる ...
  • 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...
  • 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で活性な頂点の数...
  • 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がアクテ...
  • UBLF: An Upper Bound Based Approach to Discover Influential Nodes in Social ...
    UBLF An Upper Bound Based Approach to Discover Influential Nodes in Social Networks Chuan Zhou, Peng Zhang, Jing Guo, Xingquan Zhu, Li Guo ICDM 2013 概要 CELFは最初のiterationが遅い！ もうちょっとだけ早くするんじゃ 大まかな見積もりを行列計算でやる タイトかは分からんが正しい上界が出る 上界順にMonte-Carloして、それが最上位って分かったら抜ける シミュレーション数95%カット 速度は2~5倍(´・ω・`) 提案手法 上界の見積もり方 Pr_{S,t}[v] Sが時刻tにvをactivat...
  • Influence Maximization in Social Networks When Negative Opinions May Emerge ...
    Influence Maximization in Social Networks When Negative Opinions May Emerge and Propagate Wei Chen, Alex Collins, Rachel Cummings, Te Ke, Zhenming Liu, David Rincon, Xiaorui Sun, Yajun Wang, Wei Wei, Yifei Yuan SDM 2011 概要 商品の質が低かったらdisる人も出るよねーをモデル化 質をパラメータに含めたNegative Opinion付き positiveな人数が目的関数ならsubmodularは保たれる 速い手法を作って実験してみたよ Independent Cascade Mode...
  • Influence Blocking Maximization in Social Networks under the Competitive ...
    Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model Xinran He, Guojie Song, Wei Chen, Qingye Jiang SDM 2012 概要 Competitive Linear Threshold モデルを考えたよ 目的関数は自分の最大化じゃなくて，相手の最大化だよ そうするとこのモデルではsubmodularだよ 目的関数の計算が大変なのでPMIAっぽいものを作った Competitive Linear Threshold Model 各辺には2つの重みw+とw-がある 各頂点の閾値も2つθ+とθ- 状態はin...
  • Time Constrained Influence Maximization in Social Networks
    Time Constrained Influence Maximization in Social Networks Bo Liu, Gao Cong, Dong Xu, Yifeng Zeng ICDM 2012 ※Wei ChenのTime-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Processとは独立らしい 概要 時間制限付きinfluence maximizationを提案 NP-hardだけどmonotoneかつsubmodular Influence Spreading Pathという速いアルゴリズムを提案 実験して提案手法とベースラインを比較 モデル・問...
  • 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して木っぽくパスを広げる（同じ頂点がいくつかある...
  • Learning Continuous-Time Information Diffusion Model for Social Behavioral ...
    Learning Continuous-Time Information Diffusion Model for Social Behavioral Data Analysis Kazumi Saito, Masahiro Kimura, Kouzou Ohara, Hiroshi Motoda ACML 2009 概要 Continuous-Time Independent Cascade Model r_uv 時間遅延パラメータ κ_uv 伝播確率 時刻tでuがactiveになったら， vを時刻t+δに確率κ_uvでactiveにする δはr_uvからきまる指数分布 学習したいパラメータ パラメータはrとκ カスケードの観測データD_Mは各頂点がactiveになっ...
  • 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...
  • 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が更新された時刻 どうやって早くなるの？ とりあえず、↑の値を全部計算済みだとする 最後に...
  • IMGPU: GPU-Accelerated Influence Maximization in Large-Scale Social Networks
    IMGPU GPU-Accelerated Influence Maximization in Large-Scale Social Networks Mo Li, Zhenjiang Li, Longfei Shangguan, Shaojie Tang, and Xiang-Yang Li TPDS 2014 概要 influence maximizationのGPUを取り入れたよ 既存手法の60倍速くなったよ IMGPU Bottom-Up Traversal Algorithm (BUTA) 元のグラフから沢山ランダムグラフを作る 各頂点のレベルを定義 末端までの最長距離 レベルで並列化するよ SCC内は全部同じなのでつぶすよ σ_S(u) =...
  • メニュー
    メニュー トップページ 論文一覧 気になった論文 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...
  • 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を...
  • 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する 予備知識みたいな...
  • Influential Nodes Selection: A Data Reconstruction Perspective
    Influential Nodes Selection A Data Reconstruction Perspective Zhefeng Wang, Hao Wang, Qi Liu, Enhong Chen SIGIR 2014 short paper 概要だけ 影響最大化の一手法 Influence Matrixなるものを作りそれ使ってk頂点選ぶらしい linear modelというモデルらしい よく分からん… SIGIR 影響最大化 2014/12/11
  • Holistic Influence Maximization: Combining Scalability and Efficiency with ...
    Holistic Influence Maximization Combining Scalability and Efficiency with Opinion-Aware Models Sainyam Galhotra, Akhil Arora, Shourya Roy SIGMOD 2016 概要 新しいモデル opinion-cum-interaction 高速アルゴリズム OSIM：OI用 EaSyIM：普通の影響最大化用 5%くらい質が悪いけど、良いよ！ モデル 省略します 　　,r´⌒ヽ,⌒ヽ,ヽ 　　　(⌒)､　　 .人　 λ＼､ .＿＿＿ 　　　 ＼. ＼　　　　、　ヽ.／ ー 　ー＼ 　　　　 |＼　＼ 　 　ヽ.／　（ ●）　（ ●） 　　　　 |　 ...
  • 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}...
  • An Upper Bound based Greedy Algorithm for Mining Top-k Influential Nodes in ...
    An Upper Bound based Greedy Algorithm for Mining Top-k Influential Nodes in Social Networks Chuan Zhou, Peng Zhang, Jing Guo, Li Guo WWW 2014 companion ポスター 概要 UBLF An Upper Bound Based Approach to Discover Influential Nodes in Social ...のLT版 CELFより5倍速い 提案手法 σ(S)=ΣΠw(e)の形でかける ↑は行列のべき乗和（有限）で上から抑えられる Wのべき乗和は(I-W)^-1で上から抑えられる 確率だから1以下って制約とか...
  • Maximizing Influence in a Competitive Social Network: A Follower's Perspective
    Maximizing Influence in a Competitive Social Network A Follower s Perspective Tim Carnes, Chandrashekhar Nagarajan, Stefan M. Wild, Anke van Zuylen ICEC 2007 概要 既に敵対するカスケードが広がっている時に，自分はどうシード集合を選択するか 2つのモデルを提案 NP-hardだけど1-1/e近似可能 モデル Aが自分で，Bが敵 I_B すでにBのシード集合 σ(I_A | I_B)が最大となるI_Aを選びたい ベースはICモデルと同じランダムグラフを考える E_a 残った辺 カスケードの仕...
  • 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アルゴリズ...
  • On minimizing budget and time in influence propagation over social networks
    On minimizing budget and time in influence propagation over social networks Amit Goyal, Francesco Bonchi, Laks V. S. Lakshmanan Social Network Analysis and Mining (SNAM) 2012 MINTSS (minimum target set selection) 入力 閾値η 出力 σ(S)≧ηなる最小サイズのS 提案手法 貪欲算法 σ(S)＜η-εの間，増量（min{σ(S+t),η}で考える）が最大の頂点をSに追加 定理1 貪欲算法で双基準近似 σ(S)≧η-ε |S|≦(1+ln(n/ε))OPT 関...
  • 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の近傍のアクティブ...
  • Maximizing the Long-term Integral Influence in Social Networks Under the ...
    Maximizing the Long-term Integral Influence in Social Networks Under the Voter Model Chuan Zhou, Peng Zhang, Wenyu Zang, Li Guo WWW 2014 companion ポスター 概要 Voter Modelにおける影響最大化 long-term integralを最大化したい 問題+提案手法 モデルはInfluence Diffusion Dynamics and Influence Maximization in Social Networks ... long-term integral influence maximization σ(S) = E[...
  • On Budgeted Influence Maximization in Social Networks
    On Budgeted Influence Maximization in Social Networks Huy Nguyen, Rong Zheng JSAC 2013 概要 頂点に単一でないコストがついた影響最大化 貪欲アルゴリズムをちょっと変形して1-1/√e近似 σを効率良く求めるためにDAGを作って信念伝搬っぽいことをやる Budgeted Influence Maximization 情報拡散モデルはIC max σ(S) s.t. c(S)≦b c(S)はc(u)(u∈S)の総和 [σ(S+v)-σ(S)]/c(v)で貪欲に選ぶと近似比が任意に悪くなる Leskovecのでも説明してたな… Improved Greedy ↑...
  • Information Propagation Game: a Tool to Acquire Human Playing Data for ...
    Information Propagation Game a Tool to Acquire Human Playing Data for MultiPlayer Influence Maximization on Social Networks Hung-Hsuan Chen, Yan-Bin Ciou, Shou-De Lin KDD 2012 概要だけ アプリケーションの話だったでござる competitiveなモデル 交互に頂点を選んで行ったり，先手がk頂点選んでから後手がk頂点選ぶとか こういうのをゲームのアプリケーションとして色々やってみる 特に面白い点は無かった KDD 影響最大化 情報拡散 2014-06-18 17 17 19 (Wed)
  • 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...
  • Computing and maximizing influence in linear threshold and triggering models
    Computing and maximizing influence in linear threshold and triggering models Justin T. Khim, Varun Jog, Po-Ling Loh NIPS 2016 概要 影響拡散の上下限を新たに作ったよ！ LTモデルとTriggeringモデル 下限は単調劣モジュラなので、最大化できて良い解になる 主結果 LTモデル 上限 $$ \leq |A| + \mathbf{b}_{\bar{A}}^\top (\mathbf{I}-\mathbf{B}_{\bar{A}\bar{A}})^{-1} \mathbf{1}_{\bar{A}} $$ An Upper Bound based Greed...
  • 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 ...
  • 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を以下で近似 $$ ...
  • Online Topic-aware Influence Maximization Queries
    Online Topic-aware Influence Maximization Queries Cigdem Aslay, Nicola Barbieri, Francesco Bonchi, Ricardo Baeza-Yates Yahoo Labs Barcelona EDBT 2014 概要 トピック付き影響最大化クエリ アイテム毎にトピックの重みが付いている 少量のクエリに対する答えを索引にしておく 問題定義 p_e^z トピックzに対する辺の確率 γ_i アイテムiに対するトピックの重みベクトル アイテムiのベクトルは p^i = Σ_z γ^z*p^z アイテム毎に確率が変わるけど，その上で影響最大化 枠組み H ...
  • How to Influence People with Partial Incentives
    How to Influence People with Partial Incentives Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, David L. Malec, S. Raghavan, Anshul Sawant, Morteza Zadimoghadam WWW 2014 概要 今までのinfluence maximizationは二者択一だった 実際には中間があるので，そういうモデルを作ったよ 分数版は積分版との違い モデル 積分影響モデル(integral influence model) Mossel and Rochの提案 f_v 2^V→[0,1] 辺を含んだ集合関数 ...
  • 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をする 先にある程...
  • @wiki全体から「Topic-aware Social Influence Propagation Models」で調べる

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