Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-25T07:46:58.907Z Has data issue: false hasContentIssue false
  • English
  • Français

Evolution through bursts: Network structure develops through localized bursts in time and space

Published online by Cambridge University Press:  31 August 2016

HILLA BROT ,
LEV MUCHNIK ,
JACOB GOLDENBERG  and
YORAM LOUZOUN
HILLA BROT
Affiliation:
Center for Polymer Studies and Department of Physics, Boston University, Boston, MA 02215, USA Kellogg School of Management, Northwestern University, Evanston, IL 60208, USA (e-mail: [email protected])
LEV MUCHNIK
Affiliation:
School of Business Administration, The Hebrew University of Jerusalem, Jerusalem 91905, Israel (e-mail: [email protected])
JACOB GOLDENBERG
Affiliation:
School of Business Administration, IDC Herzliya, Herzliya 46150, Israel (e-mail: [email protected])
YORAM LOUZOUN
Affiliation:
Department of Mathematics, Bar-Ilan University, Ramat Gan 52900, Israel Gonda Brain Research Center, Bar-Ilan University, Ramat Gan 52900, Israel (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Models of network evolution are based on the implicit assumption that network growth is continuous, uniform, and steady. Using the data collected from a large online-blogging platform, we show that the addition and removal of network ties by users do not occur sporadically at isolated nodes spread all over the network, as assumed by the vast majority of stochastic network models, but rather occur in brief bursts of intense local activity.

These bursts of network growth and attrition (addition and removal of network ties) are highly localized around focal nodes. Such network changes coincide with nearly instantaneous densification of the ties between the affected nodes, resulting in an increase of local clustering. Furthermore, we find that these network changes are tightly coupled to the dynamics of individual attributes, particularly the increase in homology between neighboring nodes (homophily) within the scope of the burst. Coincidence of the localized network change with the increase in homophily suggests a strong coupling between the selection and influence processes that lead to simultaneous elevation of assortativity and clustering.

Keywords

homophilysimultaneous eventsindividual traitscouplingburstsnetwork dynamicsLiveJournaltriadic closurefeedback
Type
Research Article
Information
Network Science , Volume 4 , Issue 3 , September 2016 , pp. 293 - 313
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Adamic, L. A., & Huberman, B. A. (2000). Power-law distribution of the World Wide Web. Science, 287(5461), 2115–2115.Google Scholar
Aiello, L. M., Barrat, A., Schifanella, R., Cattuto, C., Markines, B., & Menczer, F. (2012). Friendship prediction and homophily in social media. ACM Transactions on the Web (TWEB), 6 (2), 9.Google Scholar
Albert, R., Jeong, H. & Barabási, A.-L. (1999). Internet: Diameter of the world-wide web. Nature, 401(6749), 130–131.Google Scholar
Anderson, R. E., & Srinivasan, S. S. (2003). E-satisfaction and e-loyalty: A contingency framework. Psychology & Marketing, 20 (2), 123–138.CrossRefGoogle Scholar
Aral, S., Muchnik, L., & Sundararajan, A. (2009). Distinguishing influence-based contagion from homophily-driven diffusion in dynamic networks. Proceedings of the National Academy of Sciences, 106 (51), 21544–21549.CrossRefGoogle ScholarPubMed
Aral, S., Muchnik, L., & Sundararajan, A. (2013). Engineering social contagions: Optimal network seeding in the presence of homophily. Network Science, 1 (2), 125–153.Google Scholar
Barabasi, A.-L. (2005). The origin of bursts and heavy tails in human dynamics. Nature, 435(7039), 207–211.Google Scholar
Barabási, A.-L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439), 509–512.Google Scholar
Brot, H., Muchnik, L., Goldenberg, J., & Louzoun, Y. (2012). Feedback between node and network dynamics can produce real world network properties. Physica A: Statistical Mechanics and its Applications, 391 (24), 6645–6654.CrossRefGoogle Scholar
Brot, H., Muchnik, L., & Louzoun, Y. (2015). Directed triadic closure and edge deletion mechanism induce asymmetry in directed edge properties. The European Physical Journal B, 88 (1), 1–11.Google Scholar
Centola, D. & van, de Rijt, A. (2015). Choosing your network: Social preferences in an online health community. Social Science & Medicine, 125, 19–31.CrossRefGoogle Scholar
Chaintreau, A., Mtibaa, A., Massoulie, L., & Diot, C. (2007). The diameter of opportunistic mobile networks. Paper presented at the Proceedings of the 2007 ACM CoNEXT conference. New York, NY: ACM.Google Scholar
Clauset, A., Newman, M. E. J., & Moore, C. (2004). Finding community structure in very large networks. Physical Review E, 70 (6), 066111.Google Scholar
Cowley, M. A., Smart, J. L, Rubinstein, M., Cerdán, M. G., Diano, S., Horvath, T. L., . . . Low, M. J. (2001). Leptin activates anorexigenic POMC neurons through a neural network in the arcuate nucleus. Nature, 411 (6836), 480–484.CrossRefGoogle ScholarPubMed
Crandall, D., Cosley, D., Huttenlocher, D., Kleinberg, J., & Suri, S. (2008). Feedback effects between similarity and social influence in online communities. Paper presented at the Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. New York, NY: ACM.Google Scholar
Dezsö, Z., Almaas, E., Lukács, A., Rácz, B., Szakadát, I., & Barabási, A.-L. (2006). Dynamics of information access on the web. Physical Review E, 73 (6), 066132.Google Scholar
Diesmann, M., Gewaltig, M.-O., & Aertsen, A. (1999). Stable propagation of synchronous spiking in cortical neural networks. Nature, 402 (6761), 529–533.CrossRefGoogle ScholarPubMed
Diesner, J. (2012). Uncovering and managing the impact of methodological choices for the computational construction of socio-technical networks from texts, DTIC Document, Dissertations. Paper 194.Google Scholar
Eriksen, K. A., Simonsen, I., Maslov, S., & Sneppen, K. (2003). Modularity and extreme edges of the Internet. Physical Review Letters, 90 (14), 148701.Google Scholar
Fagiolo, G. (2007). Clustering in complex directed networks. Physical Review E, 76 (2), 026107.Google Scholar
Figueiredo, F., Almeida, J. M., Gonçalves, M. A., & Benevenuto, F. (2014). On the dynamics of social media popularity: A YouTube case study. ACM Transactions on Internet Technology (TOIT), 14 (4), 24.Google Scholar
Foster, J. G, Foster, D. V., Grassberger, P., & Paczuski, M. (2010). Edge direction and the structure of networks. Proceedings of the National Academy of Sciences, 107 (24), 10815–10820.Google Scholar
Fu, F., Nowak, M. A., Christakis, N. A., & Fowler, J. H. (2012). The evolution of homophily. Scientific Reports 2, doi:10.1038/srep00845.Google Scholar
Gabel, A., & Redner, S. (2013). Sublinear but never superlinear preferential attachment by local network growth. Journal of Statistical Mechanics: Theory and Experiment, 2013 (2), P02043.Google Scholar
Gallos, L. K., Rybski, D., Liljeros, F., Havlin, S., & Makse, H. A. (2012). How people interact in evolving online affiliation networks. Physical Review X, 2 (3), 031014.Google Scholar
Garber, T., Goldenberg, J., Libai, B., & Muller, E. (2004). From density to destiny: Using spatial dimension of sales data for early prediction of new product success. Marketing Science, 23 (3), 419–428.Google Scholar
Golosovsky, M., & Solomon, S. (2012). Stochastic dynamical model of a growing citation network based on a self-exciting point process. Physical Review Letters, 109 (9), 098701.Google Scholar
Grund, T. (2014). Network size and network homophily: Same-sex friendships in 595 Scandinavian schools. Analytical Sociology, 297–314.Google Scholar
Hamers, L., Hemeryck, Y., Herweyers, G., Janssen, M., Keters, H., Rousseau, R., & Vanhoutte, A. (1989). Similarity measures in scientometric research: The Jaccard index versus Salton's cosine formula. Information Processing & Management, 25 (3), 315–318.Google Scholar
Holme, P., Huss, M., & Jeong, H. (2003). Subnetwork hierarchies of biochemical pathways. Bioinformatics, 19 (4), 532–538.Google Scholar
Holme, P., & Kim, B. J. (2002). Growing scale-free networks with tunable clustering. Physical Review E, 65 (2), 026107.CrossRefGoogle ScholarPubMed
Jagerman, D. L., & Melamed, B. (1994). Burstiness descriptors of traffic streams: Indices of dispersion and peakedness. Proceedings of the 1994 Conference on Information Sciences and Systems, 1, 24–28.Google Scholar
Kämpf, M., Tismer, S., Kantelhardt, J. W., & Muchnik, L. (2012). Fluctuations in Wikipedia access-rate and edit-event data. Physica A: Statistical Mechanics and its Applications, 391 (23), 6101-6111. doi: http://dx.doi.org/10.1016/j.physa.2012.07.004.CrossRefGoogle Scholar
Khosla, A., Das, Sarma, A., & Hamid, R. (2014). What makes an image popular? Paper presented at the Proceedings of the 23rd international conference on World wide web. New York, NY: ACM.Google Scholar
Kimura, D., & Hayakawa, Y. (2008). Coevolutionary networks with homophily and heterophily. Physical Review E, 78 (1), 016103.CrossRefGoogle ScholarPubMed
Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. S. (1999). The web as a graph: Measurements, models, and methods. In: Asano, T., Imai, H., Lee, D. T., Nakano, S., & Tokuyama, T. (Eds.), Computing and Combinatorics Volume 1627 of the series Lecture Notes in Computer Science (pp. 1–17). Berlin, Heidelberg: Springer.Google Scholar
Klemm, K., & Eguiluz, V. M. (2002). Highly clustered scale-free networks. Physical Review E, 65 (3), 036123.CrossRefGoogle ScholarPubMed
Leskovec, J., Backstrom, L., Kumar, R., & Tomkins, A. (2008). Microscopic evolution of social networks. Paper presented at the Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. New York, NY: ACM.Google Scholar
Leskovec, J., Kleinberg, J., & Faloutsos, C. (2005). Graphs over time: Densification laws, shrinking diameters and possible explanations. Paper presented at the Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining. New York, NY: ACM.Google Scholar
Manski, C. F. (1993). Identification of endogenous social effects: The reflection problem. The Review of Economic Studies, 60 (3), 531–542.Google Scholar
McPherson, M., Smith-Lovin, L., & Cook, J. M. (2001). Birds of a feather: Homophily in social networks. Annual Review of Sociology, 27, 415–444.Google Scholar
Min, B., & Goh, K.-I. (2013). Burstiness: Measures, models, and dynamic consequences. In: Holme, P. & Saramäki, J. (Eds.), Temporal networks (pp. 41–64). Berlin, Heidelberg: Springer.Google Scholar
Muchnik, L., Pei, S., Parra, L. C., Reis, S. D. S., Andrade, J. S. Jr, Havlin, S., & Makse, H. A. (2013). Origins of power-law degree distribution in the heterogeneity of human activity in social networks. Scientific Reports, 3, doi:10.1038/srep01783.Google Scholar
Papadopoulos, F., Kitsak, M., Serrano, M. Á., Boguñá, M., & Krioukov, D. (2012). Popularity versus similarity in growing networks. Nature, 489 (7417), 537–540.Google Scholar
Paxson, V., & Floyd, S. (1995). Wide area traffic: The failure of poisson modeling. IEEE/ACM Transactions on Networking (ToN), 3 (3), 226–244.Google Scholar
Perc, M. (2014). The matthew effect in empirical data. Journal of The Royal Society Interface, 11 (98), 20140378.Google Scholar
Roth, C., & Cointet, J.-P. (2010). Social and semantic coevolution in knowledge networks. Social Networks, 32 (1), 16–29.Google Scholar
Rybski, D., Buldyrev, S. V., Havlin, S., Liljeros, F., & Makse, H. A. (2009). Scaling laws of human interaction activity. Proceedings of the National Academy of Sciences, 106 (31), 12640–12645.Google Scholar
Sayama, H., Pestov, I., Schmidt, J., Bush, B. J., Wong, C., Yamanoi, J., & Gross, T. (2013). Modeling complex systems with adaptive networks. Computers & Mathematics with Applications, 65 (10), 1645–1664.CrossRefGoogle Scholar
Vázquez, A. (2003). Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations. Physical Review E, 67 (5), 056104.Google Scholar
Yamasaki, K., Muchnik, L., Havlin, S., Bunde, A., & Stanley, H. E. (2005). Scaling and memory in volatility return intervals in financial markets. Proceedings of the National Academy of Sciences of the United States of America, 102 (26), 9424–9428.Google Scholar