todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Influence-based Network-oblivious Community Detection」で検索した結果

• Influence-based Network-oblivious Community Detection
  Influence-based Network-oblivious Community Detection Nicola Barbieri, Francesco Bonchi, Giuseppe Manco 最初の2人はYahoo Labs, Barcelona ICDM 2013 概要 ネットワークは与えられない 誰がいつ何かしたかのログが大量にある コミュニティ検出をしたい 情報拡散モデルをちょっと変えて検出させる 拡散具合はほぼコミュニティに依存するので、それを見積もろう Overview Q. ネットワークを再構築すればいいのでは？ A. 時間かかるので無理 例 Inferring Networks of Diffusion and Influe...
• 論文一覧
  ... Fast Influence-based Coarsening for Large Networks 予測 Prediction of Information Diffusion Probabilities for Independent Cascade Model Learning Continuous-Time Information Diffusion Model for Social Behavioral ... Learning Influence Probabilities In Social Networks Learning Stochastic Models of Information Flow Predicting Information Diffusion on Social Networks...
• 気になった論文
  ... MeiKe Influence-based Communities in Networks 影響力が高いkernel nodeと、橋渡しのmedia nodeを見つけたい ✔Multimodal Network Alignment David F. Gleich、応用として非匿名化に使える Near Optimal and Practical Algorithms for Graph Scan Statistics スキャン統計なるものがあるらしく、それに対する良い感じの手法 Sensitivity of Community Structure to Network Uncertainty Subnetwork Mining with Spatial and Temporal Smoothness...
• 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する 予備知識みたいな...
• 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...
• 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...
• 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...
• 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という速いアルゴリズムを提案 実験して提案手法とベースラインを比較 モデル・問...
• 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とセットする...
• Maximizing Influence in a Competitive Social Network: A Follower's Perspective
  Maximizing Influence in a Competitive Social Network A Follower s Perspective Tim Carnes, Chandrashekhar Nagarajan, Stefan M. Wild, Anke van Zuylen ICEC 2007 概要 既に敵対するカスケードが広がっている時に，自分はどうシード集合を選択するか 2つのモデルを提案 NP-hardだけど1-1/e近似可能 モデル Aが自分で，Bが敵 I_B すでにBのシード集合 σ(I_A | I_B)が最大となるI_Aを選びたい ベースはICモデルと同じランダムグラフを考える E_a 残った辺 カスケードの仕...
• Learning Influence Probabilities In Social Networks
  Learning Influence Probabilities In Social Networks Amit Goyal, Francesco Bonchi, Laks V.S. Lakshmanan WSDM 2010 概要 情報拡散の確率を学習したい 色々モデル提案 アクティブになる時刻も推定できるよ 問題定義 辺が作成されたタイムスタンプの考える (u, a, t_u)が一杯もらえる u ユーザー a 行動 t_u 時刻 (u,v)について，u,vの順に行動して，辺の作成時刻に矛盾が無ければ，uからvに伝搬した 各行動について，↑でありうる辺を取ってきた時の伝播グラフを考える 枠組み？ uの近傍のアクティブ...
• 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_...
• 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で...
• Cost-effective Outbreak Detection in Networks
  Cost-effective Outbreak Detection in Networks Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, Natalie Glance KDD 2007 概要 outbreak detection問題を考える 色々あるけど目的関数はsubmodularになるのが多い 貪欲アルゴリズムで近似だ！ しかもsubmodularityを活かした高速化手法+online boundも考案 安定のLeskovecといったところか Outbreak detection モチベーション グラフ上でのカスケードを検知したい！ 水質汚染 ...
• 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...
• Influence and Correlation in Social Networks
  Influence and Correlation in Social Networks Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian KDD 2008 概要 社会的な繋がりは大事ですよ 相関（似た行動）を引き起こすのは、「社会影響」の所為？ 同類性とか他の色々な要素があって紛らわしい 単純なテストを考案 Flickrで調べたら、相関はあるけど影響の所為ではない 導入とか 既存研究「Flickrで友達同士のタグの語彙が似ている」 相関の源は？ influence 友達の最近の行動に引き起こされる homophily 同じゲームを持っている人は友達になりやすい e...
