MMC Bonato

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. http://ccl.northwestern.edu/netlogo/models/PreferentialAttachment. 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'