基于igraph的有效共邻居和优先依附

Question

我正在用pythonigraph实现一些相似性度量。特别是共同的邻居和优先的依恋。在

最初我有这个：

#!/usr/bin/env python
# encoding: utf-8

import igraph

def preferential_attachment(g, i, j):
    return g.degree(i) * g.degree(j)

def common_neighbors(g, i, j):
    return len(set(g.neighbors(i)).intersection(g.neighbors(j)))

但我认为有一种方法可以提高代码性能。有人知道如何提高代码的性能吗？在

Answer 1

预先计算邻域集合到邻接列表中，然后只使用邻接列表中的项，而不是反复查询相邻项。同样的事情也有助于度数计算，因为不需要调用方法，您可以从数组中查找度数：

class PrecalculatedStuff(object):
    def __init__(self, graph):
        self.graph = graph
        self.degrees = graph.degree()
        self.adjlist = map(set, graph.get_adjlist())

    def degree_product(self):
        return self.degrees[i] * self.degrees[j]

    def common_neighbors(self, i, j):
        return self.adjlist[i].intersection(self.adjlist[j])

另外，如果使用NumPy，度数的乘积在计算时可能更有效-本质上就是将度列表转换为NumPy向量，然后将向量（列向量）与其转置（即行向量）相乘。结果是一个矩阵，其中包含所有节点对的度积，然后用C而不是Python完成循环。在