Algoritmo per identificare sottografi "fuzzily-connected"

Question

Ho un problema che sembra il problema dei sottografi connectet da un miglio alto, ma è abbastanza distinto in quanto non rientra nelle definizioni rigorose.

Affronto un grafico con alcuni milioni di nodi e collegamenti (l'analisi manuale non è possibile), tra quei milioni di nodi, ci sono noti 2 o 3 "set".

Ciascuno degli "insiemi" comprende centinaia di millesimi di nodi e decine di millesimi sotto-grafici, non fortemente connessi. Ognuno di questi set non dovrebbe teoricamente essere collegato agli altri set ... ma ci sono (congetture) una dozzina di link errati che finiscono per connettere questi set.

Il problema è trovare questi set e i collegamenti errati, o almeno ottenere un elenco gestibile dall'uomo di collegamenti errati candidati che possono essere verificati manualmente.

La mia "migliore idea" corrente è quella di selezionare a caso due nodi, trovare il percorso più breve tra di loro, quindi contrassegnare i collegamenti su quel percorso più breve. Risciacquo & ripetere milioni di volte, e i collegamenti errati alla fine finiscono come quelli più marcati, in quanto sono "chokepoints" tra i set.

Tuttavia, questo è piuttosto lento, e quando un set è molto più grande degli altri e ha chokepoint interni, finisce per dominare la lista "più marcata", rendendola priva di significato.

Ci sono algoritmi/approcci migliori per questo?

edit: un perfezionamento della marcatura percorso è quello di segnare in proporzione con la lunghezza del percorso, che aiuta con le "strozzature interne di un grande insieme" problema, ma non si fa del tutto elimina come alcuni set possono avere distanti "valori anomali", mentre altri set hanno molti nodi strettamente collegati (brevi distanze interne)

Answer 1

La mia idea è una ant colony algorithm. Mi ispiro al tuo approccio di scegliere due nodi casuali, ma ho pensato che sarebbe stato utile fare qualcosa in più invece di calcolare solo il percorso più breve.

Avvia n an in n nodi casuali. Sarà necessario regolare n con il metodo di prova ed errore. Le formiche lasciano un feromone sui bordi percorsi. Il feromone evapora nel tempo. Le formiche scelgono uno dei bordi distinti per viaggiare secondo la probabilità. Più il feromone ha un bordo, più è probabile che una formica scelga quel bordo.

Inizialmente le formiche si muovono in modo totalmente casuale, poiché non vi è alcun feromone e gli spigoli hanno la stessa probabilità. Tuttavia, col passare del tempo, i bordi più popolari, i ponti tra due componenti "collegati in modo confuso" avranno sempre più feromoni su di essi.

Quindi, si lanciano le formiche, si simula per m spire e si ritornano i bordi con la più alta quantità di feromone su di esse. È possibile visualizzare questo processo per vedere chiaramente cosa sta succedendo.

Aggiornamento: mi sono reso conto che la frase "Tuttavia, nel corso del tempo, i bordi più popolari, ponti tra due 'con confusione collegate' componenti avrà sempre di più su di loro feromone" è sbagliato. I implemented e sembra che la maggior parte dei ponti di tempo non attirano necessariamente le formiche:

C'erano n = 1000 formiche e M = 1000 passi.Inizialmente ogni bordo aveva 1 unità di feromone ed era aumentato di 1 se la formica viaggiava sopra di essa. Nessuna evaporazione, tuttavia penso che non migliorerebbe la situazione. Bridge aveva 49845 unità di feromone, ma c'erano altri tre bordi che avevano più di 100k.

---

Come suggerito dal Peter de Rivaz nel commento, ho provato (source code) ripetendo min-cut tra i 2 nodi casuali ed è molto meglio:

_{grafici generati con python-igraph biblioteca.}