### Create a StudySoup account

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

Already have a StudySoup account? Login here

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

### View Full Document

## 30

## 0

## Popular in Course

## Popular in Department

This 31 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 30 views.

## Similar to Course at Penn State

## Popular in Subject

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

Universality in largescale networks Properties common to many largescale networks independently of their origin and function 1 The degree and betweenness distribution are decreasing functions usually powerlaws 2 The distances scale logarithmically with the network size logN logltkgt 3 The clustering coefficient does not seem to depend on the network size Cocltkgt As though all these networks were part of the same familyclass Random networks The average distance and clustering coefficient only depend on the number of nodes and edges in the network This suggests that general models based only on the number of nodes and edges in the network could be successful in describing the properties of an expected characteristic network Random network distributes the edges randomly among nodes Probabilistic interpretation There exists a set ensemble of networks with given number of nodes and edges Select a random member of this set What are the expected properties of this network studied by random graph theory EX 1 Start with 10 isolated nodes For each pair of nodes throw with a dice and connect them if the number on the dice is 1 Describe the graph you obtained How many edges are in the graph Is it connected or not What is the average degree and the degree distribution EX 2 Now connect node pairs if the number on the dice is l or 2 How is the graph different from the previous case EX 2 How many edges do you expect a graph with N nodes would have if each edge is selected with throwing with a dice Random graph theory ErdosR nyi algorithm Publ Math Debrecen 6 290 1959 39 fixed node number N 39 39 39 39 connecting pairs of nodes with probability p p0 p01 p015 NN 1 Expected number of edges E p 2 Random graph theory studies the expected properties of graphs with N oo The properties of random graphs depend on p Properties studied is the graph connected does the graph contain a giant component what is the diameter of the graph does the graph contain cliques complete subgraphs Probabilistic formulation what is the probability that a graph with N nodes and connection probability p is connected Some of these properties appear suddenly at a threshold pCN 0 f MN gt0 pJN Z7 PNpQ 11f pN oo Subgraphs of a random graph Consider a subgraph with n nodes and e edges Expected number of of these subgraphs in a graph with N nodes and connection prob p We can permute n 4 EX C 12 the n edges In any Ways of selecting n nodes from N N I a way we want but identical isomorphic graphs do not count Probability of having e edges Isomorphic graphs there exists a onetoone mapping ofthe nodes in such a way that if and only if connected A E 1 5A B o 3 1 43 D node i and j are connected in one 39 then their images i and j are also C 4 3c 2D 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 en N EXCNp 7 1 a If the connection probability is a function of the number of the nodes we can find the condition of having a nonvanishing number of subgraphs Illim pNN e 0 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 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 For p lt N391 the graph contains only isolated trees 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 o p I X I he graph becomes connected If 1 Node degrees in random graphs average degree ltkgt E pN degree distribution Pk Pk E Csz ka1 UN H k ways to select k probability of nodes from N1 probability of missing N1k having k edges edges Most of the 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 39 hr of first neighbors N SUI hr of second neighbors NZ Eltkgtz estimate maximum distance log N logltkgt m IzltkrN e zm 1 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 Cl E L klkl 12 Since edges are independent and have the same probability p kiki1 quot151 acgpltkgt N 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 forthe real network Determine I C and Pk for a random graph with the same N and ltkgt logN k rand z Crand p Q logltkgt N Pm k E Czkv ka 1 UN H Measure I C and Pk for the real network Compare l ogltkgt 15 10 5 Path length and order in real networks I logN rand neural network X power grid Acollaboration networks vavw lmetabolic networks lnternet X I x i r I Vfood webs Real networks have short distances like random graphs yet show signs of local order Cltkgt 39food webs neural network I metabolic networks X power grid collaboration networks vavw 10 Pmk The degree dis ribution of the VWWV is a powerlaw 100 a 1072 7 3 a 7 7 7 4 7 O 7 7 7 1O A Pautk k z45 1076 7 7 5E 7 7 21 B n 10 7 O 7 7 7 10quot 7 7 7 7 10712 72 U 2 4 6 72 U 2 4 6 1O 1O 1O 1O 1O 1O 1O 1O 1O 10 k k R Albert H Jeong AL Barab si Nature 401 130 1999 A Broder eta Comput Netw 33 309 1999 Powerlaw degree distributions were diverse networks 10 1oquot 10 2 P0010 Pk k39 104 10 5 10 5quot Internet router level Actor collaboration O i i i i i i 39 Go a u b O 7 00 7 00 E 7 00 7 7 RE Q E u Qb 93m 10quot 101 1o2 103 101 102 103 k oundin Pkk39 R Govindan H Tangmunarunkit IEEE Infocom 2000 A L Barab si R Albert Science 286 509 1999 The powerlaw degree distribution indicates a heterogeneous topology Pk log Pk k log k Large variability the average degree not informative no characteristic scale for the degree Scalefree The average degree gives the characteristic scale value ofthe degree Idea generate random graphs with a powerlaw degree distribution Fixed N PkAk7 kltK Network assembly random edges but enforcing the right Pk 1 23quot K 2Pk1 gt A k1 K y1 ltkgtikPkgt ltkgt21Kk k1 2 Ifquot 1 The number of edges increases as 7 decreases Constructing graphs with a given degree distribution Configuration model choose a degree sequence NkN Pk give the nodes k stubs according to Nk connect stubs randomly M E J Newman 8 H Strogatz and D J Watts Phys Rev E 64 026118 2001 Ex Construct a graph with 10 nodes and degree sequence N14 N23 N32 N41 What is a necessary condition for the graph construction Theory of general random graphs Looks at a characteristic member of the ensemble of graphs with given degree distribution Seeks the answers to the same questions as random graph theory is the graph connected does the graph contain a giant component what is the diameter of the graph what is the clustering coefficient of the graph The theoretical concept needed for the analysis is the generating function H Wilf Generatingfunctionology 1994 Generating functions in a graph Node degree generating function G0x iPkxquot x s 1 Finding Pk and degree moments from the generating function Pkdd ltk gt 2k Pkx Gm If a certain property is described by a gen function then its sum over m independent realizations is generated by the mth power of the gen function x1 The generating function for the sum of the degrees of two nodes is G0x2 Generating functions in a graph Generating function for the degree of nodes at the end of a d d 39 Tan 0m 6 g6 d1scount the edge we pTObability t0 wde arrived along kP k x Gm Gave ZkPk 39 631 normalization M E J Newman S H Strogatz D J Watts Phys Rev E 64 026118 2001 Finding connected components in a random graph Breadthfirstsearch algorithm start from an arbitrary node follow its out edges record its first neighbors follow the out edges of first neighbors record any new node found continue until no new nodes are found The same step follow the edge is repeated over and over Generating functions for connected components PS distribution of component sizes H0 x ZPsxs x s 1 s0 Generating function for the cluster we reach by following a randomly chosen edge 2 l 3 repeat the same step for each edge probability to nd that node 2km H1xk1 H1x quot kPk g normalization HoxxGoH1x xG1H1x Existence of a giant connected cluster Average size of marked clusters ltsgtHg11 G3 1 GI1 Z kPk Diverges when G171 E W 1 k ltk2gt Equlvalent to W 2 A giant connected component exists if the graph is sufficiently heterogeneous Theory of scalefree random graphs The theory of scalefree random graphs is in many ways similar to that of ErdosR nyi random graphs Graph properties depend on 7 giant Cluster 7 5 347 connected y g 2 W Aiello F Chung L Lu Proc 32th ACM Theor Comp 171 2000 M E J Newman S H Strogatz D J Watts Phys Rev E 64 026118 2001 Average path length of scalefree random graphs Network N Pkzk397 for kSK 1nNB A M E J Newman S H Strogatz D J Watts Phys Rev E 64 026118 2001 Prediction 1 1 ABf7K I I I Vfood webs ltgt Elmetabolic networks 15 Olnternet Acollaboration networks 0 OWN qualitative agreement co io A worse than a random N A 2 A0 graph 5 D o 9 10 11392 10 16 10 10 Clustering coefficient of scalefree random graphs 2 2 2 Cltkgtltkgt ltkgt N ltkgt2 The second term depends on the variance of the degree distribution Pk z kquot C N N3777 1 For y lt 73 C increases with N M E J Newman SIAM Review 45 167 2003 Network Size ki K M 7m 4quot a Reference N www 3272 m mm 245 u 112 332 477 Ail nenngandBnnbdsilWU 1 www 4xm39 7 2 32 u Roma 7 7 ma 2 www 2an 75 wan 272 21 is as 761 Brmiumuij 3 wm 39 sue Moo m4 Hubernnn and Adamlc was 4 ImemeLdOmam 30i5433a 3427375 304 21722 2H 4 63 52 Faiauisos 19W 5 Inlemelmmex sass 257 30 242 m 1215 75 767 Faiauisos ma 5 Inlemelmmex now 266 an 24 24 n in 747 Govumanl 7 Movieaclms 212m 2m ago 22 22 454 365 am BambmnndA vxLi ZW a Conmhum snags 55517 m 1100 12 12 4 2m ADS quotmm 2mm a ammunmmv sums 1154 we 1 21 a 501 m Banba39suml mm m Cmnulhmxmmh 7m 39 120 25 2 95 22 653 Earbdsuml mm 11 Sexunlcamaus mu 4 24 Liiyemstrnl 2mm 12 MembahcE mi 77 74 110 2 22 32 322 m Jemgszai man 73 pm s cutv mu 23a 24 24 Jean Mam m m 14 yuunemw w x7 25 ms 105 242 225 171 Monmvnand sm 2mm 14 5mm Pmk 154 47s 27 m 172 34 222 2 Monmynand smmn 16 Cunuan 723339 a 57 3 Iednu 199 17 Phonech Slxm m 1 21 mummy mm 18 Waiamammema 4mm 7013 7 27 Fermi mmmsme m w Woldssynoi7n1 quot 22311 1242 a 2 Yuck v ai lamb in Expectations k2 1 y S 347 giant connected component giant connected component k 2 MN connected 7 s 2 connected Exponential random graphs Exponential does not refer to the degree distribution but to the model construction This is a method for generating an ensemble of graphs with N nodes 1 Select a set of informative network measures eg number of edges number of triangles degree distribution 2 Then generate an ensemble of graphs that have the those measures using the probability P G exp 231 Bi parameters a network measures 3 Estimate the coefficients such that an observed 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 chapter V of Newman 2003 review Frank amp Strauss 1986 Ex 1 A random graph has average degree ltkgt10 a How much is the maximum distance between nodes for N10nr where n2 3 b How much is the clustering coefficient for the same network sizes Ex 2 Answer the same two questions for a ring lattice where every node has degree 10

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

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

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

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