Navigieren in Netzwerken mit NetworkX: Eine kurze Anleitung zu Diagrammen in Python | von Diego Penilla | November 2024

Entdecken Sie NetworkX zum Erstellen, Analysieren und Visualisieren von Diagrammen in Python. Erkenntnisse in vernetzten Daten entdecken.

In In einer Welt voller Verbindungen – von Social-Media-Freundschaften bis hin zu komplexen Verkehrsnetzen – ist das Verständnis von Beziehungen und Mustern der Schlüssel zum Verständnis der Systeme um uns herum. Stellen Sie sich ein soziales Netzwerk vor, in dem jede Particular person ein Punkt (ein „Knoten“) ist, der durch Linien (oder „Kanten“) mit Freunden verbunden ist. Oder stellen Sie sich eine Kartierung des U-Bahn-Programs einer Stadt vor, in der jede Station ein Knotenpunkt und jede Route eine sie verbindende Kante darstellt.

Hier ist NetzwerkX glänzt und bietet eine leistungsstarke Möglichkeit, diese komplexen Beziehungsnetze aufzubauen, zu analysieren und zu visualisieren.

Mit NetworkX können wir Daten auf eine Weise darstellen, die mit herkömmlichen Tabellen umständlich oder sogar unpraktisch wäre, in einem Diagrammformat jedoch einfach und natürlich wird. Beziehungen, für deren Definition in einer Tabelle viele Zeilen und Spalten erforderlich wären, können auf intuitive, visuelle Weise erfasst werden, was uns hilft, komplexe Daten zu verstehen und zu interpretieren.

Mit der Bibliothek können wir eine breite Palette von Methoden und Algorithmen auf diese Diagramme anwenden und jedes Mal neue Erkenntnisse liefern, wenn wir unsere Daten mit einem neuen Ansatz neu gestalten.

Beginnen wir mit der Aufschlüsselung dessen, was ein Diagramm ist. Bei der Netzwerkanalyse besteht ein Diagramm aus Knoten (oder Eckpunkte) und Kanten (oder Hyperlinks).

• Stellen Sie sich Knoten als die Haupteinheiten vor, wie Menschen oder Webseiten, und Kanten als die Verbindungen zwischen ihnen – wie Freundschaften in einem sozialen Netzwerk oder Hyperlinks zwischen Web sites.
• Einige Kanten tragen sogar Gewichte, die die Stärke, Entfernung oder Kosten der Verbindung zwischen zwei Knoten darstellen. Mithilfe dieser zusätzlichen Informationsebene können wir nicht nur analysieren, ob zwei Knoten miteinander verbunden sind, sondern auch, wie stark oder eng sie sind.

Diese Diagramme können zur Modellierung einer Vielzahl von Systemen verwendet werden, von sozialen Netzwerken bis hin zu Molekülen und Transportnetzen.

Sehen wir uns zunächst an, wie man mit ein Diagramm erstellt networkx. Wenn Sie es nicht installiert haben, führen Sie zunächst Folgendes aus:

$ pip set up networkx

Erstellen eines Diagramms

Um ein Netzwerk aufzubauen, werden wir:

1. Initialisieren Sie das Netzwerk: indem Sie ein Diagramm erstellen mit G = nx.Graph()
2. Knoten mit Attributen hinzufügen: Verwenden Sie G.add_node(), um Knoten hinzuzufügen, von denen jeder benutzerdefinierte Attribute wie Beschriftungen oder Alter speichern kann.
3. Kanten hinzufügen: Knoten mit G verbinden.add_edge()wobei jede Kante ein Gewichtsattribut enthalten kann, um die Stärke oder Kosten der Verbindung darzustellen.
4. Visualisieren Sie das Diagramm: Verwenden Sie Matplotlib-Funktionen wie nx.draw() Und nx.draw_networkx_edge_labels() um das Diagramm anzuzeigen und Knotenbeschriftungen und Kantengewichtungen zur einfachen Interpretation anzuzeigen.

Dies ist der Code, um dies zu erreichen:

