WikiDegreesOfSeparation

A creation of DanCicio and EvilSouthie in a conversation, WikiDegreesOfSeparation strives to find interesting paths between WikiPages?, based off of the SixDegreesOfKevinBacon? game (alternately, Erdos numbers and PatriNumbers).

Rules

• Don't use CategoryHomePage
• No backlinks
• No RecentChanges
• No WikiDegreesOfSeparation
• No StronglyConnectedComponents

To cheat, go to http://www.cs.hmc.edu/~readams/shortpath.cgi

No longer works. Is it still searching ~mvrable?

A newer, functional version is available [here]

Example

The first use of this was an attempt to link MattBrubeck to BrianRoney.

After a comment that it would go through the MathDepartment, DanCicio came up with: MattBrubeck -> JointMajor -> MathMajor -> MathDepartment -> PreFrosh -> PreFroshWeekend -> JohnWalseth -> SuperSmashBrothers -> BrianRoney

BrianRoney was actually thinking of a different path. Apparently if you contract PreFrosh -> JohnWalseth you get ProfessorLevin. MattBrubeck -> JointMajor -> MathMajor -> MathDepartment -> ProfessorLevin -> SuperSmashBrothers -> BrianRoney

We then came up with: MattBrubeck -> RobAdams -> CurtisVinson -> MasterOfOrionTwo -> BrianRoney.

Then RobAdams automated it and came up with MattBrubeck -> BenZeckel -> MarissaAnderson -> BrianRoney.

To get back, however, all that's needed is BrianRoney -> ChessersTournament -> CurtisVinson -> MattBrubeck.

The longest shortest path

OK, there was some difficulty in determining this, but thanks to EvilSouthie I found the bug in my longest shortest path searcher. The actual, official longest shortest path, as of Sun 9/22/02, is:

Length 13: PaperClipDelusion -> StephGrush -> ProgMetal -> BenZeckel -> JessicaFisher -> AndrewSchoonmaker -> FilkSong -> BestShmackEver -> MoreBestSchmackEver -> MuddHole -> PizzaPlace -> FoodPlace -> SleazyBurger -> BoysenberryShake

To generate, go to http://www.cs.hmc.edu/~readams/longshortpath.cgi. Not necessary since it won't give you updated results, since it draws from a static database periodically synced to the Wiki database.

--RobAdams

More graph fun

If anyone wants to do some serious analysis of the FunWiki link graph, run FunWiki:action=links&exists=1 for an adjacency list. Each line starts with the name of a page, followed by the links it contains (warning: slow and CPU-intensive, do not overuse). Go to MeatBall:LinkDatabase and MeatBall:IndexingScheme for more possibilities.

Interesting facts about the FunWiki graph:

• There is more than one non-trivial component. That is, the graph of all of the WikiNodes? on FunWiki is not connected. Further, more than one non-trivial component exists (non-trivial: not an isolated vertex/node).
• RobAdams wrote a script to find the StronglyConnectedComponents of the directed link graph.
• RobAdams wrote a script to find WikiIslands in the directed link graph.

I've tried a couple of the MeatBall:IndexingScheme scripts on FunWiki. For a start, here are the Shortest Path Pages, [with] and [without] homepages included (Curtis is indeed near the top). This script could easily be modified to find all-pairs shortest paths in the directed wiki graph, which would be a quick (if cheesy) way to answer some of the questions on this page.

If you want a new challenge that's not as susceptible to automation, try finding the LongestPath on FunWiki...

• Presumably you mean longest acyclic path...-ChainMaille