todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Information Diffusion in Mobile Social Networks: The Speed Perspective」で検索した結果

• Information Diffusion in Mobile Social Networks: The Speed Perspective
  Information Diffusion in Mobile Social Networks The Speed Perspective Zongqing Lu, Yonggang Wen, Guohong Cao INFOCOM 2014 概要 拡散（時間）最小化問題 できるだけ早く全体に伝わって欲しい k-center 問題になる 近似比 log*n，時間 O(n^5)くらいしかない コミュニティベースのアルゴリズムを考案 分散集合被覆アルゴリズム（謎 問題定義 辺には重みがあって確率が決まる そういうのから期待遅延時間が定義できる max_v |(S,v)|を最小化したい！！ |(S,v)|はSからvに伝わる最小期待伝播時間 ...
• 論文一覧
  ...Nodes for Information Diffusion on a Social Network AAAI 2007 IMGPU GPU-Accelerated Influence Maximization in Large-Scale Social Networks TPDS 2014 Influence Maximization in Big Networks An Incremental Algorithm for ... IJCAI 2015 Influence at Scale Distributed Computation of Complex Contagion in Networks KDD 2015 Outward Influence and Cascade Size Estimation in Billion-scale...
• 気になった論文
  ...ection in Information Networks Fast Euclidean Minimum Spanning Tree Algorithm, Analysis, Applications Inferring Networks of Diffusion and Influence KDD 2011 Triangle Listing in Massive Networks and Its Applications KDD 2012 A Structural Cluster Kernel for Learning on Graphs Discovering Value from Community Activity on Focused Question-Answering Sites A Ca...
• Theory of Cooperation in Complex Social Networks
  Theory of Cooperation in Complex Social Networks Bijan Ranjbar-Sahraei, Haitham Bou Ammar, Daan Bloembergen, Karl Tuyls, Gerhard Weiss AAAI 2014 概要だけ Continuous-Action Iterated Prisoner s Dilemma (CAIPD) Modelなるモデルがある ソーシャルネットワーク上の協調の進化のためのモデル これをめちゃ解析（理論＋実験） evolutionary networksとsocial networksとは違うらしい 主な貢献は3つ 状態が収束する その証明がcoevolutionary netw...
• メニュー
  ...フ分割 辺分割 Information Sciences WI-IAT SNAM クラスタリング 相関クラスタリング 数え上げ モチーフ 最小頂点被覆 top-k収束頂点対 平均最短経路長最小化 CVaR 極大クリーク 不確実性グラフ 頑健グラフ 密グラフ 多様性 AAMAS 影響拡散 独立カスケード 並列分散 相互性 不確かなグラフ 影響力推定 CSoNet 劣モジュラ関数 劣モジュラ最大化 ストリームアルゴリズム 並列化 劣モジュラ 自然言語処理 uncertain graphs ネットワーク信頼性 最短経路 k-近傍 到達可能性 PAKDD 頻出部分グラフ 次数分布 時変モデル 頻出グラフ 近接中心性 DASFAA 頑健性 適応的劣モジュラ WASA MLG 最密部分グラフ AIS...
• 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)に従う 平均α/(α+β) 拡散の履歴から各α，βをインクリメントするだ...
• Finding Influential Nodes in a Social Network from Information Diffusion Data
  ...work 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 for Independent Cascade Model とほぼ同...
• 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...
• 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に適用 完全なひと月のデータ 情報がネットワークをジャンプしている ...
• 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という速いアルゴリズムを提案 実験して提案手法とベースラインを比較 モデル・問...
• The Role of Social Networks in Information Diffusion
  ...tworks in Information Diffusion Eytan Bakshy, Itamar Rosenn, Cameron Marlow, Lada Adamic In WWW 2012 メモ Y.Yoshidaさん 新しい情報は「疎遠」な友人から not 親しい友人 仕事とか 思ったよりは多いねというくらい 親しい友人の方が多い なんで？ 強い 情報がすぐ拡散 公募はすぐ埋まる 得る情報 Feed 友人のURLをシェア 外界 メールとか Feedを遮断 |V|=253M Feed有：6時間でシェア Feed無：2...
• Tractable Models for Information Diffusion in Social Networks
  Tractable Models for Information Diffusion in Social Networks Masahiro Kimura, Kazumi Saito PKDD 2006 概要（だけ） ICモデルでのσの計算がヤバイので違うモデルで計算する SPM (Shortest-Path Model) 確率的だけど最短路しか伝わらない SP1M 最短路か+1ずれた時間で伝わっても良い 頑張って数式を弄ると計算式が出てくる オリジナルが21日だったのが2時間とかになってハッピー 概要 影響最大化の中では古い方だなあ PKDD 影響最大化 情報拡散 情報拡散モデル 2014-07-01 23 24 06 (Tue)