import networkx as nx
import matplotlib.pyplot as plt
# Create a easy graph
G = nx.Graph()
# Add nodes with attributes (e.g., 'label' and 'age')
G.add_node(1, label="A", age=25)
G.add_node(2, label="B", age=30)
G.add_node(3, label="C", age=22)
G.add_node(4, label="D", age=28)
# Add weighted edges (node1, node2, weight)
G.add_edge(1, 2, weight=4)
G.add_edge(1, 3, weight=3)
G.add_edge(2, 4, weight=5)
# Retrieve and print node attributes
node_attributes = nx.get_node_attributes(G, 'age')  # Get 'age' attribute for all nodes
print("Node Attributes (Age):", node_attributes)
# Retrieve and print edge attributes
edge_weights = nx.get_edge_attributes(G, 'weight')  # Get 'weight' attribute for all edges
print("Edge Attributes (Weight):", edge_weights)
# Draw the graph with node and edge attributes
pos = nx.spring_layout(G)  # Format for node positions
node_labels = nx.get_node_attributes(G, 'label')  # Get node labels for visualization
edge_labels = nx.get_edge_attributes(G, 'weight')  # Get edge weights for visualization
plt.determine(figsize=(6, 6))
nx.draw(G, pos, with_labels=True, node_color='skyblue', font_size=15, font_weight='daring', node_size=500)
# Draw the sting weights and node labels
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.title("NetworkX Graph with Node and Edge Attributes")
plt.present()

In diesem Beispiel initialisieren wir das Diagramm und erstellen dann:

• 4 Knoten (1, 2, 3, 4) durch Aufruf G.add_node(node, label, attr)
• 3 beschwerte Kanten die diese Knoten verbinden: (1, 2), (1, 3) und (2, 4) durch Aufruf G.add_edge(node1, node2, attr)

Sowohl Knoten als auch Kanten in NetworkX können zusätzliche Attribute enthalten, wodurch das Diagramm mit Informationen reicher wird.

• Knotenattribute (Zugriff über nx.get_node_attributes(G, ‘attribute’)) Erlauben Sie jedem Knoten, Daten zu speichern, beispielsweise den Beruf einer Particular person in einem sozialen Netzwerk.
• Kantenattribute (Zugriff über nx.get_edge_attributes(G, ‘attribute’)) Speichern Sie Informationen zu jeder Verbindung, beispielsweise die Entfernung oder die Fahrzeit in einem Verkehrsnetz. Diese Attribute fügen Kontext und Tiefe hinzu und ermöglichen eine detailliertere Analyse des Netzwerks.

Wir verwenden dann das Spring-Format von NetworkX pos = nx.spring_layout(G) um die Knoten für die Visualisierung zu positionieren und sicherzustellen, dass sie im Diagramm natürlich verteilt sind. Endlich, nx.draw() Und nx.draw_networkx_edge_labels() Zeigen Sie das Diagramm mit Knotenbeschriftungen und Kantengewichtungen an und schaffen Sie so eine klare Sicht auf die Struktur und Verbindungen des Netzwerks.

Obwohl dies ein recht einfaches Netzwerk conflict, veranschaulicht es die Grundlagen der Arbeit mit Netzwerken: Um Diagramme zu manipulieren, müssen wir die Knoten und ihre Verbindungen entlang aller Attribute, die sie möglicherweise haben, verwalten.

Karate-Membership-Netzwerk

Eines der bekanntesten Beispiele in der Netzwerkwissenschaft ist das Zacharys Karate Membership, Wird häufig zur Veranschaulichung der Analyse sozialer Netzwerke und der Group-Erkennung verwendet. Der Datensatz ist gemeinfrei und standardmäßig in networkx enthalten. Sie können wie unten gezeigt darauf zugreifen:

# Load the  Karate Membership
G = nx.karate_club_graph()
# Draw the graph
plt.determine(figsize=(8, 8))
pos = nx.spring_layout(G)  # Format for nodes -> treats nodes as repelling objects
nx.draw(G, pos, with_labels=True, node_color='skyblue', font_size=12, font_weight='daring', node_size=500)
plt.title("Zachary's Karate Membership Community")
plt.present()

