  We present a new and efficient algorithm for determining a consensus value
for a network of agents. Different from existing algorithms, our algorithm
evaluates the consensus value for very large networks using heat kernel
pagerank. We consider two frameworks for the consensus problem, a weighted
average consensus among all agents, and consensus in a leader-following
formation. Using a heat kernel pagerank approximation, we give consensus
algorithms that run in time sublinear in the size of the network, and provide
quantitative analysis of the tradeoff between performance guarantees and error
estimates.
