論文一覧

参考

サーベイ一覧

videolectures

情報拡散 とか

投票者モデル

  • A model for spatial conflict
    • Biometrika 1973
  • Ergodic theorems for weakly interacting infinite systems and the voter model
    • Annals of Probability 1975.

Influence Maximization 関連

  • 会議別にもまとめてある
  • いくつかのトピックにかぶっているのもある

バイラルマーケティング

元ネタ

  • Maximizing the Spread of Influence through a Social Network

理論的結果

高速アルゴリズム

変種モデル

問題が違う

疎化・粗大化

影響拡散高速計算

予測

モデリング

時間

トピック・カテゴリ

負/競合

投票者モデル

その他

連続時間独立カスケード(CT-IC)モデル

汚染最小化

動的グラフ

斉藤 和巳さん一派

Uncertain Graphs

ネットワーク信頼性

OR系

クリーク

KKKKKKKKKKKKKKKKKKKKKK

k-means

PageRank 関連

高速計算

動的更新

バックボタン

AAAI 2007

AAAI 2008

AAAI 2010

AAAI 2011

AAAI 2012

AAAI 2013

AAAI 2014

AAAI 2015

AAMAS 2015

ACL 2013

ALENEX 2016

ASONAM 2009

ASONAM 2011

ASONAM 2012

ASONAM 2014

  • Diversified Social Influence Maximization
  • "Can you really trust that seed?": Reducing the Impact of Seed Noise in Personalized PageRank
    • PPRはシードが不安定だとランキングがおかしくなる
    • ちょっと辺でも大丈夫な頑健版を作ったよ

CHI 2010

  • ✔Signed Networks in Social Media
    • 正負の関係がどうソーシャルネットワークの構造に影響するのか
    • 社会心理学との関連付け
    • 大事そう

CIKM 2003

  • ✔The Link Prediction Problem for Social Networks
    • リンク予測問題の先駆け

CIKM 2008

CIKM 2009

CIKM 2011

  • Suggesting Ghost Edges for a Smaller World
  • User browsing behavior-driven web crawling
    • リンク構造からページの重要性を測ったりするね
    • 重要性をユーザの興味とブラウザログから直接測るよ
    • クロールも同時?にする
  • ✔Local computation of PageRank: the ranking side
    • n頂点グラフからk頂点のPageRankを知りたい
      • CIKM 2004, 2008で出てた
    • $$ \Omega(\sqrt{kn}) $$頂点は見ないとだめぽ
  • Coupling or decoupling for KNN search on road networks?: a hybrid framework on user query patterns
    • 道路ネットワーク上の空間オブジェクトの検索
    • 今までグラフの走査とオブジェクトのルックアップを分けてやってたが重い(?)
  • Discovering top-k teams of experts with/without a leader in social networks
    • まとめると必要なスキルが揃って,通信コストが最小
    • 通信コストを色々定義
    • NP-hardだけど2近似
  • Probabilistic near-duplicate detection using simhash
    • simhash(Charikar)
    • simhashたちのHamming空間で探索する手法(の考案?)
  • Link prediction: the power of maximal entropy random walk
    • リンク予測にRandomWalkがよく使われる
    • ただ頂点の中心性のようなものは無視
    • 極大Entropyで(?)hitting timeとかcommute timeとか
    • あとグラフカーネルと類似尺度
  • Exploiting longer cycles for link prediction in signed networks
    • 符号付きなので,不均衡とかそういうのでリンク予測に使うよ
    • 教室付き機械学習で長い閉路を使う(謎)
  • Determining the diameter of small world networks
    • デカイグラフの直径が欲しいよお
    • 下界/上界,頂点選択・枝刈り手法で大事なとこだけ
    • |E|<24M
  • Distributed social graph embedding
    • 推薦
    • グラフをd次元空間に埋め込む
      • コミュニティを取りたい
  • Finding information nebula over large networks
    • nebula = 星雲
    • ユーザのクエリに関連するtop-k キーワード項
  • Efficient methods for finding influential locations with adaptive grids
    • サーバーとクライアントがもらえる
    • 新しいサーバーをどこに於けばいいか?
    • クライアントが必ず最近のサーバーに行くと思ったら大間違いだぜへっへっへ!
    • ↑を緩和した問題を提案
    • めっちゃ早い近似アルゴリズムを作った
  • Answering label-constraint reachability in large graphs
    • そのまんま
  • High efficiency and quality: large graphs matching
    • 最大共通部分グラフマッチング…NP-hard
    • 厳密は遅く,近似はしょぼいので,いい感じのを作った
  • Skynets: searching for minimum trees in graphs with incomparable edge weights
    • 辺の重みが範囲…なので半順序
    • 代わりの比較演算子を考案
  • Fast fully dynamic landmark-based estimation of shortest path distances in very large graphs
    • landmarkベース
    • 最短路木をもって,辺の挿入・削除に対応
    • 最短路を被覆したい
  • Selecting related terms in query-logs using two-stage SimRank
    • クエリからクリックしたページが同じなら2つのクエリが似てるとかんがえる
    • SimRankとクラスタリング手法を使ってクエリ間の類似度を図るよ
    • ちゃんと何かしらの意味で精度が上がったらしい
  • Top-k most influential locations selection
    • 施設配置選択クエリ
    • 候補からtop-kで影響のある施設をとる
      • 影響(定義はあるらしい)
    • 厳密は辛いので近似する

CIKM 2012

  • Delineating Social Network Data Anonymization via Random Edge Perturbation
  • Gelling, and Melting, Large Graphs by Edge Manipulation
    • best paper
    • これまでは頂点を消したりワクチン接種とかで拡散を抑えることを考えてた
    • 辺を考える:どの辺を削除/追加すれば加速or減速する?
    • 理論的にも,実験でも色々と調べます
  • Graph classification: a diversified discriminative feature selection approach
    • 特徴選択と分類
      • 分類はふつうの手法使えばいいので,特徴選択に注目
    • 以前のの欠点があるので,新しいのを提案
  • Multi-scale link prediction
    • 類似度(?)の計算が激重
    • 低ランク近似…単一だけだと心もとないので,一杯
  • Density index and proximity search in large graphs
    • 頂点にラベル…クエリに対してよさそな頂点集合が欲しい
    • クエリをカバーし直径最小のをとってくる
  • Efficient algorithms for generalized subgraph query processing
    • 辺を経路にマップするクエリ(?)
  • G-SPARQL: a hybrid engine for querying large attributed graphs
    • SPARQLっぽい言語
  • Utilizing common substructures to speedup tensor factorization for mining dynamic graphs
  • Predicting emerging social conventions in online social networks
    • 集会の予測 Twitterで
    • 採択の日と露出(exposures)の数が重要
      • 個々の特徴,友達の内の採択数はそんなに大事じゃない
  • Influence propagation in adversarial setting: how to defeat competition with least amount of investment
    • 競合者あり
      • 他のにスイッチしない
    • 既に拡散が始まっている,そこから新たに自分のを流す
  • Scalable clustering of signed networks using balance normalized cut
    • 符号付きグラフのLaplacianはすでにある
    • 欠点があるらしい
    • normalized cutっぽいのを提案
    • 実験的には良い
    • 重み付きカーネルk-meansと同じ(?)
  • Pay-as-you-go maintenance of precomputed nearest neighbors in large graphs
    • 最近傍のリストを各頂点について持つ
    • 頂点追加/辺重み減少をサポート
  • Spatial influence vs. community influence: modeling the global spread of social media
    • 情報が地球上の位置的にどう広がる?
    • 下の過程を取り入れたモデル
      1. 空間的なモデル:近い所に伝わる
      2. コミュニティ類似:離れてても(文化的に)繋がってればOK
  • Evaluating geo-social influence in location-based social networks
    • geoとsocialの意味での類似度を図る指標
      • penalized hitting time
      • 地理学的な重み関数
    • ユーザーの影響力を測るアルゴリズム
  • Influence and similarity on heterogeneous networks
  • GRAFT: an approximate graphlet counting algorithm for large graph analysis
    • graphletの頻度分布が知りたい
    • 5頂点以下なら全部数え上げるよ
    • 10~100倍で5%以下
  • Fast approximation of steiner trees in large graphs
    • landmarkベースの索引構造でSteiner tree
  • Shaping communities out of triangles
    • 新しいコミュニティの尺度(WCC)
    • 構造と結合の意味である以上の最小の集合
  • Degree relations of triangles in real-world networks and graph models
    • △と次数の関係
    • ソーシャルや共同:△の次数は似てる
    • Web(情報):△の次数はかなり違う
    • 次数がtop 1%の頂点はかなりの△に所属してた
  • Finding the optimal path over multi-cost graphs
    • multi-costで最短路
    • 最良優先,分枝限定法
    • 索引も
  • On bundle configuration for viral marketing in social networks
    • いくつかのアイテムをまとめる設定の問題
    • Bundle Configuration for SpreAd Maximization
  • On compressing weighted time-evolving graphs
    • 動的グラフを圧縮したいよ
    • テンソル…
      • なんだかよく分からん
  • Tracing clusters in evolving graphs with node attributes
    • そのまま
  • Prediction of retweet cascade size over time
    • ある期間でTweetがどのくらい伸びるのか
    • 普通の特徴量+色々
    • カスケードの流れ(?)とリツイートグラフでのPageRank
  • Bridging offline and online social graph dynamics
    • LinkedInのデータで,オフラインでのイベントがオンラインネットワークに及ぼす影響
    • あとリンク予測
  • Continuous top-k query for graph streams
    • そのままっぽい

