2014 Network Science: An Introduction Chapter 4 Degree Correlations & Community Structure Xiaofan Wang xfwang@sjtu.edu.cn
Xiaofan Wang xfwang@sjtu.edu.cn 2014 Network Science: An Introduction
Your Directed Network 节点数101;边数242 节点数81;边数204 9..s 。““ 相同节点72;相同边数106
节点数 101；边数 242 节点数 81；边数 204 相同节点 72； 相同边数 106
Your Undirected Network 节点数101;边数144 节点数81;边数121 ● .,③ °.。· 相同节点72;相同边数73
节点数 101；边数 144 节点数 81；边数 121 相同节点 72； 相同边数 73
Qu uIz Q How can a network be constructed from these streets? Nodes. Street blocks Intersections Roads Edges: an edge is drawn between two nodes if they are adjacent directed connected by a segment of street with no intervening intersect
Nodes: • Street blocks • Intersections • Roads Edges: an edge is drawn between two nodes if they are • adjacent • directed connected by a segment of street with no intervening • intersect
Connectivity Property of Real Networks Many networks have a unique giant component o。o a
Many networks have a unique giant component
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 =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?