python - Quali sono le differenze tra gli algoritmi di rilevamento della comunità in igraph?




add edges (3)

Un riepilogo dei diversi algoritmi di rilevamento della comunità può essere trovato qui: http://www.r-bloggers.com/summary-of-community-detection-algorithms-in-igraph-0-6/

In particolare, l'algoritmo InfoMAP è un recente nuovo arrivato che potrebbe essere utile (supporta anche i grafici diretti).

Ho un elenco di circa 100 oggetti igraph con un oggetto tipico con circa 700 vertici e 3500 spigoli.

Vorrei identificare gruppi di vertici all'interno dei quali sono più probabili legami. Il mio piano è quello di utilizzare un modello misto per prevedere quanti nodi dei legami all'interno del gruppo hanno gli attributi di vertice e di gruppo.

Alcune persone potrebbero voler rispondere ad altri aspetti del mio progetto, il che sarebbe fantastico, ma la cosa che mi interessa di più è l'informazione sulle funzioni in igraph per il raggruppamento dei vertici. Mi sono imbattuto in questi algoritmi di rilevamento della community, ma non sono sicuro dei loro vantaggi e svantaggi, o se alcune altre funzioni sarebbero migliori per il mio caso. Ho visto i collegamenti anche here , ma non sono specifici di igraph. Grazie per il tuo consiglio.


Ecco un breve riassunto sugli algoritmi di rilevamento della comunità attualmente implementati in igraph:

  • edge.betweenness.community è un processo di decomposizione gerarchico in cui i bordi vengono rimossi nell'ordine decrescente dei loro punteggi di interlinea (ovvero il numero di percorsi più brevi che attraversano un dato spigolo). Ciò è motivato dal fatto che i bordi che connettono gruppi diversi hanno maggiori probabilità di essere contenuti in percorsi multipli più brevi semplicemente perché in molti casi sono l'unica opzione per passare da un gruppo all'altro. Questo metodo produce buoni risultati, ma è molto lento a causa della complessità computazionale dei calcoli di spigolo e perché i punteggi delle concordanze devono essere ricalcolati dopo ogni rimozione del bordo. I grafici con ~ 700 vertici e ~ 3500 spigoli si trovano intorno al limite superiore di dimensioni dei grafici che è possibile analizzare con questo approccio. Un altro svantaggio è che edge.betweenness.community costruisce un dendrogramma completo e non fornisce alcuna indicazione su dove tagliare il dendrogramma per ottenere i gruppi finali, quindi dovrai usare qualche altra misura per decidere che (ad esempio, la modularità punteggio delle partizioni ad ogni livello del dendrogramma).

  • fastgreedy.community è un altro approccio gerarchico, ma è bottom-up anziché top-down. Cerca di ottimizzare una funzione di qualità chiamata modularità in maniera avida. Inizialmente, ogni vertice appartiene a una comunità separata e le comunità vengono unite in modo iterativo in modo tale che ogni unione sia localmente ottimale (ovvero produce il maggiore aumento del valore corrente della modularità). L'algoritmo si interrompe quando non è più possibile aumentare la modularità, quindi fornisce un raggruppamento e un dendrogramma. Il metodo è veloce ed è il metodo che di solito viene provato come prima approssimazione perché non ha parametri da regolare. Tuttavia, è noto che soffre di un limite di risoluzione, cioè le comunità al di sotto di una determinata soglia di dimensione (a seconda del numero di nodi e spigoli se ricordo bene) saranno sempre unite con le comunità vicine.

  • walktrap.community è un approccio basato su passeggiate casuali. L'idea generale è che se si eseguono camminate casuali sul grafico, è più probabile che le passeggiate rimangano all'interno della stessa comunità perché ci sono solo alcuni spigoli che portano fuori da una determinata comunità. Walktrap esegue brevi passeggiate casuali di 3-4-5 passaggi (a seconda di uno dei suoi parametri) e utilizza i risultati di queste passeggiate casuali per unire comunità separate in un modo bottom-up come fastgreedy.community . Di nuovo, puoi usare il punteggio di modularità per selezionare dove tagliare il dendrogramma. È un po 'più lento dell'approccio avido ma anche un po' più accurato (secondo la pubblicazione originale).

  • spinglass.community è un approccio dalla fisica statistica, basato sul cosiddetto modello di Potts. In questo modello, ogni particella (cioè vertice) può essere in uno degli stati di rotazione c , e le interazioni tra le particelle (cioè i bordi del grafico) specificano quali coppie di vertici preferirebbero rimanere nello stesso stato di rotazione e quali preferiscono avere diversi stati di spin. Il modello viene quindi simulato per un determinato numero di passaggi e gli stati di rotazione delle particelle nella parte finale definiscono le comunità. Le conseguenze sono le seguenti: 1) Alla fine non ci saranno mai più di c comunità, sebbene sia possibile impostare c per un massimo di 200, che è probabile che sia sufficiente per i propri scopi. 2) Alla fine potrebbero esserci meno comunità in quanto alcuni stati di spin potrebbero diventare vuoti. 3) Non è garantito che i nodi in parti completamente remote (o sconcertate) delle reti abbiano stati di spin diversi. È più probabile che questo sia un problema solo per i grafici scollegati, quindi non mi preoccuperei di ciò. Il metodo non è particolarmente veloce e non deterministico (a causa della simulazione stessa), ma ha un parametro di risoluzione regolabile che determina le dimensioni del cluster. Una variante del metodo spinglass può anche prendere in considerazione i collegamenti negativi (cioè i collegamenti i cui endpoint preferiscono essere in diverse comunità).

  • leading.eigenvector.community è un approccio gerarchico top-down che ottimizza nuovamente la funzione di modularità. In ogni fase, il grafico è suddiviso in due parti in modo che la separazione stessa determini un aumento significativo della modularità. La divisione viene determinata valutando l'autovettore principale della cosiddetta matrice di modularità e vi è anche una condizione di arresto che impedisce di dividere ulteriormente i gruppi strettamente collegati. A causa dei calcoli di autovalori coinvolti, potrebbe non funzionare su grafici degenerati in cui il risolutore di autovettori ARPACK è instabile. Sui grafici non degenerati, è probabile che produca un punteggio di modularità più elevato rispetto al metodo avido veloce, sebbene sia un po 'più lento.

  • label.propagation.community è un approccio semplice in cui a ogni nodo viene assegnata una delle k etichette. Il metodo procede quindi in modo iterativo e riassegna le etichette ai nodi in modo che ogni nodo assuma l'etichetta più frequente dei suoi vicini in modo sincrono. Il metodo si interrompe quando l'etichetta di ciascun nodo è una delle etichette più frequenti nel suo quartiere. È molto veloce ma produce risultati diversi in base alla configurazione iniziale (che viene decisa casualmente), quindi si dovrebbe eseguire il metodo un gran numero di volte (ad esempio, 1000 volte per un grafico) e quindi creare un'etichettatura di consenso, che potrebbe essere noioso.

