In [1]:

    

#!/usr/bin/env python

#
# Copyright 2017 MIT Lincoln Laboratory, Massachusetts Institute of Technology
#
# Licensed under the Apache License, Version 2.0 (the "License"); you may not use these files except in compliance with
# the License.
#
# You may obtain a copy of the License at
#
#      http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on
# an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the
# specific language governing permissions and limitations under the License.
#

"""
Authors: Steven Smith, Edward Kao
Date: 9 January 2017
Installation: Python 2.7

Description: This Python script performs the baseline graph partition algorithm based on the degree-corrected stochastic block model.

References:
Peixoto, Tiago P. "Entropy of stochastic blockmodel ensembles." Physical Review E 85, no. 5 (2012): 056122.
Peixoto, Tiago P. "Parsimonious module inference in large networks." Physical review letters 110, no. 14 (2013): 148701.
Karrer, Brian, and Mark EJ Newman. "Stochastic blockmodels and community structure in networks." Physical Review E 83, no. 1 (2011): 016107.
"""


    

    
Out[1]:





'\nAuthors: Steven Smith, Edward Kao\nDate: 9 January 2017\nInstallation: Python 2.7\n\nDescription: This Python script performs the baseline graph partition algorithm based on the degree-corrected stochastic block model.\n\nReferences:\nPeixoto, Tiago P. "Entropy of stochastic blockmodel ensembles." Physical Review E 85, no. 5 (2012): 056122.\nPeixoto, Tiago P. "Parsimonious module inference in large networks." Physical review letters 110, no. 14 (2013): 148701.\nKarrer, Brian, and Mark EJ Newman. "Stochastic blockmodels and community structure in networks." Physical Review E 83, no. 1 (2011): 016107.\n'

In [2]:

    

import pandas as pd # for loading input graph TSV files
import numpy as np
from scipy import sparse as sparse
import scipy.misc as misc
from munkres import Munkres # for correctness evaluation

use_timeit = True # for timing runs (optional)
if use_timeit:
    import timeit 

use_graph_tool_options = True # for visualiziing graph partitions (optional)
if use_graph_tool_options:
    import graph_tool.all as gt


    

In [3]:

    

def load_graph(input_filename, load_true_partition, strm_piece_num = None, out_neighbors = None, in_neighbors = None):
    # read the entire graph CSV into rows of edges
    if (strm_piece_num == None):
        edge_rows = pd.read_csv('{}.tsv'.format(input_filename), delimiter='\t', header=None).as_matrix()
    else:
        edge_rows = pd.read_csv('{}_{}.tsv'.format(input_filename, strm_piece_num), delimiter='\t', header=None).as_matrix()
    
    if (out_neighbors == None): # no previously loaded streaming pieces
        N = edge_rows[:, 0:2].max() # number of nodes
        out_neighbors = [[] for i in range(N)]
        in_neighbors = [[] for i in range(N)]
    else: # add to previously loaded streaming pieces
        N = max(edge_rows[:, 0:2].max(), len(out_neighbors)) # number of nodes
        out_neighbors = [list(out_neighbors[i]) for i in range(len(out_neighbors))]
        out_neighbors.extend([[] for i in range(N-len(out_neighbors))])
        in_neighbors = [list(in_neighbors[i]) for i in range(len(in_neighbors))]
        in_neighbors.extend([[] for i in range(N-len(in_neighbors))])
    weights_included = edge_rows.shape[1] == 3

    # load edges to list of lists of out and in neighbors
    for i in range(edge_rows.shape[0]):
        if weights_included:
            edge_weight = edge_rows[i, 2]
        else:
            edge_weight = 1
        # -1 on the node index since Python is 0-indexed and the standard graph TSV is 1-indexed
        out_neighbors[edge_rows[i, 0]-1].append([edge_rows[i, 1]-1, edge_weight])
        in_neighbors[edge_rows[i, 1]-1].append([edge_rows[i, 0]-1, edge_weight])

    # convert each neighbor list to neighbor numpy arrays for faster access
    for i in range(N):
        if len(out_neighbors[i]) > 0:
            out_neighbors[i] = np.array(out_neighbors[i], dtype=int)
        else:
            out_neighbors[i] = np.array(out_neighbors[i], dtype=int).reshape((0,2))
    for i in range(N):
        if len(in_neighbors[i]) > 0:
            in_neighbors[i] = np.array(in_neighbors[i], dtype=int)
        else:
            in_neighbors[i] = np.array(in_neighbors[i], dtype=int).reshape((0,2))

    E = sum(len(v) for v in out_neighbors) # number of edges

    if load_true_partition:
        # read the entire true partition CSV into rows of partitions
        true_b_rows = pd.read_csv('{}_truePartition.tsv'.format(input_filename), delimiter='\t', header=None).as_matrix()
        true_b = np.ones(true_b_rows.shape[0], dtype=int) * -1 # initialize truth assignment to -1 for 'unknown'
        for i in range(true_b_rows.shape[0]):
            true_b[true_b_rows[i, 0]-1] = int(true_b_rows[i, 1]-1) # -1 since Python is 0-indexed and the TSV is 1-indexed

    if load_true_partition:
        return out_neighbors, in_neighbors, N, E, true_b
    else:
        return out_neighbors, in_neighbors, N, E


    

In [4]:

    

def initialize_partition_variables():
    optimal_B_found = False
    old_b = [[], [], []]  # partition for the high, best, and low number of blocks so far
    old_M = [[], [], []]  # edge count matrix for the high, best, and low number of blocks so far
    old_d = [[], [], []]  # block degrees for the high, best, and low number of blocks so far
    old_d_out = [[], [], []]  # out block degrees for the high, best, and low number of blocks so far
    old_d_in = [[], [], []]  # in block degrees for the high, best, and low number of blocks so far
    old_S = [np.Inf, np.Inf, np.Inf] # overall entropy for the high, best, and low number of blocks so far
    old_B = [[], [], []]  # number of blocks for the high, best, and low number of blocks so far
    graph_object = None
    return optimal_B_found, old_b, old_M, old_d, old_d_out, old_d_in, old_S, old_B, graph_object


    

In [5]:

    