CIKM 2013

CIKM 2014

CIKM 2015

COSN 2013

CSoNet 2015

CVPR 2014

  • Spectral Graph Reduction for Efficient Image and Streaming Video Segmentation
    • superpixelでグラフを小さくして画像分割とかを効率化

ECML PKDD 2010

ECML PKDD 2012

ECML PKDD 2015

  • Fast Inbound Top-K Query for Random Walk with Restart
  • Finding Dense Subgraphs in Relational Graphs
  • Clustering Boolean tensors

EDBT 2012

  • Limiting link disclosure in social network analysis through subgraph-wise perturbation
    • リンク関係の暴露はプライバシー侵害
    • 既存は適当にかき混ぜる→構造的性質が乱される
    • 有向グラフで行き先だけ変える
    • subgraph-wise perturbation(部分グラフに分割してそれ毎に変える)
  • Shortest-path queries for complex networks: exploiting low tree-width outside the core
    • 最短路クエリ
    • 小木幅部分と複雑ネットワーク部分クラス
  • Finding top-k similar graphs in graph databases
    • クエリグラフに近いtop-kのグラフを探す
    • 新しい類似指標 MCS (maximal common subgraph)
    • インデクシングもする
  • I/O cost minimization: reachability queries processing over massive graphs
    • メモリに入らないグラフでの到達可能性クエリでI/Oを小さくしたい
    • 分割手法も
  • Finding maximal k-edge-connected subgraphs from a large graph
    • 極大k枝連結部分グラフを見つける
    • 頂点縮小/辺縮小/カット枝刈り

EDBT 2013

EDBT 2014

  • Online Topic-aware Influence Maximization Queries
  • Privacy Preserving Estimation of Social Influence
  • Reachability Queries in Very Large Graphs: A Fast Refined Online Search Approach
    • 到達可能性クエリの索引手法
    • 2次元平面上の表現(?)
  • Distance oracles in edge-labeled graphs
    • Francesco Bonchi
    • 使える辺ラベルが指定されての最短距離の索引手法
  • Graph Analytics on Massive Collections of Small Graphs
  • ✔Fast Reliability Search in Uncertain Graphs
    • Francesco Bonchi
    • 信頼性=2頂点が連結の確率
    • クエリ頂点からある確率以上で到達可能な頂点集合が欲しい
    • GOODな索引を作るよ
    • 前の奴に似たテク?
  • CLUDE: An Efficient Algorithm for LU Decomposition Over a Sequence of Evolving Graphs
    • 動的グラフの(隣接)行列をLU分解
    • クラスタの力
  • Spatial Partitioning of Large Urban Road Networks
    • 空間的な都市道路ネットワークの分割
    • スペクトラルグラフ理論なグラフカットを使って分割,とか
  • Efficient Skyline Computation in MapReduce
    • スカイラインは大事だよ
    • でも並列してないね
    • MapReduce!!
    • でーたの空間を分割
  • L-opacity: Linkage-Aware Graph Anonymization
    • L-opacityはモデルのことらしい
  • Privacy Risk in Anonymized Heterogeneous Information Networks
  • Diversified Spatial Keyword Search On Road Networks
    • 位置に例えばレストランなら店名とか食べ物とかの内容
    • 関連があって空間的に雑多なやつをクエリとして答える
  • Distributed Spatial Keyword Querying on Road Networks
  • Cost-Based Median Query Processing in Wireless Sensor Networks
    • エネルギー消費を減らして長生きしたい
    • メディアン
    • 元からある奴を連続な奴に拡張

EDBT 2015

  • Hermes: Dynamic Partitioning for Distributed Social Network Graph Databases
    • グラフの動的分割
    • ハッシュベースの分割手法の2~3倍
  • Learning Path Queries on Graph Databases
    • ユーザが頂点を正or負にラベル付したグラフ
    • ユーザの予期したクエリを見つける(?)
  • TimeReach: Historical Reachability Queries on Evolving Graphs
    • historicalな到達可能性クエリ
    • でかいSCCを活用
  • ✔ Efficiently Computing Top-K Shortest Path Join
    • 頂点集合S,Tがある
    • SからTの最短経路のtop-k
    • 最良優先的
    • 探索空間をイイ感じに分割
    • top-kより早くなりうるのをだけ
  • SIEF: Efficiently Answering Distance Queries for Failure Prone Graphs
    • 動的なグラフ…辺が「消える」
  • A Selectivity based approach to Continuous Pattern Detection in Streaming Graphs
    • ストリームグラフ上の部分グラフマッチング
    • 応用:cyber attackの検知(?)
  • Identifying Converging Pairs of Nodes on a Budget
    • ある2つの時刻でのグラフのスナップショットがもらえる
    • どの頂点対間の最短経路が最も減少したか
    • 単一始点最短経路の計算数に制限を与えた元で

FOCS 2006

  • ✔Local Graph Partitioning using PageRank Vectors
    • 特定の頂点に近い(含む)カットを劣線形時間で求めたい
    • PPR(のようなもの)を使う
    • コンダクタンスが$$\Omega(\phi^2 / \log m)$$のカットが存在する場合,コンダクタンス$$\phi$$のカットを見つけられる

FOCS 2009

  • ✔Faster Generation of Random Spanning Trees
    • 全域木の無作為標本したい
    • 分布がちょっとずれても良いとする
    • 疎グラフでの最悪時が改善された

FOCS 2013

ICDE 2010

ICDE 2011

ICDE 2012

ICDE 2013