Dieses Netzwerk repräsentiert die Freundschaften zwischen 34 Mitgliedern eines Karate-Golf equipment und ist berühmt für die Spaltung zwischen zwei Fraktionen, die sich jeweils um eine zentrale Figur drehen – Mr. Hello und Officer.

Werfen wir einen Blick auf die in den Knotendaten enthaltenen Attribute:

# looping over nodes
for node in G.nodes():
print(f"Node: {node}, Node Attributes: {G.nodes(node)}")

Node: 0, Node Attributes: {'membership': 'Mr. Hello'}
Node: 1, Node Attributes: {'membership': 'Mr. Hello'}
Node: 2, Node Attributes: {'membership': 'Mr. Hello'}
Node: 3, Node Attributes: {'membership': 'Mr. Hello'}
Node: 4, Node Attributes: {'membership': 'Mr. Hello'}
Node: 5, Node Attributes: {'membership': 'Mr. Hello'}
Node: 6, Node Attributes: {'membership': 'Mr. Hello'}
Node: 7, Node Attributes: {'membership': 'Mr. Hello'}
Node: 8, Node Attributes: {'membership': 'Mr. Hello'}
Node: 9, Node Attributes: {'membership': 'Officer'}
Node: 10, Node Attributes: {'membership': 'Mr. Hello'}
Node: 11, Node Attributes: {'membership': 'Mr. Hello'}
Node: 12, Node Attributes: {'membership': 'Mr. Hello'}
Node: 13, Node Attributes: {'membership': 'Mr. Hello'}
Node: 14, Node Attributes: {'membership': 'Officer'}
Node: 15, Node Attributes: {'membership': 'Officer'}
Node: 16, Node Attributes: {'membership': 'Mr. Hello'}
Node: 17, Node Attributes: {'membership': 'Mr. Hello'}
Node: 18, Node Attributes: {'membership': 'Officer'}
Node: 19, Node Attributes: {'membership': 'Mr. Hello'}
Node: 20, Node Attributes: {'membership': 'Officer'}
Node: 21, Node Attributes: {'membership': 'Mr. Hello'}
Node: 22, Node Attributes: {'membership': 'Officer'}
Node: 23, Node Attributes: {'membership': 'Officer'}
Node: 24, Node Attributes: {'membership': 'Officer'}
Node: 25, Node Attributes: {'membership': 'Officer'}
Node: 26, Node Attributes: {'membership': 'Officer'}
Node: 27, Node Attributes: {'membership': 'Officer'}
Node: 28, Node Attributes: {'membership': 'Officer'}
Node: 29, Node Attributes: {'membership': 'Officer'}
Node: 30, Node Attributes: {'membership': 'Officer'}
Node: 31, Node Attributes: {'membership': 'Officer'}
Node: 32, Node Attributes: {'membership': 'Officer'}
Node: 33, Node Attributes: {'membership': 'Officer'}

Das Knotenattribut membership bezieht sich auf die Gemeinschaft "Officer" oder "Mr. Hello" zu dem jeder Knoten gehört. Lassen Sie uns sie verwenden, um die Knoten im Diagramm farbig zu gestalten.

Dazu weisen wir den Knoten mit die blaue Farbe zu membership Etikett "Mr Hello" und rot diejenigen mit Etikett "Officer" in einer Liste color_map mit dem wir das Netzwerk visualisieren können nx.draw.

# Load the Karate Membership 
G: nx.Graph = nx.karate_club_graph()
# Get the node labels
labels = nx.get_node_attributes(G, 'membership')
# Map neighborhood labels to colours
color_map = ()
for node in G.nodes():
if labels(node) == 'Mr. Hello':
# Assign blue coloration for 'Mr. Hello'
color_map.append('blue')  
else:
# Assign pink coloration for 'Officer'
color_map.append('pink')  
# Visualize the graph
plt.determine(figsize=(8, 8))
pos = nx.spring_layout(G)  
nx.draw(G, pos, with_labels=True, node_color=color_map, font_size=12, font_weight='daring', node_size=500, cmap=plt.cm.rainbow)
plt.title("Zachary's Karate Membership Community with Floor Reality Communities")
plt.present()