def initialize_edge_counts(out_neighbors, B, b, use_sparse):
    if use_sparse: # store interblock edge counts as a sparse matrix
        M = sparse.lil_matrix((B, B), dtype=int)
    else:
        M = np.zeros((B, B), dtype=int)
    # compute the initial interblock edge count
    for v in range(len(out_neighbors)):
        if len(out_neighbors[v]) > 0:
            k1 = b[v]
            k2, inverse_idx = np.unique(b[out_neighbors[v][:, 0]], return_inverse=True)
            count = np.bincount(inverse_idx, weights=out_neighbors[v][:, 1]).astype(int)
            M[k1, k2] += count
    # compute initial block degrees
    d_out = np.asarray(M.sum(axis=1)).ravel()
    d_in = np.asarray(M.sum(axis=0)).ravel()
    d = d_out + d_in
    return M, d_out, d_in, d


    

In [6]:

    

def propose_new_partition(r, neighbors_out, neighbors_in, b, M, d, B, agg_move, use_sparse):
    neighbors = np.concatenate((neighbors_out, neighbors_in))
    k_out = sum(neighbors_out[:,1])
    k_in = sum(neighbors_in[:,1])
    k = k_out + k_in
    if k==0: # this node has no neighbor, simply propose a block randomly
        s = np.random.randint(B)
        return s, k_out, k_in, k
    rand_neighbor = np.random.choice(neighbors[:,0], p=neighbors[:,1]/float(k))
    u = b[rand_neighbor]
    # propose a new block randomly
    if np.random.uniform() <= B/float(d[u]+B):  # chance inversely prop. to block_degree
        if agg_move:  # force proposal to be different from current block
            candidates = set(range(B))
            candidates.discard(r)
            s = np.random.choice(list(candidates))
        else:
            s = np.random.randint(B)
    else:  # propose by random draw from neighbors of block partition[rand_neighbor]
        if use_sparse:
            multinomial_prob = (M[u, :].toarray().transpose() + M[:, u].toarray()) / float(d[u])
        else:
            multinomial_prob = (M[u, :].transpose() + M[:, u]) / float(d[u])
        if agg_move:  # force proposal to be different from current block
            multinomial_prob[r] = 0
            if multinomial_prob.sum() == 0:  # the current block has no neighbors. randomly propose a different block
                candidates = set(range(B))
                candidates.discard(r)
                s = np.random.choice(list(candidates))
                return s, k_out, k_in, k
            else:
                multinomial_prob = multinomial_prob / multinomial_prob.sum()
        candidates = multinomial_prob.nonzero()[0]
        s = candidates[np.flatnonzero(np.random.multinomial(1, multinomial_prob[candidates].ravel()))[0]]
    return s, k_out, k_in, k


    

In [7]:

    

def compute_new_rows_cols_interblock_edge_count_matrix(M, r, s, b_out, count_out, b_in, count_in, count_self, agg_move, use_sparse):
    B = M.shape[0]
    if agg_move:  # the r row and column are simply empty after this merge move
        if use_sparse:
            M_r_row = sparse.lil_matrix(M[r, :].shape, dtype=int)
            M_r_col = sparse.lil_matrix(M[:, r].shape, dtype=int)
        else:
            M_r_row = np.zeros((1, B), dtype=int)
            M_r_col = np.zeros((B, 1), dtype=int)
    else:
        if use_sparse:
            M_r_row = M[r, :].copy()
            M_r_col = M[:, r].copy()
        else:
            M_r_row = M[r, :].copy().reshape(1, B)
            M_r_col = M[:, r].copy().reshape(B, 1)
        M_r_row[0, b_out] -= count_out
        M_r_row[0, r] -= np.sum(count_in[np.where(b_in == r)])
        M_r_row[0, s] += np.sum(count_in[np.where(b_in == r)])
        M_r_col[b_in, 0] -= count_in.reshape(M_r_col[b_in, 0].shape)
        M_r_col[r, 0] -= np.sum(count_out[np.where(b_out == r)])
        M_r_col[s, 0] += np.sum(count_out[np.where(b_out == r)])
    if use_sparse:
        M_s_row = M[s, :].copy()
        M_s_col = M[:, s].copy()
    else:
        M_s_row = M[s, :].copy().reshape(1, B)
        M_s_col = M[:, s].copy().reshape(B, 1)
    M_s_row[0, b_out] += count_out
    M_s_row[0, r] -= np.sum(count_in[np.where(b_in == s)])
    M_s_row[0, s] += np.sum(count_in[np.where(b_in == s)])
    M_s_row[0, r] -= count_self
    M_s_row[0, s] += count_self
    M_s_col[b_in, 0] += count_in.reshape(M_s_col[b_in, 0].shape)
    M_s_col[r, 0] -= np.sum(count_out[np.where(b_out == s)])
    M_s_col[s, 0] += np.sum(count_out[np.where(b_out == s)])
    M_s_col[r, 0] -= count_self
    M_s_col[s, 0] += count_self
    return M_r_row, M_s_row, M_r_col, M_s_col


    

In [8]:

    

def compute_new_block_degrees(r, s, d_out, d_in, d, k_out, k_in, k):
    new = []
    for old, degree in zip([d_out, d_in, d], [k_out, k_in, k]):
        new_d = old.copy()
        new_d[r] -= degree
        new_d[s] += degree
        new.append(new_d)
    return new


    

In [9]:

    

def compute_Hastings_correction(b_out, count_out, b_in, count_in, s, M, M_r_row, M_r_col, B, d, d_new, use_sparse):
    t, idx = np.unique(np.append(b_out, b_in), return_inverse=True)  # find all the neighboring blocks
    count = np.bincount(idx, weights=np.append(count_out, count_in)).astype(int)  # count edges to neighboring blocks
    if use_sparse:
        M_t_s = M[t, s].toarray().ravel()
        M_s_t = M[s, t].toarray().ravel()
        M_r_row = M_r_row[0, t].toarray().ravel()
        M_r_col = M_r_col[t, 0].toarray().ravel()
    else:
        M_t_s = M[t, s].ravel()
        M_s_t = M[s, t].ravel()
        M_r_row = M_r_row[0, t].ravel()
        M_r_col = M_r_col[t, 0].ravel()
        
    p_forward = np.sum(count*(M_t_s + M_s_t + 1) / (d[t] + float(B)))
    p_backward = np.sum(count*(M_r_row + M_r_col + 1) / (d_new[t] + float(B)))
    return p_backward / p_forward


    

In [10]:

    

