### Create a StudySoup account

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

Already have a StudySoup account? Login here

# 675 Class Note for PHYS 597A with Professor Albert at PSU

### View Full Document

## 24

## 0

## Popular in Course

## Popular in Department

This 20 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Pennsylvania State University taught by a professor in Fall. Since its upload, it has received 24 views.

## Similar to Course at Penn State

## Reviews for 675 Class Note for PHYS 597A with Professor Albert at PSU

### 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: 02/06/15

Random graph theory ErdosR nyi algorithm Publ Math Debrecen 6 290 1959 39 fixed node number N 39 39 39 39 connecting pairs of nodes with probability p p0 p01 p015 NN 1 Expected number of edges 11 p 2 Random graph theory studies the properties of graphs with N oo The properties of random graphs depend on p Properties studied does the graph contain cliques complete subgraphs does the graph contain a large cluster is the graph connected what is the diameter of the graph Some of these properties appear suddenly at a threshold pCN 0if MN 0 pJN 11f pN oo Evolution of a random graph Assume that the connection probability is a powerlaw of N p ch Assume that 2 increases from 00 to 0 Look for trees cycles circuits and cliques in the graph m Appearance thresholds pNNZ 1 g 1 Hh 35181 The graph contains cycles of any length if z 2 1 calh z 2 Clusters in a random graph For p lt N 1 the graph contains only isolated trees If p cN I with c lt I the graph has isolated trees and cycles At p cN39I with c I a giant cluster appears The size ofthe giant cluster approaches N rapidly as c increases Sf1fcN The graph becomes connected if p 2 lnNN Node degrees in random graphs average degree k E pN Pk degree distribution Pk E CzkakU UN H Most of the nodes have approximately the same degree The probability of very highly connected nodes is exponentially small Path lengths in random graphs Random graphs tend to have a treelike topology with almost constant node degrees 39 nr of first neighbors N Eltk nr of second neighbors NZ sltkgtz estimate average path length ltkiN l This scaling was proven by Chung and Lu Adv Appl Math 26 257 2001 There is no local order in random graphs Measure of local order Cl 5 L klkl 12 Since edges are independent and have the same probability p n kiki1 i P 2 Q Cap Ill The clustering coefficient of random graphs is small Are real networks like random graphs As quantitative data about real networks becomes available we can compare their topology with that of random graphs Starting measures N ltkgt forthe real network Determine I C and Pk for a random graph with the same N and ltkgt lnN rand Crand p N Pm k E Czkv ka 1 UN H Measure I C and Pk for the real network Compare l ogltkgt Path length and order in real networks I lnN rand 15 I I I Vfood webs ineural negNork A A A powerng A Acollaboration networks 102 39I X vavw 39 4 39 10 lmetabolic networks A lnternet x r Q 39food webs x V 10quot neural network x a metabolic networks A x X power grid 5 I collaboration networks I x 10396 WWV it o 0 l2 l4 l6 I8 10 10 8 I I 39 10 10 10 N 10 10 10 100 102 104 106 108 N Real networks have short distances like random graphs yet show signs of local order New model Smallworld networks Real networks resemble both regular lattices and random graphs perhaps they are in between WattsStrogatz model D Watts 8 Strogatz Nature 393 440 1998 Regular Smallworld 39 lattice with K neighbors rewire edges with probability p 30 p1 lncreasmg randomness 3 K 2 11 g a NM N 5 2K 4 K I an N Is there a regime with small land large C Transi ion from a lattice to a small world 14 n n1 m n D Ell D g I as 39 n Cp C0 0L LlplgLm O a i E39 0 1 39 39 00001 i0001 001 i 01 l p lattice small world random There is a broad interval of p over which C11 C0 but 10511 The onset of the smallworld behavior depends on the system size NId 1Np K fPKN d is the dimension of const if u ltlt 1 the lattice fulnuu ifu gtgt 1 C19 C01P3 These results cannot be directly compared to most real networks because the rewiring probability p is not known Degree distribution of a smallworld network rewiring does not change the average degree but modifies the degree distribution kgtK Pk depends on the rewiring parameter p but is always centered around ltkgt Degree distribution similar to that of a random graph with exponentially small probability for very highly connected nodes Ex 1 A random graph has average degree ltkgt10 How much is the average distance between nodes for N10nr where n2 3 Ex 2 The same question for a ring lattice where every node has degree 10 Ex 3 A variant of the WattsStrogatz model adds random edges to a regular lattice with probability p Start with a ring lattice with 12 nodes For each node throw with a dice and if the number is even throw with two dice and connect the original node with the node whose number you obtained What is the degree distribution before and after What is the largest distance from node 1 before and after The degree distribution of real networks is not peaked at all 03 025 02 A 31 B4 015 01 005 k Nodes with small degrees are most frequent The fraction of highly connected nodes decreases fast WWW IS a powerlaw U 10 a 102 7 E a 7 7 7 1oquot 7 O 7 7 7 A P logic 245 5 10 6 7 7 3 7 7 quot f g If Pin 16 2391 75 1o 7 O 7 7 7 10quot 7 7 7 7 10712 2 U 2 4 6 2 U 2 4 O 6 10 1O 1O 1O 1O 10 1O 1O 1O 10 k k R Albert H Jeong AL Barab si Nature 401 130 1999 A Broder eta Comput Netw 33 309 1999 Powerlaw degree distributions were diverse networks Internet router level Actor collaboration oundin 1o 10quot 10 2 P0010 Pk k39 104 10 5 10 5quot O i i i i i i 39 Go a u b O 7 00 7 00 E 7 00 7 7 RE Q E u Qb 93m 10quot 101 1o2 103 101 102 103 k Pkk39 R Govindan H Tangmunarunkit IEEE Infocom 2000 A L Barab si R Albert Science 286 509 1999 Networks of science collaborations also have powerlaw degree distributions Coauthor HEP Coauthor neurosci 10 i i i i i i 10quot 9o 7 7A 7 ltgtltgt c d 1072 00 H 7 000 Pk1o 7 0 7 7 A 4 000 21 Pkk39 1 O7 7 elk 7 Pkk 5 1 Aam 1076 l l l l l l 10 1o 102 10510 10 1o2 105 k J ewman ys ev AL Barabasi et al condmat0104162 2001 Even metabolic networks have a powerlaw degree distribution Archaeoglobus f C elegans A 100 10quot 104 103 104 10 10467 Iillllll Illlilil Iiiuil In e Out Ei 10 r 10quot 102 10 104 105 C 10639 Hm 10 102 103 10 10D 10 k k 102 103 E coli H Jeong et al Nature 407 651 2000 Pine z Ir PM k z Ir The scalefree degree distribution indicates a heterogeneous topology Pk log Pk New models are needed to reproduce this feature

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

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

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

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

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

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