igraph 0.6 includerà anche l'algoritmo di rilevamento della comunità di Infomap, che si basa su principi teorici dell'informazione; prova a costruire un raggruppamento che fornisce la lunghezza di descrizione più breve per una passeggiata casuale sul grafico, dove la lunghezza della descrizione è misurata dal numero previsto di bit per vertice richiesto per codificare il percorso di una passeggiata casuale.

Ad ogni modo, probabilmente andrei con fastgreedy.community o walktrap.community come prima approssimazione e poi walktrap.community altri metodi quando si scopre che questi due non sono adatti per un particolare problema per qualche motivo.


Qui sembra essere la differenza su un pacchetto già caricato. Mentre è vero che entrambi richiedono e la libreria non carica il pacchetto. La libreria fa un sacco di altre cose prima che controlli ed esca.

Vorrei raccomandare di rimuovere "require" dall'inizio di una funzione che esegue comunque 2mil time, ma se, per qualche motivo, dovevo tenerlo. richiedere è tecnicamente un controllo più veloce.

microbenchmark(req = require(microbenchmark), lib = library(microbenchmark),times = 100000)
Unit: microseconds
 expr    min     lq      mean median     uq        max neval
  req  3.676  5.181  6.596968  5.655  6.177   9456.006 1e+05
  lib 17.192 19.887 27.302907 20.852 22.490 255665.881 1e+05




r igraph