图的中心度计算

Question

我必须计算一张图的中心度。我的实施是：

import csv
class Graph:
    '''
    Representation of a simple graph using an adjacency map.
    There exist nested Classes for Vertex and Edge objects and
    useful methods for vertex and edge, edge incidence and
    vertex degree retrieval plus edge and vertex insertion
    '''

    # == Class Vertex == #
    class Vertex:
        '''
        Class for representing vertex structure for a graph.
        '''
        __slots__ = '_element'

    def __init__(self, x):
        '''
        Do not call constructor directly. Use Graph's insert_vertex(x).
        '''
        self._element = x

    def element(self):
        '''
        Return element associated with this vertex.
        '''
        return self._element

    def __hash__(self):
        '''
        will allow vertex to be a map/set key
        '''
        return hash(self._element)

    def __repr__(self):
        return '{0}'.format(self._element)

    def __eq__(self, other):
        if isinstance(other, Graph.Vertex):
            return self._element == other._element
        return False

# == Class Edge == #
class Edge:
    '''
    Class for representing edge structure for a graph.
    '''
    __slots__ = '_origin', '_destination', '_weight'

    def __init__(self, u, v, x):
        '''
        Do not call constructor directly. Use Graph's insert_edge(x).
        '''
        self._origin = u
        self._destination = v
        self._weight = x

    def endPoints(self):
        '''
        Return (u,v) tuple for vertices u and v.
        '''
        return (self._origin, self._destination)

    def opposite(self, v):
        '''
        Return the vertex that is opposite v on this edge.
        '''
        return self._destination if self._origin == v else self._origin

    def element(self):
        '''
        Return element associated with this edge.
        '''
        return self._weight

    def __hash__(self):
        '''
        will allow edge to be a map/set key
        '''
        return hash((self._origin, self._destination))

    def __repr__(self):
        if self._weight is None:
            return '({0}, {1})'.format(self._origin, self._destination)
        return '({0}, {1}, {2})'.format(self._origin, self._destination, self._weight)

# == Class Graph == #
def __init__(self, directed=False):
    '''
    Create an empty graph (undirected, by default).
    Graph is directed if optional parameter is set to True.
    '''
    self._outgoing = {}
    self._incoming = {} if directed else self._outgoing

def __getitem__(self, arg):
    return self._incoming[arg]

def is_directed(self):
    '''
    Return True if graph is directed
    '''

    return self._outgoing is not self._incoming

def vertex_count(self):
    '''
    Return the vertices count
    '''
    return len(self._outgoing)

def vertices(self):
    '''
    Return an iterator over the graph's vertices
    '''

    return self._outgoing.keys()

def get_vertex(self, el):
    '''
    Return the graph's vertex with corresponding element
    equal to el. Return None on failure
    '''
    for vertex in self.vertices():
        if vertex.element() == el:
            return vertex

    return None

def edges_count(self):
    '''
    Return the edges count
    '''

    edges = set()
    for secondary_map in self._outgoing.values():
        edges.update(secondary_map.values())
    return len(edges)

def edges(self):
    '''
    Return a set of graph's edges
    '''
    edges = set()
    for secondary_map in self._outgoing.values():
        edges.update(secondary_map.values())
    return edges

def get_edge(self, u, v):
    '''
    Return the edge from u to v
    '''
    return self._outgoing[u].get(v)

def degree(self, v, outgoing=True):
    '''
    Return the number of incident vertices to v
    If graph is directed then handle the case of indegree
    '''

    inc = self._outgoing if outgoing else self._incoming
    return len(inc[v])

def incident_edges(self, v, outgoing=True):
    '''
    Return all incident edges to node v.
    If graph is directed, handle the case of incoming edges
    '''
    inc = self._outgoing if outgoing else self._incoming
    if v not in inc:
        return None
    for edge in inc[v].values():
        yield edge

def adjacent_vertices(self, v, outgoing=True):
    '''
    Return adjacent vertices to a given vertex
    '''
    if outgoing:
        if v in self._outgoing:
            return self._outgoing[v].keys()
        else:
            return None
    else:
        if v in self._incoming:
            return self._incoming[v].keys()
        else:
            return None

def insert_vertex(self, x=None):
    '''
    Insert and return a new Vertex with element x
    '''
    for vertex in self.vertices():
        if vertex.element() == x:
            # raise exception if vertice exists in graph
            # exception can be handled from the class user
            return vertex

    v = self.Vertex(x)  # cria um objeto do tipo Vertex

    self._outgoing[v] = {}
    if self.is_directed:
        self._incoming[v] = {}

    return v

def insert_edge(self, u, v, x=None):
    '''
    Insert and return a new Edge from u to v with auxiliary element x.
    '''
    if (v not in self._outgoing) or (v not in self._outgoing):
        # raise exception if one of vertices does not exist
        # exception can be handled from the class user
        raise Exception('One of the vertices does not exist')

    if self.get_edge(u, v):
        # no multiple edges
        # exception can be handled from the class user
        e = self.Edge(u, v, x)
        return e

    e = self.Edge(u, v, x)  # cria um objeto do tipo Edge

    self._outgoing[u][v] = e
    self._incoming[v][u] = e

    return e

def remove_edge(self, u, v):
    if not self.get_edge(u, v):
        # exception for trying to delete non-existent edge
        # can be handled from class user
        raise Exception('Edge is already non-existent.')

    u_neighbours = self._outgoing[u]
    del u_neighbours[v]
    v_neighbours = self._incoming[v]
    del v_neighbours[u]

def remove_vertex(self, x):
    '''
    Delete vertex and all its adjacent edges from graph
    '''

    if (x not in self._outgoing) and (x not in self._incoming):
        raise Exception('Vertex already non-existent')

    secondary_map = self._outgoing[x]
    for vertex in secondary_map:
        # delete reference to incident edges
        if self.is_directed():
            del self._incoming[vertex][x]
        else:
            del self._outgoing[vertex][x]
    # delete reference to the vertex itself
    del self._outgoing[x]

def printG(self):
    '''Mostra o grafo por linhas'''
    print('Grafo Orientado:', self.is_directed())

    '''Mostra o número de vertices'''
    print("Número de Vertices: {}".format(G.vertex_count()))

    '''Mostra o número de arestas'''
    print("Número de Arestas: {}".format(G.edges_count()))

    for v in self.vertices():
        print('\nUser: ', v, ' grau_in: ', self.degree(v, False), end=' ')
        if self.is_directed():
            print('grau_out: ', self.degree(v, False))
        for i in self.incident_edges(v):
            print(' ', i, end=' ')
        if self.is_directed():
            for i in self.incident_edges(v, False):
                print(' ', i, end=' ')

我的图表由CSV文件构成：

def read_csv(filename):
    G = Graph()  # cria um objeto do tipo Graph

    with open(filename, 'r') as csv_file:  # abre o ficheiro csv
        data = csv.reader(csv_file)
        next(data)  # ignora a primeira coluna do ficheiro

        for linha in data:  # por cada linha no ficheiro
            id_origem = linha[0]  # a origem é a primeira coluna do ficheiro
            id_destino = linha[1]  # o destino é a segunda coluna do ficheiro
            peso = linha[2] if len(linha) > 2 else 1  # se não existir uma terceira coluna do ficheiro
            # assume-se que o peso das arestas, é 1

            v_origem = G.insert_vertex(id_origem)  # insere o vertex no grafo
            v_destino = G.insert_vertex(id_destino)  # insere o vertex no grafo

            G.insert_edge(v_origem, v_destino, int(peso))  # insere a aresta no grafo

    return G

CSV文件具有以下结构：

follower,followed,distance
Murphy,Thornton,45
Perkins,Walters,26
Perkins,Bradley,7
Lawrence,Hart,15

最短距离通过以下公式计算：

def shortest_path_lengths(g, src):

    d = {}
    cloud = {}
    pq = AdaptableHeapPriorityQueue()
    pqlocator = {}
    source = Graph.Vertex(src)

    for v in G.vertices():
        if v == source:
            d[v] = 0
        else:
            d[v] = float('inf')
        pqlocator[v] = pq.add(d[v], v)


    while not pq.is_empty():
        key, u = pq.remove_min()
        cloud[u] = key
        del pqlocator[u]
        for e in G.incident_edges(u):
            v = e.opposite(u)
            if v not in cloud:
                wgt = e.element()
                if d[u] + wgt < d[v]:
                    d[v] = d[u] + wgt
                    pq.update(pqlocator[v], d[v], v)

    return cloud

我根据以下公式计算中心度：

def centrality_degree(G, src=None):
    distances = []
    closeness_centr = []
    short = shortest_path_lengths(G, src)
    #print(short)
    vertex_number = G.vertex_count()
    #while contador <= len(short):
    #for vertex in G.vertices(): #G.adjacent_vertices(G.get_vertex(src)):
    for value in short.values():
        if value != float('inf'):
            distances.append(value)
    print(distances)
    soma = sum(distances)
    #print(soma)
    formula = (vertex_number-1)/soma
    closeness_centr.append(formula)
    print(closeness_centr)

有没有办法在不传递参数src的情况下计算中心度

Answer 1

尝试：

def centrality_degree(G):
    n_vertex = ...
    # compute all the shortest paths from the node i to j 
    # (do a for in a for)
    degree = ...
    return degree