Mathematicians have been studying graphs for a long while. Sociologists found out that some of them explain how we interact. Indeed, social networks just make the connection more evident to anyone. In the middle of that, some researchers have been wondering about the following question: can we make optimal decisions based on our local information into a social network?
A world of lines and dots…
Dots and lines connecting pairs of dots – that’s a graph (but we usually say vertices and edges – or nodes and arcs – when talking about them). Mathematicians study graphs because they are structures capable of modeling lots of relationships among entities. Sometimes they wonder if a property found in a certain graph implies another one, developing statements to the Graph Theory. Other times they want to leverage those properties when designing an algorithm that manipulates certain types of graphs, like in Combinatorial Optimization algorithms. As a matter of fact, that is not an isolated case – many researchers handling real-world problems aim at designing algorithms with an outstanding performance for the most common instances they expect to solve.
… and the world of people!
Many people have already heard about the “six degrees of separation” principle, which states that – on average – you can reach any person in the world through a chain of six people that know one another. Such “magical number” emerged from experiments of Stanley Milgram and others during the 1960’s, in which they asked a person in the U.S. to deliver a letter to another person by submitting it to someone that he/she knew and who he/she supposed to be closer to such person. Theoretical results also point something similar: for a random graph, the average shortest distance among pairs of vertices is proportional to the logarithm of the number of vertices, what means a very slow pace of increment as graphs get bigger and bigger. However, that is not truefor any graph. Instead, people started looking to a more specific class of graphs called Small World Graphs, which are supposed to be representative of a number of situations.
Small World Graphs to be explored everywhere
Small World Graphs can be though as a combination of lattices (grids of edges) and clusters or quasi-clusters (groups in which almost all edges exist among vertices) with a small average degree (number of edges from each vertex). The former property ensures that the graph is connected and it is possible to find a path among any pair of vertices. The later has to do with the fact that two vertices sharing an edge with a third one are more likely to share an edge among them. Think about it: you might know some people from your university, almost everyone from your department, whereas each of your colleagues is more likely to have long range connections with researchers sharing a common interest worldwide; and all of that together means that you don’t need many steps to reach most of the researchers in the world. The same goes valid for airports: your local airport might be connected to a number of airports in other cities of your country and some of them are connected to airports worldwide in a way that you can attend to your meetings everywhere without worrying too much about how to get there. However, if you need to think about it, you might probably come up with a very good answer, isn’t it?
Do we always have optimal answers from local network information?
That’s the question that Jon Kleinberg tries to answer in the article “The Small-World Phenomenon: An Algorithmic Perspective”. He claims to have found the class of graphs for which such local information ensures an optimal decision. To be honest, I didn’t read the entire paper (I’m in really busy times) but it sounds really interesting and I left to the curious reader such task (let me know about it after).
—
This post was prompted by the INFORMS Blog Challenge of July: OR and Social Networking. You can check all the submitted entries by August 4th.
Thiago Serra 