Integrated Networks

Complex networks or complex networks ( Eng. Complex networks ) are networks existing in nature ( graphs ) with non-trivial topological properties.

Most objects of nature and society have binary connections, which can be represented in the form of a network, where each object is a point, and its connection with another object is a line or arc.

So relationships between people in a group (see social network (sociology) ), relationships between firms, computer networks , the Web , relationships between genes in DNA are all examples of networks ^[1] ^[2] .

The topological properties of these networks (see topology ), considered abstractly from their physical nature, but significantly determining the functioning of networks, are the subject of study of complex networks.

Complex networks are a relatively new, rapidly developing interdisciplinary field of knowledge. Now its basic concepts are being laid and only the first results have been obtained. Researchers working in this field came from mathematics, computer science, physics, biology, sociology, and economics. Accordingly, the research results are of both theoretical value and practical applications in these sciences.

Content

Key Features of Complex Networks

Oriented and non-oriented networks

Each network node (node) can be connected with other nodes by a certain number of links (links). Connections between nodes can have a direction. In this case, the network is called a directed network. If the connection is symmetrical for both nodes connected by it, then the network formed by such connections is called an undirected network. For example, the Web is a focused network, and the Internet is a non-oriented network. Sometimes the issue of network orientation is not so trivial. For example, relationships between people. If we consider that a connection exists, if two persons are close friends, then the network will be disoriented. If we consider that a connection exists, if one person considers himself to be another, then the formed network will be oriented.

Degree distribution of nodes

The number of links of a node will be called the degree of the node. For oriented networks, the outgoing and incoming degrees of a node are distinguished (out degree and in degree). The degree distribution of nodes is an important characteristic of a complex network. Most complex networks have a power law distribution of the degrees of nodes with an exponent between 2 and 3.

Average distance between nodes

The minimum number of links that must be overcome in order to get from a node to a node is called the distance between the nodes. The average distance between all pairs of network nodes for which there is a transition path from one to another is called the average distance between nodes $d$ ${\ displaystyle d}$ . For most integrated networks $d\sim \log(N)$ ${\ displaystyle d \ sim \ log (N)}$ where $N$ ${\ displaystyle N}$ - the number of nodes in the network.

Cluster coefficient

We will call two nodes neighbors if there is a connection between them. It is typical for complex networks that two nodes adjacent to a node are often also neighbors. To characterize this phenomenon, a cluster coefficient was proposed. $C_{i}$ ${\ displaystyle C_ {i}}$ knot $i$ ${\ displaystyle i}$ . Suppose a node has a degree $k_{i}$ ${\ displaystyle k_ {i}}$ , it means that he $k_{i}$ ${\ displaystyle k_ {i}}$ neighbors and between them there can be a maximum $k_{i}(k_{i}-1)/2$ ${\ displaystyle k_ {i} (k_ {i} -1) / 2}$ connections. Then

C_{i}={\frac {2n_{i}}{k_{i}(k_{i}-1)}},

{\ displaystyle C_ {i} = {\ frac {2n_ {i}} {k_ {i} (k_ {i} -1)}},}

Where $n_{i}$ ${\ displaystyle n_ {i}}$ - the number of connections between neighbors of the node $i$ ${\ displaystyle i}$ . Obviously always $0\leqslant C_{i}\leqslant 1$ ${\ displaystyle 0 \ leqslant C_ {i} \ leqslant 1}$ . The average cluster coefficient of nodes is called the cluster coefficient of the network. For most complex networks, it is significantly larger than the cluster coefficient of a random graph of the same size.

Assortativity Coefficient

A situation is possible in the network when nodes with a large degree (“stars”) are mainly connected with nodes with a large degree. In other words, “stars” “prefer” to be associated with “stars”. Such networks are called assortative. The opposite situation is also possible: “stars” are connected with other “stars” through chains of nodes having a small number of neighbors. Such networks are called disassortative. To characterize this property, use the coefficient of assortivity $r$ ${\ displaystyle r}$ - this is the name of the Pearson correlation coefficient between the degree of neighboring nodes. By definition, $-1\leqslant r\leqslant 1$ ${\ displaystyle -1 \ leqslant r \ leqslant 1}$ . For assorted networks $r>0$ ${\ displaystyle r> 0}$ for disassorted networks $r<0$ ${\ displaystyle r <0}$ . Networks associated with social events are assorted. Networks associated with biological phenomena are often disassortative. There are networks that do not have pronounced assortativeness with $r$ ${\ displaystyle r}$ close to zero.

Notes

↑ Dorogovtsev SN, Mendes JFF Evolution of Networks: From Biological Networks to the Internet and WWW. - Oxford, USA: Oxford University Press, 2003 .-- P. 280. - ISBN 978-0198515906 .
↑ Mark Newman, Albert-Laszlo Barabasi, Duncan J. Watts. The Structure and Dynamics of Networks: (Princeton Studies in Complexity). - Princeton, USA: Princeton University Press, 2006 .-- P. 624. - ISBN 978-0691113579 .

Links

Barabasi Alberta Model

[lit1-1] Dorogovtsev SN, Mendes JFF Evolution of Networks: From Biological Networks to the Internet and WWW. - Oxford, USA: Oxford University Press, 2003 .-- P. 280. - ISBN 978-0198515906 .

[lit2-2] Mark Newman, Albert-Laszlo Barabasi, Duncan J. Watts. The Structure and Dynamics of Networks: (Princeton Studies in Complexity). - Princeton, USA: Princeton University Press, 2006 .-- P. 624. - ISBN 978-0691113579 .