Good graph traversal algorithm

问题:

Abstract problem : I have a graph of about 250,000 nodes and the average connectivity is around 10. Finding a node's connections is a long process (10 seconds lets say). Saving a node to the database also takes about 10 seconds. I can check if a node is already present in the db very quickly. Allowing concurrency, but not having more than 10 long requests at a time, how would you traverse the graph to gain the highest coverage the quickest.

Concrete problem : I'm trying to scrape a website user pages. To discover new users I'm fetching the friend list from already known users. I've already imported about 10% of the graph but I keep getting stuck in cycles or using too much memory remembering too many nodes.

My current implementation :

def run() :
    import_pool = ThreadPool(10)
    user_pool = ThreadPool(1)
    do_user("arcaneCoder", import_pool, user_pool)

def do_user(user, import_pool, user_pool) :
    id = user
    alias = models.Alias.get(id)

    # if its been updates in the last 7 days
    if alias and alias.modified + datetime.timedelta(days=7) > datetime.datetime.now() :
        sys.stderr.write("Skipping: %s\n" % user)
    else :
        sys.stderr.write("Importing: %s\n" % user)
        while import_pool.num_jobs() > 20 :
            print "Too many queued jobs, sleeping"
            time.sleep(15)

        import_pool.add_job(alias_view.import_id, [id], lambda rv : sys.stderr.write("Done Importing %s\n" % user))

    sys.stderr.write("Crawling: %s\n" % user)
    users = crawl(id, 5)
    if len(users) >= 2 :
        for user in random.sample(users, 2) :
            if (user_pool.num_jobs() < 100) :
                user_pool.add_job(do_user, [user, import_pool, user_pool])

def crawl(id, limit=50) :
    '''returns the first 'limit' friends of a user'''
    *not relevant*

Problems of current implementation :

• Gets stuck in cliques that I've already imported, thereby wasting time and the importing threads are idle.
• Will add more as they get pointed out.

So, marginal improvments are welcome, as well as full rewrites. Thanks!

回答1:

To remember IDs of the users you've already visited, you need a map of a length of 250,000 integers. That's far from "too much". Just maintain such a map and only traverse through the edges that lead to the already undiscovered users, adding them to that map at the point of finding such edge.

As far I can see, you're close to implement Breadth-first search (BFS). Check google about the details of this algorithm. And, of course, do not forget about mutexes -- you'll need them.

回答2:

I am really confused as to why it takes 10 seconds to add a node to the DB. That sounds like a problem. What database are you using? Do you have severe platform restrictions?

With modern systems, and their oodles of memory, I would recommend a nice simple cache of some kind. You should be able to create a very quick cache of user information that would allow you to avoid repeated work. When you have encountered a node already, stop processing. This will avoid cycling forever in cliques.

If you need to allow for rehashing existing nodes after a while, you can use a last_visit_number which would be a global value in the dB. If the node has that number, then this crawl is the one that encountered it. If you want to automatically revisit any nodes, you just need to bump the last_visit_number before starting the crawl.

By your description, I am not quite sure how you are getting stuck.

Edit ------ I just noticed you had a concrete question. In order to increase how quickly you pull in new data, I would keep track of the number of times a given user was linked to in your data (imported or not yet imported). When choosing a user to crawl, I would pick users that have a low number of links. I would specifically go for either the lowest number of links or a random choice among the users with the lowest number of links.

Jacob

回答3:

There is no particular algorithm that will help you optimise the construction of a graph from scratch. One way or another, you are going to have to visit each node at least once. Whether you do this depth first or breadth first is irrelevant from a speed perspective. Theran correctly points out in a comment below that breadth-first search, by exploring nearer nodes first, may give you a more useful graph immediately, before the whole graph is completed; this may or may not be a concern for you. He also notes that the neatest version of depth-first search is implemented using recursion, which could potentially be a problem for you. Note that recursion is not required, however; you can add incompletely explored nodes to a stack and process them linearly if you wish.

If you do a simple existence check for new nodes (O(1) if you use a hash for lookup), then cycles will not be a problem at all. Cycles are only a concern if you do not store the complete graph. You can optimise searches through the graph, but the construction step itself will always take linear time.

I agree with other posters that the size of your graph should not be a problem. 250,000 is not very large!

Regarding concurrent execution; the graph is updated by all threads, so it needs to be a synchronised data structure. Since this is Python, you can make use of the Queue module to store new links still to be processed by your threads.

回答4:

Although you say that getting a friend list takes a lot of time (10 seconds or more), a variant of good-old Dijkstra's algorithm just might work:

1. Get any node.
2. Get a connection from any node you already loaded.
3. If the other end hasn't been loaded yet, add the node to the graph.
4. Go to step 2.

The trick is to select the connection you load in step 2 in a smart way. A few short remarks about this:

• You should somehow prevent the same connection to be loaded twice or more often. Selecting a random connection and discard it if it's been loaded already is very inefficient if you're after all connections.
• If you want to load all connections eventually, load all connections of a node at the same time.

In order to really say something about efficiency, please provide more details about datastructure.