Friendship Paradox
en.wikipedia.org
en.wikipedia.org
Things get more interesting when you start taking longer walks. If you take a long enough walk in a (strongly connected) graph, the probability of ending up in a particular place becomes independent of your starting point.
In fact, social graphs are said to be "fast-mixing", which means that "long enough" is typically only O(log n). In contrast, if you were walking in a two dimensional lattice, "long enough" would be O(sqrt n). This is the idea behind the "6 degrees of separation" factoid.
So what is the limiting probability distribution? That's actually the pagerank.
Which means that if friends randomly pass on a token, it's likely to end up in the hands of someone very influential with a lot of friends. It's been used for vaccine delivery.
And this was the foundation of Google's PageRank. http://en.wikipedia.org/wiki/Google_matrix
Once you think "random-walk" you can build a whole class of "intentional surfer" model which model surfers seeking particular information.
You have a limited number of "waste your more important contact's time" tokens. You get more when you successfully introduce someone who is useful to your higher-status contact,
The odd thing is, even in an unsuccessful match, where you introduce two people and they don't establish a relationship they both find pleasant, if you connect a lower-status contact with the higher-status contact, even if the match is unsuccessful, you are still seen to have done your lower-status contact a favor, even though you have annoyed the higher status contact, so if the lower-status contact is someone you want to curry favor with, it might make sense to introduce them even if there is a lower probability of them forming a mutually profitable relationship with the higher-status contact, but normally it's a matter of "how interesting is the potential relationship between the two people I am introducing," which takes some thought and often times means not making the introduction.
The upshot here is that I'm not going to just right out introduce two of my contacts. I mean, I will if I think they can have a beneficial relationship, but I generally feel pretty weird when someone directly asks me for an intro to another specific person, rather than 'Hey, do you know anyone who is good with X" - because with the latter, I can talk to each person individually, and I can silently drop the whole thing without telling the other they were rejected, whereas if X asks me to introduce them to Y, and either Y says they are not interested or I think I would annoy Y, then I've gotta reject X, which can be awkward.
no?
with what is said above, it would seem to suggest that after enough people, the person you are introduced to is irrelevant to the first person who started introducing you to people.
Why not online matchmaking / dating? Not being in that market I have no idea if this already exists, if not it sounds like a great idea for a startup. Or if it already crashed and burned that would be interesting to hear about.
So ... guys ... I have this unattached sister in law, kinda athletic, professionally employed, owns her own house, she is about as much of a PITA as her sister, aka my wife, so if I can put up with my wife you should be able to tolerate her little sister ...
From historical experience my attempts setting up blind dates between my SiL and guys I know, have all gotten shot down by my wife, aka her sister, with what summarizes to "WTF were you thinking". Assuming a similarity between matchmaking and business relationships, this might indicate issues with peer to peer connection building. At least a meta-moderation facility is likely needed.
Also if A sets up a hot date or business lunch between mutual friends B and C I could conceivably lose both B and C as friends if they hate each other. So in a game theory perspective the guy who does the least matchmaking comes out furthest ahead, right? But the purpose of the site was to do matchmaking, at least in theory and in PR. Although the real purpose would be to sell subscriptions and ads. I think I'm seeing another problem here.
Six degrees of separation refers to shortest paths, and fast mixing is decidedly _not_ the intuition behind it.
You're right, 6 degrees of separation is a statement about diameter, but a small diameter and mixing speed are related.
[1] https://www.comp.nus.edu.sg/~yuhf/yuh-sybillimit.pdf
[2] http://www.internetsociety.org/sites/default/files/dane.pdf
-----
EDIT: Wow, I've read that paper you linked to. So they use the data-set from SNAP like Facebook A and Facebook B.
But, if I understand correctly, these data-sets were formed by combining "egonets", which means they took a set of people and a small ball around them, and put all those balls in the graph. That explains the horrendous eigenvalues.
In fact, the main problem with the paper is the opposite -- the Facebook graphs they use are regional networks borrowed from [1]. This means that Facebook's actual mixing time should be _dramatically higher_ than the times measured in the paper because of the tendency of random walks to get stuck in regional networks. I believe this is the reason their Facebook-A and Facebook-B mixing times are much lower than the others, such as LiveJournal.
Alvisi et al. have a couple of related papers specifically looking at the implications of our new understanding of social-graph random walks for sybil defenses. [2, 3]
[1] https://www.cs.ucsb.edu/~ravenben/publications/pdf/interacti...
[2] http://www.cs.utexas.edu/users/lorenzo/papers/Alvisi13SoK.pd...
[3] http://www.cs.utexas.edu/users/lorenzo/papers/Alvisi14Commun...
Imagine 1,000,001 people. One of them is friends with the rest, all of whom only have this one friend. The average number of friends a person has is 2, but the aggregate average for their friends is 1,000,000.
So most social graphs probably look like a spoke-hub where a minority of people have a very large number of friends.
For example, I’m near the average on thinking vs. feeling and judging vs. perceiving, so I don’t consider those traits terribly important or informative. However, I am moderately more introverted than extraverted and significantly more intuitive than sensory. Then again, I don’t need a personality quiz to know that!
Any time you try to reduce people to a few traits—Myers-Briggs, the Enneagram, whatever—you lose so much information that the exercise becomes nearly futile.
- Introspection, not introversion.
Careful. That quip is almost good enough to become famous for.
How does this one work? It doesn't seem to fit. I'm more likely to be friends with friendly people, more likely to have sex with people who like to have sex, why am I more likely to be around successful people?
[0] http://www.technologyreview.com/view/523566/how-the-friendsh...
The example of twitter makes this a bit more clear: your followers have more followers, on average, than you. But that's because you likely follow someone with a million followers. That one person greatly affects the mean follower count.
So if you follow 10 people, one of whom has 1000 followers, and the rest just have one, the paradox still holds.
I used to read them carefully first, to decide whether I should up-vote. But from that experience, I've learned I almost always should -- the downvotes were rarely warranted, and almost always lazy and brainless. So I may as well save time and cut to the chase -- just upvote.
(If enough of us do this, maybe we can minimize the problem HN is seemingly unwilling and/or unable to address.)
Start with the baseline assumption that people are broadly similar to the people they're friends with -- i.e. socialites are friends with socialites, loners are friends with loners.
Overlay that with the observation that you're more likely to be friends with someone who has lots of friends, and less likely to be friends with someone who has few friends.
Consider the extremes: You're certain to be friends with someone who is friends with everyone, and certain to not be friends with someone who has no friends.
I think it is not as much a paradox but rather a good demonstration of how the average can be an inappropriate measure to describe some samples.
Imagine that there was one single person who was friends with all 7 billion people on Earth. Assuming nobody else had more than about 250,000 friends, this would cause every other person on the planet to have fewer friends than their friends have, on average. That one person skews the mean.
What happens in reality is of course much, much more subtle.
The popular one.
xD
Lets say the total amount of RAM in your cluster is X. Depending on the average usage in your farm, you might still be able to assign 2X to your virtual machines because the average usage for a machine is 50% or lower.
On a network segment with one gateway and ten endpoints, all nodes can see ten other nodes... except the gateway, which can see more nodes outside the segment. The average is therefore higher than ten, so most nodes see less than the average.
Hrm, I'm not sure if that clears it up at all. Maybe :)