Cómo los actores de la red Bollywood revelan la turbulenta historia de la India
La red de vínculos entre los actores que han co-protagonizó en las películas de Bollywood muestra una clara conexión con la historia política y económica de la India, dicen los científicos de la red.
Seis grados de Kevin Bacon es un juego en el que los amantes del cine se retan para encontrar el camino más corto entre un actor arbitrario en Hollywood y el actor conocido Kevin Bacon, usando las películas en las que ambos han protagonizado. La broma es que esto siempre se puede hacer en seis pasos o menos.
Ya en 2008, un grupo de investigadores de la Universidad de Maryland probo sta idea mediante la construcción de una red de vínculos entre los actores de Hollywood a partir de datos de la Internet Movie Database. Para sorpresa de todos, se encontraron con que el actor conectado mejor no era Kevin Bacon, pero William Hurt, un dato que sin duda será de enorme utilidad en concursos de trivia del futuro.
Desde entonces, el estudio de las redes sociales se ha disparado. Pero mientras que los investigadores han utilizado los actores de Hollywood como un caso interesante, han ignorado la mayor red de acción completo.
La industria cinematográfica de la India, a veces llamado Bollywood, es el mayor productor mundial de películas y empequeñece su homóloga americana. Sólo en 2009 se produjo casi 3.000 películas, y la propia industria tanto refleja la cultura de la India y tiene una profunda influencia sobre él. Eso hace que sea un tema interesante para el análisis.
Hoy tenemos sólo un estudio de este tipo gracias a Sarika Jalan en el Instituto Indio de Tecnología de Indore, en India y unos pocos amigos. Estos chicos han extraído varias bases de datos de películas de la India a partir de los últimos 100 años para crear una red global que muestra actores hombres y mujeres que han trabajado juntos en la misma película.
Y su red proporciona una idea fascinante de la naturaleza de la industria cinematográfica de la India y sus vínculos con la cultura india más amplia también. Esto demuestra no sólo cómo las combinaciones de actores han sido particularmente exitosos, sino también la forma en que la industria ha sufrido altibajos en respuesta a las condiciones económicas y sociales más amplias en el país en general.
Jalan y co comienzan analizando las listas de reparto de casi 9.000 películas hechas en Bollywood entre 1913 y 2012. Cada actor es un nodo de esta red, y un enlace se dibuja entre ellos si ambos actuaron en la misma película. Al dividir el espacio de tiempo de cien años en bloques de cinco años, Jalan y co pueden ver cómo esta red ha evolucionado con el tiempo.
Esta red es similar en muchos aspectos a otras redes sociales. Por ejemplo, el número de enlaces por nodo, conocido como su grado, sigue una ley de potencia. En otras palabras, un pequeño número de actores tienen un gran número de enlaces, o un alto grado, mientras que un gran número de actores tienen un grado bajo.
Esto plantea una pregunta interesante: son los actores más conocidos y de mayor éxito también a los individuos en la red más conectados-? Para averiguarlo, Jalan y co manual compilado una lista de los principales actores masculinos y femeninos, elegidos en función de su facturación (si el plomo o no) y el número de premios importantes que habían recibido.
Para su sorpresa, encontraron que los actores principales no son las mejores conectado el. "Los nodos más importantes de la industria, reconocidos como los actores masculinos de plomo, no forman los centros de la red construida, sino que tienen un grado moderado", dicen.
En cambio, los actores mejor conectados resultan ser actores secundarios prominentes que pueden asumir más proyectos en un período de tiempo determinado y por lo tanto terminan colaborando con un gran número de otros actores. Eso es similar a la red de Hollywood, donde los actores de reparto destacados como William Hurt y Kevin Bacon también están mejor conectados que estrellas como Tom Cruise y George Clooney.
Los actores secundarios son una especie de pegamento que hace punto de la red juntos. Esto se refleja en un parámetro llamado intermediación centralidad, que mide qué tan probable es que un nodo se encuentra en el camino más corto entre una parte de la red y otro.
Actores femeninos son ni mucho menos tan destacado en esta red que los hombres. Jalal y sus colegas dicen esta brecha de género refleja una disparidad similar en la sociedad india en su conjunto.
Tal vez el aspecto más interesante de este trabajo es la forma en que la red de Bollywood ha cambiado con el tiempo. En particular, Jalal y co han estudiado la aleatoriedad subyacente en la red y la forma en que ha cambiado.
Dicen que la red se ha convertido en menos aleatoria, con un par de excepciones notables. Entre 1948 y 1952, la red se convirtió en más al azar, probablemente debido a la agitación significativa asociada a la partición en que el país se dividió en dos. Otro período de aumento de la aleatoriedad se produjo entre 1962 y 1965, durante el período de crisis económica, cuando la India estaba en guerra con Pakistán.
Curiosamente, la red también cambió dramáticamente después de 1998, cuando creció rápidamente y se convirtió en más interconectado. Esto es probablemente el resultado de Bollywood convertirse en un fenómeno reconocido en todo el mundo en lugar de sólo uno nacional.
Una pregunta que viene a la mente es si estos estudios de redes revelan el mayor actor de Bollywood en la historia. Jalal y estribillo co de hacer demasiado de esto, pero su punto de datos a Amitabh Bachchan, quien encabeza una serie de listas en términos de importancia.
El actor femenina más significativa es menos claro, aunque Kareena Kapoor y Helen reciben menciones especiales.
Es un trabajo fascinante que proporciona una visión de una de las grandes industrias del mundo.
Ref: arxiv.org/abs/1406.4607 : Uncovering randomness and success in society
Este blog reúne material del curso de posgrado "Análisis de redes sociales" dictado en la Universidad Nacional del Sur (Argentina).
sábado, 28 de junio de 2014
viernes, 27 de junio de 2014
El lado oscuro de las redes sociales: Nepotismo e ineficiencia en el Tribunal de Cuentas español
Solo cinco de los 60 informáticos del Tribunal de Cuentas son especialistas
Un informe critica la ineficiencia del personal para el servicio
José Antonio Hernández - El País
Pleno del Tribunal de Cuentas
El Tribunal de Cuentas, donde casi un centenar de sus 700 empleados son familiares y allegados de altos cargos y de representantes sindicales del organismo, necesita adaptarse a las nuevas tecnologías informáticas. Pero con el personal de que dispone no puede. Un informe del subdirector jefe del servicio central de informática de la Administración del Estado, al que ha tenido acceso EL PAÍS, revela que el 80% de la plantilla de informáticos del Tribunal de Cuentas (60 trabajadores) carece de conocimientos y titulación para afrontar las necesidades del servicio.
Este tribunal es el organismo encargado de fiscalizar a los partidos políticos y al sector público. En los últimos años se le ha cuestionado por su ceguera en casos como el de Bárcenas —que durante 20 años dispuso de una caja b en el PP nutrida con donaciones ilegales—, y porque tarda hasta cinco años en emitir sus informes sobre cómo gastan las administraciones el dinero de las arcas públicas y cómo gestionan los partidos políticos las subvenciones.
Esta carencia de personal informático adecuado (pese a su abultada plantilla de 60 trabajadores) ha obligado reiteradas veces al tribunal a acudir con urgencia a profesionales de la Administración General del Estado para resolver problemas. Y esto ocurre en un Tribunal donde se mueven todos los años cientos de expedientes “con información muy sensible y sujeta al deber de sigilo”, según detalla el informe del subdirector jefe, que además ofrece un dato demoledor: la mayoría de los informáticos solo tiene el graduado escolar o el bachillerato y no conoce más allá del programa Windows. El sueldo de un jefe de equipo de este departamento es superior al de un inspector de Hacienda recién llegado, en torno a 3.000 euros.
RELACIONES FAMILIARES EN EL TRIBUNAL DE CUENTAS.
Este estudio fue elevado el pasado mes de mayo al pleno del Tribunal de Cuentas para que entendiera la situación que existe y la necesidad de profesionalizar el servicio, externalizando una parte o contratando personal cualificado si lo que pretende el tribunal es equiparar su tecnología a la de otras administraciones.
El informe del subdirector jefe analiza la plantilla e indica: “Según esta relación de puestos de trabajo, para formar parte de una unidad informática departamental del tribunal, en el 80% de los puestos [bastó] con tener experiencia en MS-DOS, lo que a día de hoy sería equivalente a Windows, disponer de conocimientos informáticos y saber utilizar Office”.
El informe considera que la preparación de la plantilla es obsoleta, y añade: “Estos conocimientos son inherentes hoy en día al desempeño de cualquier puesto de trabajo en el que se utilice un ordenador personal, por lo que la práctica totalidad de los empleados del tribunal no estarían cualificados para ocupar uno de estos puestos”.
El informe critica que se han dado puestos laborales en el área de informática sin la debida preparación.“Si bien la descripción de los puestos y la formación exigida no corresponde con la necesidades reales de una unidad TIC, tal vez la selección del personal se realizó teniendo estas necesidades en mente y, de alguna manera, fueron ocupadas por personal con formación informática. Sin embargo, un sencillo análisis de la ocupación desmiente esta hipótesis: solo hay cinco personas con estudios de informática o telecomunicaciones entre un total de 60 puestos”.
De estos 60 miembros de la plantilla de informática, a 21 se les asignó la categoría de operador informático. Según el convenio colectivo aprobado entre los sindicatos y los altos cargos del tribunal, para acceder a este puesto solo era necesario tener estudios “de bachillerato, BUP, FP2 o LOGSE”, y alguna “experiencia en el sistema MS-DOS”. Y a otros 19 operarios solo se les exigió, por acuerdo de convenio colectivo, tener la “ESO, el graduado escolar o FP1”. Otra exigencia era tener “experiencia en desempeño de puesto de trabajo similar”. A los programadores informáticos (hay cuatro) les bastó únicamente con acreditar que tenían “experiencia en el sistema operativo MS-DOS”. Los dos jefes de negociado que hay en plantilla solo tuvieron que demostrar “conocimientos de proceso de texto, hoja de cálculo, gestores de datos y entornos ofimáticos”.
Algunos allegados de altos cargos son ahora jefes de equipo. El convenio colectivo del tribunal resta importancia a los estudios a la hora de ascender. Su artículo 6 establece: “Los aspirantes por el turno de promoción interna, excepto para acceder a los grupos 1 [titulados universitarios] y 2, quedarán exentos de reunir el requisito de titulación reseñado anteriormente, siempre y cuando acrediten una experiencia mínima de cinco años de antigüedad en la plantilla”.
Investigación@elpais.es
Un informe critica la ineficiencia del personal para el servicio
José Antonio Hernández - El País
Pleno del Tribunal de Cuentas
El Tribunal de Cuentas, donde casi un centenar de sus 700 empleados son familiares y allegados de altos cargos y de representantes sindicales del organismo, necesita adaptarse a las nuevas tecnologías informáticas. Pero con el personal de que dispone no puede. Un informe del subdirector jefe del servicio central de informática de la Administración del Estado, al que ha tenido acceso EL PAÍS, revela que el 80% de la plantilla de informáticos del Tribunal de Cuentas (60 trabajadores) carece de conocimientos y titulación para afrontar las necesidades del servicio.
Este tribunal es el organismo encargado de fiscalizar a los partidos políticos y al sector público. En los últimos años se le ha cuestionado por su ceguera en casos como el de Bárcenas —que durante 20 años dispuso de una caja b en el PP nutrida con donaciones ilegales—, y porque tarda hasta cinco años en emitir sus informes sobre cómo gastan las administraciones el dinero de las arcas públicas y cómo gestionan los partidos políticos las subvenciones.
Esta carencia de personal informático adecuado (pese a su abultada plantilla de 60 trabajadores) ha obligado reiteradas veces al tribunal a acudir con urgencia a profesionales de la Administración General del Estado para resolver problemas. Y esto ocurre en un Tribunal donde se mueven todos los años cientos de expedientes “con información muy sensible y sujeta al deber de sigilo”, según detalla el informe del subdirector jefe, que además ofrece un dato demoledor: la mayoría de los informáticos solo tiene el graduado escolar o el bachillerato y no conoce más allá del programa Windows. El sueldo de un jefe de equipo de este departamento es superior al de un inspector de Hacienda recién llegado, en torno a 3.000 euros.
RELACIONES FAMILIARES EN EL TRIBUNAL DE CUENTAS.
Este estudio fue elevado el pasado mes de mayo al pleno del Tribunal de Cuentas para que entendiera la situación que existe y la necesidad de profesionalizar el servicio, externalizando una parte o contratando personal cualificado si lo que pretende el tribunal es equiparar su tecnología a la de otras administraciones.
El documento ha sido elevado a la comisión de gobierno del tribunalEl PAÍS publicó el pasado martes que cerca de un centenar de empleados del organismo encargado de fiscalizar las cuentas del Estado son familiares de altos cargos y de representantes sindicales. Muchos de estos familiares accedieron al tribunal tras franquear exámenes, y fueron asignados inicialmente (algunos aún continúan allí) al departamento de informática, como grabadores de datos, pero sin los estudios específicos.
El informe del subdirector jefe analiza la plantilla e indica: “Según esta relación de puestos de trabajo, para formar parte de una unidad informática departamental del tribunal, en el 80% de los puestos [bastó] con tener experiencia en MS-DOS, lo que a día de hoy sería equivalente a Windows, disponer de conocimientos informáticos y saber utilizar Office”.
El informe considera que la preparación de la plantilla es obsoleta, y añade: “Estos conocimientos son inherentes hoy en día al desempeño de cualquier puesto de trabajo en el que se utilice un ordenador personal, por lo que la práctica totalidad de los empleados del tribunal no estarían cualificados para ocupar uno de estos puestos”.
El convenio colectivo facilita los ascensos obviando la titulaciónDestaca que, dadas las necesidades del tribunal, “no parece que baste con saber utilizar un ordenador para prestar los servicios que el tribunal demanda de sus profesionales TIC [Tecnologías de la Información y las Comunicaciones], y mucho menos ante la necesaria implantación de plataformas de administración electrónica que sitúen al Tribunal de Cuentas al nivel de otros órganos como el Tribunal Constitucional o el Defensor del Pueblo”.
El informe critica que se han dado puestos laborales en el área de informática sin la debida preparación.“Si bien la descripción de los puestos y la formación exigida no corresponde con la necesidades reales de una unidad TIC, tal vez la selección del personal se realizó teniendo estas necesidades en mente y, de alguna manera, fueron ocupadas por personal con formación informática. Sin embargo, un sencillo análisis de la ocupación desmiente esta hipótesis: solo hay cinco personas con estudios de informática o telecomunicaciones entre un total de 60 puestos”.
De estos 60 miembros de la plantilla de informática, a 21 se les asignó la categoría de operador informático. Según el convenio colectivo aprobado entre los sindicatos y los altos cargos del tribunal, para acceder a este puesto solo era necesario tener estudios “de bachillerato, BUP, FP2 o LOGSE”, y alguna “experiencia en el sistema MS-DOS”. Y a otros 19 operarios solo se les exigió, por acuerdo de convenio colectivo, tener la “ESO, el graduado escolar o FP1”. Otra exigencia era tener “experiencia en desempeño de puesto de trabajo similar”. A los programadores informáticos (hay cuatro) les bastó únicamente con acreditar que tenían “experiencia en el sistema operativo MS-DOS”. Los dos jefes de negociado que hay en plantilla solo tuvieron que demostrar “conocimientos de proceso de texto, hoja de cálculo, gestores de datos y entornos ofimáticos”.
20 operadores solo saben manejar sistemas informáticosEl informe analiza también los puestos del Servicio Central de Informática del Tribunal de Cuentas, donde hay otros 11 operarios. En este servicio, señala el documento, el nivel de exigencia profesional debe ser muy superior (“por encima del nivel de usuario de Windows”) al del personal antes citado. Tampoco sucede: “En siete de los once puestos es suficiente un uso básico del ordenador para ocupar un puesto informático en el Servicio Central de Informática”. Ninguno de estos siete operarios tiene estudios universitarios. En ese departamento han recalado algunos de los opositores con “padrino” en la institución, según asegura una fuente.
Algunos allegados de altos cargos son ahora jefes de equipo. El convenio colectivo del tribunal resta importancia a los estudios a la hora de ascender. Su artículo 6 establece: “Los aspirantes por el turno de promoción interna, excepto para acceder a los grupos 1 [titulados universitarios] y 2, quedarán exentos de reunir el requisito de titulación reseñado anteriormente, siempre y cuando acrediten una experiencia mínima de cinco años de antigüedad en la plantilla”.
Investigación@elpais.es
Dos grandes debilidadesEl informe sobre las graves carencias del servicio informático del Tribunal de Cuentas contiene un estudio comparativo con su análogo del Tribunal Constitucional. El informe apuesta por que haya un equipo propio competente dentro del Tribunal de Cuentas que sea capaz de desarrollar los programas adecuados para su cometido fiscalizador y, a la vez, garantice la confidencialidad de la documentación que maneja.Sin embargo, descubre “dos grandes debilidades” respecto al servicio informático del Tribunal Constitucional. “El Tribunal de Cuentas externaliza la mayoría de los mantenimientos de las infraestructuras y aplicaciones de administración electrónica. Estos mantenimientos se concretan en forma de atención telefónica desde un centro externo, por lo que no hay atención dentro del propio tribunal ni de técnico que conozcan de antemano las peculiaridades de la infraestructura del tribunal. Por ejemplo, si se cae la red de datos, la atención en primera instancia es telefónica, con independencia de la gravedad del incidente, lo que alarga los tiempos de resolución frente a los que se obtendrían si se dispusiera de técnicos en la propia sede, como sucede en el Tribunal Constitucional. Lo ideal sería disponer de técnicos informáticos en plantilla que se ocuparan de este trabajo para que el conocimiento se mantengan dentro del tribunal”.El estudio compara la capacidad y nivel de los técnicos del Tribunal Constitucional y del de Cuentas, y concluye: “La relación entre puestos TIC [los más cualificados] y empleados es de 1 a 7 en el Tribunal Constitucional, mientras que en el Tribunal de Cuentas es de 1 a 64
jueves, 26 de junio de 2014
miércoles, 25 de junio de 2014
Impresionante red familiar en el Tribunal de Cuentas español
Relaciones familiares en el Tribunal de Cuentas
El País
Vínculos familiares entre altos cargos y empleados del órgano fiscalizador de las cuentas del Estado
Los lazos de parentesco en el Tribunal de Cuentas alcanzan a 100 empleados.
El País
Vínculos familiares entre altos cargos y empleados del órgano fiscalizador de las cuentas del Estado
Los lazos de parentesco en el Tribunal de Cuentas alcanzan a 100 empleados.
martes, 24 de junio de 2014
Hipergrafos y redes celulares
lunes, 23 de junio de 2014
Elegante grafo de comercio internacional
Cómo más de la mitad de las exportaciones del mundo entran en un grafo elegante
Por Lily Kuo - QZ
Líneas en los enlaces del círculo (directamente bajo el nombre del país) indican las importaciones y exportaciones totales de ese país (en millones de dólares EE.UU.) en 2013. El gráfico representa el 60% del total de las exportaciones mundiales.
Cuarzo ha analizado la importancia de la proximidad geográfica es para determinar los mejores socios comerciales, la mayoría de los países de un país comercian más con sus vecinos. Pero un nuevo gráfico de la firma de investigación Euromonitor que ilustra las importaciones y exportaciones de una selección de los países exportadores más grandes del mundo pone de relieve algunas excepciones interesantes. (Nota: el gráfico sólo incluye la parte superior del 60% de los países exportadores, en valor, por lo que hay muchos países que no están representados.)
Por ejemplo, el principal socio comercial del año pasado de la India no era ni de China o Pakistán, sus vecinos más grandes, pero los Emiratos Árabes Unidos. El comercio bilateral indio-EAU era de $ 75 mil millones entre 2012 y 2013. La Embajada de la India en los EAU cita 2.000.000 expatriados que viven en los Emiratos Árabes Unidos, la comunidad de expatriados más grande, como una de las razones. Académicos también han argumentado que-la ida y vuelta, o la re-importación de perlas y piedras preciosas enviados a los Emiratos Árabes Unidos con el fin de tomar ventaja de las excepciones de la India a las importaciones de servicio de la joyería se inició en 2007, ha inflado artificialmente el comercio.
Por otra parte, las zonas de libre comercio establecidas en los barrios geográficas no siempre proporcionan un impulso del comercio. Comercio dentro del "Mercosur" comercio de la zona-Argentina, Brasil, Paraguay y Uruguay inventada sólo el 13% de las exportaciones totales de los países miembros del grupo. China, Estados Unidos y la Unión Europea representaron el resto. Brasil envía 2,5 veces más las exportaciones a China y los EE.UU. que lo hace para el Mercosur, notas de Euromonitor.
Esto se debe a unos pocos países, como China, los EE.UU., Francia y Alemania tienen una influencia particularmente fuerte en el comercio global. Como hemos señalado, 35 países nombrar a China como su principal socio comercial, y aproximadamente la mitad de los que no son países vecinos.
Por Lily Kuo - QZ
Líneas en los enlaces del círculo (directamente bajo el nombre del país) indican las importaciones y exportaciones totales de ese país (en millones de dólares EE.UU.) en 2013. El gráfico representa el 60% del total de las exportaciones mundiales.
Cuarzo ha analizado la importancia de la proximidad geográfica es para determinar los mejores socios comerciales, la mayoría de los países de un país comercian más con sus vecinos. Pero un nuevo gráfico de la firma de investigación Euromonitor que ilustra las importaciones y exportaciones de una selección de los países exportadores más grandes del mundo pone de relieve algunas excepciones interesantes. (Nota: el gráfico sólo incluye la parte superior del 60% de los países exportadores, en valor, por lo que hay muchos países que no están representados.)
Por ejemplo, el principal socio comercial del año pasado de la India no era ni de China o Pakistán, sus vecinos más grandes, pero los Emiratos Árabes Unidos. El comercio bilateral indio-EAU era de $ 75 mil millones entre 2012 y 2013. La Embajada de la India en los EAU cita 2.000.000 expatriados que viven en los Emiratos Árabes Unidos, la comunidad de expatriados más grande, como una de las razones. Académicos también han argumentado que-la ida y vuelta, o la re-importación de perlas y piedras preciosas enviados a los Emiratos Árabes Unidos con el fin de tomar ventaja de las excepciones de la India a las importaciones de servicio de la joyería se inició en 2007, ha inflado artificialmente el comercio.
Por otra parte, las zonas de libre comercio establecidas en los barrios geográficas no siempre proporcionan un impulso del comercio. Comercio dentro del "Mercosur" comercio de la zona-Argentina, Brasil, Paraguay y Uruguay inventada sólo el 13% de las exportaciones totales de los países miembros del grupo. China, Estados Unidos y la Unión Europea representaron el resto. Brasil envía 2,5 veces más las exportaciones a China y los EE.UU. que lo hace para el Mercosur, notas de Euromonitor.
Esto se debe a unos pocos países, como China, los EE.UU., Francia y Alemania tienen una influencia particularmente fuerte en el comercio global. Como hemos señalado, 35 países nombrar a China como su principal socio comercial, y aproximadamente la mitad de los que no son países vecinos.
domingo, 22 de junio de 2014
Hipergrafos
Hipergrafo
En matemática y ciencias de la computación, un hipergrafo es una generalización de un grafo, cuyas aristas aquí se llaman hiperaristas, y pueden relacionar a cualquier cantidad de vértices, en lugar de sólo un máximo de dos como en el caso particular.
Formalmente, dado un conjunto finito A llamado conjunto base, un hipergrafo H es una familia de subconjuntos de ; es decir, un subconjunto de , que es el conjunto potencia de . Los elementos de un hipergrafo se llaman hiperaristas, las cuales a su vez son subconjuntos de .
La cardinalidad de un hipergrafo es su número de hiperaristas, y se denota |H|. El tamaño o volumen de un hipergrafo, se define como |A|·|H|.
Los hipergrafos pueden ser vistos como estructuras de incidencia. En particular, hay "grafo de incidencia" bipartito o "grafo Levi" correspondiente a cada hipergrafo, y por el contrario, la mayoría, pero no todos, los gráficos bipartitos puede ser considerado como grafos de incidencia de hipergrafos.
Los hipergrafos tienen muchos otros nombres. En la geometría computacional, un hipergrafo a veces puede ser llamado un rango de espacio y luego los hiperenlaces son llamados rangos. En la teoría de juegos cooperativos, los hipergrafos se llaman juegos simples (juegos de votación); esta noción se aplica para resolver problemas en la teoría de la elección social. En alguna literatura los enlaces se conocen como hipervínculos o conectores.
El tamaño o volumen de una estructura está dada por |A|·(|H|+|K|).
En matemática y ciencias de la computación, un hipergrafo es una generalización de un grafo, cuyas aristas aquí se llaman hiperaristas, y pueden relacionar a cualquier cantidad de vértices, en lugar de sólo un máximo de dos como en el caso particular.
Formalmente, dado un conjunto finito A llamado conjunto base, un hipergrafo H es una familia de subconjuntos de ; es decir, un subconjunto de , que es el conjunto potencia de . Los elementos de un hipergrafo se llaman hiperaristas, las cuales a su vez son subconjuntos de .
La cardinalidad de un hipergrafo es su número de hiperaristas, y se denota |H|. El tamaño o volumen de un hipergrafo, se define como |A|·|H|.
Los hipergrafos pueden ser vistos como estructuras de incidencia. En particular, hay "grafo de incidencia" bipartito o "grafo Levi" correspondiente a cada hipergrafo, y por el contrario, la mayoría, pero no todos, los gráficos bipartitos puede ser considerado como grafos de incidencia de hipergrafos.
Los hipergrafos tienen muchos otros nombres. En la geometría computacional, un hipergrafo a veces puede ser llamado un rango de espacio y luego los hiperenlaces son llamados rangos. En la teoría de juegos cooperativos, los hipergrafos se llaman juegos simples (juegos de votación); esta noción se aplica para resolver problemas en la teoría de la elección social. En alguna literatura los enlaces se conocen como hipervínculos o conectores.
Historia
Este término fue acuñado por el matemático francés Claude Berge en 1970.1 Desde entonces, se ha desarrollado toda una teoría de hipergrafos, que aunque a veces trata conceptos y problemas similares a los de la teoría de grafos, muchas veces se distancia de ésta última. Los hipergrafos se utilizan actualmente en distintas áreas, tales como la lógica, la optimización, teoría de juegos, inteligencia artificial, minería de datos, indexación de bases de datos, entre muchas otras.Propiedades
- Un hipergrafo es propio, si no es vacío ni contiene la hiperarista vacía.
- Un hipergrafo tiene dominio total si la unión de las hiperaristas es igual al conjunto A; de lo contrario, se dice que tiene dominio parcial.
Estructura de hipergrafos
Una estructura de hipergrafos es un par ordenado G:=(H, K) de dos hipergrafos H y K, bajo el mismo conjunto base.El tamaño o volumen de una estructura está dada por |A|·(|H|+|K|).
Ejemplo
Sea , entonces , con y es una estructura de hipergrafos, de tamaño 18.Modelo de grafo bipartito
Un hipergrafo H puede ser representado por un grafo bipartito BG de la siguiente manera: los conjuntos x y e son las particiones de BG, y (x1, e1) están conectados con un enlace si y sólo si x1 vértice está contenida en e1 borde en H. a la inversa, cualquier grafo bipartito con partes fijas y no hay nodos no conectados en la segunda parte representa algunos hipergrafos en la forma descrita anteriormente. Este gráfico bipartito también se llama grafo de incidencia.Referencias
- Berge, Claude (1970). Graphes et hypergraphes (37 edición). Dunod, París: Monographies Universitaires de Mathématiques.
Suscribirse a:
Entradas (Atom)