New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Alba Langosh
Alba Langosh
GPA 3.77


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Chemical Engr And Materials Science (Grads)

This 8 page Class Notes was uploaded by Alba Langosh on Saturday September 12, 2015. The Class Notes belongs to EngrMSE 268 at University of California - Irvine taught by Staff in Fall. Since its upload, it has received 62 views. For similar materials see /class/201860/engrmse-268-university-of-california-irvine in Chemical Engr And Materials Science (Grads) at University of California - Irvine.

Similar to EngrMSE 268 at UCI

Popular in Chemical Engr And Materials Science (Grads)




Report this Material


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: 09/12/15
review articles Explor Steven H Strogatz ng complex networks Department of39Iheoretical andApplied Mechanics and CenterforApplied Mathematics 212 Kimball Hall Cornell University Ithaca New York 1485371503 USA eernail strogatzcornell edu The study of networks pervades all of science from neurobiology to statistical physics The most basic issues are structural how does one characterize the wiring diagram of a food web or the Internet or the metabolic network of the bacterium Escherichia calf Are there any unifying principles underlying their topology From the perspective of nonlinear dynamics we would also like to understand how an enormous network of interacting dynamical systems be they neurons power stations or lasers will behave collectively given their individual dynamics and coupling architecture Researchers are only now beginning to unravel the structure and dynamics of complex networks etworks are on our minds nowadays Sometimes we fear their power 7 and with good reason On 10 August 1996 a fault in two power lines in Oregon led through a cascading series of failures to blackouts in 11 US states and two Canadian provinces leaving about 7 million customers without power for up to 16 hoursl The Love Bug worm the worst computer attack to date spread over the Internet on 4 May 2000 and in icted billions of dollars of damage worldwide In our lighter moments we play parlour games about connectivity Six degrees of Marlon Brando broke out as a nationwide fad in Germany as readers of Die Zeittried to connect a falafel vendor in Berlin with his favourite actor through the shortest possible chain of acquaintancesz An during the height of the Lewinsky scandal the New York Times printed a diagram3 of the famous people within six degrees of Monica Meanwhile scientists have been thinking about networks too Empirical studies have shed light on the topology of food webs electrical power grids cellular and metabolic networks the WorldeWide Webm the Internet backbone the neural network of the nematode worm Caeno rhahditis eiegans z telephone call graphs coauthor ship and citation networks of scientistsl H and the quintessential oldeboy network the overlappingboards of directors of the largest companies in the United States17 Fig 1 These databases are now easily accessible courtesy of the Internet Moreover the availability of powerful computers has made it feasible to probe their structure until recently computations involving millionenode networks would have been impossible without specialized facilities Wh is network anatomy so important to characterize Because structure always affects function For instance the topology of social networks affects the spread of informa tion and disease and the topology of the power grid affects 1 J Fr fpuwei I I From this perspective the current interest in networks is part of a broader movement towards research on complex systems In the words of Wilson The greatest challenge today not justin cell biologyand ecologybutin all of science is the accurate and complete description of complex systems Scientists have broken down manykinds of systems They think they know most of the elements and forces The next task is to reassemble them at least in mathematical models that capture the key properties of 77 the entire ensembles 268 2001 Macmillan Magazines Ltd But networks are inherently difficult to understand as the following list of possible complications illustrates 1 Structural complexity the wiring diagram could be an intricate tangle Fig 1 2 Network evolution the wiring diagram could change over time Onthe World7Wide Web pages and links are created and lo st every minute 3 Connection diversity the links between nodes could L quot weights 139 39 J 39 vnzp p in Box l Nonlinear dynamics terminology and concepts Dynamlcal systems can often be modelled by dlflerentlal equatlons dxdt lej where xt pelt Xl ls a vectorot state varlables t ls tlme and levx vnlxjj ls a vector ottunctlons that encode the dynamlcs For example ln a chemlcal reactlon the state varlables representconcentratlons The dlflerentlal equatlons representthe lltlnetlc rate laws whlch usually lnvolve nonllneartunctlons ofthe concentratlons Such nonllnear equatlons are typlcally lmposslble to solve analytlcally butone can galn qualltatlve lnslght by lmaglnlng an abstract nedlmenslonal state space Wlth axesx X As the system evolves xltjtlovvs through state space gulded bythe veloclty tleld dxdtvx llllte a speclltcarrled along ln a steady Vlscous tluld Suppose xlt eventually comes to rest at some pOlnt x Then the veloclty must be zero there so we call x a tlgtlted polnt lt corresponds to an equlllbrlum state of the physlcal system belng modelled ltall small dlsturbances away tromx damp out x ls called a stable tlgtlted pOlnt 7 lt acts as an attractor for states ln lts Vlclnlty Another longeterm posslblllty ls that xlt flows towards a closed loop and eventually clrculates around lt forever Such a loop ls called a llmlt cycle lt represents a seltesustalned osclllatlon of the physlcal system A thlrd posslblllty ls that xlt mlght settle onto a strange attractor a set of states on whlch lt wanders forever neverstopplng or repeatlng Such erratlc aperlodlc motlon ls consldered chaotlc lt two nearby states flow away from each other exponentlally last Longeterm predlctlon ls lmposslble ln a real chaotlc system because of thls exponentlal amplltlcatlon otsmall uncertalntles or measurement errors NATUREl VOL 410 l 8 MARCH 2001 wwwmturecom the nervous system can be strong or weak inhibitory or excitatory I 1 UL 1 tem 39 39 ofeach node canvary in time in complicated ways L Th biochemical network that controls cell division in mammals 5 ml 1 1c etaacomplication the various complications can in uence each other For example the present layout of a power grid depends on how it has grown over the years 7 a case where network evolution 2 affects topology 1 When coupled L a fewofwhich are shown inF39g M strengthened this is the basis of memory and learning Here nodaldynamics4 affectconnectionweights 3 To make progress different fields have suppressed certain complications while highlighting others For instance in nonlinear mics we have tended to favour simple nearly identical NATURE VDLAIO BMARCH 2001 www nature com 2001 Macmillan Magazines Ltd rev39 wart39 les ays is static These simplifications allow us to sidestep any issues of structural complexit and to concentrate instead on the system s potentially formidable dynamics T 39 1 I I I a approximation each laser is characterized by its timeadependent gain polarization and the phase and amplitude ofits electric field These evolve according to four coupled nonlinear differential equations We usually hope the laser will settle down to a stable state corresponding to steady emission of light but periodic pulsations and even chaotic intensity uctuations can occur in some cases regular chain or ring interactingwith their neighboursby evanesa cent coupling or by overlap of their electric fields Will the lasers apattrn L Lrlquot l39 ical standpoint selfasynchronization would be the most desirable outcome because a perfectly coherent array of Nlasers would Figurel Wiring diagrams for complex networks a Food web of Little Rock Lake re functionally distinct tropnicspecies cortaining all taxatnat snare tne same set of r dators Heignt indicates tropnic level Witn in ostly pnytoplankton attne ttnetop Cannibalism is snown Witn selfrloops and ornnivoiy ng on more tnan one tropnic level is snown by different coloured links to n Martina i h gilu are transmission lines andtransforrners Linetnickness and colourindicatetne voltage level red 765 kV and 500 kV brown 345 kV green 230 kV grey 138 kV and below Pink dasned lines are transforrners Figure provided byJ Tnorp and H Wang cA portion oftne rnolecularinteraction map for tne regulatory network tnat cortrols tne rnarnrn alian cell cycle6 Colours indicate different types of interactions black binding interactions and stoicniornetric conversions red covalent modifications and gene expression green erzyrne actions blue stirnulatlons and innibitions Reproducedfrorn Fig 6a in ref 6 Witn perrnission Figure provided by K Konn c review articles lh ahetvvorkotlrrrrr39 drstrrbuted haturaltreouehores The state oteaoh osorllator rs represented H a m r n r a a t osorllatrOh corresp0hdto the radius ahd ahgle of the dot lh polar ooordrhates Colours o e the osorllators hatural frequehores ruhhrhg trorh slowest red to fastest vrole l I eaoho orllator hmquot rotate at rts hatural trequehoy However here all the osorllators are also pulled towards the rheah held that they geherate oolleotrvely showh as ah asterrsk atthe oehtre otthe populatrOh Trrhe rhoreasestrorh lettto rrght ahdtrorh top to bottom Startth from a h r5 H o my rrrgtherrarhplrtudes theh they sort therr phases so that the tastestosorllators are h the lead Ultrrhately rh Wrth h The goverhrhg eouatrOhs desorrbe a rheahrheld model of a laser array23 provrded by R Olrva SrrhulatrOh roduce NZ times as much power as a single one But in practice semiconductor laser arrays are notoriously prone to both spatial and temporal instabilitieszo Even r a simple ring geometry this problem is dynamically complex The first part of this article reviews what is known ab out dynamie cal complexity in regular networks of nonlinear systems I offer a few rules of thumb about the impact of network structure on collective dynamics especially for arrays of coupled limitecycle oscillators 39 next step would be to tackle networks that combine dynamical and structural complexity such as power grids or 1 system its longeterm behaviour is given by stable xed points limit cycles or chaotic attractors Box 1 f we now couple many such systems together what can be said about their collective behaviour The answer is not much i the details matter Duu 39quot I quot 39 If L J I each U I 1 point and no other attractors the networktends to lock into a static pattern Many such patterns may coexist especially if the nodes have competing interactions In that case the network may become frustrated and display enormous numbers of locally stable equilibria This kind of I 39 39 isseenin I39 memory neural networks and combinatorial optimization problems At the opposite extreme suppose each node has a chaotic attractor Few rules have emerged about the effect of coupling architecture on dynamics in this case It is known that networks of r 2 2 nriqtixe curiou I withI 39L IIquot 39 to pi39 nications34 35 For a wide range of network topologies synchronized chaos requires that the coupling be neither too weak nor too strong otherwise spatial instabilities are triggered Relatedlines of research deal with networks of identical chaotic maps lattice dynamical d automataTb m L used mainly as testbeds for exploring spatiotemporal chaos and pattern formation in the simplest mathematical settings rather than as models of real physical systems identical oscillalors The intermediate case where each node has a stable limit cycle has turned out to be particularly fruitful Much of the research has been inspired by biological examples ranging from the mutual 39 39 139 I cllto 39 quot 39lahing fire ies and chorusing crickets to wave propagation in the heart brain intestine and nervous system25 rrays of identical oscillators often synchronize or else form pat terns that depend on the symmetry of the underlying network Other common modes of organization are travelling waves in one spatial dimension rotating spirals in two dimensions and scroll waves in three dimensionszs For fully connected networ ere each node is coupled equally to all the others the completely synchronized state becomes like These heuristics apply to systems coupled by smooth interactions akin to diffusion But many biological oscillators communicate by sudden impulses a neuron fires a fire y ashes a cricket chirps Hence the recent interest in pulseecoupled oscillators began with Peskin s model of the sinoatrial node the heart s natural pacemaker as a collection of N identical integrateeande re oscillae tors For the simple case where each oscillator is connected to all the 1 A n g 5 F E 3 a ecological webs Unfortunately they lie beyond our reach 7 we do not even know how to characterize their wiring diagrams So we have to begin with networktopolo gy B a happy coincidence such architectural questions are being pursued in other branches of science tha he excitement about the Internet functional genomics financial networks and so on The second part of this article uses graph theory to explore the structure of complex networks an approach that has recently led to some encouraging progress especially when combined with the tools of statistical mechanics and computer simulations eed ess to say many other topics within network science deserve coverage here The subject is amazingly rich and apologies are offered LU 110 t Jcadu I I I 1 tegwlar lieimrol lta at Mutated dynamical systems Networks of dynamical systems have been used to model everything from earthquakes to ecosystems neurons to neutrinos To impose some order on this list consider the dynamics that each node would exhibit if it were isolated Assuming it is a generic dynamical 270 2001 Macmillan Magazines Ltd others n Lllat they up lit in in uni U11 JJUJudllCJ J I N quot quot 39 was later demonstrated that the conjecture holds for all N Peskin also conjectured that synchronization would occur even if the oscillators enot I 39 391 39 n thatproblrm 39 I Peskin s model has been used as a caricature of coupled neue rons W Z by including synaptic delays refractory periods inhibition and local coupling these realistic features also remove some of the undesirable discontinuities in the mathematics In an example of scienti c crossefertilization Hopfield 3 pointed out that the locally coupled version ofthe mo el is closely related to slidereblock models of earthquakes and should therefore display selfeorganized criticalie tyThat L 39 Jim 39 quot Lquot geophysics synchronization and selfeorganized criticality and sparked a burst of research activity as reviewed in re Nun illertlicaloseillalnis While modelling populations of biological oscillators Winfree discovered a new kind of cooperative phenomenon the temporal NATURE lVOL 410 I 3 MARCH 2001 lwwwmturecom analogue ofaphase transition He proposed a meani eld model of nearly identical weakly coupled limiticycle oscillators and showed that when the coupling is small compared to the spread of natural frequencies the system behaves incoherently with each oscillator running at its natural frequency As the coupling is increased the 4 viquot Nag 39 3 o O o 39 W43 K3 1 WI 300 P w are I ll Figure3 Scnematic illustration of regular and random network arcnitectures a Ring Bdle lllelgllUUUl by l nodes c Random grapn constructed by placing nnodes on a plane tnen lOllllllg pairs of tnemtogetner at randomuntil m links are used Nodes may be chosen moret an once or not at all Tne resulting Wiring diagram not snown would be a snarl of crissr crossed lines to clarify it l nave segregated tne different connected components coloured tne m and eliminated as many spurious crossings as possible The main topologlcal features are tne presence of a single giant component as expecteda J tor a random graph Witn mgt n2 nere n 200 m l 93 and the absence of an dominant nubs Tne degree or number of neignbours is POisson distributed across t enodes iieigiiuoui zero and six d Scalertree grapn grown by attacning new nodes at random to preViously egtltisting nodes The probability of attacn ment is proportional to the degree of the target node tnus ricnly connected nodes tend to get rlcner leading to the formation of nubs and a skewed degree distribution Witn a neavy tail Colours indicate tne tnree nodes Witn tne most links red k 33 links blue k12 green kl 1 Here n 200 nodes ml 99 links Figure provlded by D Callaway Network u iiigiii iai nor nttp vlado tmt unirlisipubnetworkspaiekpaiekman ntm giaiiiii NATURE l VOL 410 l 3 MARCH 2001 l wwwmturecom 2001 Macmillan Magazines Ltd review articles incoherence persists until a certain threshold is crossed i then a small cluster of oscillators suddenly freezes into synchrony For still greater coupling all the oscillators become locked in phase and amplitude Fig 2 Kuramoto26 re ned this connection between nonlinear dynamics and statistical physics He proposed an exactly solvable model of collective synchronization givenby d0 KN 7 s1n070 11N dt w N J gt Where 0 is the phase of the 1th oscillator and w is its natural frequency rhn en at randnme i J 1 uuuuny u u it 7 7 3 wrw we mm of width y and mean we Using an ingenious selficonsistency argument Kuramoto solved for the order parameter 1 N rt 7 e197 N a convenient measure of the extent of synchronization in the limit N w and ta w He found that 0 Klt KC 7 v17 KCK K K where Kc2y In other words the oscillators are desynchronized completely until the coupling strength K exceeds a critical value Kc After that the population splits into a partially synchronized state Figure 4 Solvable model of a smallrworld network Tne model starts Witn a ring lattice otnno es d tosomerange b r quoti Mnd k 3 snortcut links are added between random palrs of nodes Witn probability a per linkon tne underlying lattice ln tne limit n l tne average patn lengtn between nodes can be approgtltimated analytically Adaptedtromret 75 review articles 0 ittii tiiiii iii iii iiii iiii it iiii iiti 001 01 1 10 100 rika ll ll 0001 1000 10 00 Figure 5 Average path length normalized by system size is plotted as a function of the average number of shortcuts The Circles are results from simulations of the model With rahge Kt and size up to nt07 nodes The solid line is given bythetormttia in the text Adaptedtromret 75 consisting of two groups of oscillators a synchronized group that contributes to the order parameter r and a desynchronized group whose natural frequencies lie in the tails of the distribution gw and are too extreme to be entrained With lrther increases in K more an quot mite J 39 39 1 group and r grows accordingly Twentye ve years later the Kuramoto model continues to sure prise us see ref 45 for a review First the incoherent state with r 0 was found to be neutrally stable below threshold despite its apparent stability in simulations the analysis reveals a connection to Landau damping in plasmas Second the squareeroot critical behaviour of r almost a cliche for meane eld models in statistical mechanics turns out to be nonegeneric if the sinusoidal coupling is replaced by a periodic function with second harmonics the scaling changes to 7 K 7 KC Third although the model was motivated originally by biologicaln cillatnr it U in 11ch far quot 39 391 th avour evolution of neutrinos and arrays of Josephson junctions27 and semiconductor lasers The main unsolved problem is the stability of the partially synchronized state for K gt K Numerical simulations indicate that it is globally stable in the sense that it attracts almost all solutions but even the linear stability problem has yet to be solved Another issue concerns the extension of the model to nearesteneighbour coupling on a dedimensional cubic lattice Simulations 6 and renormalization arguments 7 indicate that the synchronization phase transition persists for d 3 and vanishes for d 1 the results are ambiguous for d 2 All of this awaits a mathematical resolution In contrast to the meanefield models ofWinfree and Kuramoto J 1 Ermentrout and Kopell s classic work deals w1 everyone s delight that prediction was later confirmed by their experimental collaborators Gamble etwoz lz iai itiieetures All the network topologies discussed so far i chains grids lattices and i J 1 L h l I re ular trig 3a b Those simple architectures allowed us to focus on the complexity caused by the nonlinear dynamics of the nodes without being burdened by any additional complexity in the network structure itself Now I take the complementary approach setting dynamics aside and turning to more complex architectures A natural place to start is at the opposite end of the spectrum from regular networks with graphs that are completely random Random gr arms agine 71 gt1 buttons strewn across the oor Pick two buttons at random and tie them together with thread Repeat this process m times always choosing pairs of buttons at random If m is large you might eventually select buttons that already have threads attached That is certainly allowed it merely creates clusters of connected buttons The result is a physical example of a random graph with n nodes and m links Fig 3c Now slowlylift a random button offthe oor If it is tied to other buttons either directly or indirectly those are dragged up too So what happens Are you likely to pull up an isolated button a small cluster or a vast meshworkZ Erdos and Renyi52 studied how the expected topology of this random graph changes as a function of m When m is small the graph is likely to be fragmented into many small clusters of nodes called I t L I at first bylinking to isolated nodes and later by coalescing with other components A hase transition occurs at m 712 where many clusters crosslink spontaneously to form a single giant component For m gt 712 t 39s giant component contains on the order of nnodes more precisely its s A minrrpq 9 size scales linearly with n as at thle its closest rival conta1n only about log n nodes Furthermore all nodes in the giant component are connected to each other by short paths the maximum number of degrees of separation between anytwo nodes grows slowly likelo n In the decades since this pioneering work random graphs have been studied deeply within pure mathematics53 The have also served as idealized coupling architectures for dynamical models of gene networks ecosystems and the spread of infectious diseases and computerviruses29 51 54 55 Sim iii networks Althou hre trim J 1 1L L itirale izations many real networks lie somewhere between the extremes of order and randomness Watts and Strogatzss 57 studied a simple model that canbe tuned through this middle ground a regular lattice Table 1 Clustering for three af liation networks Network Clustering C chains of oscillators first in connection with rhythms in the mammalian intestine and later in their model of the central pattern generator for the lamprey eel w so The main phenomena here involve travelling waves rather than the synchrony found in meane eld models This is not accidental as wave propagation is essential for the generation of peristalsis in Com party directors Movie actors Biomedical authors 7 the Forum 0 M e 1 appearances ii i 151251 feature trims as specified by the iriterriet Movie Database t Ma inn t the intestine and for the creation of the swimming rhythm 95 inlam re 39 and1000iri hi i lNFdzlzhz Ermentrout and Kopell introduced several de n hi to 7b innovations but perhaps their most impressive result is a counterine h h T Visits quot L39 39 predictinn Tiieiiiampie t atthe i tailetoehead neural connections along the spinal cord would be invoked For no what int stronger 39 turtttheadmrm l J I39 thatthe wave associated with swimming travels from head to tail To 272 2001 Macmillan Magazines Ltd communities see text Adapted from ter 91 NATURE iVOL 410 i 3 MARCH 2001 iwwwmturecom FigureG Degree distributionsfor reaT networks a WoerrWide Web M u t i i u uiim page to another The Togilog pTot shows the number of web pages that have a given inrdegree number of incoming links The raw data have been logarithmically binned With bin ratio 2 The tail of the distribution follows an approximate power law with exponent yz 2 2 i0 b c scientists an undirected TTTTK between two people means thatthey have ertten a paper together The data are for the years T 9954 999 i u t 1 l t mm Frequency in SPW p p h h p NCSTRL preprTnts Tn computer science Symbols denote different scientific communities astrophysics CTTCTBS condensedrmatter physics squares highrenergy physics upright triangles and computer heT g p the totaTofz with r truncated power law solid line of the formpZ z iexp7 NJ where 20 isthe cutoff The curves have been displaced verticaTTyfor clarity Adapted from ref T4 c Power grid of thewestern United into and f anarla M npripmmr 4 substations undirected links represent highevoTtage transmission lines between them The data are plotted as a cumulative distribution to reduce the effects of noise on this smaller data set The TinearrTog pTot shows that the proportion of nodes With at least Ktransmission Tines decays exponentially in K The negative derivative of this i attrituu utu4 Cumulative probability Adaptedfromref 62 1 Social network Nodes are 43 TVTormons in Utah undirected links represent acquaintances With other TTormons7g The Tinearilog plot of the cumulative distribution TsweTT fit by an error function solid line so the degree distribution is a gaussian Adapted from ref 62 where the original links are replaced by random ones with some probability OS 45 1 They found that the slightest bit of rewiring transforms the network into a small world with short pathsbetween anytwo nodes just as in the giant component of a random graph Yet the network is much more highly clustered than a random graph in the sense that if A is linked to B and B is linked to C there is a greatly increased probability that A will also be linked to C a property that sociologists58 call transitivity Watts and Strogatz conjectured that the same two properties 7 short paths and high clustering i would hold also for many natural and technological networks Furthermore they conjectured that dynamical systems coupled in this way would display enhanced signal propagation speed synchronizability and computational power as compared with regular lattices of the same size The intuition is that the short paths could provide highespeed communication channels between distantparts of the system thereby quot39 39 39 quot 39 39 in ma tion that requires global coordination and information ow Research has proceeded along several fronts Many empirical examples of smalleworld networks have been documented in elds ranging from cell biology to business9 14 5939 Onthe theoretical side smalleworld networks are turnin out to be a Rorschach test 7 different scientists see different problems here depending on their disciplines omputer scientists see questions about algorithms and their complexity Walsh65 showed that graphs associated with many dif cult search problems have a smalleworld topology Kleinberg66 introduced an elegant model of the algorithmic challenge posed by Milgram s original sociological experiment67 ihow to actually find a short chain of acquaintances linking yourself to a random target person using only local information i and he proved that the problem is easily solvable for some kinds of small worlds and essentially intractable for others Epidemiologists have asked how local clustering and global NATURE T VOL 410 T 3 MARCH 2001 T wwwmturecom 2001 Macmillan Magazines Ltd review articles 3 Transmission lines Acquaintances contacts together in uence the spread of infectious disease with implications for vaccination strategies and the evolution of virulenceswl Neurobiologists have wondered about the possible evolutionary signi cance of smalleworld neural architecture They have argued that this kind of topology combines fast signal processing with coherent oscillations unlike either regular or random architectures and that it may be selected by adaptation to rich sensory environments and motor demands Perhaps the strongest response to the Rorschach test comes from the statisticalphysicists who sensed immediately73 that the toymodel of Watts and Strogatzsswould yield to their techniques see ref 74 for a review In its improved form the model starts with a ring of n nodes each connected by undirected links to its nearest and next nearest neighbours out to some range k Shortcut links are then added 7 rather than rewired ibetween randomly selected pairs of nodes with probability 45 per link on the underlying lattice thus there are typically 71qu shortcuts in the graph Fig 4 The question is on average how many steps are required to go from one node to another alo ng the shortest route If 4 denotes that average separation nd that 4 drops sharply near 45 0 confirming that a few shortcuts do indeed shrinkthe world dramatically One of the most striking results is the following formula derived by Newman Moore and Watts75 n f E quotC15 where fx tanhc 7L 2 V 93 2x V a 2x This solution is asymptotically exact in the limits new large system size and either nk gt 00 or nk gt0 large or small number of 273 review articles b Figure7uroartrt V 1 h V d hetttork mt t ta it u u u mdso hodes The scherhatrc exa pte shows 11 drrectors ahd 4 boards Lrhks rhdrcate whrch people srt 0h whrch boards By detrhrtrOh there are ho trth bettteeh bars of people or b V h1The rhorerarrrrrrar V people as hodes1vvlth Hhks bettteeh those Oh the same board torrhrhg choues Thrs W h d d structures For example the trrahgte FHI correspOhds to board hurhber 31 as seeh rh a1vvhereasthe srrhrtarrtookrhg trrahgte FGI does hot corresp0hd to ahy srhgte board Ahother cOhtusrhg effect rsthe large hurhber ot choues that occur autorhatrcaHy rh thrs prorectrOh ot the full brpartrte graph Such choues accouht for much of the hrgh ctusterrhg observed rh real artrhatrOh hetvrorks58 The rahdorh graph rhodetteases out trorrr that rrturcatr e of rhteractrOhs Adapted from ref 91 A rmr rmnr shortcuts Figure 5 shows that it also gives the correct qualitative behaviour for 71qu z 1 Barb our and Reinert76 improved this result by proving a rigorous distributional approximation for 4 along with a bound on the error matetree networks In any real network some nodes are more highly connected than others are To quantifythis effectlet pk denotethe fraction of nodes that hmelrlink I Ierelri called L l 17 39 L l 139 39 The simplest random graph models 53 predict a belleshaped Poisson distribution for pk But for many real networks pk is highly skewed and decays much more slowly than a Poisson For instance the distribution decays as a power law pk k y for the Internet backbone1 1 metabolic reaction networksg the telephone call graph13 and the WorldeWide Web10 Fig 6a Remarkably the exponent y 2 2144 for all ofthese cases Takenliterally this form ofheavyetailed distribution would imply an in nite variance In reality there are a few nodes with many links Fig 3d For the World eWide Web think Yahoo for metabolic networks think ATP Barabasi Albert and Ieong77 7B have dubbed these networks scaleefree by analogy with fractals phase transitions and other situations where power laws arise and no single characteristic scale can be defined The scaleefree property is common but not universal For co authorship networks of scientists pk is fit betterby apowerlawwith an exponential cutoff Fig 6b for the power grid of the western United States pk is an exponential distribution62 Fig 6C and for a social network ofMormons in Utal179pk is gaussian62 Fig 6d L Juuuuu 274 2001 Macmillan Magazines Ltd Nevertheless the scaleefree case has stimulated a great deal of theorizing The earliest work is due to Simonm Bl in 1955 now independently rediscovered by Barabasi Albert and Ieong77 78 They showedthatab quotnquot t quot d1 139 39L 39 39 ly from a stochastic growth model in which new nodes are added 39 and attach them elve 1 39 to existing nodes withprobabilityproportional to the degree of the target node Richly connected nodes get richer and the result is pk k4 More sophisticated models M include the effects of adding or rewiring links allowing nodes to age so that they can no longer accept new links or varying the form of preferential attachment These general ized models predict exponential and truncated powerelawpk in some parameter regimes as well as scaleefree distributions Could there be a functional advantage to scaleefree architecture Albert Ieong and Barabasi85 suggested that scaleefree networks are resistant to random failures because a few hubs dominate their topology Fig 3d Anynode that fails probablyhas small degree like most nodes and so is expendable The ip side is that such networks are vulnerable to deliberate attacks onthe hubs These intuitive ideas have been confirmed numericallyl 0 85 and analytically B7 by examining how the average path length and size of the giant componen A I A I L 1 q 4 1 J 1 Some possible implications for the resilience of the Internet the design of therapeutic drugsg and the evolution of metabolic networks have been discussed Geruet aiized random gr arms 39 d above the simplest random graph predicts a Poisson degree distribution and so cannot accommodate the other types of distribution found in real networks Molloy and Reedm introduced a more exible class of random graphs in which any degree distribue tion is permitted Given a sequence of nonnegative integers dk where dk denotes the number of nodes with degree k consider the ensemble of all graphs with that prescribed degree sequence and weight them all equally when computing statistical averages of interest For this class of graphs Molloy and Reed derived a simple condition for the birth of the giant compo nent and they also found an implicit formula for its size as a fraction of n the total number of nodes Specifically let n gt 1 and define Q2pkkltk72gt k1 where pk dkn If Q lt 0 the graph consists ofmany small compo nents The average component size diverges as Qgt0 frombelow and a giant component exists for Q gt 0 In technical terms these results hold almost surely that iswith probabilitytendingto 1 as ngt 00 Aiello Chung and Lu0 applied these results to a random graph model for scaleefree networks For pk of powerelaw form the condition on Q implies that a giant component exists if and only if y lt 347 whichholds for most scaleefree networks measured so far If y lt 1 there are so many highedegree hubs that the network forms one huge connected piece They also proved theorems about the number and size of small components outside the giant component and compared these to a real graph of about 47 million telephone numbers and the calls between them in one day They found that the data are best fit by an exponent y z 21 which predicts correctly that the call graph is not connected but has a giant component The papers by Molloy and Reedm and Aiello et all0 are mathematically rigorous Newman Strogatz and Watts1 recently developed a 39 39 1 1 based 39 Function quot Jquot 39 lllcil 1 1 elementary derivations of the earlier results along with new exact results for graphs with additional structure such as directed or bipartite graphs NATURE lVOL 41013 MARCH 2001 lwwwmturecom The bipartite case is especially interesting for applicationssg By de nitinn in a L 391 39 A r nodes With inks running onlybetween different kinds Fig 7 For example consider the network of theboards of directors of the Fortune 1000 com a nies the largest US corporations ranked according to revenues This network is fascinating because the boards interlock 7 some impore tant people sit on several of themi and this overlap knits virtually all large US firms together into a giant web of corporate governance etpl I L Lquot39 tlra adirec r 39t 39 oar and let qk denote the probability that a board consists of k directors Figure 8 shows that p is approximately exponential with most directors sitting on only one board whereas qk is strongly peaked around k 10 indicatingthat most boards have about ten members As a null hypothesis assume that the Fortune 1000 network is a random member ofthe ensemble ofall bipartite graphs withthe same p and Then generating functions yield predictions for various quantities of interest1 For example suppose we want to calculate rz the probability that a random director works with a total of zother coedirectors summed over all the boards onwhich he or she serves Let fox Zw 10 goxZ quk k0 be the generating mctions associated with the empirical degree distributions pjand qk Ifwe now choose a random edge onthe bipare tite graph and follow it to theboard at one of its ends the distribution of the number of other edges leaving that board can be shown to be generated by g1x g039xv where v g0391 Then for a randomly cho e 39recto r the generating function for z is given Gox fog1x Ifwe expand G0 in a series as 6000 rzxz 20 the coefficients rz are exactly the quantities we seek They can be extracted by repeated differentiation rz 1 zideodxzlx 0 Figure 8c shows that the predicted rz agrees almost perfectl predicted for the directors lies within 1 0 Table 1 Clearly the random model captures much of the structure ofthe real network However for two other bipartite graphs 7 film actors and the movies they appeared in and biomedical scientists and the papers they coauthored i the model1 underestimates the clustering coef cients by half Table 1 The reason is that the random model quanti es only the generic portion of the clustering it re ects the cliquesthat J 39 quot er L 39I 39 L tion graph is projected onto the space ofpeople as in Fig 7b For the corporate board data those cliques account for essentially all the clustering simplybecause most directors sit r I L J thii I 1 I L J Jul 1 I I be at work WJJEJJE 1 39LI 1 r r n L L I r J 1 is that 39 o 39 I filieii other engendering new collaborations nt iswa the ran om J ic features of bipartite graphs from those that could re ect sociological effects Beyon their L 39 quot J J 1 provide a promising new class of substrates on which dynamical processes can be simulated and even approached analytically Using 39 Wattsgzhasgiven min I 39 39 L 39 r NATURE l VOL 410 l 3 MARCH 2001lwwwmturecom 2001 Macmillan Magazines Ltd review articles i39 l tlilllllitlt GO or Probability p 3 Probab ty qK 3 1039a Number of members K Probability rZ 9 20 Number of coedirectors 2 Figure 8 Structural properties of the Fortuhe l 000 hetwork of corporate directors for 1999 The data shOWh here comprise 7 673 directors ahd 914 boards lVlost directors serve Oh the board of Ohly Ohe corhpahy but about 20 sit 0h two or more oards thereby creatihg ihterlocked directorates This has potehtially irhportaht cOhseouehcestor buslhess practices lh the Uhited States 7 a DistributiOh of the hurhber of boards per director The probabilityp hat a director sits 0h exactlyboards decreases roughly expOhehtially With b DistributiOh ofthe hurhber of directors per board The probability akthat a board has Krhe rhbers is approgtltirhately loghorrhally distributed With a typical board size arouhd K10 members c DistributiOh of each director stotal hurhber of CO dlleCIOlS summed over all the boards 0h Which the director sits The probability rzot serVihg With zother cordirectors is a complicated tuhctiOh otz With a thg tail ahd a secOhdary shoulder hear 2 20 yetthe theoretical circles Adaptedtrorhret 91 normal 1 I I j c A q sparse interaction networks iiilmk In the short run there are plenty of goodproblems about the nonline ar 1 39 f 1 J 139 t r dscaleefree or generalized random connectivity The speculations that these architectures are dynamically advantageous for example more syn hronizable or erroretolerant needto be sharpened then confirmed or refuted mathematically for specific examples Other ripe topics include the design of selfehealing networks and the relationships among optimization principles network growth rules and networ topologyEH 5 In the longer run network thinking will become essential to all branches of science as we struggle to interpret the data pouring in from L 39 genomic ecology finance and the Worldwide Web Will theory be able to keep up Time to log back on to the Internet I n 1 that Occurred on the Western interconnection on Augut10th1996 at 1548 PAST AnonymouMediaSixdegreefromHollywoodJVeiAxweek110ctober 199951999 1th l39i hv Wu W T hriizrvl vi d vi 1 iiiim RT Mvrm ND 2 3 4 hnTFRvindFNmn M Tm 5 M Am i 04332000 5 Kohn K Mal Eiaz 5211102703727340999


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

Bentley McCaw University of Florida

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

Amaris Trozzo George Washington University

"I made $350 in just two days after posting my first study guide."

Jim McGreen Ohio University

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

Become an Elite Notetaker and start selling your notes online!

Refund 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


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:

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

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.