Basic concepts of complex networks

A typical network consists of nodes and edges connecting two nodes , There are a large number of complex systems in real life that can be described through the network , Like social networks 、 Power networks 、 Transportation network, etc .

Basic concepts

【 distance 】 The distance between two points in the network (Distance) Defined as the number of edges included in the shortest path connecting two points

【 The diameter of 】 The diameter of the network (Diameter) It is defined as the maximum distance of all node pairs in the network

【 Average path length 】 The average distance is the average distance of all pairs of nodes (Mean Distance), The average path length . The average distance represents the most likely typical distance between two nodes , Determine the effectiveness of the network “ Size ”. The research shows that the average distance of the network in real life is generally a relatively small value , Even if the number of edges is much smaller than that of the fully connected network with the same number of nodes . This small average distance characteristic is called “ Small world effect ”.

【 Clustering coefficient 】 node A and B Connected to a ,B and C Connected to a ,A And again C Connected to a , This is the aggregation of the network . Clustering coefficient (Clustering Coefficient) That is, the cluster coefficient is a parameter to measure the degree of node clustering . Single node The cluster coefficient of is the ratio of the number of edges connected between all its adjacent nodes to the maximum number of possible edges . The Internet Cluster coefficient of C Is the average of the cluster coefficients of all nodes , obviously C<=1,C=1 If and only if the network is a fully connected regular network （ Any node is connected to all other nodes ）. In a random network C～1/N, The cluster coefficient is much smaller than that of the real network .

【 Degree distribution 】 Degree of node (Degree)k_i It's No i Nodes have the number of adjacent nodes , Is the simplest but most important feature of a node . The higher the degree, the more important the node is . The average degree is the average of the degrees of all nodes . Degree distribution indicates that the relationship between the number of nodes with a specific degree and the specific degree is available Distribution function P(k) Approximate representation ,P(k) Indicates that the network medium is k The proportion of nodes in the total nodes . Rule network , The degree of each node is the same , Then the distribution function is a peak , Impact function . Random network The degree distribution function of is Poisson distribution (Poisson Dostribution), The waveform of Poisson distribution is leaving the peak <k> On both sides Index Form decline . Complex networks in real life are generally subject to Power law distribution (Power-law Distribution), The power-law distribution decays much slower , Therefore, some nodes have large degrees . Because the power-law distribution is independent of a particular scale , So such a network is also called Scale free network .

Network type

【 Rule network Regular Coupled Networks】 Regular networks have large cluster coefficients and average distances . Fully connected to the network 、 Adjacency network 、 Star interconnection network They are all regular networks . Fully connected network With minimum average distance and maximum cluster coefficient （ Compared with the above three networks ）, It has the characteristics of a small world , The number of sides is the same as N^2 Isomorphism . Adjacency network It is a widely studied sparse regular network model , Each node is connected to only a few of its adjacent nodes , When the number of nodes is large , Its cluster coefficient C~=3/4. But adjacency networks are not small world networks , Because when the node goes to infinity , The average distance also tends to infinity , It is almost impossible for the network to achieve some kind of synchronization . Star interconnection network It is a regular network with high aggregation and small average distance , The central node is connected to other nodes, but there is no connection between other nodes , node N As we go to infinity , The cluster coefficient tends to 1, The average distance tends to 2.

【 Random network Random Graphs】20 In the middle of the century ,Erdos and Renyi Establish the basic model of stochastic network —ER Random graphs . Random networks have small cluster coefficients and small average distances . stay ER Random graph ,N Between any bright spots in the node, the probability p Connect , There are... In the whole network pN(N-1)/2 side . If the probability p Greater than a certain threshold probability , There are no isolated nodes or subnets in the network . The average degree of a random graph is p(N-1)~=pN, Cluster coefficient C=p<<1. about N Larger random networks ,ER The degree distribution function of random graph approximately obeys Poisson distribution .

【 Small world network Small-World Models】 Small world effect refers to two statistical characteristics: large cluster coefficient and small average distance , The network with this effect is Small world network . Robustness of small world networks 、 Propagation dynamics 、 Synchronization is the research hotspot of complex networks . Besides , A large number of real network nodes obey power law distribution , A power function is a curve that declines relatively slowly , Make the nodes with large degree exist in the real network . Power functions have scale invariance , Because a network whose nodes obey power law distribution is called Scale free network (BA Model ).

-【WS Model 】 A small world network model , Adjust parameters from regular network to random network . Construction algorithm ： A ring of regular networks , Yes N node , Each point points to the nearest neighbor K Nodes are connected K side . Each edge is represented by a probability p Change the nodes to reconnect and ensure that no duplicate edges appear , And then there will be pNK/2 A long-range edge connects the point to a distant node , change p Values can be implemented from the rule network (p=0) To a random network (p=1) The transformation of .

-【NW Model 】 yes WS The model is composed of new variables , The difference is , Never disconnect the original connection with adjacent nodes , But with probability p Increase connections with other nodes , Also ensure that there are no duplicate edges and self connected edges . When p=0 when ,NW The model is adjacency network ,p=1 Time-varying global interconnection network . When p Small enough and N Sufficiently large ,NW Models and WS The model is essentially equivalent , They call it Small world model .