def compute_delta_entropy(r, s, M, M_r_row, M_s_row, M_r_col, M_s_col, d_out, d_in, d_out_new, d_in_new, use_sparse):
    if use_sparse: # computation in the sparse matrix is slow so convert to numpy arrays since operations are on only two rows and cols
        M_r_row = M_r_row.toarray()
        M_s_row = M_s_row.toarray()
        M_r_col = M_r_col.toarray()
        M_s_col = M_s_col.toarray()
        M_r_t1 = M[r, :].toarray()
        M_s_t1 = M[s, :].toarray()
        M_t2_r = M[:, r].toarray()
        M_t2_s = M[:, s].toarray()
    else:
        M_r_t1 = M[r, :]
        M_s_t1 = M[s, :]
        M_t2_r = M[:, r]
        M_t2_s = M[:, s]

    # remove r and s from the cols to avoid double counting
    idx = range(len(d_in_new))
    del idx[max(r,s)]
    del idx[min(r,s)]
    M_r_col = M_r_col[idx]
    M_s_col = M_s_col[idx]
    M_t2_r = M_t2_r[idx]
    M_t2_s = M_t2_s[idx]
    d_out_new_ = d_out_new[idx]
    d_out_ = d_out[idx]

    # only keep non-zero entries to avoid unnecessary computation
    d_in_new_r_row = d_in_new[M_r_row.ravel().nonzero()]
    d_in_new_s_row = d_in_new[M_s_row.ravel().nonzero()]
    M_r_row = M_r_row[M_r_row.nonzero()]
    M_s_row = M_s_row[M_s_row.nonzero()]
    d_out_new_r_col = d_out_new_[M_r_col.ravel().nonzero()]
    d_out_new_s_col = d_out_new_[M_s_col.ravel().nonzero()]
    M_r_col = M_r_col[M_r_col.nonzero()]
    M_s_col = M_s_col[M_s_col.nonzero()]
    d_in_r_t1 = d_in[M_r_t1.ravel().nonzero()]
    d_in_s_t1 = d_in[M_s_t1.ravel().nonzero()]
    M_r_t1= M_r_t1[M_r_t1.nonzero()]
    M_s_t1 = M_s_t1[M_s_t1.nonzero()]
    d_out_r_col = d_out_[M_t2_r.ravel().nonzero()]
    d_out_s_col = d_out_[M_t2_s.ravel().nonzero()]
    M_t2_r = M_t2_r[M_t2_r.nonzero()]
    M_t2_s = M_t2_s[M_t2_s.nonzero()]

    # sum over the two changed rows and cols
    delta_entropy = 0
    delta_entropy -= np.sum(M_r_row * np.log(M_r_row.astype(float) / d_in_new_r_row / d_out_new[r]))
    delta_entropy -= np.sum(M_s_row * np.log(M_s_row.astype(float) / d_in_new_s_row / d_out_new[s]))
    delta_entropy -= np.sum(M_r_col * np.log(M_r_col.astype(float) / d_out_new_r_col / d_in_new[r]))
    delta_entropy -= np.sum(M_s_col * np.log(M_s_col.astype(float) / d_out_new_s_col / d_in_new[s]))
    delta_entropy += np.sum(M_r_t1 * np.log(M_r_t1.astype(float) / d_in_r_t1 / d_out[r]))
    delta_entropy += np.sum(M_s_t1 * np.log(M_s_t1.astype(float) / d_in_s_t1 / d_out[s]))
    delta_entropy += np.sum(M_t2_r * np.log(M_t2_r.astype(float) / d_out_r_col / d_in[r]))
    delta_entropy += np.sum(M_t2_s * np.log(M_t2_s.astype(float) / d_out_s_col / d_in[s]))
    return delta_entropy


    

In [11]:

    

def carry_out_best_merges(delta_entropy_for_each_block, best_merge_for_each_block, b, B, B_to_merge):
    bestMerges = delta_entropy_for_each_block.argsort()
    block_map = np.arange(B)
    num_merge = 0
    counter = 0
    while num_merge < B_to_merge:
        mergeFrom = bestMerges[counter]
        mergeTo = block_map[best_merge_for_each_block[bestMerges[counter]]]
        counter += 1
        if mergeTo != mergeFrom:
            block_map[np.where(block_map == mergeFrom)] = mergeTo
            b[np.where(b == mergeFrom)] = mergeTo
            num_merge += 1
    remaining_blocks = np.unique(b)
    mapping = -np.ones(B, dtype=int)
    mapping[remaining_blocks] = np.arange(len(remaining_blocks))
    b = mapping[b]
    B -= B_to_merge
    return b, B


    

In [12]:

    

def update_partition(b, ni, r, s, M, M_r_row, M_s_row, M_r_col, M_s_col, d_out_new, d_in_new, d_new, use_sparse):
    b[ni] = s
    M[r, :] = M_r_row
    M[s, :] = M_s_row
    if use_sparse:
        M[:, r] = M_r_col
        M[:, s] = M_s_col
    else:
        M[:, r] = M_r_col.reshape(M[:, r].shape)
        M[:, s] = M_s_col.reshape(M[:, s].shape)
    return b, M, d_out_new, d_in_new, d_new


    

In [13]:

    

def compute_overall_entropy(M, d_out, d_in, B, N, E, use_sparse):
    nonzeros = M.nonzero()  # all non-zero entries
    edge_count_entries = M[nonzeros[0], nonzeros[1]]
    if use_sparse:
        edge_count_entries = edge_count_entries.toarray()

    entries = edge_count_entries * np.log(edge_count_entries / (d_out[nonzeros[0]] * d_in[nonzeros[1]]).astype(float))
    data_S = -np.sum(entries)
    model_S_term = B**2 / float(E)
    model_S = E * (1 + model_S_term) * np.log(1 + model_S_term) - model_S_term * np.log(model_S_term) + N*np.log(B)
    S = model_S + data_S
    return S


    

In [14]:

    

