WWW 2015

  • The k-clique Densest Subgraph Problem
  • Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts
  • A Game Theoretic Model for the Formation of Navigable Small-World Networks
  • Discovering Meta-Paths in Large Heterogeneous Information Networks
  • Spanning edge centrality: large-scale computation and applications
  • Scalable Methods for Adaptively Seeding a Social Network
  • Asymmetric Minwise Hashing for Indexing Binary Inner Products and Set Containment
  • Improved Theoretical and Practical Guarantees for Chromatic Correlation Clustering
  • Efficient Densest Subgraph Computation in Evolving Graphs
  • Finding the Hierarchy of Dense Subgraphs using Nucleus Decompositions
  • Skolemising Blank Nodes while Preserving Isomorphism
  • Global Diffusion via Cascading Invitations: Structure, Growth, and Homophily
  • 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
  • Essential Web Pages Are Easy to Find

SIGMOD 2015

  • GetReal: Towards Realistic Selection of Influence Maximization Strategies in Competitive Networks
  • BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs
  • Minimum Spanning Trees in Temporal Graphs
  • Influence Maximization in Near-Linear Time: A Martingale Approach
  • Community Level Diffusion Extraction
  • Divide & Conquer: I/O Efficient Depth-First Search
  • Efficient Enumeration of Maximal k-Plexes
  • Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates
  • Exact Top-k Nearest Keyword Search in Large Networks
  • Updating Graph Indices with a One-Pass Algorithm
  • The Minimum Wiener Connector Problem
  • Real-Time Multi-Criteria Social Graph Partitioning: A Game Theoretic Approach
  • COMMIT : A Scalable Approach to Mining Communication Motifs from Dynamic Networks
  • Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity
  • Efficient Route Planning on Public Transportation Networks: A Labelling Approach

■

AAAI 2014

日本から

AI and the Web
↓自分の．

  • Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations
    • Naoto Ohsaka, Takuya Akiba, Yuichi Yoshida, Ken-ichi Kawarabayashi


Game Theory and Economic Paradigms

  • Two Case Studies for Trading Multiple Indivisible Goods with Indifferences
    • Akihisa Sonoda, Etsushi Fujita, Taiki Todo, Makoto Yokoo
  • Strategyproof Exchange with Multiple Private Endowments
    • Taiki Todo, Haixin Sun, Makoto Yokoo

Knowledge Representation and Reasoning

  • The Most Uncreative Examinee: A First Step toward Wide Coverage Natural Language Math Problem Solving
    • Takuya Matsuzaki, Hidenao Iwane, Hirokazu Anai, Noriko H. Arai

Machine Learning Applications

  • Accurate Household Occupant Behavior Modeling Based on Data Mining Techniques
    • Márcia Baptista, Anjie Fang, Helmut Prendinger, Rui Prada, Yohei Yamaguchi

NLP and Machine Learning

  • Fused Feature Representation Discovery for High-Dimensional and Sparse Data
    • Jun Suzuki, Masaaki Nagata

Novel Machine Learning Algorithms

  • Monte Carlo Filtering Using Kernel Embedding of Distributions
    • Motonobu Kanagawa, Yu Nishiyama, Arthur Gretton, Kenji Fukumizu
  • Mixing-Time Regularized Policy Gradient
    • Tetsuro Morimura, Takayuki Osogami, Tomoyuki Shirai
  • Semantic Data Representation for Improving Tensor Factorization
    • Makoto Nakatsuji, Yasuhiro Fujiwara, Hiroyuki Toda, Hiroshi Sawada, Jin Zheng, James A. Hendler
  • Online and Stochastic Learning with a Human Cognitive Bias
    • Hidekazu Oiwa, Hiroshi Nakagawa

Planning and Scheduling

  • Solving the Traveling Tournament Problem by Packing Three-Vertex Paths
    • Marc Goerigk, Richard Hoshino, Ken-ichi Kawarabayashi, Stephan Westphal

Innovative Applications of Artificial Intelligence

  • The Quest Draft: An Automated Course Allocation Algorithm
    • Richard Hoshino, Caleb Raible-Clark

Student Abstracts

  • Monte Carlo Simulation Adjusting
    • Nobuo Araki, Masakazu Muramatsu, Kunihito Hoki, Satoshi Takahashi

この木なんの木　気になる木　読むべ木

論文
AAAI
  • Sparse Multi-Task Learning for Detecting Influential Nodes in an Implicit Diffusion Network
