### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Group Study MAE 298

UCD

GPA 3.78

### View Full Document

## 27

## 0

## Popular in Course

## Popular in Engineering Mechanical & Aero

This 48 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 27 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

### 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 3 April 6 2006 Network Growth Models Recall Properties of ErdosR nyi random graphs 1 Phase transition in connectivity at average node degree 2 1 Le 19 2 Poisson degree distribution pk zkeZk 3 Diameter d N log N a smallworld network 4 Clustering coefficient none Properties 1 and 3 are in Iine with realworld networks but not properties 2 and 4 Degree distribution a A large number of real world networks from an extensive range of applications have heavytailed degree distributions Also can be considered broadscale The simplest example of such a distribution is a power law What is a power law Also called a Pareto Distribution in statistics Pk N 76 7 lnpk N ylnk 1904 1901 i i 1e07 i 1e10 i i i 1 100 10000 Properties of a power law distribution See chalk board discussion Essentially Properties of a power law PDF Summary PDF probability density function a To be a properly defined probability distribution need 7 gt 1 For 1 lt 7 g 2 both the average k and standard deviation 02 are infinite For 2 lt 7 g 3 average k is finite but standard deviation 02 is infinite For 7 gt 3 both average and standard deviation finite Power laws in the real world Confusion Power law Log normal 0 WGlbU All three of these distributions can look the same Especially when we are dealing with finite data sets not enough data to get good statistics How to deal with real data a Can adjust bin size increase exponentially with degree 0 Consider the Cumulative PDF the CDF Pk 2fka For more details see 0 Newman Review pages 1213 a Mitzenmacher Review reference given at end But definitively observed in many systems a Signature of a system at the critical point of a phase transition 0 Random graphs at critical point N CiAi 7n2054247 Note 7 25 8 Power laws in social systems o Popularity of web pages Nk N 1 0 Rank of city sizes Zipf s Law Nk N k 1 Pareto In 1906 Pareto made the now famous observation that twenty percent of the population owned eighty percent of the property in Italy later generalised by Joseph M Juran and others into the socalled Pareto principle also termed the 8020 rule and generalised further to the concept of a Pareto distribution Usually explained in social systems by the rich get richer preferential attachment Known Mechanisms for Power Laws 0 Phase transitions singularities a Random multiplicative processes fragmentation o Combination of exponentials eg word frequencies a Preferential attachment Proportional attachment Polya 1923 Yule 1925 Zipf 1949 Simon 1955 Price 1976 Barabasi and Albert 1999 Attractiveness is proportional to size dPs dt 0C8 Origins of preferential attachment 1923 Polya urn models 1925 Yule explain genetic diversity 1949 Zipf distribution of city sizes 1f 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 Preferential attachment in networks D J de 8 Price Cumulative advantage o D J de 8 Price Networks of scientific papers Science 1965 First observation of power laws in a network context Studied paper cocitation network a D J de 8 Price A general theory of bibliometric and other cumulative advantage processes J Amer Soc Info Sci 1976 Cumulative advantage seemed like a natural explanation for paper citations The rate at which a paper gains citations is proportional to the number it already has Probability to learn of a paper proportional to number of references it currently has Preferential attachment in networks continued Cumulative advantage did not gain traction at the time But was rediscovered some decades later by Barabasi and Albert in the now famous about 1000 citations in SCI paper Emergence of Scaling in Random Networks Science 286 1999 They coined the term preferential attachment to describe the phenomena The Barab si and Albert model A discrete time process 0 Start with single isolated node a At each time step a new node arrives o This node makes m connections to already existing nodes Why m edges We are interested in the limit of large graph size Probability o Probability incoming node attaches to node j Prltt1 gtj djzjdj o Probability incoming node attaches to any node of of degree k Odes 01 degree k nodes X degree of that node degree sum over all nodes km 2 km 2k dk Zmn Network evolution Process on the degree sequence a Note that pk will change in time So we show denote this explicitly pm a Also when a node of degree k gains an attachment it becomes a node of degree k 1 a When the new node arrives it increases by one the number of nodes of degree m Markov flow 0 A 000 Process on the degree sequence cont Let nkgt E number of nodes of degree k at time t and 71 E total number of nodes at time t Note 71 t For each arriving link k 1 k For k gt m nkat1 nkat nk1t Z W nkat o Fork m nm 1 nmt1 2 mtnmt But each arriving node contributes m links m k l k For k gt 771 nkt 1 nkt gm mic 115 71km m2 0 For k m nm 1 nmt 1 2 mt 71mg oFOFkgtm2 Forkm Translating back to probabilities Pkg lms7105 mat75 gt 71km 75pm 751Pkt1 tpkmf 11 k Pk 1t 5 Pkg 13 1 pmt1 7519mm 1 Pong Steadystate distribution We want to consider the final steadystate pm pk oFOFkgtm2 Forkm oForkgtmz Forkm t1Pkthk2lPk 1 Pk t1pmtpm1pm Rearranging and solving for pk Recursing to pm k 1k 2m mm1m2 2 W Z k2k1m3 39pm k2k1k 39 m1 2mm1 pk k2k1k Forkgtgt1 Pk N 76 3 Did we prove the behavior of the degree distribution Details glossed over 1 Proof of convergence to steadystate 2 Proof of concentration Need to show fluctuations in each realization small so that the average nk describes well most realizations of the process For this model we can use the secondmoment method show that the effect of one different choice at time 15 dies out exponentially in time Issues Whether there are really true powerlaws in networks Usually requires huge systems and no constraints on resources Only get 7 3 Generalizations of Pref Attach a Vary steps of PA with steps of random attachment o Consider nonlinear PA where probattaching to node of degree k N dkb Simulating PA Basic code for simulating PA with m 1 using R runPA H functionN100 outLinki is the parent of i outLink H numericN numlinksi is number totallinks in and out for node i numLinks H numericN1 fori in 2N p H samplec1i1size1probnumLinks1i1 outLinki H p numLinksp H numLinksp1 returnlistoutLink numLinks i i x A V a a a E r x K 4 a x x K 1 x 1 4 a v U 4 x a Visualizing a PA graph m 1 at n 5000 Further reading All refs available on references tab of course web page PA model of network growth a Barabasi and Albert Emergence of Scaling in Random Networks Science 286 1999 o B Bollobas O Riordan J Spencer and G Tusnady The degree sequence of a scalefree random process Random Structures and Algorithms 183 279290 2001 Newman Review pages 3035 Durrett Book Chapter 4 Further reading cont Fitting power laws to data 0 Newman Review pages 1213 0 M Mitzenmacher A Brief History of Generative Models for Power Law and Lognormal Distributions Internet Mathematics1 2 226251 2003 MAE 298 Lecture 3 April 6 2006 Network Growth Models Recall Properties of ErdosR nyi random graphs 1 Phase transition in connectivity at average node degree 2 1 Le p 2 Poisson degree distribution pk zkeZk 3 Diameter d N log N a smallworld network 4 Clustering coefficient none Properties 1 and 3 are inIine with realworld networks but not properties 2 and 4 Degree distribution A large number of realworld networks from an extensive range of applications have heavytailed degree distributions o Also can be considered broadscale o The simplest example of such a distribution is a power law What is a power law Also called a Pareto Distribution in statistics Pk N 76 lnpk N ylnk 1904 1901 i i 1e07 i 1e10 i i i 1 100 10000 Properties of a power law distribution See chalk board discussion Essentially Properties of a power law PDF Summary PDF probability density function a To be a properly defined probability distribution need 7 gt 1 For 1 lt y g 2 both the average k and standard deviation 02 are infinite For 2 lt 7 g 3 average k is finite but standard deviation 02 is infinite For 7 gt 3 both average and standard deviation finite Power laws in the real world Confusion Power law Log normal 0 WGlbU All three of these distributions can look the same Especially when we are dealing with finite data sets not enough data to get good statistics How to deal with real data a Can adjust bin size increase exponentially with degree 0 Consider the Cumulative PDF the CDF Pk 2fka For more details see 0 Newman Review pages 1213 a Mitzenmacher Review reference given at end But definitively observed in many systems a Signature of a system at the critical point of a phase transition 0 Random graphs at critical point N CiAi 7n2054247 Note 7 25 8 Power laws in social systems o Popularity of web pages Nk N 1 0 Rank of city sizes Zipf s Law Nk N k l Pareto In 1906 Pareto made the now famous observation that twenty percent of the population owned eighty percent of the property in Italy later generalised by Joseph M Juran and others into the socalled Pareto principle also termed the 8020 rule and generalised further to the concept of a Pareto distribution 0 Usually explained in social systems by the rich get richer preferential attachment Known Mechanisms for Power Laws 0 Phase transitions singularities a Random multiplicative processes fragmentation o Combination of exponentials eg word frequencies a Preferential attachment Proportional attachment Polya 1923 Yule 1925 Zipf 1949 Simon 1955 Price 1976 Barabasi and Albert 1999 Attractiveness is proportional to size dPs dt 0C8 Origins of preferential attachment 1923 Polya urn models 0 1925 Yule explain genetic diversity 1949 Zipf distribution of city sizes 1f 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 Preferential attachment in networks D J de 8 Price Cumulative advantage o D J de 8 Price Networks of scientific papers Science 1965 First observation of power laws in a network context Studied paper cocitation network D J de 8 Price A general theory of bibliometric and other cumulative advantage processes J Amer Soc Info Sci 1976 Cumulative advantage seemed like a natural explanation for paper citations The rate at which a paper gains citations is proportional to the number it already has Probability to learn of a paper proportional to number of references it currently has Preferential attachment in networks continued Cumulative advantage did not gain traction at the time But was rediscovered some decades later by Barabasi and Albert in the now famous about 1000 citations in SCI paper Emergence of Scaling in Random Networks Science 286 1999 They coined the term preferential attachment to describe the phenomena The Barab si and Albert model A discrete time process 0 Start with single isolated node a At each time step a new node arrives o This node makes m connections to already existing nodes Why m edges 0 We are interested in the limit of large graph size Probability o Probability incoming node attaches to node j Prltt1ejgt djzjdj o Probability incoming node attaches to any node of of degree k nodes of degree k nodes x degree of that node degree sum over all nodes km 2 km 2k dk Zmn Network evolution Process on the degree sequence 0 Note that pk will change in time So we show denote this explicitly pm a Also when a node of degree k gains an attachment it becomes a node of degree k 1 a When the new node arrives it increases by one the number of nodes of degree m

### 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

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION 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 support@studysoup.com

#### STUDYSOUP REFUND POLICY

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: support@studysoup.com

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 support@studysoup.com

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.