[PYTHON] Créer un voisin le plus proche de connexion avec NetworkX

Je veux créer un réseau avec l'algorithme de connexion le plus proche voisin il y a quelque temps! Quand j'ai été consulté, je me souviens que je n'ai pas trouvé d'exemple pour essayer d'utiliser Python et un package tel que NetworkX même après avoir cherché autour, donc je le posterai. Je ne l'ai pas créé moi-même, mais j'ai apporté diverses modifications pour le rendre plus facile à comprendre (je pense). Si vous avez des améliorations, veuillez me le faire savoir.

environnement

• python 3.6.9
• networkx 2.4
• matplotlib 3.2.1 J'ai utilisé Google Colab

Qu'est-ce que NetworkX

Page officielle

Je ne parle pas beaucoup parce que mes aînés ont écrit beaucoup de choses utiles.

• Théorie des graphes et NetworkX
• [Python] Résumé de l'utilisation de base de Network X 2.0

J'ai étudié en faisant référence à.

Qu'est-ce que la connexion du voisin le plus proche

Un modèle de génération de réseau proposé par Vazquez. L'original est Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations

Je ne suis pas au courant car je ne faisais pas de recherche sur le réseau. Je suis désolé. En réécriture cette fois

• Génération d'un graphique à l'aide du modèle de connexion du voisin le plus proche
• Visualisez les données réseau générées par Ruby avec d3.js

J'ai été autorisé à faire référence.

algorithme

1. Déterminez le paramètre u
2. Répétez ce qui suit jusqu'à ce que vous atteigniez le nombre requis de nœuds
3. Créez un nouveau nœud avec une chance de 1 u. Sélectionnez au hasard un nœud existant et connectez un nouveau nœud avec un lien réel. Un lien potentiel est établi entre tous les nœuds connectés au nœud sélectionné par le lien réel et le nouveau nœud.
4. Avec une probabilité de u, sélectionnez au hasard un lien potentiel et changez-le en lien réel

programme

Classe CNN

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:
            #Ajouter un nouveau nœud avec la probabilité u
            if random.random() < 1 - self.u:
                new_node = len(list(self.graph.nodes))
                self.graph.add_node(new_node)
                #Sélectionnez au hasard les nœuds qui existent déjà dans le réseau
                node_list = list(self.graph.nodes)
                node_list.remove(new_node)
                selected_node = random.choice(node_list)
                # selected_nouveau pour tous les nœuds adjacents du nœud_Connectez le bord potentiel avec le nœud
                neighbor_nodes = self.get_neighbors(selected_node)
                for nn in neighbor_nodes:
                    self.graph.add_edge(nn, new_node, attribute="potential")
                #Connectez le vrai bord
                self.graph.add_edge(selected_node, new_node, attribute="real")
            #Probabilité 1-Sélectionnez au hasard un lien potentiel avec u et convertissez-le en véritable avantage
            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):
        '''
La valeur de l'arête est attr(potentiel ou réel)Renvoie une liste d'arêtes
        '''
        # {(node, node):attribut}Obtenez le dict
        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):
        '''
nœud et réel_Renvoie une liste de nœuds connectés par arête
        '''
        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()

Courir

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

Ensuite, vous obtiendrez ce chiffre.

u=0.1

u=0.5

u=0.9