Der Legende nach kam es zu einem Konflikt zwischen dem Ausbilder des Golf equipment, „Mr. Hallo“, und der Clubverwalter „Offizier“. Diese Spaltung führte schließlich dazu, dass sich der Verein in zwei verschiedene Gruppen aufspaltete, die sich jeweils um einen dieser Anführer drehten.

Indem wir diese Beziehungen als Netzwerk darstellen, können wir diese Aufteilung visuell erfassen und Muster und Cluster innerhalb der Daten aufdecken – Erkenntnisse, die bei Daten in herkömmlichen Tabellenformaten möglicherweise schwer zu erkennen sind.

Zentralität

Um die Struktur und Dynamik eines Netzwerks zu verstehen, ist es wichtig, die einflussreichsten oder strategisch positionierten Knoten zu identifizieren. Hier ist Zentralität Maßnahmen kommen ins Spiel, ein Schlüsselkonzept in der Netzwerkwissenschaft.

Es misst die Place von Knoten anhand ihrer Verbindungstypen und identifiziert Schlüsselknoten anhand bestimmter Kriterien. Zu den gängigen Maßnahmen gehören:

Diese Maßnahmen tragen dazu bei, wichtige Akteure oder Engpässe im Netzwerk aufzudecken und Einblicke in dessen Struktur/Dynamik zu geben.

import networkx as nx
import matplotlib.pyplot as plt
# Load the Karate Membership 
G = nx.karate_club_graph()
# Compute centrality measures
degree_centrality = nx.degree_centrality(G)
betweenness_centrality = nx.betweenness_centrality(G)
closeness_centrality = nx.closeness_centrality(G)
# high 5 nodes by centrality for every measure
top_degree_nodes = sorted(degree_centrality, key=degree_centrality.get, reverse=True)(:5)
top_betweenness_nodes = sorted(betweenness_centrality, key=betweenness_centrality.get, reverse=True)(:5)
top_closeness_nodes = sorted(closeness_centrality, key=closeness_centrality.get, reverse=True)(:5)
# high 5 nodes for every centrality measure
print("High 5 nodes by Diploma Centrality:", top_degree_nodes)
print("High 5 nodes by Betweenness Centrality:", top_betweenness_nodes)
print("High 5 nodes by Closeness Centrality:", top_closeness_nodes)
# high 5 nodes for Diploma Centrality
plt.determine(figsize=(8, 8))
pos = nx.spring_layout(G)  # Positioning of nodes
node_color = ('pink' if node in top_degree_nodes else 'skyblue' for node in G.nodes())
# draw high 5 nodes by diploma centrality
nx.draw(G, pos, with_labels=True, node_color=node_color, font_size=15, font_weight='daring', node_size=500)
plt.title("Karate Membership Community with High 5 Diploma Central Nodes")
plt.present()

High 5 nodes by Diploma Centrality: (33, 0, 32, 2, 1)
High 5 nodes by Betweenness Centrality: (0, 33, 32, 2, 31)
High 5 nodes by Closeness Centrality: (0, 2, 33, 31, 8)

Für Knoten 0 Und 3 Wir sehen, dass diese Knoten die zentralsten im Netzwerk sind, mit hoher Grad-, Zwischen- und Nähe-Zentralität.

Ihre zentrale Rolle lässt darauf schließen, dass es sich um intestine vernetzte Knotenpunkte handelt, die häufig als Brücken zwischen anderen Mitgliedern fungieren und in der Lage sind, andere im Netzwerk schnell zu erreichen. Diese Positionierung hebt sie als Schlüsselakteure hervor, die für den Ablauf und die Struktur des Netzwerks von Bedeutung sind.

Eine Group C ist eine Gruppe von Knoten (z. B. Einzelpersonen in einem sozialen Netzwerk, über Hyperlinks verbundene Webseiten usw.), die untereinander stärkere Verbindungen aufweisen als mit dem Relaxation des Netzwerks.

Im Hinblick auf eine visuelle Darstellung der Zentralität wenden wir den Girvan-Newman-Algorithmus auf dieses Diagramm an.

• Der Algorithmus generiert eine Reihe von Group-Splits, während er nach und nach Kanten mit der höchsten Betweenness-Zentralität entfernt.
• Wenn der Algorithmus zum ersten Mal ausgeführt wird, identifiziert er die bedeutendste Group-Abteilung.

