How network math can help you find friends

Studying the structure of existing friendships in your environment can help you best form new relationships when creating a new circle of friends

Moving to a new school, to a new job, moving to a new city - how do you make new friends? You can approach the issue actively, form strategically useful links with popular guys. Or you can leave everything to chance, relying on random groups and connections. In any approach, understanding the structure of existing friendships in a new environment can help you form the best new connections that ultimately determine your circle of acquaintances.

Imagine moving to a new unusual city, Regular, in which there is a strange rule: each person can have no more than four friends, but at the same time everyone wants to maximize the number of their connections. What will the structure of Regular links look like? To study this question, we use a mathematical object called a network.

Simply put, a network is a collection of objects called nodes, and the links between them. Networks are a mathematically flexible concept. They can designate computers and the cables connecting them, the authors and their assistants, the state of the Rubik's Cube and transformations, which allow to switch between them - in fact, any type of connections, real or abstract. To explore friendships in Regulyarska, we will create a network in which the nodes will be people, and the connections are the friendship between them.

Denoting a network, it will be useful to represent nodes as points, and links as lines, which we can also call edges. Such a network diagram can help us understand its structure. So what will the network of friendly relations Regulyarska look like? At some point in time, it may look like this:



Each person will try to find four friends, and new people coming to the city will look for those who have less than four friends so far. This network will grow over time and constantly expand with the addition of new nodes. (It is possible to form independent groups, but in this example we will neglect them).

Network diagrams can help to understand them, displaying a clear structure. But when the networks grow, or do not exhibit such a regular structure as the Regular network, diagrams may become less useful. In this case, it is useful to develop various ways to analyze the structure of the network. One of them is to estimate the distribution of the degrees of the vertices.

In a network, the number of links of a particular node is called its degree. A node with a high degree is associated with many others; a node with a low degree is associated with fewer other nodes.


On the left - a node with degree 8, on the right - with degree 3

The degree of nodes is an important characteristic of the network, but local: it describes the structure of the network only within a single node. But if you cover the degrees of all nodes at once, you can create a useful tool for studying the global structure of the network.

In our network of friends, the degree of each node is the number of friends of one person. In Regulyarsk, most people have four friends, so most nodes have a degree of 4. No one will have more friends, but someone will have fewer, so there will be nodes with degrees of 3, 2 or 1. You can summarize the distribution of degrees in the following way:



This histogram conveys important information about the structure of our network. In this simple example, it may not convey as much as a complete network diagram to us, but we will see how the distribution of degrees can be very useful for studying various networks.

Let's move to another city. In the Disorder, dating is randomized. Since randomness is a tricky thing, let's clearly define the framework: each resident of the city is indicated by a network node, and each possible edge is a friendly connection. To create a random link, we will choose one of these possible edges randomly, and draw it, thus creating a link between two nodes, and therefore a friendship between two people.

What will the Clutter network look like? If we assume that we started with several nodes and randomly added several edges, the picture might turn out like this:



In such a diagram, it is difficult to see the structure. However, we will be much informed by the distribution of degrees in this network. It is difficult to calculate it directly, but it can be represented with the help of several important properties and a simple example.

Suppose you are one of the ten inhabitants of the disorder. How many probable friendships can exist in it? Each of the ten inhabitants can be associated with nine others, therefore, in principle, it is possible to draw 10 × 9 = 90 edges. But such a calculation takes into account each link twice - once for each of the two friends. Therefore, in fact, the total number of links should be 90/2 = 45.

Now, let's say we randomly choose a friendly relationship — that is, one of 45 possible edges. What is the probability that the edge will connect with you? Nine edges can depart from you, to one of the remaining nine nodes. Since nine of the 45 possible edges lead to you, the probability that a randomly selected edge connects with you is 9/45 = 1/5, or 20%.

But the same argument applies to disorder, so each node will have a 20% chance of connecting to a randomly selected edge. With an increase in the number of edges and nodes, these probabilities will slightly change, but in the long term they will remain approximately at the same level. That is, friendly relations will be approximately equally distributed throughout the disorder. In some places small deviations will be observed, but the likelihood that a person will have too many or too few friendships will be small. In Disorder, most likely, most residents will have close to average friends.

These features relate to the " binomial distribution " of the degrees of a typical random network.



Having access only to the distribution of degrees in the network, we can already find in it a certain uniformity: most of the nodes in terms of connectivity are average, and a very small number of nodes are in extreme positions. This information is useful for understanding network structure. With the addition of nodes, that is, with the arrival of new people in the city, the distribution will change slightly, while maintaining the main features.

