Individuazione dei nodi più importanti in un grafico orientato

Non conoscendo il vero problema che il tuo grafico risolve o i dettagli del tuo grafico, questo potrebbe non essere rilevante. Ma, sospetto che la tua soluzione di base sarà inaccurata in due modi: tie-break e ciò che potrei chiamare "megalomani". In altre parole, se stai solo contando le connessioni in entrata, probabilmente ti imbatterai in nodi con la "stessa" importanza; ma, sospetto che l'intenzione sia quella di essere più importante. E, in alcuni casi, potresti avere "isole" di nodi che sono tutti altamente interconnessi tra loro, ma in modo generico con la maggioranza, producendo nodi che sembrano molto più importanti di loro (megalomani).

La soluzione? Beh ... Qualcosa come il pagerank, immagino!

Ho trovato la seguente immagine una buona chiave per la differenza tra le diverse misure (anche se i grafici non orientati sono rappresentati, alcuni si applicano anche a quelli diretti). La centralità del grado [D] è semplice: chi ha più collegamenti dentro / fuori. Eigenvector-centrality [C] cattura meglio la nozione di influenza indiretta. Vedi Centralità su wikipedia per le definizioni e i dettagli.

Suppongo che tu voglia calcolare solo la connettività del primo ordine (cioè il conteggio del numero di collegamenti che collegano direttamente al nodo).

Suppongo inoltre che tu abbia già un elenco di tutti i nodi con un posto dove archiviare i pesi dei nodi e un elenco di tutti i bordi.

Avrai bisogno di:

1. Un elenco di tutti i nodi e un luogo in cui archiviare il peso calcolato per ciascun nodo.
2. Un elenco di tutti i bordi. Come hai proposto, qualsiasi tecnica di attraversamento completo (come ampiezza o profondità) dovrebbe funzionare fintanto che il grafico è collegato (anche se potrebbe essere necessario ulteriore spazio per tracciare lo stato di esplorazione di ciascun nodo).

L'algoritmo è semplice: itera su ciascun lato e incrementa i pesi dei nodi Da e A a cui fa riferimento quel bordo.

L'interpretazione dei risultati per trovare nodi "interessanti" dipenderà dal set di dati. Ad esempio, le pagine Web potrebbero essere interessanti se hanno un alto rapporto tra i bordi in entrata e quelli in uscita, ma un grafico di aeroporti e voli potrebbe semplicemente guardare il traffico totale.

Semplicemente disegnando questo su un pezzo di carta, ho optato per la ricerca in profondità. Perché? Bene, usando l'idea di cui sopra, di attraversare il grafico seguendo i bordi diretti , possiamo idealmente tenere traccia di quante volte visitiamo un particolare nodo incrementando alcuni interi memorizzati. Potresti farlo altrettanto facilmente con l'ampiezza.

void search(node) {
    nodeInitial = pick a node
    for(nodeInitial:outgoingNodes as node) {
        node:visits++ // this is how you track in-edges
        if(node is unvisited) {
            search(node)
            node:visited = true
        }
    }
}

Una parte del problema è che con un grafico diretto, potresti avere sotto-grafici che sono connessi a se stessi, ma che non sono collegati esternamente. Altre parti del grafico potrebbero connettersi a questi sotto-grafici, ma potrebbero non esserci connessioni in uscita. Pensa a un'isola (o un gruppo di isole) che ha 3 autostrade di sola andata e solo verso l'interno che viaggiano verso di essa, ma senza autostrade in uscita. Penso che questa sia la sfida più grande: come selezionare parti del grafico che non sono state visitate. L'unico modo in cui posso pensare di farlo sarebbe se i nodi stessi tenessero anche traccia di ciò che altri nodi stanno puntando su di loro (nodi entranti). Da lì, è necessario modificare l'algoritmo in modo che scelga un nuovo nodo da un nodo in entrata dopo aver eseguito un attraversamento completo di un intero sotto-grafico. Quindi salta su quell'altro grafico secondario e attraversalo finché non hai bisogno di saltare al grafico secondario successivo, ecc.

Penso che sarebbe abbastanza facile memorizzare il nodo "più importante" con il maggior numero di spigoli creando semplicemente un singolo oggetto nodo separato che verrebbe aggiornato mentre si attraversa il grafico.

Node mostImportant = null

void search(node) {
    nodeInitial = pick a node
    if(!mostImportant) {
        mostImportant = nodeInitial
    }

    for(nodeInitial:outgoingNodes as node) {
        node:visits++ // this is how you track in-edges

        if(node.visits > mostImportant.visits)
            mostImportant = node

        if(node is unvisited) {
            search(node)
            node:visited = true
        }
    }
}

Se non è importante stabilire a quali nodi connettersi, usa una semplice matrice 2x2, che ha una colonna per ogni nodo e una riga che rappresenta un nodo. ogni nodo che è connesso ottiene il valore 1 per la colonna. quindi aggiungi una colonna in più alla fine di ogni riga che conta il numero di connessioni per quel nodo. questo ha un enorme vantaggio in testa ma otterrà il nodo più connesso e renderà più facile l'inserimento e l'eliminazione del nodo se si conosce la dimensione in anticipo. Se la dimensione del grafico è dinamica, questo non funzionerà, funziona solo per i grafici statici. Anche la memoria sarà un problema dal momento che dovrai usare un array. Ma se trovare il nodo più connesso è il grosso problema, questo è un modo semplice per farlo.

Gli algoritmi tipicamente cercano di ottimizzare una cosa o l'altra. Anche i problemi di NP sono risolvibili, tranne per il fatto che richiedono tutte le possibili combinazioni da provare, il che li rende computazionalmente costosi. Nel problema che stai cercando di risolvere, la domanda è: cosa stai cercando di ottimizzare: tempo, memoria o qualcos'altro?

Dato che sono 2 milioni di nodi, non è chiaro se siano tutti letti in memoria in una volta sola, o se risiedono su disco e quindi la gestione della memoria e la minimizzazione dell'I / O potrebbero essere un fattore.

Supponendo che l'intero grafico sia in memoria, la domanda è: chi crea il grafico? Puoi tenere un conteggio dei bordi per i nodi nel grafico durante la creazione (o quando leggi dal disco) e tenerli in un elenco ordinato?

L'altra cosa è che a volte un grafico può avere due o più parti completamente disconnesse nella vita pratica (ho dovuto occuparmi di uno di questi grafici). In questi casi, ho trovato più utile iterare attraverso tutti i nodi (non importa prima la larghezza o prima la profondità), e poi contare tutti i bordi su ogni nodo - nella maggior parte dei casi, le lingue moderne manterranno tutti i bordi in alcuni una sorta di raccolta e avrai già una proprietà o un metodo per ottenere la lunghezza o contare su quella raccolta, salvando così l'iterazione su tutti i bordi).

La complessità di entrambe queste soluzioni può essere O (n log n) dove n è il no. dei nodi.

Sebbene il tempo e la memoria siano spesso motivo di preoccupazione, ma a volte la semplicità è più importante di quegli attributi, quindi lo tengo anche nella mia equazione. In molte situazioni, come questa, considererei la complessità di implementazione come un altro fattore nella mia lista pro / contro prima di decidere cosa implementare.