Boost Graph Library: esiste un algoritmo pulito integrato in BGL per il rilevamento della comunità?

Question

Qualcuno là fuori che utilizza BGL per server di produzione di grandi dimensioni?

• Di quanti nodi è composta la tua rete?
• Come gestisci rilevamento della community
• BGL ha dei modi interessanti per rilevare le comunità?
• A volte due comunità possono essere collegate tra loro da uno o due bordi, ma questi bordi non sono affidabili e possono svanire. A volte non ci sono bordi.

Qualcuno potrebbe parlare brevemente su come risolvere questo problema. Per favore, apri la mia mente e ispirami.

Finora sono riuscito a capire se due nodi si trovano su un'isola (in una comunità) in un modo per nulla costoso, ma ora ho bisogno di capire quali due nodi su isole separate sono più vicini l'uno all'altro. Possiamo solo fare un uso minimo di dati geografici inaffidabili.

Se lo confrontiamo figurativamente con una terraferma e un'isola e lo portiamo fuori dal contesto della distanza sociale. Voglio capire quali due parti di terra sono le più vicine tra loro attraverso uno specchio d'acqua.

Answer 1

Ho usato il BGL per i grafici con milioni di nodi, ma le dimensioni del grafico che puoi usare dipendono dall'algoritmo che stai cercando di eseguire. È possibile calcolare rapidamente le distanze tra i nodi. Esistono 4 algoritmi di percorso più brevi che sono più applicabili a seconda dei dati: (singole coppie di punti, per tutte le coppie di punti, grafici sparsi e densi, ...).

Per quanto riguarda il rilevamento della comunità, non ci sono algoritmi integrati nel BGL appositamente per questo (ma forse puoi contribuire con uno al termine del tuo progetto). Esistono alcuni algoritmi che potrebbero essere utili nella creazione di un algoritmo di rilevamento della comunità. Gli algoritmi max-flow / min-cut vengono generalmente utilizzati nel rilevamento della comunità (se è possibile un flusso molto lungo tra due nodi, è probabile che si trovino nella stessa comunità, se non vi è molto flusso, è probabile che il taglio minimo rappresenti strade tra le comunità ). Esistono anche euristiche per ordinare i nodi del grafico per ridurre larghezza di banda. Nodi che compongono " comunità " è probabile che siano vicini l'uno all'altro in un tale ordinamento.

Answer 2

Per quanto ne so, BGL non ha algoritmi specifici per il rilevamento della comunità.

Per " isola " intendi un sottografo disconnesso?

Inoltre, i grafici non hanno alcuna nozione di "distanza".

Questa "distanza sociale" è qualcosa che dovrai definire. Una volta fatto ciò, gran parte del lavoro è fatto.

Esistono numerosi metodi elencati nella pagina a cui sei collegato, la maggior parte di questi richiede solo di definire qualcosa come una metrica "distanza", quindi collegare le tue definizioni all'algoritmo.

@ David Nehme

I grafici senza contrappesi riguardano solo la connessione, non hanno nozione di distanza. Se vuoi parlare di una rete, puoi parlare di distanza. Ma un grafico senza pesi dei bordi non ha alcuna distanza, a meno che non si desideri assumere un peso dei bordi implicito di 1 per tutti i bordi. Ma questo sta davvero trasformando il grafico in una rete.

Inoltre, sta parlando della distanza tra due grafici disconnessi. Per modellarlo, devi introdurre un concetto esterno per la distanza tra i nodi, separato dalla distanza dal bordo.