### Create a StudySoup account

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

Already have a StudySoup account? Login here

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

### View Full Document

## 19

## 0

## Popular in Course

## Popular in Department

This 7 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 19 views.

## Similar to Course at Penn State

## Popular in Subject

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

pe successmt th descrtpthg he prctperttes drah expected charactertsttc hetwurx Uhtturrhtyrahddrh netWEIrK dtsthpdtes the edges dhtrdrrhty arhcthg hddes Prdpaptttsttc trterpreta tcth There elttsts a set ehserhpte ctr hethtrxswtth gtveh humperdr hddes and edges setecta rahdctrh rherhper crthts set What are the expected prppemes ctr hts hethtrxrestddted by rahdctrh graphthectry Ex 1 Stan wtth 1n tsutsted nudes Fur ach pan drnddes Lhmw wtth a dtee and eumeetthemtrthe numba39 unthe dteets 1 Desmhethe gapth uhtamed Huwmany edges are m the gephr Is tt eumeeted Dr nuW What tsthe average degeeand the degee dtstnhutmnr Ex 2 Newedmeetnddepatmrthe nunhemnthedteets t m2 Hdwts the geph diffa39enlfmmthepremuusmse7 Ex 2 Huwmany edges dd yuu expect a geph wtthN nudes Vmuld have xfanh edge is selected wtth thmwtng wtth a dice 7 Random graph theory ErdOSrRe39nyt atgohthrh e Pupt Ma h rebreten 290 ttaaar hxed hdde humperrv 39 39 39 ccthhecnhg patrs ctr hddes 39 k wtth prupapttttyp no u 1 Expected humperetedges 5 FW Randum graph thectrystddtesthe expected prctperttes cttgraphs wtth N Mu The properties of random graphs depend on p Properties studied is he graph connected does the graph contain a giant connected component what is the diameter ofthe graph does the graph contain cliques complete subgraphs Probabilistic formulation what is the probability hat a graph wi h N nodes and connec ion probability p is connected Increase p from 0 to 1 Some ofthese properties appear suddenly at a threshold pcN 01f p w m PJN lzm PINQ N aw pJN Subgraphs of a random graph Consider a subgraph wi h n nodes and e edges Expected number of of these subgraphs in a graph with N nodes and connec ion prob p We can permute n e quotI he n nodes in any EX CNP 7 way we want Ways of selec ing Probability of Wt identic n nodes from N having e edges 39Somorphlc graphs do not count lsomorphic graphs there exists a onetoone mapping of the nodes in such a way that if and only if node i andj are connected in one then their images i and j are also Connected Special subgraphs Consider a subgraph with n nodes and e edges Expected number of subgraphs with n nodes and e edges in a graph with N nodes and connection prob p n e n N quot p E X C Np E a a lfthe connection probability is a function ofthe number of the nodes we can find the condition of having a nonvanishing number of subgraphs lim pNNquot a 0 N uu Ex Find the condition of having a nonvanishing number of trees cycles and completely connected subgraphs Evolution of a random graph Assume that the connection probability is a powerlaw of N 11 UN Assume that 2 increases from 00 to 0 Look for trees cycles circuits and cliques in the graph AAle Appearance thresholds pNNZ g 5 g 1 2 Kalb Hh gm The graph contains cycles of any length if z 2 1 zrm Clusters in a random graph For p lt Nquot the graph contains only isolated trees quotI with c lt 1 the graph has isolated trees and cycles If p c At p cNquot with c 1 a giant connected component appears The size ofthe giant connected component approaches N rapidly as c increases Sf1fcN The graph becomes connected if 11 CD 159 lnNN Pk Node degrees in random graphs average degree k5 pN degree distribu ion WM 5 CLIPquot FINN 139 ltkgt vvkays to select k probability of nodes from N1 probability of missing N1k having k edges edges Most of he nodes have approximately the same degree The probability of very highly connected nodes is exponentially small Distances in random graphs Random graphs tend to have a treelike topology with almost constant node degrees hr of first neighbors N Eltkgt hr of second neighbors N E ltk2 estimate maximum distance I m lag N I k N l gt a m lagltkgt This scaling was proven by Chung and Lu Adv Appl Math 26 257 2001 There is no local order in random graphs Measure of local order Ci EL kk 12 Since edges are independent and have the same probability p k k 1 ni p QCEP Ill The clustering coefficient of random graphs is small Are real networks like random graphs As quantitative data about real networks becomes available we can compare their topology with that of random graphs Starting measures N ltkgt for the real network Determine I C and Pk for a random graph with he same N and ltkgt log N lmwlogltkgt Cm p N Pmk E CI LIP YI p quotquot Measure I C and Pk forthe real network Compare Path length and order in real networks The degree distribution of the VWWV is a powerlaw 1o 7 O 7 7 7 A A PHMUCH k 245 573 1076 7 7 5E 7 11 1 B n 10 7 O 7 7 7 10quot 7 7 7 7 10712 72 U 2 4 5 72 U 2 4 O 5 1O 1O 1O 1O 1O 1O 1O 1O 1O 10 k k R Albert ll Jeong AL Barabasi Nature 401 1301999 A Broder eta Comput Netw 33 309 1999 logN ltkgt m Cm logltkgt N ii i i i i 10 lz sialiizm 0 A in 7mulicnemmks 7 A A mema A Vruuu webs 8 f irrlimm 0 migraan 5 Eullabugratdlun networks n 5 www it 10 0 Din lE Iz iti N lE I if in loxmn 32 13 an 103 Real networks have short distances like random graphs yet show signs of local order Powerlaw degree distributions were found in diverse networks Internet router level Actor collabora ion D 10 O i 71 1 39 Go a 39 quotu b 39 10 2 7 000 7 7 N 7 Home 7 7 7 EEE 7 O 23 PkSk 23941074 7 00 7 E 7 Pkk 1075 930 u913m 7 1076quot l I l l l 10 101 102 103 101 102 103 k R Govindan H Tangmunarunkit EEE Infocom 2000 AL Barabasi R Albert Science 286 509 1999 The powerlaw degree distribution indicates a heterogeneous topology The aerage eegree gives the characteristic scaie vaiue er he eegree Large variaeiiity he average eegree het i f rmativE he characteristic scaie rer he eegree Scaierree Idea generate random graphs with a powerlaw degree distribution Fixed NV PkAk39 kltK NEIWEIM assembiyr raheerh edges but ehrercihgthe right Pk gym1 A I v ltkgt2kPk 00721quot Zquot The herheer er eeges increases as r eecreases Constructing graphs with a given degree distribution Cun gura un rheeei cheese a eegree segeehce Wyn Pm give the heees K stubs accereihg te W cehhect stubs randumiy M E J Newman s H Strudatz andD J Watts F th Rex E BO UZBMBQUUW Ex Cehstmct a graph Wi h in heees ahe eegree segeehce Ni4 N23 N3 h4i What is a hecessaryceheinehrer he graph cehstmctiem Theory of general random graphs Luuks ata characterisnc rherheererthe ehserheie er graphs With given eegree eistrieeneh Seeks the answers te the same geestiehs as raheerh graph theery isthe graph EunnEEtEd7 eeesthe graph cehtaih a giant lmp nent Whatis he eiarheter erthe graph7 Whatis he ciesterihg ceerriciehterthe graph7 Thetheereticai cehcept heeeeererthe anaiysis isthe geheratihg rehctieh one irhpertahtreseit A giahtcehhecee cerhpeherit Busts irthe graph is Summermy heteregeheees gym 2 Connectivity of scalefree random graphs Given 1v Pk u r rdr ks crapn prppemes depend unthe degree expdnem r giantciuster rs 47 cunnected 752 vv Areun r cndngt LU F39mc 320mm THEEH cdrnwm mun M E J Newman 5 H Stingatz D J Watts ths Rev E N nzm unm Average path length of scalefree random graphs Nabmm 1v Newquot rdr ks Wm M E J Newman s H Simgatz D J Watts ths Rev E m uzm impair Predictiun I quaiitative agreement Wursethan a randdrn Clustering coef cient of scalefree random graphs 1 Cltkgt ltk gt ltkgt 39 N 1039 The seedndterrn depends dn ne variance drtne degree dish ibu inn Pkl 7 C NDWtrl Edr 73 Cincreasesvvith N n E J Newman 5mm Review05 m7 zznnai Expectanuns k21 grantednneetededrnpdnenr 2an cunnected 75347 giantcunnectedcumpunent 752 dnneeted Exponential random graphs Exponen ialquot does not refer to the degree distribution but to the model construction This is a statistical me nod for generating a of graph with N nodes byspecifying a distribution function over all graphs wi h N nodes 1 Select a set of informative network measures eg number of edges number oftriangles degree distribu ion 2 Then select a network from he ensemble of all graphs using the probability HG N 6x17 2 B parameters 5 network measures 3 Estimate the coef cients such that an observed real network corresponds to the most likely graph in that ensemble maximum likelihood estimation Markov graphs edges that do not share a node are independent Further reading Frank amp Strauss 1986 David Hunter39s webpage

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

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

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

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