Density Property of Real Networks Many networks densify over time, but are still sparse E(t 10 Autonomous Systems 10 10 Edges 0.87x11R2=100 Number of nodes
Many networks densify over time, but are still sparse N(t) E(t) 1.18 Autonomous Systems
Small-World Property of Real Networks In most real networks there are small distances between two randomly selected nodes Network Name N L k d d Internet 192,244609,0666.34 6.98 WWW 3257291,4971344.60 11.27 93 8.32 Power grid 4,941 6.594 18.99 46 8.66 Mobile phone calls 36.595 91,826 2.51 11.42 57194 103,731 1.81 5.88 Science collaboration 8.08 5.35 985 184 4.81 Actor Network 212,25030542782878 Citation Network 4496734,70795810.47 11.21 E Coli Metabolism 1039 5,802584 2.98 8 east Protein Interactions 2.018 2,930 2.90 5.61 714
• In most real networks, there are small distances between two randomly selected nodes
Clustering Property of Real Networks Many real networks have a much higher clustering coefficient than expected for a completely random network of same no of nodes and links High-degree nodes tend to have a smaller clustering coefficient than low-degree nodes
• Many real networks have a much higher clustering coefficient than expected for a completely random network of same no. of nodes and links • High-degree nodes tend to have a smaller clustering coefficient than low-degree nodes
Scale-Free Feature of Real Networks Many real networks are scale-free in the sense that the degree distribution deviates significantly from the poisson distribution Bell Curve Power Law Distribution teith only a few links number of links No highly A fw hubs with large number of links Number of links(k) Number of links(k)
• Many real networks are scale-free in the sense that the degree distribution deviates significantly from the Poisson distribution
Towards High-Order Degree Distribution Average Degree < k>=2M/N Degree Distribution P(h)=n(k)/N(k)=kP(k) How many nodes have degree k? What's the maximum degree? We need more properties to characterize a network Ex. Whom do u contact with?
Towards High-Order Degree Distribution = k M N 2 / P k n k N ( ) ( ) / = 0 ( ) k k kP k = = Average Degree Degree Distribution We need more properties to characterize a network How many nodes have degree k？ What’s the maximum degree? Ex. Whom do u contact with?