Naoto Ohsaka
Abstract
We propose the first real-time fully-dynamic index data structure designed for influence analysis on evolving networks. With this aim, we carefully redesign the data structure of the state-of-the-art sketching method introduced by Borgs et al., and construct corresponding update algorithms. Using this index, we present algorithms for two kinds of queries, influence estimation and influence maximization, which are strongly motivated by practical applications, such as viral marketing. We provide a thorough theoretical analysis, which guarantees the non-degeneracy of the solution accuracy after an arbitrary number of updates. Furthermore, we introduce a reachability-tree-based technique and a skipping method, which greatly reduce the time consumption required for edge/vertex deletions and vertex additions, respectively, and counter-based random number generators, which improve the space efficiency.
Experimental evaluations using real dynamic networks with tens of millions of edges demonstrate the efficiency, scalability, and accuracy of our proposed indexing scheme. Specifically, it can reflect a graph modification within a time of several orders of magnitude smaller than that required to reconstruct an index from scratch, estimate the influence spread of a vertex set accurately within a millisecond, and select highly influential vertices at least ten times faster than state-of-the-art static algorithms.
- E. Adar and L. A. Adamic. Tracking information epidemics in blogspace. In WI, pages 207--214, 2005. Google Scholar
Digital Library
- A. Anagnostopoulos, R. Kumar, and M. Mahdian. Influence and correlation in social networks. In KDD, pages 7--15, 2008. Google ScholarDigital Library
- C. Borgs, M. Brautbar, J. Chayes, and B. Lucier. Maximizing social influence in nearly optimal time. In SODA, pages 946--957, 2014. Google ScholarDigital Library
- W. Chen, C. Wang, and Y. Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In KDD, pages 1029--1038, 2010. Google ScholarDigital Library
- W. Chen, Y. Wang, and S. Yang. Efficient influence maximization in social networks. In KDD, pages 199--208, 2009. Google ScholarDigital Library
- X. Chen, G. Song, X. He, and K. Xie. On influential nodes tracking in dynamic social networks. In SDM, pages 613--621, 2015.Google ScholarCross Ref
- J. Cheng, L. Adamic, P. A. Dow, J. M. Kleinberg, and J. Leskovec. Can cascades be predicted? In WWW, pages 925--936, 2014. Google ScholarDigital Library
- S. Cheng, H. Shen, J. Huang, G. Zhang, and X. Cheng. StaticGreedy: Solving the scalability-accuracy dilemma in influence maximization. In CIKM, pages 509--518, 2013. Google ScholarDigital Library
- P. Domingos and M. Richardson. Mining the network value of customers. In KDD, pages 57--66, 2001. Google ScholarDigital Library
- N. Du, L. Song, M. Gomez-Rodriguez, and H. Zha. Scalable influence estimation in continuous-time diffusion networks. In NIPS, pages 3147--3155, 2013. Google ScholarDigital Library
- J. Goldenberg, B. Libai, and E. Muller. Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing Letters, 12(3):211--223, 2001.Google ScholarCross Ref
- J. Goldenberg, B. Libai, and E. Muller. Using complex systems analysis to advance marketing theory development: Modeling heterogeneity effects on new product growth through stochastic cellular automata. Academy of Marketing Science Review, 9(3):1--18, 2001.Google Scholar
- A. Goyal, F. Bonchi, and L. V. Lakshmanan. Learning influence probabilities in social networks. In WSDM, pages 241--250, 2010. Google ScholarDigital Library
- K. Jung, W. Heo, and W. Chen. IRIE: Scalable and robust influence maximization in social networks. In ICDM, pages 918--923, 2012. Google ScholarDigital Library
- D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. In KDD, pages 137--146, 2003. Google ScholarDigital Library
- M. Kimura, K. Saito, and R. Nakano. Extracting influential nodes for information diffusion on a social network. In AAAI, pages 1371--1376, 2007. Google ScholarDigital Library
- R. Kumar, J. Novak, and A. Tomkins. Structure and evolution of online social networks. In Link Mining: Models, Algorithms, and Applications, pages 337--357. Springer, 2010.Google ScholarCross Ref
- J. Leskovec, J. Kleinberg, and C. Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data, 1(1):2, 2007. Google ScholarDigital Library
- J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Cost-effective outbreak detection in networks. In KDD, pages 420--429, 2007. Google ScholarDigital Library
- B. Lucier, J. Oren, and Y. Singer. Influence at scale: Distributed computation of complex contagion in networks. In KDD, pages 735--744, 2015. Google ScholarDigital Library
- M. Minoux. Accelerated greedy algorithms for maximizing submodular set functions. Optimization Techniques, 7:234--243, 1978.Google ScholarCross Ref
- S. A. Myers, C. Zhu, and J. Leskovec. Information diffusion and external influence in networks. In KDD, pages 33--41, 2012. Google ScholarDigital Library
- G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 14:265--294, 1978.Google ScholarDigital Library
- N. Ohsaka, T. Akiba, Y. Yoshida, and K. Kawarabayashi. Fast and accurate influence maximization on large networks with pruned monte-carlo simulations. In AAAI, pages 138--144, 2014. Google ScholarDigital Library
- M. Richardson and P. Domingos. Mining knowledge-sharing sites for viral marketing. In KDD, pages 61--70, 2002. Google ScholarDigital Library
- K. Saito, R. Nakano, and M. Kimura. Prediction of information diffusion probabilities for independent cascade model. In KES, pages 67--75, 2008. Google ScholarDigital Library
- J. K. Salmon, M. A. Moraes, R. O. Dror, and D. E. Shaw. Parallel random numbers: as easy as 1,2,3. In SC, pages 1--12, 2011. Google ScholarDigital Library
- Y. Tang, Y. Shi, and X. Xiao. Influence maximization in near-linear time: A martingale approach. In SIGMOD, pages 1539--1554, 2015. Google ScholarDigital Library
- Y. Tang, X. Xiao, and Y. Shi. Influence maximization: Near-optimal time complexity meets practical efficiency. In SIGMOD, pages 75--86, 2014. Google ScholarDigital Library
- Y. Wang, G. Cong, G. Song, and K. Xie. Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In KDD, pages 1039--1048, 2010. Google ScholarDigital Library
- H. Zhuang, Y. Sun, J. Tang, J. Zhang, and X. Sun. Influence maximization in dynamic social networks. In ICDM, pages 1313--1318, 2013.Google ScholarCross Ref
Index Terms
- Dynamic influence analysis in evolving networks
Recommendations
Coarsening Massive Influence Networks for Scalable Diffusion Analysis
SIGMOD '17: Proceedings of the 2017 ACM International Conference on Management of DataFueled 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 ...
3-dynamic coloring and list 3-dynamic coloring of K1,3-free graphs
For positive integers k and r, a (k,r)-coloring of a graph G is a proper coloring of the vertices with k colors such that every vertex of degree i will be adjacent to vertices with at least min{i,r} different colors. The r-dynamic chromatic number of G, ...
Dynamic coloring and list dynamic coloring of planar graphs
A dynamic coloring of a graph G is a proper coloring of the vertex set V(G) such that for each vertex of degree at least 2, its neighbors receive at least two distinct colors. The dynamic chromatic number@g"d(G) of a graph G is the least number k such ...
Comments