• 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は明示的に与える と主張しているはず モデル ...
• 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...
• 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[...
• Scalable Methods for Adaptively Seeding a Social Network
  Scalable Methods for Adaptively Seeding a Social Network Thibaut Horel, Yaron Singer WWW 2015 概要 影響最大化の問題 … アクセスできる頂点には制限有 解決法 … 二段階アプローチ [Seeman-Singer. FOCS 13] 独立カスケード・線形閾値等で定数近似 独立カスケード・線形閾値等で定数近似 すごく遅い この論文 より簡単な拡散モデルで効率的近似手法 実験でスケーラビリティ 効果を検証 詳細は https //www.slideshare.net/secret/nIKkJnFLPQeMj WWW 影響最大化 情報拡散 2017/10/02
• 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...
• Locating the Source of Diffusion in Large-Scale Network
  Locating the Source of Diffusion in Large-Scale Network Pedro C. Pinto, Patrick Thiran, Martin Vetterli PRL 2012 概要 情報拡散の話 一部の頂点だけを観測して、「「発信源」」を推定する モデル化+実験 モデル 辺の時間 正規分布 負の値はごまかす 発信源 uniformly at randomに選択される 受信者 時刻+ソース 他の頂点に伝えない 理不尽な仮定はおかない 受信者がネットワークを分離したり、最初の観測時刻だけ記録 問題設定 入力 グラフ G=(V,E) 分布 ...
• 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とす...
• Dynamic social networks promote cooperation in experiments with humans
  Dynamic social networks promote cooperation in experiments with humans David G. Rand, Samuel Arbesman, Nicholas A. Christakis In PNAS 2011 メモ Y.Horita 社会的ネットワークの社会科学的研究 実証データをもとに理論・モデルを修正 協力 コストを払って他者に資源を与える行動 背景 実験でおかしかったところ 関係が静的だった ホントは誰と付き合うかは動的じゃね？ 動的ネットワークで実験 このpaper 実験 Amazon Mechanical Turksで囚人のジレン...
• 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は分からない いつ誰が記事を投稿 / 病...
• Human Wayfinding in Information Networks
  Human Wayfinding in Information Networks Robert West, Jure Leskovec Stanford univ. In WWW 2012 概要 クリックの列に関する大量のデータを解析 人間をどうナビゲートするか？ Wikispedia Game スタートとゴールが与えられるので、wikipediaだけ辿ってゴールを目指す リストとかの汎用的なページは確か見れない 人間の探索能力 ヒストグラムを見てみる shortest paths small-world human, effective human, incl. back-clicks human, drop-ou...
• 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 $$の計算
• 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)) つまり，遅延時間の分布が指数関数 他の関数でも使える 情報拡散過程は普通 ...
• 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とセットする...
• 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 スパム同士は結合...
• 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 ...
• Mining Social Networks Using Heat Diffusion Processes for Marketing ...
  Mining Social Networks Using Heat Diffusion Processes for Marketing Candidates Selection Hao Ma, Haixuan Yang, Michael R. Lyu, Irwin King CIKM 2008 概要 熱拡散過程によるモデリング 3つの拡散モデル，3つのアルゴリズム 製品採択に時間を入れる クラスタ（係数）を反映 正負の意見を伝える 熱拡散モデル 当然，物理現象 分類，次元削減とかに使われている 開発者・ターゲットは熱源として振る舞い，一杯熱を持ってる で，どんどん広がっていく f_t(x,t)=Δf(x,t) f(x,t) 時刻t...
• 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...
• Minimizing the expected complete influence time of a social network
  ...g 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}}{\sum_{i \in N(j)}w_{ij}} $$ の確率で活性化 自分の周囲の活性頂点の（重み付き）割合 τ(A) complete influence time ...
• 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)
• 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)でアクティベーションが成功する これは一回だけ ...
• Maximizing Submodular Set Function with Connectivity Constraint: Theory and ...
  ...enter for Information Technology Innovation（資訊科技創新研究中心） National Tsing Hua University（國立清華大學） INFOCOM 2013 概要 ワイヤレスネットワークのルーターの設置問題 submodular関数で表せる さらにルーターは連結であるという制約を追加 この設定でも近似アルゴリズムが設計できる 1/O(√k)近似 頂点に重みをつけたbudget版も考えた 実験：ヒューリスティクスより良いよ モチベーション ワイヤレスネットワークのルーター 下の2つの評価を良くしたい 被覆領域 スループット 現実的にはルーターは連結 ...
• 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 残った辺 カスケードの仕...
• 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...
• 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...
• 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...
• Predicting Japanese General Election in 2013 with Twitter: Considering ...
  Predicting Japanese General Election in 2013 with Twitter Considering Diffusion of Candidates Tweets Twitter における候補者の情報拡散に着目した国政選挙当選者予測 Nasuno Kaoru, Matsuo Yutaka JSAI 2014 関連研究 Twitterを使った選挙結果の予測 有権者に焦点 2010にうまおな論文が出たらしいが，2012年に否定されて，色々あって結局微妙っぽい 候補者に焦点 ほとんど無いっぽいよ！これやるよ！ アイデア 情報拡散の規模・多様度・候補者への忠誠度の指標 Twitterアカウントの状態の指標 をいれる...
• 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...
• 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して木っぽくパスを広げる（同じ頂点がいくつかある...
• 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...
• Tight Bounds for Influence in Diffusion Networks and Application to Bond ...
  Tight Bounds for Influence in Diffusion Networks and Application to Bond Percolation and Epidemiology Rémi Lemonnier, Kevin Scaman, Nicolas Vayatis NIPS 2014 概要だけ 情報拡散のサイズの期待値のバウンドが欲しい ネットワーク科学方面の結果は辺確率が一様の場合 拡散モデル 離散時間情報カスケード いつもの 連続時間情報カスケード 遅延時間の分布、T→∞だけ考える ランダムグラフ 到達可能なら拡散 無限時間後なので、ぶっちゃけ同じ（補題1） Hazard matrix ...
• 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...
• 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...
• 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を以下で近似 $$ ...
• 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 ...
• 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 ...
• 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する 予備知識みたいな...
• 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種類あるので、最大の確率はかなり小さく、代表的とは...
• @wiki全体から「Information Diffusion in Mobile Social Networks: The Speed Perspective」で調べる

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