• Fast Influence-based Coarsening for Large Networks
  Fast Influence-based Coarsening for Large Networks Manish Purohit, B. Aditya Prakash, Chanhyun Kang, Yao Zhang, V.S. Subrahmanian KDD 2014 概要 情報拡散の特徴を保ったままグラフを小さくしたい，近似したい 頂点対を「縮約」 アイデア：ほとんどの辺は無意味 問題を定式化 スコア付けがGOODで，ほぼ線形時間 90%削減も（頂点数を） 問題定義 入力 G=(V,E,w)，α 出力 H=(V ,E ,w ) |V |=(1-α)|V| HはGを伝播の特徴の意味で近似する 今回使う特徴 ...
• 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) ...
• Influence maximization in complex networks through optimal percolation
  Influence maximization in complex networks through optimal percolation Flaviano Morone, Hernán A. Makse Nature 2015 概要 頂点を削除して最大の連結成分を最小化したい 強影響力頂点抽出，immunization，コミュニティ検出 既存手法…ヒューリスティクス 本手法 最適化問題 ある種の貪欲アルゴリズム 輪郭 最適パーコレーション 固有値の最小化問題 上を解く 最適パーコレーション $$ \nu_i $$の計算
• 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}...
• 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...
• メニュー
  メニュー トップページ 論文一覧 気になった論文 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...
• Heat Kernel Based Community Detection
  Heat Kernel Based Community Detection Kyle Kloster, David F. Gleich KDD 2014 概要 頂点を含むコミュニティを定数時間で出力 熱方程式をシミュレート PageRankを使ったPushアルゴリズムを熱核にしたよ 熱核 熱方程式に対する基本解 拡散過程によるコミュニティ抽出 良いコミュニティ≒コンダクタンスが小さい 種の頂点から遷移行列に従い拡散 定常分布になる前に止めないと駄目 ⇨スコアベクトルf 各ステップkでの重みに適当な重み付けc_kをする ↑が大きい頂点を順にコミュニティに追加 追加していく途中で一番良い物を出力 熱核とPageRankの関係 ...
