MMC Bonato

Information about MMC Bonato

Published on June 26, 2007

Author: BAWare

Source: authorstream.com

Content

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'

Related presentations


Other presentations created by BAWare

Integration into the SDLC
30. 08. 2007
0 views

Integration into the SDLC

hot topic
28. 09. 2007
0 views

hot topic

hispanics
01. 10. 2007
0 views

hispanics

zhang
10. 10. 2007
0 views

zhang

schwa
30. 08. 2007
0 views

schwa

aocc
30. 08. 2007
0 views

aocc

Pedersen
30. 08. 2007
0 views

Pedersen

Mining Sciences
30. 08. 2007
0 views

Mining Sciences

Intelligence Gathering mallorca
30. 08. 2007
0 views

Intelligence Gathering mallorca

ppt00021
30. 08. 2007
0 views

ppt00021

hoe wat over adsl
30. 11. 2007
0 views

hoe wat over adsl

The Healthy Potato
04. 12. 2007
0 views

The Healthy Potato

KINDS OF NOUNS
05. 11. 2007
0 views

KINDS OF NOUNS

CUPA 2007 Adv HW part 3
07. 11. 2007
0 views

CUPA 2007 Adv HW part 3

p Javier Carrillo
14. 11. 2007
0 views

p Javier Carrillo

High Intensity Interval Training
13. 12. 2007
0 views

High Intensity Interval Training

measurement
17. 12. 2007
0 views

measurement

OWASP AppSecEU2006 AJAX Security
30. 08. 2007
0 views

OWASP AppSecEU2006 AJAX Security

Feb05Sepracor
29. 11. 2007
0 views

Feb05Sepracor

aula17
28. 12. 2007
0 views

aula17

lab 04
11. 12. 2007
0 views

lab 04

cattle2000
31. 12. 2007
0 views

cattle2000

Mechanized Logging
02. 01. 2008
0 views

Mechanized Logging

Lightning Safety
03. 01. 2008
0 views

Lightning Safety

water problems
21. 11. 2007
0 views

water problems

mideastmaps
07. 01. 2008
0 views

mideastmaps

schulze
12. 10. 2007
0 views

schulze

Sept 17 03B
19. 11. 2007
0 views

Sept 17 03B

Empowerment2
29. 10. 2007
0 views

Empowerment2

LIU MIT 2006
28. 11. 2007
0 views

LIU MIT 2006

USFS Tourism
22. 11. 2007
0 views

USFS Tourism

omni partner guide pps
02. 10. 2007
0 views

omni partner guide pps

convergence
28. 12. 2007
0 views

convergence

sal mauro 061128
28. 02. 2008
0 views

sal mauro 061128

lec05
29. 02. 2008
0 views

lec05

nypss nsta nov 2003
26. 06. 2007
0 views

nypss nsta nov 2003

Movies MC 061129 3
26. 06. 2007
0 views

Movies MC 061129 3

MOUG 08 2002
26. 06. 2007
0 views

MOUG 08 2002

mold
26. 06. 2007
0 views

mold

moilanen movies
26. 06. 2007
0 views

moilanen movies

mm class 8
26. 06. 2007
0 views

mm class 8

Oceans 2005
26. 06. 2007
0 views

Oceans 2005

C3A6
04. 01. 2008
0 views

C3A6

Session8Massimiliano Claps
21. 03. 2008
0 views

Session8Massimiliano Claps

paper Columbia pipelines
30. 08. 2007
0 views

paper Columbia pipelines

CDW Ches99 Talk
05. 01. 2008
0 views

CDW Ches99 Talk

Marketing Mix IPG Presentation
26. 03. 2008
0 views

Marketing Mix IPG Presentation

Moab Marketing
27. 03. 2008
0 views

Moab Marketing

0Kim
30. 08. 2007
0 views

0Kim

Coglx to cultlx
22. 11. 2007
0 views

Coglx to cultlx

12 Igra 4pm
06. 12. 2007
0 views

12 Igra 4pm

Rao
28. 03. 2008
0 views

Rao

Goorevich Richard
30. 03. 2008
0 views

Goorevich Richard

06MYMRes2
09. 04. 2008
0 views

06MYMRes2

quickreview
10. 04. 2008
0 views

quickreview

MontanaDDpresentatio n060105a
13. 04. 2008
0 views

MontanaDDpresentatio n060105a

The Happy Monkey
29. 11. 2007
0 views

The Happy Monkey

cnea 376
20. 11. 2007
0 views

cnea 376

e know GV Presentation
17. 04. 2008
0 views

e know GV Presentation

SustainabilityCaseSt udies
22. 04. 2008
0 views

SustainabilityCaseSt udies

mark
30. 08. 2007
0 views

mark

Dialectal Differentiation
24. 11. 2007
0 views

Dialectal Differentiation

Chapter01
30. 08. 2007
0 views

Chapter01

n0102 SPIE1
26. 06. 2007
0 views

n0102 SPIE1

tues RMI cloonan
07. 12. 2007
0 views

tues RMI cloonan

Modi
26. 06. 2007
0 views

Modi

mne tools scripts kskassam
26. 06. 2007
0 views

mne tools scripts kskassam

hausmesse vortrag meyer
16. 11. 2007
0 views

hausmesse vortrag meyer

sjw
21. 12. 2007
0 views

sjw

stew cartons
17. 06. 2007
0 views

stew cartons

stellmach tim
17. 06. 2007
0 views

stellmach tim

Twelfth Night 2
17. 06. 2007
0 views

Twelfth Night 2

tuebingen seminar nov 04
17. 06. 2007
0 views

tuebingen seminar nov 04

TNG Presentation1
17. 06. 2007
0 views

TNG Presentation1

THE SCIENCE OF LOVE
17. 06. 2007
0 views

THE SCIENCE OF LOVE

t06B Functions Examples
17. 06. 2007
0 views

t06B Functions Examples

Sunny
17. 06. 2007
0 views

Sunny

28 1330 HARP rohacs hideg
18. 03. 2008
0 views

28 1330 HARP rohacs hideg

Water way Awareness
17. 06. 2007
0 views

Water way Awareness

Watergate Political Cartoons
17. 06. 2007
0 views

Watergate Political Cartoons

Valentine s PPT
17. 06. 2007
0 views

Valentine s PPT

USB FunctionDrv
17. 06. 2007
0 views

USB FunctionDrv

urban legends
17. 06. 2007
0 views

urban legends

unti 17Le 1 Funny stories
17. 06. 2007
0 views

unti 17Le 1 Funny stories

Understanding Political Cartoons
17. 06. 2007
0 views

Understanding Political Cartoons

Week2 Augustineandhisera
17. 06. 2007
0 views

Week2 Augustineandhisera

Tee
09. 10. 2007
0 views

Tee

seshun
13. 11. 2007
0 views

seshun

Locke 1 07
30. 08. 2007
0 views

Locke 1 07

ames tornado
05. 10. 2007
0 views

ames tornado

TEAM 9
08. 11. 2007
0 views

TEAM 9

Ferragina
23. 11. 2007
0 views

Ferragina

robo wk 4 controls
07. 01. 2008
0 views

robo wk 4 controls

ScottStroup
02. 11. 2007
0 views

ScottStroup

dyer w ref
04. 03. 2008
0 views

dyer w ref

act31sld
30. 08. 2007
0 views

act31sld

WA Final
17. 06. 2007
0 views

WA Final

EnB presentatie Fischbacher
30. 08. 2007
0 views

EnB presentatie Fischbacher

What to do in Harrisonburg
17. 06. 2007
0 views

What to do in Harrisonburg