A social network evolution model based on seniority
Tóm tắt
A social network is a representation that describes the relationships between individuals. In recent years, several interesting phenomena, such as the densification power law, have been observed in social networks and a number of models have been proposed to explain them. In this paper, we investigate an interesting phenomenon called the seniority difference distribution of new connections, which we observed in our data. The distribution reveals that there exists a seniority preference when a new network node tries to establish connections with existing nodes. To explain the phenomenon, we propose several models based on different local selection policies, namely, equal-probability selection, freshness-based selection, oldness-based selection, and combined freshness/oldness selection. The results of simulations show that, by combining the concepts of freshness and oldness, it is possible to reproduce a social network that matches the observation.
Tài liệu tham khảo
Akoglu L, Mcglohon M et al (2008) RTM: laws and a recursive generator for weighted time-evolving graphs. In: Eighth IEEE international conference on data mining (ICDM), pp 701–706
Alber R, Barabási AL (1999) Emergence of scaling in random networks. Science 286(5439):509–512
Bu T, Towsley D (2002) On distinguishing between internet power law topology generators. INFOCOM 2002, vol 2, pp 638–647. doi:10.1109/INFCOM.2002.1019309
Chakrabarti D, Zhan Y et al (2004) R-MAT: a recursive model for graph mining. In: 4th SIAM international conference on data mining
Du N, Faloutsos C, Wang B, Akoglu L (2009) Large human communication networks: patterns and a utility-driven generator. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining (KDD ’09). ACM, New York
Erdős P, Rényi A (1959) On random graphs. Mathematicae Debrecen 6:290–297
Kleinberg JM, Kumar R, Raghavan P, Rajagopalan S, Tomkins AS (1999) The web as a graph: measurements, models, and methods. In: Proceedings of the 5th annual international conference on computing and combinatorics (COCOON ’99)
Kossinets G, Watts DJ (2006) Empirical analysis of an evolving social network. Science 311(5757):88–90
Leskovec J, Faloutsos C (2007) Scalable modeling of real graphs using Kronecker multiplication. In: Proceedings of the 24th international conference on machine learning (ICML ’07). ACM, New York
Leskovec J, Chakrabarti D, Kleinberg J, Faloutsos C (2005a) Realistic, mathematically tractable graph generation and evolution, using Kronecker multiplication. In: European conference on principles and practice of knowledge discovery in databases (ECML/PKDD)
Leskovec J, Kleinberg J, Faloutsos C (2005b) Graphs over time: laws, shrinking diameters and possible explanations. In: ACM SIGKDD international conference on knowledge discovery and data mining (KDD)
Leskovec J, Kleinberg J, Faloutsos C (2007) Graph evolution: densification and shrinking diameters. In: ACM transactions on knowledge discovery from data (ACM TKDD), vol 1, no. 1
Mahadevan P, Krioukov D, Fall K, Vahdat A (2006) Systematic topology analysis and generation using degree correlations. In: Proceedings of the 2006 conference on applications, technologies, architectures, and protocols for computer communications (SIGCOMM ’06). ACM, New York
Newman MEJ (2003) Random graphs as models of networks. In: Bornholdt S, Schuster HG (eds) Handbook of graphs and networks. Wiley, Berlin
Pedarsani P, Figueiredo DR, Grossglauser M (2008) Densification arising from sampling fiex graphs. In: ACM SIGMETRICS performance evaluation review—SIGMETRICS ’08, vol 36, no. 1
Pennock DM, Flake GW, Lawrence S, Glover EJ, Lee Giles C (2001) Winners don’t take all: characterizing the competition for links on the web. Proc Natl Acad Sci USA 99(8):5207–5211
Sakaki T, Okazaki M, Matsuo Y (2010) Earthquake shakes Twitter users: real-time event detection by social sensors. In: Proceedings of the 19th international conference on world wide web (WWW ’10). ACM, New York
Vázquez A (2003) Growing network with local rules: preferential attachment, clustering hierarchy, and degree correlations. Phys Rev E 67:056104
Watts DJ, Strogatz S (1998) Collective dynamics of ‘small-world’ networks. Nature 393:440–442. doi:10.1038/30918