todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「2013 State of Social Media Spam」で検索した結果

• 論文一覧
  ....il/files/2013/03/notes_2007_Fall.pdf (PCPP; robust PCP) CS359 Hardness of Approximation (Tim Roughgarden, 2007) https //timroughgarden.org/w07b/w07b.html (講義録少) 😋15-854(B) Advanced Approximation Algorithms (2008, Anupam Gupta Ryan O Donnell) https //www.cs.cmu.edu/~anupamg/adv-approx/ 😋6.895 Probabilistically Checkable Proofs and Hardness of Approximation (2010, Dana Moshkovit...
• 気になった論文
  ... ICALP 2013 Optimal Partitioning for Dual Pivot Quicksort New Doubling Spanners Better and Simpler Maximum Edge-Disjoint Paths in k-Sums of Graphs Faster Exponential-Time Algorithms in Graphs of Bounded Average Degree Fixed-Parameter Algorithms for Minimum Cost Edge-Connectivity Augmentation- ICALP 2014 Listing Triangles Randomized Rumor Spreading in D...
• 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 スパム同士は結合...
• 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...
• 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...
• A user-centric model of voting intention from Social Media
  ...n ACL 2013 株価，伝染病，地震の被害予測 世論調査 媒体 個別訪問，電話（ランダム），インターネット 媒体としてのTwitter 利点 低コスト，若者の意見を反映 欠点 ユーザの偏り（暇人ばっか），嘘 線形回帰モデル 目的変数=係数*説明変数+決定項 y=ax+c 正則化項の目的 パラメータがスパースになれるよ！ 提案モデル Bilinear Elastic Net(BEN) 単語頻度とユーザを考慮した線形回帰モデル Elastic Net 正則化項がこれらしい 評価 イギリス 政党数3，60Mツイート オーストリア 政党数4，0.8Mツイート ...
• 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)に従う 平均α/(α+β) 拡散の履歴から各α，βをインクリメントするだ...
• Negative Influence Minimizing by Blocking Nodes in Social Networks
  ... Workshop 2013 概要 ノードを取り除いて影響の拡散を抑えたい！ ウイルス，誤情報等 Negative Influence Minimization 感染シード(given) I ブロック S(|S|=k) 目標 minimize σ(I; V-S) Sは感染しない 手法 σが小さくなるノードを貪欲に選んでいく 実験 比較対象 出次数，betweenness，PageRank 設定 |E|=370K ICモデル p=0.2,0.4 100~200位感染シードを設定 適当なヒューリスティクスはダメ，提案手法はoutperform まとめ ...
• 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する 予備知識みたいな...
• 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...
• Estimating Sizes of Social Networks via Biased Sampling
  ...ampling 2013-12-16 14 31 41 (Mon)
• 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 ...
• 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...
• The Role of Social Networks in Information Diffusion
  ...trength 2013-10-17 23 36 57 (Thu)
• Limiting the Spread of Misinformation in Social Networks
  ...ffusion 2013-10-24 01 09 16 (Thu)
• Scalable and Parallelizable Processing of Influence Maximization for ...
  ... In ICDE 2013 概要 並列化可能なアルゴリズム 競技相手はPMIA 質はCELF並、PMIAより良い 速度はPMIAより速い 提案手法 Independent Path Algorithm(IPA) 経路を指定したらそれを使う確率は全部かければ良い グラフがもらえた 有るノードからtraverseして木っぽくパスを広げる（同じ頂点がいくつかある） しきい値θ未満になった or 閉路にあたったら打ち切り もっかいまとめる（同じ頂点がいくつかある） σ(v)は、vからいけるやつについて、各々確率を足す（+1は自分 v- uの確率は、1-Π[1-ipp(p)] pは↑ので計算されるであろう経路達 ...
• 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は分からない いつ誰が記事を投稿 / 病...
• 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 サイズが大きくなる...
• 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)
• 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種類あるので、最大の確率はかなり小さく、代表的とは...
• 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) ...
• Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs
  ... 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)を求めないで頑張る 乱択を使う 3/2近似が高速O(m^{2-\eps})にできると，2と3が区別できる． それから，支配集合問題を帰着できる O(n^{k-\eps})時間で求められる． 支配集合問題はS...
• Privacy Preserving Estimation of Social Influence
  Privacy Preserving Estimation of Social Influence Tamir Tassa, Francesco Bonchi EDBT 2014 概要だけ 情報拡散モデルには辺確率の推定が必要 実際には，2種類の人がいる グラフを持っているホスト カスケードのログを持っているサービス提供者（複数） 互いに情報を教えたくない，サービス提供者同士でも 実験では，通信費用を見ている EDBT 情報拡散 秘匿性保護 2015/03/10 1 40
