todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Competitive Influence Maximization in Social Networks」で検索した結果

• Competitive Influence Maximization in Social Networks
  Competitive Influence Maximization in Social Networks Shishir Bharathi, David Kempe, Mahyar Salek WINE 2007 概要 モデル 辺uvが試行成功したら指数分布の遅延時間T_{uv}が発生する bプレイヤがサイズk_i以下の集合S_iを選択する 複数人が選択した頂点はランダムに誰かの頂点になる これでカスケードをしていく 純粋戦略ナッシュ均衡は無い（？） 混合戦略ナッシュ均衡は有る 戦略 もし，他の人の戦略が固定されていたら 自分の戦略に対するσは単調かつ劣モジュラ First Mover Strategies Influence Max...
• Influence Blocking Maximization in Social Networks under the Competitive ...
  ...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つθ+とθ- 状態はinactive，-active，+activeの3つ 基本的には普通に拡散していく，早い者...
• 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という速いアルゴリズムを提案 実験して提案手法とベースラインを比較 モデル・問...
• 論文一覧
  .../競合 Competitive Influence Maximization in Social Networks WINE 2007 Word of Mouth Rumor Dissemination in Social Networks SIROCCO 2008 Threshold Models for Competitive Influence in Social Networks WINE 2010 Influence Maximization in Social Networks When Negative Opinions May Emerge ... Influence Blocking Maximization in Social Networks under the Competitive ... Maximiz...
• Efficient Influence Maximization in Social Networks
  Efficient Influence Maximization in Social Networks Wei Chen, Yajun Wang, Siyu Yang In KDD 2009 概要 Wei Chen 劇場の始まりっぽい influence maximization のアルゴリズムを2つ提案 greedy based algorithm の高速化 ヒューリスティックによるinfluence spreadの近似 アルゴリズム NewGreedyIC seedを選ぶためにグラフをR=20000個作る Sから到達可能なノードは省く vから到達可能なノード数を計算、これがmarginに相当 これの計算は自明ではないが論文ではlinearでできると...
• Influence Diffusion Dynamics and Influence Maximization in Social Networks ...
  Influence Diffusion Dynamics and Influence Maximization in Social Networks with Friend and Foe Relationships Yanhua Li, Wei Chen, Yajun Wang, Zhi-Li Zhang WSDM 2013 概要 voter modelを拡張 元はunsigned network signed networkにした 味方とは同じ意見（色） 敵とは違う意見（色） 最初の色の分布を与えた時の挙動を解析（面白い） このモデルでinfluence maximization ある意味で簡単 確率的振舞を計算するのが超大変 Voter ...
• Personalized Influence Maximization on Social Networks
  Personalized Influence Maximization on Social Networks Jing Guo, Peng Zhang, Chuan Zhou, Yanan Cao, Li Guo 中国科学院の人たち CIKM 2013 概要 influence maximizationの亜種を考案 特定のノードにinfluenceする確率を上げたい この問題設定における性質とかを挙げてアルゴリズムを設計 普通のと、それの高速化と、ヒューリスティクスっぽいの ベースラインを比較していいことを示した 問題 目的関数 $$ R_w(U) = \mathbb{E}^U[1_{\{w \in X\}}] $$ ターゲットwがUによりinfluence...
• 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 Maximization in Dynamic Social Networks
  Influence Maximization in Dynamic Social Networks Honglei Zhuang, Yihan Sun, Jie Tang, Jialin Zhang, Xiaoming Sun ICDM 2013 概要 influence max.の動的グラフ版を考える 現実的設定で、どこの頂点をprobeし直せば良いかを問題とする b頂点だけ更新できる influence spreadのずれがでかそうな頂点を頑張って計算する 実験の結果ベースラインよりかなり良かった 問題設定 G^t 時刻tでのグラフ b probeできる頂点数 b頂点を更新した時に、そのグラフで計算した解と真の解ができるだけ近くなるようにしたい ...
