Abstract
We consider the model of information diffusion in social networks from Hui et al. (Agentbased simulation of the diffusion of warnings, 2010) which incorporates trust (weighted links) between actors, and allows actors to actively participate in the spreading process, specifically through the ability to query friends for additional information. This model captures how social agents transmit and act upon information more realistically as compared to the simpler threshold and cascade models. However, it is more difficult to analyze, in particular with respect to seeding strategies. We present efficient, scalable algorithms for determining good seed sets—initial nodes to inject with the information. Our general approach is to reduce our model to a class of simpler models for which provably good sets can be constructed. By tuning this class of simpler models, we obtain a good seed set for the original more complex model. We call this the projected greedy approach because a model is ‘projected’ onto a class of simpler models where the greedy seed set selection is near-optimal. We demonstrate the effectiveness of our seeding strategy on synthetic graphs as well as a realistic San Diego evacuation network constructed during the 2007 fires, and the DBLP network of collaborations.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
Choosing a seed set to maximize a diffusion belongs to the class of NP-hard problems, a class for which there are no known efficient procedures. A procedure is efficient if it runs in time that is polynomial in the size of the social network. For practical purposes an algorithm that takes longer than the cube of the network size is already not feasible on population scale networks. Since the only known algorithms that maximize a diffusion are exponential, such algorithms are far from feasible.
A node here is assumed to fuse all the information received from the same source into a single value, and thus cannot get “overwhelmed” or “congested” with too much information.
For example if, when a node \(u_i\) propagates an information-value set to \({u}_{j}\), it is received at the other end with some probability \(p(i,j)\) depending on the communication infrastructure, then the number of nodes which are ultimate believers is a random variable.
References
Aguirre, B. E. (1994). Planning, warning, evacuation, and search and rescue: A review of the social science research literature. College Station, TX: Hazard Reduction & Recovery Center.
Albert, R., & Barabási, A.-L. (2002). Statistical mechanics of complex networks. Reviews of Modern Physics, 74, 47–97.
Amman, H. M., Tesfatsion, L., Judd, K. L., Kendrick, D. A., & Rust, J. (2006). Handbook of computational economics: Agent-based computational economics, chapter agent-based models of innovation and technological change. Elsevier: Handbooks in Economics.
Bailey, Norman. (1975). The mathematical theory of infectious diseases and its applications. London: Griffin.
Barabási, A. L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286, 509–512.
Bass, Frank M. (1969). A new product growth for model consumer durables. Management Science, 15(5), 215–227.
Berger, T. (2001). Agent-based spatial models applied to agriculture: A simulation tool for technology diffusion, resource use changes and policy analysis. Agricultural Economics, 25(2–3):245–260, 2001. Increasing Efficiency in Production, Research, Markets and Environmental Management. Selected and edited papers presented during the XXIV Conference of the International Association of Agricultural Economists.
Bonabeau, E. (2002). Agent-based modeling: Methods and techniques for simulating human systems. Proceedings of the National Academy of Sciences, 99(Suppl 3), 7280.
Calinescu, Gruia, Chekuri, Chandra, Pál, Martin, & Vondrák, Jan. (2011). Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6), 1740–1766.
Chellappa, R., & Jain, A. (Eds.). (1993). Markov random fields: Theory and application. Waltham, MA: Academic Press.
Chopra, K., & Wallace, W. A. (2000). Modeling relationships among multiple graphical structures. Computational and Mathematical Organization Theory, 6(4), 361–380.
Chopra, K., & Wallace, W. A. (2003). Trust in electronic environments. Proceedings of the 36th Hawaii International Conference on Systems Science, Hawaii.
Committee on Disaster Research in the Social Sciences: Future Challenges and Opportunities, National Research Council. (2006). Facing hazards and disasters: Understanding human dimensions. Washinton, D.C.: The National Academies Press.
Delre, Sebastiano A., Jager, Wander, & Janssen, Marco A. (2007). Diffusion dynamics in small-world networks with heterogeneous consumers. Computational and Mathematical Organization Theory, 13(2), 185–202.
Ding, Amy Wenxuan. (2006). A theoretical model of public response to the homeland security advisory system. The Journal of Defense Modeling and Simulation, 3(1), 45–55.
Fisher, M. L., Nemhauser, G. L., & Wolsey, L. A. (1978). An analysis of approximations for maximizing submodular set functions, II. In M. L. Balinski & A. J. Hoffman (Eds.), Polyhedral combinatorics, volume 8 of mathematical programming studies (pp. 73–87). Philadelphia, PA: Springer, Berlin Heidelberg.
Golden, Joseph H., & Adams, Christopher R. (2000). The tornado problem: Forecast, warning, and response. Natural Hazards Review, 1(2), 107–118.
Granovetter, Mark. (1978). Threshold models of collective behavior. American Journal of Sociology, 83(6), 1420–1443.
Gruhl, D., Guha, R., Liben-Nowell, D., & Tomkins, A. (2004). Information diffusion through blogspace. In Proceedings of the 13th International Conference on World Wide Web, WWW ’04 (pp. 491–501). New York, NY: ACM.
Hill, Shawndra, Provost, Foster, & Volinsky, Chris. (2006). Network-based marketing: Identifying likely adopters via consumer networks. Statistical Science, 21, 256–276.
Hui, C. (2011). Modeling the diffusion of information in dynamic social and communication networks. PhD thesis, Decision Science and Engineering System, Rensselaer Polymer Institute, Troy, NY.
Hui, C., Goldberg, M., Magdon-Ismail, M., Wallace, & William A. (2010). Agent-based simulation of the diffusion of warnings. In Proceedings of the 2010 Spring Simulation Multiconference, SpringSim ’10, (pp. 9:1–9:8). San Diego, CA: Society for Computer Simulation International.
Hui, Cindy, Goldberg, Mark, Magdon-Ismail, Malik, & Wallace, William A. (2010). Simulating the diffusion of information: An agent-based modeling approach. International Journal of Agent Technologies and Systems (IJATS), 2(3), 31–46.
Hui, C., Magdon-Ismail, M., Wallace, W. A., & Goldberg, M. (2010). Importance of ties in information diffusion. Poster presentation at Workshop on Information In Networks (WIN).
Iribarren, Jose Luis, & Moro, Esteban. (2009). Information diffusion epidemics in social networks. Physics Review Letter, 103, 038702.
Java, A., Kolari, P., Finin, T., & Oates, T. (2006). Modeling the spread of influence on the blogosphere. Technical report : University of Maryland, Baltimore County, Baltimore, MD.
Kelton, Kari, Fleischmann, Ken R., & Wallace, William A. (2008). Trust in digital information. Journal of American Society for Information Science and Technology, 57(3), 363–374.
Kempe, D., Kleinberg, J., & Tardos, Éva. (2003). Maximizing the spread of influence through a social network. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’03, (pp. 137–146). New York, NY: ACM.
Kempe, David, Kleinberg, Jon, & Tardos, Éva. (2006). Influential nodes in a diffusion model for social networks. Automata Languages and Programming, 3580(1), 99–120.
Krause, A., Leskovec, J., Guestrin, C., VanBriesen, J., & Faloutsos, C. (2008). Efficient sensor placement optimization for securing large water distribution networks. Journal of Water Resources Planning and Management, 134(6), 516–526. (Draft; full version available here.
Leskovec, J. (2013). Dblp collaboration network and ground-truth communities.
Leskovec, J., Adamic, L. A., & Huberman, B. A. (2007). The dynamics of viral marketing. ACM Trans. Web, 1, May 2007.
Leskovec, J., Singh, A., & Kleinberg, J. (2006). Patterns of influence in a recommendation network. In Proceedings of the 10th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD’06, (pp. 380–389). Singapore: Springer.
Lindell, M. K., & Prater, C. S. (2004). Estimating evacuation time components: Lessons from nuclear power plants, hurricanes, and the first world trade center bombing. In National Institute for Standards and Technology Workshop on Building Occupant Movement During Fire Emergencies, pp. 91–95, Gaithersburg, MD.
Lindell, M. K., & Prater, Carla S. (2007). Critical behavioral assumptions in evacuation time estimate analysis for private vehicles: Examples from hurricane research and planning. Journal of Urban Planning and Development, 133(1), 18–29.
Lindell, Michael K., Prater, Carla S., & Peacock, Walter Gillis. (2007). Organizational communication and decision making for hurricane emergencies. Natural Hazards Review, 8(3), 50–60.
Lindell, M. K., & Perry, R. W. (2004). Communicating environmental risk in multiethnic communities, communicating effectively in multicultural contexts. Thousand Oaks, CA: Sage Publications.
Ma, T., & Nakamori, Y. (2005). Agent-based modeling on technological innovation as an evolutionary process. European Journal of Operational Research, 166(3), 741–755. Advances in Complex Systems Modeling.
Mileti, Dennis. (1999). Disasters by design: A reassessment of natural hazards in the United States. Washington, DC: The National Academies Press.
Monge, P., & Contractor, N. (2003). Theories of communication networks. New York: Oxford University Press.
Neri, F. (2004). Agent based simulation of information diffusion in a virtual market place. In Proceedings. IEEE/WIC/ACM International Conference on Intelligent Agent Technology, 2004, (pp. 333–336).
Newman, M. E. J. (2002). The spread of epidemic disease on networks. Physics Review Letter, 66, 016128.
Nowak, M. A., & May, R. M. (2000). Virus dynamics: Mathematical principles of immunology and virology (Vol. 291). Oxford: Oxford University Press.
Perez, L., & Dragicevic, S. (2009). An agent-based approach for modeling dynamics of contagious disease spread. International Journal of Health Geographics, 8, 50.
Perry, Ronald W., & Lindell, Michael K. (2003). Understanding citizen response to disasters with implications for terrorism. Journal of Contingencies and Crisis Management, 11(2), 49–60.
Perry, Ronald W., Lindell, Michael K., & Greene, Marjorie R. (1982). Crisis communications: Ethnic differentials in interpreting and acting on disaster warnings. Social Behavior and Personality, 10(1), 97–104.
Perry, R. W., & Mushkatel, A. H. (2008). Minority citizens in disasters. Athens, GA: University of Georgia Press.
Rogers, G. O., & Sorensen, J. H. (1991). Risk analysis prospects and opportunities, chapter diffusion of emergency warning: Comparing empirical and simulation results. New York: Plenum Press.
Schwarz, N., & Ernst, A. (2009). Agent-based modeling of the diffusion of environmental innovations: An empirical approach. Technological Forecasting and Social Change, 76(4):497–511, 2009. Evolutionary Methodologies for Analyzing Environmental Innovations and the Implications for Environmental Policy.
Sorensen, J. H. (2000). Hazard warning systems: Review of 20 years of progress. Natural Hazards Review, 1(2), 119–125.
Sorensen, J. H. (2003). Modeling human response to a chemical weapons accident. In: DIMACS Working Group on Modeling Social Responses to Bio-terrorism Involving Infectious Agents, New Bruncswick, NJ.
Sorensen, J. H., & Mileti, D. S. (1987). Decision-making uncertainies in emergency warning system organizations. International Journal of Mass Emergencies and Disasters, 5(1), 33–61.
Sorensen, J.H., United States. Dept. of Energy, Martin Marietta Energy Systems Inc., Oak Ridge National Laboratory. (1992). Assessment of the need for dual indoor/outdoor warning systems and enhanced tone alert technologies in the Chemical Stockpile Emergency Preparedness Program. Oak Ridge, Tennessee: Oak Ridge National Laboratory.
Sorensen, J. H., Vogt, B. M., & Mileti, D. S. (1987). Evacuation: An assessment of planning and research. Oak Ridge, TN: Oak Ridge National Laboratory.
Strang, David, & Soule, Sarah A. (1998). Diffusion in organizations and social movements: From hybrid corn to poison pills. Annual Review of Sociol, 24(1), 265–290.
Valente, Thomas W. (1996). Network models of the diffusion of innovations. Computational & Mathematical Organization Theory, 2, 163–164.
Wan, X., Yang, J. (2007). Learning information diffusion process on the web. In Proceedings of the 16th International Conference on World Wide Web, WWW ’07, (pp. 1173–1174). New York, NY: ACM.
Yang, J., & Leskovec, J. (2012). Defining and evaluating network communities based on ground-truth. In Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, MDS ’12, (pp. 3:1–3:8). New York, NY: ACM.
Young, H. P. (2000). The diffusion of innovations in social networks. Economics Working Paper Archive 437, The Johns Hopkins University, Department of Economics, May 2000.
Acknowledgments
Anshelevich was partially supported by NSF grants CCF-0914782, CNS-1017932, and CCF-1101495 and Magdon-Ismail was partially supported by the Army Research Laboratory under Cooperative Agreement Number W911NF-09-2-0053.
Author information
Authors and Affiliations
Corresponding author
Additional information
Portions of this work appeared as a short paper in AAMAS 2013.
Rights and permissions
About this article
Cite this article
Anshelevich, E., Hate, A. & Magdon-Ismail, M. Seeding influential nodes in non-submodular models of information diffusion. Auton Agent Multi-Agent Syst 29, 131–159 (2015). https://doi.org/10.1007/s10458-014-9254-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10458-014-9254-4