[PYTHON] Erstellen Sie mit NetworkX einen verbindenden nächsten Nachbarn

Ich möchte vor einiger Zeit ein Netzwerk mit dem verbindenden Nearest Neighbor-Algorithmus erstellen! Als ich konsultiert wurde, erinnere ich mich, dass ich selbst nach dem Durchsuchen kein Beispiel für die Verwendung von Python und einem Paket wie NetworkX finden konnte, also werde ich es veröffentlichen. Ich habe es nicht selbst erstellt, aber ich habe verschiedene Änderungen vorgenommen, um das Verständnis zu erleichtern (glaube ich). Wenn Sie Verbesserungen haben, lassen Sie es mich bitte wissen.

Umgebung

• python 3.6.9
• networkx 2.4
• matplotlib 3.2.1 Ich habe Google Colab verwendet

Was ist NetworkX?

Offizielle Seite

Ich rede nicht viel, weil meine Senioren viele nützliche Dinge geschrieben haben.

• Graphentheorie und NetworkX
• [Python] Zusammenfassung der grundlegenden Verwendung von Network X 2.0

Ich habe unter Bezugnahme studiert.

Was verbindet den nächsten Nachbarn?

Ein von Vazquez vorgeschlagenes Modell der Netzwerkgenerierung. Das Original ist Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations

Ich bin damit nicht vertraut, weil ich keine netzwerkbezogene Forschung betrieben habe. Es tut mir leid. Diesmal beim Umschreiben

• Erstellen eines Diagramms mit dem Modell "Connecting Nearest Neighbor"
• Von Ruby mit d3.js generierte Netzwerkdaten visualisieren

Ich durfte mich beziehen.

Algorithmus

1. Bestimmen Sie den Parameter u
2. Wiederholen Sie die folgenden Schritte, bis Sie die erforderliche Anzahl von Knoten erreicht haben
3. Erstellen Sie einen neuen Knoten mit einer 1-u-Chance. Wählen Sie zufällig einen vorhandenen Knoten aus und verbinden Sie einen neuen Knoten mit einer echten Verbindung. Eine mögliche Verbindung wird zwischen allen Knoten hergestellt, die durch die tatsächliche Verbindung mit dem ausgewählten Knoten verbunden sind, und dem neuen Knoten.
4. Wählen Sie mit einer Wahrscheinlichkeit von u zufällig einen potenziellen Link aus und ändern Sie ihn in einen echten Link

Programm

CNN-Klasse

import networkx as nx
import random
import matplotlib.pyplot as plt


class CNN:
    def __init__(self, node_num, u, seed = 0):
        self.graph = nx.Graph()
        self.node_num = node_num
        self.u = u
        random.seed(seed)
        self.make_cnn()
        
    def make_cnn(self):
        self.graph.add_node(0)
        while len(list(self.graph.nodes)) < self.node_num:
            #Fügen Sie einen neuen Knoten mit der Wahrscheinlichkeit u hinzu
            if random.random() < 1 - self.u:
                new_node = len(list(self.graph.nodes))
                self.graph.add_node(new_node)
                #Wählen Sie zufällig Knoten aus, die bereits im Netzwerk vorhanden sind
                node_list = list(self.graph.nodes)
                node_list.remove(new_node)
                selected_node = random.choice(node_list)
                # selected_neu für alle benachbarten Knoten des Knotens_Verbinden Sie die potenzielle Kante mit dem Knoten
                neighbor_nodes = self.get_neighbors(selected_node)
                for nn in neighbor_nodes:
                    self.graph.add_edge(nn, new_node, attribute="potential")
                #Verbinden Sie die echte Kante
                self.graph.add_edge(selected_node, new_node, attribute="real")
            #Wahrscheinlichkeit 1-Wählen Sie zufällig eine mögliche Verknüpfung mit u aus und konvertieren Sie sie in eine echte Kante
            else:
                potential_edge_list = self.get_attribute_edgelist("potential")
                if len(potential_edge_list) > 0:
                    node_a, node_b = random.choice(potential_edge_list)
                    self.graph.edges[node_a, node_b]["attribute"] = "real"
                    

    def get_attribute_edgelist(self, attr):
        '''
Der Wert der Kante ist attr(potenziell oder real)Gibt eine Liste von Kanten zurück
        '''
        # {(node, node):Attribut}Holen Sie sich das Diktat
        edge_dict = nx.get_edge_attributes(self.graph, "attribute")
        attr_edgelist = []
        for edge, attribute in edge_dict.items():
            if attribute == attr:
                attr_edgelist.append(edge)
        return attr_edgelist
                
    def get_neighbors(self, node):
        '''
Knoten und real_Gibt eine Liste der durch Edge verbundenen Knoten zurück
        '''
        edgelist = self.get_attribute_edgelist("real")
        nodelist = []
        for node_a, node_b in edgelist:
            if node_a == node:
                nodelist.append(node_b)
            elif node_b == node:
                nodelist.append(node_a)
        return nodelist
    
    def plot_graph(self):
        plt.figure(figsize=(15, 10), facecolor="w")
        pos = nx.spring_layout(self.graph, k=1.0)
        real_edge_list = self.get_attribute_edgelist("real")
        nx.draw_networkx_nodes(self.graph,
                               pos,
                               node_color="r")
        nx.draw_networkx_edges(self.graph, pos, edgelist=real_edge_list)
        nx.draw_networkx_labels(self.graph, pos, font_size=10)
        
        plt.axis("off")
        plt.show()

Lauf

cnn = CNN(node_num=100, u=0.9)
cnn.make_cnn()
cnn.plot_graph()

Dann erhalten Sie diese Zahl.

u=0.1

u=0.5

u=0.9