The web as an adaptive network: coevolution of web behavior and web structure

ABSTRACT

Much is known about the complex network structure of the Web, and about behavioral dynamics on the Web. A number of studies address how behaviors on the Web are affected by different network topologies, whilst others address how the behavior of users on the Web alters network topology. These represent complementary directions of influence, but they are generally not combined within any one study. In network science, the study of the coupled interaction between topology and behavior, or state-topology coevolution, is known as 'adaptive networks', and is a rapidly developing area of research. In this paper, we review the case for considering the Web as an adaptive network and several examples of state-topology coevolution on the Web. We also review some abstract results from recent literature in adaptive networks and discuss their implications for Web Science. We conclude that adaptive networks provide a formal framework for characterizing processes acting 'on' and 'of' the Web, and offers potential for identifying general organizing principles that seem otherwise illusive in Web Science.

References

1. Watts, D. J. and Strogatz, S. H. Collective dynamics of 'small-world' networks. 1998. Nature, 393, 6684, 440--442.
2. Bárabasi, A. L. A., R. Emergence of Scaling in Random Networks. 1999. Science, 286, 5439, 509--512.
3. Newman, M. E. J. 2001. Clustering and preferential attachment in growing networks. Physical Review E, 64, 2, 025102.
4. Girvan, M. and Newman, M. E. J. Community structure in social and biological networks. 2002. Proceedings of the National Academy of Sciences, 99, 12, 7821--7826.
5. Mislove, A., Marcon, M., Gummadi, K. P., Druschel, P. and Bhattacharjee, B. Measurement and analysis of online social networks. 2007. In Proceedings of the 7th ACM SIGCOMM conference on Internet measurement San Diego, California, USA.
6. Dawkins, R. The Selfish Gene. 1989. Oxford University Press.
7. Leskovec, J., Backstrom, L. and Kleinberg, J. Memetracking and the dynamics of the news cycle. 2009. In Proceedings of 15th ACM SIGKDD Int. Conf. on Knowledge discovery and data mining. Paris, France.
8. Wu, S., Hofman, J. M., Mason, W. A. and Watts, D. J. Who says what to whom on twitter. 2011. In Proceedings of the WWW (2011). ACM, New York, USA.
9. Java, A., Song, X., Finin, T. and Tseng, B. 2007. Why we twitter: understanding microblogging usage and communities. In Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis. San Jose, California.
10. Letierce, J., Passant, A., Breslin, J. and Decker, S. 2010. Understanding how Twitter is used to spread scientific messages, In: Proceedings of the WebSci10: Extending the Frontiers of Society On-Line (April 26--27, 2010) Raleigh, NC, USA.
11. Onnela, J.-P. and Reed-Tsochas, F. Spontaneous emergence of social influence in online systems. 2010. Proceedings of the National Academy of Sciences (October 11, 2010)
12. Centola, D. 2010. The Spread of Behavior in an Online Social Network Experiment. Science, 329, 5996 (September 3, 2010), 1194--1197.
13. Kempe, D., Kleinberg, J. M. and Tardos, É. 2005. Influential nodes in a diffusion model for social networks. Computer, 3580, 1127--1138. Springer. 3580, 1127--1138. Springer.
14. Leskovec, J., Adamic, L. A. and Huberman, B. A. 2006. The dynamics of viral marketing. In Proceedings of the 7th ACM conference on Electronic commerce. Ann Arbor, Michigan, USA.
15. Liu, Y.-Y., Slotine, J.-J. and Bárabasi, A.-L. 2011. Controllability of complex networks. Nature, 473, 7346, 167--173.
16. Jin, E. M., Girvan, M. and Newman, M. E. J. 2001. Structure of growing social networks. Physical Review E, 64, 4, 046132.
17. Dorogovtsev, S. N., Mendes, J. F. F. and Samukhin, A. N. 2000. Structure of Growing Networks with Preferential Linking. Physical Review Letters, 85, 21, 4633.
18. Kossinets, G. and Watts, D. J. Empirical Analysis of an Evolving Social Network. 2006. Science, 311, 5757 (January 6 2006) 88--90.
19. Liben-Nowell, D. and Kleinberg, J. 2007. The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology, 58, 7. 1019--1031.
20. Backstrom, L., Huttenlocher, D., Kleinberg, J. and Lan, X.2006. Group formation in large social networks: membership, growth, and evolution. In Proceedings. of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. Philadelphia, PA, USA.
21. Chen, J., Geyer, W., Dugan, C., Muller, M. and Guy, I. Make new friends, but keep the old: recommending people on social networking sites. 2009. In Proceedings of the 27th international conference on Human factors in computing systems. (April 4-9, 2009) Boston, MA, USA.
22. Brzozowski, M. J. and Romero, D. M. 2011. Who Should I Follow? Recommending People in Directed Social Networks. In Proceedings of CSCW2011 (March 19-23, 2011) Hangzhou, China.
23. McPherson, M., Lovin, L. and Cook, J. 2001. Birds of a Feather: Homophily in Social Networks. Annual Review of Sociology, 27, 1, 415--444.
24. Gross, T. and Sayama, H. 2009. Adaptive Networks. Springer-Verlag: Berlin
25. Gross, T. and Blasius, B. 2008. Adaptive coevolutionary networks: a review. Journal of The Royal Society Interface, 5, 20, 259--271.
26. Halford, S., Pope, C. and Carr, L. 2010. A Manifesto for Web Science In Proceedings of the WebSci10: Extending the Frontiers of Society On-Line (Raleigh, NC: US., April 26-27, 2010).
27. Lee, T., Hall, W., Hendler, J., O'Hara, K., Shadbolt, N. and Weitzner, D. A 2006. Framework for Web Science. Foundations and Trends in Web Science, 1--130.
28. Hendler, J., Shadbolt, N., Hall, W., Berners-Lee, T. and Weitzner, D. 2008. Web Science: An Interdisciplinary Approach to Understanding the Web. Communications of the ACM, 51, 7, 60--69.
29. Jackson, M. O. and Watts, A. 2002. A. On the formation of interaction networks in social coordination games.. Games and Economic Behavior 41, 2, 265.
30. Pacheco, J. M., Traulsen, A. and Nowak, M. A. 2006. Coevolution of Strategy and Structure in Complex Networks with Dynamical Linking. Physical Review Letters, 97, 25, 258103.
31. Herrera, J. L., Cosenza, M. G. and Tucci, K. 2011. General coevolution of topology and dynamics in networks. 2011. arXiv preprint arXiv:1102.3467.
32. Sayama, H. Call for papers: workshop on "State-Topology Coevolution in Adaptive Networks" (STCAN 2011). In Proceedings of the as part of the Eighth International Conference on Complex Systems (ICCS 2011) (Feb. 2011)
33. Berlingerio, M., Bonchi, F., Bj Bringmann, R. and Gionis, A. 2009. Mining Graph Evolution Rules. In Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases: Part I (Bled, Slovenia, 2009). Springer-Verlag,
34. Kleinberg, J., Suri, S., Tardos, É. and Wexler, T. 2008. Strategic network formation with structural holes. SIGecom Exch., 7, 3, 1--4.
35. Van Segbroeck, S., Santos, F. C., Lenaerts, T. and Pacheco, J. M. Reacting Differently to Adverse Ties Promotes Cooperation in Social Networks. 2009. Physical Review Letters, 102, 5, 058105.
36. Boccaletti, S., Latora, V., Moreno, Y., Chavez, M. and Hwang, D.-U. 2006. Complex networks: Structure and dynamics. Physics Reports, 424, 4-5, 175--308.
37. Strogatz, S. H. Exploring complex networks. Nature, 4102001), 268--276.
38. Newman, M. E. J. 2003. The structure and function of complex networks. SIAM Review 45, 2, 167--256.
39. Holme, P. and Newman, M. E. J. 2006. Nonequilibrium phase transition in the coevolution of networks and opinions. Physical Review E, 74, 5, 056108.
40. Nardini, C., Kozma, B., and Barrat, A. Who's Talking First? 2008. Consensus or Lack Thereof in Coevolving Opinion Formation Models. Physical Review Letters, 100, 15, 158701.
41. Kozma, B. and Barrat, A. 2008. Consensus formation on adaptive networks. Physical Review E, 77, 1, 016102.
42. Centola, D., Gonzalez-Avella, Juan Carlos., Eguiluz, Victor M., Miguel, Maxi San Homophily, Cultural Drift and the Co-Evolution of Cultural Groups. 2007. Journal of Conflict Resolution, 51, 6 (December 2007), 905--929.
43. Giddens, A. The constitution of society. 1984. Polity Press, Cambridge.
44. Lane, D. C. 2001. Rerum cognoscere causas: Part II---Opportunities generated by the agency/structure debate and suggestions for clarifying the social theoretic position of system dynamics. System Dynamics Review, 17, 4, 293--309.
45. Lane, D. C. and Husemann, E. 2008. Steering without Circe: attending to reinforcing loops in social systems. System Dynamics Review, 24, 1, 37--61.
46. Newman, M. E. J. 2002. Assortative Mixing in Networks. Physical Review Letters, 89, 20, 208701.
47. Gross, T. and Kevrekidis, I. G. 2008. Robust oscillations in SIS epidemics on adaptive networks: Coarse graining by automated moment closure. EPL (Europhysics Letters), 82, 38004.
48. Shaw, L. B. and Schwartz, I. B. 2008. Fluctuating epidemics on adaptive networks. Physical Review E, 77, 6, 066101.
49. Gross, T. and Kevrekidis, I. G. 2008. Robust oscillations in SIS epidemics on adaptive networks: Coarse graining by automated moment closure. EPL (Europhysics Letters), 82, 38004.
50. Santos, F. C., Pacheco, J. M. and Lenaerts, T. 2006. Cooperation Prevails When Individuals Adjust Their Social Ties. PLoS Comput Biol, 2, 10, e140.
51. Davies, A., Watson, R., Mills, R., Buckley, C. L. and Noble, J. 2010. If you can't be with the one you love, love the one you're with: How Individual Habituation of Agent Interactions Improves Global Utility. In Proc. Of Artificial Life XII, (Odense, Denmark August 19--23, 2010)
52. Watson, R. A., Buckley, C. L. and Mills, R. 2010. Optimization in "Self-modeling" complex adaptive systems. Complexity. Vol. 16 5, 17--26, (May/June 2011).
53. Watson, R. A., Mills, R. and Buckley, C. L. 2011. Global Adaptation in Networks of Selfish Components: Emergent Associative Memory at the System Scale. Artificial Life. (In Press)
54. Hebb, D. O. 2002. The Organization of Behavior: A Neuropsychological Theory. Psychology Press
55. Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A. and Wiener, J. 2000. Graph structure in the Web. Comput. Netw., 33, 1-6, 309--320.
56. Wei, D., Zhou, T., Cimini, G., Wu, P., Liu, W. and Zhang, Y.-C. 2011. Effective mechanism for social recommendation of news. Physica A: Statistical Mechanics and its Applications, 390, 11, 2117--2126.
57. Blasius, B. and Gross, T. 2009 Dynamic and Topological Interplay in Adaptive Networks. Wiley-VCH Weinheim.
58. Tetlow, P. D. 2007. The Web's Awake: An Introduction to the Field of Web Science and the Concept of Web Life. Wiley-Blackwell.
59. Rupert, M., Rattrout, A. and Hassas, S. 2008. The Web from a Complex Adaptive Systems Perspective. J. Comput. Syst. Sci. 74, 2, 133--145.
60. Kauffman, S. A. 1993. The Origins of Order. Oxford University Press.
61. Miller, J. H. and Page, S. E. 2007. Complex Adaptive Systems: An Introduction to Computational Models of Social Life. Princeton University Press.
62. Ebel, H. and Bornholdt, S. Coevolutionary Games on Networks. 2002. Physical Review E, 66, 5, 056118.
63. Eguíluz, V. M., Zimmermann, M. G., Cela-Conde, C. J. and Miguel, M. S. 2005. Cooperation and the Emergence of Role Differentiation in the Dynamics of Social Networks. American Journal of Sociology, 110, 4, 977--1008.
64. Granovetter, M. 1985. Economic Action and Social Structure: The Problem of Embeddedness. The American Journal of Sociology, 91, 3, 481--510.
65. McEvily, B., Perrone, V. and Zaheer, A. 2003. Trust as an Organizing Principle. Organization Science, 14, 1 (January 1, 2003), 91--103.
66. Guha, R., Kumar, R., Raghavan, P. and Tomkins, A. 2004. Propagation of trust and distrust. In the Proceedings of the 13th international conference on World Wide Web (New York, NY, USA.
67. Hwang, J., Altmann, J. and Kim, K. 2009.The structural evolution of the Web 2.0 service network. Online Information Review, 33, 6, 1040--1057.
68. Marsili, M., Vega-Redondo, F. and Slanina, F. 2004. The rise and fall of a networked society: A formal model. In Proceedings of the National Academy of Sciences of the United States of America, 101, 6 (February 10, 2004), 1439--1442.
69. Palla, G., Bárabasi, A.-L. and Vicsek, T. 2007. Quantifying social group evolution. Nature, 446, 7136, 664--667.
70. Albert, R. and Bárabasi, A.-L. 2000. Topology of Evolving Networks: Local Events and Universality. Physical Review Letters, 85, 24, 5234.
71. Ritzer, G. and Goodman, D. J. 2004. Sociological Theory. McGraw-Hill.
72. Laland, K., Odling-Smee, J. and Feldman, M. Niche Construction, Biological Evolution and Cultural Change. 1999. Behavioral and Brain Sciences, 23, 1.
73. Powers, S. T. Social Niche Construction: Evolutionary Explanations for Cooperative Group Formation. Doctoral Thesis, University of Southampton.
74. Powers, S. T., Penn, A. S. and Watson, R. A. 2011.The Concurrent Evolution of Cooperation and the Population Structures that Support it. Evolution.
75. Shadbolt, N. and Berners-Lee, T. 2008. Web Science Emerges. Scientific American.

Index Terms

• Applied computing

  • Law, social and behavioral sciences

    • Sociology

• Computing methodologies

  • Artificial intelligence

    • Philosophical/theoretical foundations of artificial intelligence

      • Cognitive science

• Human-centered computing

  • Human computer interaction (HCI)