BibSonomy publications for /user/andreab/modelsSat Apr 05 14:58:45 CEST 2008New York, NY, USAKDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining611--617Structure and evolution of online social networks2006yahoo structure social imported network flickr models analysis 2006 In this paper, we consider the evolution of structure within large online social networks. We present a series of measurements of two such networks, together comprising in excess of five million people and ten million friendship links, annotated with metadata capturing the time of every event in the life of the network. Our measurements expose a surprising segmentation of these networks into three regions: singletons who do not participate in the network; isolated communities which overwhelmingly display star structure; and a giant component anchored by a well-connected core region which persists even in the absence of stars.We present a simple model of network growth which captures these aspects of component structure. The model follows our experimental results, characterizing users as either passive members of the network; inviters who encourage offline friends and acquaintances to migrate online; and linkers who fully participate in the social evolution of the network.Tue Apr 10 15:50:31 CEST 2007New YorkUrn Models and Their Applications: An Approach to Modern Discrete Probability Theory1977d4.1 statistics models polya urns tagora Fri Feb 23 15:33:22 CET 2007Journal of Statistical Mechanics: Theory and Experiment02P02004Understanding scale invariance in a minimal model of complex relaxation phenomena20062006imported modeling physics models citingme scaling We report on the computer study of a lattice system that relaxes from a metastable state. Under appropriate nonequilibrium randomness, relaxation occurs by avalanches, i. e., the model evolution is discontinuous and displays many scales in a way that closely resembles the relaxation in a large number of complex systems in nature. Such apparent scale invariance simply results in the model from summing over many exponential relaxations, each with a scale which is determined by the curvature of the domain wall at which the avalanche originates. The claim that scale invariance in a nonequilibrium setting is to be associated with criticality is therefore not supported. Some hints that may help in checking this experimentally are discussed.Thu Dec 21 18:20:07 CET 2006Journal of Statistical Physics11-48Scaling, Optimality, and Landscape Evolution1042001review statistical modeling physics models rivernetworks A nonlinear model is studied which describes the evolution of a landscape under the effects of erosion and regeneration by geologic uplift by mean of a simple differential equation. The equation, already in wide use among geomorphologists and in that context obtained phenomenologically, is here derived by reparametrization invariance arguments and exactly solved in dimension d=1. Results of numerical simulations in d=2 show that the model is able to reproduce the critical scaling characterizing landscapes associated with natural river basins. We show that configurations minimizing the rate of energy dissipation (optimal channel networks) are stationary solutions of the equation describing the landscape evolution. Numerical simulations show that a careful annealing of the equation in the presence of additive noise leads to configurations very close to the global minimum of the dissipated energy, characterized by mean field exponents. We further show that if one considers generalized river network configurations in which splitting of the flow (i.e., braiding) and loops are allowed, the minimization of the dissipated energy results in spanning loopless configurations, under the constraints imposed by the continuity equations. This is stated in the form of a general theorem applicable to generic networks, suggesting that other branching structures occurring in nature may possibly arise as optimal structures minimizing a cost function.Mon Dec 18 20:20:02 CET 2006Physical Review E056101k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects732006kcore percolation theory networks models physics network simulation model imported graphs We develop the theory of the k-core (bootstrap) percolation on uncorrelated random networks with arbitrary degree distributions. We show that the k-core percolation is an unusual, hybrid phase transition with a jump emergence of the k-core as at a first order phase transition but also with a critical singularity as at a continuous transition. We describe the properties of the k-core, explain the meaning of the order parameter for the k-core percolation, and reveal the origin of the specific critical phenomena. We demonstrate that a so-called ``corona'' of the k-core plays a crucial role (corona is a subset of vertices in the k-core which have exactly k neighbors in the k-core). It turns out that the k-core percolation threshold is at the same time the percolation threshold of finite corona clusters. The mean separation of vertices in corona clusters plays the role of the correlation length and diverges at the critical point. We show that a random removal of even one vertex from the k-core may result in the collapse of a vast region of the k-core around the removed vertex. The mean size of this region diverges at the critical point. We find an exact mapping of the k-core percolation to a model of cooperative relaxation. This model undergoes critical relaxation with a divergent rate at some critical moment.Mon Dec 18 20:10:08 CET 2006The dynamical collision network in granular gases2006model kcore physics statistics simulation imported network models granular We dynamically construct the interaction network in a granular gas, using the sequence of collisions collected in an MD event driven simulation of inelastic hard disks from time 0 till time t. The network is decomposed into its k-core structure: particles in a core of index k have collided at least k times with other particles in the same core. The difference between cores k+1 and k is the so-called k-shell, and the set of all shells is a complete and on-overlapping decomposition of the system. Because of energy dissipation, the gas cools down: its initial spatially homogeneous dynamics, characterized by the Haff law, i.e. a t^{-2} energy decay, is unstable towards a strongly inhomogeneous phase with clusters and vortices, where energy decays as t^{-1}. The clear transition between those two phases appears in the evolution of the k-shells structure in the collision network. In the homogeneous regime the k-shell structure evolves as in a growing network with fixed number of vertices and randomly added links: the shell distribution is strongly peaked around the most populated shell, which has an index k\_{max} ~ 0.9 <d> with <d> the average number of collisions experienced by a particle. During the final non-homogeneous regime a growing fraction of collisions is concentrated in small, almost closed, 'communities' of particles: k\_{max} is no more linear in <d> and the distribution of shells becomes extremely large developing a power-law tail ~ k^{-3} for high shell indexes. We propose the k-shell decomposition as a quantitative characterization of Molecular Chaos violation.Tue Dec 05 17:41:13 CET 2006Internet Mathematics 4 525-534Editorial: The Future of Power Law Research22006models d4.1 tagora research power paper editorial law article Abstract. I argue that power law research must move from focusing on observation, in- terpretation, and modeling of power law behavior to instead considering the challenging problems of validation of models and control of systems. Tue Dec 05 17:34:04 CET 2006submitted to Internet Mathematics A Brief History of Generative Models for Power Law and Lognormal Distributions - submission version 2004paper simon submission yule d4.1 model zipf models power law review article tagora Recently, I became interested in a current debate over whether file size distributions are best modelled by a power law distribution or a lognormal distribution. In trying to learn enough about these distributions to settle the question, I found a rich and long history, spanning many fields. Indeed, several recently proposed models from the computer science community have antecedents in work from decades ago. Here, I briefly survey some of this history, focusing on underlying generative models that lead to these distributions. One finding is that lognormal and power law distributions connect quite naturally, and hence, it is not surprising that lognormal distributions have arisen as a possible alternative to power law distributions across many fields. Tue Dec 05 17:30:15 CET 2006Internet Mathematics 2 226-251A Brief History of Generative Models for Power Law and Lognormal Distributions1 2004models d4.1 article model law paper zipf review yule tagora simon power Mon Dec 04 17:08:06 CET 2006ACL271-278A Stochastic Process for Word Frequency Distributions.1991d4.1 mandelbrot tagora distribution words models frequency language simon imported stochastic zipf model statistics linguistics Fri Dec 01 16:29:10 CET 2006Re-inventing Willis2006preferetial network tagora attachment physics models theory model d4.1 urn Scientists often re-invent things which were long known. Here we review these activities as related to the mechanism of producing power law distributions, originally proposed in 1922 by Yule to explain experimental data on the sizes of biological genera, collected by Willis. We estimate that scientists are busy re-discovering America about 2/3 of time.Thu Aug 31 15:02:04 CEST 2006Collaborative Tagging and Semiotic Dynamics2006models d4.1 sapienza collaborative tagging tagora theory