todo314 @ ウィキ
todo314 @ ウィキ

Extracting Analyzing and Visualizing Triangle K-Core Motifs within Networks

todo314 @ ウィキ内検索 / 「Extracting Analyzing and Visualizing Triangle K-Core Motifs within Networks」で検索した結果

検索 :
  • Extracting Analyzing and Visualizing Triangle K-Core Motifs within Networks
    Extracting Analyzing and Visualizing Triangle K-Core Motifs within Networks Yang Zhang, Srinivasan Parthasarathy ICDE 2012 概要 Triangle K-Core なる密グラフの概念を提案 かなり速く抽出できる しかも動的更新もできる template pattern cliquesをサポート 可視化とかイベント検出とか Triangle K-Core 部分グラフG がTriangle K-Core G 内の各辺がk個以上の三角形に含まれている 辺eのMaximum Triangle K-Core eを含む部分グラフG_eでTri...
  • 論文一覧
    ... 2014 Extracting Influential Nodes for Information Diffusion on a Social Network AAAI 2007 IMGPU GPU-Accelerated Influence Maximization in Large-Scale Social Networks TPDS 2014 Influence Maximization in Big Networks An Incremental Algorithm for ... IJCAI 2015 Influence at Scale Distributed Computation of Complex Contagion in Networks KDD 2015 Outward Influence and Cascade...
  • 気になった論文
    ...d Extracting and Analyzing Hidden Graphs from Relational Databases 関係データベースから*隠れた*グラフを抽出するとメモリとか時間とかが辛い いい感じに扱うよ！ ✔BePI Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart 高速、メモリ効率、スケーラブルな手法 前処理時間が100倍高速、クエリ時間が7倍高速 Landmark indexing for scalable evaluation of label-constrained reachability queries Lucien Valstar, George H. L. ...
  • 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...
  • 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 $$ でかい...
  • 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...
  • 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 関...
  • 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...
  • 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 スパム同士は結合...
  • メニュー
    メニュー トップページ 論文一覧 気になった論文 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...
  • 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に適用 完全なひと月のデータ 情報がネットワークをジャンプしている ...
  • 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...
  • Efficiently Anonymizing Social Networks with Reachability Preservation
    Efficiently Anonymizing Social Networks with Reachability Preservation Xiangyu Liu, Bin Wang, Xiaochun Yang CIKM 2013 概要 匿名化の話 Kleinbergのに考え方は似てる 目標 個人情報を隠しつつ、なんかのクエリ=到達可能性を処理する k-degree anonymous 敵がvを次数情報のみから頂点を特定できる確率は1/k以下 有向グラフだけど、in-degとout-degがそれぞれ等しい頂点はk個以上 Reachability Preserving Anonymization 問題設定 入力 G=(V,E), 整数k ...
  • Human Wayfinding in Information Networks
    Human Wayfinding in Information Networks Robert West, Jure Leskovec Stanford univ. In WWW 2012 概要 クリックの列に関する大量のデータを解析 人間をどうナビゲートするか？ Wikispedia Game スタートとゴールが与えられるので、wikipediaだけ辿ってゴールを目指す リストとかの汎用的なページは確か見れない 人間の探索能力 ヒストグラムを見てみる shortest paths small-world human, effective human, incl. back-clicks human, drop-ou...
  • 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を...
  • Maximizing Influence in an Ising Network: A Mean-Field Optimal Solution
    Maximizing Influence in an Ising Network A Mean-Field Optimal Solution Christopher W. Lynn, Daniel D. Lee NIPS 2016 概要 Isingモデル上の影響最大化 意見＝スピン、外部影響＝外部磁場、影響力＝J 相互作用の反復による意見の「平衡」状態 平均場近似で解く 外部磁場に対して滑らかかつ凹になる十分条件 平均場の安定非負定常分布の存在に関する条件 実験もしたよ 問題定式化 Ising influence maximization $$ \Pr[\sigma_i(t+1) \mid \sigma(t)] = \frac{\exp\Bigl( \...
  • Trial and Error in Influential Social Networks
    Trial and Error in Influential Social Networks Xiaohui Bei, Ning Chen, Liyu Dou, Xiangru Huang, Ruixin Qiang KDD 2013 概要だけ 情報拡散に「試行錯誤」を導入 aを選んでいたとする; 確率p bを試行 良かったら bを選択 悪かったら aを維持 確率1-p aの維持 Nash均衡がどうとか言っている 局所的な相互作用の結果が大域的なコミュニティの検出とかに使える 同じコミュニティだったら同じ選択になりそうなので Louvain法より良いらしい 影響最大化にも使える 色々やっているなあという感想 KDD ...
  • Minimizing Seed Set Selection with Probabilistic Coverage Guarantee in a ...
    Minimizing Seed Set Selection with Probabilistic Coverage Guarantee in a Social Network Peng Zhang, Wei Chen, Xiaoming Sun, Yajun Wang, Jialin Zhang KDD 2014 概要 大きいカスケードが「起こりやすい」ようにシードを選びたい 期待値の代わりに確率を議論するのがミソ この問題は劣モジュラでない 色々解析 動機付け トピックがある閾値まで広まって欲しい tipping point 当然シードセットは小さくしたい しかも確率保証つきで 問題定義 独立カスケードモデル Seed Mini...
  • 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 $...
  • 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して木っぽくパスを広げる（同じ頂点がいくつかある...
  • Make It or Break It: Manipulating Robustness in Large Networks
    Make It or Break It Manipulating Robustness in Large Networks Hau Chan, Leman Akoglu, Hanghang Tong SDM 2014 yamaguchiyutoさんのまとめ http //yamaguchiyuto.hatenablog.com/entry/2014/05/04/120705 概要 グラフの頑健性の研究 測定する 追跡する 操作する 比較する 色々な尺度 最大の連結成分の大きさ 逆最短経路長 代数的連結性 (algebraic connectivity) 理想は完全グラフ O(n^2)は現実的に無理 応用...
  • 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になるけどいいや 色々推定 ※μは公開するとして良い 密度 μが分かるので、て...
  • 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_...
  • 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) ...
  • 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 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 ...
  • A practical bounding algorithm for computing two-terminal reliability based ...
    A practical bounding algorithm for computing two-terminal reliability based on decomposition technique Yi-feng Niu, Fang-Ming Shao Computers and Mathematics with Applications 2011 概要 2端子信頼性計算のアルゴリズム 実験なし （某イベントで知った） 提案手法 C 事象の集合 事象=各辺の状態 A1(C) Cでの状態が生の辺集合 A2(C) Cでの状態が死の辺集合 A1(C)がs-t経路を構成→必ず到達可能 A2(C)がs-tカットを構成→必ず到達不可能 良く分から...
  • Computing and maximizing influence in linear threshold and triggering models
    Computing and maximizing influence in linear threshold and triggering models Justin T. Khim, Varun Jog, Po-Ling Loh NIPS 2016 概要 影響拡散の上下限を新たに作ったよ！ LTモデルとTriggeringモデル 下限は単調劣モジュラなので、最大化できて良い解になる 主結果 LTモデル 上限 $$ \leq |A| + \mathbf{b}_{\bar{A}}^\top (\mathbf{I}-\mathbf{B}_{\bar{A}\bar{A}})^{-1} \mathbf{1}_{\bar{A}} $$ An Upper Bound based Greed...
  • 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が高い 解釈 情報発信能力と情報収集能力が共に高い頂点が多いと情報拡散能力の高いグラフ...
  • 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 ...
  • Extrapolation Methods for Accelerating PageRank Computations
    Extrapolation Methods for Accelerating PageRank Computations Sepandar D. Kamvar, Taher H. Haveliwala, Christopher D. Manning, Gene H. Golub WWW 2003 概要 PageRankのためのPower methodの高速化 25--300%速くなった メモ：イントロで… Dangling nodesからは一様に飛ぶとしている Aitken Extrapolation $$ x^{(k-2)} $$が上位2つの固有ベクトルの線形結合で表せるとする $$ x^{(k-2)}, x^{(k-1)}, x^{(k)} $$を使って$u_1$を求めたい！...
  • Triangle-Based Representative Possible Worlds of Uncertain Graphs
    ...le 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)| $$を最小化せよ t(v) vを含む△の個数／平均個数 各△の出現確率を足し合わせればOK 提案手法 初期グラフを作る 大体平均辺数まで適当にサンプリング 目的関数値を減らすように努力する 辺取替で良くなる場合 辺挿入で良くなる場合 それぞれ目的関数値の更新がそこそこ速い 実験 ...
  • Is Nearly-linear the Same in Theory and Practice? A Case Study with a ...
    Is Nearly-linear the Same in Theory and Practice? A Case Study with a Combinatorial Laplacian Solver Daniel Hoske, Dimitar Lukarski, Henning Meyerhenke, Michael Wegner SEA 2015 概要 A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Timeを実装してみました！ ほぼ線形時間の計算量だけど、定数が大きすぎて、全然遅いよ！残念！ low stretch保証のある手法よりも、単純な全域木のほうが良かったりしたよ！ 準備 基本的なソルバの...
  • Co-clustering documents and words using Bipartite Spectral Graph Partitioning
    Co-clustering documents and words using Bipartite Spectral Graph Partitioning Inderjit S. Dhillon KDD 2001 概要 文書と単語の共クラスタリング カット最小化として妥当な問題設定 スペクトラルグラフ理論の知見から固有ベクトル計算問題として緩和 後はk-meansすると大体上手い 問題設定 $$ G=({\cal D}, {\cal W}, E) $$ 文書と単語の二部グラフ 辺重みが謎… 単語・文書クラスタリングの関係 文書のクラスタが与えられた時、各単語は{最も重み和の大きい文書クラスタ}に対応する単語クラスタに属すると考える というわけで、k...
  • TwitterRank: Finding Topic-sensitive Influential Twitterers
    TwitterRank Finding Topic-sensitive Influential Twitterers Jianshu Weng, Ee-Peng Lim, Jing Jiang, Qi He WSDM 2010 ビデオ見て書いてみたよ http //videolectures.net/wsdm2010_weng_trft/ 概要 トピックを指定して影響力の高い頂点を見つけたい 応用 leaderの特定 マーケティング、広告 難しいところ ユーザ同士の関係がnon-serious トピックが分からん ground truthとは…？ データ シンガポールに限って 1000人位 割りと疎...
  • Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in ...
    Stop-and-Stare Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks Hung T. Nguyen, My T. Thai, Thang N. Dinh SIGMOD 2016 概要 TIM+やIMMより速い影響最大化アルゴリズムを作りました RR集合のサンプル数が最小だよ！ 枠組み 2つの条件 $$ \Pr[\widehat{\mathsf{Inf}}(S_k) \leq (1+\epsilon_a)\mathsf{Inf}(S_k)] \geq 1-\delta_a $$ $$ \Pr[\widehat{\mathsf{Inf}}(S_k^*) \geq (1+\epsilon_b)...
  • Social Influence Spectrum with Guarantees: Computing More in Less Time
    Social Influence Spectrum with Guarantees Computing More in Less Time Dinh, Thang and Nguyen, Hung and Ghosh, Preetam and Mayo, Michael CSoNet 2015 概要 新しいアルゴリズムLISA $$k=1,\ldots,n$$について同時に解けるよ！ $$ O(\epsilon^{-2}\ln \frac{2}{\delta} (n+m)) $$時間だよ！ 提案手法 Linear-time Influence Spectrum Algorithm (LISA) 終了条件が重要 $$ \Upsilon_L = 1+4.6\epsilon^{-2}...
  • 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 ...
  • On Integrating Network and Community Discovery
    On Integrating Network and Community Discovery Jialu Liu, Charu Aggarwal, Jiawei Han WSDM 2015 概要だけ グラフの全体を得るのは難しい，サイズ・個人情報 で，少しずつグラフを統合？拡大させながらコミュニティ検出をしたい どうやって拡大するかがコミュニティ検出手法以上に重要 今あるグラフについてコミュニティ検出 ↓↑ どの頂点を新たに見るか選ぶ 実験では色々試す，ground truthはよく分からん… WSDM コミュニティ検出 2015/02/23 19 27
  • 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_...
  • Inferring Networks of Diffusion and Influence
    Inferring Networks of Diffusion and Influence Manuel Gomez-Rodriguez, Jure Leskovec, Andreas Krause In KDD 2010 よしださん 概要 ネットワークは明示的に得られない 薬物乱用者の注射針共有ネットワーク 分かるのは現象、結果だけ 結果からネットワークを推定できる？ 結果 O(n^2)時間でできる グラフの候補は2^n*n通り 拡散モデル 伝播時間 P(Δ)∝exp(Δ/α) or 1/Δ^α u- v の伝播の尤度を設定 外部からの伝播もあり 特定のカスケードに対して有向木Tの尤度を各辺について掛け合わせる ...
  • 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)だけど実験的にはもう少し速い（し精度も良い） 動機付けとか リバーネットワーク(?)の階層的構造を木構造で表現 その応...
  • 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 Maximization in Big Networks: An Incremental Algorithm for ...
    Influence Maximization in Big Networks An Incremental Algorithm for Streaming Subgraph Influence Spread Estimation Weixue Lu, Peng Zhang, Chuan Zhou, Chun-Yi Liu, Li Gao IJCAI 2015 概要 小さい部分グラフに分割する 頂点を共有しうるが辺は互いに素 挑戦 部分グラフ間のシミュレーションが重なる 提案手法 M=シミュレーション回数 N=分割個数 $$ (V_i)_i $$ Vの被覆 $$ (E_i)_i $$ Eの分割 X_r = コインフリッピング結果rを表す01値ベクトル ...
  • 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...
  • 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...
  • 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 サイズが大きくなる...
  • 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は感染しない 手法 σが小さくなるノードを貪欲に選んでいく 実験 比較...
  • 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以下って制約とか...
  • Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph ...
    Path Sampling A Fast and Provable Method 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)は簡単な線形関係に...
  • @wiki全体から「Extracting Analyzing and Visualizing Triangle K-Core Motifs within Networks」で調べる

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