• 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)でアクティベーションが成功する これは一回だけ ...
• 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...
• 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 ↑...
• IRIE: Scalable and Robust Influence Maximization in Social Networks
  IRIE Scalable and Robust Influence Maximization in Social Networks Kyomin Jung, Wooram Heo, Wei Chen In ICDM 2012 概要 Influence maximizationを超高速に求めるアルゴリズムを開発 しかもロバストに良い解を発見する アルゴリズム $$ \sigma(S \cup \{v\}) - \sigma(S) $$を次で近似する $$ r(v) = (1-AP_S(v))\left[ 1+\alpha \sum_{vu}p_{vu}r(u) \right] $$ AP_S(v) Sがvをactivateする確率 $$ AP_S(v) - \sum_{s \in ...
• 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は感染しない 手法 σが小さくなるノードを貪欲に選んでいく 実験 比較...
• Efficient algorithms for influence maximization in social networks
  Efficient algorithms for influence maximization in social networks Yi-Cheng Chen, Wen-Chih Peng, Suh-Yin Lee KAIS 2012 概要 CDH Community and Degree Heuristic CDH-KcutとCDH-SHRINK Heat diffusion model (HDM) 熱拡散（物理現象） f_i(t) 時刻tでのv_iの熱 初期状態t=0が与えられる 近傍からΔtの間影響を受ける iの変化量 = αΣ_j [f_j(t)-f_i(t)] 熱がθを超えたらアクティブになったとする シードに対してf(t_0)=h_0とセットする...
• 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...
• 気になった論文
  ...under the Competitive Linear Threshold Model 競合相手の情報伝播をブロック LDAGの拡張（Wei Chen 似たの無かったっけ？ A Framework for the Evaluation and Management of Network Centrality 経路数ベースの中心性の一般的に定義 それの最適化問題k辺とるとか Structural Analysis in Multi-Relational Social Networks 一般化Stochastic Block Models 関係の予測？ Fast Random Walk Graph Kernel O(n^3)/O(m^2)時間 low rank活用？ ...
• 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 残った辺 カスケードの仕...
• 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とす...
• 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) =...
• Influence maximization in complex networks through optimal percolation
  Influence maximization in complex networks through optimal percolation Flaviano Morone, Hernán A. Makse Nature 2015 概要 頂点を削除して最大の連結成分を最小化したい 強影響力頂点抽出，immunization，コミュニティ検出 既存手法…ヒューリスティクス 本手法 最適化問題 ある種の貪欲アルゴリズム 輪郭 最適パーコレーション 固有値の最小化問題 上を解く 最適パーコレーション $$ \nu_i $$の計算
• Opinion maximization in social networks
  Opinion maximization in social networks Aristides Gionis, Evimaria Terzi, Panayiotis Tsaparas SDM 2013 概要 意見を表現するモデル 影響最大化のフレームワーク？として問題定式化 導入 意見 ICやLTでは表現できない バイナリ状態も微妙 というわけで，実数の状態をとるよ 問題定義 モデル [Bindel, Kleinberg, Oren. FOCS11]に従う [Friedkin, Johnsen. 90]も大事 Social influence and opinions 内部意見 s_i と表明意見 z_i がある ...
• 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を以下で近似 $$ ...
• 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して木っぽくパスを広げる（同じ頂点がいくつかある...
• Influence Maximization with Novelty Decay in Social Networks
  Influence Maximization with Novelty Decay in Social Networks Shanshan Feng, Xuefeng Chen, Gao Cong, Yifeng Zeng, Yeow Meng Chee, Yanping Xiang AAAI 2014 概要 目新しさの減衰を考慮した情報拡散モデル 非単調だし非劣モジュラ Novelty Decay 実データセットを調査 n人の友達が既に影響されているとする nが大きい程，その人自信は影響されやすいけれど，徐々にその効果が弱まるはず (nの時の確率 / n-1の時の確率)みたいなものを計算すると，f(n) = γ^{n-1}くらい これを根拠 IC Model wi...
• 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が更新された時刻 どうやって早くなるの？ とりあえず、↑の値を全部計算済みだとする 最後に...
• 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モデルと同じ ...
• Extracting Influential Nodes for Information Diffusion on a Social Network
  Extracting Influential Nodes for Information Diffusion on a Social Network Masahiro Kimura, Kazumi Saito, Ryohei Nakano AAAI 2007 概要 influence maximizationの高速アルゴリズム ICとLT 提案手法 ICもLTもランダムグラフを考えればいい σの増加量を効率的にもとめる 事前にランダムグラフを作っておく シード集合 A Aから到達可能な頂点を除く 頂点uについて，↑で出来たグラフでuから到達可能な頂点数Fをもとめる uと同じ連結成分に入っている頂点vについて，σ_i(A∪{v})=σ_i(A)+Fとする ...
• 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 実験 ...
• 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...
• 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 Social Influence in Nearly Optimal Time
  Maximizing Social Influence in Nearly Optimal Time Christian Borgs, Michael Brautbar, Jennifer Chayes, Brendan Lucier first author有名？ SODA 2014 概要 influence maximization(IC model)の近似アルゴリズム 今までみたいに、各ノードからの到達可能ノード数や確率を求めるんじゃない 逆に考える 探索するノードの数をほぼ線形にboundしても良い解が出てくることを保証できる 提案手法 逆グラフを作る ノードをランダムに選び、逆グラフ上でシミュレートする v「に」伝搬する頂点を選んでいることに等しい ...
