Detecting Global Efficiency in Complex Networks Using Local Measurements and Neighborhood Information
Resumo
Modelos de redes complexas são encontradas em uma ampla gama de aplicações, desde redes em ambientes biológicos e sociais até ambientes tecnológicos. A sua natureza intrinsecamente dinâmica é resultado de características de autonomia e ubiquidade. Desta forma, avaliar o seu comportamento face a falhas e ataques é relevante para definir mecanismos de controle e recuperação. No entanto, aspectos práticos tornam métricas globais não mensuráveis. Além disso, as métricas locais não são adequadas para lidar com propriedades globais. Neste trabalho, apresentamos uma nova métrica local para detectar mudanças globais em redes complexas considerando o conceito de informação da vizinhança. Os resultados mostram que a métrica proposta obteve resultados satisfatórios para redes livres-de-escala, mundo-pequeno e aleatória.Referências
Albert, R. and Barabasi, A. L. (2002). Statistical mechanics of complex networks. Reviews of Modern Physics, 74(1).
Albert, R., Jeong, H., and Barabasi, A.-L. (2000). Error and attack tolerance of complex networks. Nature, 406(6794):378–382.
Almaas, E. and Barabasi, A. (2004). Power laws in biological networks. q-bio.
Biskupski, B., Dowling, J., and Sacha, J. (2007). Properties and mechanisms of self-organizing manet and p2p systems. ACM Trans. Auton. Adapt. Syst., 2(1).
Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., and Wiener, J. (2000). Graph structure in the web. Computer Networks, 33(1):309–320.
Crucitti, P. and Latora, V. (2001). Efficient behavior of small-world networks. Physical Review Letters, 87(19):198701+.
Crucitti, P., Latora, V., Marchiori, M., and Rapisarda, A. (2004). Error and attack tolerance of complex networks. Physica A: Statistical Mechanics and its Applications, 340:Pages 388–394.
Dall’Asta, L., Barrat, A., Barthelemy, M., and Vespignani, A. (2006). Vulnerability of weighted networks. Theory and Experiment, 2006:04006.
Dodds, P. S., Muhamad, R., and Watts, D. J. (2003). An experimental study of search in global social networks. Science, 301(5634):827–829.
Erdős, P. and Rényi, A. (1959). On random graphs. Publicationes Mathematicae Debrecen, 6:290–297.
Erdős, P. and Rényi, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5:17–61.
Faloutsos, M., Faloutsos, P., and Faloutsos, C. (1999). On power-law relationships of the internet topology. In In SIGCOMM, pages 251–262.
Holl, J. and H, M. S. (2003). An assessment of preferential attachment as a mechanism for human sexual network formation.
Klemm, K. and Eguíluz, V. (2002). Growing scale-free networks with small world behavior. Phys Rev E, (65).
Latora, V. and Marchiori, M. (2002). Economic small-world behavior in weighted networks.
Lua, K., Crowcroft, J., Pias, M., Sharma, R., and Lim, S. (2005). A survey and comparison of peer-to-peer overlay network schemes. Communications Surveys & Tutorials, IEEE, pages 72–93.
Newman, M. E. J. (2003). The structure and function of complex networks.
Stephenson (1989). Rethinking centrality: Methods and applications. Social Networks, 11:1–37.
Vega-Redondo, F. (2007). Complex Social Network. Cambridge University Press.
Wasserman, S., Faust, K., and Iacobucci, D. (1994). Social Network Analysis : Methods and Applications (Structural Analysis in the Social Sciences). Cambridge University Press.
Watts, D. J. (2003). Small Worlds : The Dynamics of Networks between Order and Randomness (Princeton Studies in Complexity). Princeton University Press.
Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of ’small-world’ networks. Nature, 393(6684):440–442.
Wuchty, S. (2003). Small worlds in rna structures. Nucl. Acids Res., 31:1108–1117.
Albert, R., Jeong, H., and Barabasi, A.-L. (2000). Error and attack tolerance of complex networks. Nature, 406(6794):378–382.
Almaas, E. and Barabasi, A. (2004). Power laws in biological networks. q-bio.
Biskupski, B., Dowling, J., and Sacha, J. (2007). Properties and mechanisms of self-organizing manet and p2p systems. ACM Trans. Auton. Adapt. Syst., 2(1).
Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., and Wiener, J. (2000). Graph structure in the web. Computer Networks, 33(1):309–320.
Crucitti, P. and Latora, V. (2001). Efficient behavior of small-world networks. Physical Review Letters, 87(19):198701+.
Crucitti, P., Latora, V., Marchiori, M., and Rapisarda, A. (2004). Error and attack tolerance of complex networks. Physica A: Statistical Mechanics and its Applications, 340:Pages 388–394.
Dall’Asta, L., Barrat, A., Barthelemy, M., and Vespignani, A. (2006). Vulnerability of weighted networks. Theory and Experiment, 2006:04006.
Dodds, P. S., Muhamad, R., and Watts, D. J. (2003). An experimental study of search in global social networks. Science, 301(5634):827–829.
Erdős, P. and Rényi, A. (1959). On random graphs. Publicationes Mathematicae Debrecen, 6:290–297.
Erdős, P. and Rényi, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5:17–61.
Faloutsos, M., Faloutsos, P., and Faloutsos, C. (1999). On power-law relationships of the internet topology. In In SIGCOMM, pages 251–262.
Holl, J. and H, M. S. (2003). An assessment of preferential attachment as a mechanism for human sexual network formation.
Klemm, K. and Eguíluz, V. (2002). Growing scale-free networks with small world behavior. Phys Rev E, (65).
Latora, V. and Marchiori, M. (2002). Economic small-world behavior in weighted networks.
Lua, K., Crowcroft, J., Pias, M., Sharma, R., and Lim, S. (2005). A survey and comparison of peer-to-peer overlay network schemes. Communications Surveys & Tutorials, IEEE, pages 72–93.
Newman, M. E. J. (2003). The structure and function of complex networks.
Stephenson (1989). Rethinking centrality: Methods and applications. Social Networks, 11:1–37.
Vega-Redondo, F. (2007). Complex Social Network. Cambridge University Press.
Wasserman, S., Faust, K., and Iacobucci, D. (1994). Social Network Analysis : Methods and Applications (Structural Analysis in the Social Sciences). Cambridge University Press.
Watts, D. J. (2003). Small Worlds : The Dynamics of Networks between Order and Randomness (Princeton Studies in Complexity). Princeton University Press.
Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of ’small-world’ networks. Nature, 393(6684):440–442.
Wuchty, S. (2003). Small worlds in rna structures. Nucl. Acids Res., 31:1108–1117.
Publicado
20/07/2009
Como Citar
GHEDINI, Cinara Guellner; RIBEIRO, Carlos H. C..
Detecting Global Efficiency in Complex Networks Using Local Measurements and Neighborhood Information. In: WORKSHOP EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO (WPERFORMANCE), 8. , 2009, Bento Gonçalves/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2009
.
p. 2209-2223.
ISSN 2595-6167.
