ecl@ahutb.UUCP (ecl) (03/09/85)
The recent "small world" postings reminded me that this sort of thing runs in my father's family: My parents' landlord in Miami in 1944 was my father's brother's next-door neighbor in Dayton in 1970. A friend of my father's (from when they were stationed together in Iceland in 1953) was one of my high school teachers in Chicopee (Massachusetts) in 1964. A close friend of my mother's (from pre-1950 in New York City) was called back from retirement to work on a project for IBM in Florida this year. One of her co-workers (also called back from retirement)? My father's brother-in-law. It's getting downright spooky! Evelyn C. Leeper Note temporary kluge for new address => ...{ihnp4, houxm, hocsj}!ahuta!ahutb!ecl
bulko@ut-sally.UUCP (William C. Bulko) (03/14/85)
[ bug off! ] I remember reading an article a looooong time ago, in which a mathematician (discussing probability) stated that you could connect any two people in the United States by a string of no more than 5 people 95% of the time. By "connected", he meant connected to another person by at least being reasonably well acquainted. For example, I could (by this theory) be "connected" to Dan Rather because my father's neighbor's sister-in-law's dentist is Dan Rather's neighbor's grandson, or something like that. (And 19 out of 20 times -- 95% -- you could find a string like that.) Does anyone remember reading this and can quote the source? I always wondered how this mathematician arrived at his numbers. . . -- _______________________________________________________________________________ "To err is human; to admit it is not." Bill Bulko Department of Computer Sciences The University of Texas {ihnp4,harvard,gatech,ctvax,seismo}!ut-sally!bulko _______________________________________________________________________________
davet@oakhill.UUCP (Dave Trissel) (03/17/85)
In article <1308@ut-sally.UUCP> bulko@ut-sally.UUCP (William C. Bulko) writes: >I remember reading an article a looooong time ago, in which a mathematician >(discussing probability) stated that you could connect any two people in >the United States by a string of no more than 5 people 95% of the time. Its not that suprizing once you realize how quickly power series grow. You remember the old "one seed on the first square, two on the second" of the chess board. Then think of 20 people knowing 20 people knowing... However, what IS suprizing is that people find the links out at all. For example one posting here told about a someone's landlord from 1940 connected to a father's brother's neighbor. Obviously last names may prompt questions "Gee I knew a [whatsit] back in Ohio" "Wow, my father's from Ohio" etc. But think how often the following conversation doesn't occur - "When I was stationed in Iceland..." "Wow, my father was too!!!" Notice that if the subject had never been brought up (by a schoolteacher) it is highly unlikely that the connection would otherwise ever been made. Lets make real use of the net and do an experiment. The BOZO experiement. I know a girl here in Austin who had a close friend whose parent played the original BOZO the Clown. (I think it was a parent relationship but I'm not sure now.) Anyway, anyone knowing anyone who knows anyone etc. who has any claim to knowing this fellow please post so. It will be fun to see just how many (if any) people have connections to him. By the way, I don't know who or where he is and thats not important to the experiment even though it would be interesting to find out. Lets here from you BOZO knowers! Dave Trissel {seismo,gatech,ihnp4}!ut-sally!oakhill
ndiamond@watdaisy.UUCP (Norman Diamond) (03/18/85)
> I remember reading an article a looooong time ago, in which a mathematician > (discussing probability) stated that you could connect any two people in > the United States by a string of no more than 5 people 95% of the time. I've also heard it said for strings of 3. I've also heard it said for the WORLD by strings of 3. I'm more inclined to believe the United States by strings of 3, because I heard that in the United States, and we all know how they cannot distinguish between the United States and the World (except sometimes when the USSR is involved). -- Norman Diamond UUCP: {decvax|utzoo|ihnp4|allegra}!watmath!watdaisy!ndiamond CSNET: ndiamond%watdaisy@waterloo.csnet ARPA: ndiamond%watdaisy%waterloo.csnet@csnet-relay.arpa "Opinions are those of the keyboard, and do not reflect on me or higher-ups."
gino@voder.UUCP (Gino Bloch) (03/18/85)
[ bug off! ] { I concur } > I remember reading an article a looooong time ago, in which a mathematician > (discussing probability) stated that you could connect any two people in > the United States by a string of no more than 5 people 95% of the time. > By "connected", he meant connected to another person by at least being > reasonably well acquainted. For example, I could (by this theory) be > "connected" to Dan Rather because my father's neighbor's sister-in-law's > dentist is Dan Rather's neighbor's grandson, or something like that. (And > 19 out of 20 times -- 95% -- you could find a string like that.) Does > anyone remember reading this and can quote the source? > > I always wondered how this mathematician arrived at his numbers. . . It was an experiment. A number of people were told that their goal was to reach some famous person by mail. They were to start by sending a letter to someone they knew that they thought a likely person to have a connection. Each such recipient was given the same instruction. It turned out that the average number of letters was five. No theory here, it was measured. There was a report in Scientific American's "Mathematical Games" column, obviously therefore before Hofstadter, but I don't know the date. To clarify: each subject was given the name of a specific famous person, eg "Jacques, I'd like you to reach Henry Mancini". (In fact I wouldn't bet money on "before Hofstadter"). -- Gene E. Bloch (...!{ucbvax, ihnp4!nsc, decwrl!nsc}!voder!gino) The accidents expressed above are opinions.
jaw@ames.UUCP (James A. Woods) (03/19/85)
# Resist specialization. The connection concept is an common lllustration of the "reflexive transitive closure" graph/matrix operation arising in the study of LALR parsing lookahead sets. Translation: the Unix 'yacc' program probably computed this type of closure when building the C compiler. I assume that a variant of the technique is used by 'pathalias' to construct minimal mail paths, only with transition probablities assigned to each graph arc. It's best to consult a standard text on formal languages such as Aho/Hopcroft/Ullman for definitions. It has been surmised that the closure of the world is around seven, if handshakes are taken as the metric. I'd guess that closure of this net is less than that, as all roads seemingly lead to 'ihnp4' -- ask down!honey. One can imagine extensions into the "fuzzy" domain to categorize more informal relation types. Somehow I doubt that the Bureau of the Census keeps this kind of data, though it would be a boon to conspiracy theorists. Other "applications": If you've ever wondered about the origins of your junk mail, you can compute a rough "closure" by salting surname spelling variants into magazine subscriptions/mailing lists. And, if you want to optimize your success with chain mail or pyramid schemes, pick victims who have low closure (i.e. many connections). This is just common sense, really. Oh, and don't forget the immortal "How to be your own grandfather" puzzle, popularized by Mark Twain, wherein the establishment of this non-intuitive kinship shown to be physically possible. -- James A. Woods {ihnp4,hplabs}!ames!jaw
bobd@zaphod.UUCP (Bob Dalgleish) (03/19/85)
> > I remember reading an article a looooong time ago, in which a mathematician > (discussing probability) stated that you could connect any two people in > the United States by a string of no more than 5 people 95% of the time. > By "connected", he meant connected to another person by at least being > reasonably well acquainted. ... > > Bill Bulko {ihnp4,harvard,gatech,ctvax,seismo}!ut-sally!bulko Actually, it wasn't a mathematician, it was a social psychologist by the name of Millikan. He ran a series of experiments, and found the 95% result. I think he also ran a similar series and showed the same level of confidence for contacting anybody in the world in 10 people or fewer. The actual reference can be found in an introductory social-psych text. Millikan is most famous for his experiment in torture: he showed that 9 people out of 10 (or some such) would apply dangerous levels of voltage to a subject (shill) when the experimenter and/or other shills applied social pressure. This is the one quoted in intro psych classes. -- [The opinions expressed here are only loosely based on the facts] Bob Dalgleish ...!alberta!sask!zaphod!bobd ihnp4! (My company has disclaimed any knowledge of me and whatever I might say)
barry@ames.UUCP (Kenn Barry) (03/22/85)
> Millikan is most famous for his experiment in torture: he showed that 9 > people out of 10 (or some such) would apply dangerous levels of voltage > to a subject (shill) when the experimenter and/or other shills applied > social pressure. This is the one quoted in intro psych classes. Small correction: the psychologist in question is named Stanley Milgram, I believe.
see1@sphinx.UChicago.UUCP (ellen keyne seebacher) (03/22/85)
Millikan? I don't know who did the string-of-5/3/whatever work, but the man who ran the shock experiments was Stanley MILGRAM. Check those introductory social-psych texts... -- ellen keyne seebacher ...ihnp4!gargoyle!sphinx!see1 university of chicago computation center "...and to my Democratic precinct (x9.xes@UChicago.Mailnet) captain, I leave my vote."
honey@down.FUN (code 101) (03/24/85)
pathalias does not use floyd/warshall's closed semi-ring algorithm, it uses johnson's variant of dijkstra's algorithm. i have described the algorithm in net.mail in the recent past; read the code for details. suffice it to say the the asymptotic time complexity is O(v log v), assuming the graph is sparse. peter