ASONAM 2009
  • An Analytical Way to Find Influencers on Social Networks and Validate their Effects in Disseminating Social Games
  • Models of Communication Dynamics for Simulation of Information Diffusion
  • Waiting Time Sensitivities of Social and Random Graph Models
ASONAM 2010
  • The Structure of the Computer Science Knowledge Network
  • Product adoption networks and their growth in a large mobile phone network
  • What Can the Temporal Social Behavior Tell Us? An Estimation of Vertex - Betweenness Using Dynamic Social Information
  • Efficient Extraction of High - Betweenness Vertices
  • Detecting New Trends in Terrorist Networks （バンされた？）
  • Rhythm and Randomness in Human Contact
  • Virus Propagation Modeling in Facebook
  • Information propagation analysis in a social network site
ASONAM 2011
  • Efficient Search in Networks Using Conductance
  • Social Network Anonymization via Edge Addition
  • Probabilistic Subgraph Matching on Huge Social Networks
  • How Much Similar Are Terrorists Networks of Istanbul?
ASONAM 2012
  • Large Social Networks Can Be Targeted for Viral Marketing with Small Seed Sets
  • On Measurement of Influence in Social Networks
  • Visual Analysis of Dynamic Networks Using Change Centrality
  • Communities and Balance in Signed Networks: A Spectral Approach
  • A New Algorithm for Positive Influence Dominating Set in Social Networks
  • On Learning Cluster Coefficient of Private Networks
  • Fast Exact Computation of betweenness Centrality in Social Networks
ASONAM 2013
  • Hierarchical influence maximization for advertising in multi-agent markets
  • Incremental algorithm for updating betweenness centrality in dynamically growing networks
  • Modeling information diffusion and community membership using stochastic optimization
  • Estimation of exponential random graph models for large social networks via graph limits
  • Spectral embedding for dynamic social networks
  • Finding influencers in networks using social capital
  • An agent-based approach to modeling online social influence
  • Novel user influence measurement based on user interaction in microblog
COSN 2013
  • Hierarchical Community Decomposition Via Oblivious Routing Techniques
  • On the Performance of Percolation Graph Matching
COSN 2014
  • Computing Classic Closeness Centrality, at Scale
  • Spreading Rumours without the Network
  • Role of Conformity in Opinion Dynamics in Social Networks
  • Inferring Coarse Views of Connectivity in Very Large Graphs
CIKM 2014
  • Distributed Graph Summarization
    • Xingjie Liu (Penn State); Yuanyuan Tian (IBM); Qi He (Linkedin); Wang-Chien Lee (Penn State)
  • Pattern Match Query in a Large Uncertain Graph
    • Ye Yuan (Neu)
  • Efficient Probabilistic Supergraph Search over Large Uncertain Graphs
    • Yongxin Tong (HKUST); Caleb Chen CAO (HKUST); Lei Chen (HKUST)
  • Robust Entity Linking via Random Walks
    • Zhaochen Guo (University of Alberta); Denilson Barbosa ("University of Alberta, Canada")
  • Travel Distance versus Navigation Complexity: A Study on Different Spatial Queries on Road Networks
    • Jie Shao (UESTC); Lars Kulik (University of Melbourne); Egemen Tanin (University of Melbourne); Long Guo (National University of Singapore)
  • Query-Driven Mining of Citation Networks for Patent Citation Retrieval and Recommendation
    • Parvaz Mahdabi (University of Lugano); Fabio Crestani (University of Lugano)
  • Predicting Relationship Occurrence Time In Heterogeneous Networks Through Dynamic Frequent Prototype Network Mining
    • Yang Liu (NJIT); Songhua Xu (New Jersey Institute of Technology)
  • Supervised Nested PageRank
    • Maksim Zhukovskii (Yandex); Gleb Gusev (yandex); Pavel Serdyukov (Yandex)
  • Within-Network Classification Using Radius-Constrained Neighborhood Patterns
    • Jialong Han, Renmin Univerisity of China; Wen Ji-Rong, Renmin University of China; Jian Pei, "Simon Fraser University, Canada"
  • Graph-based Point-of-interest Recommendation with Geographical and Temporal Influences
    • Quan Yuan, Nanyang Technological Univ.; Gao Cong, "Nanyang Technological University, Singapore"; Aixin Sun, NTU
  • Influence Maximization over Large-Scale Social Networks: A Bounded Linear Approach
    • Qi Liu, USTC; Biao Xiang, ; Enhong Chen, University of Science and Technology of China; Hui Xiong, "Rutgers,the State University of New Jersey"; Fangshuang Tang, ; Jeffrey Xu Yu, CUHK
  • MapReduce Triangle Enumeration With Guarantees
    • Ha-Myung Park, KAIST; Francesco Silvestri, University of Padova, Italy; U Kang, KAIST; Rasmus Pagh, IT University of Copenhagen, Denmark
  • Efficient Subgraph Skyline Search Over Large Graphs
    • Weiguo Zheng, Peking university; Lei Zou, Beijing University; Xiang Lian, UTPA; Liang Hong, ; Dongyan Zhao,
  • Ranking-based Clustering on General Heterogeneous Information Networks by Network Projection
    • Chuan Shi, BUPT; Wang Ran, ; Yitong Li, BUPT
  • Learning a linear model of influence from transient opinion dynamics
    • Abir De, IIT Kharagpur; sourangshu Bhattacharya, IIT Kharagpur; Parantapa Bhattacharya, IIT Kharagpur; niloy Ganguly, IIT Kharagpur; Soumen Chakrabarti, IIT Bombay
  • Component Detection in Directed Networks
    • Yu-Keng Shih, ; Sungmin Kim, ; Yiye Ruan, The Ohio State University; Jinxing Cheng, ; Abhishek Gattani, ; Tao Shi, ; Srinivasan Parthasarathy
  • Sketch-based Influence Maximization and Computation: Scaling up with Guarantees