def prepare_for_partition_on_next_num_blocks(S, b, M, d, d_out, d_in, B, old_b, old_M, old_d, old_d_out, old_d_in, old_S, old_B, B_rate):
    optimal_B_found = False
    B_to_merge = 0

    # update the best three partitions so far and their statistics
    if S <= old_S[1]:  # if the current partition is the best so far
        # if the current number of blocks is smaller than the previous best number of blocks
        old_index = 0 if old_B[1] > B else 2
        old_b[old_index] = old_b[1]
        old_M[old_index] = old_M[1]
        old_d[old_index] = old_d[1]
        old_d_out[old_index] = old_d_out[1]
        old_d_in[old_index] = old_d_in[1]
        old_S[old_index] = old_S[1]
        old_B[old_index] = old_B[1]

        index = 1
    else:  # the current partition is not the best so far
        # if the current number of blocks is smaller than the best number of blocks so far
        index = 2 if old_B[1] > B else 0

    old_b[index] = b
    old_M[index] = M
    old_d[index] = d
    old_d_out[index] = d_out
    old_d_in[index] = d_in
    old_S[index] = S
    old_B[index] = B

    # find the next number of blocks to try using golden ratio bisection
    if old_S[2] == np.Inf:  # if the three points in the golden ratio bracket has not yet been established
        B_to_merge = int(B*B_rate)
        if (B_to_merge==0): # not enough number of blocks to merge so done
            optimal_B_found = True
        b = old_b[1].copy()
        M = old_M[1].copy()
        d = old_d[1].copy()
        d_out = old_d_out[1].copy()
        d_in = old_d_in[1].copy()
    else:  # golden ratio search bracket established
        if old_B[0] - old_B[2] == 2:  # we have found the partition with the optimal number of blocks
            optimal_B_found = True
            B = old_B[1]
            b = old_b[1]
        else:  # not done yet, find the next number of block to try according to the golden ratio search
            if (old_B[0]-old_B[1]) >= (old_B[1]-old_B[2]):  # the higher segment in the bracket is bigger
                index = 0
            else:  # the lower segment in the bracket is bigger
                index = 1
            next_B_to_try = old_B[index + 1] + np.round((old_B[index] - old_B[index + 1]) * 0.618).astype(int)
            B_to_merge = old_B[index] - next_B_to_try
            B = old_B[index]
            b = old_b[index].copy()
            M = old_M[index].copy()
            d = old_d[index].copy()
            d_out = old_d_out[index].copy()
            d_in = old_d_in[index].copy()
    return b, M, d, d_out, d_in, B, B_to_merge, old_b, old_M, old_d, old_d_out, old_d_in, old_S, old_B, optimal_B_found


    

In [15]:

    

def plot_graph_with_partition(out_neighbors, b, graph_object = None, pos = None):
    if len(out_neighbors) <= 5000:
        if graph_object is None:
            graph_object = gt.Graph()
            edge_list = [(i,j) for i in range(len(out_neighbors)) if len(out_neighbors[i])>0 for j in out_neighbors[i][:,0]]
            graph_object.add_edge_list(edge_list)
            if pos is None:
                graph_object.vp['pos'] = gt.sfdp_layout(graph_object)
            else:
                graph_object.vp['pos'] = graph_object.new_vertex_property("vector<float>")
                for v in graph_object.vertices():
                    graph_object.vp['pos'][v] = pos[graph_object.vertex_index[v],:]
        block_membership = graph_object.new_vertex_property("int")
        vertex_shape = graph_object.new_vertex_property("int")
        block_membership.a = b[0:len(out_neighbors)]
        vertex_shape.a = np.mod(block_membership.a,10)
        gt.graph_draw(graph_object, inline=True, output_size=(400,400), pos=graph_object.vp['pos'], vertex_shape=vertex_shape,
                      vertex_fill_color=block_membership, edge_pen_width=0.07, edge_marker_size=1, vertex_size = 10)
    else:
        print('That\'s a big graph!')
    return graph_object


    

In [16]:

    