ICDE 2014

  • How to Partition a Billion-Node Graph
  • Random-walk Domination in Large Graphs
  • Evaluating Multi-Way Joins over Discounted Hitting Time
  • A General Algorithm for Subtree Similarity-Search
    • クエリ木Qと木の集合Γに対してQに最も似ている部分木を見つける
    • 類似度はtree distanceで定義
    • 半順序木にも使える手法
  • Efficient Top-K Closeness Centrality Search
  • Contract & Expand: I/O Efficient SCCs computing
    • メモリに入らないグラフのSCCを計算したい
  • ✔Efficient and Accurate Query Evaluation on Uncertain Graphs via Recursive Stratified Sampling
    • 期待値クエリ評価と閾値クエリ評価を提案
    • Monte-Carloを避けたいのでestimatorを提案,階層的な標本
    • cut-set basedなestimator
    • 影響力評価と期待信頼距離クエリに応用
  • ✔Subgraph Pattern Matching over Uncertain Graphs with Identity Linkage Uncertainty
    • probabilistic entity graph (PEG)
    • 部分グラフパターンマッチング
  • Multi-Cost Optimal Route Planning under Time-Varying Uncertainty
    • 旅行時間や温室効果ガスとかのコストは時間に依存するし不確実
    • 道路ネットワークで,multi-cost, time-dependent, uncertain GPSデータを元に
    • 開始時間と開始・終了頂点が入力で最適経路を計算
  • ✔Fast Incremental SimRank on Link-Evolving Graphs
    • 既存は特異値分解 O(r^4 n^2)
    • 逐次的更新のためにシルベスター行列とか使う
    • 枝刈りを入れる
  • Geometry Approach for k-Regret Query
    • top-kやskylineはダメなので,k-regret queryを考える
    • 幾何的な考察をもとに,happy pointsなる点を同定する
    • 既存のものよりめっちゃ高速

ICDE 2015

  • Finding Dense and Connected Subgraphs in Dual Networks
    • 物理・概念の世界を表す2つのグラフ
    • ↑で連結↑で高密度
    • NP-hard
  • Multi-Constrained Graph Pattern Matching in Large-Scale Contextual Social Graphs
    • Contextual Social Graphs
  • ✔Multicore Triangle Computations Without Tuning
    • マルチコアを活かしきれてない
    • cache-friendly OpenMPとかで実装可能
    • G頂点
  • Preserving Privacy in Social Networks Against Connection Fingerprint Attacks
    • 新しいprivacy attack モデル
  • Real Time Personalized Search on Social Networks
    • データベースっぽい
    • 頻繁な更新とスモールワールド性を活かせてない
    • 索引構造とグラフ上の関係性
  • Quick-Motif: An Efficient and Scalable Framework for Exact Motif Discovery
    • 配列データベース
    • 関連ある部分列の組を見つけたい
    • 2段階の手法(前処理)
  • Size-Constrained Weighted Set Cover
    • Weighted Set CoverとMaximum Coverageの一般化(?)
    • 入力: T, Cost:T→R>=0,k,s^
    • S⊆T (|S|≦k)であって,
    • |∪s Ben(s)|≧s^|T|かつΣs Cost(s)が最小
  • The Safest Path via Safe Zones
    • safe zoneが与えられるので,"safe以外を通る距離"を最小化したい
    • プロコンぽい?
  • ✔Scalable SimRank Join Algorithm
    • Takanori Maehara, Mitsuru Kusumoto, Ken-ichi Kawarabayashi
    • uに対するSimRank top-kの頂点をとってくる
    • 線形っぽく,酔歩ベース,局所領域だけ,上限を使って枝刈り
    • G辺にスケール
  • Diversified Top-K Clique Search
    • top-kは重複しててツマラン
    • top-kが全体をcoverして欲しい
    • 極大クリーク列挙は辛い→top-kだけ保持しておく
    • 近似比
  • VENUS: Vertex-Centric Streamlined Graph Computation on a Single PC
    • ディスクベースシステム,安価なPCで
  • On Random Walk Based Graph Sampling
    • Rong-Hua Li, Jeffrey Xu Yu, Lu Qin, Rui Mao, Tan Jin
    • 今までのサンプリング手法(3つ)は良くない
    • 新手法2つ
  • Making Pattern Queries Bounded in Big Graphs
    • Qのパターンマッチング.GでなくG_Qだけ見れば良いようにしたい
  • A Tale of Three Graphs: Sampling Design on Hybrid Social-Affiliation Networks
    • 一つのグラフをサンプリングするんだけど,実世界のは付随した他のグラフがある
    • それを利用すると連結になってサンプリングしやすい
  • Asymmetric Structure-Preserving Subgraph Queries for Large Graphs
    • subgraph isomorphism ムズイ
    • 強力なマシンに外注→信頼性がないので秘匿したい
  • Linear Path Skylines in Multicriteria Networks
    • ちょっとSkylineとは違う?
  • Dynamic Interaction Graphs with Probabilistic Edge Decay
    • 動的相互作用を扱う,確率的減衰で
  • HaTen2: Billion-scale Tensor Decompositions
    • Inah Jeon, Evangelos E. Papalexakis, U Kang, Christos Faloutsos
    • テンソル分解,MapReduce,疎性利用
  • Bump hunting in the dark: Local discrepancy maximization on graphs
    • クエリQに対し連結部分グラフCを出力
    • |Q∩C|を多く,|C\Q|を少なくしたい
    • 2つのアクセスモデル
    • ヒューリスティクスを実験で
  • Network Motif Discovery: A GPU Approach
    • そのまんま,motifはランダムグラフ上の出現頻度より多いよ考える
  • Convex Risk Minimization to Infer Networks from Probabilistic Diffusion Data At Multiple Scales
    • SEIRモデルの辺の推定
    • 頂点の状態情報だけ,不完全でもOK
  • ✔Mining Maximal Cliques from an Uncertain Graph
    • α-maximal clique数え上げ
    • それの出現確率がα以上,一つでも足すとα未満になる

ICDM 2010

ICDM 2011

ICDM 2012

ICDM 2013

ICDM 2014

ICDM 2015

  • Catching the head, tail, and everything in between: a streaming algorithm ...
    • 次数分布をストリームで見積もりたい
    • 本来の1%以下(数百万辺だけど・・・)
    • どのスケールでも精度良い
    • tailのほうが無視されがちなので,Relative Hausdorffという新しい概念を作った
  • Absorbing random-walk centrality: Theory and algorithms
    • Qについて中心的な(?)頂点集合Cを求めたい
    • 具体的に:Qからランダムウォークを開始して,Cに「吸収」されるまでの期待ステップ数最小化
    • 単調劣モジュラ
  • ✔Diamond Sampling for Approximate Maximum All-pairs Dot-product (MAD) Search
    • ベクトルの集合が2つ与えられる,内積の組を見つけよ
    • (i,j)を対応する内積に比例する確率で標本する

ICML 2011

ICML 2012

ICML 2014

  • Influence Function Learning in Information Diffusion Networks
    • 学習するにしても情報拡散のモデル化が物凄くシビア
    • 被覆関数っぽいので,random basis関数の凸結合で表す
    • モデルを定義しなくても良い
  • ✔Fast Multi-Stage Submodular Maximization
    • 多段階でメモリを節約,1000倍とか速くなった

ICML 2015

  • An Aligned Subtree Kernel for Weighted Graphs
    • 実験すると分類の精度で既存より良い
  • A Provable Generalized Tensor Spectral Method for Uniform Hypergraph Partitioning
    • 類似度は普通2点間
    • CVとかTextMiningではmulti-wayなのでhypergraphを分割したくなる
    • tensor trace optimization として
  • A Divide and Conquer Framework for Distributed Graph Clustering
    • 分割統治,小さいクラスタのサイズがo(√n)でOK(よくわからん)
  • ✔Yinyang K-Means: A Drop-In Replacement of the Classic K-Means with Consistent Speedup
    • 基本は距離計算の枝刈り
    • 普通のk-meansと同じ結果を返す
  • Random Coordinate Descent Methods for Minimizing Decomposable Submodular Functions
    • 最近は凸最適化
    • random coordinate descentなるものを使う
    • 線形収束,速いらしい…
  • Inferring Graphs from Cascades: A Sparse Recovery Framework
    • 疎復元の観点から
    • IC,Voterを含む一般的なモデルを考える
    • グラフの辺(重みパラメータも)を高確率で復元
  • ✔Faster cover trees
    • cover tree data structure…厳密最近傍クエリに有効
    • もっと早くしました
    • 頂点数: O(n)→n
    • 並列で処理できるお
    • キャッシュ効率も良く
  • ✔On Greedy Maximization of Entropy
    • 何で1-1/eより良い(ほぼ最適)?
    • curvatureに基づいて