• 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...
• 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...
• 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 ...
• 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は感染しない 手法 σが小さくなるノードを貪欲に選んでいく 実験 比較...
• 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がアクテ...
• 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)) つまり，遅延時間の分布が指数関数 他の関数でも使える 情報拡散過程は普通 ...
• 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モデルでの応用 先...
• 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 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とす...
• Maximizing the Long-term Integral Influence in Social Networks Under the ...
  Maximizing the Long-term Integral Influence in Social Networks Under the Voter Model Chuan Zhou, Peng Zhang, Wenyu Zang, Li Guo WWW 2014 companion ポスター 概要 Voter Modelにおける影響最大化 long-term integralを最大化したい 問題+提案手法 モデルはInfluence Diffusion Dynamics and Influence Maximization in Social Networks ... long-term integral influence maximization σ(S) = E[...
• 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について↓で...
• On minimizing budget and time in influence propagation over social networks
  On minimizing budget and time in influence propagation over social networks Amit Goyal, Francesco Bonchi, Laks V. S. Lakshmanan Social Network Analysis and Mining (SNAM) 2012 MINTSS (minimum target set selection) 入力 閾値η 出力 σ(S)≧ηなる最小サイズのS 提案手法 貪欲算法 σ(S)＜η-εの間，増量（min{σ(S+t),η}で考える）が最大の頂点をSに追加 定理1 貪欲算法で双基準近似 σ(S)≧η-ε |S|≦(1+ln(n/ε))OPT 関...
• Learnability of Influence in Networks
  Learnability of Influence in Networks Harikrishna Narasimhan, David C. Parkes, Yaron Singer NIPS 2015 概要だけ 様々な拡散モデルのPAC学習性 辺のパラメータそのものより、影響関数値の方が大事 Linear threshold 多層NN分類器っぽみ、VC次元 部分観測×、完全観測○ Independent cascade Covering numberで考えられる 完全観測○ Voter 線形回帰に帰着 部分観測○、完全観測○ 推定したいもの 影響関数$$ F 2^V \to [0,1]^n $$ シード集合に対して、各頂点...
• 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)$$、予算$...
• Threshold Models for Competitive Influence in Social Networks
  Threshold Models for Competitive Influence in Social Networks Allan Borodin, Yuval Filmus, Joel Oren WINE 2010 久しぶりの論文記事(ヽ´ω`) 概要 LTモデルを競合者付きモデルに拡張 劣モジュラどころか単調ですらないものもある Weight-Proportional Competitive Linear Threshold Model 頂点vはしきい値θ_vを持つ 活性近傍からの重みの和がθ_vになったら活性化 状態は3つ 非活性，活性A，活性B 活性Aの近傍の割合 活性Bの近傍の割合で確率的にAかBかに決まる S_B=∅なら元のLTモデルと同じ ...
• Overlapping Community Detection Using Seed Set Expansion
  Overlapping Community Detection Using Seed Set Expansion Joyce Jiyoung Whang, David F. Gleich, Inderjit S. Dhillon CIKM 2013 概要 コンダクタンスがいい感じになる重複コミュニティ検出手法を提案 提案手法 目標 全体をカバーしつつ、最大のコンダクタンスを小さくしたい Filtering whiskerを取り除きたいので、以下のような分解をする core=（ざっくりいうと）最大の2点連結成分 bridge=橋 whisker=残り Seeding 色々な手法でクラスタ中心を決める Graclus centers, Spr...
• Sampling Community Structure
  Sampling Community Structure Arun S. Maiya, Tanya Y. Berger-Wolf WWW 2010 概要 expander graphのコンセプトによるコミュニティのサンプリング手法 コミュニティ検出で推論っぽいこと？もできるらしい 問題 X(S) = |N(S)|/|S| 隣接頂点数/頂点数 サイズkのサンプルSがcommunity representative sample minimize D[P_S(G(S)), P_S(G)] D[,]は分割に対する距離尺度 P_S(G)はGを使って作られた分割 手法 X(S)の最小化もあるけれどそうではなくて、最大のサンプルを見つ...
• UBLF: An Upper Bound Based Approach to Discover Influential Nodes in Social ...
  UBLF An Upper Bound Based Approach to Discover Influential Nodes in Social Networks Chuan Zhou, Peng Zhang, Jing Guo, Xingquan Zhu, Li Guo ICDM 2013 概要 CELFは最初のiterationが遅い！ もうちょっとだけ早くするんじゃ 大まかな見積もりを行列計算でやる タイトかは分からんが正しい上界が出る 上界順にMonte-Carloして、それが最上位って分かったら抜ける シミュレーション数95%カット 速度は2~5倍(´・ω・`) 提案手法 上界の見積もり方 Pr_{S,t}[v] Sが時刻tにvをactivat...
• The Importance of Communities for Learning to Influence
  The Importance of Communities for Learning to Influence Eric Balkanski, Nicole Immorlica, Yaron Singer NIPS 2017 概要 The Power of Optimization from Samplesはcurvature制限時だった 今回は影響最大化をコミュニティ構造が明らかな場合、OPSの枠組みでなんとかするよ コミュニティの大きさを捉えられそうなアルゴリズムを提案 SBMの簡単な設定で近似比を証明 アルゴリズム COmmunity Pruning from Samples 設定 無向なので、基本的に連結成分の大きさ（の和）の期待値が影響力になる underlyingな...
• Assessing Attack Vulnerability in Networks with Uncertainty
  Assessing Attack Vulnerability in Networks with Uncertainty Thang N. Dinh, My T. Thai INFOCOM 2015 概要 ネットワーク脆弱性を「期待対連結性」で評価したい 「k頂点消すと期待対連結性はどれ位下がるか？」という離散最適化問題 提案手法は、LPによる緩和＋交換ヒューリスティクス 期待対連結性のFPRASを提案 期待対連結性 脆弱性の色々な尺度 最短経路長、代数的連結性、連結成分数・サイズ…はあまり良くない 対連結性 (pairwise connectivity)は結構良いらしい 致命的頂点検出問題 (critical node detection; CND) 普通...
• 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...
• 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以下って制約とか...
• 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)で求めている？ 何でこんなことをしたのか若干謎
• 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(ε)...
• 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)に従う 平均α/(α+β) 拡散の履歴から各α，βをインクリメントするだ...
• 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...
• 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 サイズが大きくなる...
• @wiki全体から「Influence-based Network-oblivious Community Detection」で調べる

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