Complex network modeling (I)

degree 、 Average degree and degree distribution

The degree of a node is the number of adjacent edges of the node . The average degree is the average of all node degrees . Degree distribution describes the distribution of node degrees , It is usually represented by histogram .

Connectivity

In undirected network If any pair of nodes i And nodes j There is at least one path between , Then the network is connected , If it does not exist, it is disconnected .

Agglomeration coefficient

The agglomeration coefficient is used to capture the connection degree between the neighbor nodes of a given node . For a degree of k_i The node of i,
The local aggregation coefficient is determined as

As shown in the figure below

The degree of agglomeration of the whole network can be characterized by the average agglomeration coefficient , It represents the average value of the local agglomeration coefficient of all nodes

Global agglomeration coefficient

Degree distribution

The degree of nodes in most practical networks satisfies a certain probability distribution . Definition p(k) For the network, moderate for k The proportion of nodes in the whole network .
Rule network ： Because every node has the same degree , Therefore, its degree distribution is concentrated on a single peak , It's a kind of Delta Distribution .
Completely random network ： The degree distribution has the form of Poisson distribution , The probability of each side is equal , The degree of most nodes is basically the same , The average degree of the network is close to （k）, Away from peak （k）, The degree distribution decreases exponentially . This kind of network is called uniform network .

Cumulative distribution

The cumulative degree distribution function can be used to describe the degree distribution , The relationship between it and degree distribution is
$$P_k=\sum _{x=k}^{\infty }P(x)$$
It means that the degree is not less than k Probability distribution of nodes .

The diameter and average distance of the network

Two nodes in the network V_i and V_j A simple path with the least number of edges （ The sides of experience are different ）, Called geodesic . Number of sides of geodesic line d_ij Called two nodes V_i and V_j Distance between （ Or geodesic distance ）.
1/d_ij Referred to as a node V_i and V_j Efficiency between , Write it down as ε_ij. Efficiency is usually used to measure the speed of information transmission between nodes .
The diameter of the network D Defined as all distances d_ij The maximum

Average distance （ Characteristic path length ）

Average distance L It is defined as the average value of the distance between all node pairs , It describes the average separation degree between nodes in the network .
Many actual networks, although the number of nodes is huge , But the average distance is surprisingly small , This is the so-called small world effect .

degree — Degree dependence

1. Degree based on nearest neighbor average degree value - Degree dependence
degree - Degree correlation describes the relationship between moderately large nodes and low degree nodes in the network . If nodes with the high degrees tend to connect with the nodes with the high degrees , Then the network is degree - Degree positive correlation , The opposite is degrees - Degree negative correlation .
node V_i The nearest neighbor average of is defined as ：

among k_i Representation node V_i Degree value of ,a_ij Is the adjacency matrix element
All degree values are k The average value of the nearest neighbor average degree value of the node is k_nn(k) Defined as

In the formula N Is the total number of nodes ,P（k） Is the degree distribution function
If k_nn(k) With k Rise with the rise of , It shows that nodes with large degrees tend to connect with nodes with large degrees , The network has positive correlation characteristics , It is called co distribution network ; On the contrary, the network has negative correlation , Call it a mismatch network .
2. be based on Pearson The degree of correlation coefficient - Degree dependence
Newman Using the degree of nodes at both ends of the edge Pearson The correlation coefficient r To describe the degree of network - Degree dependence , The definition is as follows ：