Wikipedia

Grafo ponderado

En teoría de grafos, un grafo ponderado, valorado o con pesos es un grafo en el que las aristas tienen un valor o peso asociado.[1]​

Ejemplo de grafo ponderado (no dirigido).

En análisis de redes sociales y ciencia de redes, este tipo de grafos sirven para representar redes sociales o redes complejas con relaciones valoradas.[1]​

Definición formal

editar

Formalmente, un grafo ponderado se puede definir como un trío ordenado  , donde   es su conjunto de vértices,   es su conjunto de aristas, y   es el conjunto de pesos asociados a cada arista.[1]​ Asimismo,   se puede representar también como una función de asignación de pesos  , de modo que para cualquier arista  , su peso es  . Dado que cualquier conjunto finito de valores se puede asociar a un subconjunto de los números reales, las aristas también admiten solo números enteros, o bien valores no numéricos, tales como letras o colores. En redes sociales, es común restringirse a números naturales.[1]​

Por definición, los grafos signados son un caso particular de grafos ponderados, en que los valores válidos para cada arista se reducen a un valor booleano, 0 o 1, o bien -1 o +1. Asimismo, un grafo normal sin valores en las aristas también se puede considerar un caso particular de grafo ponderado, en que todas las aristas tienen un mismo valor 1.[1]​

Análisis de redes ponderadas

editar

Varias métricas para grafos o redes sin aristas valoradas pueden ser adaptadas para grafos ponderados. Por ejemplo, las medidas de centralidad clásicas como el grado,[2]​ cercanía[3]​ o intermediación,[4]​[5]​ también pueden considerar los pesos de las aristas. Asimismo, el coeficiente de agrupamiento global y local también se puede aplicar considerando ternas de valores[6]​[2]​ o fórmulas algebraicas.[7]​ Las trayectorias basadas en la noción de camino también se pueden definir para aristas valoradas, estando bien definidos conceptos de valor y longitud de un camino, así como de accesibilidad entre vértices.[1]​

Una ventaja teórica de los grafos ponderados es que permiten derivar relaciones entre diferentes métricas de la red, también llamados conceptos de red, estadísticos o índices.[8]​ Por ejemplo, simples relaciones entre métricas de la red pueden derivarse a partir de grupos de nodos (comunidades) en las redes ponderadas.[9]​ Para las redes ponderadas de correlación, puede usarse la interpretación angular de las correlaciones para proporcionar una interpretación geométrica de los conceptos teóricos de la red, y derivar relaciones inesperadas entre ellas.[10]​

Aplicaciones

editar

En general, medir o registrar la importancia de los diferentes enlaces, permite crear grafos ponderados que capturan más información que los grafos sin pesos.[11]​

Redes sociales y redes complejas

editar
Artículos principales: Red social y Red compleja.

En redes del mundo real, no siempre todos los vínculos tienen la misma importancia o capacidad. En muchos casos, se les asocia a los vínculos un valor que los diferencia en términos de fuerza, intensidad o capacidad.[2]​[8]​

Acerca de las redes sociales, Mark Granovetter argumentó en 1973 que la importancia de las relaciones es función de su duración, intensidad emocional, intimidad e intercambio de servicios.[12]​ En el análisis de redes sociales, el concepto de camino de nivel c se utiliza para estudiar subgrupos cohesivos para grafos ponderados.[1]​

Para otros tipos de redes complejas, con frecuencia los pesos refieren a la función que cumplen los vínculos. Ejemplos de esto son diferentes valores de flujos de carbono (mg / m² / día) entre especies en las redes alimentarias,[13]​ la cantidad de sinapsis y las uniones de brechas en redes neuronales,[14]​ o la cantidad de tráfico vehicular a lo largo de las conexiones en redes de transporte.[15]​

Las redes ponderadas también se usan ampliamente en aplicaciones genómicas y de sistemas biológicos.[8]​ Por ejemplo, el análisis de redes ponderadas de coexpresión de genes (WGCNA, por sus siglas en inglés) se usa a menudo para construir una red entre diferentes genes o productos genéticos, basados en datos de expresión de genes como micromatrices.[7]​ De manera más general, pueden definirse otras redes ponderadas de correlación a partir de determinar un umbral entre pares entre variables, como activación de distintas partes del cerebro o expresión de diferentes genes).[16]​

Cadenas de Márkov

editar
Artículo principal: Cadena de Márkov
 
Ejemplo de una cadena de Márkov.

En teoría de la probabilidad, los grafos ponderados pueden restringirse a valores de probabilidades entre 0 y 1, esto es, funciones de pesos  , para representar procesos estocásticos conocidos como cadenas de Márkov. En estos grafos, además, la suma de los pesos incidentes desde cada nodo suman 1.[1]​ A las sociomatrices o matrices de adyacencia de dichos grafos se les conoce como matriz de transiciones o matrices estocásticas.[17]​

