todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Propagation of Trust and Distrust」で検索した結果

• Propagation of Trust and Distrust
  Propagation of Trust and Distrust R. Guha, Ravi Kumar, Prabhakar Raghavan, Andrew Tomkins WWW 2004 概要 知りたい=「ある人がある人を信頼しているか？」 本当はdistrust=不信も考慮すべき 信頼・不信を合わせた伝播に基づく予測手法を作ったよ Epinionsのデータで確かめたよ 提案手法 信頼T、不信D、信念B=T or T-D 原始的な伝播 i→jかつj→kならi→k、i→jかつk→lかつk→jならi→l、みたいなのを4つ作る（全部BとB転置で表せる） $$ C_{B,\alpha} = \alpha_1 B + \alpha_2 B^\top B + \al...
• 論文一覧
  ...Influence Propagation on Networks CIKM 2013 Community-based Greedy Algorithm for Mining Top-K Influential Nodes in ... KDD 2010 Efficient algorithms for influence maximization in social networks KAIS 2012 CINEMA Conformity-Aware Greedy Algorithm for Influence Maximization in ... EDBT 2013 A Novel and Model Independent Approach for Efficient Influence Maximization ... WISE 2013 ...
• Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms
  Truss Decomposition of Probabilistic Graphs Semantics and Algorithms Xin Huang, Wei Lu, Laks V.S. Lakshmanan SIGMOD 2016 概要 Core decomposition of uncertain graphsのk-trussへの拡張 局所的：部分グラフの各辺がk-2△に含まれる確率≧γ k-coreっぽく辺を取り除いていく 当該確率はDPで計算 大域的：部分グラフ全体がk-trussを含む≧γ 確率の厳密計算が#P-hard ランダムサンプリングして探索 実験しました 問題定式化 局所$$(k, \gamma)$$-...
• 気になった論文
  ... Affinity Propagation Yasuhiro Fujiwara、Affinity Propagationを爆速化 MASCOT Memory-efficient and Accurate Sampling for Counting Local Triangles in Graph Streams U Kang Network Lasso Clustering and Optimization in Large-Scale Graphs Jure Leskovec、一般的な凸計画よりは少し特殊なクラスタリングや最適化に使えるネットワーク上の問題 Set Cover at Web Scale TimeCrunch Interpretable Dynamic Graph Summariza...
• 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...
• Estimating Clustering Coefficients and Size of Social Networks via Random Walk
  Estimating Clustering Coefficients and Size of Social Networks via Random Walk Stephen J. Hardiman, Liran Katzir In WWW 2013 メモ Liran KatzirはMSR Israel 概要 ランダムウォークでクラスタ係数と頂点数を見積もる 全体をとってくるのが厳しい用 ちょっとタイムリー 既存手法よりかなり良い 近似が指数関数的によくなる（ランダムウォークの長さの 頂点のIDと、隣接リスト（次数）さえわかれば良い しかも前と後の1つずつだけ覚えていれば計算可能 問題 global clustering coefficien...
• 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)に従う 平均α/(α+β) 拡散の履歴から各α，βをインクリメントするだ...
• Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs
  Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs Liam Roditty, Virginia Vassilevska Williams In STOC 2013 メモ Y.Yano 直径2近似O(n+m) BFSして最大の高さ additive approximation Aingworth 2つの組み合わせ 2種類のBFS木の高さの最大値 $$ s \in [1,n] $$ O(ns^2 + (s+n/s)m) 論文の内容 ns^2の項を消したい ↑高々s頂点のBFS N_s^out(v)を求めないで頑...
• 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 ...
• k-means--: A unified approach to clustering and outlier detection
  k-means-- A unified approach to clustering and outlier detection Sanjay Chawla, Aristides Gionis SDM 2013 概要 l点除いてかつk-meansも最小 除いたLが外れ値 問題定義 D(X\L, C)を最小化するC (of size k) とL (of size l) を求めたい Dは最小二乗距離和 k=1ならn^d^3で解けるけど基本NP-hard 提案手法 k-meansの変形に相当 各点についてクラスタまでの距離計算 距離でソートして大きいl点をLにつっこむ Lを無視してクラスタ更新 これを収束するま...
