Thesis » QuynhNguyen-MS

# Implement the section III in Puzis 2012 paper

# Heuristic Betweenness Centrality - Unifying Structurally Equivalent Vertices

# Dec 9, 2015

import os

import pprint

import networkx as nx

import betweenness_centrality as centrality

import utility

from pdb import set_trace as debugger

MAIN_CODE_DIR = os.environ.get('MAIN_CODE_DIR', '/home/quynh/Thesis/quynhnguyen-ms/fiddle/heuristic-betweenness-centrality')

class CommunicationImportance():

    def __init__(self, QG, G):

        self.QG = QG

        self.G = G

        # Generate empty communication importance matrix

        l = len(self.QG)

        self.h = [[0 for i in range(l)] for i in range(l)]

        self.compute_paths_between_structurally_equivalent_vertices()

        self.compute_paths_between_different_equivalence_classes()

        self.compute_paths_between_different_equivalence_classes()

        pp = pprint.PrettyPrinter(indent=4)

        pp.pprint(self.h)

    def get_by_index(self, index_1, index_2):

        return self.h[index_1][index_2]

    def update_by_index(self, index_1, index_2, new_value):

        self.h[index_1][index_2] = new_value

    def compute_paths_between_structurally_equivalent_vertices(self):

        """

        Calculates the Eq.4 in [Puzis 2012]

        """

        for index, node in enumerate(self.QG):

            vertex = list(node)[0]

            lhs = 2 * self.QG.get_1st_addend(vertex)

            rhs = 2 * self.QG.get_2nd_addend(vertex)

            print '%s \t %f \t %f' % (node, lhs, rhs)

            communication = lhs + rhs

            self.update_by_index(index, index, communication)

    def compute_paths_between_different_equivalence_classes(self):

        """

        Calculates the Eq.5 in [Puzis 2012]

        Interclass communication importance

        """

        l = len(self.QG)

        if l <= 1:

            return

        for i in range(l - 1):

            for j in range(1, l):

                if i == j:

                    continue

                lhs = self.QG.number_of_original_vertices_by_index(i)

                rhs = self.QG.number_of_original_vertices_by_index(j)

                communication = lhs * rhs

                self.update_by_index(i, j, communication)

                self.update_by_index(j, i, communication)

class QuotientGraph(nx.Graph):

    """

    node, nodes: are used to refer to the contracted nodes in the Quotient Graph

    vertex, vertices: are used to refer to the original vertices/nodes in the Graph.

    """

    def __init__(self, QG, G = None):

        super(QuotientGraph, self).__init__(QG)

        self.G = G

    def index_by_vertex(self, vertex):

        """

        Returns the index of the nodes in the quotient graph (QG),

        when given the original vertex from the original graph G.

        """

        for index, node in enumerate(self.nodes()):

            if vertex in node:

                return index

        # TODO: should I raised "Contracted node not found"

        return -1

    def get_node(self, index):

        if index < self.number_of_nodes() and index >= 0:

            return self.nodes()[index]

        else:

            raise nx.NetworkXError

    def get_node_by_vertex(self, vertex):

        return self.get_node(self.index_by_vertex(vertex))

    def number_of_original_vertices(self, node):

        """

        Returns the number of vertices in the original graph G, when given the

        contracted node.

        node: a contracted node from QG.

        """

        return len(node)

    def number_of_original_vertices_by_index(self, index):

        """

        Returns the number of nodes/vertices in the original graph G that

        was contracted in the QG.

        """

        node = self.get_node(index)

        return self.number_of_original_vertices(node)

    def neighbors_by_vertex(self, vertex):

        """

        Returns the neighbors in the QG when given the original vertex from the G.

        """

        node = self.get_node_by_vertex(vertex)

        return self.neighbors(node)

    def number_of_original_neighbors_by_vertex(self, vertex):

        """

        Returns the total number of v's neighbors in the original graph G.

        """

        neighbors = self.neighbors_by_vertex(vertex)

        nn = 0

        for neighbor in neighbors:

            nn += self.number_of_original_vertices(neighbor)

        return nn

    def number_of_original_neighbors_by_node(self, node):

        """

        Returns the total number of node's neighbors in the original graph G.

        """

        neighbors = self.neighbors(node)

        nn = 0

        for neighbor in neighbors:

            nn += self.number_of_original_vertices(neighbor)

        return nn

    def get_1st_addend(self, vertex):

        node = self.get_node_by_vertex(vertex)

        size_node = self.number_of_original_vertices(node)

        return size_node * (size_node - 1)

    def get_2nd_addend(self, vertex):

        """

        Returns the result for 2nd addend in Eq. 4 [Puzis 2012]

        """

        neighbors = self.neighbors_by_vertex(vertex)

        total = 0

        node = self.get_node_by_vertex(vertex)

        for neighbor in neighbors:

            size_node = self.number_of_original_vertices(node)

            size_neighbor = self.number_of_original_vertices(neighbor)

            total += size_node * size_neighbor * (size_neighbor - 1) * 1.0 / (

                self.number_of_original_neighbors_by_vertex(vertex))

        return total

if __name__ == '__main__':

    filepath = MAIN_CODE_DIR + '/input/simple.edges'

    file_suffix = 'edge_list'

    # Brandes betweenness centrality

    # utility.brandes_betweenness_centrality(filepath, file_suffix)

    # Heuristic betweenness centrality

    G = nx.read_weighted_edgelist(filepath)

    same_neighbors = lambda u, v: (u not in G[v] and v not in G[u]

                                and G[u] == G[v])

    QG = QuotientGraph(nx.quotient_graph(G, same_neighbors))

    CI = CommunicationImportance(QG, G)