5 ms·

This 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 lon

This 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 ago
  Indeed. 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 ago
I 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 ago
  Like Conspire? https://www.goconspire.com/welcome https://www.goconspire.com/welcome
  - jiggy2011 12y ago
    That 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 ago
  I 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 ago
    All 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.
- dangayle 12y ago
  Isn't that what LinkedIn does?
  - dangayle 12y ago
    Who downvoted this? This is exactly what LinkedIn does. You ask to be connected to a third party through one of your pre-existing connections. If you get connected to someone with a huge network, you can then connect with even more people without jumping through LinkedIn's hoops, or paying for their service.
- autokad 12y ago
  i dont see how that would introduce you to someone influential. yes, someone influential is 6 degrees away from someone you know, but there are like 5 billion people in those 6 degrees. 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.
- VLM 12y ago
  "for business networking purposes" 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.
randomwalker 12y ago
Social 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 ago
  Interesting, 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 ago
  So 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 ago
    No. 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...

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 ago
Indeed. 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 ago

I 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 ago
Like Conspire? https://www.goconspire.com/welcome https://www.goconspire.com/welcome
- jiggy2011 12y ago
  That 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 ago
I 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 ago
  All 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.
dangayle 12y ago
Isn't that what LinkedIn does?
- dangayle 12y ago
  Who downvoted this? This is exactly what LinkedIn does. You ask to be connected to a third party through one of your pre-existing connections. If you get connected to someone with a huge network, you can then connect with even more people without jumping through LinkedIn's hoops, or paying for their service.
autokad 12y ago
i dont see how that would introduce you to someone influential. yes, someone influential is 6 degrees away from someone you know, but there are like 5 billion people in those 6 degrees. 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.
VLM 12y ago
"for business networking purposes" 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.

randomwalker 12y ago

Social 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 ago
Interesting, 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 ago
So 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 ago
  No. 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...