• Analyzing Spammer's Social Networks for Fun and Profit
  ...nce Score Propagation 3ヒューリスティクスにもとづいてアカウントにスコアを割り当てる 悪垢をフォローしているとスコア増（？ 悪垢から遠いとスコア減 悪垢に近いほどスコア増 良さげな定式化をする サポーターの特徴 3つある social butterflies, social promoters, dummies Social Butterflies フォローもフォロワーも多い 2,000フォローをしきい値 4,000くらいいた 蝶は何も考えずにフォローバックを返すから悪垢もフォローしちゃう 検証もした Social Promoters フォローがフォロワーに比べてめちゃ多い ビジネス ...
• Nonnegative Spectral Clustering with Discriminative Regularization
  Nonnegative Spectral Clustering with Discriminative Regularization Yi Yang, Heng Tao Shen, Feiping Nie, Rongrong Ji, Xiaofang Zhou AAAI 2011 概要（だけ） よくあるクラスタリング手法 どの要素がどのクラスタに属するかを表すindicator matrixで目的関数を表現 そのままだと解けないので{0,1}から緩和する 固有値分解をココらへんで使う 頑張って解く ±混ざっている {0,1}にする 何が問題？ 混合符号の行列がもらえた時にそれを量子化する簡単な方法が無い EM-like / k-means / spe...
• 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を...
• 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...
• Probabilistic Solutions of Influence Propagation on Networks
  ...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になるには… 1→2 wp P_12 ...
• 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 Maximization with Viral Product Design
  Influence Maximization with Viral Product Design Nicola Barbieri, Francesco Bonchi SDM 2014 概要 製品設計も考えた情報拡散LTモデル 同じアイテムでも特徴が違うとσが変わる 頂点+特徴の選択が必要 提案モデルF-TMの学習手法 最適化アルゴリズムを頑張る share-of-choice (SoC)問題 u_{f,l}^i 人i，特徴f，レベルlについてその効果 負もありうる 各人iについて Σ_fΣ_l x_{f,l} u_{f,l}^i ≧ h_i ならiはこの製品を採用する x_{f,l}は0-1変数，これを決定するのが問題 fe...
• Adaptation and Optimization of Biological Transport Networks
  Adaptation and Optimization of Biological Transport Networks Dan Hu, David Cai PRL 2013 流れのあるネットワーク フローとか 物理とCSのコネクション biological networksの観点 葉脈！！ 葉っぱに穴を開けたら葉脈はどーなるの？？？？？？？？？？？？？？？？？？？？？？？？ 葉っぱ氏は省エネを保ちつつ色々頑張っている ループが出たり出なかったり この論文 シンクが開閉するよ！！ インフラと関係あるかなー Kirchhoff s law 圧力とか出てくる 実際には圧力差しかいらない？ アダプテーション ...
• 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...
• An Application of Boosting to Graph Classification
  An Application of Boosting to Graph Classification Taku Kudo, Eisaku Maeda, Yuji Matsumoto NIPS 2004 概要 グラフ分類にBoostingを応用する（最初期の論文？） 提案手法 概要 ラベル付きグラフがL個あります 決定株$$ h_{\langle t,y \rangle}(\mathbf{x}) $$ xについてある部分グラフyを含んでいたらyを返す ものすごく弱いので、Boosting(特にAdaBoost)を適用 決定株をK個用意する $$ \mathrm{gain}(\langle t,y \rangle) = \sum_{1 \leq i \leq L} ...