But none of these examples — no more than four friends in Regulyarsk or a randomly appearing friendship in Disorder — is a realistic model of friendships. People may have more than four friends, and the presence of a large number of acquaintances is not at all such a rarity as in the binomial distribution. What will be a more realistic model of friendship?

When building links with friends and friends, the structure of your friendships will most likely resemble other networks in the real world — food networks , protein-protein interactions, or the Internet. Their properties characterize the so-called scale - free networks - such a connectivity model has dominated the science of networks for more than 20 years. Researchers from mathematics, physics, economics, biology, and the social sciences observed characteristic signs of scale-free networks in their fields of study.


Complicated scale-free social network

The structure of a scale-free network depends on the simple principle of “preferred connections”. The preferred connection is the “rich get richer” rule, which refers to the growth of networks. A node with a large number of existing connections is much more likely to get new connections than a node with a small number. New connections demonstrate hubbing with lots of connections.

Does this make sense in the context of the formation of friendly relations? In principle, it is reasonable to assume that a person with a large number of friends is more likely to make new ones. Since he is already associated with a large number of people, the probability of meeting new people thanks to existing connections is high. The more friends, the more opportunities to make new friends. And the fact that they already have a lot of friends, says that they have some kind of opportunity or a penchant for friendship. This is more likely to attract others to them, just as popular sites attract links from other sites and blogs, and developed cities generate new railways and air routes.

And although the growth of scale-free networks is influenced by several factors, many consider preferred communications most important. It also has an amazing effect on the distribution of degrees in the network.



It predicts the appearance of a distribution with a "thick tail." Most of the nodes in the network will have a small degree, but there will also be nodes with increasing degrees. This is very different from the friendly networks of Regulyarska and Disorders, in which there are very few nodes with large degrees.

These nodes with large degrees work as network hubs and are a critical characteristic of scale-free networks. They are social butterflies in networks of friends, banks in the center of economies, centralized routers that allow regional Internet connections to pass through,Kevinov Beykonov acting world . Hubs can provide a feeling of a close world in a huge network - for example, any two randomly selected people out of 2 billion Facebook users are on average no further from each other than in four friendships . The number and variety of hubs gives scale-free networks resistance to certain types of breaks. For example, even with the failure of many Internet connections, messages can still reach, in particular, because there are still many ways to get to many hubs to many other hubs.

And while many agree that scale-free networks and their properties are useful, there are contradictions in this area of ​​research. The exact mathematical characteristics of such a power distribution are sometimes difficult to interpret. In the book Related: New Science of Networks [Linked: The New Science of Networks], the pioneer of network research and the physicist Albert-Laszlo Barabasi writes that in networks showing preferred connections, the distribution of degrees will follow a power law. Power-law distributions are often found in many physical situations — for example, in the inverse square law for gravity or electric fields. They can be represented as functions of the form

$$

Their charts usually look like this:



Power distributions do have “fat tails”. But how thick? How many hubs of a certain degree should there be in such a network? In a study published this year, more than 1,000 real-life networks were studied, and it was found that only one-third of them can have a power distribution described by a power law. For many networks, the distribution of powers can be more accurately described as exponential or lognormal . They may have the high-level properties of scale-free networks, but can they be considered as such if the degrees in them are not distributed as expected? And does it even matter?

It matters if we want to connect our theories with our data. Is the preferred connection the main factor in the formation of scale-free networks? Are there other factors that play an important role and can divert the distribution of degrees in the other direction? Having answered these questions and having understood which questions should be asked further, we really will better understand the nature and structure of networks, how they develop and evolve.

These contradictions also remind us that mathematics, like networks, is also a set of developing links. Modern research challenges 20-year-old hypotheses in the relatively new field of network research. New ideas, joining the network, connect all of us with the mathematics of both the past and the future. So in math questions, as well as in the field of friendship, it will be useful to find hubs and maximize your degree.

Exercises

• What will the network of friends look like if each person has exactly two friends?
• In Regulyarska each person can make up to four friends. There may exist separate groups in which each person has exactly four friends. How many people can belong to such a group? (Hint: the answer is related to the correct polyhedra ).
• Our networks are based on the fact that friendship is a symmetrical concept. If A is friends with B, then B is friends with A. How can we tweak our network model so that it can include asymmetric connections in which A can be friends with B, and B is not friends with A?
• In Friends, each resident is friends with everyone else. If there are n people living in Friendship, how many friendship ties are formed there?