EDBT 2013
  • Efficient Breadth-First Search on Large Graphs with Skewed Degree Distributions
EDBT 2014
  • Reachability Queries in Very Large Graphs: A Fast Refined Online Search Approach
  • Distance oracles in edge-labeled graphs
  • Graph Analytics on Massive Collections of Small Graphs
  • Fast Reliability Search in Uncertain Graphs
  • CLUDE: An Efficient Algorithm for LU Decomposition Over a Sequence of Evolving Graphs
  • Spatial Partitioning of Large Urban Road Networks
  • L-opacity: Linkage-Aware Graph Anonymization
  • Privacy Risk in Anonymized Heterogeneous Information Networks
  • Diversified Spatial Keyword Search On Road Networks
  • Distributed Spatial Keyword Querying on Road Networks
ICDE 2011
  • Efficient Core Decomposition in Massive Networks
  • Mining Large Graphs: Algorithms, Inference, and Discoveries
  • Spectrum Based Fraud Detection in Social Networks
    • privacy
  • Decomposing DAGs into Spanning Trees: A New Way to Compress Transitive Closures
    • query proc.
  • Efficient Spectral Neighborhood Blocking for Entity Resolution
    • data mining
  • Consensus Spectral Clustering;
    • data mining
  • A New, Highly Efficient, and Easy To Implement Top-Down Join Enumeration Algorithm
    • best paper
ICDE 2012
  • An Efficient Graph Indexing Method
  • Community Detection with Edge Content in Social Media Networks
  • Efficient Graph Similarity Joins with Edit Distance Constraints
ICDE 2013
  • SociaLite: Datalog Extensions for Efficient Social Network Analysis
    • social
  • LinkProbe: Probabilistic Inference on Large-Scale Social Networks
    • social
  • Towards Efficient SimRank Computation on Large Graphs
  • Link Prediction across Networks by Biased Cross-Network Sampling
  • FERRARI: Flexible and Efficient Reachability Range Assignment for Graph Indexing
    • large graph
  • Top-k Graph Pattern Matching over Large Graphs
  • gIceberg: Towards Iceberg Analysis in Large Graphs
ICDE 2013
  • Efficient Search Algorithm for SimRank
ICDE 2014
  • A General Algorithm for Subtree Similarity-Search
  • Efficient Top-K Closeness Centrality Search
  • Contract & Expand: I/O Efficient SCCs computing
  • Efficient and Accurate Query Evaluation on Uncertain Graphs via Recursive Stratified Sampling
  • Subgraph Pattern Matching over Uncertain Graphs with Identity Linkage Uncertainty
  • Multi-Cost Optimal Route Planning under Time-Varying Uncertainty
  • Fast Incremental SimRank on Link-Evolving Graphs
ICDM 2012

