Prerrequisito: Introducción a las Redes Sociales
La descomposición de K-shell es el método en el que podemos dividir los Nodes en función del número de su grado, como Nodes con grado 1 en un cubo, etc.
Considere un ejemplo, suponga que hay n Nodes y aplica la descomposición de k-shell en él. Entonces, los Nodes con el grado 1 estarán en el depósito 1, luego veremos que después de desconectar estos Nodes, ¿queda algún Node con el grado 1? Si es así, los agregaremos en el depósito 1 y nuevamente verificaremos y repetiremos estos pasos para el grado 2, 3 y así sucesivamente y colóquelos en bucket2 , bucket3 , etc.
Gráfico inicial con 7 Nodes
En el gráfico anterior, primero colocaremos los Nodes con grado 1 en el depósito 1, es decir, los Nodes 3 y 7. Después de eso, eliminaremos los Nodes 3 y 7 y comprobaremos si queda algún Node con grado 1, es decir, el Node 6. Ahora lo haremos elimine el Node 6 y verifique que quede cualquier Node de grado 1, que es el Node 5. Entonces, eliminaremos el Node 5 y nuevamente verificaremos, pero no queda ningún Node con grado 1, por lo que ahora buscaremos Nodes con grado 2 que son Nodes 1, 2 y 4 y ahora queda un Node en el gráfico. Así cubo1 = [3, 7, 6, 5] y cubo2 = [1, 2, 4] .
A continuación se muestra la implementación de la descomposición de K-shell en una red social:
Python3
# Import required modules import networkx as nx import matplotlib.pyplot as plt # Check if there is any node left with degree d def check(h, d): f = 0 # there is no node of deg <= d for i in h.nodes(): if (h.degree(i) <= d): f = 1 break return f # Find list of nodes with particular degree def find_nodes(h, it): set1 = [] for i in h.nodes(): if (h.degree(i) <= it): set1.append(i) return set1 # Create graph object and add nodes g = nx.Graph() g.add_edges_from( [(1, 2), (1, 9), (3, 13), (4, 6), (5, 6), (5, 7), (5, 8), (5, 9), (5, 10), (5, 11), (5, 12), (10, 12), (10, 13), (11, 14), (12, 14), (12, 15), (13, 14), (13, 15), (13, 17), (14, 15), (15, 16)]) # Copy the graph h = g.copy() it = 1 # Bucket being filled currently tmp = [] # list of lists of buckets buckets = [] while (1): flag = check(h, it) if (flag == 0): it += 1 buckets.append(tmp) tmp = [] if (flag == 1): node_set = find_nodes(h, it) for each in node_set: h.remove_node(each) tmp.append(each) if (h.number_of_nodes() == 0): buckets.append(tmp) break print(buckets) # Illustrate the Social Network # in the form of a graph nx.draw(g, with_labels=1) plt.show()
Producción:
[[2, 3, 4, 7, 8, 17, 16, 1, 6, 9], [11, 5, 10, 13, 12, 14, 15]]
Gráfico con 17 Nodes
Publicación traducida automáticamente
Artículo escrito por sankalpsharma424 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA