Medidas de conectividade baseadas em cortes de vértices para redes complexas
Resumo
Neste trabalho apresentamos medidas de conectividade para redes complexas. Essas medidas identificam os nodos importantes em uma rede de acordo com a conectividade dos mesmos em relação aos demais nodos. Mostramos como calcular o valor da medida que chamamos de vértice-conectividade e que denotamos por κ(v). Relacionamos o valor da vértice-conectividade com outras medidas como grau de intermediação, closeness, excentricidade, grau e medidas baseadas em cortes de arestas. Analisamos as medidas em casos extremos e em redes sintéticas aleatórias.
Referências
Albert, R., Barabási, A. L., and Jeong, H. (2000). Scale-free characteristics of random networks: The topology of the world wide web. Physica A, 281.
Albert, R., Jeong, H., and Barabási, A. L. (1999). The diameter of the world wide web. Nature, 401.
Balthrop, J., Forrest, S., Newman, M. E. J., and Williamson, M. M. (2004). Technological networks and the spread of computer viruses. Science, 304.
Barabási, A. L. (2003). Linked: How Everything Is Connected to Everything Else and What It Means. Plume.
Cohen, J., Schroeder, J., and Duarte Jr., E. P. (2011). Connectivity criteria for ranking network nodes. Communications in Computer and Information Science (CCIS) - aceito para publicação.
Costa, L. F., Rodrigues, F. A., Travieso, G., and Boas, P. R. V. (2006). Characterization of complex networks: A survey of measurements. Advances in Physics, 56(1).
Echenique, P., Gómez-Gardeñes, J., and Moreno, Y. (2005). Dynamics of jamming transitions in complex networks. EPL (Europhysics Letters), 71(2).
Faloutsos, M., Faloutsos, P., and Faloutsos, C. (1999). On power-law relationships of the internet topology. In Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, volume 29 of SIGCOMM ’99.
Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 40.
Hage, P. (1995). Eccentricity and centrality in networks. Social Networks, 17.
Korte, B. and Vygen, J. (2002). Combinatorial Optimization: Theory and Algorithms. Springer, 2nd edition.
Leskovec, J., Huttenlocher, D., and Kleinberg, J. (2010). Signed networks in social media. Proceedings of the 28th international conference on Human factors in computing systems.
Liljeros, F., Edling, C. R., Amaral, L. A., Stanley, E. H., and åberg Y. (2001). The web of human sexual contacts. Nature, 411.
Duarte Jr., E. P., Santini, R., and Cohen, J. (2004). Delivering packets during the routing convergence latency interval through highly connected detours. In DSN. IEEE Computer Society.
Nagamochi, H. and Ibaraki, T. (2008). Algorithmic Aspects of Graph Connectivity. Cambridge University Press.
Okamoto, K., Chen, W., and Li, X. (2008). Ranking of closeness centrality for Large-Scale social networks. Frontiers in Algorithmics, 5059.
Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of small-world networks. Nature, 393.
Albert, R., Jeong, H., and Barabási, A. L. (1999). The diameter of the world wide web. Nature, 401.
Balthrop, J., Forrest, S., Newman, M. E. J., and Williamson, M. M. (2004). Technological networks and the spread of computer viruses. Science, 304.
Barabási, A. L. (2003). Linked: How Everything Is Connected to Everything Else and What It Means. Plume.
Cohen, J., Schroeder, J., and Duarte Jr., E. P. (2011). Connectivity criteria for ranking network nodes. Communications in Computer and Information Science (CCIS) - aceito para publicação.
Costa, L. F., Rodrigues, F. A., Travieso, G., and Boas, P. R. V. (2006). Characterization of complex networks: A survey of measurements. Advances in Physics, 56(1).
Echenique, P., Gómez-Gardeñes, J., and Moreno, Y. (2005). Dynamics of jamming transitions in complex networks. EPL (Europhysics Letters), 71(2).
Faloutsos, M., Faloutsos, P., and Faloutsos, C. (1999). On power-law relationships of the internet topology. In Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, volume 29 of SIGCOMM ’99.
Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 40.
Hage, P. (1995). Eccentricity and centrality in networks. Social Networks, 17.
Korte, B. and Vygen, J. (2002). Combinatorial Optimization: Theory and Algorithms. Springer, 2nd edition.
Leskovec, J., Huttenlocher, D., and Kleinberg, J. (2010). Signed networks in social media. Proceedings of the 28th international conference on Human factors in computing systems.
Liljeros, F., Edling, C. R., Amaral, L. A., Stanley, E. H., and åberg Y. (2001). The web of human sexual contacts. Nature, 411.
Duarte Jr., E. P., Santini, R., and Cohen, J. (2004). Delivering packets during the routing convergence latency interval through highly connected detours. In DSN. IEEE Computer Society.
Nagamochi, H. and Ibaraki, T. (2008). Algorithmic Aspects of Graph Connectivity. Cambridge University Press.
Okamoto, K., Chen, W., and Li, X. (2008). Ranking of closeness centrality for Large-Scale social networks. Frontiers in Algorithmics, 5059.
Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of small-world networks. Nature, 393.
Publicado
30/05/2011
Como Citar
PIRES, Karine; COHEN, Jaime; DUARTE JR., Elias P..
Medidas de conectividade baseadas em cortes de vértices para redes complexas. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 12. , 2011, Campo Grande/MS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2011
.
p. 77-89.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2011.23091.
