Weitere Artikel dieser Ausgabe durch Wischen aufrufen
Portions of this work appeared as a short paper in AAMAS 2013.
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.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
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.
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. MATH
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. CrossRef
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. CrossRef
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.
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. CrossRef
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. CrossRef
Golden, Joseph H., & Adams, Christopher R. (2000). The tornado problem: Forecast, warning, and response. Natural Hazards Review, 1(2), 107–118. CrossRef
Granovetter, Mark. (1978). Threshold models of collective behavior. American Journal of Sociology, 83(6), 1420–1443. CrossRef
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.
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. CrossRef
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. CrossRef
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. CrossRef
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. CrossRef
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. CrossRef
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. CrossRef
Lindell, M. K., & Perry, R. W. (2004). Communicating environmental risk in multiethnic communities, communicating effectively in multicultural contexts. Thousand Oaks, CA: Sage Publications.
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. CrossRef
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. CrossRef
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. CrossRef
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. CrossRef
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. CrossRef
Valente, Thomas W. (1996). Network models of the diffusion of innovations. Computational & Mathematical Organization Theory, 2, 163–164. CrossRef
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.
- Seeding influential nodes in non-submodular models of information diffusion
- Springer US
Neuer Inhalt/© ITandMEDIA