todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Dynamic PageRank using Evolving Teleportation」で検索した結果

• Dynamic PageRank using Evolving Teleportation
  Dynamic PageRank Using Evolving Teleportation Ryan A. Rossi and David F. Gleich WAW 2012 概要 嗜好ベクトルが変化する下でPageRankの微分方程式を考える Euler法が実は、べき乗法=Richardson法と似た手法 嗜好ベクトルが固定なら、普通のPageRankに収束する 色々便利; 予測 動的テレポーテーションなPageRank Δx^(k) = x^(k+1)-x^(k) = (1-α)v-(I-αP)x^(k)のアナロジーで、 x (t) = (1-α)v(t)-(I-αP)x(t)という微分方程式を考える 普通の微分方程式なので、x(t)は解ける 特にv(t)=tの時は...
• 論文一覧
  ...Influence Dynamics in Billion-scale Networks ICDM 2017 ヒューリスティクス Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale ... KDD 2010 Scalable Influence Maximization in Social Networks under the Linear ... ICDM 2010 IRIE Scalable and Robust Influence Maximization in Social Networks ICDM 2012 Simulated Annealing Based Influence Maximization in Socia...
• 気になった論文
  ... Power of Dynamic Distance Oracles Efficient Dynamic Algorithms for the Steiner Tree. Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams. STOC 2016 Simpler Analysis and Enumeration of Parametric Minimum Cuts David Karger Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem Breaking the Logarithm...
• 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...
• PageRank on an Evolving Graph
  PageRank on an Evolving Graph Bahman Bahmani, Ravi Kumar, Mohammad Mahdian, Eli Upfal In KDD 2012 概要 PageRankの入力データが固定なんて意味ないだろいい加減にしろ！！ ちょこちょこグラフが変化するモデルを考えたよ でも、実際にはあまりprobeできないので、1頂点だけout-edgeを調べる問題を考えたよ 頂点を選ぶ簡単なアルゴリズムを作ったけど、理論的保証があるし、実験的にも上手くいったよ モデル G^t 時刻tでのモデル G^{t+1}とG^tの違いは（極端には）多くないとする 高々1頂点だけprobeできる どの段階でもある程度精度の良いPageRankベクトル...
