[PYTHON] Create a Connecting Nearest Neighbor with NetworkX
I want to create a network with the connecting Nearest Neighbor algorithm a while ago! When I was consulted, I remember that I couldn't find an example of trying using Python and a package such as NetworkX even if I looked around, so I will post it. I didn't create it by myself, but I made various changes to make it easier to understand (I think). If you have any improvements, please let me know.
environment
- python 3.6.9
- networkx 2.4
- matplotlib 3.2.1 I used Google Colab
What is NetworkX
I don't talk much because my seniors have written a lot of useful things.
I studied while referring to.
What is Connecting Nearest Neighbor
A model of network generation proposed by Vazquez. The original is Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations
I'm not familiar with network-related research, so I'm sorry. In rewriting this time
- Generating a graph using the Connecting Nearest Neighbor model
- Visualize network data generated by Ruby with d3.js
I was allowed to refer to.
algorithm
- Determine the parameter u
- Repeat the following until you reach the required number of nodes
- Create a new node with a probability of 1-u. Randomly select one existing node and connect a new node with a real link. A potential link is established between all the nodes connected to the selected node by the actual link and the new node.
- With a probability of u, randomly select a potential link and change it to a real link
program
CNN class
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:
#Add a new node with probability u
if random.random() < 1 - self.u:
new_node = len(list(self.graph.nodes))
self.graph.add_node(new_node)
#Randomly select nodes that already exist in the network
node_list = list(self.graph.nodes)
node_list.remove(new_node)
selected_node = random.choice(node_list)
# selected_new to all adjacent nodes of node_Connect the potential edge with node
neighbor_nodes = self.get_neighbors(selected_node)
for nn in neighbor_nodes:
self.graph.add_edge(nn, new_node, attribute="potential")
#Connect the real edge
self.graph.add_edge(selected_node, new_node, attribute="real")
#Probability 1-Randomly select a potential link with u and convert it to a real edge
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):
'''
The value of the edge is attr(potenntial or real)Returns a list of edges
'''
# {(node, node):attribute}Get the 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):
'''
node and real_Returns a list of nodes connected by edge
'''
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()
Run
cnn = CNN(node_num=100, u=0.9)
cnn.make_cnn()
cnn.plot_graph()
Then you will get this figure.
u=0.1
u=0.5
u=0.9
Recommended Posts