### Create a StudySoup account

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

Already have a StudySoup account? Login here

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

### View Full Document

## 13

## 0

## Popular in Course

## Popular in Department

This 32 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 13 views.

## Similar to Course at Penn State

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

A model with high clustering coefficient Each node of the network can be either 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 no a k1 1 10D Hkak usu N 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 Case study Internet topology 10 4 I l Population 10 Router Router El As A quot a 2 4 AS ltgt E 7 ya 7 Geometric 390 g g F m 39 DenSIty E lt 10 3 G o c l E a lt9 8 10 a 7 E g 09 0 2 3 9 0 o b o 10 55139 10 39 39 o2 10 104 10 10quot 107 1 km Population 1 S ltgt 0 o 39 l0 39 0 ltgt 7 08 lt 9 06 i 3903 7 7 Euclldlan g 3 7 7 Pref attach E E dlstance a 04 g In AS map distribution o 10 02 0 10quot 0 l I 10quot 1039 102 1oquot S H Yook H Jeong AL Barab si PNAS 99 13382 2002 Model for Internet growth Start with a 2D map divided into squares with population density pxy At each step place a new node according to pxy The new node connects to m nodes selected with probability k 139 Parameters Df fractal dimension of density 139Ik j 11g 0C 75 a 6 mm I II rxrrnrmii Case study Citation networks 09 u u m un us mm m w W ms w m was 1939quot W W W W95 W W W l K The number of edges increases faster than the number of nodes The clustering coefficient decreases slowly 1AJ cw 61 m mi in m r quot5 a m 5 3 04 v j W Pref attach present 7 I2 NS 10 1039 m 10 In 10 in39 In in AL Barab si et al Physica A 311 590 2002 Identity in social networks Social networks are composed of groups This group structure can be incorporated into a bipartite graph D Watts P S Dodds M E J Newman Science 296 2002 M E J Newman 8 Strogatz D Watts Phys Rev E 64 026118 2001 A deterministic scalefree model E Ravasz AL Barabasi Phys Rev E 67 026112 2003 Properties of the model 0 10 l I 0 c 1 1o 2 2 m9 610 Q Q 103 8 Q Q 0 4 10 102 103 102 1o3 104 1o5 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 Robustness of complex networks Cells are able to adapt to varying external conditions Ecosystems recover from natural disasters Computers need to compute reliably in the presence of noise or defective components Communication networks function despite local failures Complex systems are able to function in the presence of perturbations robustness Some of this robustness is functional some topological Focus possible robustness to local perturbations that result in loss of edges or nodes Perturbations in complex systems can deactivate some of the edges or nodes increase of path lengths 00 separation into isolated clusters More connected network less effect of an edge removal But bridges are definite points of vulnerability The effect of a node removal depends on the number and characteristics of its edges Resilience to perturbations Topological resilience the remaining nodes are still connected the average distance does not increase We will remove edgesnodes one by one and look at o the size of the giant connected component the average distance between nodes in the giant connected component Influencing factors the type of removal the original topology 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 If lim pN 0the graph contains only isolated trees N oo 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 lim L 00 Ngt lnNN Edge removal Start with a connected ER random graph with conn prob p limLoo Ngt lnNN Remove a random fraction fof the edges Expected result an ER graph with conn prob p1f Connected if lim M N gt In N N 00 For a broad class of starting graphs there exists a threshold edge removal probability such that if a smaller fraction of edges is removed the graph is still connected B Bollobas Random Graphs 1985 Node removal Removing a node deactivates all its edges We can expect that the effect of the node removal will depend on the number of edges it had The size of the connected component will decrease at least by one Assume we have two networks with the same number of nodes and edges and remove a fraction fof the nodes Can the two networks resilience be different Numerical simulations of network resilience Two networks with equal number of nodes and edges ER random graph scalefree network BA model Study the properties of the network as an increasing fraction fof the nodes are removed Node selection random errors the node with the largest number of edges attack Measures the fraction of nodes in the largest connected cluster 8 the average distance between nodes in the largest cluster I R Albert H Jeong AL Barabasi Nature 406 378 2000 Random networks respond similarly to errors and attacks The size S and average path length of the largest cluster 100 10 2 39 El 80 80 III B S 60 E 60 N N h D h D I D 40 a 40 U I 20 IQ I 20 lllllllllllIII D 39 0 I I I IDDHI IEEI 0 00 02 04 06 08 10 f Random failure Targeted attack Similar to an inverse percolation transition Breakdown transition in general random graphs Consider a random graph with arbitrary Pk0 A giant cluster exists if each node is connected to at least two other nodes 18gt 2 ltkgt Cohen et al Phys Rev Lett 85 4626 2000 After the random removal of a fraction fof the nodes ltkgtltkagt1 f k2gtltko2gt1f2k0f1 f Breakdown threshold fc 1 Application random graphs Consider a random graph with connection probability p such that at least a giant cluster is present in the graph k0gt pN ltk5gt pNY pN Find the critical fraction of removed nodes such that the giant cluster is destroyed The higher the original average degree the larger damage the network can survive Scalefree networks are more error tolerant but also more vulnerable to attacks 100 r 0 blue symbols random failure red symbols targeted attack 80 60 81 40 Attacks same breakdown scenario as for random graphs Failures little effect on the integrity of the network Is the low peak in average distance a finite size effect How does the breakdown threshold depend on the size of the network and the degree exponent Breakdown threshold of scalefree random graphs Scalefree random graph with Pk Akquot with k mK fc1 m1 7 3 In nite systems with y lt 3 do not break down under random failure Cohen et al Phys Rev Lett 85 4626 2000 Real scalefree networks show the same dual behavior Du Internet break down if 5 ofthe nodes are eliminated selectively resilient to the random failure of 50 of the nodes 20 a u llllllllllligll I 0 0 M 13H 00 02 04 06 08 10 00 02 04 06 08 10 f blue symbols random failure red symbols targeted attack Similar results have been obtained for metabolic networks and food webs Robustness of scalefree networks 0 o O o oo Failures O 0 0 80 0 O Topologlcal O O O OO 9 O 1 error toleranc y s 3 fc1 R Cohen et al PRL 2000 0 fc f 1 O O O o O O o o 0 O o 00 Attacks 0 O 0 go 00 O O O O 00 Betweenness centrality load Find all the shortest pathways between nodes i andj Cij Determine how many of these pass through node k Ckij The betweenness centrality of node k is Ck 13139 ampCmn L C Freeman Sociometry 40 35 1977 Calculate the betweenness centrality of the nodes in the two graphs For each node determine what is the effect of its removal on the size of the connected component and the distances on the connected component Distribution of betweenness centrality 02 104 L 10 P5g gquotz m w 9 0 A34 10395 ID A m0 1039 in2 103 1047 u1 102 103 104 105 g g K Goh et al PNAS 99 12583 2002 Internet AS loadbased removal quot Lu I I i g 11 5 3 quot39 I I u 39 M r lt5 W V E tSIIjquot HS gelquot 1 v H g inquot III 5 I ILH K Goh et al PNAS 99 12583 2002 Case study NA powergrid Nodes generators transmission substations distribution substations Edges highvoltage transmission lines 14099 nodes 1633 generators 2179 distribution substations the rest transmission substations 19657 edges Connected network power from any generator is in principle accessible to any substation Connectivity Ni N g p d 0I 05 Degree distribution 1 I 39i a ia39 08 n OO 8 06 D O hf Ell E 04 D D E 02 dith 39339 0I I nl O 0 5 10 15 20 3915 k I 0 5 10 15 20 25 K Pk gt K z exp 05K 30 Betweenness distribution and edge range Edge range what would the distance between the endpoints of an edge be if the edge is removed LL 100 E 101 103922 E E 3 5 El E q 3 a 01 D 10 2 n 39 E E 39H 005 O E u 103945 0 Ii I I I I I E 3 0 02 04 06 08 1 3 1 1 105 100 101 102 103 104 105 106 107 L Pl gt L z 2500 L39 397 Connectivity loss for generator removal 60 4 O J O connectivity loss 30 40 50 60 R Albert Albert GN Nakarado Phys Rev E 2004 connectivity loss Connectivity loss for transmission substation removal 100 I cascading 00 O O O 4 O 20

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

#### "I made $350 in just two days after posting 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.