ICML 2016

  • k-variates++: more pluses in the k-means++
    • 一般的な密度でのサンプリング
    • Arthur-Vassilvitskii近似保証の一般化
    • 何か上位互換っぽい感じ?
    • differential privacyへの応用
  • ✔Correlation Clustering and Biclustering with Locally Bounded Errors
    • 各頂点における誤り数の何かしらの関数で考える
    • 丸めアルゴリズム,定数近似
  • Fast k-means with accurate bounds
    1. 高速化,3倍くらい
    2. 距離推定の奴の改善,1.8倍くらい
  • K-Means Clustering with Distributed Dimensions
    • 次元がいくつかのマシンに分割
    • 新しい近似アルゴリズム
      • 通信費用少ない,定数近似
  • Fast Constrained Submodular Maximization: Personalized Data Summarization
    • 単調とは限らない,p-systemとl knapsackの交差制約
      • 制約の例が参考になるのでは?!
    • クエリ数 vs. 近似比
  • Learning Sparse Combinatorial Representations via Two-stage Submodular Maximization
    • Krause, Singer
    • 二段階の奴,基数制約劣モジュラ最大化の一般化
    • 連続最適化と局所探索1/2近似
  • Speeding up k-means by approximating Euclidean distances via block vectors
    • Holder不等式なるもので,ユークリッド距離を近似する
    • で,k-meansに応用,Yinyangにも優る
  • ✔Algorithms for Optimizing the Ratio of Submodular Functions
    • Bilmes
    • 新しい問題,割りとタイトな結果(hardnessと手法),効率を調べる
    • 差の最小化との関連も
  • Horizontally Scalable Submodular Maximization
    • Krause
    • 分散劣モジュラ最大化,各マシンの容量に制約がある

ICWSM 2010

ICWSM 2011

IJCAI 2009

IJCAI 2011

IJCAI 2015

  • Influence Maximization in Big Networks: An Incremental Algorithm for ...
  • Non-monotone Adaptive Submodular Maximization
  • A Fast Local Search for Mnimum Vertex Cover in Massive Graphs
  • A Scalable Community Detection Algorithm for Large Graphs Using Stochastic Block Models
  • Scalable Graph Hashing with Feature Transformation
  • Maximizing the Coverage of Information Propagation in Social Networks
  • Analysis of Sampling Algorithms for Twitter
  • Generalized Transitive Distance with Minimum Spanning Random Forest
  • Exploiting k-Degree Locality to Improve Overlapping Community Detection
  • Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning

INFOCOM 2012

INFOCOM 2013

INFOCOM 2014

ISAAC 2015

  • How to select the largest k elements from evolving data?
  • Fully Dynamic Betweenness Centrality
  • Randomized Minmax Regret for Combinatorial Optimization Under Uncertainty

ITCS 2014

  • ✔Why do simple algorithms for triangle enumeration work in the real world?
    • C. Seshadhri
    • ベキ則次数分布を持つグラフでの三角形列挙の性能を解析
    • 特に簡単なヒューリスティクス
    • α>7/3だと期待計算時間が線形

KDD 2003

  • Mining distance-based outliers in near linear time with randomization and a simple pruning rule
    • 外れ値検出割りと成功してる
    • 入れ子ループで最悪自乗な手法
    • データがランダムオーダーで枝刈り入れるとだいたい線形
  • Inverted matrix: efficient discovery of frequent items in large datasets in the context of interactive mining
    • アソシエーション分析: 商品間の関連性の分析とかそういう
    • ディスクベースの手法
  • Algorithms for estimating relative importance in networks
    • いくつかの頂点を基準とした関連
    • いろんな基準を入れた手法をつくったよ
    • テロリストネットワークとか,共同研究とか
  • CloseGraph: mining closed frequent graph patterns
    • グラフgがclosed: 真のgのsupergraphで,同じsupport(なぞすぎた?)のが無い
  • Finding recent frequent itemsets adaptively over online data streams
    • 昔の出現は割り引かれる
    • 枝刈り?
  • Natural communities in large linked networks
    • コミュニティがどう変化すんの
    • ちょっとの摂動では変化が無い方がいい
  • Graph-based anomaly detection
    • Regularityの計算手法を使って異常検出
    • ↑がNAZO