• Importance Sketching of Influence Dynamics in Billion-scale Networks
  ...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 Sampling ($$\mathsf{...
• 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 サイズが大きくなる...
• Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and ...
  ... Basic Dynamic Programming [Jeh-Widom 03] 任意、O(V(k-近傍))空間 提案手法 任意、O(NV)空間（Nは標本数） 各頂点からNランダムウォーク標本し、終了頂点を記録 普通のクエリは、ただの頂点数 分解定理 $$ \mathbf{\pi}_u = (1-\alpha)\mathbf{1} + \alpha |\mathcal{N}^+(u)|^{-1}\sum_{u \in \mathcal{N}^+(u)} \mathbf{\pi}_v $$ ∑で得をする; 「個々がε誤差」では無くて、「$$|\mathcal{N}^+(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...
• 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は分からない いつ誰が記事を投稿 / 病...
• Visual Analysis of Dynamic Networks using Change Centrality
  Visual Analysis of Dynamic Networks using Change Centrality Paolo Federico, Jürgen Pfeffer, Wolfgang Aigner, Silvia Miksch, Lukas Zenk ASONAM 2012 動的グラフに対する新しい中心性 $$ \frac{|N_{t_1}(i) \triangle N_{t_2}(i) |}{|N_{t_1}(i) \cup N_{t_2}(i)|} $$ N_t(i) 時刻tでのiからの距離が丁度1の頂点集合 分子は時刻t1からt2にかけて，追加/削除した辺の数 分母は時刻t1からt2にかけて，追加/削除/生存した辺の数 距離が1でなくてnの場合の一般ケース $$ r_{t_1,t_...
• Maximizing the Long-term Integral Influence in Social Networks Under the ...
  ...Diffusion Dynamics and Influence Maximization in Social Networks ... long-term integral influence maximization σ(S) = E[Σ_{t≧0}|S_t|] これって発散しないの？怪しい… このΣは行列の無限べき乗和で書ける（またかよ なので，(I-W)^-1を計算すればOK σは線形なので，貪欲にとれば厳密解 実験 グラフのサイズが無いのでガチギレ PageRankの10倍遅いくらい 実行時間のグラフが3Dでガチギレ WWW 影響最大化 2014-05-22 23 23 36 (Thu)
• 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(ε)...
• Streaming Graph Partitioning for Large Distributed Graphs
  Streaming Graph Partitioning for Large Distributed Graphs Isabelle Stanton, Gabriel Kliot In KDD 2012 メモ セミナー K.Inabaさん 問題 巨大グラフを複数に分割したい ストリーミングアルゴリズムじゃないと意味ないお 入力 G(V,E) k マシン台数 ε アンバランス度 出力 V1, V2, …, Vk $$ |Vi| \leq \frac{(1+\epsilon)|V|}{k} $$ または $$ \sum \deg(V_i) \leq (1+\epsilon)\sum \deg(v)/k $$ を満たすよ...
• Link Evolution: Analysis and Algorithms
  Link Evolution Analysis and Algorithms Steve Chien, Cynthia Dwork, Ravi Kumar, Daniel R. Simon, D. Sivakumar Internet Mathematics 2010 概要 PageRankの動的更新手法 アイデアは追加・削除された辺の近傍のみを真面目に再計算する 提案手法 aggregation/disaggregation method 観察 辺ijが追加されたら，iとjの近傍についてのみPageRankスコアが変化する S(t)←時刻tで追加・削除された辺の近傍集合 G ←V\S(t)を1つの頂点に縮約したグラフ 辺の遷移確率は注意深く設定する G のP...
• Preserving Personalized Pagerank in Subgraphs
  Preserving Personalized Pagerank in Subgraphs Andrea Vattani, Deepayan Chakrabarti, Maxim Gurevich ICML 2011 概要 既存のグラフサンプリングは、Sを計算して、G[S]を出力 局所的な指標は良いけど、大域的な指標は駄目 S={u,v}だと、N(u)∩N(u)が大きくても、微妙になる 辺を弄ってPPRを保持する問題 SINKを足すと上手く行く 密になるので疎化 問題定式化と提案手法 入力 $$ G=(V,w_G), S \subseteq V $$ 出力 $$ H=(S,w_H) $$ 目標 $$ \pi_i^H(j) = \pi_i^H(...
• Finding Spread Blockers in Dynamic Networks
  Finding Spread Blockers in Dynamic Networks Habiba, Yintao Yu, Tanya Y. Berger-Wolf, Jared Saia SNA-KDD 2008 概要 情報拡散を止めたい 計算コストが高い手法はやだ 適当なヒューリスティクスを動的グラフで実験してみるよ 指標 次数，密度，直径，平均次数，betweenness，closeness，クラスタ係数 こういうので高い頂点を取り除いてみてinfluence spreadはどうなるか？ 実験 次数とかでも良いね SNA-KDD contamination minimization 2014-02-20 00 32 08 (Thu)
• FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs
  FAST-PPR Scaling Personalized PageRank Estimation for Large Graphs Peter Lofgren, Siddhartha Banerjee, Ashish Goel, C. Seshadhri KDD 2014 概要 $$ \pi_s(t) \delta $$を$$ \mathcal{O}(\sqrt{d/\delta}) $$時間で近似計算 相対誤差が小さい 既存は$$ \Omega(1/\delta) $$時間で、$$ \delta=\Theta(1/n) $$にしたいので遅い□ 計算時間の下限$$ \Omega(1/\sqrt{\delta}) $$を示した 実験的には数十倍速い 提案手法 設定 ...
• 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 ...
• 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スコアの高いクエリを出力 実験 提...
• IMRank: Influence Maximization via Finding Self-Consistent Ranking
  IMRank Influence Maximization via Finding Self-Consistent Ranking Suqi Cheng, Huawei Shen, Junming Huang, Wei Chen, Xueqi Cheng SIGIR 2014 概要 貪欲アルゴリズムで選ぶと，ゲインは単調非増加 逆にゲインが単調なランキング（順列）は割りと良さそう？ 適当なランキングから初めて，並び替えを反復 ゲインの計算はヒューリスティック 提案手法 自己整合(self-consistent)な順列 以下を満たすランキング $$ r [n] \to V $$ $$ i j \Rightarrow M(i) \geq M(j) $$ $$ M(...
• 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...
• Temporal PageRank
  Temporal PageRank Polina Rozenshtein, Aristides Gionis ECML-PKDD 2016 概要だけ dynamicなPageRankは、単にstaticなグラフが沢山あるだけ 今回はtemporal pathを考慮したPageRank tempora path u1,v1,t1 , …, uL,vL,tL where t1 =… =tL が成立するもの 出現順に辿れるという意味です temporal pathの意味でのRandom walkっぽいもの（適当な重み付け）を考えて、temporal PageRankを定義する 計算手法も与える 感想 それなりに解析をしている 計算した結果面白いか？というと何ともいえない ...
• Delineating Social Network Data Anonymization via Random Edge Perturbation
  Delineating Social Network Data Anonymization via Random Edge Perturbation Mingqiang Xue, Panagiotis Karras, Chedy Raissi, Panos Kalnis, Hung Keng Pung CIKM 2012 概要 random edge perturbation によるグラフの匿名化 上を攻撃する手法 グラフの特徴量を推定 Random Edge Perturbation 辺を確率μで独立に足したり消したりする XORってこと denseになるけどいいや 色々推定 ※μは公開するとして良い 密度 μが分かるので、て...
• 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...
• Maximizing the Extent of Spread in a Dynamic Network
  ...read 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 他の時刻で辺があったらまた試行できる σ(A) 最終時刻でactiveな頂点数 ...
• 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で囚人のジレン...
• StaticGreedy: Solving the Scalability-Accuracy Dilemma in Influence Maximization
  StaticGreedy Solving the Scalability-Accuracy Dilemma in Influence Maximization Suqi Cheng, Huawei Shen, Junming Huang, Guoqing Zhang, Xueqi Cheng In CIKM 2013 ArXiv 2012 概要 実は今までのMonte-Carloは間違っていた！ 毎回ランダムグラフを作っているのが問題 そのせいで莫大な試行回数が要求される 俺が最強のMonte-Carloアルゴリズムを提案するぜ！ ランダムグラフを使いまわす Rは1/100に減った StaticGreedy R回ループ 各辺を割り当てられた確率に応じて消す...
• Dynamic Influence Maximization Under Increasing Returns to Scale
  Dynamic Influence Maximization Under Increasing Returns to Scale Haifeng Zhang, Ariel D. Procaccia, Yevgeniy Vorobeychik AAMAS 2015 概要 時間が動的な設定 予算投入を途中で行う 活性化頂点 時間に従い適当に増える，指数とか多項式とか 予算 時間に従い指数的に増える 適当な設定では，ある時点に一斉投入（使い切る）のが最適 そうでない場合はヒューリスティクス 導入 ICモデルは劣モジュラ 最近は適応的劣モジュラ最大化もある しかし，Bassモデルのような古典的なモデルはS-shaped Curve ここはミスリーディングで，劣...
• Dynamic Density Based Clustering
  Dynamic Density Based Clustering Junhao Gan, Yufei Tao SIGMOD 2017 概要だけ 動的なクラスタリングは毎回結果を返すから微妙 要求クエリ 追加・削除クエリ、O(1)時間 Group-byクエリ、O(|Q|)時間 Qだけの結果（グルーピング）を返す 厳密／近似DBSCANで考えます d=2, 厳密 要求を達成 d=3, 厳密 追加だけでも不可能 可能だとバッチの性能を超える ρ approx 追加だけは達成 完全動的は不可能 ρ double approx（緩和版） 遂に達成 実験もしました SIGM...
• Dynamic and Static Influence Models on Starbucks Networks
  Dynamic and Static Influence Models on Starbucks Networks Minkyoung Kim, Byoung-Tak Zhang ASONAM 2009 概要 韓国のStarbucksを調べたい！ モデル立てた！楽しい！！！ ASONAM 2014-09-21 01 58 51 (Sun)
• Accelerating Graph Adjacency Matrix Multiplications with Adjacency Forest
  Accelerating Graph Adjacency Matrix Multiplications with Adjacency Forest Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato, Masaaki Nagata SDM 2014 概要 AXみたいな行列計算を高速にしたい Aの列中の値が同じ（確率遷移行列とか）だと余分な計算を省ける さらにAを分解して個々に省略手法を適用できる 3倍位速くなった 提案手法 Single Tree Adjacency Forest(STAF) Column-scaled nonzeros property 行列の各列j中の値＝0 or cj こんなやつ $$ A = \left( ...
• 2.5K-Graphs: from Sampling to Generation
  2.5K-Graphs from Sampling to Generation Minas Gjoka, Maciej Kurant, Athina Markopoulou INFOCOM 2013 概要 2.5K-graph 次数kの頂点と次数lの頂点を結ぶ辺の個数の分布と、次数kの頂点のクラスタ係数の平均値を分布に着目 ソーシャルネットワークから↑を高速に見積もり、そういう分布になるグラフも生成する ↑以外の分布も結構一致する！ 問題 JDD(k,l) = 次数kの頂点と次数lの頂点を結ぶ辺の数 JDD = Joint Degree Distribution 2頂点の部分グラフの次数依存の分布 ‾c(k) = 次数kの頂点のクラスタ係数の平均値 dk...
• 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頂点を更新した時に、そのグラフで計算した解と真の解ができるだけ近くなるようにしたい ...
• The Effect of the Back Button in a Random Walk: Application for PageRank
  The Effect of the Back Button in a Random Walk Application for PageRank Fabien Mathieu, Mohamed Bouklit WWW 2004 概要 バックボタンを入れたPageRankを考える 計算も早そう Back Button Model Reversible Back バックボタンの効果 1つ前の「状態」に戻る 2回バックすると，今いるページに戻る 記憶領域は前の状態一つだけ どれかの辺をたどる確率とバックボタンの確率は同じ t+1ステップ目でwからvに遷移する確率 Pr[今wにいてwvを辿る]+Pr[vからwに移動した状態でバック] (wv∈E) Pr...
• Approximate Bayesian Image Interpretation using Generative Probabilistic ...
  Approximate Bayesian Image Interpretation using. Generative Probabilistic Graphics Programs 画像認識の新手法 応用 CAPTHA…これは文字ほげだ！ 道路認識 画像のシーンをシンボリックに 大きなコーパスが必要 トップダウンに考えるよ！ ボトムアップ 画像を要素に分解 それぞれを解釈 トップダウン 要素を仮定し画像を構成 その確率を出す モデル シーン…文字の種類とか 入力からこれを推定する レンダラを使った生成モデルで予測 Metropolis-Hastings 変数をちょっと動かしてほげ...
• On Influential Node Discovery in Dynamic Social Networks
  ...covery 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とする 伝播確率は1-Π_m(1-f...
• Memory Efficient Minimum Substring Partitioning
  Memory Efficient Minimum Substring Partitioning Yang Li, Pegah Kamousi, Fangqiu Han, Shengqi Yang, Xifeng Yan, Subhash Suri In VLDB 2013 アブスト 並列DNAシーケンス技術が進歩している Illumina, SOLiD Human Whole Genome Sequencingの値段 $3,750 数G個の断片をとってきて遺伝子全体の再構築 short read A,C,G,Tからなる短いシーケンス 既存手法 ランダムサンプリングして、重複があるreadを拾ってくる readの長さ 数十 ~ 数百 ...
• 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...
• 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 これって問題って言うのか？？？ ...
• Real-Time Influence Maximization on Dynamic Social Streams
  ...zation 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 u, a_{t } \rangle $$ ...
• On Influential Nodes Tracking in Dynamic Social Networks
  ...acking in Dynamic Social Networks Xiaodong Chen, Guojie Song, Xinran He, Kunqing Xie SDM 2015 概要 動的グラフでの影響最大化 今のシードを交換ヒューリスティック 影響力の評価は上限ベースの手法も使って枝刈り 提案手法 [Nemhauser-Wolsey-Fisher. 78]の交換ヒューリスティック 局所改善で1/2近似 あまりシード集合が変わらないはずだからという観察 $$ S = S-v_s+v^* $$ $$ v^* \in V \setminus S $$ 一番上昇する奴 $$ v_s $$ 上限使って一番良さそうなの ...
• Rounded Dynamic Programming for Tree-Structured Stochastic Network Design
  Rounded Dynamic Programming for Tree-Structured Stochastic Network Design Xiaojian Wu, Daniel Sheldon, Shlomo Zilberstein AAAI 2014 Xiaojian WuにはAAAIでお会いした このグループはあくまでStochastic Network Designとして捉えているっぽい（影響最大化も） 概要 有向木上の確率的ネットワーク設計に対する丸め動的計画法 河のネットワークでの状況を想定できるらしい FPTASでO(n^2/ε^2)だけど実験的にはもう少し速い（し精度も良い） 動機付けとか リバーネットワーク(?)の階層的構造を木構造で表現 その応...
• Extrapolation Methods for Accelerating PageRank Computations
  Extrapolation Methods for Accelerating PageRank Computations Sepandar D. Kamvar, Taher H. Haveliwala, Christopher D. Manning, Gene H. Golub WWW 2003 概要 PageRankのためのPower methodの高速化 25--300%速くなった メモ：イントロで… Dangling nodesからは一様に飛ぶとしている Aitken Extrapolation $$ x^{(k-2)} $$が上位2つの固有ベクトルの線形結合で表せるとする $$ x^{(k-2)}, x^{(k-1)}, x^{(k)} $$を使って$u_1$を求めたい！...
• Is Nearly-linear the Same in Theory and Practice? A Case Study with a ...
  Is Nearly-linear the Same in Theory and Practice? A Case Study with a Combinatorial Laplacian Solver Daniel Hoske, Dimitar Lukarski, Henning Meyerhenke, Michael Wegner SEA 2015 概要 A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Timeを実装してみました！ ほぼ線形時間の計算量だけど、定数が大きすぎて、全然遅いよ！残念！ low stretch保証のある手法よりも、単純な全域木のほうが良かったりしたよ！ 準備 基本的なソルバの...
• 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 関...
• 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...
• Clustering Large Probabilistic Graphs
  Clustering Large Probabilistic Graphs George Kollios, Michalis Potamias, Evimaria Terzi TKDE 2013 概要 Uncertain graphのクラスタリング 編集距離ベースの目的関数 Correlation Clusteringと同じになる その他自明な拡張 問題定義＋提案手法 pClusterEdit クラスタグラフ （Gと同じ頂点集合を持つ、）互いに素なクリークの和集合 期待編集距離 「Gからサンプルした部分グラフ」と「クラスタグラフ」の（辺の意味での）編集距離の期待値 辺毎に考えれば良く、クラスタグラフに辺が無い→p(e)／有る→1-p(e) これはCo...
• Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in ...
  ...する Dynamic Stop-and-Stare Algorithm (D-SSA) $$(\epsilon_a, \epsilon_b, \delta_a, \delta_b)$$の選択が異常に複雑化 会議版、ArXivで色々と違う どちらも、定数倍だけthresholdより悪い（らしい） 実験 辺確率／重み：1/入次数「だけ」 比較手法：D-SSA, SSA, IMM, TIM+, TIM, CELF++ まとめ はい。 SIGMOD 影響最大化 2017/10/02
• 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全体から「Dynamic PageRank using Evolving Teleportation」で調べる

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