Publications
カンファレンス (国際) Coarsening Massive Influence Networks for Scalable Diffusion Analysis
Naoto Ohsaka (The University of Tokyo), Tomohiro Sonobe (National Institute of Informatics), Sumio Fujita, Ken-Ichi Kawarabayashi (National Institute of Informatics)
ACM SIGMOD International Conference on Management of Data (SIGMOD 2017)
2017.5.14
Fueled by the increasing popularity of online social networks, social influence analysis has attracted a great deal of research attention in the past decade. The diffusion process is often modeled using influence graphs, and there has been a line of research that involves algorithmic problems in influence graphs. However, the vast size of today’s real-world networks raises a serious issue with regard to computational efficiency. In this paper, we propose a new algorithm for reducing influence graphs. Given an input influence graph, the proposed algorithm produces a vertex-weighted influence graph, which is compact and approximates the diffusion proper- ties of the input graph. The central strategy of influence graph reduction is coarsening, which has the potential to greatly reduce the number of edges by merging a vertex set into a single weighted vertex. We provide two imple- mentations; a speed-oriented implementation which runs in linear time with linear space and a scalability-oriented implementation which runs in practically linear time with sub-linear space. Further, we present general frameworks using our compact graphs that accelerate existing algorithms for influence maximization and influence estimation problems, which are motivated by practical applications, such as viral marketing. Using these frameworks, we can quickly obtain solutions that have accuracy guarantees under a reasonable assumption. Experiments with real-world networks demonstrate that the proposed algorithm can scale to billion-edge graphs and reduce the graph size to up to 4%. In addition, our influence maximization framework achieves four times speed-up of a state-of-the-art D-SSA algorithm, and our influence estimation framework cuts down the computation time of a simulation-based method to 3.5%.
Paper :
Coarsening Massive Influence Networks for Scalable Diffusion Analysis
（外部サイト）