It's definately exponential, even if you just consider network traffic.

Let me paint a strawman to burn...

The network topology, as it exists, is largely random.  A full client is expected to have at least 8 active connections, although three would suffice for the health of the network and only one works for the node itself.  Many can, and do, have more connections than 8.  Many of the 'fallback' nodes have hundreds, perhaps thousands, of connections.  So here is the problem; when a block is found, it's in every honest nodes' own interest that said block propagates to the edges of the network as quickly as possible.  A recently as last year, it wouldn't normally take more than 10 seconds to saturate the network, but Satoshi chose a 10 minute interval, in part, to reduce the number of network splits and orphaned blocks due to propagation times, because he presumed that the process that nodes go through (verify every transaction, verify the block, broadcast a copy to each peer that does not have it) would grow as blocks became larger.  The verification delays grow exponentially with the number of transactions simply because each node must perform it's own series of checks before forwarding said block. 

Now we get to the traffic problem...

Once the block has been found by a miner, that miner very much wants to send it to every peer he has as quickly as he can.  So he has to upload that block, whatever it's size, at least 8 times because it's impossible that any of his peers already has it.  Then, after each of those peers has performed the checks, he then proceeds to upload that block to all of his peers save one (the one it got it from) because at this point it is very unlikely that any of his other connected peers already has the block.  These nodes also have a vested interest in getting this block out quickly, once they have confirmed it's a valid block, if they are miners themselves because they don't want to end up mining on a minority block.  Thus, as you can see, the largest miners will always form the center of the network, because they all have a vested interest in being very well connected to each other.  So they also have a vested interest in peer connections with other miners of their same caliber, but not so much with the rest of the network, since sending to lesser miners or non-mining full clients will slow down their ability to transmit said block to those peers that increase the odds that said block will be the winner in a blockchain split.  This effect just gets worse as the size of the block increases, no matter how fast the connection that the mining nodes may have.

Well, this process continues across the p2p network until half of the network already has the block, at which point each node, on average, only finds that half of his peers still need the block.  The problem is that, for small miners, the propagation of a block that is not their own offers them somewhat less advantage than it does for the big miners at the center of the network, because those big miners have already been mining against that new block for many milliseconds to several seconds before the marginal miner even received it.  To make matters worse, the marginal miner tends to have a slower connection than the majors.  So even though it's increasingly likely that his peers don't need the block at all; as the size of the block increases, the incentives for the marginal miner to fail to forward that block, or otherwise pretend it doesn't have it, increase at a rate that is greater than linear.  This is actually true for all of the mining nodes, regardless of their position in the network relative to the center, but those who are closest to the center are always those with the greatest incentives to propagate, so the disincentives increase at a rate closer to linear the closer one is in the network to the center.

Now there is a catch, most of the nodes don't know where they are in the network.  It's not that they can't determine this, most owners simply don't bother to figure this out, nor do they deliberately establish peer connections with the centermost nodes.  However, those centermost nodes almost certainly do have favored connections directly to each other, and they were established deliberately by the ownership for these very reasons.