def evaluate_partition(true_b, alg_b):
    blocks_b1 = true_b
    blocks_b1_set = set(true_b)
    blocks_b1_set.discard(-1) # -1 is the label for 'unknown'
    B_b1 = len(blocks_b1_set)

    blocks_b2 = alg_b
    B_b2 = max(blocks_b2) + 1

    print('\nPartition Correctness Evaluation\n')
    print('Number of nodes: {}'.format(len(alg_b)))
    print('Number of partitions in truth partition: {}'.format(B_b1))
    print('Number of partitions in alg. partition: {}'.format(B_b2))

    # populate the confusion matrix between the two partitions
    contingency_table = np.zeros((B_b1, B_b2))
    for i in range(len(alg_b)): # evaluation based on nodes observed so far
        if true_b[i] != -1: # do not include nodes without truth in the evaluation
            contingency_table[blocks_b1[i], blocks_b2[i]] += 1
    N = contingency_table.sum()

    # associate the labels between two partitions using linear assignment
    assignment = Munkres()  # use the Hungarian algorithm / Kuhn-Munkres algorithm
    if B_b1 > B_b2:  # transpose matrix for linear assignment (this implementation assumes #col >= #row)
        contingency_table = contingency_table.transpose()
    indexes = assignment.compute(-contingency_table)
    total = 0
    contingency_table_before_assignment = np.array(contingency_table)
    for row, column in indexes:
        contingency_table[:, row] = contingency_table_before_assignment[:, column]
        total += contingency_table[row, row]
    # fill in the un-associated columns
    unassociated_col = set(range(contingency_table.shape[1])) - set(np.array(indexes)[:, 1])
    counter = 0;
    for column in unassociated_col:
        contingency_table[:, contingency_table.shape[0] + counter] = contingency_table_before_assignment[:, column]
        counter += 1
    if B_b1 > B_b2:  # transpose back
        contingency_table = contingency_table.transpose()
    print('Contingency Table: \n{}'.format(contingency_table))
    joint_prob = contingency_table / sum(
        sum(contingency_table))  # joint probability of the two partitions is just the normalized contingency table
    accuracy = sum(joint_prob.diagonal())
    print('Accuracy (with optimal partition matching): {}'.format(accuracy))
    print('\n')

    # Compute pair-counting-based metrics
    def nchoose2(a):
        return misc.comb(a, 2)
    num_pairs = nchoose2(N)
    colsum = np.sum(contingency_table, axis=0)
    rowsum = np.sum(contingency_table, axis=1)
    # compute counts of agreements and disagreement (4 types) and the regular rand index
    sum_table_squared = sum(sum(contingency_table ** 2))
    sum_colsum_squared = sum(colsum ** 2)
    sum_rowsum_squared = sum(rowsum ** 2)
    count_in_each_b1 = np.sum(contingency_table, axis=1)
    count_in_each_b2 = np.sum(contingency_table, axis=0)
    num_same_in_b1 = sum(count_in_each_b1 * (count_in_each_b1 - 1)) / 2
    num_same_in_b2 = sum(count_in_each_b2 * (count_in_each_b2 - 1)) / 2
    num_agreement_same = 0.5 * sum(sum(contingency_table * (contingency_table - 1)));
    num_agreement_diff = 0.5 * (N ** 2 + sum_table_squared - sum_colsum_squared - sum_rowsum_squared);
    num_agreement = num_agreement_same + num_agreement_diff
    rand_index = num_agreement / num_pairs

    vectorized_nchoose2 = np.vectorize(nchoose2)
    sum_table_choose_2 = sum(sum(vectorized_nchoose2(contingency_table)))
    sum_colsum_choose_2 = sum(vectorized_nchoose2(colsum))
    sum_rowsum_choose_2 = sum(vectorized_nchoose2(rowsum))
    adjusted_rand_index = (sum_table_choose_2 - sum_rowsum_choose_2 * sum_colsum_choose_2 / num_pairs) / (
    0.5 * (sum_rowsum_choose_2 + sum_colsum_choose_2) - sum_rowsum_choose_2 * sum_colsum_choose_2 / num_pairs)
    print('Rand Index: {}'.format(rand_index))
    print('Adjusted Rand Index: {}'.format(adjusted_rand_index))
    print('Pairwise Recall: {}'.format(num_agreement_same / (num_same_in_b1)))
    print('Pairwise Precision: {}'.format(num_agreement_same / (num_same_in_b2)))
    print('\n')

    # compute the information theoretic metrics
    marginal_prob_b2 = np.sum(joint_prob, 0)
    marginal_prob_b1 = np.sum(joint_prob, 1)
    idx1 = np.nonzero(marginal_prob_b1)
    idx2 = np.nonzero(marginal_prob_b2)
    conditional_prob_b2_b1 = np.zeros(joint_prob.shape)
    conditional_prob_b1_b2 = np.zeros(joint_prob.shape)
    conditional_prob_b2_b1[idx1,:] = joint_prob[idx1,:] / marginal_prob_b1[idx1, None]
    conditional_prob_b1_b2[:,idx2] = joint_prob[:,idx2] / marginal_prob_b2[None, idx2]
    # compute entropy of the non-partition2 and the partition2 version
    H_b2 = -np.sum(marginal_prob_b2[idx2] * np.log(marginal_prob_b2[idx2]))
    H_b1 = -np.sum(marginal_prob_b1[idx1] * np.log(marginal_prob_b1[idx1]))

    # compute the conditional entropies
    idx = np.nonzero(joint_prob)
    H_b2_b1 = -np.sum(np.sum(joint_prob[idx] * np.log(conditional_prob_b2_b1[idx])))
    H_b1_b2 = -np.sum(np.sum(joint_prob[idx] * np.log(conditional_prob_b1_b2[idx])))
    # compute the mutual information (symmetric)
    marginal_prod = np.dot(marginal_prob_b1[:, None], np.transpose(marginal_prob_b2[:, None]))
    MI_b1_b2 = np.sum(np.sum(joint_prob[idx] * np.log(joint_prob[idx] / marginal_prod[idx])))

    if H_b1>0:
        fraction_missed_info = H_b1_b2 / H_b1
    else:
        fraction_missed_info = 0
    if H_b2>0:
        fraction_err_info = H_b2_b1 / H_b2
    else:
        fraction_err_info = 0
    print('Entropy of truth partition: {}'.format(abs(H_b1)))
    print('Entropy of alg. partition: {}'.format(abs(H_b2)))
    print('Conditional entropy of truth partition given alg. partition: {}'.format(abs(H_b1_b2)))
    print('Conditional entropy of alg. partition given truth partition: {}'.format(abs(H_b2_b1)))
    print('Mututal informationion between truth partition and alg. partition: {}'.format(abs(MI_b1_b2)))
    print('Fraction of missed information: {}'.format(abs(fraction_missed_info)))
    print('Fraction of erroneous information: {}'.format(abs(fraction_err_info)))


    

In [17]:

    