Social Networks 1

  • Defining and Evaluating Network Communities based on Ground-truth
    • Leskovec
  • Community Preserving Lossy Compression of Social Networks
  • Spotting Culprits in Epidemics: How many and Which ones?
  • Detecting Anomalies in Bipartite Graphs with Mutual Dependency Principles
  • RankTopic: Ranking Based Topic Modeling
  • Automatically Discovering Talented Musicians with Acoustic Analysis of YouTube Videos

Privacy and Security

  • Reconstructing Graphs from Neighborhood Data
  • A General Framework for Publishing Privacy Protected and Utility Preserved Graph (Short)
  • Privacy-preserving SimRank over Distributed Information Network (Short)
  • Risks of Friendships on Social Networks (Short)

Clustering 2

  • Scalable and Memory-efficient Clustering of Large Scale Social Networks

Social Networks 2

  • Sequential Network Change Detection with Its Applications to Ad Impact Relation Analysis
  • Detecting Spam and Promoting Campaigns in the Twitter Social Network (Short)

Social Networks 3

  • Diffusion of Information in Social Networks: Is It All Local?
  • Clash of the Contagions: Cooperation and Competition in Information Diffusion
    • Leskovec
  • Link Prediction and Recommendation across Heterogenous Social Networks
  • Predicting Links in Multi-Relational and Heterogeneous Networks

Graphs and Networks

  • CT-IC: Continuously activated and Time-restricted Independent Cascade Model for Viral Marketing (Short)
  • Community-Affiliation Graph Model for Overlapping Network Community Detection (Short)
    • Leskovec
  • Mining User Mobility Features for Next Place Prediction in Location-based Services (Short)
  • Spatial Interpolation using Multiple Regression (Short)
ICDM 2013
  • http://icdm2013.rutgers.edu/schedule
  • CSI: Charged System Influence Model for Human Behavior Prediction
  • Massive Influence in Multiplex Social Networks: Model Representation and Analysis
  • Influence and Profit: Two Sides of the Coin
  • Validating Network Value of Influencers by means of Explanations

Social Network Analysis

  • Tree-like Structure in Social and Information Networks
  • An Efficient Approach to Updating Closeness Centrality and Average Path Length in Dynamic Networks

Graph and Network Mining

  • On Pattern Preserving Graph Generation
ICWSM 2010
  • Measuring User Influence in Twitter: The Million Follower Fallacy
ICWSM 2011
  • Modelling Action Cascades in Social Networks
  • Differential Adaptive Diffusion: Understanding Diversity and Learning Whom to Trust in Viral Marketing
  • Participation Maximization Based on Social Influence in Online Discussion Forums
  • What Stops Social Epidemics?
  • Sentiment Flow Through Hyperlink Networks
ICWSM 2012
  • Event Diffusion Patterns in Social Media
  • On the Study of Social Interactions in Twitter
  • Modeling Spread of Disease from Social Interactions
  • The YouTube Social Network
  • Automatic versus Human Navigation in Information Networks
IJCAI 2007
  • Web Page Clustering using Heuristic Search in the Web Graph
  • Edge Partitioning in External-Memory Graph Search
IJCAI 2011
  • Active Online Classification via Information Maximization
  • Context Sensitive Topic Models for Author Influence in Document Networks
IJCAI 2013
  • A global constrained optimization method for designing road networks with small diameters
  • Parameter Learning for Latent Network Diffusion
  • Graph Classification with Imbalanced Class Distributions and Noise
  • Large Scale Spectral Clustering on Graphs
  • Multiple Link Sign Prediction in Online Signed Social Networks
  • PageRank with Priori: An Influence Propagation Perspective
  • Retweet Behavior Understanding through Influence Locality Analysis
  • Online Community Detection for Very Large Complex Networks
INFOCOM 2012
  • TurfCast: A service for controlling information dissemination in wireless networks
  • Understanding the tempo-spatial limits of information dissemination in multi-channel Cognitive Radio Networks
  • Proactive seeding for information cascades in cellular networks
INFOCOM 2013
  • Providing probabilistic guarantees on the time of information spread in opportunistic networks
INFOCOM 2014
  • Maximizing the Value of Sensed Information in Underwater Wireless Sensor Networks via an Autonomous Underwater Vehicle
  • A Robust Information Source Estimator with Sparse Observations
INFOCOM 2015
  • measuring the mixing time of a network
  • cliques in hyperbolic random graphs
KDD 2005
  • Graphs over time: densification laws, shrinking diameters and possible explanations
