Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Graph Theory, Perl, and the Six Degrees of Wikipedia

by Starky (Chaplain)
on May 28, 2008 at 03:34 UTC ( [id://688797]=CUFP: print w/replies, xml ) Need Help??

Having done some work using Perl for optimization experiments on graphs back in the day, I was intrigued to read that Stephen Nolan at Trinity College Dublin recently conducted a graph-theoretic analysis of the number of links required to get from any Wikipedia article to any other. The results are quite interesting.

As you might expect since you're reading it here, he mentions in his posting that he wrote the code in Perl.

Replies are listed 'Best First'.
Re: Graph Theory, Perl, and the Six Degrees of Wikipedia (fun paths)
by tye (Sage) on May 28, 2008 at 06:32 UTC

    I enjoyed looking at how things get connected. Some queries were rather boring, just routing through shared dates (or, worse, years), like the first one below. Some were quite funny.

    Shortest path from Great Wall of China to Larry Wall is 3 clicks:
    Great Wall of China -> April 19 -> 1949 -> Larry Wall

    Shortest path from Larry Wall to Great Wall of China is 3 clicks:
    Larry Wall -> Christianity -> Attila the Hun -> Great Wall of China

    Shortest path from Perl to Great Wall of China is 3 clicks:
    Perl -> Bioinformatics -> Evolution -> Great Wall of China

    Shortest path from Perl to Carnegie Hall is 3 clicks:
    Perl -> American National Standards Institute -> New York City -> Carnegie Hall

    Shortest path from Perl to Python is 3 clicks:
    Perl -> C (programming language) -> Buffer overflow -> Python

    Shortest path from Python to Perl is 2 clicks:
    Python -> Monty Python -> Perl

    Shortest path from Perl to Bowler hat is 3 clicks:
    Perl -> Latin -> The Adventures of Tintin -> Bowler hat

    Shortest path from Perl to Pineapple is 3 clicks:
    Perl -> Golf -> Mexico -> Pineapple

    Shortest path from Perl to Athlete's foot is 3 clicks:
    Perl -> 1987 -> Dougie Poynter -> Athlete's foot

    Shortest path from Perl to Potted meat is 5 clicks:
    Perl -> APL (programming language) -> 1964 -> Hedda Hopper -> Treet -> Potted meat food product

    Shortest path from Perl Monks to Potted meat is 5 clicks:
    Perl Monks -> Slashdot -> South Park -> 58th Primetime Emmy Awards -> List of Camp Lazlo episodes -> Potted meat food product

    I'll just let you enjoy that tableau without further comment, so you can enjoy your own interpretations of the results (of speculation at why I came up with those specific end-points).

    - tye        

      Oh yeah, great fun... and some paths are quite convincing:

      Shortest path from Perl to Kidney is 2 clicks:
      Perl > Camel > Kidney

      Shortest path from Perl to Spam is 3 clicks:
      Perl > BASIC > Bill Gates > Spam

      Shortest path from Perl to Onion is 3 clicks:
      Perl > Camel > Taboo food and drink > Onion

      Shortest path from Perl to Chaos is 3 clicks:
      Perl > Usenet > Duke University > Chaos

      --shmem

      _($_=" "x(1<<5)."?\n".q·/)Oo.  G°\        /
                                    /\_¯/(q    /
      ----------------------------  \__(m.====·.(_("always off the crowd"))."·
      ");sub _{s./.($e="'Itrs `mnsgdq Gdbj O`qkdq")=~y/"-y/#-z/;$e.e && print}

        Hahaha

        Shortest path from Perlmonks to Conan the Barbarian: 4 clicks needed

        Perl Monks > Computer programming > Buffer overflow > OpenBSD > Conan the Barbarian

        LOL

        mwa

        perl to heaven Perl > Gospel of Matthew > Death and resurrection of Jesus > Heaven

      Interesting

      Perl to Sex 2 clicks

      Perl -> Usenet -> Sex

      but Sex to Perl is 3

      Sex -> Hetrosexuality -> H2g2 -> Perl

      Strange easier going than coming!

      Finding interesting paths not through dates or lists is difficult. It would be interesting to develop some heuristic for eliminating them (maybe links per volume?) and do so. I think, at least, it would increase the humor per attempt when searching between random things.

Re: Graph Theory, Perl, and the Six Degrees of Wikipedia
by Tux (Canon) on May 29, 2008 at 07:57 UTC

    Great fun indeed.

    #!/pro/bin/perl use strict; use warnings; use LWP::Simple; use HTML::TreeBuilder; my ($from, $to) = @ARGV; my $route = get "http://www.netsoc.tcd.ie/~mu/cgi-bin/shortpath.cgi?fr +om=$from&to=$to" or exit; my $tree = HTML::TreeBuilder->new; $tree->parse_content ($route); print $_->as_text, "\n" for $tree->look_down (_tag => qr{^(?:h[12]|a)$ +});
    $ wikigraph.pl here eternity Shortest path from here to eternity Here Here (comic) Time Eternity 3 clicks needed $ wikigraph.pl cradle grave Shortest path from cradle to grave Cradle Mobile phone South Africa Hyena Grave 4 clicks needed $

    Enjoy, Have FUN! H.Merijn
Re: Graph Theory, Perl, and the Six Degrees of Wikipedia
by moritz (Cardinal) on May 28, 2008 at 09:14 UTC
    A friend of mine asked what the longest path was, so I tried to search for long pathes. 5 clicks is as far as I got, but I didn't really try sparsely linked articles.

    So if anyone found a path with at least 6 clicks, please let me know. I promise a beer (or comparable beverage) at our next real-life meeting for the first to find a 8 click path ;-)

      Try from Clabony to Relocker ;-)

      --shmem

      _($_=" "x(1<<5)."?\n".q·/)Oo.  G°\        /
                                    /\_¯/(q    /
      ----------------------------  \__(m.====·.(_("always off the crowd"))."·
      ");sub _{s./.($e="'Itrs `mnsgdq Gdbj O`qkdq")=~y/"-y/#-z/;$e.e && print}

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: CUFP [id://688797]
Approved by kyle
Front-paged by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others having a coffee break in the Monastery: (5)
As of 2024-03-29 06:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found