使用 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.

中完成

使用 igraph 的高效共同邻居和优先依附

Efficient common neighbors and preferential attachment using igraph

python

performance

time-complexity

igraph