• Estimating Clustering Coefficients and Size of Social Networks via Random Walk
  ... In WWW 2013 メモ Liran KatzirはMSR Israel 概要 ランダムウォークでクラスタ係数と頂点数を見積もる 全体をとってくるのが厳しい用 ちょっとタイムリー 既存手法よりかなり良い 近似が指数関数的によくなる（ランダムウォークの長さの 頂点のIDと、隣接リスト（次数）さえわかれば良い しかも前と後の1つずつだけ覚えていれば計算可能 問題 global clustering coefficient average clustering coefficient network size 参考 clustering coefficient 前提知識 Random walk...
• The Power of Random Neighbors in Social Networks
  The Power of Random Neighbors in Social Networks Silvio Lattanzi, Yaron Singer WSDM 2015 概要 友達は友達が多い (friendship paradox) power-lawが十分条件では無い どういうモデルがparadoxを説明できるのか？ というわけで，モデルを提案 辺を張り替える 影響最大化への適用例 友達の逆説 friendship paradox 友達は友達が多い （頂点の近傍次数） （その頂点の近傍の平均次数） power-lawが十分条件では無い 実際にそういう例を作れる 極端な例 正則グラフ ☆ ...
• 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上のランダムウォークでやる ...
• On the Streaming Complexity of Computing Local Clustering Coefficients
  ... WSDM 2013 概要 ワンパスでlocal clustering coefficientを求めたい ローカルなので、頂点ごと 辺リストが任意の順でもらえる 全く三角形が無い or 1/2以上のCCを持つ次数2d以上の頂点がある、かをある程度の確率でワンパスで判定するためにはΩ(m/d)ビット必要 ↑の限界にマッチした乱択アルゴリズムを考案 Lower bound Theorem 1 ワンパス乱択アルゴリズムが 次数2dの頂点はクラスタ係数0 クラスタ係数1/2位上の次数2dの頂点が存在する を1/3以上の確率で正しく区別するためにはΩ(m/d)bit以上を必要とする One pass algorithm ...
• Triadic Measures on Graphs: The Power of Wedge Sampling
  ...a SDM 2013 概要 クラスタ係数、次数毎のとか、色々を統一的なフレームワークでもとめる wedgeを適当な重みでサンプリングしてtriangleを数えるだけ サンプルサイズがグラフのサイズに依存しないところがポイント シンプルにboundが出る 提案手法 サンプリングの方法 基本的にはwedgeをとってきて、それがtriangleを構成するか？を判定する global clustering coefficient choose(deg(v), 2)に比例する確率でvをとってくる vの近傍2頂点u,wをランダムにとってくる (u,v,w)は一様ランダムにサンプリングされる k = O(ε^{-2}logδ)サンプルで(ε,δ)を保証 ...
• Blocking Links to Minimize Contamination Spread in a Social Network
  Blocking Links to Minimize Contamination Spread in a Social Network Masahiro Kimura, Kazumi Saito, Hiroshi Motoda TKDD 2009 多分Minimizing the Spread of Contamination by Blocking Links in a Networkのジャーナル版
• k-means++: The Advantages of Careful Seeding
  ...k-means 2013-10-07 16 00 46 (Mon)
• Top-K Nearest Keyword Search on Large Graphs
  ... In VLDB 2013 メモ Jeffrey Xu Yu!! 概要 top-k nearest keyword search 頂点 0個以上のキーワード 辺 長さ クエリ ノード、キーワード、k 出力 キーワードを含みノードに近いkノード top-k nearest keyword search に対するアルゴリズム 最短経路木 2つ提案 kが小さいよう 大きくてもOK 応用 Facebook、hikingが好きな20人を探すというのは、なんか使える 近い店を列挙 既存手法 Partitioned Multi-Indexing (PMI) distance o...
