owner_graph_metrics.py 文件源码

def getOwnerToOwnerCentrality(self, graph):
        """ compute the network centrality of all the nodes owned by a person
        with respect to all shortest paths beteween any owner"""

        nodeOwner = {}  # node -> owner
        ownerNodes = defaultdict(list)  # owner -> [nodes]
        ownerCentrality = defaultdict(int)
        ownerNodes, nodeOwner = self.get_owner_distribution(graph)
        counter = 0
        shortestPathAndDistance = {}
        for n in graph.nodes():
            shortestPathAndDistance[n] = nx.single_source_dijkstra(graph, n)
            # returns a couple (distance, path)
        for i in range(len(ownerNodes)):
            from_owner, from_nodes = ownerNodes.items()[i]
            for j in range(i+1, len(ownerNodes)):
                to_owner, to_nodes = ownerNodes.items()[j]
                shortest_path = []
                shortest_cost = 0
                for s in from_nodes:
                    for d in to_nodes:
                        if not shortest_path or shortestPathAndDistance[s][0][d] < shortest_cost:
                                shortest_path = shortestPathAndDistance[s][1][d]
                                shortest_cost = shortestPathAndDistance[s][0][d]
                counter += 1
                path_set = set([nodeOwner[node] for node in shortest_path])
                for o in path_set:
                    ownerCentrality[o] += 1
        print "# owner".rjust(long_align_space), ",",\
              "owner-to-owner cent.".rjust(long_align_space)
        for (p, c) in sorted(ownerCentrality.items(), key=lambda x: -x[1]):
            print p.rjust(long_align_space), ",",\
                str(c*1.0/counter).rjust(long_align_space)
        print ""
        print ""
        return ownerCentrality, counter