Um Algoritmo Paralelo Eficiente para Cálculo de Centralidade em Grafos
Resumo
Estudos em áreas tão diversas quanto sistemas de comunicação, Internet e Web, computação móvel, sistemas biológicos, redes sociais e redes de transporte, dentre outras, apresentam em comum o fato de que todos esses sistemas podem ser modelados por grafos. A quantidade de elementos participantes nessas redes complexas tem alcançado escalas cada vez maiores, o que requer o uso de processamento paralelo para a análise dos grafos. Neste artigo apresentamos um novo algoritmo paralelo para o cálculo exato de centralidades em grafos grandes, usando o paradigma de programação MapReduce/Hadoop. O objetivo é computar as distâncias entre os vértices e extrair medidas de centralidades decorrentes dessas distâncias, fazendo uso eficiente dos recursos computacionais. Para avaliar o algoritmo proposto foram processados diversos grafos e os resultados comparados com algoritmos sequenciais e paralelos. Os experimentos mostraram que o algoritmo proposto faz uso eficiente da memória e do espaço em disco, comparado à outras implementações.
Palavras-chave:
processamento paralelo, grafos, redes complexas
Referências
R. Bryant, “Data-intensive scalable computing for scientific applications,” Computing in Science & Engineering, vol. 13, no. 6, pp. 25–33, Nov.-Dec. 2011.
L. C. Freeman, “Centrality in social networks conceptual clarification,” Social Networks, vol. 1, no. 3, pp. 215 – 239, 1979.
U. Kang, S. Papadimitriou, J. Sun, and H. Tong, “Centralities in large networks: Algorithms and observations,” in SIAM International Conference on Data Mining. SIAM / Omnipress, Apr 2011b, pp. 119–130.
U. Kang, C. E. Tsourakakis, A. P. Appel, C. Faloutsos, and J. Leskovec, “Hadi: Mining radii of large graphs,” ACM Trans. Knowl. Discov. Data, vol. 5, no. 2, pp. 8:1–8:24, Feb 2011a.
J. P. B. Nascimento and C. D. Murta, “Um Algoritmo Paralelo para Cálculo de Centralidade em Grafos Grandes,” in Anais do XXX SBRC, 2012, pp. 393–406.
J. P. B. Nascimento, “Um Algoritmo Paralelo para Cálculo de Centralidade em Grafos Grandes,” Master’s thesis, PPGMMC, CEFET-MG, 2011.
J. Lin and M. Schatz, “Design patterns for efficient graph algorithms in MapReduce,” in Proceedings of the Eighth Workshop on Mining and Learning with Graphs, ser. MLG ’10. ACM, 2010, pp. 78–85.
J. Dean and S. Ghemawat, “MapReduce: Simplified data processing on large clusters,” in USENIX Association Proceedings of the Sixth Symposium on Operating Systems Design and Implementation (OSDE‘04). USENIX ASSOC, 2004, pp. 137–149.
——, “Mapreduce: simplified data processing on large clusters,” Commun. ACM, vol. 51, no. 1, pp. 107–113, Jan 2008.
H. Karloff, S. Suri, and S. Vassilvitskii, “A model of computation for MapReduce,” in Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, ser. SODA’10. Society for Industrial and Applied Mathematics, 2010, pp. 938–948.
S. N. Srirama, P. Jakovits, and E. Vainikko, “Adapting scientific computing problems to clouds using MapReduce,” Future Gener. Comput. Syst., vol. 28, no. 1, pp. 184–192, Jan 2012.
J. Cohen, “Graph Twiddling in a MapReduce World,” Computing in Science & Engineering, vol. 11, no. 4, pp. 29–41, Jul-Aug 2009.
L. Page, S. Brin, R. Motwani, and T. Winograd, “The pagerank citation ranking: Bringing order to the web.” Stanford InfoLab, Technical Report 1999-66, November 1999.
P. Flajolet and G. N. Martin, “Probabilistic counting algorithms for data base applications,” J. Comput. Syst. Sci., vol. 31, no. 2, pp. 182–209, Sep. 1985.
A. A. Hagberg, D. A. Schult, and P. J. Swart, “Exploring network structure, dynamics, and function using NetworkX,” in Proceedings of the 7th Python in Science Conference (SciPy2008), Aug. 2008, pp. 11–15.
M. R. S. Gonçalves, J. N. Maciel, and C. D. Murta, “Geração de Topologias da Internet por Redução do Grafo Original.” in Anais do XXVIII SBRC, 2010, pp. 959–972.
L. C. da Cruz, “Um Algoritmo Paralelo Eficiente para Cálculo de Centralidade em Grafos,” Master’s thesis, PPGMMC, CEFET-MG, 2013.
L. C. Freeman, “Centrality in social networks conceptual clarification,” Social Networks, vol. 1, no. 3, pp. 215 – 239, 1979.
U. Kang, S. Papadimitriou, J. Sun, and H. Tong, “Centralities in large networks: Algorithms and observations,” in SIAM International Conference on Data Mining. SIAM / Omnipress, Apr 2011b, pp. 119–130.
U. Kang, C. E. Tsourakakis, A. P. Appel, C. Faloutsos, and J. Leskovec, “Hadi: Mining radii of large graphs,” ACM Trans. Knowl. Discov. Data, vol. 5, no. 2, pp. 8:1–8:24, Feb 2011a.
J. P. B. Nascimento and C. D. Murta, “Um Algoritmo Paralelo para Cálculo de Centralidade em Grafos Grandes,” in Anais do XXX SBRC, 2012, pp. 393–406.
J. P. B. Nascimento, “Um Algoritmo Paralelo para Cálculo de Centralidade em Grafos Grandes,” Master’s thesis, PPGMMC, CEFET-MG, 2011.
J. Lin and M. Schatz, “Design patterns for efficient graph algorithms in MapReduce,” in Proceedings of the Eighth Workshop on Mining and Learning with Graphs, ser. MLG ’10. ACM, 2010, pp. 78–85.
J. Dean and S. Ghemawat, “MapReduce: Simplified data processing on large clusters,” in USENIX Association Proceedings of the Sixth Symposium on Operating Systems Design and Implementation (OSDE‘04). USENIX ASSOC, 2004, pp. 137–149.
——, “Mapreduce: simplified data processing on large clusters,” Commun. ACM, vol. 51, no. 1, pp. 107–113, Jan 2008.
H. Karloff, S. Suri, and S. Vassilvitskii, “A model of computation for MapReduce,” in Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, ser. SODA’10. Society for Industrial and Applied Mathematics, 2010, pp. 938–948.
S. N. Srirama, P. Jakovits, and E. Vainikko, “Adapting scientific computing problems to clouds using MapReduce,” Future Gener. Comput. Syst., vol. 28, no. 1, pp. 184–192, Jan 2012.
J. Cohen, “Graph Twiddling in a MapReduce World,” Computing in Science & Engineering, vol. 11, no. 4, pp. 29–41, Jul-Aug 2009.
L. Page, S. Brin, R. Motwani, and T. Winograd, “The pagerank citation ranking: Bringing order to the web.” Stanford InfoLab, Technical Report 1999-66, November 1999.
P. Flajolet and G. N. Martin, “Probabilistic counting algorithms for data base applications,” J. Comput. Syst. Sci., vol. 31, no. 2, pp. 182–209, Sep. 1985.
A. A. Hagberg, D. A. Schult, and P. J. Swart, “Exploring network structure, dynamics, and function using NetworkX,” in Proceedings of the 7th Python in Science Conference (SciPy2008), Aug. 2008, pp. 11–15.
M. R. S. Gonçalves, J. N. Maciel, and C. D. Murta, “Geração de Topologias da Internet por Redução do Grafo Original.” in Anais do XXVIII SBRC, 2010, pp. 959–972.
L. C. da Cruz, “Um Algoritmo Paralelo Eficiente para Cálculo de Centralidade em Grafos,” Master’s thesis, PPGMMC, CEFET-MG, 2013.
Publicado
23/10/2013
Como Citar
CRUZ, Leonardo Carlos da; MURTA, Cristina Duarte.
Um Algoritmo Paralelo Eficiente para Cálculo de Centralidade em Grafos. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 14. , 2013, Porto de Galinhas.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2013
.
p. 3-10.
DOI: https://doi.org/10.5753/wscad.2013.16767.
