'The Six Handshakes Rule Applies to Social Media'

Ivan Samoylenko specialises in graph theory; in his third year of university, he developed an idea that later became the foundation of a highly cited academic article. In this interview with the HSE Young Scientists project, he speaks about the Watts-Strogatz small-world model, being a performer in the Bolshoi Children's Choir, and making the choice between science and industry. 

How I Started in Science

I am a graduate of Moscow School 57 with specialised mathematics classes. While in middle school, I attended mathematics clubs there, and in 9th grade, enrolled in a mathematics class. Back then, I was introduced to some mathematical disciplines at a fairly advanced level. At the same time, I became interested in graphs, perhaps because many real-life problems can be clearly formulated using them. After graduating from high school, I enrolled in the Faculty of Mathematics at HSE University, where I am currently primarily focused on graph theory.

I work in two laboratories at HSE University. At the International Laboratory of Game Theory and Decision Making at the HSE campus in St Petersburg, I research the applications of graphs to game-theoretic problems. At the Faculty of Mathematics, we established the Laboratory for Complex Networks, Hypergraphs, and Their Applications. As the name suggests, my research there focuses on both graphs and their generalised form, hypergraphs. I explore these structures not only from a theoretical perspective but also in terms of their practical applications in various fields, including biology, medicine, and data analysis.

What Is a Graph?

Visually, a graph can be represented as a set of points (vertices) connected by lines (edges). The key characteristic of graph theory is its ability to describe almost any system as a collection of objects and their interactions. For example, when a journalist interviews me, it can be represented as a directed graph. However, this particular example does not clearly demonstrate the usefulness of graphs, as it does not reveal any new information about the interaction. On the other hand, when multiple journalists interview different scientists, graph theory can be used to analyse the structural properties of the vertices (people) and uncover non-obvious, high-level insights.

On the History of Graph Theory

Leonhard Euler is considered the father of graph theory. In 1736, he published a solution to the Seven Bridges of Königsberg problem. He proved that it is impossible to cross all seven Königsberg bridges and return to the starting point without crossing any bridge more than once. With the advancement of technology and the emergence of large datasets, graph theory has increasingly captured the interest of mathematicians and found applications across various fields of knowledge.

Another well-known problem in graph theory is the Four Colour Theorem, which states that no more than four colours are needed to colour any map that divides a plane into regions, ensuring that no two adjacent regions share the same colour. Although the problem is stated in a way that even a school student can understand and can be illustrated with simple pictures, it took humanity more than 100 years to solve. When a solution was finally found in 1976—by the way, the proof was far from simple, as one of its steps involved checking nearly 2,000 configurations—it marked a significant turning point in the history of mathematics as the first theorem to be fully proven using a computer.

In general, major breakthroughs and milestones in the history of graph theory are closely intertwined with the advancement of information technology. Thus, graph theory has gained particular popularity with the emergence of a well-understood example of a very large, irregular graph—the internet—which cannot be fully described by a small set of rules. The advent of the internet has, in general, led to the emergence of a major branch of graph theory—complex network theory.

The two main modern developments in complex network theory are the papers describing the mechanisms behind the emergence of complex networks in the real world: the Watts-Strogatz small-world model and the Barabási–Albert preferential attachment model. These papers have received a significant number of citations, which is quite rare in mathematics. The Watts-Strogatz model is even included in the top 100 most-cited papers of all time.

When large datasets become available, it is interesting to uncover structural patterns. Given the abundance of data available today, it is possible to construct informative graph systems in nearly any field. For example, I came across a study describing the graph of interactions among British composers of the 20th century. By calculating the characteristics of this graph, such as centralities, we can identify which composers were structurally important for the development of British music. Moreover, this can be analysed from various perspectives: some composers may be considered as independent musicians or founders of schools, while others may serve as connectors, enabling more successful colleagues to engage with one another.

In general, using the language of graph theory, one can formulate models—whether probabilistic or game-theoretic—and prove their properties through rigorous mathematical theorems. Thus, it is both an applied and a fundamental area of mathematics.

