todo314 @ ウィキ
todo314 @ ウィキ

Theory of Cooperation in Complex Social Networks

todo314 @ ウィキ内検索 / 「Theory of Cooperation in Complex Social Networks」で検索した結果

検索 :
  • 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...
  • 論文一覧
    ...omplexity Theory (2017, Ryan O Donnell) http //www.cs.cmu.edu/~odonnell/complexity17/ その他 Journals with quick reviewing - Theoretical Computer Science Stack Exchange https //cstheory.stackexchange.com/questions/8335/journals-with-quick-reviewing Backlog of MathematicsResearch Journals https //www.ams.org/journals/notices/201810/rnoti-p1289.pdf Online TCS Seminars https //cs...
  • 気になった論文
    理論計算機科学 ACM Symposium on Theory of Computing STOC 2000 Circuit minimization problem A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions Improved algorithms for submodular function minimization and submodular flow On dual minimum cost flow algorithms The small-world phenomenon an algorithm perspective A random graph model for mass...
  • 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}...
  • 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ノードを一様サンプリングす...
  • 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...
  • 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...
  • 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 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]...
  • A General Framework of Hybrid Graph Sampling for Complex Network Analysis
    A General Framework of Hybrid Graph Sampling for Complex Network Analysis Xin Xu, Chul-Ho Lee, Do Young Eun INFOCOM 2014 概要 グラフをサンプリングしたい どっちかっていうとΣf(v)を近似したい ランダムウォークとかランダムジャンプとかある ランダムジャンプはたまに失敗する ↑を統合したのを考えて解析 分散（小さいと良）がランダムジャンプ確率に対して凸 既存手法 ランダムウォーク Simple Random Walk (SRW) with Re-weighting Metropolis-Hastings 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が十分条件では無い 実際にそういう例を作れる 極端な例 正則グラフ ☆ ...
  • 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 $...
  • Minimizing the Spread of Contamination by Blocking Links in a Network
    Minimizing the Spread of Contamination by Blocking Links in a Network Masahiro Kimura, Kazumi Saito, Hiroshi Motoda AAAI 2008 概要 タイトルまんまの論文 汚染最小化問題 目的関数は各頂点のσの平均 既存の研究（Kempe依然）では，出次数の大きい順に頂点を消していけば大体良いとしてた 今回は辺を消す 問題定義 min 1/|V|Σσ(v) Eからk辺取り除ける 提案手法 最も目的関数が小さい辺を選ぶ貪欲アルゴリズム σの計算がやばい この著者らが考えたBond Percolationで高速化 実験 ...
  • 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
    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は感染しない 手法 σが小さくなるノードを貪欲に選んでいく 実験 比較...
  • Importance Sketching of Influence Dynamics in Billion-scale Networks
    Importance Sketching of 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...
  • 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して木っぽくパスを広げる（同じ頂点がいくつかある...
  • 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 ある頂点の拡散過程を沢...
  • Locating the Source of Diffusion in Large-Scale Network
    Locating the Source of Diffusion in Large-Scale Network Pedro C. Pinto, Patrick Thiran, Martin Vetterli PRL 2012 概要 情報拡散の話 一部の頂点だけを観測して、「「発信源」」を推定する モデル化+実験 モデル 辺の時間 正規分布 負の値はごまかす 発信源 uniformly at randomに選択される 受信者 時刻+ソース 他の頂点に伝えない 理不尽な仮定はおかない 受信者がネットワークを分離したり、最初の観測時刻だけ記録 問題設定 入力 グラフ G=(V,E) 分布 ...
  • 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 $$ でかい...
  • 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...
  • 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を...
  • 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...
  • 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 ...
  • 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のジャーナル版
  • Control Profiles of Complex Networks
    Control Profiles of Complex Networks Justin Ruths, Derek Ruths Science 2014 概要 Network Controllabilityには次数分布が大事 特に重要なのはsourceとsinkの数 Network Controllability 微分方程式 dx(t)/dt = Ax(t)+Bu(t) A 隣接行列，B 入力行列 例 脳，人の意見，空港の利用客数 uをうまく設定してxを任意の状態にしたい 実際には… 辺の重みが分からん（ ＾ω＾）おっ Structural Controllability 辺の重みを（ゼロ以外に）定めてc...
  • 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 ...
  • Mining the Network Value of Customers
    Mining the Network Value of Customers Pedro Domingos, Matt Richardson KDD 2001 概要 中身はあんま読んでない http //www.lr.pi.titech.ac.jp/~ikeda/reading/2005-07-12.html マーケティングの決断 顧客から得られる利益 顧客へのマーケティングコスト の場合に実行 どうやって利益を知るか？ ネットワークから広がる利益の総量を測る ソーシャルネットワーク上マルコフ確率場を用いたモデル化 ネットワークは協調フィルタリングデータベースから作成 有効性を示した KDD バイラルマーケティング 2014-05-02 15...
  • 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 ヒューリスティクスはあまりイカないらしい まとめ ...
  • 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に適用 完全なひと月のデータ 情報がネットワークをジャンプしている ...
  • 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...
  • 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)) つまり，遅延時間の分布が指数関数 他の関数でも使える 情報拡散過程は普通 ...
  • 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...
  • 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...
  • 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_...
  • 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) ...
  • 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 ...
  • 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する 予備知識みたいな...
  • 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 ...
  • 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 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 サイズが大きくなる...
  • 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モデルでの応用 先...
  • 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と相性が良い頂点集合 ...
  • 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 complexity of influence maximization problem in the deterministic linear ...
    The complexity of influence maximization problem in the deterministic linear threshold model Zaixin Lu, Wei Zhang, WeiliWu, Joonmo Kim, Bin Fu Journal of Combinatorial Optimization 2012 概要だけ linear threshold modelのしきい値を固定したバージョンを考える 近似の難しさ しきい値を固定するとσは多項式時間で求められる 当たり前。なぜO(n^2)で求めている？ 何でこんなことをしたのか若干謎
  • 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...
  • 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で高速化 定式化 ...
  • A Gang of Bandits
    A Gang of Bandits 挑戦する問題 bandit problem contextual bandit problem Gang of Bandits Bandit problemとは スロットマシンがいっぱい、どうベットするのがいい？ やっていくと確率が推定できる Contextual 報酬を予測しながら行動、結果から予測モデルを修正 アイテムの推薦みたいな？ 学習 一番良かったの+信頼性みたいなのを考える contextual bandit problemをsocial networksで表現したい！！！！ ユーザの興味関心 アイテム推薦 隣接するユーザは類似 LinUCBっていうcont...
  • Fast Discovery of Reliable Subnetworks
    Fast Discovery of Reliable Subnetworks Petteri Hintsanen, Hannu Toivonen, Petteri Sevon ASONAM 2010 概要 The Most Reliable Subgraph Problemの2端子版のアルゴリズム ヒューリスティクス 提案手法 基本はランダムグラフのサンプリング Phase1 パスサンプリング s-tパスの候補集合を集める パスPを候補Cに足した時，Pr[C∨P]=Pr[C]+Pr[\bar{C}∧P]を最大化したい 怪しい感じ（保証等なし）に右項を近似計算する Phase2 部分グラフの構築 Pr[∨P]が最大となるようにCからパス部分集合を...
  • @wiki全体から「Theory of Cooperation in Complex Social Networks」で調べる

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