todo314 @ ウィキ
todo314 @ ウィキ

Influence analysis of information diffusion focusing on directed networks

todo314 @ ウィキ内検索 / 「Influence analysis of information diffusion focusing on directed networks」で検索した結果

検索 :
  • 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が高い 解釈 情報発信能力と情報収集能力が共に高い頂点が多いと情報拡散能力の高いグラフ...
  • 論文一覧
    ... Influence Maximization 関連 バイラルマーケティング Mining the Network Value of Customers Mining Knowledge-Sharing Sites for Viral Marketing 元ネタ Maximizing the Spread of Influence through a Social Network 理論的結果 On the Approximability of Influence in Social Networks 影響最大化／影響力推定の爆速アルゴリズム シミュレーション CELF++ Optimizing the Greedy Algorithm for In...
  • Inferring Networks of Diffusion and Influence
    ...usion 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の尤度を各辺について掛け合わせる ↑をカスケード集合について掛けあわせたら全体の...
  • 気になった論文
    ...08 ✔Influence and correlation in social networks Efficient semi-streaming algorithms for local triangle counting in massive graphs Feedback effects between similarity and social influence in online communities The structure of information pathways in a social communication network Microscopic evolution of social networks Weighted graphs and disconnected components pat...
  • The Role of Social Networks in Information Diffusion
    The Role of Social Networks in Information Diffusion Eytan Bakshy, Itamar Rosenn, Cameron Marlow, Lada Adamic In WWW 2012 メモ Y.Yoshidaさん 新しい情報は「疎遠」な友人から not 親しい友人 仕事とか 思ったよりは多いねというくらい 親しい友人の方が多い なんで？ 強い 情報がすぐ拡散 公募はすぐ埋まる 得る情報 Feed 友人のURLをシェア 外界 メールとか Feedを遮断 |V|=253M Feed有：6...
  • 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...
  • Uncovering the Temporal Dynamics of Diffusion Networks
    ...usion and Influence On the Convexity of Latent Social Network Inference モチベーション whereとwhenはわかるがhowとwhyは分からない いつ誰が記事を投稿 / 病気に感染したかはわかるけど，その経路とか根は分からない 仮定 拡散は（その構造は分からない）静的グラフ上で起こる 状態は活性 or 非活性 辺毎の感染は独立 a- bでの拡散の遅延は何かしたの確率分布に従う ある時間窓での感染がすべてわかる 目的 辺とその尤度を推定する モデル データ 沢山カスケードがある 各カスケードは各頂点が活性化した時刻を持っている 活性化し...
  • 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(ε)...
  • 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) 分布 ...
  • Information Diffusion and External Influence in Networks
    ... 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 ある頂点の拡散過程を沢...
  • Modeling Information Diffusion in Implicit Networks
    ... Linear Influence Model Linear Influence Model 定式化 仮定 uがアクティブになった時刻 これだけ、リンク関係は謎 V(t) 時刻tに情報に言及した頂点の数 I_u(l) 頂点uが言及してから影響を受けてl時間後の言及した頂点の数 A(t) 時刻tまでにアクティブになった頂点の集合 M_u,k(t) 時刻tまでにuがアクティブなったら1 $$ V(t+1) = \sum_{u \in A(t)}I_u(t - t_u) $$ 難しいのは？ I_u(l) のモデリング ノンパラメトリックアプローチだよ～ 長さL $$ V_k(t+1) = \sum_{u=1}^{N}\...
  • Learning Stochastic Models of Information Flow
    ... Learning Influence Probabilities In Social Networks 確率分布は色々な設定で歪ませてある RMSEで比較 まとめ 機械学習よりは難しい… ICDE 情報拡散 情報拡散パラメータ推定 2014-03-31 23 57 24 (Mon)
  • Spectral Analysis of Communication Networks Using Dirichlet Eigenvalues
    Spectral Analysis of Communication Networks Using Dirichlet Eigenvalues Alexander Tsiatas, Iraj Saniee, Onuttom Narayan, Matthew Andrews In WWW 2013 概要 スペクトルグラフ理論 有限グラフでは適切なカット・コミュニティが見つけられない Dirichlet固有値を使うよ！ スペクトルグラフ理論 正規化されたラプラシアン degreeのところをちょっと変える $$ 0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n \leq 2 $$ スペクトルギャップ$$ \lambda_2 $...
  • 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...
  • Prediction of Information Diffusion Probabilities for Independent Cascade Model
    Prediction of Information Diffusion Probabilities for Independent Cascade Model Kazumi Saito, Ryohei Nakano, and Masahiro Kimura KES 2008 概要 ICモデルの辺の伝搬確率を沢山のカスケードから予測したい 頂点uが時刻tにアクティブになった情報 u,t が分かる 尤度を設定して期待値最大化 人工的なネットワークで実験するとそれなりに良い 問題 カスケードが与えられたとして vが時刻t+1でアクティブになる確率は↓ $$ P_v(t+1) = 1 - \prod_{u \in A_t}(1 - p_{uv}) $$ 伝搬確率p_uvを...
  • 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 ...
  • 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で活性な頂点の数...
  • Proposal of AIDM: Agent-based Information Diffusion Model
    Proposal of AIDM Agent-based Information Diffusion Model マルチエージェント型情報拡散モデル(AIDM) の提案 Keisuke IKEDA, Yoshiyuki OKADA, Takeshi SAKAKI, Fujio TORIUMI, Youiti KAZAMA, Itsuki NODA, Kosuke SHINODA, Hirohiko SUWA, Satoshi KURIHARA JSAI 2014 概要 ピークが沢山あるようなモデルを作ったよ モチベーション 東日本大震災でのTwitterの使われ方に注目 デマ（訂正）情報の拡散のピークが1個だけだったり一杯あったりするよ マルチバースト型（一杯の方）を再現したい ...
  • 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モデルでの応用 先...
  • 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...
  • Inferring the Underlying Structure of Information Cascades
    Inferring the Underlying Structure of Information Cascades Bo Zong, Yinghui Wu, Ambuj K. Singh, Xifeng Yan ICDM 2012 概要 ICモデルのカスケードが部分的に与えられる 時刻tにuがアクティブになったみたいな どういう経路を辿ったかの木を知りたい 時刻が厳密に一致する場合とそうでない場合の問題を定式化 難しいけど頑張って解く 実験したらいい感じ 問題定式化 カスケードC 根付き木で時刻がある bounded consistent tree 木上での根sから頂点v_iまでの距離が観測時刻t_i以下 d(s,v_i)≦t_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)) つまり，遅延時間の分布が指数関数 他の関数でも使える 情報拡散過程は普通 ...
  • 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]...
  • 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を...
  • 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は感染しない 手法 σが小さくなるノードを貪欲に選んでいく 実験 比較...
  • On Approximation of Real-World Influence Spread
    ...eal-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の簡易版 行列で表されるので、ガウスザイデルが出来る ...
  • A Note on Maximizing the Spread of Influence in Social Networks
    ...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つ選んで採択するんだからそうか Pr[f_t(v)=1]...
  • 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}...
  • 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 スパム同士は結合...
  • Scalable and Parallelizable Processing of Influence Maximization for ...
    ...essing 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して木っぽくパスを広げる（同じ頂点がいくつかある） しきい値θ未満になった or 閉路にあたったら...
  • 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)につい...
  • 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...
  • 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 ...
  • Word of Mouth: Rumor Dissemination in Social Networks
    Word of Mouth Rumor Dissemination in Social Networks Jan Kostka, Yvonne Anne Oswald, Roger Wattenhofer SIROCCO 2008 概要 Bharathi+WINE 07とかあるけど，先手に注目したらしい？ 先手がどうやっても負けるインスタンスがある Centroid problem 先手 後手が選ぶ頂点数が分かった上で最適なシード集合を選択する Medianoid problem 後手 先手が選んだ頂点数がわかった上で最適なシード集合を選択する CentroidもMedianoidもNP-hard ヒューリスティクスはあまりイカないらしい まとめ ...
  • 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...
  • 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...
  • 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 サイズが大きくなる...
  • 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にな...
  • 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...
  • Social Network Sensors for Early Detection of Contagious Outbreaks
    Social Network Sensors for Early Detection of Contagious Outbreaks Nicholas A. Christakis, James H. Fowler PLoS ONE 2010 概要（だけ） outbreakを検知したい でもネットワーク全体を入手するのがダルい ランダムに選択した頂点の近傍をモニターすると良い ランダムに選択しただけよりも中心性が高くなるから 調査（インフルエンザの拡散）すると，提案手法の方が早くピークを検知できていた PLoS1 outbreak detection 2014-03-15 06 00 12 (Sat)
  • 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...
  • 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する 予備知識みたいな...
  • A General Framework of Hybrid Graph Sampling for Complex Network Analysis
    A General Framework of Hybrid Graph Sampling for Complex Network Analysis Xin Xu, Chul-Ho Lee, Do Young Eun INFOCOM 2014 概要 グラフをサンプリングしたい どっちかっていうとΣf(v)を近似したい ランダムウォークとかランダムジャンプとかある ランダムジャンプはたまに失敗する ↑を統合したのを考えて解析 分散（小さいと良）がランダムジャンプ確率に対して凸 既存手法 ランダムウォーク Simple Random Walk (SRW) with Re-weighting Metropolis-Hastings Random Walk ...
  • 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) ...
  • 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 他の時刻で辺があったらまた試行できる ...
  • The Price of Stability for Undirected Broadcast Network Design with Fair ...
    The Price of Stability for Undirected Broadcast Network Design with Fair Cost Allocation is Constant Vittorio Bilò, Michele Flammini, Luca Moscardelli In FOCS 2013 ブロードキャストゲーム nプレイヤー s1,…sn 1ゴール t 各々はsi- tを目指す プレイヤーiのコスト Σ_e c(e)/(eを使った人数) 例えばケーブルだったら、皆でコストを等分配 各プレイヤーのコストの総和が社会的コスト このゲームにはNash均衡がある cost Nash均衡 / cost 社会的最適 Contri...
  • Minimizing the Spread of Contamination by Blocking Links in a Network
    Minimizing the Spread of Contamination by Blocking Links in a Network Masahiro Kimura, Kazumi Saito, Hiroshi Motoda AAAI 2008 概要 タイトルまんまの論文 汚染最小化問題 目的関数は各頂点のσの平均 既存の研究（Kempe依然）では，出次数の大きい順に頂点を消していけば大体良いとしてた 今回は辺を消す 問題定義 min 1/|V|Σσ(v) Eからk辺取り除ける 提案手法 最も目的関数が小さい辺を選ぶ貪欲アルゴリズム σの計算がやばい この著者らが考えたBond Percolationで高速化 実験 ...
  • 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上のランダムウォークでやる ...
  • @wiki全体から「Influence analysis of information diffusion focusing on directed networks」で調べる

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