Graphentheorie - Analyse und Visualisierung

22

Ich bin nicht sicher, ob das Thema in das CrossValidated-Interesse eintritt. Du wirst es mir sagen.

Ich muss einen Graphen studieren (aus der Graphentheorie ) dh. Ich habe eine bestimmte Anzahl von Punkten, die verbunden sind. Ich habe eine Tabelle mit allen Punkten und den Punkten, von denen jeder abhängig ist. (Ich habe auch eine andere Tabelle mit den Auswirkungen)

Meine Fragen sind:
Gibt es eine gute Software (oder ein R-Paket), um das leicht zu studieren?
Gibt es eine einfache Möglichkeit, das Diagramm anzuzeigen?

RockScience
quelle
Ich habe versucht, cran.r-project.org/web/packages/graph/vignettes/graph.pdf zu verwenden, aber es scheint , dass das Paket "Rgraphviz" nicht mehr verfügbar ist. Hat jemand eine andere Lösung?
RockScience
1
Rgraphviz ist auf bioconductor: bioconductor.org/packages/release/bioc/html/Rgraphviz.html
Rob Hyndman
1
Vielen Dank! Graphviz ist perfekt und sehr flexibel, ich benutze es in R mit der Schnittstelle Rgraphviz und es funktioniert großartig.
RockScience

Antworten:

15

iGraph ist eine sehr interessante sprachübergreifende Bibliothek (R, Python, Ruby, C). Es ermöglicht das Arbeiten mit unidirektionalen und gerichteten Diagrammen und verfügt bereits über einige implementierte Analysealgorithmen.

nico
quelle
1
(+1) Meine Antwort ist anscheinend nach deiner gekommen. Da Ihre Antwort eine etwas andere Perspektive (plattformübergreifend, Algorithmen) hervorhebt, glaube ich, dass unsere Antworten nicht so redundant sind, aber ich kann meine ohne Probleme entfernen.
chl
14

Es gibt verschiedene Pakete zur Darstellung gerichteter und ungerichteter Graphen, Inzidenz- / Adjazenzmatrix usw. zusätzlich zum Graphen ; Schauen Sie sich zum Beispiel die gR- Aufgabenansicht an.

Für die Visualisierung und grundlegende Berechnung halte ich das igraph- Paket zusätzlich zu Rgraphviz (auf BioC, wie von @Rob hervorgehoben) für das zuverlässigste . Beachten Sie , dass graphviz ebenfalls installiert sein muss, damit letzteres ordnungsgemäß funktioniert . Das igraph- Paket enthält nette Algorithmen zum Erstellen guter Layouts, ähnlich wie graphviz .

Hier ist ein Anwendungsbeispiel ausgehend von einer gefälschten Adjazenzmatrix:

adj.mat <- matrix(sample(c(0,1), 9, replace=TRUE), nr=3)
g <- graph.adjacency(adj.mat)
plot(g)

Alt-Text

chl
quelle
Danke für deine Antwort. graphviz ist nicht einfach mit R zu installieren, aber es
scheint
Was ich jetzt tue, ist, dass ich den graphviz-Code mit R generiere und ihn mit der mediawiki-Erweiterung graphviz in einem Mediawiki lese. (Das Rgraphviz-Paket ist nicht einfach zu installieren und funktioniert nicht mit der letzten Version von R)
RockScience
Msgstr "Das Paket" graph "wurde aus dem CRAN - Repository entfernt."
Bartektartanus
8

Abgesehen von dem, was gesagt wurde, könnten Sie allein für die Vusualisierungsaufgabe (und außerhalb von R) daran interessiert sein, Gephi zu überprüfen .

F. Tusell
quelle
8

Eine weitere Option ist das statnet-Paket. Statnet verfügt über Funktionen für alle in SNA häufig verwendeten Kennzahlen und kann auch ERG-Modelle schätzen. Wenn Sie Ihre Daten in einer Kantenliste haben, lesen Sie die Daten wie folgt ein (vorausgesetzt, Ihr Datenrahmen trägt die Bezeichnung "Kantenliste"):

net <- as.network(edgelist, matrix.type = "edgelist", directed = TRUE) #if the network is directed, otherwise: directed = FALSE

Befinden sich Ihre Daten in einer Adjazenzmatrix, ersetzen Sie das Argument matrix.type durch "Adjazenz":

net <- as.network(edgelist, matrix.type = "adjacency", directed = TRUE)

Das statnet-Paket verfügt über einige sehr schöne Plotfunktionen. Um ein einfaches Diagramm zu erstellen, geben Sie einfach Folgendes ein:

gplot(net)

Gehen Sie wie folgt vor, um die Knoten entsprechend ihrer Interferenzzentralität zu skalieren:

bet <- betweenness(net)
gplot(net, vertex.cex = bet)

Standardmäßig verwendet die gplot-Funktion den Fruchterman-Reingold-Algorithmus zum Platzieren der Knoten. Dies kann jedoch über die Option mode gesteuert werden, um beispielsweise MDS für die Platzierung des Knotentyps zu verwenden:

gplot(net, vertex.cex, mode = "mds")

oder um ein Kreislayout zu verwenden:

gplot(net, vertex.cex, mode = "circle")

Es gibt viele weitere Möglichkeiten, und dieser Leitfaden behandelt die meisten grundlegenden Optionen. Für ein eigenständiges Beispiel:

net <- rgraph(20) #generate a random network with 20 nodes
bet <- betweenness(net) #calculate betweenness scores
gplot(net) #a simple plot
gplot(net, vertex.cex = bet/3) #nodes scaled according to their betweenness centrality, the measure is divided by 3 so the nodes don't become to big.
gplot(net, vertex.cex = bet/3, mode = "circle") #with a circle layout
gplot(net, vertex.cex = bet/3, mode = "circle", label = 1:20) #with node labels
Thomas Jensen
quelle
(+1) Ich habe dieses Paket noch nie verwendet, aber Ihre Übersicht legt nahe, dass ich es versuchen sollte. Scheint auf den ersten Blick gut zu sein.
chl
3

Eine ähnliche Frage wurde zu cstheory gestellt, auch wenn Sie sich speziell für ebene Graphen oder bibliografische Visualisierungen interessieren .

Gephi wurde hier bereits erwähnt, aber es wurde auch von einigen auf cstheory empfohlen, also denke ich, dass das eine gute Wahl ist.

Andere coole Optionen sind:

  • Flare bietet einige wirklich coole Visualisierungstools und erstellt sehr hübsche Grafiken für Berichte und Papiere.
  • Cyptoscape verfügt über einige sehr leistungsstarke Analyse- und Visualisierungstools. Es ist besonders gut für die Chemie und Molekularbiologie.
  • Diese Website enthält Links zu vielen anderen nützlichen Visualisierungstools und -bibliotheken (allerdings nicht für R).
Artem Kaznatcheev
quelle
2

Ich fand NodeXL sehr hilfreich und einfach zu bedienen. Es ist eine MS Excel-Vorlage, die den einfachen Import / Export eines Diagramms, die Formatierung von Kanten / Scheitelpunkten, die Berechnung einiger Metriken und einige Cluster-Algorithmen ermöglicht. Sie können problemlos benutzerdefinierte Bilder als Scheitelpunkte verwenden.
Ein weiteres hilfreiches Tool für mich war Microsoft Automatic Graph Layout, das ein gutes Layout bietet und online ausprobiert werden kann (mit einem Browser, der SVG unterstützt).

Kniganapolke
quelle