Analysis of Maximum Flow in Random Graphs for Network Coding
Hongzheng Wang, Pingyi Fan, Zhigang Cao · 2006
Network coding is an essential way to achieve the maximum flow of multicast networks. Recent results have shown that random graph theory has a heuristic role in guiding the construction of network coding. In this paper, we study the distribution of maximum flow in different random graph models. We show that in a n nodes network with sampling probability p the mean of any s-t maximum flow is about (n-1)p-/spl radic/((n-1)pq//spl pi/). In a n nodes random geometric graph, a model for wireless network, we can get similar results as long as the parameter has corresponding value to the one in random graph model. We also show that the changing of connectivity radius would affect the maximum flow significantly.