Caracterização da distribuição de carga em redes complexas submetidas a um tráfego uniforme

• Elias Bareinboim UFRJ
• Valmir C. Barbosa UFRJ

Resumo

A carga de um nó em uma rede é o tráfego total passando atavés dele. Nós expressamos a carga do nó em termos de uma noção mais elementar de descendência em árvores de busca em largura, e estudamos as distribuições da descendência e da carga do nó no caso de redes scale-free. Nosso resultado principal é que a distribuição da carga, mesmo podendo ser obtida como uma power-law através da aplicação sútil (mas inapropriada) de binning sobre os dados brutos, é na verdade uma sucessão de picos de probabilidades bem delineados, cada um podendo ser interpretado como uma função da descendência BFS subjacente. Tal descoberta encontra-se em oposição direta a crença previamente estabelecida, baseada na qual uma power-law com expoente −2.2 foi conjecturada como valida independente do expoente da distribuição da power-law para os graus dos vértices.

Referências

E. Bareinboim and V. C. Barbosa, Phys. Rev. E 77, 046111 (2008).

P. Erdős and A. Rényi, Publ. Math. 6, 290 (1959).

S. Bornholdt and H. G. Schuster, eds., Handbook of Graphs and Networks (Wiley-VCH, Weinheim, Germany, 2003).

M. Newman, A.-L. Barabási, and D. J. Watts, eds., The Structure and Dynamics of Networks (Princeton University Press, Princeton, NJ, 2006).

K.-I. Goh, B. Kahng, and D. Kim, Phys. Rev. Lett. 87, 278701 (2001).

M. Barthélemy, Phys. Rev. Lett. 91, 189803 (2003).

K.-I. Goh, C.-M. Ghim, B. Kahng, and D. Kim, Phys. Rev. Lett. 91, 189804 (2003).

A. O. Stauffer and V. C. Barbosa, IEEE ACM T. Network. 15, 425 (2007).

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (The MIT Press, Cambridge, MA, 2001), 2nd ed.

M. E. J. Newman, in Complex Networks, edited by E. Ben-Naim, H. Frauenfelder, and Z. Toroczkai (Springer, Berlin, Germany, 2004), pp. 337–370.

M. E. J. Newman and M. Girvan, Phys. Rev. E 69, 026113 (2004).

D. Aldous, in Microsurveys in Discrete Probability, edited by D. Aldous and J. Propp (American Mathematical Society, Providence, RI, 1998), pp. 1–20.

V. C. Barbosa, R. Donangelo, and S. R. Souza, Phys. A 321, 381 (2003).

D. Achlioptas, A. Clauset, D. Kempe, and C. Moore, in Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing (ACM Press, New York, NY, 2005), pp. 694–703.

E. Bareinboim, Master’s thesis, Systems Engineering and Computer Science Program, Federal University of Rio de Janeiro, Rio de Janeiro, Brazil (2007), in Portuguese.

A. Clauset, C. R. Shalizi, and M. E. J. Newman, Power-law distributions in empirical data (2007), URL [link].