todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Maximizing the Long-term Integral Influence in Social Networks Under ...」で検索した結果

• 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[...
• 論文一覧
  ...元ネタ Maximizing the Spread of Influence through a Social Network 理論的結果 On the Approximability of Influence in Social Networks 影響最大化／影響力推定の爆速アルゴリズム シミュレーション CELF++ Optimizing the Greedy Algorithm for Influence Maximization in Social ... WWW 2011 Efficient Influence Maximization in Social Networks KDD 2009 StaticGreedy Solving the Scalability-Accuracy...
• 気になった論文
  ...ethod Maximizing submodular set functions subject to multiple linear constraints Clique-width on the price of generality A simple combinatorial algorithm for submodular function minimization SODA 2010 Rumour Spreading and Graph Conductance conductanceが大きいほどrumour spreading／randomized broadcastのステップ数が小さい Counting Stars and Other Small Subgraphs in Sublinear ...
• ASIM: A Scalable Algorithm for Influence Maximization under the Independent ...
  ASIM A Scalable Algorithm for Influence Maximization under the Independent Cascade Model Sainyam Galhotra, Akhil Arora, Srinivas Virinchi, Shourya Roy WWW 2015 概要だけ 当時最強のTIMはメモリ消費がやばいので、新しいアルゴリズムを作ったよ！ アルゴリズム Simpath An Efficient Algorithm for Influence Maximization under the Linear ...のような事をする vのスコア：vから始まる単純経路の重み付き和、重みは辺確率の積 辺確率行列Pの行列積のようなもの？ 以降の反復...
• 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以下って制約とか...
• 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...
• 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)に従う 平均α/(α+β) 拡散の履歴から各α，βをインクリメントするだ...
• 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モデルでの応用 先...
• 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...
• 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...
• Sampling Community Structure
  Sampling Community Structure Arun S. Maiya, Tanya Y. Berger-Wolf WWW 2010 概要 expander graphのコンセプトによるコミュニティのサンプリング手法 コミュニティ検出で推論っぽいこと？もできるらしい 問題 X(S) = |N(S)|/|S| 隣接頂点数/頂点数 サイズkのサンプルSがcommunity representative sample minimize D[P_S(G(S)), P_S(G)] D[,]は分割に対する距離尺度 P_S(G)はGを使って作られた分割 手法 X(S)の最小化もあるけれどそうではなくて、最大のサンプルを見つ...
• 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...
• 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)でアクティベーションが成功する これは一回だけ ...
• 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内の頂点から出てる単...
• 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 サイズが大きくなる...
• 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)| $$を最小化せよ ...
• 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を始点とす...
• 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 practical bounding algorithm for computing two-terminal reliability based ...
  A practical bounding algorithm for computing two-terminal reliability based on decomposition technique Yi-feng Niu, Fang-Ming Shao Computers and Mathematics with Applications 2011 概要 2端子信頼性計算のアルゴリズム 実験なし （某イベントで知った） 提案手法 C 事象の集合 事象=各辺の状態 A1(C) Cでの状態が生の辺集合 A2(C) Cでの状態が死の辺集合 A1(C)がs-t経路を構成→必ず到達可能 A2(C)がs-tカットを構成→必ず到達不可能 良く分から...
• 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アカウントの状態の指標 をいれる...
• Catching the head, tail, and everything in between: a streaming algorithm ...
  Catching the head, tail, and everything in between a streaming algorithm for the degree distribution Olivia Simpson, C. Seshadhri, Andrew McGregor ICDM 2015 概要 ストリームで次数分布を求めたい 精確には累積分布 普通にやると，tail部分の精度が酷いことに（というか破滅）なる head／tailそれぞれに推定器を用意 Relative Hausdorff距離というナイスな距離を導入 実験では↑で評価→良 アルゴリズム 各辺が任意の順番にワンパスで来る n,mは知らない（というか不定） 辺削除／繰り返...
• Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in ...
  Stop-and-Stare Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks Hung T. Nguyen, My T. Thai, Thang N. Dinh SIGMOD 2016 概要 TIM+やIMMより速い影響最大化アルゴリズムを作りました RR集合のサンプル数が最小だよ！ 枠組み 2つの条件 $$ \Pr[\widehat{\mathsf{Inf}}(S_k) \leq (1+\epsilon_a)\mathsf{Inf}(S_k)] \geq 1-\delta_a $$ $$ \Pr[\widehat{\mathsf{Inf}}(S_k^*) \geq (1+\epsilon_b)...
• Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm ...
  Zig-zag Sort A Simple Deterministic Data-Oblivious Sorting Algorithm Running in O(nlogn) Time Michael T. Goodrich STOC 2014 data-oblivious シェルソート i mod hでグループ分けして挿入ソートしていく hを小さくしていく Zig-zagは？ AKSソートより単純 ε-halver n = 2^k 以下をk回繰り返す splitting step 2個に分割 outer zig outer zag 未解決問題 サイズO(nlogn)の単純なソーティングネットワークを構成する ...
• From Machu_Picchu to rafting the urubamba river: Anticipating information ...
  From Machu_Picchu to "rafting the urubamba river" Anticipating information needs via the Entity-Query Graph Ilaria Bordino, Gianmarco De Francisci Morales, Ingmar Weber, Francesco Bonchi WSDM 2013 概要 今見ているwebページの内容から非自明かつ偶察力を有する少数かつ多様な検索クエリを提示 手法 ページ内容をWikipediaエンティティで表現 エンティティとクエリからなるグラフ上でPersonalized PageRank PageRankスコアの高いクエリを出力 実験 提...
• Improved approximation for 3-dimensional matching via bounded pathwidth ...
  Improved approximation for 3-dimensional matching via bounded pathwidth local search Marek Cygan あのMarek Cygan In FOCS 2013 k-Set packing kの最大マッチングのようなもの 既存の 貪欲とか局所探索とか あるkつ組を捨てれば、2つのkつ組をとれる、みたいな局所探索 2じゃなくてr以下とする これ、FPTなんですか？？？ 結果 FPT=W[1]でない限りf(r)poly(|F|)-timeは無い 交換の範囲を多項式個に制限 ↑の判定をpath-widthで抑える しかし近似比は変わらん！ ...
• Approximation Algorithms for Regret-Bounded Vehicle Routing and Applications ...
  Approximation Algorithms for Regret-Bounded Vehicle Routing and Applications to Distance-Constrained Vehicle Routing Zachary Friggstad, Chaitanya Swamy STOC 2014 概要 Approximation Algorithms for Regret-Bounded Vehicle Routingについて 30.86近似アルゴリズム 今までO(log n)近似 RVRP 入力 完全グラフ 距離 三角不等式 始点r 整数R rを始点とするパスの集合で次を満たす 全頂点が少なくとも1つに被...
• Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for ...
  Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems Yin Tat Lee, Aaron Sidford In FOCS 2013 リプシッツ連続、強凸関数の最小化 加速座標勾配法 逆条件数κ^-1が0に近いとヤバイ 収束しにくい 加速勾配法・座標勾配法のマージ 今まではupdateがO(n)で遅い これをO(1)にしたヨ！！！ 遅延評価っぽいことをする FOCS 2013-11-03 02 19 09 (Sun)
• Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and ...
  Towards Scaling Fully Personalized PageRank Algorithms, Lower Bounds, and Experiments Dániel Fogaras, Balázs Rácz, Károly Csalogány, Tamás Sarlós Internet Mathematics 2005 概要 fully personalizationが良いです ランダムウォーク手法を考案 分解定理を使って少し精度改善 実験もしました 関連研究 Topic-sensitive PageRank [Haveliwala 02] tトピックの線形結合のみ、O(tV)空間 Hub Decomposition [Jeh-Widom 03...
• Tracking the Random Surfer: Empirically Measured Teleportation Parameters in ...
  Tracking the Random Surfer Empirically Measured Teleportation Parameters in PageRank David F. Gleich, Paul G. Constantine, Abraham D. Flaxman, Asela Gunawardana WWW 2010 概要 PageRankのαの値は何なんだ？ 平均が0.3~0.7のβ分布に従う 分布の測定 人一人なら簡単 (リンククリックによる総閲覧ページ数) / (総閲覧ページ数) 複数人いると，平均とかいうわけにも行かない PageRankはαに対して非線形だから 代わりに，人毎にαを求め，グループ全体にフィットする分布を求める ↓の2...
• An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting ...
  An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree Jochen Koenemann, Sina Sadeghian, Laura Sanità In FOCS 2013 ノード重みはキテるんですよ！！ Prize collecting node-weighted steiner tree w V→R+ p V→R+ min w(V(T)) + P(V-V(T)) s.t. Tはtree 左はスパンしている、右はしていない LMP Lagrangian multiplier preserving w(V(T))+αp(V-V(T))≦αw(V(...
• 4chan and /b/: An Analysis of Anonymity and Ephemerality in a Large Online ...
  4chan and /b/ An Analysis of Anonymity and Ephemerality in a Large Online Community Michael S. Bernstein, Andrés Monroy-hernández, Drew Harry, Paul André, Katrina Panovich, Greg Vargas ICWSM 2011 概要 anonymity（匿名性）とephemerality（短命であること）の面から4chanを理解する 4chanと/b/ /b/はランダム掲示板 4chan全体の30%のトラフィック リプライしたりすると最初のページに浮上 15ページ目の最下層に行くと消されて`Page Not Found ...
• TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in ...
  TF-Label a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph James Cheng, Silu Huang, Huanhuan Wu, Ada Fu In SIGMOD 2013 概要 reachability の高速化 Topological foldingとラベリング Topological folding なにそれ DAGをトポロジカル順にlevel付 G1, G2, …と行くに従い、偶数レベルの頂点だけを残す 到達可能なエッジ間にはエッジを張っておく エッジが変になっているとめんどい cross-level エッジ ま...
• OSNAP: Faster numerical linear algebra algorithms via sparser subspace ...
  OSNAP Faster numerical linear algebra algorithms via sparser subspace embeddings Jelani Nelson, Huy L. Nguyen In FOCS 2013 線形空間の次元削減の話 問題 (1-eps)||x||≦||Πx||≦(1+eps)||x|| Π R^n→R^m Πはm×n行列上の確率分布Dに従う 設計したいのはD 応用 min ||Ax-b|| min ||ΠAx-Πb||にする m dなら解きやすい だけど、Πが疎じゃないと意味ない（行列演算が重くなる 結果 (i)既存の評価をimprove 非ゼロは各列1つだけ Π_...
• @wiki全体から「Maximizing the Long-term Integral Influence in Social Networks Under ...」で調べる

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