• 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に適用 完全なひと月のデータ 情報がネットワークをジャンプしている ...
• 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)だけど実験的にはもう少し速い（し精度も良い） 動機付けとか リバーネットワーク(?)の階層的構造を木構造で表現 その応...
• 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...
• 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上のランダムウォークでやる ...
• 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を...
• The Role of Network Distance in LinkedIn People Search
  The Role of Network Distance in LinkedIn People Search Shih-Wen Huang, Daniel Tunkelang, Karrie Karahalios 2人目はLinkedIn SIGIR 2014 概要 LinkedInのクエリを色々調べてみた クエリの種類（タグ）でクリックの挙動がかなり変わる 名前じゃないクエリは自分から2次の人が選ばれやすい 1次はもういらないが，距離1の人のコネを使うと新しいコネができやすい ログ解析 Non-name Job Title, Skill, Company Name Name Last Name, First Name, First Nam...
• Estimating Sizes of Social Networks via Biased Sampling
  Estimating Sizes of Social Networks via Biased Sampling Liran Katzir, Edo Liberty, Oren Somekh Yahoo! Labs, Israel WWW 2011 概要 ネットワークのサイズ=頂点数を見積もりたい どういうシチュエーション？ FacebookとかTwitterとか…隣接リストは辿れるけどexplicitに|V|が得られない ランダムウォークベースのアルゴリズム 一様サンプリングでなくて次数でバイアスがかかっているのがポイント 一様よりも高性能であることを実験で示した サンプリング 誕生日パラドックスに基づいた手法 rノードを一様サンプリングす...
• On the Streaming Complexity of Computing Local Clustering Coefficients
  On the Streaming Complexity of Computing Local Clustering Coefficients Konstantin Kutzkov, Rasmus Pagh WSDM 2013 概要 ワンパスでlocal clustering coefficientを求めたい ローカルなので、頂点ごと 辺リストが任意の順でもらえる 全く三角形が無い or 1/2以上のCCを持つ次数2d以上の頂点がある、かをある程度の確率でワンパスで判定するためにはΩ(m/d)ビット必要 ↑の限界にマッチした乱択アルゴリズムを考案 Lower bound Theorem 1 ワンパス乱択アルゴリズムが 次数2dの頂点はクラスタ係数0 ...
• Quick Detection of High-degree Entities in Large Directed Networks
  Quick Detection of High-degree Entities in Large Directed Networks Konstantin Avrachenkov, Nelly Litvak, Liudmila Ostroumova Prokhorenkova, Eugenia Suyargulova ICDM 2014 概要 準線形時間で高次数の頂点を同定したい！ 問題 |V|より遥かに小さいAPI呼び出しで人気ユーザを知る 人気…高次数 API ユーザを一様ランダムに選ぶ ユーザ1人の入次数 ユーザ1人の出辺 ホントは1回当たり5000本 提案手法 S ← n1頂点をランダムに選ぶ Sの出辺を...
• 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モデルでの応用 先...
• Inferring Networks of Diffusion and Influence
  Inferring Networks of Diffusion 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の尤度を各辺について掛け合わせる ...
• Modeling Information Diffusion in Implicit Networks
  Modeling Information Diffusion in Implicit Networks Jaewon Yang, Jure Leskovec ICDM 2010 概要 基本的にunderlyingなグラフは分からん グラフ構造っぽいのを使わずにモデリング Linear Influence Model Linear Influence Model 定式化 仮定 uがアクティブになった時刻 これだけ、リンク関係は謎 V(t) 時刻tに情報に言及した頂点の数 I_u(l) 頂点uが言及してから影響を受けてl時間後の言及した頂点の数 A(t) 時刻tまでにアクティブになった頂点の集合 M_u,k(t) 時刻tまでにuがアクテ...
• 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...
• On k-Path Covers and their Applications
  On k-Path Covers and their Applications Stefan Funke, André Nusser, Sabine Storandt VLDB 2014 best paper award スライド見てね 概要 Minimum k-All Path Cover (k-APC) 入力 有向グラフ G=(V,E) 整数k 出力 C⊆V であって，任意の長さkの単純経路πについて，C∩π≠∅ minimize |C| Minimum k-Shortest-Path Cover (k-SPC) [Tao, Sheng, Pei. SIGMOD 11] 入力 有向グラフ G=(V,E,c) ...