from networkx.algorithms.neighborhood import girvan_newman
# Load the Karate Membership graph
G = nx.karate_club_graph()
# Apply Girvan-Newman neighborhood detection
comp = girvan_newman(G)
first_level_communities = subsequent(comp)
# Visualize the primary stage of communities
pos = nx.spring_layout(G)
plt.determine(figsize=(8, 8))
# Colour nodes by their neighborhood
node_colors = ('skyblue' if node in first_level_communities(0) else 'orange' for node in G.nodes())
nx.draw(G, pos, with_labels=True, node_color=node_colors, font_size=12, node_size=500)
plt.title("Karate Membership Community with Girvan-Newman Communities")
plt.present()
print("Detected Communities:", first_level_communities)

• Seit girvan_newman(G) gibt einen Iterator als zurück compruft subsequent(comp) ermöglicht es Ihnen, die erste Aufteilung, additionally die erste Aufteilung des Netzwerks in zwei Communities, abzurufen.

Vergleichen wir die erkannten Communities mit der tatsächlichen Knotenbezeichnung membership

print("Detected Communities:", first_level_communities)
# Print the precise communities (floor reality)
print("nActual Communities (Floor Reality):")
mr_hi_nodes = (node for node, label in labels.objects() if label == 'Mr. Hello')
officer_nodes = (node for node, label in labels.objects() if label == 'Officer')
print(f"Mr. Hello's Group: {mr_hi_nodes}")
print(f"Officer's Group: {officer_nodes}")

Detected Communities: (
{0, 1, 3, 4, 5, 6, 7, 10, 11, 12, 13, 16, 17, 19, 21}, 
{2, 8, 9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33}
)
Precise Communities (Floor Reality):
Mr. Hello's Group: (0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 16, 17, 19, 21)
Officer's Group: (9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33)

Die vom Girvan-Newman-Algorithmus erkannten Communities ähneln den tatsächlichen Mr. Hello- und Officer-Communitys, stimmen jedoch nicht genau überein. Dies liegt daran, dass der Girvan-Newman-Algorithmus das Netzwerk ausschließlich auf der Grundlage der Edge Betweenness-Zentralität unterteilt, ohne sich auf vordefinierte Group-Labels zu verlassen.

Dieser Ansatz ist besonders nützlich in unstrukturierten Datensätzen, in denen keine Beschriftungen vorhanden sind, da er sinnvolle Gruppierungen basierend auf den Struktureigenschaften des Netzwerks aufdeckt. Dies unterstreicht einen wichtigen Aspekt bei der Group-Erkennung: Es gibt keine strenge Definition dessen, was eine Group ausmacht.

Daher gibt es keinen einzigen „richtigen“ Weg, ein Netzwerk zu partitionieren. Verschiedene Methoden, die auf unterschiedlichen Metriken basieren, können zu unterschiedlichen Ergebnissen führen, die je nach Kontext wertvolle Erkenntnisse liefern.

Cliquen

Ein nützliches Konzept in Netzwerken ist die Clique. In der Netzwerkwissenschaft bezieht sich eine Clique auf eine Teilmenge von Knoten in einem Diagramm, bei der jeder Knoten mit jedem anderen Knoten in dieser Teilmenge verbunden ist. Das bedeutet, dass alle Mitglieder einer Clique direkte Beziehungen zueinander haben und eine eng verbundene Gruppe bilden. Cliquen können besonders nützlich sein, wenn man die Struktur komplexer Netzwerke untersucht, da sie häufig stark verbundene oder zusammenhängende Gruppen innerhalb eines größeren Programs darstellen.

Zum Beispiel in:

• In sozialen Netzwerken: Cliquen können Gruppen von Menschen darstellen, die sich kennen, etwa enge Freundeskreise oder Berufskollegen.
• In kollaborativen Netzwerken: In einem kollaborativen Netzwerk (z. B. Forschungskooperationen) können Cliquen Forscherteams hervorbringen, die gemeinsam an denselben Themen oder Projekten arbeiten.
• In biologischen Netzwerken: In biologischen Netzwerken können Cliquen funktionelle Gruppen von Proteinen oder Genen anzeigen, die innerhalb eines biologischen Prozesses eng interagieren.

