Prerrequisito : Introducción a las Redes Sociales , Barabasi Albert Graph
En las redes sociales, existe un fenómeno llamado Rico cada vez más rico, también conocido como Apego preferencial. En el apego preferencial, una persona que ya es rica obtiene más y más y una persona que tiene menos obtiene menos. Esto se conoce como el fenómeno de los ricos cada vez más ricos o apego preferencial.
Por ejemplo, suponga que hay algunos estudiantes en una clase y cada estudiante es amigo de algunos estudiantes, lo que se llama su grado, es decir, el grado de un estudiante es la cantidad de amigos que tiene. Ahora el estudiante con un título superior es rico y el estudiante con un título bajo es pobre. Ahora supongamos que llega un nuevo estudiante a la clase y tiene que hacer m amigos, por lo que seleccionará estudiantes con un grado más alto y se hará amigo de ellos, lo que aumenta el grado de riqueza. Esto se llama Rico cada vez más rico o Vínculo preferencial .
El modelo Barabasi Albert es la implementación del apego preferencial.
Lógica: a continuación se muestra la lógica detrás del modelo Barabasi Albert:
- Tome un gráfico aleatorio con n 0 Nodes y conéctelos al azar con la condición de que cada uno tenga al menos 1 enlace.
- En cada momento agregamos un nuevo Node n que es menor o igual a n 0 enlaces que conectarán el nuevo Node a n Nodes que ya están en la red.
- Ahora la probabilidad de que un Node se conecte a un Node en particular dependerá de su grado. (Adjunto preferencial).
Enfoque: a continuación se detallan los pasos para implementar el modelo Barabasi Albert:
- Tome un gráfico con n Nodes.
- Tome m del usuario, es decir, el número de aristas que se conectarán al nuevo Node.
- Tome m0, es decir, el número inicial de Nodes tal que m<=m0.
- Ahora agregue los Nodes n-m0.
- Ahora agregue bordes a estos Nodes n-m0 de acuerdo con el accesorio preferencial.
A continuación se muestra la implementación del modelo Barabasi Albert.
Python3
import networkx as nx
import random
import matplotlib.pyplot as plt
def display(g, i, ne):
pos = nx.circular_layout(g)
if i == '' and ne == '':
new_node = []
rest_nodes = g.nodes()
new_edges = []
rest_edges = g.edges()
else:
new_node = [i]
rest_nodes = list(set(g.nodes()) - set(new_node))
new_edges = ne
rest_edges = list(set(g.edges()) - set(new_edges) - set([(b, a) for (a, b) in new_edges]))
nx.draw_networkx_nodes(g, pos, nodelist=new_node, node_color='g')
nx.draw_networkx_nodes(g, pos, nodelist=rest_nodes, node_color='r')
nx.draw_networkx_edges(g, pos, edgelist=new_edges, style='dashdot')
nx.draw_networkx_edges(g, pos, edgelist=rest_edges,)
plt.show()
def barabasi_add_nodes(g, n, m0):
m = m0 - 1
for i in range(m0 + 1, n + 1):
g.add_node(i)
degrees = nx.degree(g)
node_prob = {}
s = 0
for j in degrees:
s += j[1]
print(g.nodes())
for each in g.nodes():
node_prob[each] = (float)(degrees[each]) / s
node_probabilities_cum = []
prev = 0
for n, p in node_prob.items():
temp = [n, prev + p]
node_probabilities_cum.append(temp)
prev += p
new_edges = []
num_edges_added = 0
target_nodes = []
while (num_edges_added < m):
prev_cum = 0
r = random.random()
k = 0
while (not (r > prev_cum and r <= node_probabilities_cum[k][1])):
prev_cum = node_probabilities_cum[k][1]
k = k + 1
target_node = node_probabilities_cum[k][0]
if target_node in target_nodes:
continue
else:
target_nodes.append(target_node)
g.add_edge(i, target_node)
num_edges_added += 1
new_edges.append((i, target_node))
print(num_edges_added, ' edges added')
display(g, i, new_edges)
return g
def plot_deg_dist(g):
all_degrees = []
for i in nx.degree(g):
all_degrees.append(i[1])
unique_degrees = list(set(all_degrees))
unique_degrees.sort()
count_of_degrees = []
for i in unique_degrees:
c = all_degrees.count(i)
count_of_degrees.append(c)
print(unique_degrees)
print(count_of_degrees)
plt.plot(unique_degrees, count_of_degrees, 'ro-')
plt.xlabel('Degrees')
plt.ylabel('Number of Nodes')
plt.title('Degree Distribution')
plt.show()
N = 10
m0 = random.randint(2, N / 5)
g = nx.path_graph(m0)
display(g, '', '')
g = barabasi_add_nodes(g, N, m0)
plot_deg_dist(g)
Producción:
Enter the value of n: 10 3 [0, 1, 3] 1 edges added [0, 1, 3, 4] 1 edges added [0, 1, 3, 4, 5] 1 edges added [0, 1, 3, 4, 5, 6] 1 edges added [0, 1, 3, 4, 5, 6, 7] 1 edges added [0, 1, 3, 4, 5, 6, 7, 8] 1 edges added [0, 1, 3, 4, 5, 6, 7, 8, 9] 1 edges added [0, 1, 3, 4, 5, 6, 7, 8, 9, 10] 1 edges added [1, 2, 3, 6] [7, 1, 1, 1]
Gráfico inicial con m0 Nodes
Node final con nuevo Node agregado
Gráfico de distribución
Publicación traducida automáticamente
Artículo escrito por sankalpsharma424 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA