Scratch

Well, it's certainly a very interesting problem 

I don't know how much computation you need; I'm not sure what algorithm one uses. I think this might be called the "all-pairs shortest path problem", from a little Wikipediaring: finding the shortest path between every pair of nodes in a graph, where the nodes are people and edges represent "friend" relationships. I suppose it's also a directed graph, (as I understand it) because you can add me as a friend without me "friending" you.

Somehow I imagine that you might end up downloading all the friend lists for each user. After all, if it's true that any two people are separated at most by six degrees of separation, finding your friends's friends to six degrees would include everyone! 

I'd definitely ask the ST first...    Or maybe just download the data very slowly, over a long period of time?

Hardmath123 wrote:

I want to try to set up a shared computing system...

Again, this depends on the algorithms you use and how they work — but I'm not sure it'll be very easy to parallelise.

The analysis sounds fascinating if you can do it, and a JS visualiser sounds cool! 

Last edited by blob8108 (2012-09-08 11:42:07)

Hardmath123 wrote:

There are 354,694 Scratchers with projects, so...

xD

How much of a hit is each API request, performance-wise? (download size, response time)

Interesting idea!  Can you break it up so that you are only pulling data for a limited amount of people at a run?  And maybe run it in the off- hours?

Paddle2See wrote:

Interesting idea!  Can you break it up so that you are only pulling data for a limited amount of people at a run?  And maybe run it in the off- hours?

Sure, I'm thinking about how to break up data downloads, and how to minimize it, and implementing small measures such that friends of a user are only downloaded once and only if the user had created projects.

But I'll have to do it for all Scratchers, even those whom haven't been friended by anyone else. It's simpler to go recursively, looking at my friends, then their friends, and so on. We will have to store the crunched Scratchers on a server so that all participating computers know what has been done. In the end, simply put, I want every Scratcher's friends list. I can then work with that offline.

A thing to note: there are over 1 million Scratchers. Let's say there are 1,500,000 to be conservative. Each has an average of say 30 friends. Each friend id is about 6 characters. So we have to in total download about 260MB of data.

EDIT: I take that back... maybe it is better to just brute-force through all Scratchers... 

EDIT2: I'd like to get the collection done by the end of October. So let's try to get a basic shared computing system and all that stuff ready by September 20th and then get the actual downloading done over the next 2 months. That gives us 25,000 Scratchers per day, which implies under 1 Scratcher per second running 24x7. Obviously that's impractical for just me, so we should aim for 10 volunteers, so each volunteer has to get 100,000 Scratchers in 2 months, implying around two every 3 minutes, a much more realistic estimate. So, who'd like to volunteer?

Last edited by Hardmath123 (2012-09-09 06:35:10)

bobbybee wrote:

I'll volunteer, and I 'might' put it on my server that I run 24/7.

Thanks! I think all the server needs to do is accept a one-line message and write it to a text file which I can download later.

blob8108 wrote:

If you're using Python, definitely have a look at using:
* Twisted: great for networking! Seriously, you don't want to do stuff without it. Deferreds take a bit of getting used to.
* the multiprocessing module: lets you split tasks across multiple cores. Normal Python threads don't work properly (read about the GIL)
* Stackless Python.

Stackless is really cool — it lets you run hundreds/thousands of lightweight micro-threads, called "tasklets". It implements co-operative multitasking: periodically call stackless.schedule() from each tasklet to yield to the others. It has channels to communicate between tasklets. They're also pickleable, so I think you can pause a running tasklet (ie. a Python function), save it to a string/file, send it across the network, and then resume it on a different machine!    (I'm sure I managed to make this last one work at least once...)

Stackless might be useful for designing the algorithm to perform the actual computation. You can do things like getting around Python's recursion limit of 1000, and you could have, say, a microthread for each Scratcher and use channels to communicate between them. Or something. It's fun, anyway! 

And there are ways of making Twisted and Stackless play nice, too.

Anyway, have a look and see what you think 

That sounds cool. If there's one thing I never truly understood, it was how to make threading work right (JS is miserable with settimeout). Pickleable threads sound plain awesome.

I got the API-networking-thing working wonderfully with urllib (that's the right way to go, right?), and I can at this point get all the friends of a user, which was my intention all along. I'll most probably assign intervals of 100,000 or so to all volunteers. Maybe if I'm lucky, I can get Paddle to run it on MIT's servers and get it all at once as part of a nightly con job.

Do you think you could run some of the computation for me? Just leave it on overnight and post what you get in the morning.

blob8108 wrote:

which I'm still not convinced of

...now you tell me...

What do you think is the answer to my problem?

Hardmath123 wrote:

Here's what I have:

Just being picky ( ), but I find this more readable:

import urllib

def get_user_by_id(id):
    url = "http://scratch.mit.edu/api/getusernamebyid/"+str(id)
    return urllib.urlopen(url).read().strip()

def get_friends(user):
    url = "http://scratch.mit.edu/api/getfriendsbyusername/"+user
    friends = urllib.urlopen(url).read().strip().split(":")
    return map(get_user_by_id, friends)

get_user_by_id(1)
get_friends("Hardmath123")

You can probably just use strip() to get rid of the whitespace, since spaces aren't valid in usernames or ids.

It does take a worryingly long time -- is there an API method to get friends by user id (or friends as usernames?). At least you only have to lookup the username once for each user id...

I'm going to do all the analysis locally, it's just collection I want to distribute. To be honest, I'm worried about both the server and my computer. It's a tremendous computation. I'll look up th Apis for better friend detection, you're right about it being worryingly long. 

Ask if you can download the friend database. Then you don't have to call their servers. 
I was thinking about this months ago, but i also had the server load worry.

Hardmath123 wrote:

scimonster wrote:

Ask if you can download the friend database. Then you don't have to call their servers. 
I was thinking about this months ago, but i also had the server load worry.

... how did I not think of that?! 

Well, I doubt they'd accept 

What would really be nice is a PHP script to run on the Scratch servers that queried the MySQL databases directly without needing to go through the http server.

Of course, that's nearly as impossible as them giving you the friends databases. Which I frankly don't find very logical since they'd rather you risk slowing down their servers...