¿Existe un algoritmo que encuentre subgrafías de un gráfico de manera que cada nodo en una subgrafía esté conectado a al menos k otros nodos de esa subgrafía?

Answer 1

Estás mezclando dos nociones diferentes.

• Se dice que una gráfica tiene un grado mínimo [matemática] k [/ matemática] si cada vértice tiene al menos [matemática] k [/ matemática] vecinos.
• Se dice que un gráfico está [math] k [/ math] conectado si se elimina cualquier subconjunto de vértices [math] k-1 [/ math] del gráfico deja un gráfico conectado. (Ver gráfico conectado a k-vértice).

Una “comunidad” de personas en una red social es una noción muy vaga, y ninguna de estas definiciones necesariamente la capta bien. En primer lugar, nunca dijiste qué era [matemáticas] k [/ matemáticas]; un subgrafo conectado a 1 no es lo mismo que un subgrafo conectado a 6.

Ahora, hay muchos gráficos con un grado mínimo 3, digamos, que no se parecen en nada a una comunidad; Por ejemplo, un conjunto de 12 personas organizadas en camarillas de 4 es un subgrafo de grado mínimo 3, pero las camarillas no están familiarizadas entre sí, por lo que difícilmente es una comunidad.

Los gráficos de 2 o 3 conectados son un mejor modelo para una comunidad, pero aún podría haber muchos casos en los que parecerían incorrectos. Un ciclo largo (A sabe B quién sabe C quién sabe D … quién sabe Z quién sabe A) está conectado 2, pero ¿es eso una comunidad? A no conoce a nadie aquí excepto B y Z, y lo mismo se aplica a todos los demás. Puede presionar para 3 o 4 conectados, etc., pero rápidamente corre el riesgo de no encontrar ninguna comunidad de acuerdo con esas definiciones más estrictas.

De todos modos, asegúrese de que existan algoritmos para encontrar subgrafías conectadas [math] k [/ math] de un gráfico dado; Probablemente quieras preguntar si hay eficientes . Para [math] k [/ math] = 2 la respuesta es sí, hay un algoritmo de tiempo lineal de Hopcroft y Tarjan que encuentra componentes biconéctados (esos son subgrafos máximos conectados a 2). Ver componente Biconnected.

Para [math] k [/ math]> 2 la situación se vuelve más compleja ya que no hay una forma única de definir componentes máximos. Si solo desea encontrar un subgrafo conectado [math] k [/ math], esto puede ser más fácil, pero puede o no ser factible dependiendo del valor de [math] k [/ math] y el tamaño de su grafico. Consulte el árbol SPQR y otras referencias que puede encontrar buscando en Google los “componentes conectados a k”.

Answer 2

En general, la respuesta a su pregunta es sí, pero no de manera muy eficiente. El problema de la k-camarilla es el problema de encontrar una camarilla de k nodos en un gráfico, es decir, una subgrafía de k nodos con cada nodo compartiendo un borde con todos los demás nodos de la camarilla. Entonces, en este ejemplo, la “comunidad” consistiría en amigos (es decir, nodos) que comparten una ventaja (es decir, amistad) entre sí. Esto parece ser lo que estás preguntando.

La solución es polinómica para un k fijo, O (k ^ 2 * n ^ k), que es el método de fuerza bruta. No estoy al tanto de mejores soluciones fuera de mi cabeza. Encontrar camarillas máximas, o el problema de decisión de si existe una camarilla de un tamaño particular o mayor, es NP-completo, por lo que no se conoce una solución de tiempo polinomial para el problema (las soluciones más conocidas son O (c ^ n), donde c es aproximadamente 1.2).

Si está preguntando si existe un algoritmo para encontrar subgrafías donde cada nodo tenga una distancia máxima de colaboración de d con cada otro nodo, entonces me temo que no tiene suerte (esto es análogo a los seis grados de hecho de separación que escuchas de vez en cuando). Ese problema parece intratable a primera vista dado que agregar o eliminar nodos a la subgrafía inducida alteraría la distancia de colaboración de todos los nodos candidatos, por lo que uno potencialmente necesitaría ejecutar el algoritmo de Djikstra (o una variante O (n ^ 2) más eficiente para el caso de peso de borde uniforme) cada vez que se agrega un nodo, ya que las rutas más cortas (es decir, la distancia de colaboración) dependen de los nodos intermedios para d> 1.

Uno podría ser capaz de formular este problema como el problema del isomorfismo del subgrafo (construyendo explícitamente gráficos que contengan el requisito de colaboración implícita) ya que una distancia mínima de colaboración implica una cierta regularidad en el gráfico. Sin embargo, ese problema también es NP-completo, aunque existen soluciones polinómicas (algoritmo de Ullman) para encontrar subgrafías fijas, por lo que podría ser factible si puede construir subgrafías de colaboración para buscar en tiempo polinómico (lo que parece factible).

Por cierto, el caso de una distancia de colaboración de 1 es exactamente el problema de la camarilla k, por lo que uno esperaría que el problema k> 1 sea aún más difícil, aunque esto no necesariamente tiene que ser cierto (piense en la conjetura generalizada de Poincare. Pero yo divago…)

Answer 3

Solo voy a tomar su pregunta al pie de la letra. Se le da un gráfico con vértices V y aristas E, y desea encontrar una subgrafía de manera que cada vértice en la subgrafía tenga un grado> = k.

En realidad, hay un algoritmo eficiente para resolver este problema. En lugar de preguntar qué vértices deberían estar en su subgrafía, puede preguntarse, ¿qué vértices no deberían estar en su subgrafía?

La respuesta a eso es bastante obvia. Los vértices con grado = k en el subgrafo? En caso afirmativo, ha encontrado su subgrafo. Si no, hay algunos vértices en el subgrafo con grado

Puede simular este proceso con bastante facilidad en tiempo O (VE lg V). Todo lo que necesitas hacer es:

1. Verifique el vértice con un grado mínimo. Llamémoslo x.
2. ¿Tiene deg (x)> = k? En caso afirmativo, envíe el gráfico que tiene actualmente
3. Si no, elimine x de su gráfico y disminuya los grados de sus vecinos. Regrese al paso 1.