How Small is the World? Socially Speaking

[ygolo]

OK. I should be asleep but I find myself pondering things. But my insomniac brain is working at 1/8 capacity. If that.

So I'll pose the puzzle to you guys and see if I get answers.

Roughly speaking, there are 7 billion people in the world. The way TheStarchDefenders and I figured it, we estimate about 4 trillion relationships (at least acquaintanceship, current or former with people who are still alive) in the world.

Assuming there is nobody who knows nobody, and everyone is connected by at least one "relationship chain" to everyone else. What is the maximum length of the minimum chain between two people? What would you estimate as the average length of the minimum chain between two people?

This is an open form puzzle. Kept a little ambiguous to allow for your own creativity in the actual definition of the puzzle. Feel free to define (or redefine) the puzzle as you deem fit. Just make sure the puzzle is still interesting once defined. My take on this is that it is a fun little "Fermi Problem" with some graph theory thrown in.

 

[Fluffywolf]

Assuming 1 billion people are fairly isolated and the average number of connections per person is 200, then the average length of the chain is probably:

How do you define aquaintences though? I mean, I meet tens, sometimes hundreds of people weekly, who most are aquainted to me, or know me, but I hardly know any one of them. (Due to my work)

Take a huge celebrity for example, a billion people may be aquainted to him, but he isn't aquainted to any of those people.

Anyhow, ignoring those kind of variables, I'd come up with this.

3.000.000.000 x (200 x 0.75) = 450 billion average length. (0.75 is the factor of any new connection leading to a new inner social circle. Assuming ones inner social circle is approximate 1/4 of all of their connections. So there's a 75% chance of a relation jump to lead to new people.)

Assuming that in ideal circumstances, every connection in turn leads to the most ideal fresh supply of new connections with the least amount of possible reconnections until all options are explored:

7.000.000.000 x (200^2) = 280.000.000.000.000 approximate maximum length.


Still, it's all pretty meaningless, no?

 

[Ginkgo]

If someone only has a single relationship, then they break the relationship chain. Seeing as it is a "chain", backpedaling to an individual within the chain so you can deviate into other relationships is moot. A chain must necessarily include only 2 people who have only 1 relationship each. These people serve as points from one end of the chain to the other.

...

I define relationship as 2 people having at least a superficial, but personal correspondence with each other. It's entirely possible that if 2 people are isolated, they are the shortest chain, which consists of a single relationship.

...

...




...

 

[Fluffywolf]

Considering it takes two people to conceive a new one, chances are highly improbably someone has only one relation in this world.

Not impossible, but improbable.

 

[Ginkgo]

3.000.000.000 x (200 x 0.75) = 450 billion average length. (0.75 is the factor of any new connection leading to a new inner social circle. Assuming ones inner social circle is approximate 1/4 of all of their connections. So there's a 75% chance of a relation jump to lead to new people.)

That chain intersects a good number of times...

 

[ygolo]

These are interesting interpretations. But I made some clarifications in the post (well at least I hope it clarified).

Between two people, there can be many different choice of relationship chains. There will be a minimum length one.

Consider all such minimum length chains. What is the maximum length out of these chains? What is the average length of these chains?

Basically I am asking what is the maximum "degree of separation" and average degree of separation?

To put it more colloquially, "How small is the world?" Socially speaking.

Actually that may have been a better title.

 

[Totenkindly]

I'm not even sure where to begin, realistically, to guessing at a chain length. Not only will there be a variable amount of cross-chaining and needless additional looping (where one could take the "long way around" to reach someone else they already know directly), but the probable path will depend on how many connections the individual(s) have and what sort of loops they are integated into. If two particular endpoints fall within a cloud of probable contact, the length will be very short; if one is not integrated into the same basic cloud, the chain could be far longer.

EDIT: Wait, didn't Kevin Bacon already answer this?

 

[ygolo]

I'm not even sure where to begin, realistically, to guessing at a chain length. Not only will there be a variable amount of cross-chaining and needless additional looping (where one could take the "long way around" to reach someone else they already know directly), but the probable path will depend on how many connections the individual(s) have and what sort of loops they are integated into. If two particular endpoints fall within a cloud of probable contact, the length will be very short; if one is not integrated into the same basic cloud, the chain could be far longer.

EDIT: Wait, didn't Kevin Bacon already answer this?

Hmm. Yeah. I think the way I worded it initially made it kind of less interesting. I change the wording.

It is essentially like the Kevin Bacon game, but instead of having acted together, it is having been at least acquainted with each other.

 

[Octarine]

I've never really studied graph or network theory, so I don't really have an answer. There is some interesting info on Wikipedia though:
http://en.wikipedia.org/wiki/Small-world_network

 

[SilkRoad]

I don't have anything very scientific to contribute, but I love degrees of separation, it fascinates me.

I'm not necessarily thinking of proper "relationships", but at least with people having met or being acquainted with each other. On that basis, I've got two or three degrees of separation (through three different people, one of whom is famous herself) to Colonel Gaddaffi, Hitler, and Ali Abdullah Saleh of Yemen. (Two for Hitler and Gaddaffi, and three for Saleh, I think.)

 

[ygolo]

I don't think this is the type of puzzle with "an answer", necessarily. I am interested in how people attack both the average and the maximum. To me they are very different types of problems.

To get people thinking about the maximum length minimal chains between people.

(I will let you double check me)
In a network of 2 people with 1 relationship, the maximum length chain is 1.
In a network of 3 people with 2 relationships, the maximum length chain is 2.
In a network of 3 people with 3 relationships, the maximum length chain is 1.
In a network of 4 people with 3 relationships, the maximum length chain is 3.
In a network of 4 people with 4 relationships, the maximum length chain is 2.
In a network of 4 people with 5 relationships, the maximum length chain is 2.
In a network of 4 people with 6 relationships, the maximum length chain is 1.

In general, in a "path" topology is the worst case for N people with N-1 relationships, with the longest chain, of length N-1, being between the two "ends".
In general, in a "clique" topology, where everyone knows every one, the longest length chain is 1. For N people there needs to be Chose(N,2) relationships for clique. That is N(N-1)/2 relationships.
For 7 billion people, to form a clique would require almost 25*10^18 relationships, far more than the 4 trillion estimate.

So you can bound the length of the maximum minimal path to be between 2 and 7 billion. Not much of a bound.

 

[Such Irony]

Six Degrees of Separation

 

[ygolo]

Six Degrees of Separation

Yeah, I have heard of the idea. But how do they work out 6 on average? ...and what would be the maximum?