def main():
    input_filename = '../../data/static/simulated_blockmodel_graph_500_nodes'
    true_partition_available = True
    visualize_graph = True # whether to plot the graph layout colored with intermediate partitions
    verbose = True # whether to print updates of the partitioning

    out_neighbors, in_neighbors, N, E, true_partition = load_graph(input_filename, true_partition_available)
    if verbose:
        print('Number of nodes: {}'.format(N))
        print('Number of edges: {}'.format(E))

    if use_timeit:
        t0 = timeit.default_timer()

    # initialize by putting each node in its own block (N blocks)
    num_blocks = N
    partition = np.array(range(num_blocks))

    # partition update parameters
    beta = 3 # exploitation versus exploration (higher value favors exploitation)
    use_sparse_matrix = False # whether to represent the edge count matrix using sparse matrix 
                              # Scipy's sparse matrix is slow but this may be necessary for large graphs

    # agglomerative partition update parameters
    num_agg_proposals_per_block = 10 # number of proposals per block
    num_block_reduction_rate = 0.5 # fraction of blocks to reduce until the golden ratio bracket is established

    # nodal partition updates parameters
    max_num_nodal_itr = 100 # maximum number of iterations
    delta_entropy_threshold1 = 5e-4 # stop iterating when the change in entropy falls below this fraction of the overall entropy
                                    # lowering this threshold results in more nodal update iterations and likely better performance, but longer runtime
    delta_entropy_threshold2 = 1e-4 # threshold after the golden ratio bracket is established (typically lower to fine-tune to partition) 
    delta_entropy_moving_avg_window = 3 # width of the moving average window for the delta entropy convergence criterion

    # initialize edge counts and block degrees
    interblock_edge_count, block_degrees_out, block_degrees_in, block_degrees = initialize_edge_counts(out_neighbors, num_blocks, partition, use_sparse_matrix)

    # initialize items before iterations to find the partition with the optimal number of blocks
    optimal_num_blocks_found, old_partition, old_interblock_edge_count, old_block_degrees, old_block_degrees_out, old_block_degrees_in, old_overall_entropy, old_num_blocks, graph_object = initialize_partition_variables()
    num_blocks_to_merge = int(num_blocks*num_block_reduction_rate)

    # begin partitioning by finding the best partition with the optimal number of blocks
    while not optimal_num_blocks_found:
        # begin agglomerative partition updates (i.e. block merging)
        if verbose:
            print("\nMerging down blocks from {} to {}".format(num_blocks, num_blocks - num_blocks_to_merge))
        best_merge_for_each_block = np.ones(num_blocks, dtype = int)*-1 # initialize to no merge
        delta_entropy_for_each_block = np.ones(num_blocks)*np.Inf # initialize criterion
        block_partition = range(num_blocks)
        for current_block in range(num_blocks): # evalaute agglomerative updates for each block
            for proposal_idx in range(num_agg_proposals_per_block):
                # populate edges to neighboring blocks
                if use_sparse_matrix:
                    out_blocks = interblock_edge_count[current_block,:].nonzero()[1]
                    out_blocks = np.hstack((out_blocks.reshape([len(out_blocks),1]), interblock_edge_count[current_block,out_blocks].toarray().transpose()))
                else:
                    out_blocks = interblock_edge_count[current_block,:].nonzero()
                    out_blocks = np.hstack((np.array(out_blocks).transpose(), interblock_edge_count[current_block,out_blocks].transpose()))
                if use_sparse_matrix:
                    in_blocks = interblock_edge_count[:,current_block].nonzero()[0]
                    in_blocks = np.hstack((in_blocks.reshape([len(in_blocks),1]), interblock_edge_count[in_blocks,current_block].toarray()))
                else:
                    in_blocks = interblock_edge_count[:,current_block].nonzero()
                    in_blocks = np.hstack((np.array(in_blocks).transpose(), interblock_edge_count[in_blocks,current_block].transpose()))

                # propose a new block to merge with
                proposal, num_out_neighbor_edges, num_in_neighbor_edges, num_neighbor_edges = propose_new_partition(current_block, out_blocks, in_blocks, block_partition, interblock_edge_count, block_degrees, num_blocks, 1, use_sparse_matrix)

                # compute the two new rows and columns of the interblock edge count matrix
                new_interblock_edge_count_current_block_row, new_interblock_edge_count_new_block_row, new_interblock_edge_count_current_block_col, new_interblock_edge_count_new_block_col = \
                    compute_new_rows_cols_interblock_edge_count_matrix(interblock_edge_count, current_block, proposal, out_blocks[:,0], out_blocks[:,1], in_blocks[:,0], in_blocks[:,1], interblock_edge_count[current_block, current_block], 1, use_sparse_matrix)    

                # compute new block degrees           
                block_degrees_out_new, block_degrees_in_new, block_degrees_new = compute_new_block_degrees(current_block, proposal, block_degrees_out, block_degrees_in, block_degrees, num_out_neighbor_edges, num_in_neighbor_edges, num_neighbor_edges)

                # compute change in entropy / posterior
                delta_entropy = compute_delta_entropy(current_block, proposal, interblock_edge_count, new_interblock_edge_count_current_block_row, new_interblock_edge_count_new_block_row, new_interblock_edge_count_current_block_col, new_interblock_edge_count_new_block_col, block_degrees_out, block_degrees_in, block_degrees_out_new, block_degrees_in_new, use_sparse_matrix)
                if delta_entropy < delta_entropy_for_each_block[current_block]: # a better block candidate was found
                    best_merge_for_each_block[current_block] = proposal
                    delta_entropy_for_each_block[current_block] = delta_entropy

        # carry out the best merges
        partition, num_blocks = carry_out_best_merges(delta_entropy_for_each_block, best_merge_for_each_block, partition, num_blocks, num_blocks_to_merge)

        # re-initialize edge counts and block degrees
        interblock_edge_count, block_degrees_out, block_degrees_in, block_degrees = initialize_edge_counts(out_neighbors, num_blocks, partition, use_sparse_matrix)

        # perform nodal partition updates
        if verbose:
            print("Beginning nodal updates")
        total_num_nodal_moves = 0            
        itr_delta_entropy = np.zeros(max_num_nodal_itr)

        # compute the global entropy for MCMC convergence criterion
        overall_entropy = compute_overall_entropy(interblock_edge_count, block_degrees_out, block_degrees_in, num_blocks, N, E, use_sparse_matrix)

        for itr in range(max_num_nodal_itr):
            num_nodal_moves = 0;
            itr_delta_entropy[itr] = 0

            for current_node in range(N):
                current_block = partition[current_node] 
                # propose a new block for this node
                proposal, num_out_neighbor_edges, num_in_neighbor_edges, num_neighbor_edges = propose_new_partition(current_block, out_neighbors[current_node], in_neighbors[current_node], partition, interblock_edge_count, block_degrees, num_blocks, 0, use_sparse_matrix)

                # determine whether to accept or reject the proposal
                if (proposal != current_block):
                    # compute block counts of in and out neighbors
                    blocks_out, inverse_idx_out = np.unique(partition[out_neighbors[current_node][:,0]], return_inverse = True)
                    count_out = np.bincount(inverse_idx_out, weights=out_neighbors[current_node][:,1]).astype(int)
                    blocks_in, inverse_idx_in = np.unique(partition[in_neighbors[current_node][:,0]], return_inverse = True)
                    count_in = np.bincount(inverse_idx_in, weights=in_neighbors[current_node][:,1]).astype(int)

                    # compute the two new rows and columns of the interblock edge count matrix
                    self_edge_weight = np.sum(out_neighbors[current_node][np.where(out_neighbors[current_node][:,0]==current_node),1]) # check if this node has a self edge
                    new_interblock_edge_count_current_block_row, new_interblock_edge_count_new_block_row, new_interblock_edge_count_current_block_col, new_interblock_edge_count_new_block_col = \
                        compute_new_rows_cols_interblock_edge_count_matrix(interblock_edge_count, current_block, proposal, blocks_out, count_out, blocks_in, count_in, self_edge_weight, 0, use_sparse_matrix)

                    # compute new block degrees           
                    block_degrees_out_new, block_degrees_in_new, block_degrees_new = compute_new_block_degrees(current_block, proposal, block_degrees_out, block_degrees_in, block_degrees, num_out_neighbor_edges, num_in_neighbor_edges, num_neighbor_edges)

                    # compute the Hastings correction
                    if num_neighbor_edges>0:
                        Hastings_correction = compute_Hastings_correction(blocks_out, count_out, blocks_in, count_in, proposal, interblock_edge_count, new_interblock_edge_count_current_block_row, new_interblock_edge_count_current_block_col, num_blocks, block_degrees, block_degrees_new, use_sparse_matrix)
                    else: # if the node is an island, proposal is random and symmetric
                        Hastings_correction = 1
                    # compute change in entropy / posterior
                    delta_entropy = compute_delta_entropy(current_block, proposal, interblock_edge_count, new_interblock_edge_count_current_block_row, new_interblock_edge_count_new_block_row, new_interblock_edge_count_current_block_col, new_interblock_edge_count_new_block_col, block_degrees_out, block_degrees_in, block_degrees_out_new, block_degrees_in_new, use_sparse_matrix)

                    # compute probability of acceptance
                    p_accept = np.min([np.exp(-beta*delta_entropy)*Hastings_correction, 1])

                    # if accept the proposal, update the partition, inter_block_edge_count, and block degrees
                    if (np.random.uniform() <= p_accept):
                        total_num_nodal_moves += 1
                        num_nodal_moves += 1
                        itr_delta_entropy[itr] += delta_entropy
                        partition, interblock_edge_count, block_degrees_out, block_degrees_in, block_degrees = update_partition(partition, current_node, current_block, proposal, interblock_edge_count, new_interblock_edge_count_current_block_row, new_interblock_edge_count_new_block_row, new_interblock_edge_count_current_block_col, new_interblock_edge_count_new_block_col, block_degrees_out_new, block_degrees_in_new, block_degrees_new, use_sparse_matrix)
            if verbose:
                print("Itr: {}, number of nodal moves: {}, delta S: {:0.5f}".format(itr, num_nodal_moves, itr_delta_entropy[itr]/float(overall_entropy)))
            if itr>=(delta_entropy_moving_avg_window-1): # exit MCMC if the recent change in entropy falls below a small fraction of the overall entropy
                if not(np.all(np.isfinite(old_overall_entropy))): # golden ratio bracket not yet established 
                    if (-np.mean(itr_delta_entropy[(itr-delta_entropy_moving_avg_window+1):itr]) < (delta_entropy_threshold1*overall_entropy)):
                        break
                else: # golden ratio bracket is established. Fine-tuning partition.
                    if (-np.mean(itr_delta_entropy[(itr-delta_entropy_moving_avg_window+1):itr]) < (delta_entropy_threshold2*overall_entropy)):
                        break

        # compute the global entropy for determining the optimal number of blocks
        overall_entropy = compute_overall_entropy(interblock_edge_count, block_degrees_out, block_degrees_in, num_blocks, N, E, use_sparse_matrix)

        if verbose:
            print("Total number of nodal moves: {}, overall_entropy: {:0.2f}".format(total_num_nodal_moves, overall_entropy))
        if visualize_graph & use_graph_tool_options:
            graph_object = plot_graph_with_partition(out_neighbors, partition, graph_object)

        # check whether the partition with optimal number of block has been found; if not, determine and prepare for the next number of blocks to try
        partition, interblock_edge_count, block_degrees, block_degrees_out, block_degrees_in, num_blocks, num_blocks_to_merge, old_partition, old_interblock_edge_count, old_block_degrees, old_block_degrees_out, old_block_degrees_in, old_overall_entropy, old_num_blocks, optimal_num_blocks_found = \
            prepare_for_partition_on_next_num_blocks(overall_entropy, partition, interblock_edge_count, block_degrees, block_degrees_out, block_degrees_in, num_blocks, old_partition, old_interblock_edge_count, old_block_degrees, old_block_degrees_out, old_block_degrees_in, old_overall_entropy, old_num_blocks, num_block_reduction_rate)

        if verbose:
            print('Overall entropy: {}'.format(old_overall_entropy))
            print('Number of blocks: {}'.format(old_num_blocks))
            if optimal_num_blocks_found:
                print('\nOptimal partition found with {} blocks'.format(num_blocks))
    if use_timeit:
        t1 = timeit.default_timer()
        print('\nGraph partition took {} seconds'.format(t1-t0))

    # evaluate output partition against the true partition
    evaluate_partition(true_partition, partition)


    

