The 6th Workshop on Algorithms and Models for the Web Graph (WAW2009)
Home arrow Keynote Talks
Call for Papers
Important Dates
Keynote Talks
Attending Conference
Funding Opportunities

Keynote Talks

Ravi Kumar (Yahoo! Research)

Online social networks: modeling and mining

Online social networks have become major and driving phenomena on the web. In this talk we will address key modeling and algorithmic questions related to large online social networks. From the modeling perspective, we raise the question of whether there is a generative model for network evolution. The availability of time-stamped data makes it possible to study this question at an extremely fine granularity. We exhibit a simple, natural model that leads to synthetic networks with properties similar to the online ones. From an algorithmic viewpoint, we focus on data mining challenges posed by the magnitude of data in these networks. In particular, we examine topics related to influence and correlation in user activities and compressibility of such networks.

José Fernando Mendes (University of Aveiro)

Transition from small to large world in growing networks

A relation between small worlds (compact, infinite dimensional objects) and large worlds (finite-dimensional objects) is a key issue in understanding of networks. The surge of interest in networks has been triggered by the paper of Watts and Strogatz [1] who found a transition from lattices to networks with a small-world organization. The Watts-Strogatz construction describes a smooth crossover between the two limiting situations. A sharp transition between finite- and infinite-dimensional networks (it coincides with a so-called searchability point) has been observed in studies of decentralized search algorithms [2–4].

These findings have been made in “static” networks. Results of numerical simulations [5–8] suggest a sharp transition also in specific growing network models. The existence of this special point was confirmed analytically in work [9]. Yet essentially nothing is known about the nature of these transitions in static and especially in growing random networks. Here we provide an analytical description of a transition from an infinite-dimensional network to a finite-dimensional one in random recursive graphs with aging.

We examine the global organization of growing networks in which a new vertex is attached to already existing ones with a probability depending on their age. We find that the network is infinite- or finite-dimensional depending on whether the attachment probability decays slower or faster than (age)−1. The network becomes one-dimensional when the attachment probability decays faster than (age)−2. We have demonstrated a rich set of regimes in a global organization of growing networks with aging. Our results have been derived in the context of a specific model, yet the major conclusions should be applicable to a larger class of networks.

[1] Watts D. J. and Strogatz S. H., Nature, 393 (1998) 409.
[2] Kleinberg J. M., Nature, 406 (2000) 845.
[3] Kleinberg J., Proceedings of the International Congress of Mathematicians (ICM), Madrid, August 22–30, 2006, edited by M. Sanz-Sol´e, J. Soria, J. L. Varona and J.Verdera 2007, p. 1019.
[4] Moukarzel C. F. and Argollo de Menezes M., Phys. Rev. E, 65 (2002) 056709.
[5] Holme P., Physica A, 377 (2007) 315.
[6] Hinczewski M. and Berker A. N., Phys. Rev. E, 73 (2006) 066126.
[7] Tian L., Zhu C.-P., Shi D.-N., Gu Z.-M. and Zhou T., Phys. Rev. E, 74 (2006) 046103.
[8] Zhang Z., Zhou S., Wang Z. and Shen Z., J. Phys. A, 40 (2007) 11863; Zhang Z., Zhou S., Shen Z. and Guan J., Physica A, 385 (2007) 765.
[9] Lambiotte R., J. Stat. Mech., (2007) P02020.

Monday, 19 August 2019