• Probabilistic Solutions of Influence Propagation on Networks
  ... 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 1→3→2 wp P_13*P_32 ただし、この2つはindependentでないので包除原理をする $$ \pi_2 = P_{1 \rightarrow 2} + P_{1 \rig...
• 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 ...
• Recommendations to Boost Content Spread in Social Networks
  Recommendations to Boost Content Spread in Social Networks Vineet Chaoji, Sayan Ranu, Rajeev Rastogi, Rushi Bhatt WWW 2012 概要 コンテンツ共有は強力 どういう広がるかは連結関係が大事 共通近傍とか，類似度じゃなくて，コンテンツの量を考慮したい 辺を次数制約のもと挿入する 劣モジュラじゃないので，色々と改造する 近似アルゴリズム コンテンツ最大化問題 各頂点iについて $$ p_i $$ iが各近傍と共有する確率（独立） $$ c_i $$ iの作った／発見したコンテンツ $$ N_i $$ iと相性が良い頂点集合 ...
• Information Diffusion and External Influence in Networks
  ...ffusion 2013-10-16 03 19 42 (Wed)
• A Note on Maximizing the Spread of Influence in Social Networks
  A Note on Maximizing the 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つ選んで採択するんだ...
• 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...
• Minimum-Risk Maximum Clique Problem
  ...pproaches 2013 概要 最小危険最大クリーク問題 各頂点には費用／損失を表す確率変数 同時分布は既知 特定の危険尺度で危険最小のクリークを見つけたい 尺度の単調性から最適解は極大クリークになる Erdős–Rényiグラフで実験 導入 状況 頂点 が不確かさを持つ 危険回避グラフ理論的問題 Xi 頂点iに紐づく確率変数 Xiの同時分布は分かる 危険尺度ρ $$ \min_{S \subseteq V, w} \rho\left( \sum_{i \in S} w_i X_i \right) $$ $$ s.t. \sum_{i \in S} w_i = 1, w_i \geq 0, S[G] \...
• 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| $$番...
• 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がアクテ...
• Exact Computation of Influence Spread by Binary Decision Diagrams
  Exact Computation of Influence Spread by Binary Decision Diagrams Takanori Maehara, Hirofumi Suzuki, Masakazu Ishihata WWW 2017 概要 BDDで影響拡散を厳密計算する方法を提案 最大で100点くらいのグラフなら出来る！ 提案手法 到達可能性に関する情報を圧縮すれば良い もしBDDが構築できたら、後は任意の辺確率設定について、DAG上の動的計画法で計算できる 各頂点対(s,t)について構築できればOK；あとは併合すればいいので [sからtへ到達可能]を考えて、フロンティア法を実行 $$\texttt{isOneTerminal}$$ 今1の辺だけでsからt...
• 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を...
• Fast Discovery of Reliable k-terminal Subgraphs
  Fast Discovery of Reliable k-terminal Subgraphs Melissa Kasari, Hannu Toivonen, Petteri Hintsanen PAKDD 2010 概要 Uncertain graphがもらえるので、 クエリ頂点集合の連結確率を最大化する辺数に制限のついた部分グラフが欲しい 謎ヒューリスティクス提案 Path coveringを元に [Hintsanen-Toivonen-Sevon Fast discovery of reliable subnetworks]多分ASONAM 動機付け・問題定義 グラフがデカイので抽出するのが目的 興味があるもの（遺伝子とか）に関連あるのだけで良い 入...
• The Price of Stability for Undirected Broadcast Network Design with Fair ...
  ... In FOCS 2013 ブロードキャストゲーム nプレイヤー s1,…sn 1ゴール t 各々はsi- tを目指す プレイヤーiのコスト Σ_e c(e)/(eを使った人数) 例えばケーブルだったら、皆でコストを等分配 各プレイヤーのコストの総和が社会的コスト このゲームにはNash均衡がある cost Nash均衡 / cost 社会的最適 Contribution 無向グラフでの Price of Stability がO(1) やり方ふわふわ 何かのNash均衡をとってきて上からbound ポテンシャル最小は既に駄目と分かっている 局所探索する loglog nと分かっている Homo...
• Spectral Analysis of Communication Networks Using Dirichlet Eigenvalues
  ... In WWW 2013 概要 スペクトルグラフ理論 有限グラフでは適切なカット・コミュニティが見つけられない Dirichlet固有値を使うよ！ スペクトルグラフ理論 正規化されたラプラシアン degreeのところをちょっと変える $$ 0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n \leq 2 $$ スペクトルギャップ$$ \lambda_2 $$ コンダクタンス Cheeger不等式 木の固有値 d正則無限サイズ d正則有限サイズ 0に近づく 複雑ネットワークの構造 入力が巨大グラフの一部の場合は、あんまり意味ないとこを切...
• k-Nearest Neighbors in Uncertain Graphs
  k-Nearest Neighbors in Uncertain Graphs Michalis Potamias, Francesco Bonchi, Aristides Gionis, George Kollios VLDB 2010 概要 k近傍クエリ 最短距離や酔歩に基づく尺度を拡張 厳密計算は難しい Monte-Carloサンプリングで近似アルゴリズム グラフ変形，枝刈り 実験：数十M辺 メモ VLDB版ではない原稿を読んだのでちょっと違う イントロ 確率的グラフ 辺に確率が割り振られている センサや実験による雑音 不安定な通信 リンク予測 秘匿性のための摂動 気になること...
• Towards Context-Aware Search by Learning A Very Large Variable Length Hidden ...
  ...arch kk 2013-12-10 01 08 02 (Tue)
• 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...
• Profit Maximization over Social Networks
  Profit Maximization over Social Networks Wei Lu, Laks V.S. Lakshmanan ICDM 2012 概要 バイラルマーケティングで得られる利益についてちゃんと考えよう LTモデルを拡張するよ 非活性→活性→採択 [価格 評価]なら活性→採択に遷移 採択の段階で初めて利益発生 (利益 - シードへの費用)が評価関数 シードと価格の設定を求めたい Linear Threshold Model with User Valuation and Its Properties モデル・問題定義 v_i ユーザiが感じる商品への価値 確率分布から抽出 p_i 相場 c_a ...
• 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)だけど実験的にはもう少し速い（し精度も良い） 動機付けとか リバーネットワーク(?)の階層的構造を木構造で表現 その応...
• @wiki全体から「2013 State of Social Media Spam」で調べる

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