KDD 2010
  • Community Outliers and their Efficient Detection in Information Networks
  • Fast Euclidean Minimum Spanning Tree: Algorithm, Analysis, Applications
KDD 2011
  • Triangle Listing in Massive Networks and Its Applications
KDD 2012
  • A Structural Cluster Kernel for Learning on Graphs
  • Discovering Value from Community Activity on Focused Question-Answering Sites: A Case Study of Stack Overflow
  • Efficient Personalized PageRank with Accuracy Assurance
  • Fast Algorithms for Maximal Clique Enumeration with Limited Memory
  • Feature Grouping and Selection Over an Undirected Graph
KDD 2013
  • Efficient Single-Source Shortest Path and Distance Queries on Large Graphs
  • Clustered Graph Randomization: Network Exposure to Multiple Universes
  • Mining Frequent Graph Patterns with Differential Privacy
  • Maximizing Acceptance Probability for Active Friending in On-Line Social Networks
NIPS
  • Scalable influence estimation in continuous-time diffusion networks
PODS 2012
  • Graph Sketches: Sparsification, Spanners, and Subgraphs
  • Approximating and Testing k-Histogram Distributions in Sub-linear Time
  • Worst-case Optimal Join Algorithms
  • Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates
  • Nearest-Neighbor Searching Under Uncertainty
  • Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks
PODS 2013
  • The Complexity of Mining Maximal Frequent Subgraphs
  • Nearest Neighbor Searching Under Uncertainty II
PODS 2014
  • All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis
    • Edith Cohen
  • Is Min-Wise Hashing Optimal for Summarizing Set Intersection?
  • The Input/Output Complexity of Triangle Enumeration
  • A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting
    • Yufei Tao
  • On Scale Independence for Querying Big Data
PODS 2008
SDM 2014
  • A Deep Learning Approach to Link Prediction in Dynamic Networks
  • Multi-Task Feature Selection on Multiple Networks via Maximum Flows
  • Local Learning for Mining Outlier Subgraphs from Network Datasets
SEA 2011
  • A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks
    • やはりそのうち読もう。
SEA 2013
  • Space-Efficient, High-Performance Rank & Select Structures
  • Hub Label Compression
  • Faster Customization of Road Networks
  • Dominator Certification and Independent Spanning Trees: An Experimental Study
  • Hypergraph Dualization Algorithm Based on Binary Decision Diagrams
  • Efficient Counting of Maximal Independent Sets in Sparse Graphs
SEA 2014
  • A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs
  • Implementation of the Iterative Relaxation Algorithm for the Minimum Bounded-Degree Spanning Tree Problem
  • Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth
  • Experimental Evaluation of Dynamic Shortest Path Tree Algorithms on Homogeneous Batches
  • Hub Labels: Theory and Practice
  • Efficient Wavelet Tree Construction and Querying for Multicore Architectures
  • Tree-based Coarsening and Partitioning of Complex Networks
  • Improved Upper and Lower Bound Heuristics for Degree Anonymization in Social Networks
  • Beyond Synchronous Computation: New Techniques for External Memory Graph Algorithms
  • Partitioning Complex Networks via Size-constrained Clustering
  • An Evaluation of Dynamic Labeling Schemes for Tree Networks
SIGIR 2014

Full
Indexing and Efficiency

  • Skewed Partial Bitvectors for List Intersection

How to Win Friends and Influence People

  • On Measuring Social Friend Interest Similarities in Recommender Systems
  • IMRank: Influence Maximization via Finding Self-Consistent Ranking
  • Leveraging Knowledge across Media for Spammer Detection in Microblogging

Short

  • Towards Context-Aware Search with Right Click
  • Sig-SR: SimRank Search over Singular Graphs
  • Influential Nodes Selection: A Data Reconstruction Perspective
  • Large-Scale Author Verification: Temporal and Topical Influences
  • Modeling Evolution of a Social Network using Temporal Graph Kernels
  • Inferring Topic-Dependent Influencing Roles of Twitter Users
SIGMOD 2011
  • Local Graph Sparsification for Scalable Clustering
  • Fast Personalized PageRank on MapReduce
  • Neighborhood Based Fast Graph Search in Large Networks
  • Assessing and Ranking Structural Correlations in Graphs
  • A memory efficient reachability data structure through bit vector compression
  • Incremental Graph Pattern Matching
  • On k-skip shortest paths
  • Sampling Based Algorithms for Quantile Computation in Sensor Networks
