有效的常见邻居和使用igraph优惠附件

Question

我正在实施一些与python-igraph相似的措施。特别常见的邻居和优惠依恋。

起初，我有这样的：

#!/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语言完成。