Finden wir die größte Clique im Karate-Netzwerk. Wir werden die größte Gruppe von Menschen finden, die alle Verbindungen zueinander haben.

import networkx as nx
import matplotlib.pyplot as plt
# Load the Karate Membership graph
G = nx.karate_club_graph()
# Discover all cliques within the Karate Membership community
cliques = listing(nx.find_cliques(G))
# Discover the most important clique (the one with probably the most nodes)
largest_clique = max(cliques, key=len)
# Print the most important clique
print("Largest Clique:", largest_clique)
# Visualize the graph with the most important clique highlighted
plt.determine(figsize=(8, 8))
pos = nx.spring_layout(G)  # Format for node positions
nx.draw(G, pos, with_labels=True, node_color='skyblue', font_size=12, node_size=500)
# Spotlight the nodes within the largest clique
nx.draw_networkx_nodes(G, pos, nodelist=largest_clique, node_color='orange', node_size=500)
plt.title("Karate Membership Community with Largest Clique Highlighted")
plt.present()

Trotz der Herausforderungen bei der Definition von „Gemeinschaft“ in der Netzwerkwissenschaft bieten Cliquen ein konkretes und klar definiertes Konzept zur Identifizierung vollständig miteinander verbundener Gruppen und bieten aussagekräftige Einblicke in strukturierte und unstrukturierte Netzwerke.

Kürzester Weg

Ein weiteres interessantes Konzept in der Netzwerkwissenschaft ist Shortest Path. Der kürzeste Weg zwischen zwei Knoten in einem Diagramm bezieht sich auf die Kantenfolge, die die Knoten verbindet und gleichzeitig die Gesamtentfernung oder die Kosten minimiert, was je nach Anwendung auf unterschiedliche Weise interpretiert werden kann. Dieses Konzept spielt eine entscheidende Rolle in Bereichen wie Routing-Algorithmen, Netzwerkdesign, Transportplanung und sogar der Analyse sozialer Netzwerke.

NetworkX bietet mehrere Algorithmen zur Berechnung kürzester Pfade, z. B. den Dijkstra-Algorithmus für gewichtete Diagramme und die Breadth-First Search (BFS) für ungewichtete Diagramme.

Schauen wir uns ein Beispiel an: Wir erstellen einen synthetischen Datensatz, in dem Knoten Stationen darstellen und die Kanten Verbindungen zwischen den Stationen darstellen.

• Wir werden auch die gewichtete Kantenzeit hinzufügen, die die Zeit darstellt, die benötigt wird, um von einer Station zur nächsten zu gelangen.

import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt
# Simulate loading a CSV file (actual instance would load an precise CSV file)
# Outline a extra intensive set of stations and journey instances between them
knowledge = {
'station_id': ('A', 'A', 'B', 'B', 'C', 'C', 'D', 'D', 'E', 'E', 'F', 'F', 'G', 'G', 'H'),
'connected_station': ('B', 'C', 'A', 'C', 'A', 'D', 'C', 'E', 'B', 'F', 'D', 'G', 'E', 'H', 'F'),
'time': (10, 20, 10, 15, 20, 10, 5, 15, 10, 25, 10, 5, 15, 10, 30)  # Journey instances in minutes
}
# Create a DataFrame
df = pd.DataFrame(knowledge)
# Create a graph from the DataFrame
G = nx.Graph()
# Add edges to the graph (station connections with weights as journey instances)
for index, row in df.iterrows():
G.add_edge(row('station_id'), row('connected_station'), weight=row('time'))
# Draw the graph
plt.determine(figsize=(8, 8))
pos = nx.spring_layout(G)  # Format for node positions
nx.draw(G, pos, with_labels=True, node_size=500, node_color='skyblue', font_size=12, font_weight='daring')
# Draw edge weights (journey instances)
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.title("Expanded Transportation Community with Journey Occasions")
plt.present()

In diesem Beispiel verwenden wir den Dijkstra-Algorithmus, um den kürzesten Weg von Station A zu Station H zu berechnen, wobei die Kantengewichte die Reisezeiten darstellen. Der kürzeste Weg und seine Gesamtfahrzeit werden ausgedruckt, und der Weg wird zur Visualisierung im Diagramm rot hervorgehoben, wobei Kantengewichtungen angezeigt werden, um die Fahrzeiten zwischen Stationen anzuzeigen.

# Compute the shortest path utilizing Dijkstra's algorithm (contemplating the journey time as weight)
supply = 'A'
goal = 'H'
shortest_path = nx.shortest_path(G, supply=supply, goal=goal, weight='weight')
path_length = nx.shortest_path_length(G, supply=supply, goal=goal, weight='weight')
# Print the shortest path and its size
print(f"Shortest path from {supply} to {goal}: {shortest_path}")
print(f"Whole journey time from {supply} to {goal}: {path_length} minutes")
# Visualize the shortest path on the graph
plt.determine(figsize=(8, 8))
nx.draw(G, pos, with_labels=True, node_size=500, node_color='skyblue', font_size=12, font_weight='daring')
# Spotlight the shortest path in pink
edges_in_path = ((shortest_path(i), shortest_path(i + 1)) for i in vary(len(shortest_path) - 1))
nx.draw_networkx_edges(G, pos, edgelist=edges_in_path, edge_color='pink', width=2)
# Draw edge weights (journey instances)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.title(f"Shortest Path from {supply} to {goal} with Journey Time {path_length} minutes")
plt.present()

Shortest path from A to H: ('A', 'B', 'E', 'G', 'H')
Whole journey time from A to H: 45 minutes

Der Algorithmus berechnet sowohl die kürzeste Route als auch deren Gesamtfahrzeit und zeigt diese an. Der kürzeste Weg zwischen A und H wird im Diagramm rot hervorgehoben, wobei die Kantengewichtungen die Zeit zwischen den einzelnen verbundenen Stationen anzeigen, was insgesamt 45 ergibt.

Obwohl es sich hierbei um eine einfache Berechnung handelte, haben Algorithmen für kürzeste Wege vielfältige Anwendungsmöglichkeiten. Im Transportwesen optimieren sie Routen und verkürzen die Reisezeit; In der digitalen Kommunikation leiten sie Daten effizient weiter. Sie sind in der Logistik unverzichtbar, um Kosten zu minimieren, in Lieferketten für pünktliche Lieferungen und in sozialen Netzwerken, um die Nähe zwischen Einzelpersonen zu messen. Das Verständnis kürzester Wege ermöglicht datengesteuerte Entscheidungen in allen Bereichen – von der Stadtplanung bis zur Netzwerkinfrastruktur – und ist damit ein wichtiges Werkzeug für die effiziente Navigation komplexer Systeme.

Danke fürs Lesen

Wir haben mit NetworkX mehrere grundlegende Konzepte der Netzwerkwissenschaft untersucht, wie z. B. Algorithmen für kürzeste Wege, Group-Erkennung und die Leistungsfähigkeit der Graphentheorie zur Modellierung und Analyse komplexer Systeme.

Wenn Sie weiter lernen möchten, habe ich unten ein paar Hyperlinks platziert :). Wenn Sie tiefer in die Group-Erkennungsalgorithmen einsteigen möchten, schauen Sie sich die CDLib-Bibliothek an.

1. Networkx-Tutorial
2. CDLib, eine Bibliothek zur Group-Erkennung

NOTIZ: Die Berechnung komplexer Metriken und Kennzahlen in Diagrammen kann oft mehrdeutig oder sogar irreführend sein. Da so viele potenzielle Kennzahlen verfügbar sind, ist es leicht, Zahlen zu generieren, die möglicherweise keinen aussagekräftigen Wert haben oder die wahre Struktur des Netzwerks falsch darstellen. Die Auswahl der richtigen Kennzahlen erfordert sorgfältige Überlegungen, da nicht alle Kennzahlen relevante Erkenntnisse für jede Artwork von Netzwerkanalyse liefern. Wenn dies Anklang findet, finden Sie hier weitere Informationen: Statistische Inferenz verknüpft Daten und Theorie in der Netzwerkwissenschaft

Referenzen