Boost Graph Library: ¿Hay algún algoritmo ordenado en BGL para la detección de comunidades?

Question

¿Hay alguien usando BGL para grandes servidores de producción?

• ¿Cuántos nodos comprende su red?
• ¿Cómo se maneja community detection
• ¿Tiene BGL alguna forma genial de detectar comunidades?
• A veces dos comunidades pueden estar unidas por uno o dos bordes, pero estos bordes no son confiables y pueden desaparecer. A veces no hay bordes en absoluto.

¿Podría alguien hablar brevemente sobre cómo resolver este problema. Por favor, abre mi mente e inspírame.

Hasta ahora he logrado averiguar si dos nodos están en una isla (en una comunidad) de una manera costosa, pero ahora necesito averiguar qué dos nodos en islas separadas están más cerca uno del otro. Solo podemos hacer un uso mínimo de datos geográficos poco confiables.

Si lo comparamos figurativamente con un continente y una isla y lo sacamos del contexto de la distancia social. Quiero averiguar qué dos trozos de tierra son los más cercanos entre sí a través de un cuerpo de agua.

Answer 1

He usado BGL para gráficos con millones de nodos, pero el tamaño del gráfico que puede usar depende del algoritmo que está intentando ejecutar. Puede calcular rápidamente distancias entre nodos. Existen 4 algoritmos de ruta más cortos que son más aplicables dependiendo de sus datos: (pares de puntos únicos, para todos los pares de puntos, gráficos dispersos y densos, ...).

En cuanto a la detección de comunidad, no hay algoritmos incorporados en el BGL específicamente para eso (pero tal vez pueda contribuir con uno cuando haya terminado su proyecto). Hay algunos algoritmos que pueden ser útiles para construir un algoritmo de detección de comunidad.Los algoritmos max-flow/min-cut se usan generalmente en la detección de comunidades (si hay mucho flujo entre dos nodos, entonces es probable que estén en la misma comunidad, si no hay mucho flujo, entonces es probable que el min-cut represente caminos entre comunidades). También hay heurísticas para ordenar los nodos del gráfico para reducir bandwidth. Es probable que los nodos que componen las "comunidades" estén cerca el uno del otro en ese orden.

Answer 2

Por lo que sé BGL no tiene ningún algoritmo específicamente para la detección de comunidades.

Por "isla" ¿te refieres a un subgrafo desconectado?

Además, los gráficos no tienen ninguna noción de "distancia".

Esta 'distancia social' es algo que vas a tener que definir. Una vez que haya hecho eso, una gran parte del trabajo ya está hecho.

Existen numerosos métodos enumerados en la página a la que se ha vinculado, la mayoría de ellos solo requieren que defina algo así como una métrica de "distancia", y luego conecte sus definiciones al algoritmo.

@ David Nehme

gráficos sin borde pesos son sólo alrededor de conectividad, no tienen noción de distancia. Si quiere hablar de una red, puede hablar de distancia. Pero un gráfico sin pesas de borde no tiene ninguna distancia, a menos que desee asumir un peso de borde implícito de 1 para todos los bordes. Pero esto realmente solo está convirtiendo el gráfico en una red.

Además, él está hablando de la distancia entre dos gráficos desconectados. Para modelar esto, debe introducir un concepto externo de distancia entre nodos, separado de la distancia al borde.