SIGMOD 2012
  • Towards Effective Partition Management for Large Graphs
  • Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach
  • SCARAB: Scaling Reachability Computation on Large Graphs
  • A Highway-Centric Labeling Approach for Answering Distance Queries on Large Graphs
SIGMOD 2013
  • Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice
    • 炎上
VLDB 2010
  • On Graph Query Optimization in Large Networks
    • r10_
VLDB 2011
  • Mining Top-K Large Structural Patterns in a Massive Network
    • r8
VLDB 2012
  • Dense Subgraph Maintenance under Streaming Edge Weight Updates for Real-time Story Identification
    • best paper
  • Truss Decomposition in Massive Networks
    • k-truss
VLDB 2013
  • Efficient SimRank-based Similarity Join Over Large Graphs
WSDM
  • Everyone's an Influencer Quantifying Influence on Twitter
WSDM 2012
  • Effects of User Similarity in Social Media
WSDM 2013
  • On the Streaming Complexity of Computing Local. Clustering Coefficients
  • Cascade-based Community Detection
  • Overlapping community detection at scale: A Nonnegative Matrix Factorization Approach
    • Leskovec
WSDM 2014
  • FENNEL: Streaming Graph Partitioning for Massive Scale Graphs
  • Learning Social Network Embeddings for Predicting Information Diffusion
  • Active Learning for Networked Data Based on Non-progressive Diffusion Model
  • Fast Approximation of Betweenness Centrality Through Sampling
  • The Last Click: Why Users Give up Information Network Navigation
    • 例のごとくLeskovec
  • Scalable k-Means
    • タイトルがシンプルすぎる…
  • Effective Co-betweenness Centrality Computation
  • Finding HeavyPaths in Weighted Graphs and a Case-Study on Core Community Detection
WSDM 2015
  • The Power of Random Neighbors in Social Networks
  • "Negative Link Prediction in Social Media"
  • "Finding Subgraphs with Maximum Total Density and Limited Overlap"
  • "Inverting a Steady-State"
  • "On Integrating Network and Community Discovery"
WWW
  • Who says what to whom on twitter
  • Empirical Comparison of Algorithms for Network Community Detection
WWW 2000
  • Graph Structure in the Web
    • best paper
WWW 2004
  • Information diffusion through blogspace
WWW 2012
  • Community Detection in Incomplete Information Networks
  • Distributed Graph Pattern Matching
  • Vertex Collocation Profiles: Subgraph Counting for Link Analysis and Prediction
WWW 2013
  • Predicting Positive and Negative Links in Signed Social Networks by Transfer Learning
  • Mining Structural Hole Spanners in Large Networks
  • What Is the Added Value of Negative Links in Online Social Networks?
WWW 2014
  • Random Walks based Modularity: Application to Semi-Supervised Learning by Robin Devooght, Amin Mantrach, Ilkka Kivimäki, Hugues Bersini, Alejandro Jaimes and Marco Saerens
  • High Quality, Scalable and Parallel Community Detection for Large Real Graph by Arnau Prat-Pérez, David Dominguez-Sal and Josep-Lluis Larriba-Pey
  • Dynamic and Historical Shortest-Path Distance Queries on Large Evolving Networks by Pruned Landmark Labeling by Takuya Akiba, Yoichi Iwata and Yuichi Yoshida
  • On Estimating the Average Degree by Anirban Dasgupta, Ravi Kumar and Tamas Sarlos
  • How information diffusion shapes social network structure by Seth Myers and Jue Leskovec
  • Can cascades be predicted? by Justin Cheng, Lada Adamic, Alex Dow, Jon Kleinberg and Jure Leskovec

?

  • Parameterized Approximability of Maximizing the Spread of Influence in Networks
KKKKKKKKKKKKKKKKKKKKKK
  • Towards Context-Aware Search by Learning A Very Large Variable Length Hidden Markov Model from Search Logs
    • WWW 2008
  • BBM: Bayesian Browsing Model from Petabyte-scale Data
  • Measuring Inter-Site Engagement
    • Y!
  • SIGIR 2007から
    • The Influence of Caption Features on Clickthrough Patterns in Web Search
    • Investigating the Querying and Browsing Behavior of Advanced Search Engine Users
    • Studying the Use of Popular Destinations to Enhance Web Search Interaction
Steiner Tree
  • Fast approximation of steiner trees in large graphs
  • STAR: Steiner-Tree Approximation in Relationship Graphs

