### Create a StudySoup account

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

Already have a StudySoup account? Login here

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

### View Full Document

## 29

## 0

## Popular in Course

## Popular in Department

This 44 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 29 views.

## Similar to Course at Penn State

## Popular in Subject

## Reviews for 209 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

Network models Properties common to many largescale networks independently of their origin and function 1 The degree and betweenness distribution are decreasing functions usually powerlaws scale free 2 The distances scale logarithmically with the network size I logN logltkgt 3 The clustering coefficient does not seem to depend on the small world network size and is larger than the clustering coefficient of comparable random graphs There are two model families proposed to explain these properties Small world network models and scalefree network models Benchmark 1 regular lattices Onedimensional lattice l is N k const C const lszsL Nl2 k 6 for inside nodes C i for inside nodes 15 1D The average pathlength varies as 1 R4 N Constant degree coordination number constant clustering coefficient Benchmark 2 random graph theory ErdosR nyi algorithm Publ Math Debrecen 6 290 1959 o 0 fixed node number N 39 39 39 connecting pairs of nodes with probability p po p01 p015 Expected degree distribution Prand k E Cil ka 1 AWN H Expected path length quotmquot 3 0gltk Expected clustering coefficient CHM l ogltkgt 15 10 5 Path length and order in real networks I logN rand neural network X power grid Acollaboration networks vavw lmetabolic networks lnternet X I x i r I Vfood webs Real networks have short distances like random graphs yet show signs of local order Cltkgt 39food webs neural network I metabolic networks X power grid collaboration networks vavw 10 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 p21 lncreasmg randomness 11 Cw a logN 5 2K 4 K I logK 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 d is the dimension of lNp N K fpKN the lattice f const if u ltlt 1 lattice like u nuu If it gtgt 1 random graph like The transition point depends on the rewiring probability the size of the network and the average degree 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 variant of the WattsStrogatz model adds random edges to a regular lattice Start with a ring lattice For each existing edge of a node add an edge with a probability p The endpoint of the edge is selected randomly from all other nodes How many edges do you expect the graph will have after edge addition Ex 2 How do you expect the degree distribution will look like after edge addition Most importantly will it be symmetrical or not kl Kml nl POquot 5 C2Pm1 Pym m Starting pomquot endpoint Pn C 1 To 1 pNKZ n pNKZ N N Minimum K peak KpK The scalefree degree distribution indicates a heterogeneous topology Pk log Pk New models are needed to reproduce this feature We need to uncover the mechanisms responsible for the scalefree Pk random graphs smallworld networks Stat39c scalefree random graphs Real networks continuously change random graphs Homogeneous smallworld networks Scalefree degree distribution the nodes are not equivalent We need to model the evolution of networks not just their topology A simple model of network assembly and evolution BA model Start with a small seed of mo nodes and m0m012 edges growth a node and m edges added at every step k 2 k J J preferential attachment Hk Price J Amer Soc Inform Sci 27 292 1976 Barabasi and Albert Science 286 509 2000 General properties of the network nr of nodes N m0 t m m 1 onrofedges nmt 10392 2n g average degree ltkgt W 2m a 10 degree distribution 1039 Lgrvs I Although the network grows the degree distribution becomes stationary Analytical determination of Pk The degree of old nodes increases by acquiring new edges The probability of this process is ml39Iklm ki NE k 21 J J 1 with prob Degree increase Aki 0 otherwise Choices follow the increase in the number of nodes with degree k rate equation approach follow the increase in time in kcontinuum theory Rate equation approach Change in average number of nodes with degree k k1 gt k k gt k1 dN k l N t kN t k m HO quot 6km lt first node dt Zkaa quot T number of edges normalization of new node PkNktNanktt k 1Pk 1 kPkt 5 ZkPrk x k Plug in Pkm ltkgt Degree distribution The rate equation leads to a recursive relationship between Pk and Pk 1 k 1Pk 1 kPk6 2 km Pk l f0rkgtm k2 Pk 2 m2 f0rkm 2mm 1 3 Leads to Pk m Stationary power law with an exponent 7 3 P Krapivsky S Redner F Leyvraz Phys Rev Lett 85 4629 2000 Continuum theory 139 1 with prob Degree increase M 21 l 0 otherwise Assume that there is a continuous rate of change of k dkl N k 1 dt z t Initial condition kltl m t time when node iwas added to the network Solve for k klttl m J Continuum theory kitgtti n1tZ Calculate the cumulative probability that klttl lt k 2 2 Pktltk 11tigt 2 1 Iti lt25 I All t values are equlprobable PM m0 t We need to find the probability of ti being smaller than a given value Tm2tk2 given the distribution pti PxltX zpx mzt mzt xxltX lt 2 k k m0t PtiltTz 1 1 T Continuum theory 2 2 mzt1 2 mt k k m0t PkltltkI Pttilt The noncumulative degree distribution is the derivative of the cumulative degree distribution with respect to k apnea lt k 2m2t 1 k3 6k m0 t k3 Pk Stationary power law with an exponent 7 3 The functional form of the degree distribution does not depend on m and m0 in the longtime limit Simulations and theory agree u u u 10 my x ocuuu 0 N if XA imam Eu 1 3 Mu mmmuuu u cfwuu vac m m I 1 a a a D a x Ex 1 Start from a seed of two nodes connected by an edge At each step add a new node and connect it by a single edge to a preexisting node Let the probability of selection be directly proportional with the degree of the old node Is there an easy way to do this Continue growing the graph until you reach 15 nodes Describe the graph average degree degree distribution clustering coefficient maximum distance Ex 2 How will the properties of the graph change if at each step a new node and two new edges are added Model A growth re 39 ment 39k uniform w 639 Amie quot at m0 t 1 10393 kl t mlnLt l 1 5 m ti 1 m e k 7 exp 10397 m m a k Characteristic degree scale m Model B M preferential attachment k 1 N k 1 a t A139Iki at N N 10 N 2 N 1 0 kit tCt2 N NN 2 ltkgt 2 quot n 39 N 5 10393 a Pk power law initially gt Gaussian 1o a BA algorithm with directed edges New edges are directed from the new to the old nodes kio39 m for i gt m0 t0 t2 t3 4 kl varies ki gt m k iquot k iquot aki mHkiiquotm i 4 at 2k t j mt mt 1 Pk t ltk 1 P k k392 km0t S m m tk2 The degree exponent ofthe directed scalefree network is 2 How do the other network measures compare with real networks Average path length Clustering coefficient 10 l l l I OBA d l 10quot o 2 Brand graph 11 o C g jg 10392 N 31 D 8 O 10393 O O E O E Odynamic scalefree model 939 1074 random graph U 10395 392 393 394 5 10 10 10 10 N Average distances smaller in the BA model than in equivalent random graphs but not as small as in scalefree random graphs Clustering coefficient decreases with network size B Bollobas and O Riordan in Handbooks ofGraphs and Networks 2003 Evolving network models The scalefree model is only a minimal model Makes the simplest assumptions linear growth ltkgt 2m linear preferential attachment Hk oc k Does not capture variations in the shape of the degree distribution variations in the exponent of the powerlaw region the sizeindependent clustering coefficient Hypothesis the basic mechanisms need to be augmented by the incorporation of addition of edges without new nodes edge rewiring removal node removal Preferential attachment in real networks citation K0 neurosci 4 39 10 xkZIIK Kltk Internet no pref attach linear pref attach HkAk asl actor collab Consequences of nonlinear preferential attachment HkzAk 6131 A initial attractiveness 1 Sublinear preferential attachment leads to a stretch exponential degree distribution Pk z exp kk0 P Krapivsky S Redner F Leyvraz Phys Rev Lett 85 4629 2000 2 Initial attractiveness only shifts the degree exponent A 7 2 m Dorogovtsev Mendes Samukhin Phys Rev Lett 85 4633 2000 Growth constraints and aging cause cutoffs 10 E 10quot a 3 E 10 FInIte lifetime to achIre g quotg 104 new edges 3 13104 E5 0 No aging 510 S ltgt Slow aging U J Fastaging 1 107 1 1 0 100 1000 10000 Number of edges L A N Amaral et al PNAS 97 11149 2000 Gradual aging Hkl cc kl t tlquot39 y increases with v S N Dorogovtsev and J F F Mendes Phys Rev E 62 1842 2000 Additional processes also change the degree exponent mp new edges Pk N k k0quot 097 fp9q9m mq edges rewired R Albert AL Barabasi Phys Rev Lett 85 5234 2000 o c edges added or removed 1 12c y2 S N Dorogovtsev J F F Mendes Europhys Lett 52 33 2000 Example of an evolving network model At each step a choice is made between three possible mechanisms m new edges one node selected randomly the other with preferential attachment kl 1 clone with probability p Ham 2 k 1 J J o m edges rewired disconnected from a randomly selected node and connected to a node using pref attach done with probability q o a new node added with m edges that connect to nodes selected with preferential attachment done with probability 1pq Continuum theory dk39 dt 7 q N 200 random 139 preferential edge gain edge loss edge gam Pk z k k0 q m7pqm 2 1 k0p q m P IIH lj1 2m1q1 p q1 m 70011 m R Albert AL Barab si Phys Rev Lett 85 5234 2000 Continuum theory Pk R k k0 pqm7p q m onlyvalidif p q 1m1gt0 Elsewhere the degree distribution becomes an exponential pOWe r l aw an 112 04 as us 10 Rate equation approach de 1 k pm Nk l m Nk 1 dt N ij k1gtk rand J k1k pref 1 k1 pqm Nk m Nk N 20 1 j k gtk1 rand k gtk1 rand k gtk1 pref 1 quNk1 6km k1gtk rand Can Latecomers Make It BA model k tt 0 t 12 rst mover advantage Real systems nodes compete for links tness Fitness Model tness 7 name 39 k39 m k kntmW where l mu eve Madam 1 BoseEinstein Condensation in Evolving Networks k Network Hi m Bose gas 2139quotij 84 1 iiiiiiiii H 86 3 wk 1 e 81 e quot 83 85 40 0 0 078 BoseEinstein condensation G Bianconi and AL Barab si Physical Review Letters 86 5632 2001 Mechanisms for preferential attachment 1 Copying mechanism directed network select a node and an edge of this node attach to the endpoint of this edge 2 Walking on a network directed network the new node connects to a node then to every first second neighbor of this node 3 Attaching to edges select an edge attach to both endpoints of this edge A model with high clustering coefficient Each node of the network can be either active or inactive There are only rn active nodes in the network at any instance Start with rn active completer connected nodes At each timestep add a new node active that connects to rn active nodes Deactivate one active node Pd ki o a k1 1 10D Hkak usu H kZ um Uau ciusienng memmem c um n i 2 w w in w in network Size N K Klemm and V Eguiluz Phys Rev E 65 036123 2002 A deterministic scalefree model Start with a completely connected graph with five nodes one central four peripheral Make four copies of the graph keep the original in the center Connect the four peripheral nodes of each copy to the central node of the original Make four copies of the graph again connect peripheral nodes to the central node 8 5clique A deterministic scalefree model connect peripheries to central node E Ravasz AL Barabasi Phys Rev E 67 026112 2003 Ex 1 How does the number of nodes increase as a function of time steps Ex 2 How does the number of edges increase as a function of time steps Ex 3 How does the degree of the central node increase in time Ex 4 Can you identify the highest degree nodes Prooerties of the model 9 lt Q Q Q Q o0 1 01 102 1 o3 k Degree distribution Clustering coefficient 10 I I g 0 10391 A m 402 Q Q 103 Q 104 C 102 1o3 104 105 N x k l ln4ln3 C z 06 independent of network size Hierarchical structure ID 39 39n39 m P 1dquot 100 b W a 39 m39 u 5 5 to W 7 E 1E1quot E E 123quot m U 5 10 13 i I g ml l3 4 l L Inquot H 11 m m m 1gquot 1u Is it Average clustering coefficient of 1 nodes with degree k Ck z k Also observed in various cellular networks sign of hierarchical modular architecture E Ravasz et al Science 297 1551 2002 Lessons learned from evolving network models 1 There is no universal exponent characterizing all networks 2 The origins of the preferential attachment might be system dependent 3 It is generally true that networks evolve 4 Modeling real networks identify the processes that play a role measure their frequency from real data develop dynamical models that capture these processes

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

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

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I 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."

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