Software para analizar redes ponderadas

editar

Existe un gran número de paquetes de software que pueden usarse para analizar redes ponderadas. Entre estos se encuentran el software propietario UCINET y el paquete de código abierto tnet.[18]​ El paquete de R, WGCNA,[19]​ implementa funciones para construir y analizar redes ponderadas, particularmente redes de correlación.[16]​ En general, la gran mayoría de herramientas para análisis de redes sociales permiten trabajar con grafos ponderados.

Véase también

editar

Referencias

editar
  1. ↑ a b c d e f g h Wasserman y Faust, 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.
  2. ↑ a b c Barrat, A.; Barthelemy, M.; Pastor-Satorras, R.; Vespignani, A. (2004). «The architecture of complex weighted networks». Proceedings of the National Academy of Sciences 101 (11): 3747-3752. Bibcode:2004PNAS..101.3747B. PMC 374315. PMID 15007165. arXiv:cond-mat/0311416. doi:10.1073/pnas.0400087101. 
  3. ↑ Newman, M. E. J. (2001). «Scientific collaboration networks: II. Shortest paths, weighted networks, and centrality». Physical Review E 64 (1): 016132. Bibcode:2001PhRvE..64a6132N. PMID 11461356. arXiv:cond-mat/0011144. doi:10.1103/PhysRevE.64.016132. 
  4. ↑ Brandes, U. (2008). «On variants of shortest-path betweenness centrality and their generic computation». Social Networks 30 (2): 136-145. doi:10.1016/j.socnet.2007.11.001. 
  5. ↑ Opsahl, T. «Betweenness in wighted networks» (en inglés). Consultado el 2 de mayo de 2021. 
  6. ↑ Opsahl, T.; Panzarasa, P. (2009). «Clustering in Weighted Networks». Social Networks 31 (2): 155-163. doi:10.1016/j.socnet.2009.02.002. 
  7. ↑ a b Zhang, B.; Horvath, S. (2005). «A general framework for weighted gene co-expression network analysis». Statistical Applications in Genetics and Molecular Biology 4: Article17. PMID 16646834. doi:10.2202/1544-6115.1128. 
  8. ↑ a b c Horvath, S. (2011). Weighted Network Analysis. Applications in Genomics and Systems Biology. Springer Book. ISBN 978-1-4419-8818-8. 
  9. ↑ Dong, J.; Horvath, S. (2007). «Understanding Network Concepts in Modules». BMC Systems Biology 1 (24). doi:10.1186/1752-0509-1-24. 
  10. ↑ Dong, J.; Horvath, S. (2008). «Geometric interpretation of gene coexpression network analysis». PLoS Computational Biology 4 (8): e1000117. Bibcode:2008PLSCB...4E0117H. PMC 2446438. PMID 18704157. doi:10.1371/journal.pcbi.1000117. 
  11. ↑ Opsahl, T. (6 de febrero de 2009). «Operationalisation of tie strength in social networks» (en inglés). Consultado el 2 de mayo de 2021. 
  12. ↑ Granovetter, M. (1973). «The strength of weak ties». American Journal of Sociology 78 (6): 1360-1380. doi:10.1086/225469. 
  13. ↑ Luczkowich, J.J.; Borgatti, S.P.; Johnson, J.C.; Everett, M.G. (2003). «Defining and measuring trophic role similarity in food webs using regular equivalence». Journal of Theoretical Biology 220 (3): 303-321. PMID 12468282. doi:10.1006/jtbi.2003.3147. 
  14. ↑ Watts, D. J.; Strogatz, S. (1998). «Collective dynamics of 'small-world' networks». Nature 393 (6684): 440-442. Bibcode:1998Natur.393..440W. PMID 9623998. doi:10.1038/30918. 
  15. ↑ Opsahl, T.; Colizza, V.; Panzarasa, P.; Ramasco, J. J. (2008). «Prominence and control: The weighted rich-club effect». Physical Review Letters 101 (16): 168702. Bibcode:2008PhRvL.101p8702O. PMID 18999722. arXiv:0804.0417. doi:10.1103/PhysRevLett.101.168702. 
  16. ↑ a b Langfelder, Peter; Horvath, Steve (2008). «WGCNA: an R package for weighted correlation network analysis». BMC Bioinformatics 9: 559. PMC 2631488. PMID 19114008. doi:10.1186/1471-2105-9-559. 
  17. ↑ Harary, F. (1959). «Graph theoretic methods in the management sciences». Management Science 5. pp. 387-403. doi:10.1287/mnsc.5.4.387. 
  18. ↑ Opsahl, T. «tnet». Consultado el 2 de mayo de 2021. 
  19. ↑ «WGCNA: Weighted Correlation Network Analysis». Consultado el 2 de mayo de 2021. 

Bibliografía

editar
  • Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053. 
Obtenido de «https://es.wikipedia.org/w/index.php?title=Grafo_ponderado&oldid=147921228»