Um novo modelo para grafos variantes no tempo
Resumo
Nós propomos um novo modelo para grafos variantes no tempo (GVTs), adequados para a representação de redes dinâmicas, por exemplo. Mostramos que o modelo proposto é suficientemente geral para representar vários casos de redes dinâmicas encontrados na literatura recente. Nós também estudamos as estruturas de dados usadas para representação de redes dinâmicas construídas de acordo com nosso modelo. Nós demonstramos ainda que quando os nós do GVT podem ser considerados como nós independentes em cada instante de tempo, o GVT analisado é isomorfo a um grafo estático orientado. Esse é um resultado teórico importante, pois permite a aplicação direta de resultados conhecidos em teoria de grafos orientados ao contexto de redes dinâmicas. Em suma, a contribuição deste artigo situa-se na proposição de um novo modelo para GVTs bem como no embasamento teórico que fundamenta sua generalidade e aplicabilidade.
Referências
Ferreira, A. (2004). Building a reference combinatorial model for MANETs. IEEE Network, 18(5):24–29.
Figueiredo, D., Nain, P., Ribeiro, B., de Souza e Silva, E., e Towsley, D. (2012). Characterizing continuous time random walks on time varying graphs. In ACM SIGMETRICS Performance Evaluation Review, volume 40, page 307.
Graham, R., Knuth, D., e Patashnik, O. (1994). Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, Reading, MA, USA.
Holme, P. (2005). Network reachability of real-world contact sequences. Physical Review E, 71(4):1–8.
Holme, P. e Saramäki, J. (2012). Temporal networks. Physics Reports, 519(3):97–125.
Kempe, D., Kleinberg, J., e Kumar, A. (2002). Connectivity and Inference Problems for Temporal Networks. Journal of Computer and System Sciences, 64(4):820–842.
Kim, H. e Anderson, R. (2012). Temporal node centrality in complex networks. Physical Review E, 85(2):026107.
Kostakos, V. (2009). Temporal graphs. Physica A: Statistical Mechanics and its Applications, 388(6):1007–1023.
Leskovec, J., Kleinberg, J., e Faloutsos, C. (2005). Graphs over time. In Proc. of the ACM Int. Conference on Knowledge Discovery in Data Mining (KDD), pages 177–187.
Lund, J. e Bowers, K. (1992). Sinc Methods for Quadrature and Differential Equations. SIAM, Philadelphia, PA, USA.
Nicosia, V., Tang, J., Musolesi, M., Russo, G., Mascolo, C., e Latora, V. (2012). Components in time-varying graphs. Chaos: An Interdisciplinary Journal of Nonlinear Science, 22(2):023101.
Pan, R. e Saramäki, J. (2011). Path lengths, correlations, and centrality in temporal networks. Physical Review E, 84(1):1–10.
Pfitzner, R., Scholtes, I., Tessone, C., Garas, A., e Schweitzer, F. (2012). Time-explicit graphs: A framework for dynamic network analysis. In Summer School for Master and PhD Students on Modeling and Analysis of Novel Mechanisms in Future Internet Applications, Würzburg, Germany.
Sengul, C., Viana, A. C., e Ziviani, A. (2012). A survey of adaptive services to cope with dynamics in wireless self-organizing networks. ACM Computing Surveys, 44(4):23:1–23:35.
Tang, J., Musolesi, M., Mascolo, C., e Latora, V. (2009). Temporal distance metrics for social network analysis. In Proc. of the ACM Workshop on Online Social Networks (WOSN), pages 31–36. ACM Press.
Tang, J., Musolesi, M., Mascolo, C., Latora, V., e Nicosia, V. (2010). Analysing information flows and key mediators through temporal centrality metrics. In Proc. of the Workshop on Social Network Systems (SNS), pages 1–6. ACM Press.
Xuan, B. B., Ferreira, A., e Jarry, A. (2003). Evolving graphs and least cost journeys in dynamic networks. In Proc. of the Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt).
