ps2-6.py

medici.py

# Reference:
# http://networkx.github.io/documentation/networkx-1.9.1/
# reference/algorithms.centrality.html

import operator
import networkx as nx
import pandas as pd
import matplotlib.pyplot as plt
import itertools

families = ["Acciaiuoli", "Albizzi", "Barbadori", "Bischeri", "Castellani",
            "Ginori", "Guadagni", "Lamberteschi", "Medici", "Pazzi",
            "Peruzzi", "Pucci", "Ridolfi", "Salviati", "Strozzi",
            "Tornabuoni"]

relationships = [[8, 9], [5,6,8], [4,8], [6,10,14], [2,10,14],
                 [1], [1,3,7,15], [6], [0,1,2,12,13,15], [13],
                 [3,4,14], [], [8,14,15], [8,9], [3,4,10,12],
                 [6,8,12]]

def draw_graph(vertices, edges):
    G = nx.Graph()
    G.add_nodes_from(vertices)

    for idx, edge in enumerate(edges):
        for dest in list(edge):
            G.add_edge(families[idx], families[dest])

    return G

def descending(node_value_dict):
    return sorted(node_value_dict.iteritems(),
                  key=operator.itemgetter(1),
                  reverse=True)


def comb_small_networks(vertices, edges, n):
    vertices_list = []
    edges_list = []
    for combi in itertools.combinations(vertices, n):
        vertices_index = []
        for vertex in combi:
            vertices_index.append(vertices.index(vertex))

        rel_set = []
        for index in vertices_index:
            remain = set(edges[index]).intersection(set(vertices_index))
            rel_set.append(list(remain))

        vertices_list.append(vertices_index)
        edges_list.append(rel_set)

    not_empty_vertices_list = []
    not_empty_edges_list = []
    for index, edge_list in enumerate(edges_list):
        if len([edge for edges in edge_list for edge in edges]) != 0:
            not_empty_vertices_list.append(vertices_list[index])
            not_empty_edges_list.append(edges_list[index])

    return not_empty_vertices_list, not_empty_edges_list

def find_max_degree(vertices, edges, n=2, centrality_type="degree"):
    max_val = 0
    max_vertice_list = []
    max_edges_list = []
    vertice_lists, edges_lists = comb_small_networks(vertices, edges, n)
    for index, vertice_list in enumerate(vertice_lists):
        g = draw_graph(vertice_list, edges_lists[index])

        if centrality_type == "degree":
            centrality = nx.degree_centrality(g)
        elif centrality_type == "eigenvector":
            centrality = nx.eigenvector_centrality(g)
        elif centrality_type == "betweenness":
            centrality = nx.betweenness_centrality(g)
        elif centrality_type == "closeness":
            centrality = nx.closeness_centrality(g)

        if max(centrality.values()) > max_val:
            max_val = max(centrality.values())
            max_vertice_list = vertice_list
            max_edges_list = edges_lists[index]

    return max_val, max_vertice_list


if __name__=="__main__":
    #centrality_types = ["degree", "eigenvector", "betweenness", "closeness"]
    centrality_types = ["degree", "betweenness", "closeness"]
    for centrality_type in centrality_types:
        print "===type:", centrality_type
        for i in range(2, 8):
            print "i:",
            print i, find_max_degree(families, relationships, i, centrality_type)
    #g = draw_graph(families, relationships)

    """
    s_dc = pd.Series(nx.degree_centrality(g), name="Degree")
    s_ec = pd.Series(nx.eigenvector_centrality(g), name="Eigenvector")
    s_bc = pd.Series(nx.betweenness_centrality(g), name="Betweenness")
    s_cc = pd.Series(nx.closeness_centrality(g), name="Closeness")

    df = pd.concat([s_dc, s_ec, s_bc, s_cc], axis=1)
    df.columns = ["Degree", "Eigen", "Betweenness", "Closeness"]
    plot = df.plot()
    fig = plot.get_figure()
    fig.savefig("centrality.png")
    """

ps2-6.py

from operator import itemgetter
from itertools import permutations
import networkx as nx

def full_degree_sequences(n):
    """
    n: number of vertex
    """

    first = []
    for i in range(1, n+1):
        first.extend([j for j in range(1, n)])

    return set(permutations(first, n))
    #return permutations(first, n)

def maximum(d):
    max_val = max(d.iteritems(), key=itemgetter(1))[1]
    max_vertices = []
    for vertex, value in d.iteritems():
        if value == max_val:
            max_vertices.append(vertex)
    return [max_val, max_vertices]

def distinct(g):
    bc = nx.betweenness_centrality(g)
    cc = nx.closeness_centrality(g)
    dc = nx.degree_centrality(g)
    ec = nx.eigenvector_centrality(g)

    return [maximum(bc), maximum(cc), maximum(dc), maximum(ec)]

def job(degree_sequence):
    try:
        G = nx.configuration_model(degree_sequence)
        G = nx.Graph(G) # to remove patallel edges
        G.remove_edges_from(G.selfloop_edges())
        distinct_prop = distinct(G)

        only_best_list = [i for x in zip(*distinct_prop)[1] if len(x)==1 for i in x]
        if len(set(only_best_list)) >= 2:
            len_best = [len(x) for x in zip(*distinct_prop)[1]]
            num_uniq = len(set([i for x in zip(*distinct_prop)[1] for i in x]))
            if sum(len_best) < 7 and len_best.count(0) == 0 and num_uniq >= 3:
                with open("result.txt", "a") as f:
                    print ""
                    print num_uniq, zip(*distinct_prop)
                    print G.nodes(), G.edges()
                    print ""
                    print>>f, num_uniq, zip(*distinct_prop)
                    print>>f, G.nodes(), G.edges()
    except nx.exception.NetworkXError, e:
        #print e, degree_sequence
        pass

if __name__=="__main__":
    max_n = 7

    for n in range(4, max_n+1):
        print "=== num of vertex:", n
        for degree_sequence in full_degree_sequences(n):
            job(degree_sequence)

$ time python ps2-6.py > result.txt

n=7
ds = [4443331]