New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Group Study

by: Consuelo Herman DDS
Consuelo Herman DDS
GPA 3.78


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




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.

Popular in Engineering Mechanical & Aero


Reviews for Group Study


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

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


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.