todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Estimating Sizes of Social Networks via Biased Sampling」で検索した結果

• 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ノードを一様サンプリングす...
• 論文一覧
  ...works Estimating Sizes of Social Networks via Biased Sampling CELF++ Optimizing the Greedy Algorithm for Influence Maximization in Social ... WWW 2012 The Role of Social Networks in Information Diffusion Analyzing Spammer s Social Networks for Fun and Profit Human Wayfinding in Information Networks Optimizing Budget Allocation Among Channels and Influencers ...
• 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...
• 気になった論文
  ...い Estimating graph parameters via random walks with restarts 頂点数とか、mixing time 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-Connec...
• 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...
• 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) ...
• 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...
• 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 サイズが大きくなる...
• 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}...
• 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...
• 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で活性な頂点の数...
• Spectral Counting of Triangles in Power-Law Networks via Element-Wise ...
  Spectral Counting of Triangles in Power-Law Networks via Element-Wise Sparsification 概要 三角形の個数を早く求めたい 辺を確率1-pで削除 残った辺に重み1/pを割り振る 固有値で近似 何か速いよ！( (ﾟ∀ﾟ∩ 提案手法 まず，隣接行列を低ランクに近似 高固有値だけ計算する Lanczos methodというのを使い固有値を大きい順に求めていく 現在の固有値の三乗和に対する寄与がtot以下になったら打ち切り Eigen Triangle $$ \Delta(G) = \frac{1}{6}\sum_{i=1}^{n}\lambda_i^3 $$ でかい...
• 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つ選んで採択するんだ...
• 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は感染しない 手法 σが小さくなるノードを貪欲に選んでいく 実験 比較...
• 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)に従う 平均α/(α+β) 拡散の履歴から各α，βをインクリメントするだ...
• 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 スパム同士は結合...
• 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...
• 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のジャーナル版
• 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 ...
• 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 ...
• Scalable and Parallelizable Processing of Influence Maximization for ...
  Scalable and Parallelizable Processing 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して木っぽくパスを広げる（同じ頂点がいくつかある...
• 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...
• 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する 予備知識みたいな...
• Revenue Maximization in Incentivized Social Advertising
  Revenue Maximization in Incentivized Social Advertising Çigdem Aslay, Francesco Bonchi, Laks V. S. Lakshmanan, Wei Lu VLDB 2017 概要 Viral Marketing Meets Social Advertising Ad Allocation with Minimum Regret VLDB 15の続き感 Incentivized ユーザにも収入の分け前を上げる設定 単調劣モジュラ最大化 with 分割マトロイド制約 (for 広告-シード配置) and 劣モジュラナップサック制約 (for 各広告主の予算) 2つの近似手法を提案して、RISで高速化 定式化 ...
• 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...
• 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)) つまり，遅延時間の分布が指数関数 他の関数でも使える 情報拡散過程は普通 ...
• 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)| $$を最小化せよ ...
• Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large ...
  Subgraph Frequencies Mapping the Empirical and Extremal Geography of Large Graph Collections Johan Ugander, Lars Backstrom, Jon Kleinberg In WWW 2013 メモ 岩田さん 概要 social networkを全体を見て解析するのではなく、密な部分ごとに見る 3-4頂点の部分グラフの出現頻度を見ると特徴がわかる 実験データ Facebook Lars BackstromがFacebookの人だからしょーがないね(´・ω・`) 抽出する部分グラフ Neighborhoods 友人 Groups...
• 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は分からない いつ誰が記事を投稿 / 病...
• 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に適用 完全なひと月のデータ 情報がネットワークをジャンプしている ...
• COMMIT: A Scalable Approach to Mining Communication Motifs from Dynamic Networks
  COMMIT A Scalable Approach to Mining Communication Motifs from Dynamic Networks Saket Gurukar, Sayan Ranu, Balaraman Ravindran SIGMOD 2015 概要 テンポラルネットワーク上で頻出するモチーフを抽出したい 次数列に変換，部分列マイニングで絞る Frequent subgraph mining A- B(1)とB- C(2) A- B(2)とB- C(1) 違うお グラフ同型問題的なので，時間的関係を考慮するのはちょいやばめ？ マイニング的手法…厳密でない 定義 辺はある時刻に瞬間的に発生 $$ |t_i - t_...
• 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 ある頂点の拡散過程を沢...
• 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)だけど実験的にはもう少し速い（し精度も良い） 動機付けとか リバーネットワーク(?)の階層的構造を木構造で表現 その応...
• 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モデルでの応用 先...
• 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)につい...
• Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph ...
  ...ethod for Estimating 4-Vertex Subgraph Counts Madhav Jha, C. Seshadhri, Ali Pinar WWW 2015 概要 数千万辺でも数十秒 誤差1%以下 Chernoff boundからエラーバーも出せる 問題定義 4-頂点部分グラフは6種類 3-star, 3-path, tailed-triangle 4-cycle, chordal-4-cycle, 4-clique C_i 誘導部分グラフにおけるi-th 部分グラフの出現個数 N_i i-th 部分グラフの出現個数 (C_i)と(N_i)は簡単な線形関係にある 特に各N_iは(C_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]...
• 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 ヒューリスティクスはあまりイカないらしい まとめ ...
• A user-centric model of voting intention from Social Media
  A user-centric model of voting intention from Social Media Vasileios Lampos, Daniel Preotiuc-Pietro, Trevor Cohn ACL 2013 株価，伝染病，地震の被害予測 世論調査 媒体 個別訪問，電話（ランダム），インターネット 媒体としてのTwitter 利点 低コスト，若者の意見を反映 欠点 ユーザの偏り（暇人ばっか），嘘 線形回帰モデル 目的変数=係数*説明変数+決定項 y=ax+c 正則化項の目的 パラメータがスパースになれるよ！ 提案モデル Bilinear Elastic Net(BEN) 単語頻度とユーザ...
• 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が十分条件では無い 実際にそういう例を作れる 極端な例 正則グラフ ☆ ...
• 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)
• 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_...
• 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 $...
• 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 ...
• The Power of Optimization from Samples
  The Power of Optimization from Samples Eric Balkanski, Aviad Rubinstein, Yaron Singer NIPS 2016 概要 単調劣モジュラ関数を大量の標本データからその場で学習 curvature制限時に多項式個のサンプルで近似比保証できる 動機づけと貢献 関数・信託のどちらにもアクセスできない 情報検索ランキング、タギング、影響最大化 学習した関数が劣モジュラでも、最適化結果はめちゃくちゃ駄目 各集合がサイズkの$$ \{ (S_i, f(S_i)) \}_{i \in [m]} $$がもらえる 被覆関数でも辛いよ！（limitation of optimization from samples）...
• 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...
• 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にな...
• 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 圧力とか出てくる 実際には圧力差しかいらない？ アダプテーション ...
• 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上のランダムウォークでやる ...
• Towards Context-Aware Search by Learning A Very Large Variable Length Hidden ...
  Towards Context-Aware Search by Learning A Very Large Variable Length Hidden Markov Model from Search Logs Huanhuan Cao, Daxin Jiang, Jian Pei, Enhong Chen, Hang Li MSRAとUniversity of Science and Technology of China WWW 2009 概要 たった今調べたクエリからURLを正しくレコメンドするのは無理 例 ホントは車のレビューサイトを見たい 検索クエリ Ford new cars → Toyota new cars 個々のクエリに着目するとautohome.comは出てこない ...
• @wiki全体から「Estimating Sizes of Social Networks via Biased Sampling」で調べる

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