• 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 関...
• Influence Maximization in Near-Linear Time: A Martingale Approach
  Influence Maximization in Near-Linear Time A Martingale Approach Youze Tang, Yanchen Shi, Xiaokui Xiao SIGMOD 2015 概要 TIMInfluence Maximization Near-Optimal Time Complexity Meets Practical Efficiencyから更に改善しました 直接最適値の下限を推定するよ！ TIMよりめっちゃ速くなった TIMの問題点 最悪時には下限が最適値よりn/k倍悪い 下限の計算自体が結構（シード選択段階よりも）遅い 提案手法 Influence Maximization via Martingales (IMM)...
• Maximizing Influence in an Ising Network: A Mean-Field Optimal Solution
  Maximizing Influence in an Ising Network A Mean-Field Optimal Solution Christopher W. Lynn, Daniel D. Lee NIPS 2016 概要 Isingモデル上の影響最大化 意見＝スピン、外部影響＝外部磁場、影響力＝J 相互作用の反復による意見の「平衡」状態 平均場近似で解く 外部磁場に対して滑らかかつ凹になる十分条件 平均場の安定非負定常分布の存在に関する条件 実験もしたよ 問題定式化 Ising influence maximization $$ \Pr[\sigma_i(t+1) \mid \sigma(t)] = \frac{\exp\Bigl( \...
• 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にな...
• 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...
• 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) ...
• 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)
• 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内の頂点から出てる単...
• 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つ選んで採択するんだ...
• Which Targets to Contact First to Maximize Influence over Social Network
  Which Targets to Contact First to Maximize Influence over Social Network ソーシャルネットワーク上での影響を最大化するターゲットノード Kazumi Saito, Masahiro Kimura, Kouzou Ohhara, Hiroshi Motoda 概要だけ ちょっと違う影響最大化 G=(V,E),kに追加で 外部頂点x，辺確率r_xvが与えられる 頂点をk個選んでσ({x})を最大化 まとめ 当たり前だよなぁ？ JSAI 影響最大化 2014-09-26 23 02 31 (Fri)
• Influence Maximization in Big Networks: An Incremental Algorithm for ...
  Influence Maximization in Big Networks An Incremental Algorithm for Streaming Subgraph Influence Spread Estimation Weixue Lu, Peng Zhang, Chuan Zhou, Chun-Yi Liu, Li Gao IJCAI 2015 概要 小さい部分グラフに分割する 頂点を共有しうるが辺は互いに素 挑戦 部分グラフ間のシミュレーションが重なる 提案手法 M=シミュレーション回数 N=分割個数 $$ (V_i)_i $$ Vの被覆 $$ (E_i)_i $$ Eの分割 X_r = コインフリッピング結果rを表す01値ベクトル ...
• 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の近傍のアクティブ...
• Cost-aware Targeted Viral Marketing in Billion-scale Networks
  Cost-aware Targeted Viral Marketing in Billion-scale Networks Hung T. Nguyen, Thang N. Dinh, My T. Thai INFOCOM 2016 概要 新しい問題 Cost-aware Targeted Viral Marketing ユーザ毎に最初の費用が違う ユーザ毎に影響させた事による効果が違う いい感じにすれば$$ 1-1/\sqrt{e} $$近似が可能 効率的アルゴリズム BCT：CTVMにもInfMaxにも適用可能 LISA [CSoNet 15]の後続 Cost-aware Targeted Viral Marketing 費用$$c(u)$$、利益$$b(u)$$、予算$...
• 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...
• 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 ...
• Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency
  Influence Maximization Near-Optimal Time Complexity Meets Practical Efficiency Youze Tang, Xiaokui Xiao, Yanchen Shi SIGMOD 2014 概要 RIS (SODA 14)を実用的に改良するよ！ 提案手法 TIM, TIM+ サンプリング回数をいい感じにしました。 $$ O(\epsilon^{-2}(k+\ell)(n+m)\log n) $$時間 ヒューリスティックで更に効率改善→TIM+ triggeringモデルにも拡張したよ 提案手法 Two-phase Influence Maximization (TIM) フェーズ1：サンプリング回数θを...
• Real-time Targeted Influence Maximization for Online Advertisements
  Real-time Targeted Influence Maximization for Online Advertisements Yuchen Li, Dongxiang Zhang, Kian-Lee Tan VLDB 2015 概要だけ Keyword-Based Targeted Influence Maximization トピックつきのモデル キーワード集合Tとシードサイズkが与えられる Tによって、頂点の重みが変わる(TF-IDFに基づいた奴)、Tに関して線形な感じ $$ \phi(v,T) = \sum_{w \in T}\mathrm{tf}_{w,v} \cdot \mathrm{idf}_w $$ if_wvはユーザvのワードwへの嗜好 だから"targeted...
• @wiki全体から「Competitive Influence Maximization in Social Networks」で調べる

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