todo314 @ ウィキ
todo314 @ ウィキ

Simulated Annealing Based Influence Maximization in Social Networks

todo314 @ ウィキ内検索 / 「Simulated Annealing Based Influence Maximization in Social Networks」で検索した結果

検索 :
  • 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...
  • 論文一覧
    ... 2012 Simulated Annealing Based Influence Maximization in Social Networks AAAI 2011 On Approximation of Real-World Influence Spread PKDD 2012 Scalable and Parallelizable Processing of Influence Maximization for ... ICDE 2013 Simpath An Efficient Algorithm for Influence Maximization under the Linear ... ICDM 2011 Probabilistic Solutions of Influence Propagation on Networks C...
  • Time Constrained Influence Maximization in Social Networks
    Time Constrained Influence Maximization in Social Networks Bo Liu, Gao Cong, Dong Xu, Yifeng Zeng ICDM 2012 ※Wei ChenのTime-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Processとは独立らしい 概要 時間制限付きinfluence maximizationを提案 NP-hardだけどmonotoneかつsubmodular Influence Spreading Pathという速いアルゴリズムを提案 実験して提案手法とベースラインを比較 モデル・問...
  • Personalized Influence Maximization on Social Networks
    Personalized Influence Maximization on Social Networks Jing Guo, Peng Zhang, Chuan Zhou, Yanan Cao, Li Guo 中国科学院の人たち CIKM 2013 概要 influence maximizationの亜種を考案 特定のノードにinfluenceする確率を上げたい この問題設定における性質とかを挙げてアルゴリズムを設計 普通のと、それの高速化と、ヒューリスティクスっぽいの ベースラインを比較していいことを示した 問題 目的関数 $$ R_w(U) = \mathbb{E}^U[1_{\{w \in X\}}] $$ ターゲットwがUによりinfluence...
  • Time-Critical Influence Maximization in Social Networks with Time-Delayed ...
    Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process Wei Chen, Wei Lu, Ning Zhang AAAI 2012 概要 ICモデルは時間制限を設けないからダメ 締切＋時間の遅延付きモデルを考案 高速(?)アルゴリズムも提案して実験 Independent Cascade with Meeting events 遭遇確率 m(u,v) 伝搬確率 p(u,v) 各ステップtで、アクティブな頂点uは非アクティブな頂点に確率m(u,v)で遭遇する 一回目の遭遇において確率p(u,v)でアクティベーションが成功する これは一回だけ ...
  • On Budgeted Influence Maximization in Social Networks
    On Budgeted Influence Maximization in Social Networks Huy Nguyen, Rong Zheng JSAC 2013 概要 頂点に単一でないコストがついた影響最大化 貪欲アルゴリズムをちょっと変形して1-1/√e近似 σを効率良く求めるためにDAGを作って信念伝搬っぽいことをやる Budgeted Influence Maximization 情報拡散モデルはIC max σ(S) s.t. c(S)≦b c(S)はc(u)(u∈S)の総和 [σ(S+v)-σ(S)]/c(v)で貪欲に選ぶと近似比が任意に悪くなる Leskovecのでも説明してたな… Improved Greedy ↑...
  • IMGPU: GPU-Accelerated Influence Maximization in Large-Scale Social Networks
    IMGPU GPU-Accelerated Influence Maximization in Large-Scale Social Networks Mo Li, Zhenjiang Li, Longfei Shangguan, Shaojie Tang, and Xiang-Yang Li TPDS 2014 概要 influence maximizationのGPUを取り入れたよ 既存手法の60倍速くなったよ IMGPU Bottom-Up Traversal Algorithm (BUTA) 元のグラフから沢山ランダムグラフを作る 各頂点のレベルを定義 末端までの最長距離 レベルで並列化するよ SCC内は全部同じなのでつぶすよ σ_S(u) =...
  • 気になった論文
    理論計算機科学 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...
  • CELF++: Optimizing the Greedy Algorithm for Influence Maximization in Social ...
    CELF++ Optimizing the Greedy Algorithm for Influence Maximization in Social Networks Amit Goyal, Wei Lu, Laks V.S. Lakshmanan 何かよく見るな名前 WWW 2011 CELF++ CELFを速くしたよ！！！ 頂点uは→を持つ u.mg1, u.prev_best, u.mg2, u.flag mg1 Sに対するマージン prev_best u以前に見た中でbest mg2 S+prev_bestに対するマージン flag 最後にmg1が更新された時刻 どうやって早くなるの？ とりあえず、↑の値を全部計算済みだとする 最後に...
  • Real-time Targeted Influence Maximization for Online Advertisements
    Real-time Targeted Influence Maximization for Online Advertisements Yuchen Li, Dongxiang Zhang, Kian-Lee Tan VLDB 2015 概要だけ Keyword-Based Targeted Influence Maximization トピックつきのモデル キーワード集合Tとシードサイズkが与えられる Tによって、頂点の重みが変わる(TF-IDFに基づいた奴)、Tに関して線形な感じ $$ \phi(v,T) = \sum_{w \in T}\mathrm{tf}_{w,v} \cdot \mathrm{idf}_w $$ if_wvはユーザvのワードwへの嗜好 だから"targeted...
  • CINEMA: Conformity-Aware Greedy Algorithm for Influence Maximization in ...
    CINEMA Conformity-Aware Greedy Algorithm for Influence Maximization in Online Social Networks Hui Li, Sourav S Bhowmick, Aixin Sun EDBT 2013 Contribution conformity-aware cascade model(c^2 model) の提案 mag-list というデータ構造 CINEMA (Conformity-aware INfluEnce MAximization) 部分グラフに分割する←a novel approach ??? 何が問題なの？ ぶっちゃけよく分からん とにかく普通のIC・LTモデルはダメでconfo...
  • 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する 予備知識みたいな...
  • 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}...
  • Cost-aware Targeted Viral Marketing in Billion-scale Networks
    Cost-aware Targeted Viral Marketing in Billion-scale Networks Hung T. Nguyen, Thang N. Dinh, My T. Thai INFOCOM 2016 概要 新しい問題 Cost-aware Targeted Viral Marketing ユーザ毎に最初の費用が違う ユーザ毎に影響させた事による効果が違う いい感じにすれば$$ 1-1/\sqrt{e} $$近似が可能 効率的アルゴリズム BCT：CTVMにもInfMaxにも適用可能 LISA [CSoNet 15]の後続 Cost-aware Targeted Viral Marketing 費用$$c(u)$$、利益$$b(u)$$、予算$...
  • 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にな...
  • Influence Blocking Maximization in Social Networks under the Competitive ...
    Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model Xinran He, Guojie Song, Wei Chen, Qingye Jiang SDM 2012 概要 Competitive Linear Threshold モデルを考えたよ 目的関数は自分の最大化じゃなくて，相手の最大化だよ そうするとこのモデルではsubmodularだよ 目的関数の計算が大変なのでPMIAっぽいものを作った Competitive Linear Threshold Model 各辺には2つの重みw+とw-がある 各頂点の閾値も2つθ+とθ- 状態はin...
  • Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale ...
    Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale Social Networks Wei Chen, Chi Wang, Yajun Wang In KDD 2010 概要 MIAモデルというのを使ってinfluence maximizationを高速化 アルゴリズム maximum influence paths (MIP) v- uへの伝搬は最短経路だけを考える しきい値θ以下の伝搬は無視する Dijkstraの途中で打ち切る maximum influence arborescence model influence spreadを以下で近似 $$ ...
  • Resampling-based Predictive Simulation for Identifying Influential Nodes ...
    Resampling-based Predictive Simulation for Identifying Influential Nodes over Social Network 社会ネットワーク上の強影響度ノード同定のためのリサンプリングに基づく予測シミュレーション法の提案 Kouzou Ohara, Kazumi Saito, Masahiro Kimura, Hiroshi Motoda JSAI 2014 概要 ICモデルのシミュレーションは何回やればいいの？ 真の影響度との誤差を知りたいけれど，真値が分からない leave-N-out 交差検証 |S|回シミュレートした $$ \bar{A}_S(v) $$ 試行集合Sに対するvの影響度の平均値 パラメータNについて↓で...
  • Mining Social Networks Using Heat Diffusion Processes for Marketing ...
    Mining Social Networks Using Heat Diffusion Processes for Marketing Candidates Selection Hao Ma, Haixuan Yang, Michael R. Lyu, Irwin King CIKM 2008 概要 熱拡散過程によるモデリング 3つの拡散モデル，3つのアルゴリズム 製品採択に時間を入れる クラスタ（係数）を反映 正負の意見を伝える 熱拡散モデル 当然，物理現象 分類，次元削減とかに使われている 開発者・ターゲットは熱源として振る舞い，一杯熱を持ってる で，どんどん広がっていく f_t(x,t)=Δf(x,t) f(x,t) 時刻t...
  • Efficient Influence Maximization in Social Networks
    Efficient Influence Maximization in Social Networks Wei Chen, Yajun Wang, Siyu Yang In KDD 2009 概要 Wei Chen 劇場の始まりっぽい influence maximization のアルゴリズムを2つ提案 greedy based algorithm の高速化 ヒューリスティックによるinfluence spreadの近似 アルゴリズム NewGreedyIC seedを選ぶためにグラフをR=20000個作る Sから到達可能なノードは省く vから到達可能なノード数を計算、これがmarginに相当 これの計算は自明ではないが論文ではlinearでできると...
  • メニュー
    メニュー トップページ 論文一覧 気になった論文 Parameterized Algorithms influence maximizati ICDM KDD AAAI k-means SCG SODA nearest neighbor IJCAI VLDB clustering coefficie random walk WWW STOC SIGMOD quasi-clique NIPS ICML SDM PNAS JMLR information diffusio triangle I/O-efficient algori Econometrica SCC streaming algorithm JEA ALENEX graph partitioning spectral clustering causality t...
  • ASIM: A Scalable Algorithm for Influence Maximization under the Independent ...
    ASIM A Scalable Algorithm for Influence Maximization under the Independent Cascade Model Sainyam Galhotra, Akhil Arora, Srinivas Virinchi, Shourya Roy WWW 2015 概要だけ 当時最強のTIMはメモリ消費がやばいので、新しいアルゴリズムを作ったよ！ アルゴリズム Simpath An Efficient Algorithm for Influence Maximization under the Linear ...のような事をする vのスコア：vから始まる単純経路の重み付き和、重みは辺確率の積 辺確率行列Pの行列積のようなもの？ 以降の反復...
  • Competitive Influence Maximization in Social Networks
    Competitive Influence Maximization in Social Networks Shishir Bharathi, David Kempe, Mahyar Salek WINE 2007 概要 モデル 辺uvが試行成功したら指数分布の遅延時間T_{uv}が発生する bプレイヤがサイズk_i以下の集合S_iを選択する 複数人が選択した頂点はランダムに誰かの頂点になる これでカスケードをしていく 純粋戦略ナッシュ均衡は無い（？） 混合戦略ナッシュ均衡は有る 戦略 もし，他の人の戦略が固定されていたら 自分の戦略に対するσは単調かつ劣モジュラ First Mover Strategies Influence Max...
  • Influence Diffusion Dynamics and Influence Maximization in Social Networks ...
    Influence Diffusion Dynamics and Influence Maximization in Social Networks with Friend and Foe Relationships Yanhua Li, Wei Chen, Yajun Wang, Zhi-Li Zhang WSDM 2013 概要 voter modelを拡張 元はunsigned network signed networkにした 味方とは同じ意見（色） 敵とは違う意見（色） 最初の色の分布を与えた時の挙動を解析（面白い） このモデルでinfluence maximization ある意味で簡単 確率的振舞を計算するのが超大変 Voter ...
  • Delineating Social Network Data Anonymization via Random Edge Perturbation
    Delineating Social Network Data Anonymization via Random Edge Perturbation Mingqiang Xue, Panagiotis Karras, Chedy Raissi, Panos Kalnis, Hung Keng Pung CIKM 2012 概要 random edge perturbation によるグラフの匿名化 上を攻撃する手法 グラフの特徴量を推定 Random Edge Perturbation 辺を確率μで独立に足したり消したりする XORってこと denseになるけどいいや 色々推定 ※μは公開するとして良い 密度 μが分かるので、て...
  • Approximate Convex Decomposition Based Localization in Wireless Sensor Networks
    Approximate Convex Decomposition Based Localization in Wireless Sensor Networks Wenping Liu, Dan Wang, Hongbo Jiang, Wenyu Liu, Chonggang Wang INFOCOM 2012 概要 Localization やばいのでヒューリスティクスばかり MDSって既存手法 凹だったり穴があるとやばい 凸図形に分割して気合 問題 2次元のWireless Sensor Netrwork 各頂点の位置が知りたい GPSはコスト高 ｰ すこしの頂点（アンカー）だけに設置 互いに距離が小さい所は通信 その距離が分からない場合...
  • 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を...
  • 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...
  • Influence Maximization in Social Networks When Negative Opinions May Emerge ...
    Influence Maximization in Social Networks When Negative Opinions May Emerge and Propagate Wei Chen, Alex Collins, Rachel Cummings, Te Ke, Zhenming Liu, David Rincon, Xiaorui Sun, Yajun Wang, Wei Wei, Yifei Yuan SDM 2011 概要 商品の質が低かったらdisる人も出るよねーをモデル化 質をパラメータに含めたNegative Opinion付き positiveな人数が目的関数ならsubmodularは保たれる 速い手法を作って実験してみたよ Independent Cascade Mode...
  • 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ノードを一様サンプリングす...
  • 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は感染しない 手法 σが小さくなるノードを貪欲に選んでいく 実験 比較...
  • IRIE: Scalable and Robust Influence Maximization in Social Networks
    IRIE Scalable and Robust Influence Maximization in Social Networks Kyomin Jung, Wooram Heo, Wei Chen In ICDM 2012 概要 Influence maximizationを超高速に求めるアルゴリズムを開発 しかもロバストに良い解を発見する アルゴリズム $$ \sigma(S \cup \{v\}) - \sigma(S) $$を次で近似する $$ r(v) = (1-AP_S(v))\left[ 1+\alpha \sum_{vu}p_{vu}r(u) \right] $$ AP_S(v) Sがvをactivateする確率 $$ AP_S(v) - \sum_{s \in ...
  • Learning Diffusion Probability based on Node Attributes in Social Networks
    Learning Diffusion Probability based on Node Attributes in Social Networks Kazumi Saito, Kouzou Ohara, Yuki Yamagishi, Masahiro Kimura, Hiroshi Motoda ISMIS 2011 概要 拡張した情報拡散モデル 時間遅延付き 頂点属性付き（新しい） パラメータ学習を提案 人口データで実験 上手くいった！ AsICモデル 実際の情報拡散は離散時間なワケがない p_uv 伝播確率 r_uv 遅延時間のパラメータ 遅延時間は指数分布 頂点属性 頂点vはJ個の属性を持つ，j番目はv...
  • Information Propagation Game: a Tool to Acquire Human Playing Data for ...
    Information Propagation Game a Tool to Acquire Human Playing Data for MultiPlayer Influence Maximization on Social Networks Hung-Hsuan Chen, Yan-Bin Ciou, Shou-De Lin KDD 2012 概要だけ アプリケーションの話だったでござる competitiveなモデル 交互に頂点を選んで行ったり，先手がk頂点選んでから後手がk頂点選ぶとか こういうのをゲームのアプリケーションとして色々やってみる 特に面白い点は無かった KDD 影響最大化 情報拡散 2014-06-18 17 17 19 (Wed)
  • A Novel and Model Independent Approach for Efficient Influence Maximization ...
    A Novel and Model Independent Approach for Efficient Influence Maximization in Social Networks Hemank Lamba, Ramasuri Narayanam WISE 2013 概要 influence maximizationの手法は大体はモデルに強く依存する(・A・)ｲｸﾅｲ!! sparsificationするよ！ 精度を落とさずに数倍高速化 提案手法 ある頂点の近傍のスコアを出す スコアの出し方 色々な基準を大量に持ってくる 適当に重みを計算して足し合わせる スコアの大きい近傍をdeg(i)^eだけ残す 0 =e =1 実験 ...
  • 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して木っぽくパスを広げる（同じ頂点がいくつかある...
  • Extracting Influential Nodes for Information Diffusion on a Social Network
    Extracting Influential Nodes for Information Diffusion on a Social Network Masahiro Kimura, Kazumi Saito, Ryohei Nakano AAAI 2007 概要 influence maximizationの高速アルゴリズム ICとLT 提案手法 ICもLTもランダムグラフを考えればいい σの増加量を効率的にもとめる 事前にランダムグラフを作っておく シード集合 A Aから到達可能な頂点を除く 頂点uについて，↑で出来たグラフでuから到達可能な頂点数Fをもとめる uと同じ連結成分に入っている頂点vについて，σ_i(A∪{v})=σ_i(A)+Fとする ...
  • 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が高い 解釈 情報発信能力と情報収集能力が共に高い頂点が多いと情報拡散能力の高いグラフ...
  • On Influential Node Discovery in Dynamic Social Networks
    On Influential Node Discovery in Dynamic Social Networks Charu Aggarwal, Shuyang Lin, Philip S. Yu SDM 2012 概要 SN上のやりとりは瞬間的 その確率は瞬間を表す時間の関数 globally optimized forward trace approach locally optimized backward approach 動的モデル 頂点・辺はある時間帯に存在するみたいな感じ f_ij(δt) = a(1-exp(-λ_ij*δt)) δtの時間だけ辺ijが出現する時の伝播確率 (t1, t2)の間に辺(i, j)があるとする (t1, t2)をm分割してδt_iとす...
  • A Data-Based Approach to Social Influence Maximization
    A Data-Based Approach to Social Influence Maximization Amit Goyal, Francesco Bonchi, Laks V. S. Lakshmanan VLDB 2012 概要 Data-Basedの意味：伝播確率をデータから推定するのではなく、直接σを推定する Credit Distribution Modelというモデルを提案 NP-hardでsubmodular σ_CDでの最大化が良いし速い！！ 何でこんなことになったのか いろんなモデルを使って実験してみよう weighted cascade model trivalency model uniform IC model EMアルゴリズ...
  • Maximizing Submodular Set Function with Connectivity Constraint: Theory and ...
    Maximizing Submodular Set Function with Connectivity Constraint Theory and Application to Networks Tung-Wei Kuo, Kate Ching-Ju Lin, Ming-Jer Tsai Research Center for Information Technology Innovation（資訊科技創新研究中心） National Tsing Hua University（國立清華大學） INFOCOM 2013 概要 ワイヤレスネットワークのルーターの設置問題 submodular関数で表せる さらにルーターは連結であるという制約を追加 この設定でも近似アルゴリズムが設計できる 1...
  • Reducing Social Network Dimensions Using Matrix Factorization Methods
    Reducing Social Network Dimensions Using Matrix Factorization Methods Václav Snášel, Zdenek Horák, Jana Kocıbová, Ajith Abraham ASONAM 2009 概要だけ グラフを小さくしたい concept lattice(概念束)なるものがあるらしい Formal concept analysis(形式概念分析)と特異値分解 ASONAM 概念束 特異値分解 2014-09-21 01 47 31 (Sun)
  • Dynamic Influence Maximization Under Increasing Returns to Scale
    Dynamic Influence Maximization Under Increasing Returns to Scale Haifeng Zhang, Ariel D. Procaccia, Yevgeniy Vorobeychik AAMAS 2015 概要 時間が動的な設定 予算投入を途中で行う 活性化頂点 時間に従い適当に増える，指数とか多項式とか 予算 時間に従い指数的に増える 適当な設定では，ある時点に一斉投入（使い切る）のが最適 そうでない場合はヒューリスティクス 導入 ICモデルは劣モジュラ 最近は適応的劣モジュラ最大化もある しかし，Bassモデルのような古典的なモデルはS-shaped Curve ここはミスリーディングで，劣...
  • An Upper Bound based Greedy Algorithm for Mining Top-k Influential Nodes in ...
    An Upper Bound based Greedy Algorithm for Mining Top-k Influential Nodes in Social Networks Chuan Zhou, Peng Zhang, Jing Guo, Li Guo WWW 2014 companion ポスター 概要 UBLF An Upper Bound Based Approach to Discover Influential Nodes in Social ...のLT版 CELFより5倍速い 提案手法 σ(S)=ΣΠw(e)の形でかける ↑は行列のべき乗和（有限）で上から抑えられる Wのべき乗和は(I-W)^-1で上から抑えられる 確率だから1以下って制約とか...
  • Influence Maximization in Undirected Networks
    Influence Maximization in Undirected Networks Sanjeev Khanna Brendan Lucier SODA 2014 難しいので概要だけ 無向グラフでのinfluence maximizationでは、貪欲アルゴリズムは1-1/eよりも良い近似比が保証できるという話 1-1/e+c cはタイトな値は示さずfuture work 直感的な例 p12=1/2, p13=1/2のグラフを考える 有向グラフだと、貪欲解={1,2}、最適解={2,3}で競合比が酷いことになる 無向グラフだと、貪欲解={2,3}、最適解={2,3}で一致する こういうのを考慮すると良いらしい XYZ Lemma x,y,zが確率pで...
  • 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) ...
  • 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)に従う 平均α/(α+β) 拡散の履歴から各α，βをインクリメントするだ...
  • Efficient algorithms for influence maximization in social networks
    Efficient algorithms for influence maximization in social networks Yi-Cheng Chen, Wen-Chih Peng, Suh-Yin Lee KAIS 2012 概要 CDH Community and Degree Heuristic CDH-KcutとCDH-SHRINK Heat diffusion model (HDM) 熱拡散（物理現象） f_i(t) 時刻tでのv_iの熱 初期状態t=0が与えられる 近傍からΔtの間影響を受ける iの変化量 = αΣ_j [f_j(t)-f_i(t)] 熱がθを超えたらアクティブになったとする シードに対してf(t_0)=h_0とセットする...
  • 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)につい...
  • Scalable Influence Maximization in Social Networks under the Linear ...
    Scalable Influence Maximization in Social Networks under the Linear Threshold Model Wei Chen, Yifei Yuan, Li Zhang In ICDM 2010 概要 LTモデル用の高速アルゴリズム LTモデルでのσの計算は#P-hard DAGをとってきて、それの上で高速計算 #P-hardness 基本は単純経路の数え上げからの帰着 アルゴリズム LTモデルからlive-edge graphを考える eはw_eの確率で残ると書いてあるが、本当だろうか…？ Kempeのではもっと複雑なことをしていた こうすると、random graph上でのreacha...
  • @wiki全体から「Simulated Annealing Based Influence Maximization in Social Networks」で調べる

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