What I Take Pride In

I developed a game-theoretic model that explains why the ‘six handshakes’ rule observed in the real world also applies to social networks. Although it had been previously described why there should be relatively few handshakes, I was able to show where the 'magic number' of six comes from. An article on this topic, based on my bachelor's degree paper, was published in 2023 in Physical Review X.

It is easy to define a social network in terms of graph theory. Vertices represent people, and the relationships between them (such as acquaintance or friendship) are the edges. In this context, we can interpret the six handshakes rule as follows: if we take two random people on a social network, the probability is close to one that the path connecting them through the 'friends' edges will be no longer than six steps.

In the paper by Watts and Strogatz that I mentioned earlier, a random graph model was proposed in which a similar phenomenon could be observed. And I developed a model in which, on one hand, I explain why this model is reasonable, and on the other hand, I theoretically prove that if two people in the system happen to be more than six handshakes apart, the system will not be stable under relatively weak constraints.

It was a fortunate coincidence that our article was published 25 years after the one by Watts and Strogatz. Strogatz himself even mentioned our article on his social media. As a well-known public figure, his mention significantly boosted the visibility of our article. At one point, journalists from various countries even reached out to me for comments. As a result, based on my estimates using altmetrics—an indicator of attention and mentions in global media and social networks—my article is the most mentioned among those where the primary author is affiliated with HSE University.

Getting Published in a Highly Rated Journal

Getting published in highly rated journals is a unique kind of art—or more precisely, a craft. You may be a young genius, but if you don't know how to write articles or present your work in a format acceptable in your domain, you're unlikely to get published in top-tier journals.

Our article, as published in the journal, consists of two parts: the main, or 'selling' part, which is designed to be understandable even to those unfamiliar with the technical details, and an additional section that contains the technical aspects and detailed proofs. As the author of the concept and idea, I wrote nearly all of the additional material, including the detailed proofs, while a team of several leading scientists worked on the first part. First and foremost, a significant contribution to the publication was made by Stefano Boccaletti, to whom I was introduced by Andrei Raigorodskii, my academic supervisor in the MIPT doctoral programme.

Boccaletti was the first person who was able to read my drafts and believed in the concept I proposed. It's worth noting that back in 2021, when I began writing this paper, advanced LLM chats didn't yet exist, and my English was so poor that even in local paper competitions organised by the Faculty of Mathematics, my work failed to win any prizes. As I later discovered, one of the main reasons was that it was virtually unreadable.

Over time, Stefano invited his colleagues—renowned network scientists—to join our team and help refine and further develop the study. They guided us on which experiments to conduct and how to emphasise key aspects to make the paper suitable for publication in a major interdisciplinary journal. Eventually, everything fell into place—our article has been well-cited both in the media and in other scientific publications. Thus, discovering a phenomenon is one thing, but successfully communicating your results to the scientific community is quite another. Moreover, the criteria for making a publication interesting vary across different domains. For example, I know that my economist colleagues at the Game Theory Laboratory didn't particularly like the format of my work. I have yet to master the art of writing good economic articles.

On the Shortage of Time, Not Ideas

I maintain a document where I note down problems I could work on and where minimal progress has been made so far. There are over 20 items on my list. There is no shortage of ideas, but there is a shortage of time, and sometimes a lack of human resources.

It is often unclear in advance whether partially applied ideas are good or not, as this can only be determined through experimentation. In contrast, with theoretical concepts, you sometimes come up with an idea and immediately recognise that it is a good one. Even disproving it could be informative and interesting. It’s different with applied methods—if something doesn’t work, it’s no longer as interesting. On the other hand, if you already know the result in advance, why call it science? You are exploring, and if something works out, that's great.

My Dreams

