? ?

Previous Entry | Next Entry

Blow your mind

Consider the various people on your friends list. Now assign each one of them a point in space in your mind, like you are hanging stars in the sky. Put yourself in the sky as well, and draw a line between yourself and each one of your friends.

Do any of those friends know each other? If they do, draw lines between them.

Now do the same thing for each person on your friends list. There will be some new names that come up. Do the same process for them, and keep going until you reach the absolute end of all possible livejournal users that you connect with (which is a finite number equal to or less than the total number of livejournal users).

Consider this your "network" of livejournal users. If the image in your head could keep up with the connections, congratulations-- you should now have a 3-D virtual image of a sort of starfield in your head. Consider that image as the map of your network.

Your job, should you decide to accept it, is fourfold:

Task 1: design a program that will determine the shortest route between any two livejournal users in your network.

Task 2: Using that program, design a program that will model the path that a meme generated by any livejournal user is likely to propogate along, assuming that the shortest path is the most likely.
Display the results as a 3-D image on the computer screen.

Task 3: Add an option to the shortest-path algorithm you designed (Task 1 above) to take into account whether any individual user is currently online. If they aren't, you can't connect through them.

Task 4: Add an option that will allow you to display only those friends that you can reach within some number of links.

Feels like finals week.


( 1 comment — Leave a comment )
Jan. 20th, 2004 07:46 am (UTC)
This is a lovely graph theory problem. Task 1 has been solved. (And in fact I used this algorithm when I was a systems engineer to change a "let it run overnight" simulation to a "it's done in literally less than a second" simulation, making my boss very happy.

Task 2: I would allow one to WEIGHT the edges. In other words, if user "Ilovemycat" is very likely to pass on a meme, and user "cockmonkey" tends not to pass them on, the likely propogating path will be the one going through "Ilovemycat" even if the SHORTEST path goes through "cockmonkey"

Task 3: Cool

Task 5: I'd then add, of course, a number that gives your mean distance between any livejournal user - your "Kevin Bacon" number as it were.
( 1 comment — Leave a comment )

Latest Month

April 2012


Page Summary

Powered by
Designed by Tiffany Chow