10 Abril, 2020, 15:34 *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Homenaje a aladan
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Definición de comunidades en grafos  (Leído 1224 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Cristian C
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 482



Ver Perfil
« : 08 Mayo, 2017, 08:59 »

Hola a todos.

En un grafo (sin lazos ni enlaces paralelos) con gran número de nodos, muchas veces se presentan agrupaciones de ellos que están más interconectados entre sí que con el resto del grafo. Estas agrupaciones se denominan comunidades. He visto muchos algoritmos por allí diseñados para detectar comunidades en redes, pero no veo una definición formal de comunidad. Algunos artículos mencionan incluso dificultades a la hora de definirlas, pero no me queda claro que sea así.

¿Donde puedo encontrar una presentación formal donde se definan estas comunidades?

Saludos.
En línea

Mi primer gran deslumbramiento matemático consistió en comprender que puede demostrarse que existen infinitos de diferente tamaño.
El segundo fue comprender que lo anterior, aun pese a ser correcto, carece de todo significado.
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 46.144


Ver Perfil
« Respuesta #1 : 08 Mayo, 2017, 09:58 »

Hola

En un grafo (sin lazos ni enlaces paralelos) con gran número de nodos, muchas veces se presentan agrupaciones de ellos que están más interconectados entre sí que con el resto del grafo. Estas agrupaciones se denominan comunidades. He visto muchos algoritmos por allí diseñados para detectar comunidades en redes, pero no veo una definición formal de comunidad. Algunos artículos mencionan incluso dificultades a la hora de definirlas, pero no me queda claro que sea así.

¿Donde puedo encontrar una presentación formal donde se definan estas comunidades?


Tal como planteas la pregunta, mi sensación es que ya has leído bastante sobre el tema y probablemente la referencia que te voy a dar ya la has visto.  Además apenas lo he ojeado. Pero por si acaso...

Aquí vine planteado el problema (y con una buena colección de referencias):

https://arxiv.org/pdf/0906.0612.pdf

En la página 9 explica el problema que indicas sobre el no acuerdo sobre una definición cerrada. Pero lo motiva. Dependiendo del ámbito específico donde se aplica la teoría pudiera interesar llamar o no a un determinado grupo de vérties aristas comunidad.

Después propone no sé si una definición, pero si una medida de la densidad de connectividad de un subgrafo que puede servir para medir en que medida puede ser considerado comunidad.

Saludos.
En línea
Cristian C
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 482



Ver Perfil
« Respuesta #2 : 08 Mayo, 2017, 10:35 »

¡Gracias, el_manco!

Enseguida me sumerjo a ver qué ideas atrapo.
Lo que ocurre es que cuando leí por allí que no existía una forma clara de definirlas me pareció qué no debía ser un problema tan complicado y me armé una definición. Quiero ver cuán chapucera es y como se aborda el tema por allí.
En línea

Mi primer gran deslumbramiento matemático consistió en comprender que puede demostrarse que existen infinitos de diferente tamaño.
El segundo fue comprender que lo anterior, aun pese a ser correcto, carece de todo significado.
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!