Requisito previo: conceptos básicos de Python , conceptos básicos de NetworkX
Vamos a dividir los Nodes del grafo en dos o más comunidades usando el método de fuerza bruta. El método de fuerza bruta significa que probaremos cada división de Nodes en comunidades y verificaremos si las comunidades están divididas correctamente o no. Usaremos un método de fuerza bruta para esta tarea.
Algoritmo:
- Cree un gráfico de N Nodes y sus bordes o tome un gráfico incorporado como un gráfico con barra.
- Ahora tome dos listas como FirstCommunity y SecondCommunity.
- Ahora comience a colocar Nodes en comunidades como colocar el primer Node en FirstCommunity y descansar N-1 Nodes en SecondCommunity y verifique sus bordes inter e intra.
- Ahora haremos combinaciones usando itertools .
- Repita los pasos 3 y 4 para cada combinación.
- Ahora verifique qué división es la mejor tomando la proporción de bordes intracomunitarios/cantidad de bordes intercomunitarios.
- Ahora encuentre el valor de FirstCommunity y SecondCommunity con la proporción máxima e imprima ese valor.
A continuación se muestra la implementación.
Python3
import networkx as nx
import itertools
def communities_using_brute(gfg):
nodes = gfg.nodes()
n = gfg.number_of_nodes()
first_community = []
for i in range(1, n//2 + 1):
c = [list(a) for a in itertools.combinations(nodes, i)]
first_community.extend(c)
second_community = []
for i in range(len(first_community)):
b = list(set(nodes)-set(first_community[i]))
second_community.append(b)
# Which division is best...
intra_edges1 = []
intra_edges2 = []
inter_edges = []
# ratio of number of intra/number of inter
# community edges
ratio = []
for i in range(len(first_community)):
intra_edges1.append(gfg.subgraph(first_community[i]).number_of_edges())
for i in range(len(second_community)):
intra_edges2.append(gfg.subgraph(second_community[i]).number_of_edges())
e = gfg.number_of_edges()
for i in range(len(first_community)):
inter_edges.append(e-intra_edges1[i]-intra_edges2[i])
# Calculate the Ratio
for i in range(len(first_community)):
ratio.append((float(intra_edges1[i]+intra_edges2[i]))/inter_edges[i])
maxV=max(ratio)
mindex=ratio.index(maxV)
print('[ ', first_community[mindex], ' ] , [ ', second_community[mindex], ' ]')
# Example graph
gfg=nx.barbell_graph(5, 0)
communities_using_brute(gfg)
Producción:
[ [0,1,2,3,4] ] , [ [8,9,5,6,7] ]
Publicación traducida automáticamente
Artículo escrito por sankalpsharma424 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA