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

Qu'est-ce que NetworkX

Page officielle

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

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

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.1.png

u=0.5 u=0.5.png

u=0.9 u=0.9.png

Recommended Posts

Créer un voisin le plus proche de connexion avec NetworkX
Dessinez un graphique avec NetworkX
Créer une page d'accueil avec django
Créer un répertoire avec python
Dessinez un graphique avec networkx
Créez un environnement virtuel avec Python!
Créez un stepper de poisson avec numpy.random
Créer un téléchargeur de fichiers avec Django
Créer un décorateur de fonction Python avec Class
Créez une image factice avec Python + PIL.
[Python] Créez un environnement virtuel avec Anaconda
Créons un groupe gratuit avec Python
Créer un gros fichier texte avec shellscript
Créez un système stellaire avec le script Blender 2.80
Créer une machine virtuelle avec un fichier YAML (KVM)
Créez une application Web simple avec Flask
Créer un compteur de fréquence de mots avec Python 3.4
Créer un service Web avec Docker + Flask
Créer un référentiel privé avec AWS CodeArtifact
Créez un compteur de voiture avec Raspberry Pi
Créez une image diabolique avec le script de Blender
Créer une matrice avec PythonGUI (zone de texte)
Créer un graphique avec des bordures supprimées avec matplotlib
Créez un environnement Python 3 avec pyenv sur Mac et affichez des graphiques Network X
Créer un fichier exécutable GUI créé avec tkinter
Créer un LINE BOT avec Minette pour Python
Créez une interface utilisateur de jeu à partir de zéro avec pygame2!
Créer un fichier PDF avec une taille de page aléatoire
Créer une page qui se charge indéfiniment avec python
[Note] Créez une classe de fuseau horaire sur une ligne avec python
Vous pouvez facilement créer une interface graphique même avec Python
Créer un environnement de construction python3 avec Sublime Text3
Créer un babillard avec Heroku, Flask, SQL Alchemy
Créez un tableau de bord pour les appareils réseau avec Django!
Créer une matrice avec PythonGUI (combo tkinter)
Créer une barre de couleurs avec Python + Qt (PySide)
Étapes pour créer un bot Twitter avec Python
Créer un arbre de décision à partir de 0 avec Python (1. Présentation)
Créer une nouvelle page en confluence avec Python
Créer un widget avec une couleur spécifiée avec Python + Qt (PySide)
Procédure de création d'application multi-plateforme avec kivy
Créez une application Hello World avec un seul fichier avec django
Créer un fichier au format Photoshop (.psd) avec python
Facile à créer une application console Python avec Click
Créer un cylindre avec une sortie de fichier open3d + STL
Créer un serveur "Hello World" (HTTP) dans Tornado
Créez un outil de traduction avec Translate Toolkit
Créer une table avec le notebook IPython
[Python] Dessinez un diagramme de relation de balises Qiita avec NetworkX
Créer une application Todo avec Django REST Framework + Angular
Créez une application graphique native avec Py2app et Tkinter
Comment créer un sous-menu avec le plug-in [Blender]
Essayez de créer un Checkbutton dynamiquement avec Tkinter en Python
Créez un environnement virtuel avec Anaconda installé via Pyenv
[Python] Générer ValueObject avec un constructeur complet à l'aide de classes de données
Essayez de créer une application Todo avec le framework Django REST
Pourquoi ne pas créer facilement une table élégante avec Python?
Créez un environnement de développement python avec vagrant + ansible + fabric