Group Study MAE 298
Popular in Course
Popular in Engineering Mechanical & Aero
This 28 page Class Notes was uploaded by Consuelo Herman DDS on Tuesday September 8, 2015. The Class Notes belongs to MAE 298 at University of California - Davis taught by Staff in Fall. Since its upload, it has received 18 views. For similar materials see /class/187472/mae-298-university-of-california-davis in Engineering Mechanical & Aero at University of California - Davis.
Reviews for Group Study
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/08/15
MAE 298 Lecture 5 April 13 2006 Optimization and network growth Recall Preferential Attachment process Origins of preferential attachment 1923 Polya urn models 1925 Yule explain genetic diversity 1949 Zipf distribution of city sizes 1f o 1955 Simon distribution of wealth in economies The rich get richer o Interesting note in sociology this is referred to as the Matthew effect after the biblical edict For to every one that hath shall be given Matthew 2529 An alternate view Mandelbrot 1953 optimization Information theory of the statistical structure of language a Goal Optimize information conveyed for unit transmission cost a Consider an alphabet of d characters with n distinct words a Order all possible words by length ABCAABBCC Cost of jth word Cj N logdj 0 Ave information per word H ijlogpj Ave cost per word 0 ijCj Minimize g gt pj Nj O Optimization versus Preferential Attachment origin of power laws Mandelbrot and Simon s heated public exchange a A series of six letters between 195961 in Information and Control a Optimization on hold for many years but recently resurfaced o Calson and Doyle HOT 1999 o Fabrikant Koutsoupias and Papadimitriou 2002 o SOI 2002 From Barab si and Albert to FKP o Barabasi and Albert Emergence of Scaling in Random Networks Science 286 1999 A preferential attachment model of network growth 0 A Fabrikant E Koutsoupias and C HPapadimitriou Heuristically Optimized Trade offs Lecture Notes In Computer Science ICALP 2002 2380 2002 FKP extend the ideas of Carlson and Doyle to network context 0 JM Carlson and J Doyle Highly optimized tolerance A mechanism for power laws in designed systems Physical Review E 1999 See also JM Carlson and J Doyle Complexity and Robustness PNAS 2002 o For a recent press account of optimization versus power laws see Sara Robinson Recent Research Provides New Picture of Route rLevel Internet Computing in Science amp Engineering 8 2 MarchApril 2006 pp 36 FKP Fabrikant Koutsoupias and Papadimitriou 2002 o Nodes arriving sequentially at random in a unit square o Upon arrival each node connects to an already existing node that minimizes cost Oddij h Using R to explore the FKP model a a0imit o a gtoo limit inbetween FKP degree distribution FKP vs dFKP N500 alphagamma5 FKP vs dFKP N1000 alphagamma5 FKP vs dFKP N2000 alphagamma5 8 E 8 8 I n n 39 FKP 39 o FKP 8 4 N dFKP w100 E g c Clquot o I o n n v o o 0quot A o A A 5 I 5 m 5 8 a r a 9 n I D D n D 39 lt1 or 1 3 E 13gt I m n O gt h39 I i hquot n if oulz 39 39 I I I I I I I v I I I I I I I I I I I I I I I 1 2 5 1O 2O 50 100 1 2 5 1O 2O 50 100 200 1 2 5 1O 2O 50 100 200 500 n degree k n degree k n degree k A bimodal distribution hubs and leaves but almost all nodes are leaves For details see N Berger and B Bollobas and C Borgs and J Chayes and O Riordan Degree distribution of the FKP network model Lecture Notes In Computer Science ICALP 2003 2003 CompetitionInduced Preferential Attachment N Berger C Borgs J Chayes RD R Kleinberg ICALP 2004 o Like FKP start with linear tradeoffs but consider a scalefree metric Plus will result in local model o Show how mechanism of PA arises but with eventual saturation PA w Saturation in turn gives with to Power Laws with eventual Exponential Decay o Such distributions observed ubiquitously in nature Saturation like PA has previously been used as axiom to explain data Competition Induced Preferential Attachment Consider points arriving sequentially uniformly at random along the unit line III I I III 0 Hi i Each incoming node t attaches to an existing nodej wherej lt t which minimizes the function th minj O udtj M Where oatj ozptj antjdtj The cost becomes th minj 047123 hj Ej minj 0mm i 0 am ozptj local density eg real estate in Manhattan a Reduces to ntj number of points in the interval between t and j o Transit domains captures realistic aspects of Internet costs ie ASISPtransit requires BGP and peering 0 Like FKP tradeoff intia connection cost versus usage cost 0 Note cases oz 0 and oz gt 1 The process on the line for 13 lt a lt 12 Border Toll Optimization Problem BTOP th minj omtj F30 a t1 F10 0 F3 F32 1 0 1 0 2 3 1 F31 1 F40 3 a F 20 0 t2 Q i 14 m Fem 12 F21 1 F43 1 a 0 2 1 0 2 3 1 4 F41 1 Fertility 0 23 1 m l t4 0 23 1 4 Node 1 becomes fertile at time t 3 Define A 104 a A node must have A 1 infertile children before giving birth to a fertile child Mapping onto a tree equal in distribution to the line 9 i1 i2 i4 1 A N i n 2 3 1 From line to tree Integrating out the dependence on interval length from the conditional probability Prmt1 e 1k mm Prxt1 e 1k 7tt t dP t SklttgtdPlt lttgtgt ie The probability to land in the kth interval is uniform over all intervals Preferential attachment with a cutoff Let djt equal the degree of fertile nodej at time t The number of intervals contributing to j s fertility is 1r1rlatxdj7 7 A Probability node t 1 attaches to node j is P7 t l 1 gt j maxdjt At l 1 The process on degree sequence Can go through a similar heuristic derivation as with PA Let N0t E number of infertile vertices Let Nkt E number of fertile vertices of degree k for 1 g k lt A Let NAt E number of fertile vertices of degree k 2 A Le NAt 22 Nkt the tail 0 1 2 3 4 000 AA1 ooo Recursion relation 19k k 1pk1t kpkt 1lt k lt A and Pk 1 Pk k 2 A Implies pk H122 221 1lt k lt A and 1 P1 Power law for 1 lt k lt A i l i1 c 2 k H i2 Exponential decay for k gt A Recursion relation pk A pk1 pk k 2 A Implies A k A Pk fl 1 PA k 2 A 1 kA 1 AH k AA1 1 pk 1 A1gt 19A A1gt M N exp k AA 1pA 1 1 Degree sequence summary elk 7 for kltA Cgexp kA1 for kgtA Power law gt power law with exponential tail Ubiquitous empirical measurements Saturation and PA often put in apriori to explain with p 13 N 33 exp 13 B map map as function of spatial distance ArXiv coauthor network paper Fitting the WHOIS AS level Internet data 39Whois39 AS data with CIPA fit 1eOO I ccdf 1e 02 1e O4 degreed Definitely not a power law so previously no model to explain distribution CIPA PA g a A 53 x Comparing CIPA and PA graphs Network growth models Preferential attachment Heuristically Optimized Tolerance o CompetitionInduced Preferential Attachment o Validation but what does this really mean can only validate aspects Further reading a A Fabrikant E Koutsoupias and C HPapadimitriou Heuristically Optimized Tradeoffs Lecture Notes In Computer Science ICALP 2002 2380 2002 FKP extend the ideas of Carlson and Doyle to network context JM Carlson and J Doyle Highly optimized tolerance A mechanism for power laws in designed systems Physical Fieview E 1999 See also JM Carlson and J Doyle Complexity and Robustness PNAS 2002 a N Berger C Borgs J Chayes R D Souza R Kleinberg CompetitionInduced Preferential Attachment Lecture Notes in Computer Science ICALP 2004 3142 208221 2004