KDD 2004

  • Approximating a collection of frequent sets
    • 出力も超大きかったりする
    • 頻出のアイテム集合のCollectionをk個の集合で「近似」
  • Fast discovery of connection subgraphs
    • connection subgraph: 2頂点間の関係をよくとらえた部分グラフ
    • 電気回路的な類推でよさ気な定義して,高速手法
  • Cyclic pattern kernels for predictive graph mining
    • 閉路と木のパターンでカーネル関数?
      • 頻度には依存しない
    • 頻出パターンに基づくグラフカーネルより良い性能
  • Mining the space of graph properties
    • 特定の性質を満たす頂点が~とかが類似度の基準とかで使われる
    • ↑適切なのってどうすんの?
    • 性質のマイニングそのものの基礎的な枠組みを提案
    • グラフの性質の空間
  • Kernel k-means: spectral clustering and normalized cuts
    • Kernel k-meansとスペクトラルクラスタリングの関係
    • 色々書いてあるけ
  • SPIN: mining maximal frequent subgraphs from graph databases
    • 特定の部分グラフ数え上げとかやばめ
    • 「極大」なものにして出力サイズを小さくする
  • Mining scale-free networks using geodesic clustering
    • 測地線?みたいなのでモデル化
    • で,クラスタリングもする(謎

KDD 2005

  • On Mining Cross-Graph Quasi-Cliques
    • 問題定義は謎
    • 応用があるらしい
    • 生物学のデータセットで色々出てくる
  • Mining tree queries in a graph
    • 木っぽいパターンを見つける
    • 色々謎
  • ✔Graphs over time: densification laws, shrinking diameters and possible explanations
  • Mining closed relational graphs with connectivity constraints
    • 頻出する連結度の高いグラフを探し出す
  • Creating social networks to improve peer-to-peer networking
    • P2Pの効率を上げたい人
    • overlay networkの生成をいろいろ試したよ
  • Discovering frequent topological structures from graph datasets
    • topologicalなのが気になる
    • topological minorがベース
  • Evaluating similarity measures: a large-scale study in the orkut social network
    • 6つの類似度をメンバ推薦に使えるか比較
  • Building connected neighborhood graphs for isometric data embedding
    • 近傍グラフ
    • 最近傍が良いとは限らん
    • k-edge-connected neighborhood graphがある
      • 手法も色々ある
    • k-connected nrighborhood graphの手法を提案

KDD 2006

  • Group formation in large social networks: membership, growth, and evolution
  • NeMoFinder: dissecting genome-wide protein-protein interactions with meso-scale network motifs
  • Estimating the global pagerank of web communities
  • Frequent subgraph mining in outerplanar graphs
  • Measuring and extracting proximity in networks
  • Center-piece subgraphs: problem definition and fast solutions
  • Structure and evolution of online social networks
  • Sampling from large graphs
  • Coherent closed quasi-clique discovery from large dense graph databases

KDD 2007

  • Cost-effective Outbreak Detection in Networks
  • Correlation search in graph databases
  • GraphScope: parameter-free mining of large time-evolving graphs
  • A spectral clustering approach to optimally combining numericalvectors with a modular network
  • A framework for community identification in dynamic social networks
  • SCAN: a structural clustering algorithm for networks

KDD 2008

  • Influence and correlation in social networks
  • Efficient semi-streaming algorithms for local triangle counting in massive graphs
  • Feedback effects between similarity and social influence in online communities
  • The structure of information pathways in a social communication network
  • Microscopic evolution of social networks
  • Weighted graphs and disconnected components: patterns and a generator
  • Mobile call graphs: beyond power-law and lognormal distributions
  • Community evolution in dynamic multi-mode networks
  • Colibri: fast mining of large static and dynamic graphs
  • A family of dissimilarity measures between nodes generalizing both the shortest-path and the commute-time distances

KDD 2009

KDD 2010

KDD 2011

KDD 2012

KDD 2013

KDD 2014

KDD 2015

  • Influence at Scale: Distributed Computation of Complex Contagion in Networks
  • Efficient Algorithms for Public-Private Social Networks
  • Reciprocity in Social Networks with Capacity Constraints
  • Online Influence Maximization
  • Locally Densest Subgraph Discovery
  • Panther: Fast Top-k Similarity Search on Large Networks
  • COSNET: Connecting Heterogeneous Social Networks with Local and Global Consistency
  • Edge-Weighted Personalized PageRank: Breaking A Decade-Old Performance Barrier
  • Adaptive Message Update for Fast Affinity Propagation
    • NTT
  • MASCOT: Memory-efficient and Accurate Sampling for Counting Local Triangles in Graph Streams
  • Network Lasso: Clustering and Optimization in Large-Scale Graphs
  • Set Cover at Web Scale
  • TimeCrunch: Interpretable Dynamic Graph Summarization
  • Integrating Vertex-centric Clustering with Edge-centric Clustering for Meta Path Graph Analysis
  • An Evaluation of Parallel -- Eccentricity Estimation Algorithms on Real-World Graphs
  • Improved Bounds on the Dot Product under Random Projection and Random Sign Projection
  • Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling
  • A Learning-based Framework to handle Multi-round Multi-party influence maximization on social networks
  • Deep Graph Kernels
  • Beyond Triangles: A Distributed Framework for Estimating 3-profiles of Large Graphs

KDD 2016

  • Structured Doubly Stochastic Matrix for Graph Based Clustering
    • 二重確率行列のクラスタ構造は謎,後処理必要
    • 凸モデルで何かいい感じにする
  • ✔Approximate Personalized PageRank on Dynamic Graphs
    • Peter Lofgren
    • Forward Push: ソースから辺に沿って確率を押し流す
    • Reverse Push: ターゲットから辺を逆に沿って局所的変化を伝播
    • RP: ランダム辺モデルでの更新時間
    • FP: ちょい違う設定での更新時間
    • ついでに新しい双方向PPR推定アルゴリズム
  • Fast Memory-efficient Anomaly Detection in Streaming Heterogeneous Graphs
    • グラフ同士の新しい類似関数を提案して,いい感じにストリームで検出する
  • Structural Neighborhood based Classification of Nodes in a Network
    • ランダムウォークを使うと,ノイズとかに強い分類が出来るらしい
  • Graph Wavelets via Sparse Cuts
    • Multiway cutsとかと関係がある,でヒューリスティック
    • ベクトル最適化問題で定式化していい感じに解ける
  • TRIEST: Counting Local and Global Triangles in Fully-Dynamic Streams with Fixed Memory Size
    • Eli Upfal
    • 辺追加削除のあるストリームグラフでのワンパスアルゴリズム
    • メモリ使用量が指定できる
  • ABRA: Approximating Betweenness Centrality in Static and Dynamic Graphs with Rademacher Averages
    • ランダムサンプリング,道具:Rademacher averagesとpseudodimension
      • 統計的学習理論からの概念の最初の適用
    • めちゃ良い
  • Compact and Scalable Graph Neighborhood Sketching
    • Akiba-Yano
  • Robust Influence Maximization
    • Xinran He, David Kempe
  • PTE: Enumerating Trillion Triangles On Distributed Systems
    • U Kang
    • 分散アルゴリズムで超頑張る,ClueWeb12まで動く
  • Asymmetric Transitivity Preserving Graph Embedding
    • ベクトル空間に埋め込む
    • u-vパスがあれば,u-v辺がありやすいってなってほしい
    • そういうのの一般化した奴を保つ埋め込みアルゴリズム
  • Robust Influence Maximization
    • Wei Chen, Tian Lin, Zihan Tan, Mingfei Zhao, Xuren Zhou

ポスター

  • Scalable Betweenness Centrality Maximization via Sampling
    • [Yoshida. KDD'14]の改善に相当
    • ちょっと解析もする
  • Reconstructing an Epidemic over Time
    • テンポラルネットワークが入力で,流れを復元したい
    • 既存研究は仮定が強すぎ
    • テンポラルSteiner木として定式化
  • Compressing Graphs and Indexes with Recursive Graph Bisection
    • reorderingで圧縮を改善する
    • reorderingは再帰的グラフbisectionベースアルゴリズムで解く
  • Scalable Pattern Matching over Compressed Graphs via Dedensification
    • デデン!
    • 高次数頂点が辛くて
    • 周囲を圧縮するためのテクを提案
  • Diversified Temporal Subgraph Pattern Mining
    • James Cheng
    • 応用: トレンド,ホットスポット
    • 分割統治でベースラインより早いお

NIPS 2013

NIPS 2014

  • Provable Submodular Minimization using Wolfe's Algorithm
    • 1976年の手法だけど,あんま解析されてなかった
    • 擬多項式時間保証を得られた
  • ✔Parallel Double Greedy Submodular Maximization
    • 非単調な場合の二重貪欲の並列化
    • 数十億辺規模のグラフで実験

PAKDD 2010

PKDD 2006

PKDD 2007

PKDD 2012

SDM 2009

  • FutureRank: Ranking Scientific Articles by Predicting their Future PageRank
    • 論文のランキング
      • 引用ネットワークは日々進化
    • 将来的なのが気になる→将来のPageRank
    • 共著ネットワークと公開時刻も利用
  • On Randomness Measures for Social Networks
    • ちょっとランダム性がある
    • 非ランダム性の測り方
      • 辺単位,グラフ全体でも
  • Randomization Techniques for Graphs
    • よく分からん
  • Detecting Communities in Social Networks Using Max-Min Modularity
    • Max-Min Modularityが新しいらしい
    • 階層的クラスタリング
  • Top-k Correlative Graph Mining
    • クエリグラフの出現分布が似ていると関係がある
    • 効率的な関係性のチェック,枝刈り,候補の探索

SDM 2010

  • Fast Single-Pair SimRank Computation
  • Reconstructing Randomized Social Networks
    • グラフGと特徴ベクトルF
    • 匿名化や雑音によってG'とF'に変化
    • ある乱択手法(どういう過程かわかってる
    • 元に戻せる?
  • Reconstruction from Randomized Graph via Low Rank Approximation
    • 辺がごちゃごちゃにされたグラフから再構築
    • 低rank近似
  • GraSS: Graph Structure Summarization
    • 色々な要因で要約したい
    • ランダムワールドモデル(?)
    • クエリにも答えられる
  • Mining Frequent Graph Sequence Patterns Induced by Vertices
    • グラフ列で頻繁なパターンをとってきたい
    • 鷲尾研
  • On Clustering Graph Streams
    • アプローチ: hash-compressed micro-clusters
  • Inferring Probability Distributions of Graph Size and Node Degree from Stochastic Graph Grammars
    • 確率的グラフ
    • 頂点・辺・密度の確率質量関数
    • Graph grammarsとは???
  • Direct Density Ratio Estimation with Dimensionality Reduction
    • 杉山先生

SDM 2011

  • Influence Maximization in Social Networks When Negative Opinions May Emerge ...
  • Maximising the Quality of Influence
    • 活性化が[0,1]の範囲で質を測る
    • 辺に沿って減衰する
    • 予算制約下で上手くやる←貪欲アルゴリズム
  • The Network Completion Problem: Inferring Missing Nodes and Edges in Networks
    • 期待値最大化の枠組
    • leskovec
  • Centralities in Large Networks: Algorithms and Observations
    • 媒介・近接は計算難しい
    • よさ気な中心性を定義,計算
  • Large Scale Graph Mining and Inference for Malware Detection
    • 信念伝播法的な
    • CMUとSymantecの共同研究
  • Non-Negative Residual Matrix Factorization with Application to Graph Anomaly Detection
    • そういうの
  • Kernel-based Similarity Search in Massive Graph Databases with Wavelet Trees
    • ラベル付きグラフの類似性
      • XML,化合物
    • 共通する部分構造の数で類似度
    • k個以上共通するとか欲しい
    • Wavelet treesでGrossi et al., SODA’03
    • たべいさん
  • Clustered low rank approximation of graphs in information science applications
    • クラスタリングして,各クラスタをいろんな方法で近似
      • 特異値分解とか
  • Towards Community Detection in Locally Heterogeneous Networks
    • グラフ上の振舞が一様だと思ってるのが駄目,大域的なコミュニティの欠点
    • 局所的簡潔性という性質
  • On Classification of Graph Streams
    • メモリ内に要約みたいなものを確率的に作る
    • 2次元ハッシュ空間で特徴的なパターンを見つける
    • 理論的に質?の保証

SDM 2012

  • On Influential Node Discovery in Dynamic Social Networks
  • Influence Blocking Maximization in Social Networks under the Competitive ...
  • Fast Robustness Estimation in Large Social Graphs: Communities and Anomaly ...
    • Q. 頑健性について何か言える?速く?成長する場合にどう変わる?
    • expansion properties
  • Symmetric Nonnegative Matrix Factorization for Graph Clustering
    • NMF+頂点間の類似度を持つ(?)のでクラスタリングが良い?
  • Multi-skill Collaborative Teams based on Densest Subgraphs
    • 頂点には複数のスキル,辺重みは類似とか共同適合性
    • 入力: データベース専門3人,理論専門2人
    • ↑の条件で共同研究の適合性が高い人を見つけたい
    • 3-近似アルゴリズム
  • Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model
    • 競合相手の情報伝播をブロック
    • LDAGの拡張(Wei Chen
    • 似たの無かったっけ?
  • A Framework for the Evaluation and Management of Network Centrality
    • 経路数ベースの中心性の一般的に定義
    • それの最適化問題k辺とるとか
  • Structural Analysis in Multi-Relational Social Networks
    • 一般化Stochastic Block Models
    • 関係の予測?
  • Fast Random Walk Graph Kernel
    • O(n^3)/O(m^2)時間
    • low rank活用? O(n^2)/O(m)時間
  • Global Linear Neighborhoods for Efficient Label Propagation
    • ラベルがないなら伝播するよってのが上手く言っていた前から
    • 重みつき近傍がよさ気だった
    • 大域的線形近傍を捉えるために非負low-rankグラフを学習????
  • A Tree-Based Kernel for Graphs
    • 木ベースの新しいグラフカーネル
    • 順序ずけられたDAGに分解
  • The Similarity Between Stochastic Kronecker and Chung-Lu Graph Models
    • Stochastic Kronecker Graphsの性質は謎
      • Graph500とかでも使われてる
    • Chung-Luが似てるよって示すよ
      • CLはfit?しやすい
  • WIGM: Discovery of Subgraph Patterns in a Large Weighted Graph
    • 重み付きグラフでマイニング
    • 重みに閾値がついて部分グラフ抽出
    • 重みtop-kのパターン

SDM 2013

SDM 2014

SDM 2015

  • Selecting Shortcuts for a Smaller World
    • 平均最短距離長を最小化するようなk辺を追加したい
    • 一辺追加時の効果を効率的に厳密計算
    • ヒューリスティクスを考案
  • Where Graph Topology Matters: The Robust Subgraph Problem
    • 頑健性は輸送・通信ネットワークで大事
    • 局所的な頑健性を見たい
    • 最も頑健な部分グラフは?
      • 密グラフ(!)と関連
    • NP-hardなのでヒューリスティクス
  • On Influential Nodes Tracking in Dynamic Social Networks
  • A Divide-and-Conquer Algorithm for Betweenness Centrality
    • 媒介中心性の厳密計算は[Brandes. 2001]がこれまで最速
    • グラフのスケッチを使った手法
    • 部分グラフを簡単な構造のグラフに置き換える
    • 超速い
  • Cheetah: Fast Graph Kernel Tracking on Dynamic Graphs
    • グラフカーネル:グラフの類似尺度に使える
    • 固有分解/隣接行列のSVDを逐次的に更新する
    • sub-linearにスケール
  • Community Detection for Emerging Networks
    • Community
    • 新しい近接尺度intimacyを提案
    • (謎)
  • Dropout Training of Matrix Factorization and Autoencoder for Link Prediction in Sparse Graphs
    • 教師なし学習:Matrix factorizationとAutoencoder
    • 疎グラフのリンク予測に使う
    • MFとAEを両方使うよ
  • Efficient Algorithms for a Robust Modularity-Driven Clustering of. Attributed Graphs
    • Modularityベースのクラスタリング
    • 頂点には追加の属性がある
    • 無関係の属性や外れ値に関するクラスタリングのmodularityベースの手法(?)
  • Fast Mining of a Network of Coevolving Time Series
    • Coevolving(共進化)
    • 環境監視,ネットワークトラフィック監視,モーションキャプチャとか
    • 動的Contextual(文脈上の)行列分解アルゴリズム
  • Functional Node Detection on Linked Data
  • Hidden Hazards: Finding Missing Nodes in Large Graph Epidemics
    • 雑音がある/標本したグラフ上の感染のスナップショットがある
    • 真に感染してる紛失した頂点を復元できるか?
    • どこから始まったか?
    • MDLで考える
  • Modeling Users' Adoption Behaviors with Social Selection and Influence
    • ユーザの意思決定に作用するのはsocial selection/influence
    • (1) ユーザレベルの意思決定に↑がどう枠割を果たすのか?
    • (2) そういう要素がモデリング・予測に役立つのか?
    • モデル作るよ
  • ✔Reducing the spectral radius to control epidemic spread
    • スペクトル半径は大事だよ
    • SISモデルとかでは半径が大事なパラメータ
    • 半径を弄って感染を操作したい
    • 辺を削除して半径を抑える
    • O(log^2 n)近似
    • 主双対アルゴリズム O(log n)近似
  • Spectral Embedding of Signed Networks
    • そのまんま,既存の手法には問題が有るらしい
  • Tensor Spectral Clustering for Partitioning Higher-order Network Structures
    • スペクトラルな手法は一次Markov chainに基づく
    • 高次な△,閉路は利用してない
    • ↑を何か上手く使う
  • Vertex Clustering of Augmented Graph Streams
    • グラフストリームでクラスタリング
    • 構造的+属性に関する類似尺度利用
    • クラスタ数が必要ない

SIGIR 2014

SIGMOD 2003

  • Spectral Bloom Filters

SIGMOD 2004

  • Online Maintenance of Very Large Random Samples
  • Graph Indexing: A Frequent Structure-based Approach

SIGMOD 2005

  • Substructure Similarity Search in Graph Databases

SIGMOD 2006

  • 無し

SIGMOD 2007

  • Fast and practical indexing and querying of very large graphs
  • Fg-index: towards verification-free query processing on graph databases

SIGMOD 2008

  • Graph summarization with bounded error
  • Mining significant graph patterns by leap search
  • CSV: visualizing and mining cohesive subgraphs
  • Efficient aggregation for graph summarization
  • Efficiently answering reachability queries on very large directed graphs
  • Minimization of tree pattern queries with constraints

SIGMOD 2009

  • Monitoring path nearest neighbor in road networks
  • 3-HOP: a high-compression indexing scheme for reachability query

SIGMOD 2010

  • TEDI: efficient shortest path query answering on graphs
  • GBLENDER: towards blending visual query formulation and query processing in graph databases
  • Computing label-constraint reachability in graph databases
  • Pregel: a system for large-scale graph processing
  • Finding maximal cliques in massive networks by H*-graph
  • K-isomorphism: privacy preserving network publication against structural attacks
  • Towards proximity pattern mining in large graphs
  • GAIA: graph classification using evolutionary computation
  • Finding maximum degrees in hidden bipartite graphs
  • Connected substructure similarity search

SIGMOD 2011

  • On k-skip Shortest Paths
  • Neighborhood-privacy protected shortest distance computing in cloud
  • On k-skip shortest paths
  • Finding shortest path on land surface
  • Neighborhood based fast graph search in large networks
  • A memory efficient reachability data structure through bit vector compression
  • Incremental graph pattern matching
  • Assessing and ranking structural correlations in graphs

SIGMOD 2012

  • Managing large dynamic graphs efficiently
  • Query preserving graph compression
  • SCARAB: scaling reachability computation on large graphs
  • A highway-centric labeling approach for answering distance queries on large sparse graphs
  • Efficient processing of distance queries in large graphs: a vertex cover approach
  • Towards effective partition management for large graphs
  • TreeSpan: efficiently computing similarity all-matching

SIGMOD 2013

SIGMOD 2014

  • In Search of Influential Event Organizers in Online Social Networks
  • Efficient Location-Aware Influence Maximization
  • Querying K-Truss Community in Large and Dynamic Graph
  • The Pursuit of a Good Possible World: Extracting Representative Instances of ...
  • HYDRA: large-scale social identity linkage via heterogeneous behavior modeling
  • Influence maximization: near-optimal time complexity meets practical efficiency
  • Efficient algorithms for optimal location queries in road networks
  • Scalable similarity search for SimRank
  • Efficient cohesive subgraphs detection in parallel
  • Parallel subgraph listing in a large-scale graph
  • OPT: a new framework for overlapped and parallel triangulation in large-scale graphs
  • Scalable big graph processing in MapReduce
  • Navigating the maze of graph analytics frameworks using massive graph datasets
  • Local search of communities in large graphs
  • Mining statistically significant connected subgraphs in vertex labeled graphs
  • Fast and unified local search for random walk based k-nearest-neighbor query in large graphs
  • Answering top-k representative queries on graph databases
  • Querying k-truss community in large and dynamic graphs
  • Reachability queries on large dynamic graphs: a total order approach
  • Localizing anomalous changes in time-evolving graphs
  • Tracking set correlations at large scale
  • Tripartite graph clustering for dynamic sentiment analysis on social media

SIGMOD 2015

  • COMMIT: A Scalable Approach to Mining Communication Motifs from Dynamic Networks
  • Minimum Spanning Trees in Temporal Graphs
  • Influence Maximization in Near-Linear Time: A Martingale Approach
  • GetReal: Towards Realistic Selection of Influence Maximization Strategies in Competitive Networks
  • ✔BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs
    • Random Walk with Restartの計算
    • 隣接行列をreorder 逆行列を取りやすい?
    • Schur補行列
    • クエリに対してブロック対角化
  • Community Level Diffusion Extraction
  • Divide & Conquer: I/O Efficient Depth-First Search
    • グラフを分割してDFSしてマージ
  • ✔Efficient Enumeration of Maximal k-Plexes
  • Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates
    • 具体的なNN関数が無い
    • それでもよさ気な候補が欲しい
    • いろんなNN関数を分類
  • Exact Top-k Nearest Keyword Search in Large Networks
  • Updating Graph Indices with a One-Pass Algorithm
  • ✔The Minimum Wiener Connector Problem
    • Wiener index=頂点対の最短距離の総和
    • クエリ頂点を連結しつつWiener indexが最小の部分グラフ
    • 基本NP-hard
    • O~(|Q||E|)時間,定数近似
  • Real-Time Multi-Criteria Social Graph Partitioning: A Game Theoretic Approach
    • ゲーム理論的枠組を押してる
    • 各ユーザがその目的関数を最適化
  • Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity
    • 頂点集合qに対して連結度最大のSteiner成分
    • これをオンラインで解く
  • Efficient Route Planning on Public Transportation Networks: A Labelling Approach

SODA 2008

SODA 2014

SODA 2016

  • ✔Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions
    • 影響最大化のadaptive seedingの一般化
    • 一段階目での選択が二段階目のrealizationに影響する
    • (1-1/e)^2近似アルゴリズム
  • ✔Algorithmic Complexity of Power Law Networks
    • Power lawグラフのアルゴリズム計算量を解析
    • ベキ則の判定(?)
    • なんで色んな(最悪時は遅い)アルゴリズムが高速に動作するのか?
    • ランダムグラフだとうまく行くと示されていたが(average-case analysis)
    • 固定されてものでやった

STOC 2013

STOC 2014

UAI (Uncertainty in Artificial Intelligence)

UAI 2015

  • Revisiting Non-Progressive Influence Models: Scalable Influence Maximization in Social Networks
    • 熱伝導を取りいれた非進歩的(選択が戻ったりする)な拡散モデル
    • 劣モジュラ,で,σが閉じた式で表せるっぽい?

VLDB 2010

VLDB 2011

VLDB 2012

VLDB 2013

VLDB 2014

  • More is Simpler: Effectively and Efficiently Assessing Node Pair ...
  • On k-Path Covers and their Applications
  • Toward a Distance Oracle for Billion-Node Graphs
    • 最短経路の近似
    • 微妙
  • Finding Shortest Paths on Terrains by Killing Two Birds with One Stone
    • shortest surface distance
      • 複雑な地形,山とか,の上を這って行く最短経路問題
  • Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited
    • joinの実験的性能
  • From "Think Like a Vertex" to "Think Like a Graph"
    • 分散グラフ処理システム
    • 分割の考え方
  • ✔Computing k-Regret Minimizing Sets
    • k-Regret Minimizingの難しさ,DPな手法,実験
  • GRAMI: Frequent Subgraph and Pattern Mining in a Single Large Graph
    • タイトルのまんま
  • A Principled Approach to Bridging the Gap between Graph Data and their Schemas
    • RDFグラフ
  • Finding the Cost-Optimal Path with Time Constraint over Time-Dependent Graphs
    • コストが変わるグラフ
    • vへの最速到達時刻が,vの近傍の最速到達時刻から得られるわけではないのでムズイ
  • Path Problems in Temporal Graphs
    • temporal graph上の最短路
    • 既存のは問題がある
    • 新しいので,性質と効率的アルゴリズム
  • ✔On k-Path Covers and their Applications
  • Repairing Vertex Labels under Neighborhood Constraints
    • 近傍制約なるものが成立するように頂点のラベルを復元する
    • 貪欲な近似アルゴリズム
  • ✔Computing Personalized PageRank Quickly by Exploiting Graph Structures
  • Distributed Graph Simulation: Impossibility and Possibility
    • 並列計算のアルゴリズムの性質の話?
  • Reachability Querying: An Independent Permutation Labeling Approach
    • 乱択アルゴリズムでラベリング
    • permutationが乱択に関連するらしい
  • Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks
    • 索引サイズのbound,I/Oコスト,をスケールフリーネットワークの性質から
  • Real-Time Twitter Recommendation: Online Motif Detection in Large Dynamic Graphs
    • 一時的に関連がある行動に基づいて推薦
    • オンラインMotif検出
  • VERTEXICA: Your Relational Friend for Graph Analytics!
    • グラフ解析ツール
    • SQLとか
  • Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees
  • Auto-Approximation of Graph Computing
  • LogGP: A Log-based Dynamic Graph Partitioning Method
  • Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs
  • Large Scale Real-time Ridesharing with Service Guarantee on Road Networks

VLDB 2015

  • ✔Viral Marketing Meets Social Advertising: Ad Allocation with Minimum Regret
    • 広告配置をバイラルマーケティング的に考える
  • ✔Online Topic-Aware Influence Maximization
    • MIAを利用
    • ε(1-1/e)近似
  • From Competition to Complementarity: Comparative Influence Diffusion and Maximization
    • 競合性と相補性をかね備えたICモデル
    • 辺だけの拡散ではない(らしい)
    • 2種類の問題を考えていろいろしてとく

WAW 2012

  • ✔A Sublinear Time Algorithm for PageRank Computations
    • PageRank値がΔ以上の頂点集合をとってきたい
    • ちょっと難しいので,Δ/c未満は絶対含まない(Δ/c以上は含んでても良い)って弱める
    • O~(n/Δ)時間アルゴリズム ほぼタイト
    • 提案手法はPPRの局所的探索を改善して使う

WINE 2007

WINE 2010

WSDM 2010

WSDM 2013

WSDM 2015

WSDM 2016

  • ✔Personalized PageRank Estimation and Search: A Bidirectional Approach
    • Estimation: 普通のPPR計算を双方向な感じで高速化
    • Search: sとTが与えられるので,PPR_sがtop-kのT中の頂点を見つける

WWW 2003

WWW 2004

WWW 2005

WWW 2007

WWW 2010

WWW 2011

WWW 2012

WWW 2013

WWW 2014

WWW 2015

  • Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph ...
  • ✔The k-clique Densest Subgraph Problem
    • 頂点集合Sであって,平均k-cliqueの下図を最大化したい
    • 分母は超点数
    • k=2…densest subgraph
    • k=3…$$ \frac{\# \Delta(S)}{|S|} $$
    • k固定で厳密多項式時間
    • 1/k-近似…効率的
    • 実験: 3-clique densestの解はnear-clique
  • A Game Theoretic Model for the Formation of Navigable Small-World Networks
    • ゲーム理論的モデル
    • ↑のNash近郊がnavigable small-world networks
    • 距離とreciprocityとの関係
  • Discovering Meta-Paths in Large Heterogeneous Information Networks
  • HIN…頂点・辺にラベル
    • meta-path…2頂点を結ぶ経路のラベル列
      • 情報検索・意思決定・商品推薦
    • 2頂点間の最も関連のある経路を出す←貪欲算法
  • ✔Spanning edge centrality: large-scale computation and applications
    • eの全域中心性=Gの全域木がeを含む割合
    • 近似手法←理論を持ちこむ(?)
    • 消すとやばい辺の同定に使える
  • ✔Scalable Methods for Adaptively Seeding a Social Network
    • 直接指定するんじゃなくてその近傍にやってもらう
    • friendship paradoxのおかげで強そう
    • scalableな手法を作ったよ
  • Asymmetric Minwise Hashing for Indexing Binary Inner Products and Set Containment
    • 非対称minhashという新しい手法
  • ✔Improved Theoretical and Practical Guarantees for Chromatic Correlation Clustering
    • LPベースの手法4近似
      • 遅いけど理論的理解
    • ヒューリスティクス
  • ✔Efficient Densest Subgraph Computation in Evolving Graphs
    • 動的・大規模同時はない
    • ↑クロールの手間
    • 2(1+ε)近似 O(polylog(n+r))コスト
  • Skolemising Blank Nodes while Preserving Isomorphism
    • RDFグラフ
  • Global Diffusion via Cascading Invitations: Structure, Growth, and Homophily
    • Webサイトとか招待でメンバが増える←カスケード!
    • LinkedIn
      • カスケードの形が違う(サインアップ)
      • 長時間起こる
  • Uncovering the Small Community Structure in Large Networks: A Local Spectral Approach
  • Recommendation Subgraphs for Web Discovery
    • 二部グラフ上の最適化問題
    • 左:よく訪れる
    • 右:あんま訪れない
    • 左から出辺をいくつか選ぶ
    • 右が冗長に選ばれる沢山
    • いろんな手法
      • 局所的無作為標本
      • 貪欲法
      • 分割
  • Random-Walk TripleRush: Asynchronous Graph Querying and Sampling
    • SPARQL 3つ組
    • DBの話
  • Essential Web Pages Are Easy to Find
    • 沢山のクエリに答えられる
    • ログから索引サイズの推定
    • Max Cover 63%近似

WWW 2016

  • ✔Social Networks Under Stress
    • ベストペーパー
    • "外部"事象がネットワーク構造・コミュニケーションにどう紐づく?
    • 価格ショック、ネットワーク構造
    • ネットワーク構造の変化が色々と(集団態度)予測する
  • Measuring Urban Social Diversity Using Interconnected Geo-Social Networks
  • Recommendations in Signed Social Networks
    • 符号付きネットワークでの推薦がそもそも少なかったので、頑張ってモデルを作りました
  • Economic Recommendation with Surplus Maximization
  • In a World That Counts: Clustering and Detecting Fake Social Engagement at Scale
    • YouTubeのヤバげなやつを検出したい
    • 偽のエンゲージメント活動を追跡する
    • semi-supervisedで、シードと似たパターンを探す
  • Tracking the Trackers
  • ✔Visualizing Large-scale and High-dimensional Data
    • 大規模高次元データを低次元空間に可視化
    • 提案手法LargeVis: 近似k-近傍グラフを構築→低次元空間にレイアウト
    • 確率的勾配降下法で線形時間
  • ✔On Sampling Nodes in a Network
    • 事前に指定した分布に従って,頂点をサンプリングしたい,ランダムウォーク!
  • Distributed Estimation of Graph 4-Profiles
    • 4-profile(連結でなくても良い部分グラフ)
    • 拡張点が11次元空間に埋め込まれる
  • ✔Do Cascades Recur?
    • Facebookのデータを解析,デカイカスケードが再発する
    • 経過時間とか重複具合とかで測定してみる
    • 予測できたよ
  • Exploring Limits to Prediction in Complex Social Systems
    • 複雑社会系での成功の予測
  • The Effect of Recommendations on Network Structure
    • 推薦はニッチなユーザの数を増やすのか,既にポピュラーなユーザの数を増やすのか
    • rich get richer的な現象が起きた

Manuscript+Technical report

ジャーナル

Computational Social Networks

Computers and Mathematics with Applications

Dynamics of Information Systems: Algorithmic Approaches

Discrete Applied Mathematics

  • On the maximum quasi-clique problem

KAIS (Knowledge and Information Systems) 2012

IPL (Information Processing Letters)

Internet Mathematics

  • Link Evolution: Analysis and Algorithms
  • ✔Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
    • 枝刈りメインでめっちゃ大きいグラフでもはしる最大クリーク検出アルゴリズム
    • 会議版WAW 2013

Information Sciences

JCO (Journal of Combinatorial Optimization) 2012

JSAC (IEEE Journal on Selected Areas in Communications) 2013

SNAM (Social Network Analysis and Mining) 2012

TKDD (Transactions on Knowledge Discovery from Data) 2009

TPDS (IEEE Transactions on Parallel and Distributed Systems)

Theoretical Computer Science

  • Computing maximal cliques in link streams
    • temporal graphでの極大クリークの列挙アルゴリズム,実験あり

*大見出し

フォーカス外

ACL-HLT

ACML (Asian Conference on Machine Learning) 2009

ICEC (International Conference on Electronic Commerce)

KES (International Conference on Knowledge-Based Intelligent Information and Engineering Systems)

ISMIS (International Conference on Foundations of Intelligent Systems)

SBP (International Workshop on Social Computing and Behavioral Modeling) 2009

PDPTA (International Conference on Parallel and Distributed Processing Techniques and Applications)

SNA-KDD (International Workshop on Social Network Mining and Analysis)

WI-IAT (International Joint Conference on Web Intelligence and Intelligent Agent Technology)

WISE 2013

国内会議

人工知能学会 JSAI

その他

American Journal of Sociology

  • Why Your Friends Have More Friends Than You Do

Econometrica

PLoS ONE

Proceedings of the National Academy of Sciences: PNAS

Physical Review E

  • ✔The spread of epidemic disease on networks
    • Newman

Physical Review Letters

Science

Nature Communications

2016-06-01 20:02:24 (Wed)