In [18]:

    

main()


    

    




Number of nodes: 500
Number of edges: 9384

Merging down blocks from 500 to 250
Beginning nodal updates
Itr: 0, number of nodal moves: 152, delta S: -0.01493
Itr: 1, number of nodal moves: 100, delta S: -0.00479
Itr: 2, number of nodal moves: 68, delta S: -0.00235
Itr: 3, number of nodal moves: 44, delta S: -0.00136
Itr: 4, number of nodal moves: 39, delta S: -0.00102
Itr: 5, number of nodal moves: 36, delta S: -0.00087
Itr: 6, number of nodal moves: 45, delta S: -0.00106
Itr: 7, number of nodal moves: 33, delta S: -0.00073
Itr: 8, number of nodal moves: 29, delta S: -0.00037
Itr: 9, number of nodal moves: 24, delta S: -0.00042
Itr: 10, number of nodal moves: 27, delta S: -0.00036
Total number of nodal moves: 597, overall_entropy: 213954.57






    













    




Overall entropy: [inf, 213954.57448411512, inf]
Number of blocks: [[], 250, []]

Merging down blocks from 250 to 125
Beginning nodal updates
Itr: 0, number of nodal moves: 85, delta S: -0.00524
Itr: 1, number of nodal moves: 75, delta S: -0.00299
Itr: 2, number of nodal moves: 68, delta S: -0.00302
Itr: 3, number of nodal moves: 48, delta S: -0.00128
Itr: 4, number of nodal moves: 36, delta S: -0.00107
Itr: 5, number of nodal moves: 27, delta S: -0.00070
Itr: 6, number of nodal moves: 31, delta S: -0.00096
Itr: 7, number of nodal moves: 25, delta S: -0.00040
Itr: 8, number of nodal moves: 23, delta S: -0.00045
Itr: 9, number of nodal moves: 22, delta S: -0.00032
Total number of nodal moves: 440, overall_entropy: 96914.53






    













    




Overall entropy: [213954.57448411512, 96914.530160666036, inf]
Number of blocks: [250, 125, []]

Merging down blocks from 125 to 63
Beginning nodal updates
Itr: 0, number of nodal moves: 52, delta S: -0.00190
Itr: 1, number of nodal moves: 46, delta S: -0.00109
Itr: 2, number of nodal moves: 34, delta S: -0.00067
Itr: 3, number of nodal moves: 36, delta S: -0.00064
Itr: 4, number of nodal moves: 24, delta S: -0.00044
Itr: 5, number of nodal moves: 20, delta S: -0.00038
Itr: 6, number of nodal moves: 16, delta S: -0.00019
Total number of nodal moves: 228, overall_entropy: 79955.92






    













    




