Takanori Maehara
ABSTRACT
Evaluating influence spread in social networks is a fundamental procedure to estimate the word-of-mouth effect in viral marketing. There are enormous studies about this topic; however, under the standard stochastic cascade models, the exact computation of influence spread is known to be #P-hard. Thus, the existing studies have used Monte-Carlo simulation-based approximations to avoid exact computation.
We propose the first algorithm to compute influence spread exactly under the independent cascade model. The algorithm first constructs binary decision diagrams (BDDs) for all possible realizations of influence spread, then computes influence spread by dynamic programming on the constructed BDDs. To construct the BDDs efficiently, we designed a new frontier-based search-type procedure. The constructed BDDs can also be used to solve other influence-spread related problems, such as random sampling without rejection, conditional influence spread evaluation, dynamic probability update, and gradient computation for probability optimization problems.
We conducted computational experiments to evaluate the proposed algorithm. The algorithm successfully computed influence spread on real-world networks with a hundred edges in a reasonable time, which is quite impossible by the naive algorithm. We also conducted an experiment to evaluate the accuracy of the Monte-Carlo simulation-based approximation by comparing exact influence spread obtained by the proposed algorithm.
- C. Borgs, M. Brautbar, J. Chayes, and B. Lucier. Maximizing social influence in nearly optimal time. In SODA, pages 946--957, 2014. Google Scholar
Digital Library
- T. B. Brecht and C. J. Colbourn. Lower bounds on two-terminal network reliability. Discrete Applied Mathematics, 21(3):185--198, 1988. Google ScholarDigital Library
- R. E. Bryant. Graph-based algorithms for boolean function manipulation. Transactions on Computers, 100(8):677--691, 1986. 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
- 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
- E. Cohen, D. Delling, T. Pajor, and R. F. Werneck. Sketch-based influence maximization and computation: Scaling up with guarantees. In CIKM, pages 629--638, 2014. Google ScholarDigital Library
- P. Domingos and M. Richardson. Mining the network value of customers. In KDD, pages 57--66, 2001. Google ScholarDigital Library
- S. Even, A. Itai, and A. Shamir. On the complexity of time table and multi-commodity flow problems. In FOCS, pages 184--193, 1975. 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, 2001:1, 2001.Google Scholar
- A. Goyal, W. Lu, and L. V. Lakshmanan. Simpath: An efficient algorithm for influence maximization under the linear threshold model. In ICDM, pages 211--220, 2011. Google ScholarDigital Library
- G. Hardy, C. Lucet, and N. Limnios. Computing all-terminal reliability of stochastic networks with binary decision diagrams. In ASMDA, pages 17--20. Citeseer, 2005.Google Scholar
- K. Inoue, T. Sato, M. Ishihata, Y. Kameya, and H. Nabeshima. Evaluating abductive hypotheses using an em algorithm on bdds. In IJCAI, pages 810--815, 2009. Google ScholarDigital Library
- Y. Inoue and S. Minato. Acceleration of ZDD construction for subgraph enumeration via path-width optimization. TCS-TR-A-16-80. Hokkaido University, 2016.Google Scholar
- M. Ishihata, Y. Kameya, T. Sato, and S. Minato. Propositionalizing the em algorithm by bdds. In Late Breaking Papers of the 18th International Conference on Inductive Logic Programming, pages 44--49, 2008.Google Scholar
- M. Ishihata and T. Sato. Bayesian inference for statistical abduction using markov chain monte carlo. In ACML, pages 81--96, 2011.Google Scholar
- J. Kawahara, T. Inoue, H. Iwashita, and S. Minato. Frontier-based search for enumerating all constrained subgraphs with compressed representation. TCS-TR-A-13-64. Hokkaido University, 2014.Google Scholar
- D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. In KDD, pages 137--146, 2003. Google ScholarDigital Library
- N. G. Kinnersley. The vertex separation number of a graph equals its path-width. Information Processing Letters, 42(6):345--350, 1992. Google ScholarDigital Library
- D. Knuth. The art of computer programming: Bitwise tricks & techniques; binary decision diagrams, volume 4, fascicle 1, 2009. 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
- S. Minato, N. Ishiura, and S. Yajima. Shared binary decision diagram with attributed edges for efficient boolean function manipulation. In DAC, pages 52--57, 1990. Google ScholarDigital Library
- G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions?i. Mathematical Programming, 14(1):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
- N. Ohsaka, T. Akiba, Y. Yoshida, and K. Kawarabayashi. Dynamic influence analysis in evolving networks. VLDB, 9(12):1077--1088, 2016. 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. Sekine, H. Imai, and S. Tani. Computing the tutte polynomial of a graph of moderate size. In International Symposium on Algorithms and Computation, pages 224--233. Springer, 1995. Google ScholarDigital Library
- D. Sieling and I. Wegener. Reduction of obdds in linear time. Information Processing Letters, 48(3):139--144, 1993. 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
- L. G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410--421, 1979.Google ScholarDigital Library
- Z. Yan, C. Nie, R. Dong, X. Gao, and J. Liu. A novel OBDD-based reliability evaluation algorithm for wireless sensor networks on the multicast model. Mathematical Problems in Engineering, 2015, 2015.Google Scholar
- R. Yoshinaka, T. Saitoh, J. Kawahara, K. Tsuruma, H. Iwashita, and S.-i. Minato. Finding all solutions and instances of numberlink and slitherlink by zdds. Algorithms, 5(2):176--213, 2012.Google ScholarCross Ref
Index Terms
- Exact Computation of Influence Spread by Binary Decision Diagrams
Recommendations
Limiting Concept Spread in Environments with Interacting Concepts
AAMAS '17: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent SystemsThe propagation of concepts in a population of agents is a form of influence spread, which can be modelled as a cascade from an initial set of individuals. In real-world environments there may be many concepts spreading and interacting. Previous work ...
User spread influence measurement in microblog
With the popular of online social network, the studies of information diffusion on social media also become very attractive direction. Knowing the influence of users and being able to predict it can be very helpful in enhancing or controlling the ...
A parameterizable influence spread-based centrality measure for influential users detection in social networks
AbstractIn social network analysis, centrality refers to the relevance of actors or nodes within a social network represented as a graph. Traditional centrality measures are based on topological aspects of the network or the information flow ...
Highlights- We propose a new centrality measure based on influence spread models.
- This ...
Comments