9 ms·
Friendship Paradox
- murbard2 12y agoThis is established by making a one-step random walk in the friendship graph. 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.
- gertef 12y ago> 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. And this was the foundation of Google's PageRank. http://en.wikipedia.org/wiki/Google_matrix http://en.wikipedia.org/wiki/Google_matrix
- murbard2 12y agoIndeed. However, it's easy to miss the "random-walk" aspect of pagerank if one simply think of it as a recursive relation between inbound and outbound links. Once you think "random-walk" you can build a whole class of "intentional surfer" model which model surfers seeking particular information.
- jiggy2011 12y agoI wonder if this can be exploited for business networking purposes. Simply choose a person in your "network" and ask them to introduce you to one other person they know and repeat with the new person.
- jgmmo 12y agoLike Conspire? https://www.goconspire.com/welcome https://www.goconspire.com/welcome
- jiggy2011 12y agoThat seems too planned, it assumes you have a specific person in mind. What I mean is asking for random introductions until you meet someone influential.
- jdmichal 12y agoI wonder whether people would tend to introduce you more influential friends, over less influential friends, as a kind of status display. You could potentially "climb" faster than a random walk would.
- lsc 12y agoAll of the guided "ask X to introduce you to Y" systems that I have seen are... poorly implemented. The thing is, asking for an intro is complex; it depends on your relationship with the person doing the introduction, and with their relationship with the end target, and with how beneficial the potential relationship between the introduced parties is perceived to be. 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.
- randomwalker 12y agoSocial graphs are not fast mixing. This used to be widely assumed but recent empirical measurements have refuted the assumption. [1] If I recall correctly, random walks tend to get stuck in cities and other highly-dense subgraphs. Six degrees of separation refers to shortest paths, and fast mixing is decidedly _not_ the intuition behind it. [1] http://syssec.kaist.ac.kr/~yongdaek/doc/imc2010.pdf http://syssec.kaist.ac.kr/~yongdaek/doc/imc2010.pdf
- murbard2 12y agoInteresting, I've played with the SNAP datasets and did find very high eigenvalues, but I attributed it to the graphs bring a partial snapshot. You're right, 6 degrees of separation is a statement about diameter, but a small diameter and mixing speed are related.
- murbard2 12y agoSo what do you make of the papers such as SybilLimit[1] or SybilInfer[2] which rely on a fast-mixing assumption? They do seem to claim good empirical results on actual social graphs... [1] https://www.comp.nus.edu.sg/~yuhf/yuh-sybillimit.pdf https://www.comp.nus.edu.sg/~yuhf/yuh-sybillimit.pdf [2] http://www.internetsociety.org/sites/default/files/dane.pdf 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.
- randomwalker 12y agoNo. None of the graphs they use are ego-nets. That would be methodologically ridiculous, as you point out. 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/interaction-eurosys09.pdf https://www.cs.ucsb.edu/~ravenben/publications/pdf/interacti... [2] http://www.cs.utexas.edu/users/lorenzo/papers/Alvisi13SoK.pdf http://www.cs.utexas.edu/users/lorenzo/papers/Alvisi13SoK.pd... [3] http://www.cs.utexas.edu/users/lorenzo/papers/Alvisi14Communities.pdf http://www.cs.utexas.edu/users/lorenzo/papers/Alvisi14Commun...
- comrade1 12y agoThis is not that different than the slut paradox. Most people are having less sex than the people they're having sex with, mostly because of a fair number of super-sluts (male and female) that have sex with a large number of people. edit: clarification: I'm one of those super-sluts.
- comrade1 12y agoShould I have used the phrase super-fecund instead of the word 'slut'? Actually, with birth control we fool our bodies into thinking that we're mating so fecundity doesn't apply I guess.
- arjie 12y ago'Promiscuity' is a term that is less loaded. Anyway, your observation is in the lede in the article, so it's likely the combination of language and lack of new information that sunk your earlier comment.
- tbrownaw 12y agoIf you drop the needless pejorative language, you get the observation from the second paragraph of the article...
- andrey-p 12y agoThat's actually quite depressing. "You are always surrounded by people who are more popular than you."
- kull 12y ago98% of the time to be more specific
- Groxx 12y agoOn Twitter. I think we can safely assume Twitter is an extreme example.
- deleted 12y ago[deleted]
- kstenerud 12y agoActually, I prefer it that way. Let other people deal with the hassle of dealing with people. My greatest fear is discovering too late that something I'm doing will make me famous.
- cyorir 12y agoAlso depressing are some of the corollaries that have cropped up. "On average, you are surrounded by people who are more successful than you." "On average, your (sexual) partners have more partners than you."
- zpem 12y ago"Hacker News"
- eric_h 12y ago"On-Topic: Anything that good hackers would find interesting. That includes more than hacking and startups. If you had to reduce it to a sentence, the answer might be: anything that gratifies one's intellectual curiosity."[1] [1] https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- arjie 12y agoRead the article and you'll find that this is an interesting observation that has current relevance (the Ebola outbreak).
- jiggy2011 12y agoThis might explain why introverts tend to think that everyone else is more extrovert than them, there's probably a lot more introverts than we realise but we're just less likely to meet them.
- jokoon 12y agoI'm not sure, but my intuition tells me there's half introverts, half extraverts. (introversion/extraversion is a spectrum).
- lifeisstillgood 12y agoAnd you are thus less likely to be friends with an introvert than an extrovert.
- dredwerker 12y agoIts not just your intuiton the bell curve tops outs squarely in the middle of the two not with two nice peaks. I found this out looking in to Myers briggs(I think its very qustionable). People can never work out whether I am introvert or extrovert.
- cm127 12y agoBut that's the point... It's a continuous distribution meaning you probably fluctuate between introvert and extravert very smoothly with most of the population within the standard deviation. There will probably always be people that stay at the tail ends, but it's not average.
- GregorStocks 12y agoThe shape of the distribution affects the value of the introvert/extrovert distinction pretty strongly, though. If it's strongly bimodal (so a random extrovert is very different from a random introvert), then it says a lot, while if it's unimodal with a small variance (so a random extrovert is only a little more extroverted than a random introvert) it doesn't say much.
- mariusz79 12y agoOh, so now I know why I have no friends.. Someone must be at the very bottom of this pyramid. :)
- exo762 12y agoI can be your friend. The popular one. xD
- pizza 12y agoGood article by Strogatz, with clear explanation: http://opinionator.blogs.nytimes.com/2012/09/17/friends-you-can-count-on/ http://opinionator.blogs.nytimes.com/2012/09/17/friends-you-...
- clairity 12y agoyay for strogatz! he was one of my favorite math profs in school because he really knew how to explain counter-intuitive phenomena like this.
- gitonup 12y agoHead Squeeze did a bit on this a while ago, as applied to Twitter: https://www.youtube.com/watch?v=Z_15zbgNpHk https://www.youtube.com/watch?v=Z_15zbgNpHk
- andrewstuart2 12y agoI may be oversimplifying, but thinking of it at this extreme helped me intuit a bit better. 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.
- visakanv 12y agoAn excellent way of thinking about it.
- Paul_S 12y agoCan you really have more than 1 or 2 friends? You only have two kidneys and a friend is someone you'd be willing to give a kidney to (compatibility aside).
- mehrdada 12y agoYes. You can oversubscribe your friends to your kidneys. You just have to be willing to give them, but that does not need to actually happen. You'll be fine as long as you pick your friends wisely.
- Turibur 12y agoThink of it as a farm of virtual machines. 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.
- goblin89 12y agoThis is a fun property of scale-free networks in general (https://en.wikipedia.org/wiki/Scale-free_network https://en.wikipedia.org/wiki/Scale-free_network).
- dangayle 12y agoI've never heard this before. It kinda hurts my brain a little to think about.
- vacri 12y agoIf you think about it like a computer network, most nodes have fewer neighbours than their neighbour nodes. Most nodes are endpoints with only a few neighbours, but some nodes are networking midpoints with a lot of neighbours, and every endpoint knows at least one midpoint. 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 :)
- dangayle 12y agoThat makes good sense. Yeah, thanks for clearing that up
- sjwright 12y agoAn even simpler explanation: 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.
- _RPM 12y agoI don't have any friends, am I excluded?
- sjwright 12y agoNo, you're just a divide-by-zero error.
- taliesinb 12y agoWhen I was working on http://blog.stephenwolfram.com/2013/04/data-science-of-the-facebook-world/ http://blog.stephenwolfram.com/2013/04/data-science-of-the-f..., a lot of bizarre results (such as a huge gender difference in number-of-friends for people older than 40) went away after I took into account the friendship paradox. It would be really interesting to revisit that anomaly and try to explain why.
- sjwright 12y agoAnother simple explanation: 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.
- cJ0th 12y agoI don't think it is a paradox when you look at it from a "better" perspective. Just plot a graph displaying the frequency people have x friends. Chances are, there are some outliers with enormous amounts of friends who thus push the average. 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.