Exercício 2 - Caminhos Médios

Computar, para os mesmos gráficos do Exercício 1, a média dos caminhos mais curtos.



In [14]:

    
import networkx as nx
import network_analysis_utils as nau

# Funções disponíveis:
#
#  - nau.facebook_nx_graph(): Obtém o grafo Networkx do facebook
#  
#  - nau.random_nx_graph(): Obtém o grafo Networkx randômico
#
# Obs: o prefixo 'nx' indica o uso da Networkx, a lib de grafos utilizada nesse exercício

Dica: está permitido o uso da função da distância de caminhos mais curtos da Networkx

Requisito: não está permitido o uso da função da média da distância dos caminhos mais curtos da Networkx



In [44]:

    
import itertools

def avg_shortest_paths(nx_graph):
    """ Retorna a média (como valor escalar) dos caminhos mais curtos no grafo"""
    nodes = nx_graph.nodes()
    len_nodes = len(nodes)
    summation = sum( [ nx.shortest_path_length(nx_graph, s, t)
                      for s, t in itertools.product(nodes, nodes) 
                      if s != t] )
    return float(summation) / (len_nodes * (len_nodes-1))



In [ ]:

    
facebook_graph = nau.facebook_nx_graph()
random_graph = nau.random_nx_grap()

print '[You] facebook graph average shortest paths: %.2f ' % avg_shortest_paths( facebook_graph )
print '[You] random graph average shortest paths: %.2f ' % avg_shortest_paths( random_graph )
print '[Networkx] facebook graph average shortest paths: %.2f ' % nx.average_shortest_path_length( facebook_graph )
print '[Networkx] random graph average shortest paths: %.2f ' % nx.average_shortest_path_length( random_graph )



In [ ]: