### Create a StudySoup account

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

Already have a StudySoup account? Login here

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

### View Full Document

## 26

## 0

## Popular in Course

## Popular in Department

This 23 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 26 views.

## Similar to Course at Penn State

## Popular in Subject

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

Topological perturbation of complex networks Perturbations in complex systems can deactivate some of the edges or nodes Edge loss the edge is deleted Node loss the node and all its edges are deleted node 39 removal Effects on the global topology g increase of path lengths 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 Appearance thresholds prz zl m 2 A a 1 a Hh 35181 The graph contains cycles of any length if z 2 1 Clusters in a random graph If Zlvim pN 0the graph contains only isolated trees 00 If p cN39I with c lt I the graph has isolated trees and cycles At p cN1 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 NmlnNN Existence of a giant connected cluster in a general random graph G 1 a era es39 eofcl sters s 10 v g lZ u lt 1G1 w k G0x node degree generating G0 x 2Pkx function quot0 G1x generating function for the M k k I degree of an edge endpoint x G1 x Z kPk s 00 when kPk k2 2 equivalent to Q 2 mam ltkgt A giant connected component exists if the graph is sufficiently heterogeneous Edge removal in random graphs Start with a connected ER random graph with conn prob p Ngt lnNN Remove a random fraction fof the edges Expected result an ER graph with conn prob p1f Connected if lim M N In N N X 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 graph evolution 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 k2gtltko2gt1f2k0f1f 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 k0gtpN ltk5gtpN2 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 7 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 1 Rank order the nodes by the effect of their removal What were your criteria in doing so 2 For each node determine what is the effect of its removal on the size ofthe connected component and the distances on the connected component 3 Do the results match your expectations 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 The role of the power grid is to route power from generators to distribution substations and then to customers Connected network power from any generator is in principle accessible to any substation Degree distribution d i iiiiii 10 10 15 20 quot 25 1047 1 396 0 0 5 10 15 20 25 Pk gt K as 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 100 E 10quot E 1 2 10 Q E e i E 9 i E i i 3 a 017 7 10 an o 0057 7 O D 104 0 ii i i i i i i 7 3 o 02 04 06 03 3 1quot 105 i i i i i i i 3 10 10 10 1o 104 105 10quot 107 L Pl gt L m 2500 L 397 Resilience of the NA powergrid The relevant question is whether distribution substations receive enough power Studied measure how many generators can feed a given distribution substation Average connectivity the fraction of generators able to feed a given substation averaged over substations Ni Connectivity loss CL 1 expressed as a percentage N l Generator removal will definitely lead to connectivity loss transmission substation removal not necessarily g Connectivity loss for generator removal A w 0 w 60 A 0 O A o A e g degree based A A 3 I 0 g 407 A o 7 o A o 3911 7 A o 7 g A 0 0 Inme g 20 A o i u A o A o w w w w w w 6 10 20 30 40 50 60 f2 ltgt R Albert Aber1 GN Nakarado Phys Rev E 2004 Connectivity loss for transmission substation removal 100 i loadbased current 00 O a degree based connectivity loss 70 20 random 10 f 1 Highest damage if the next substation to be removed is the current highestload substation Limitations of topological resilience The most relevant measure of connectivity may not be the size of the giant connected cluster The effects of removing a node or edge propagate through the network Eg cascading failure on the power grid gene mutation Depends on the dynamical properties of the network The network topology still determines the boundaries of propagating failure

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

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