MMC Bonato

50 %
50 %
Information about MMC Bonato

Published on June 26, 2007

Author: BAWare


Modelling the infinite web:  Modelling the infinite web Anthony Bonato Wilfrid Laurier University Waterloo, Canada Coast to Coast Miniconference on the Mathematics of Computation August 5, 2006 Graph theory – the last century:  Graph theory – the last century Slide3:  Today… The web graph/network:  The web graph/network nodes: web pages edges: links Google uses graph theory!:  Google uses graph theory! How big is the web?:  How big is the web? The web is really infinite… calendars, online organizers random strings: google 'raingod random strings' Total web ≈ 11.5 billion static pages (Gulli andamp; Signorini, 05) about 2.3 billion pages are unknown to Google Collaboration networks:  Collaboration networks nodes: mathematicians edges: co-authoring Slide8:  Biological networks:  Biological networks nodes: proteins edges: biochemical interactions Hollywood network:  Hollywood network nodes: actors edges: star in same movie Slide11:  The web graph and related networks above are often called: self-organizing scale-free massive complex heterogeneous Power laws in web graph:  Power laws in web graph for some bandgt;1 ratio of # nodes of degree k, to # nodes Broder et al, 01 Interpreting the power law:  Many low-degree nodes Few high-degree nodes Interpreting the power law Slide14:  Binomial Power law Highway network Air traffic network Other properties of self-organizing networks:  Other properties of self-organizing networks small world topology (Watts, Strogatz, 98): low diameter/average distance diameter of the web: 19 globally sparse, locally dense rich bipartite structures (Kumar et al, 00) Random graphs:  Random graphs Paul Erdős Alfred Rényi Slide17:  G(n,p) random graph model(Erdős, Rényi, 63) :  G(n,p) random graph model (Erdős, Rényi, 63) p a real number in (0,1), n a positive integer G(n,p): probability space on graphs with nodes {1,…,n}, two nodes joined independently and with probability p Properties of G(n,p):  Properties of G(n,p) Almost regular: node degrees concentrated around np Degree distribution is binomial Low diameter, low clustering, rich but uniform substructures G(n,p) as a model for the web graph:  G(n,p) as a model for the web graph Pros: Corpus of existing literature:large arsenal of tools Independence Cons Binomial degree distribution Independence Off-line Slide21:  (Bonato, 04) A model for self-organizing networks should have the following properties: On-line property. The number of nodes and edges changes with time. Power law degree distribution. Small world property. Many bipartite substructures. Preferential attachment (PA) model(Barabási, Albert, 99), (Bollobás et al,01):  Preferential attachment (PA) model (Barabási, Albert, 99), (Bollobás et al,01) Parameter: m a positive integer At time 0, add a single edge At time t+1, add m edges from a new node vt+1 to existing nodes the edge vt+1 vs is added with probability Simulation of the model: m=1:  Wilensky, U. (2005). NetLogo Preferential Attachment model. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL. Simulation of the model: m=1 Theorem (Bollobás et al, 01):  Then with probability tending to 1 as t, for all k satisfying 0≤k≤t1/5 Theorem (Bollobás et al, 01) Fix m a positive integer and fix  andgt; 0. For k a non-negative integer, define Theorem (Bollobás, Riordan, 04):  Fix an integer m1 and a positive real number . With probability 1 as t, Gm(t) is connected and Theorem (Bollobás, Riordan, 04) Other web graph models:  (Aiello, Chung Lu, 01) ACL. (Chung, Lu, 03) CL. (Kumar et al, 99) Copying model. (Chung, Lu, 04) CL-del growth-deletion model. (Cooper, Frieze, Vera, 04) CFV growth-deletion model. Other web graph models Properties of the models:  Properties of the models Open problem:  Open problem Design a model that provably has all of the four properties. Infinite graphs:  A new research direction: As time tends to ∞ in on-line models, number of nodes grows Consider infinite limit: union of chain of nodes and edges Limit behaviour studied in other disciplines: Economics (continuum of agents) Physics (lattice structures) Infinite graphs Slide30:  Infinite limit graph loses some properties of finite system: -nodes have infinite degree Certain structural properties are magnified: -self-similarity Slide31:  Theorem (Erdős,Rényi, 63): The random process generates a unique isomorphism type of graph with probability 1. 0 1 2 3 4 5 6 paradoxical: random process with deterministic conclusion Infinite random graph:  Infinite random graph unique isomorphism type, R Infinite random graph, Rado graph, universal homogeneous graph, … R focus of intensive research for over 50 years Graph theorists Logicians Probabilists Group and semigroup theorists Topologists Copying models:  Copying models New nodes copy some of the link structure of an existing node Motivation: web page generation mutation in biology Slide34:  u v x y Limits of copying models:  Limits of copying models (Bonato,Janssen, 04): Start with a finite graph H At each time-step, choose a node u, and choose a subset S of N(u) Add a node z joined to S Do for all u and S Resulting limit is RH Non-isomorphic RH:  Non-isomorphic RH The graph RH admits a homomorphism to H (using a greedy colouring) There are infinitely many non-isomorphic RH for example, RK3 is not isomorphic to RK4 Properties of RH :  Properties of RH Almost surely limits of graphs generated by copying model (with initial graph H) isomorphic to RH Inexhaustible: for all nodes x, RH-x isomorphic to RH Isomorphism type related to dismantling orderings on finite graphs studied by Nowakowski, Winkler Rich endomorphisms (Bonato, P. Cameron, Delic, 06) A variation: ↑G:  A variation: ↑G ↑G formed by extending closed neighbour sets N[u] starting with G Inexhaustible Locally R All countable graphs are induced subgraphs of ↑G Isomorphism types characterized (Scott, Charbit,06) A variation: R(n):  A variation: R(n) Extend only sets of cardinality n gives R(n) Theory is connected to a new finite graph class: n-ordered graphs, which generalize partial n-trees R(n) is the limit of a random process Joint work with J. Janssen and C. Wang Limits for PA models:  Limits for PA models In 2005, J. Kleinberg and R. Kleinberg considered limits of preferential attachment models Limits of PA models: m=1,2: unique limit mandgt;2: limit not unique Proofs use martingale techniques Research Directions:  Research Directions Limits of graphs generated by models. graph searching and sweeping, graph homomorphisms, endo/automorphisms, adjacency properties. Global theory for self-organizing networks. definitions, concentration results (eg via differential equations); node deletion models. Dynamics in networks. modelling viruses and worms, network attacks, network congestion and routing. Slide42:  Preprints, reprints, contact: Google: 'Anthony Bonato'

