Considerar grandes (más de 100.000 vértices, digamos) de gráficos, que pensamos como representación de una población con bordes que representan algún tipo de relación simétrica. Las que podrían ser Amigo graph de Facebook, matemáticos con la colaboración de la relación, o una gran red de computadoras.
Estas redes tienen la propiedad de que no son ni muy estructurado, ni totalmente al azar. No hay información sobre otras aristas en el grafo me puede decir con certeza si un determinado par de vértices está conectado. Dicho esto, si un determinado par de vértices tienen en común muchos de los vecinos, entonces es mucho más probable que ellos están conectados por una arista (por lo que no es totalmente al azar). He visto algunas de las conferencias en los gráficos como este, y tengo entendido que es un área productiva de la investigación (véase, por ejemplo, Kleinberg o Lovasz).
Estoy curioso sobre el siguiente fenómeno (mi descripción es vaga, pero una parte de mi pregunta está pidiendo una buena definición). Estas redes tienden a tener subconjuntos (que voy a llamar 'grumos'), que son significativamente más conectados entre sí que para el promedio de los vértices en la gráfica. Considere la posibilidad de un colegio en Facebook o un grupo de investigación en matemáticas, por ejemplo. Si los gráficos eran lo suficientemente pequeñas como para dibujar de una manera razonable, matas sería obvio para el ojo desnudo. Los gráficos de gran tamaño, esto es poco práctico; por lo que en lugar, te pido,
1) ¿Qué es una gráfica de la teoría de la forma de caracterizar a estos grupos?
Claramente, no va a ser un sí-no hay un criterio, pero estoy esperando para una cierta cantidad que mide la cantidad de un determinado subconjunto es un grupo. Esto también debería incluirse en la significación estadística de la mata. Muy pequeños subgrupos que están muy conectados sucede aun en totalmente grafos aleatorios, mientras que un gran subconjunto que es incluso moderadamente bien conectado es raro en un azar gráfico, y sería interesante conocer.
2) Dado un grafo (y una definición de un grupo), ¿cómo hace uno para encontrar las matas?
Hay una definición y un algoritmo tan robusto que puede tomar redes como Facebook o la colaboración gráfica, y el retorno de las matas que sabemos que están ahí, como universidades o de investigación discplines?
Ah, y yo no estoy en busca de la Szemeredi partición de un gráfico, que tiene algunas similitudes con el tipo de particiones que estoy buscando, pero es explícitamente una partición de la gráfica en trozos de tamaño similar. Las matas en un gráfico que no tiene que ser del mismo tamaño, distinto, ni contener cada elemento.
