Deliverables - D04

In the first publication we proposed a "Multi-Layer" model of the Webgraph in which every new page that enters the graph is assigned with a constant number of regions it belongs to and it is allowed to link only to vertices in the same region. When deciding the end-points of the edges we adopt a combination of Copying and Evolving Network in the sub graph of the specific region. In particular, if an edge is not copied from the prototype vertex, its end-point is chosen with probability proportional to the in-degree in the existing graph. The final outcome of the stochastic process is the graph obtained by merging the edges inserted between vertices of all layers. This model shows surprising stability properties with respect to the variability of the parameters. In the second of the publications reported below we presented the first extensive comparison study of the statistical properties of large scale simulations of the most important models for the Webgraph presented so far in literature. These models are compared on several relevant observables such as in-degree, out-degree, PageRank, correlation between different measures, e.g. in-degree and Pagerank, number of small bipartite cliques. These models are also compared with a large sample of 300Ml documents and about 1 Billion edges crawled by Alexa in 2001. The analysis of this new sample has allowed discovering some new properties of the Webgraph. For instance, the out-degree does not follow a power law distribution and we can observe a much larger number of cyber-communities with respect to a 3 years older sample always collected by Alexa. This comparison study has required the development of external and semi-external algorithms for computing several graph properties and large scale simulation of stochastic graph models. This deliverable consists of the following publications


  1. Decision making dynamics in corporate boards.
    S. Battiston, E. Bonabeau and G. Weisbuch
    ArXiv:cond-mat/0209590 (2002).

  2. Number of Loops of size h in growing scale-free networks.
    G. Bianconi and A.Capocci
    ArXiv:cond-mat/0212028 (2002).

  3. Epidemic spreading in correlated complex networks.
    M. Boguñá and R. Pastor-Satorras
    Physical Review E 66 047104 (2002).

  4. Topology of correlation based minimal spanning trees in real and model markets.
    G. Bonanno, G. Caldarelli, F. Lillo and R. Mantegna
    ArXiv:cond-mat/0211546 (2002).

  5. Introduction to Complex Networks.
    G. Caldarelli
    Proceedings of the 7th Conference on Statistical and Computational Physics Granada (2002).

  6. Scale-Free Networks from Varying Vertex Intrinsic Fitness.
    G. Caldarelli, A. Capocci, P. De Los Rios and M. A. Muñoz
    Physical Review Letters 89, 258702 (2002).

  7. Cycles structure and local ordering in complex networks.
    G. Caldarelli, R. Pastor-Satorras and A. Vespignani
    ArXiv:cond-mat/0212026 (2002).

  8. Quantitative description and modelling of real networks.
    A.Capocci, G. Caldarelli, and P. De Los Rios
    ArXiv:cond-mat/0206336 (2002).

  9. Visualization of the High Level Structure of the Internet with Hermes.
    A.Carmignani, G. Di Battista, W. Didimo, F. Matera and M. Pizzonia
    Journal of Graph Algorithms and Applications 6,281 (2002).

  10. How Can Extremism Prevail? A study based on the relative agreement interaction model.
    G. Deffuant, F. Amblard, G. Weisbuch and T. Faure
    Journal of Artificial Societies and Social Simulation 5 (2002).

  11. Exploration bias of Complex Networks.
    P. De Los Rios
    Proceedings of the 7th Conference on Statistical and Computational Physics Granada (2002).

  12. Drawing database schemas.
    G. Di Battista, W. Didimo, M. Patrignani and M. Pizzonia
    Software-Practice and Experience. 32, 1065 (2002).

  13. Archive of BGP Updates: Integration and Visualization.
    G. Di Battista, F. Mariani, M. Patrignani and M. Pizzonia
    Preprint (2002).

  14. Computing the types of the Relationships Between Autonomous Systems.
    G. Di Battista, M. Patrignani and M. Pizzonia
    Technnical Report University of Rome 3 RT-DIA-73(2002).

  15. Dynamical properties of model communication networks.
    R. Guimerà, A. Arenas, A. Díaz-Guilera and F. Giralt
    Physical Review E 66, 026704 (2002).

  16. Optimal network topologies for local search with congestion.
    R. Guimerà, A. Díaz-Guilera, F. Vega-Redondo, A. Cabrales, and A. Arenas
    Physical Review Letters 89, 248701 (2002).

  17. A Multi-layer model for the Web Graph
    L. Laura, S. Leonardi, G. Caldarelli and P. De Los Rios
    Contribution to 2nd Web Dynamics Workshop (2002).

  18. Critical load and congestion instabilities in scale-free networks.
    Y. Moreno, R. Pastor-Satorras A. Vázquez and A. Vespignani
    ArXiv:cond-mat/0209474 (2002).

  19. Scale-free behavior of the Internet global performance.
    R. Percacci and A. Vespignani
    ArXiv:cond-mat/0209619 to be published in European Journal of Physics B (2002).

  20. Epidemics and immunization in scale-free networks.
    R. Pastor-Satorras and A. Vespignani
    Handbook of Graphs and Networks: From the Genome to the Internet, eds. S. Bornholdt and H. G. Schuster, Wiley-VCH, Berlin, pp. 113-132 (2002).

  21. Topology and correlations in structured scale-free networks.
    A. Vázquez, M. Boguñá, Y. Moreno, R. Pastor-Satorras and A. Vespignani
    ArXiv:cond-mat/0209183 (2002).

  22. Large-scale topological and dynamical properties of the Internet.
    A. Vázquez, R. Pastor-Satorras, and A. Vespignani
    Physical Review E 65, 066130 (2002).

  23. Internet topology at the router and autonomous system level.
    A. Vázquez, R. Pastor-Satorras, and A. Vespignani
    ArXiv:cond-mat/0206084 (2002).

  24. Adjustment and social choice.
    G. Weisbuch and D. Stauffer
    submitted to Physica A (2002).


    2003

  25. Size of Quantum Networks.
    G. Bianconi
    ArXiv:cond-mat/0301551.

  26. Absence of Epidemic threshold in scale-free networks with degree correlations.
    M. Boguñá R. Pastor-Satorras and A. Vespignani
    Physical Review Letters 90, 028701 (2003).

  27. Epidemic spreading in complex networks with degree correlations.
    M. Boguñá R. Pastor-Satorras and A. Vespignani
    ArXiv:cond-mat/0301149 to appear in Lecture notes in Physics (2003).

  28. Topology of the World Trade Web.
    M. A. Serrano, and M. Boguñá
    ArXiv:cond-mat/0301015.

  29. GraphML Progress Report: Structural Layer Proposal.
    Ulrik Brandes, Markus Eiglsperger, Ivan Herman, Michael Himsolt, and M. Scott Marshall
    Proc. 9th Intl. Symp. Graph Drawing (GD '01), LNCS 2265, pp. 501-512. © Springer-Verlag, 2002.

  30. Guide - Changes
    Volker Maag and Thomas Willhalm
    preprint

  31. visone - Analysis and Visualization of Social Networks.
    U. Brandes and D. Wagner
    accepted on Graph Drawing Software Springer Series "Mathematics and Visualization" M. Junger P. Mutzel (eds).

  32. Analysis and Visualization of Social Networks
    Dorothea Wagner
    to appear in Proceedings of WEA 2003, LNCS

  33. A Multi-Layer Model for the Web Graph
    L. Laura, S. Leonardi, G. Caldarelli and P. De Los Rios
    Proceedings of the 2nd International Workshop on Web Dynamics

  34. Communicating Centrality in Policy Network Drawings.
    U. Brandes, P. Kenis and D. Wagner
    accepted on IEEE transactions on Visualization and Computer Graphics.

  35. Visual Ranking of Link Structures
    U. Brandes and S. Cornelsen
    accepted on Journals of Graph Algorithms and Applications.

  36. on Clustering Large graphs.
    U. Brandes, M. Gaertler and D. Wagner
    preprint.

  37. Universality in Food webs
    D. Garlaschelli, G. Caldarelli, L. Pietronero
    accepted on Nature.

  38. Self-similar community structure in organizations
    R. Guimerà, L. Danon, A. Diaz-Guilera, A. Arenas
    preprint

  39. Quantifying the creation of social capital in a digital community
    R. Guimerà, X. Guardiola, A. Arenas, A. Diaz-Guilera, D. Streib, L.A.N. Amaral
    Preprint

  40. A study of stocastic model for the Web Graph
    G. Caldarelli, P. De Los Rios, S. Leonardi, S. Millozzi, A. Vespignani
    Preprint

  41. Topology of Protein Protein Interaction Networks from Physical Principles
    G. Caldarelli, P. De Los Rios, F. Squartini
    Preprint

  42. Statistical Properties of Shareholders Network.
    S. Battiston, G. Caldarelli, M. Castri, D. Garlaschelli, L. Pietronero
    preprint

  43. Evolving Protein Interaction Networks through gene duplication.
    R. Pastor-Satorras, E. Smith and R. V. Sole
    In press Journal of Theoretical Biology
    Contact us: Webmaster