Add a comment

Related presentations

Related pages

Giovanni Bonato: O lilium convallium - Vokalna Akademija ...

22nd National Choir Competition Slowenia - Opening Concert, April 20, 2012, Maribor, Unionska dvorana, Vokalna Akademija Ljubljana, Stojan Kuret ...
Read more

John Bonato |

View John Bonato's business profile and see work history, affiliations and more.
Read more

Marcelo Bonato - Google+

Marcelo Bonato. 1,502 views. About Posts Photos Videos. Stream. In his circles. 3 people. Tiago Bonato. Flavio Crovador. Mcc Comunicação.
Read more

Italian customs Police Academy visit to HQ Allied Force ...

Italian customs Police Academy visit to HQ Allied Force Command Madrid Madrid, 3 October 2011. On September 15, all the Officer Cadets of the Italian ...
Read more

MARIST SM AUSTRALIA - Marist Mission Centre

MARIST SM AUSTRALIA Australian Marist Mission Centre (MMC) People you support through MMC who do not make headlines but make a difference Sarnelli is near ...
Read more

Towards a European Circular Economy Congress

Danilo Bonato Managing Director . WEEE 2020: a Circular Economy Program Secondary ... MöbiusWorldLoop MCC Telecom MARAS Eurometaux Murata Outotec OVAM
Read more

Rappresentanza Permanente d'Italia presso il Consiglio ...

... (Kabul) with General Bonato. Iraq. ... as Commander of the MCC (Maritime Component Command).. ^^^^^ - It should also be noted that, Italy ...
Read more

Teboho Nthoana | LinkedIn

View Teboho Nthoana's (South Africa) professional profile on LinkedIn. LinkedIn is the world's largest business network, helping professionals like Teboho ...
Read more