Overall entropy: [96914.530160666036, 79955.915528940968, inf]
Number of blocks: [125, 63, []]

Merging down blocks from 63 to 32
Beginning nodal updates
Itr: 0, number of nodal moves: 42, delta S: -0.00065
Itr: 1, number of nodal moves: 44, delta S: -0.00080
Itr: 2, number of nodal moves: 24, delta S: -0.00057
Itr: 3, number of nodal moves: 42, delta S: -0.00041
Itr: 4, number of nodal moves: 33, delta S: -0.00046
Total number of nodal moves: 185, overall_entropy: 77278.08






    













    




Overall entropy: [79955.915528940968, 77278.081763204318, inf]
Number of blocks: [63, 32, []]

Merging down blocks from 32 to 16
Beginning nodal updates
Itr: 0, number of nodal moves: 16, delta S: -0.00026
Itr: 1, number of nodal moves: 19, delta S: -0.00022
Itr: 2, number of nodal moves: 14, delta S: -0.00027
Total number of nodal moves: 49, overall_entropy: 76769.69






    













    




Overall entropy: [77278.081763204318, 76769.687956196649, inf]
Number of blocks: [32, 16, []]

Merging down blocks from 16 to 8
Beginning nodal updates
Itr: 0, number of nodal moves: 0, delta S: 0.00000
Itr: 1, number of nodal moves: 0, delta S: 0.00000
Itr: 2, number of nodal moves: 0, delta S: 0.00000
Total number of nodal moves: 0, overall_entropy: 76545.57






    













    




Overall entropy: [76769.687956196649, 76545.567859553776, inf]
Number of blocks: [16, 8, []]

Merging down blocks from 8 to 4
Beginning nodal updates
Itr: 0, number of nodal moves: 0, delta S: 0.00000
Itr: 1, number of nodal moves: 0, delta S: 0.00000
Itr: 2, number of nodal moves: 0, delta S: 0.00000
Total number of nodal moves: 0, overall_entropy: 80054.42






    













    




Overall entropy: [76769.687956196649, 76545.567859553776, 80054.415918279672]
Number of blocks: [16, 8, 4]

Merging down blocks from 16 to 13
Beginning nodal updates
Itr: 0, number of nodal moves: 11, delta S: -0.00009
Itr: 1, number of nodal moves: 13, delta S: -0.00012
Itr: 2, number of nodal moves: 7, delta S: -0.00006
Itr: 3, number of nodal moves: 10, delta S: -0.00011
Total number of nodal moves: 41, overall_entropy: 76673.44






    













    




Overall entropy: [76673.437002407722, 76545.567859553776, 80054.415918279672]
Number of blocks: [13, 8, 4]

Merging down blocks from 13 to 11
Beginning nodal updates
Itr: 0, number of nodal moves: 8, delta S: -0.00008
Itr: 1, number of nodal moves: 3, delta S: -0.00001
Itr: 2, number of nodal moves: 6, delta S: -0.00002
Total number of nodal moves: 17, overall_entropy: 76629.13






    













    




Overall entropy: [76629.130069876614, 76545.567859553776, 80054.415918279672]
Number of blocks: [11, 8, 4]

Merging down blocks from 8 to 6
Beginning nodal updates
Itr: 0, number of nodal moves: 0, delta S: 0.00000
Itr: 1, number of nodal moves: 0, delta S: 0.00000
Itr: 2, number of nodal moves: 0, delta S: 0.00000
Total number of nodal moves: 0, overall_entropy: 77928.31






    













    




Overall entropy: [76629.130069876614, 76545.567859553776, 77928.305025526235]
Number of blocks: [11, 8, 6]

Merging down blocks from 11 to 10
Beginning nodal updates
Itr: 0, number of nodal moves: 6, delta S: -0.00007
Itr: 1, number of nodal moves: 3, delta S: -0.00000
Itr: 2, number of nodal moves: 3, delta S: -0.00002
Total number of nodal moves: 12, overall_entropy: 76609.20






    













    




Overall entropy: [76609.196307625389, 76545.567859553776, 77928.305025526235]
Number of blocks: [10, 8, 6]

Merging down blocks from 10 to 9
Beginning nodal updates
Itr: 0, number of nodal moves: 4, delta S: 0.00002
Itr: 1, number of nodal moves: 7, delta S: -0.00004
Itr: 2, number of nodal moves: 2, delta S: -0.00000
Total number of nodal moves: 13, overall_entropy: 76584.66






    













    




Overall entropy: [76584.65950356696, 76545.567859553776, 77928.305025526235]
Number of blocks: [9, 8, 6]

Merging down blocks from 8 to 7
Beginning nodal updates
Itr: 0, number of nodal moves: 0, delta S: 0.00000
Itr: 1, number of nodal moves: 0, delta S: 0.00000
Itr: 2, number of nodal moves: 0, delta S: 0.00000
Total number of nodal moves: 0, overall_entropy: 76972.25






    













    




Overall entropy: [76584.65950356696, 76545.567859553776, 76972.254262542338]
Number of blocks: [9, 8, 7]

Optimal partition found with 8 blocks

Graph partition took 52.8209969997 seconds

Partition Correctness Evaluation

Number of nodes: 500
Number of partitions in truth partition: 8
Number of partitions in alg. partition: 8
Contingency Table: 
[[  71.    0.    0.    0.    0.    0.    0.    0.]
 [   0.   56.    0.    0.    0.    0.    0.    0.]
 [   0.    0.   51.    0.    0.    0.    0.    0.]
 [   0.    0.    0.   58.    0.    0.    0.    0.]
 [   0.    0.    0.    0.   41.    0.    0.    0.]
 [   0.    0.    0.    0.    0.  106.    0.    0.]
 [   0.    0.    0.    0.    0.    0.   52.    0.]
 [   0.    0.    0.    0.    0.    0.    0.   65.]]
Accuracy (with optimal partition matching): 1.0


Rand Index: 1.0
Adjusted Rand Index: 1.0
Pairwise Recall: 1.0
Pairwise Precision: 1.0


Entropy of truth partition: 2.03964887352
Entropy of alg. partition: 2.03964887352
Conditional entropy of truth partition given alg. partition: 0.0
Conditional entropy of alg. partition given truth partition: 0.0
Mututal informationion between truth partition and alg. partition: 2.03964887352
Fraction of missed information: 0.0
Fraction of erroneous information: 0.0