めも

Estimate on Expectation for Influence Maximization in Social Networks.

By: Yao Zhang, Qing Gu, Jun Zheng, Daoxu Chen
In: PAKDD (1), 2010


In-time estimation for influence maximization in large-scale social networks.

By: Xiaodong Liu, Shanshan Li, Xiangke Liao, Lei Wang, Qingbo Wu
In: SNS, 2012


Information propagation game: a tool to acquire humanplaying data for multiplayer influence maximization on social networks.
KDD

AAAI-14に論文採択

旅先（WWW'14）での投稿なので，帰国後詳細を書きます．→書きました．(2014/04/14)→更に書き足しました．(2014/04/16)

論文がAAAI-14 (Twenty-Eighth Conference on Artificial Intelligence)に採択されました．

タイトルは``Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations''で，秋葉さん(同研究室)，吉田さん(NII)，河原林先生(NII)との共著で，非常にお世話になりました．一人では不可能でした．

AAAIはその名の通りAIに関する会議なのですが，実に非常に多岐に渡る内容をカバーしていると思います．提出論文数1406，採択論文数398，採択率28%という数字からもその多さがわかると思います．

今回の研究のメインはInfluence Maximization（影響最大化）という情報拡散に関する問題です．2003年に問題が定式化されて[KKT03]からしばらくはこの問題の高速化はなされてこなかったのですが，ここ数年（2009年位）から沢山の手法がCIKM,ICDM,ICDE,KDD,WWW等に出てくるようになりました．

今回の研究の貢献は，Influence Maximizationの高速手法で，既存のヒューリスティクスとほぼ同等の速度かつ理論的保証のある高精度の解を出力します．例えば，LiveJournal(|V|=4.8M, |E|=69M)を約10分で処理できます．今回提出した論文の元となる論文はICDE'14に出したのですが落ちてしまったので，再編しての挑戦となりました．2013年の時点で相当数の手法が提案されていたため，既存手法との明確な差別化が求められていました．さらに，非常に最近になってSIGMOD'14にも新しい高速手法が現れたので，この時点で通ってホッとしています．

Influence Maximizationって何？

日本語に直訳すると影響最大化（問題）になりますが，馴染みのある人は少ないと思います．主なモチベーションはバイラル（感染式）マーケティング[DR01,RD02]といって，少数の人に商品の無料サンプルを渡すことで，その（良い）噂が「口コミ」を通して多数の人に伝わっていくことを期待するものです．ソエンド(http://soen.do/contents/)は関連があると思います．また，馴染みのある近い文脈ではTwitter上のRT等があります．

情報拡散をグラフでモデル化すると，頂点が人，辺が人と人の関係を表します．頂点は活性化（影響された，RTした） or 非活性化（影響されてない，RTしてない）の2状態をもちます．非活性化→活性化には遷移しますが，逆は遷移しません．また，人と人の関係の強さというのは色々違ったりするので，各辺eに重み（確率）p_eを割り当てます．
対象となる情報拡散モデルは最も基本的なIndependent Cascade Model（独立カスケードモデル）[KKT03]というモデルです．このモデルは，最初に活性化させる人の集合（シード）を決めた後，次の確率的な情報拡散過程を繰り返します．

0. シードを活性化．
1. 新たに活性化した人は近傍の（非活性な）人を活性化させる試行を行う．この試行は指定された確率p_eで成功するが，失敗したらそれ以降試行しない．
2. 新たに活性化した人がいれば1.に戻る．

各辺を高々一回しか見ないので，↑の処理は有限時間内に終わります．最初に活性化させるターゲットSに対して平均で何人が活性化するかというのが影響力を表す指標としてとても気になるので，これをσ(S)で表し，influence spread（影響拡散）と呼ぶことにます．

最後にInfluence Maximizationを定式化すると，「有向グラフ・辺の確率・ターゲットの人数kが与えられるので，σを最大化するようなk人のシード集合を求めよ」という問題になります．

近似アルゴリズムとヤバい点

悲しいことに，Influence Maximizationは一般にNP-困難であることが証明されています[KKT03]．さらに，目的関数σの値の厳密計算が#P-困難であることも証明されています[CWW10]．しかし，それぞれの困難は貪欲アルゴリズムとMonte-Carloシミュレーションである程度解決できます．

貪欲アルゴリズム

この問題は目的関数が劣モジュラであるので貪欲アルゴリズムで簡単に1-1/e(≒63%)近似解が得られることが証明されています[NWF78]．
劣モジュラ関数とは，以下を満たす関数です．
S \subseteq T \subseteq \Omega,\; x \in \Omega,\; f(S+x)-f(S) \geq f(T+x)-f(T)
または，
S, T \subseteq \Omega,\; f(S)+f(T) \geq f(S \cup T)+f(S \cap T)
（等）が成り立つ．前者の意味を限界収穫逓減とか言ったりします．
貪欲アルゴリズムは，今の解をS（最初は空集合）とすると，σ(S+v)-σ(S)が最大となるvを取ってきて，Sに加えるという操作をk回繰り返すだけです．しかも，経験的には実際のネットワークではかなり最適解に近い解が計算できます．

Monte-Carloシミュレーション

Monte-Carloシミュレーションは，先の確率過程を沢山シミュレートして活性化した頂点数の平均値を計算し，σの近似値とします．シミュレーション回数をRとするとこの計算コストはO(mR)です．

ヤバい点

貪欲アルゴリズム+Monte-Carloシミュレーションによるアルゴリズムは63%近似解を出力します．これは嬉しい事ですが，貪欲アルゴリズムはσをkn回計算し，一回σを求めるのにO(Rm)くらいの計算コストがいるので，全体の計算コストはO(knmR)となります．

つまりヤバいのは，目的関数の計算コストと計算回数によって，計算量がグラフサイズの自乗以上になるという点にあります．

ですから，多くの既存手法はσの値を求めることに主眼を置いており，σの値を適当に近似するヒューリスティクスか，σの値をMonte-Carloシミュレーションで精度良く求める手法かに二分されてました．前者は速いけど精度が悪い，後者は精度が良いけど遅い，という問題があります．

貢献

今回の論文の手法はシミュレーションベースに相当します．とにかくシミュレーションを高速化，しかも精度を落とさないところがポイントです．

まず，コインフリップテクニックというテクニックを説明します．これはIndependent Cascade Modelのシミュレーションがランダムグラフ上の到達可能性検査に等価であることを示すものです．ラフに言うと，
1. 各辺が確率1-p_eで消えるようなランダムグラフを沢山生成します．
2. 各ランダムグラフにおいて，頂点集合Sから到達可能な頂点数の平均を計算します．BFSとかで．
で計算した値がσ(S)を近似します．

これだけだと，元のシミュレーションベースのアルゴリズムとほとんど変わらないので高速化手法を導入します．元の貪欲アルゴリズムは最悪計算量がO(kmnR)ですが，直感・実験的には，手法1がRの値を10000から100くらいのオーダーに減らし，手法2がmの値を100未満に減らし，手法3がkを10以下にまで抑える感じです．

高速化手法1: 生成する必要のあるグラフ数をbound

先ほどのように事前にランダムグラフを生成しておくと，毎回シミュレーションをするよりも生成すべきグラフ数（上図のパラメータR）を抑えることができます．このテクニックはStaticGreedy[CSH+13]という既存の手法が提案していましたが，今回はそれに理論的保証を与えました．

高速化手法2: 到達可能な頂点数計算の枝刈り

σ({v})を各頂点vについて求めることを考えます．各頂点からBFSをすれば求められますが，合計でn回BFSするので計算コストは最悪でO(n^2)位になります．ソーシャルネットワークでも，数百万頂点とかになると全然終わらないです．高速化手法では，n回のBFSで冗長な部分は省くことで探索頂点を大幅に減らしています．

高速化手法3: 不必要なゲインの再計算の抑制（省略）

こちらも到達可能な頂点数の計算をできるだけ抑制しています．

参考文献

[CWW10] W. Chen, C. Wang and Y. Wang. Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale Social Networks. In KDD 2010.
[CSH+13] S. Cheng, H. Shen, J. Huang, G. Zhang and X. Cheng. StaticGreedy: Solving the Scalability-Accuracy Dilemma in Influence Maximization. In CIKM 2013.
[DR01] P. Domingos and M. Richardson. Mining the Network Value of Customers. In KDD 2001.
[KKT03] D. Kempe, J. Kleinberg and É. Tardos. Maximizing the Spread of Influence through a Social Network. In KDD 2003.
[NWF78] G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 1978.
[RD02] M. Richardson and P. Domingos. Mining Knowledge-Sharing Sites for Viral Marketing. In KDD 2002.