Properties of Social Networks – Intro to Algorithms

Social networks are just graphs like the kinds of graphs we’ve been studying. But the real world networks that you actually find have some distinctive properties. And these have been documented by researchers like Duncan Watts and others. One property of these graphs is that they tend to exhibit the small world phenomenon, which essentially means that there are short paths between arbitrary nodes in the graph. Another is that they’re cliqueish, which means they exhibit a high clustering coefficient. I’m going to illustrate these two properties next. So this is me essentially. I live in Bernardsville, NJ. This is Chris M. He lives in Wellesley, MA and he’s very tall. Finally, this is Chris S. and I’m not sure exactly where he lives but I’m going to say New Brunswick, NJ. So last summer, Chris S. and Chris M. were both at the New Jersey Shore at the same time and they got together for drinks. Chris S. told Chris M. that he worked at Rutgers University. And Chris M. said, “Oh! Do you know Michael Littman?” And Chris S. said, “Actually yes. Small world!” So it turned out that Chris S. was connected to me. We both worked at Rutgers and had worked on a project together. And Chris Metcalf and I went to the same undergraduate institution, and we’re friends doing computer sciencey stuff. And here are these two random people meeting in some far away place hundreds of miles away from where they live and they had this connection between them and what we say when this sort of thing happens is it’s sort of a small world. Even though there’s lot people in lots of places, people are not as foreign to us as we might think. So the classic example of this kind of effect was from the experiment by Stanley Milgram. He very coarsely estimated that any person in the US was just 5 or 6 steps away from any other, and this gave rise to what we now think of as being the idea of 6 degrees of separation. In graph theoretic terms, what we say is that a graph exhibits the small world phenomenon if nodes have relatively small degree but also a relatively short path to other arbitrary nodes, and social network seem to exhibit exactly this property. So just to get you thinking about the degree of different graphs and the path links in different graphs, here’s four different kinds of graphs we’ve talked about before. Clique where all the nodes are connected to each other. A ring where the nodes are connected into a ring. A balance tree where you have a tree structure, but there’s a node that kind of separates the other nodes into these two different components that are about the same size. And a hypercube like this three-dimensional hypercube. And what I’d like you to do is think about in an N node version of that graph what is the degree and what is the path length between sort of the longest path link in the graph as a function of the number of nodes. Is it constant? Does it depend on the number of nodes in the graph? Is it logarithmic? Or is it linear? So a graph that has a low degree might be of 1 or log n, and if it has short paths it might be of 1 or log n. So which properties do these graphs exhibit?