todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Locating the Source of Diffusion in Large-Scale Network」で検索した結果

• 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) 分布 ...
• 論文一覧
  ...works Locating the Source of Diffusion in Large-Scale Network Enhanced Flow in Small-World Networks Science Quantifying Long-Term Scientific Impact Control Profiles of Complex Networks Nature Communications Griffiths phases and the stretching of criticality in brain networks A scaling law for random walks on networks Influence maximization in comple...
• 気になった論文
  理論計算機科学 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...
• 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...
• 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...
• 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...
• 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モデルでの応用 先...
• 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)に従う 平均α/(α+β) 拡散の履歴から各α，βをインクリメントするだ...
• 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 ...
• 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に適用 完全なひと月のデータ 情報がネットワークをジャンプしている ...
• 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して木っぽくパスを広げる（同じ頂点がいくつかある...
• 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)) つまり，遅延時間の分布が指数関数 他の関数でも使える 情報拡散過程は普通 ...
• 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は分からない いつ誰が記事を投稿 / 病...
• 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...
• 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 ...
• 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...
• 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...
• 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 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 サイズが大きくなる...
• 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を...
• 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...
• 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...
• 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...
• 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...
• 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が高い 解釈 情報発信能力と情報収集能力が共に高い頂点が多いと情報拡散能力の高いグラフ...
• 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...
• 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(ε)...
• 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は感染しない 手法 σが小さくなるノードを貪欲に選んでいく 実験 比較...
• 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...
• 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...
• 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)だけど実験的にはもう少し速い（し精度も良い） 動機付けとか リバーネットワーク(?)の階層的構造を木構造で表現 その応...
• 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 スパム同士は結合...
• 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) ...
• 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...
• 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つ選んで採択するんだ...
• 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は出てこない ...
• Maximizing the Extent of Spread in a Dynamic Network
  Maximizing the Extent of Spread 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 他の時刻で辺があったらまた試行できる ...
• 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を...
• 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...
• 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のジャーナル版
• 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)につい...
• 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]...
• 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 ...
• 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 $$ でかい...
• 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で高速化 定式化 ...
• 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}) $$を示した 実験的には数十倍速い 提案手法 設定 ...
• 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種類あるので、最大の確率はかなり小さく、代表的とは...
• The Pursuit of a Good Possible World: Extracting Representative Instances of ...
  The Pursuit of a Good Possible World Extracting Representative Instances of Uncertain Graphs Panos Parchas, Francesco Gullo, Dimitris Papadias Francesco Bonchi SIGMOD 2014 概要 Uncertain graphsを扱うのは大変 サンプリングは標本数が多くなる 問題：最短経路長，パターンマイニング，部分グラフ探索 問題毎にアドホックに開発されている→既存の枠組みが無駄→辛い あるグラフで代表させたい 元の性質を保ったまま，決定的な代表的グラフを作るよ 元の性質=（今回は）期待頂点次数 平均次数リワイヤ(AD...
• 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 圧力とか出てくる 実際には圧力差しかいらない？ アダプテーション ...
• 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する 予備知識みたいな...
• @wiki全体から「Locating the Source of Diffusion in Large-Scale Network」で調べる

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