Deprecated: Assigning the return value of new by reference is deprecated in /WebSpace/Tw/twmed/waw2009/public_html/includes/joomla.php on line 836 Deprecated: Function split() is deprecated in /WebSpace/Tw/twmed/waw2009/public_html/templates/siteground11/index.php on line 4
The 6th Workshop on Algorithms and Models for the Web Graph (WAW2009)
Deprecated: Function eregi() is deprecated in /WebSpace/Tw/twmed/waw2009/public_html/includes/pathway.php on line 280 Deprecated: Function eregi() is deprecated in /WebSpace/Tw/twmed/waw2009/public_html/includes/pathway.php on line 313 Home arrow Keynote Talks
Home
News
Organization
Call for Papers
Important Dates
Keynote Talks
Attending Conference
Funding Opportunities
Registration
Program
Venue

Keynote Talks
Deprecated: Function ereg() is deprecated in /WebSpace/Tw/twmed/waw2009/public_html/includes/joomla.php on line 3762 Deprecated: Function ereg() is deprecated in /WebSpace/Tw/twmed/waw2009/public_html/includes/joomla.php on line 3762

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.


References:
[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.

 
Friday, 23 June 2017