I would like to see early-career Russian scientists have an easier life. So that they don't have to struggle to survive if they focus exclusively or primarily on science. Having technical specialists who can fully devote their time to research is critically important for the advancement of science and technology. I can clarify my perspective on this issue with an example from game theory. One of its concepts is that of a rational agent. Suppose a young man or woman acts as a rational agent when choosing which career to pursue. The assumption is that a career in science offers less money but more freedom in what you do, while the opposite is true for a career in industry. This is a trade-off with clear alternatives: for each individual, you can figuratively imagine the payoff function depending on these two factors, and each person chooses one of the two options based on which factor is more important to them.

However, this model is only relevant if the economic difference is not too large. In practice—although this problem is not unique to Russia, it is particularly acute here—the gap is enormous. In some situations, it may be wiser and easier to get a job with a corporation and, in your free time, get together with friends to discuss science, which is the choice some people make.

Another important issue is the time frame. From a bureaucratic perspective, many scientific projects/grants/programmes are cumbersome and inflexible. The inception phase of a project can begin when a student, for instance, has just enrolled in a master's programme, and by the time the project is actually launched, the student has completed the final pages of their thesis.

Under such conditions, an early-career scientist would need to seek part-time or side employment, remaining in a state of constant uncertainty, which leads to ongoing stress. As a result, many people—even those who are truly passionate about a career in science—become frustrated and simply abandon it. Providing competitive market conditions for early-career scientists and administrative support staff—in my view, a scientist should not have to handle paperwork but should focus on science unless they are paid to perform additional administrative duties—could lead to significantly more interesting developments and breakthroughs in science.

If I Hadn't Become a Mathematician

The simplest answer is that I would have gone into IT, because that's how I actually earn money. But in principle, I could have become anyone, because mathematics is not just about theorems—it's about a particular way of thinking. Indeed, I'm not sure who I wouldn't have been able to become. I could have even pursued a career in music— in fact, I once sang in the children's choir of the Bolshoi Theatre. Many opera productions feature pieces where children sing, and opera houses typically have children's choirs.

To clarify, so you don't think I'm anything like Luciano Pavarotti, it's much easier for young boys to be accepted into a children's choir than for girls. The children's choir of Bolshoi Theatre —at least when I was in it—consisted mostly of girls. Having a boy in the choir was considered a stroke of luck; there are fewer boys pursuing music to begin with, and many leave during early adolescence due to their voices changing. We had a situation where three boys stopped participating in performances at once. When two boys, each nearly a metre ninety tall, and a third one, big enough to be nicknamed 'Horse,' had to pretend to be small children while standing next to a soloist who was a head and a half shorter than them, it created a noticeable dissonance.

My Interests in School

I was interested in history. In fact, I came closer to winning the finals in history than in mathematics at the All-Russian Olympiad of School Students. I also played the game of What? Where? When? a lot in school and continued in university, although a little less frequently. Unfortunately, I don't have much time for this at the moment: I have to work in industry, pursue science, and handle organisational responsibilities in the laboratories where I work. 

Who I Would Like to Meet

John Conway. I can relate to his attitude toward mathematics—he saw it, among other things, in various everyday things. Although he became famous mainly for his Game of Life, he was, in fact, an incredibly multifaceted scientist with a large number of important publications across various fields of mathematics. I was deeply saddened when I learned in the news about his death early in the COVID-19 pandemic. It would also be fascinating to converse with mathematicians from the golden age of mechanics and mathematics, such as Andrey Kolmogorov, the author of the axiomatic foundations of probability theory.

My Interests Besides Science

I am a curious person and enjoy exploring various fields and learning about what's happening in the world. Sometimes I watch history channels, other times I might watch something about football or an odd documentary. In general, I am interested in almost any kind of information, though it's all unsystematic. What I do systematically is work: if I've had enough sleep, that's great; if not, well, there's nothing I can do about it.

Advice for Aspiring Scientists

Carefully consider your future track. I can also wish you patience and strength, both mental and physical—you will definitely need them.

My Favourite Place in Moscow

I really like Moscow as a whole. I have visited various cities, and I can't say that any of them compares to Moscow in terms of living comfort—though, of course, I'm biased being a Muscovite. If I had to name a specific place, it would be the Moscow metro—it is very practical, and the older stations are also aesthetically pleasing.