Boost Graph Library: ¿Hay un algoritmo ordenado integrado en BGL para la detección de la comunidad?

Question

¿Alguien usa BGL para grandes servidores de producción?

• ¿De cuántos nodos está compuesta su red?
• ¿Cómo maneja detección comunitaria
• ¿Tiene BGL alguna forma genial de detectar comunidades?
• Algunas 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 menos costosa, pero ahora necesito determinar 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í en un cuerpo de agua.

Answer 1

He usado el 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 según sus datos: (pares únicos de puntos, para todos los pares de puntos, gráficos dispersos y densos, ...).

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

Answer 2

Hasta donde yo sé, BGL no tiene ningún algoritmo específicamente para la detección de la comunidad.

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 tendrá que definir. Una vez que hayas hecho eso, una gran parte del trabajo está hecho.

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

@ David Nehme

Los gráficos sin pesos de borde son solo acerca de la conectividad, no tienen noción de distancia. Si desea hablar sobre una red, puede hablar sobre la distancia. Pero un gráfico sin pesos 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, está hablando de la distancia entre dos gráficos desconectados. Para modelar esto, debe introducir un concepto externo para la distancia entre nodos, separado de la distancia al borde.