• 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 ある頂点の拡散過程を沢...
• 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]...
• Stochastic Submodular Maximization: The Case of Coverage Functions
  Stochastic Submodular Maximization The Case of Coverage Functions Mohammad Reza Karimi, Mario Lucic, Hamed Hassani, Andreas Krause NIPS 2017 概要 確率的劣モジュラ最大化のための新しい手法を提案 まずは、被覆関数から 連続拡張をさらに緩和した問題を直接解いてから元に戻す 問題 目的関数 $$ f(S) = \mathbb{E}_{\gamma \sim \Gamma}[f_\gamma(S)] $$ 影響最大化なら、影響グラフからサンプルしたグラフ上で到達可能な頂点数 線形連続拡張 $$ F(\bm{x}) = \mathbb{E}...
• 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...
• Approximating the Spectrum of a Graph
  Approximating the Spectrum of a Graph David Cohen-Steiner, Weihao Kong, Christian Sohler, Gregory Valiant KDD 2018 概要 （正規化）Laplacianのスペクトラムが欲しい！ $$ \exp(O(1/\epsilon)) $$時間：定数！！！ $$ \| \tilde{\mathbf{\lambda}} - \mathbf{\lambda} \|_1 \leq \epsilon|V| $$ 性質検査的な話もあるよ！ 提案手法 定数時間にしたいので、出力は[0,2]上の離散分布 $$ \epsilon|V|, 2\epsilon|V|, 3\epsilon|V| $$番...
• 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 ヒューリスティクスはあまりイカないらしい まとめ ...
• 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)) つまり，遅延時間の分布が指数関数 他の関数でも使える 情報拡散過程は普通 ...
• Co-clustering documents and words using Bipartite Spectral Graph Partitioning
  Co-clustering documents and words using Bipartite Spectral Graph Partitioning Inderjit S. Dhillon KDD 2001 概要 文書と単語の共クラスタリング カット最小化として妥当な問題設定 スペクトラルグラフ理論の知見から固有ベクトル計算問題として緩和 後はk-meansすると大体上手い 問題設定 $$ G=({\cal D}, {\cal W}, E) $$ 文書と単語の二部グラフ 辺重みが謎… 単語・文書クラスタリングの関係 文書のクラスタが与えられた時、各単語は{最も重み和の大きい文書クラスタ}に対応する単語クラスタに属すると考える というわけで、k...
• Top-K Nearest Keyword Search on Large Graphs
  Top-K Nearest Keyword Search on Large Graphs Miao Qiao, Lu Qin, Hong Cheng, Jeffrey Xu Yu, Wentao Tian In VLDB 2013 メモ Jeffrey Xu Yu!! 概要 top-k nearest keyword search 頂点 0個以上のキーワード 辺 長さ クエリ ノード、キーワード、k 出力 キーワードを含みノードに近いkノード top-k nearest keyword search に対するアルゴリズム 最短経路木 2つ提案 kが小さいよう 大きくてもOK 応用 Facebo...
• 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 サイズが大きくなる...
• 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が高い 解釈 情報発信能力と情報収集能力が共に高い頂点が多いと情報拡散能力の高いグラフ...
• 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...
• 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 ...
• Lazy Walks Versus Walks with Backstep: Flavor of PageRank
  Lazy Walks Versus Walks with Backstep Flavor of PageRank Mieczysław A. Kłopotek, Sławomir T. Wierzcho´n, Krzysztof Ciesielski, Dariusz Czerski, Michał Drami´nski WI-IAT 2014 概要だけ PageRankの色々な変種を考える でも，PageRankで表現できる Lazy Random Walk x = (1-α)(0.5I+0.5P)x + αb 確率(1-α)/2 Random walk 確率(1-α)/2 留まる (lazy) 確率α Random jump Generalized Lazy Rando...
• 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 ...
• 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は感染しない 手法 σが小さくなるノードを貪欲に選んでいく 実験 比較...
• @wiki全体から「Propagation of Trust and Distrust」で調べる

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