### Create a StudySoup account

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

Already have a StudySoup account? Login here

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

### View Full Document

## 12

## 0

## Popular in Course

## Popular in Department

This 28 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 12 views.

## Similar to Course at Penn State

## Reviews for 233 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 studied in the literature the remaining nodes are still connected the average distance does not increase Ex Propose other measures of resilience Testing resilience to incremental damage 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 Ex What factors affect the topological resilience of a network Review components in a random graph Erd6sR nyi uniform random graph olf pN 0 the graph contains only isolated trees If p cN39I with c lt 1 the graph has isolated trees and cycles At 1 cN39I with c 1 a giant connected component appears The size of the giant connected component approaches N rapidly as c increases The graph is connected if lim p 00 Ngt lnNN Random graph with degree distribution Pk A giant connected component exists if ltk2gtltkgt 2 2 Ex How is this related to topological resilience 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 randomly chosen fraction fof the nodes Can the two networks resilience be different 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 ltk2gt gt 2 ltkgt After the random removal of a fraction fof the nodes ltkgtltkogt1 f k2 k gt1 ff k0f1f 1 Breakdown threshold fc 1 k2gt 0 1 Cohen et al Phys Rev Lett 85 4626 2000 1 Application random graphs Consider a random graph with connection probability p such that at least a giant connected component is present in the graph Find the critical fraction of removed 10 ago D nodes such that the giant connected so Egan S component is destroyed N 60 ngggx Minimum 5 40 DDD damage I I 1 DUB fcI 2 1 21 20 Z IEE ltk0gt I llllllllllllII DD ll s k gt 000 39 02 39 04 39 06 39 33 10 0 f The higher the original average degree the larger damage the network can survive Q How do you explain the peak in the average distance Breakdown threshold of scalefree random graphs Scalefree random graph with 1 PkAkquot WithkmK 08 06 S 139 f 1 1 0394 1m 52 Kano 7 2m1 02 7 3 0 xxx 0 02 04 06 08 1 Cohen et al Phys Rev Lett 85 4626 2000 f Infinite scalefree networks with 7 lt 3 do not break down under random node failure Q Do you think there is a ip side of this resilience to random node removal 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 Scalefree networks are more error tolerant but also more vulnerable to attacks Random Scalefree 10 i i 10 r i i i i 0 8 a 0 8 E b 7 squares random failure g u 39 E 50 circles targeted attack 06 r q JED e 06 r o 39u e U 39 2 in i h 04 o jLD e O4 7 L4 q 02 7 0 37 o2 O L L U 0 l ODMQOM 00 02 04 06 08 10 00 02 04 05 08 10 Failures effect on 40 60 the integrity ofthe C d network 39 4O Attacks fast breakdown O l l l O 00 02 04 06 08 10 00 02 04 06 08 10 f N Real scalefree networks show the same dual behavior blue squares random failure red circles targeted attack open symbols 8 filled symbols I El llllllllllligll I 0 0 M gull 00 02 04 06 08 10 00 02 04 06 08 10 f break down if 5 of the nodes are eliminated selectively always the highest degree node resilient to the random failure of 50 ofthe nodes Similar results have been obtained for metabolic networks and food webs 1 Rank order the nodes by your expectation for 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 of the connected component 3 Do the results match your expectations Case study NA powergrid 14000 nodes 1600 generators 10200 transmission substations 2200 distribution substations 19700 edges highvoltage transmission lines Exponential degree distribution longtailed betweenness distribution 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 15 of edges are bridges Q Are there more appropriate measures of network resilience for the power grid Resilience of the NA powergrid The relevant question is whether the 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 N1 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 40 mm degree based connectivity loss 70 20 random 10 f 1 Highest damage if the next substation to be removed is the current highestload substation Resilience o39 the ABA signal transduction network ABA Halli Relevant connectivity the connection of source ABA to sink closure At least four separate ABAclosure paths through Caz through actin l39hmugh pHC and through malate 4 nodes eg depolar actin pHC malate need to be simultaneously disrupted to block all ABA closure paths Q what other connectivity measures could be considered 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 Case study Modeling cascading failures in the North American power grid Three types of substations within the power grid generators transmitters distributors Assume that power is routed through the shortest paths starting from generators and ending with distributors Thus the betweenness load of a transmission substation is assumed to be a proxy for the power flowing through it Assume that each transmitter has a tolerance ability to handle increased load or so the maximum bearable load is CocL0 Node loss will cause the reversible overload of frequently used transmission nodes and the rerouting of power P Crucitti V Latora and M Marchiori Phys Rev E 69 O45104R 2004 Network measures Ef ciency Initial edge efficiency eij1 Degrades at overload of eitheri orj eij eijCiLi returns to 1 if CigtLi Path efficiency 51 harmonic sum of edge efficiencies over the path 1 Network efficiency E NGND Iggjgljgif over the shortest paths from generators to distributing stations V Latora M Marchiori Phys Rev Lett 87 198701 2001 o Damage D EG0EGf rerouting E Go normalized efficiency loss after One node is removed then the node loads are recalculated then the edgepathnetwork efficiencies are updated then the node loads are recalculated until efficiency stabilizes Single Node Random Removals Above a critical tolerance value the removal of a single node has little effect on network however below this critical tolerance value 20 global efficiency loss possible etvlm39l efficiency HG generators l l l l l l l transmissmu nodes i l l l l l l l 1 12 14 16 13 Overload tolerance x 2 1 11 14 16 18 Overload tolerance 11 Upper line no efficiency loss after removing a node in this category Lower curve tolerance dependent efficiency loss Z Maximum damage D0 25 Three separable classes of nodes Nodes whose removal causes little or no damage nearly 60 of nodes Nodes that follow a tolerancedependent curve B Dn1 quot 1 J K nz 1 Nodes that follow the curve then jump to no damage behavior 05 I Ovexload miemuce a R Kinney P Crucitti R Albert V Latora Eur Phys J B 46 101107 2005 Low Damage Node Characteristics 015 l W l l l e 10 O O a m m m 63 l 8 o l o is I mid lllblu 0 05 o W O 7 0 z e a b l l O l l i l O 0 0 52705 0 5 IO 15 20 o 2000 4000 5000 Node load Node degree load bins Correlation between low degree low load and little damage see filled circles 90 of no damage nodes have betweenness below 1000 and degreelt 3 for generators and load below 2000 and degree 2 for transmitters 72 of nodamage generators have degree 1 thus are expected to cause insignificant damage to power routing Resilience of cellular interaction networks Perturbation knockout mutation of a gene This means thbat all products of this gene mRNA protein will be a sent Measured outcome phenotype eg growth behavior of the mutant strain The literature aims to correlate topological measures of the gene product usually a protein in a protein interaction network with the phenotype of the gene mutation Caveats The gene knockout may be incompletely represented by the loss of a protein node in a proteinprotein interaction network The effects of knockouts propagate through the network Systematic deletion of Scerevisiae genes Galactose sensrlwe deletion Strains 5196 gene knockout yeast strains quot F m Studied growth in rich media m and altered environmental ZCTEZM as conditions 39 mum Sn an 47 mm 35 m 4 ram us 9 19 of genes essential without them the yeast does not survive even in rich medium 02 15 of knockouts show slow growth in a rich medium Time in 15 of strains show morphological alteration different cell sizeshape Giaever et al 2002 Nature 418 387 Correlating yeast gene essentiality and protein degree Start with yeast protein interaction network and knowledge of essential genes The network topology displays the error tolerantattack susceptible behavior seen in other networks Group proteins by degree determine the percentage of essential genes that encode these proteins in each group Green random node removal Red removal of highest degree node at each step Highly connected proteins are more essential of essential proteins 5 S l l l l H H l r l O l l v l l v l l v l l l l l O l l O l l l 0 l l l H Jeong et al Nature 411 41 2001 0 5 10 15 20 of links A05 Essential lethal after deletion Toxicity modulating growth inhibition of 0 mutant after exposure to DNA damaging agent 02 No phenotype PU Construct subgraphs ofthese three node quot2 types 0 All have giant connected components with gt60 of nodes 01 Essential Pz subgraph has quotm highest average 0 degree 000m Protein Degree 1 High sensitivity corresponds to higher connectivity degree and shorter characteristic path length Essential subgraph has smallest average path length 2 4 5 a 10 12 Shortesi Path Length I Average Smartest P alh Length king 0 Distribution of each node s average distance from every other reachable node aid et al 2004 PNAS 101 18006 Resilience of metabolic networks Nodes metabolites edges reactions Gene knockouts removal of the reaction catalyzed by enzyme Consider edge removal gene knockout and node metabolite removal Determine the lethality fraction of edge or node removal from nodes of given degree Relatively narrow range of lethality fraction in case of edge removal Very highly connected metabolites are 100 lethal but The lethality fraction of some less connected nodes is higher than the lethality fraction of more connected nodes 1 39 39 39 ac39onsAeiubyem Edge removal ECoiAnaembic 05v I 390 14 003939Pa 939 0 L o 5 o 5 in 10 107 10 53 l T islc r visiiae A robicr I ScerevisraeAnaarobic 305 a m a g o q Fg mqlii v o g 10quot 10 102 10 1 o Gvsullurreducensfumarale G sulfurreducensfe ill 05 0 e o aquot o39 o a a 390 5 no l 6 o 10quot 10 102 101 Conn crvity CK Node remova x 1 0 i i E 0 o E coliAcrobic L o Ecali Anaembic 5 9 5 E u 0 gm 16 1 5 3 5 lt1 0 3910 1039 102 1o1 Connectvlty Cl Mahadevan et al 2005 Biophys Jour 88 L0709

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

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

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