Putting the magic in the machine since 1980.

Thursday, June 14, 2012

Constructive Network Formation Models

Gary Fredericks recently presented a poster at AAMAS on our recent work on An Analysis of Constructive Network Formation Models.

This is really interesting theoretical work where we are looking at the possible topologies that can emerge given initial payment rules. For example, given a bunch of disconnected nodes (think ISPs before buying access to any other ISP, or businesses before establishing relationships with any other, etc.) and a rule that says that any link between two nodes has a fixed cost which must be paid by the two nodes in questions, but where everyone benefits from being closer (fewer edges between them) to everyone else, what kind of topologies will we expect to emerge if we let all agents build edges as they see fit?

We examine this problem in part by building graphs of graphs. That is, we built directed graphs, such as the one you see here, that show the possible evolution of these networks over time. From these we can then determine which topologies, or which features (small-world, small-diameter, etc.) are more likely given different initial rules of the game (equal payment for edge, one must pay, auctions, etc.)