Общие соседи и матрицы преимущественных вложений с использованием igraph для python - PullRequest
Новая
       8

Общие соседи и матрицы преимущественных вложений с использованием igraph для python

6 голосов
/ 09 июля 2011

Существует ли эффективный способ вычисления оценки матрицы для общих соседей (CC) и привилегированного вложения (PA) в python? Я использую igraph для вычисления матриц оценок для других методов, таких как коэффициент jaccard (Graph.simility_jaccard ()), dice (Graph.simility_dice) и adamic / adar (Graph.simility_inverse_log_weighted ()), но я не нашел никакой функции вычислить оценочные матрицы для CC и PA.

В настоящее время я делаю: 

#Preferential attachment score between nodes i and j in a graph g
len(g.neighbors(i))*len(g.neighbors(j))

#Common neighbors score between nodes i and j in a graph g
len(g.neighbors(i) and g.neighbors(j))

но я должен сделать это для всех ребер (i, j) в сети, которая в моем случае действительно велика.

Если кто-нибудь знает какую-либо математическую матричную операцию, которая генерирует такие матрицы оценок, которые я ищу, я был бы также признателен.

1 Ответ

2 голосов
/ 09 июля 2011

В igraph нет прямой функции для этого. Тем не менее, обратите внимание, что len(g.neighbors(i)) - это просто степень вершины i , поэтому вы можете вызвать g.degree(), обработать ее как одномерную матрицу, используя NumPy, а затем умножить ее на собственный transpose s.t. вектор столбца умножается на вектор строки справа. Это дает вам матрицу преимущественных вложений: 

from numpy import matrix
d = matrix(g.degree())
pref_score_matrix = d.T*d

Общая оценка соседей сложнее с использованием матричной нотации, и я бы не стал работать с матрицами в любом случае, если ваш граф действительно большой (даже с 2000 вершинами, у вас будет матрица с 4 миллионами элементов). Я просто кэшировал бы представления наборов g.neighbors(i) для всех возможных значений в списке, а затем использовал это для вычисления общих оценок соседей, поскольку наборы могут эффективно пересекаться: 

neisets = [set(g.neighbors(i)) for i in xrange(g.vcount())]
for v1, v2 in g.get_edgelist():
    common_neis = neisets[v1].intersection(neisets[v2])
    print "%d --> %d: %d" % (v1, v2, len(common_neis))

Если вы действительно хотите придерживаться матриц, вы можете построить матрицу n на n , состоящую только из нулей, используя функцию zeros из NumPy, а затем зациклить на вершинах один раз. Получите всех соседей вершины v и обратите внимание, что любая пара соседей v имеет одного общего соседа: v сам по себе: 

from itertools import combinations
from numpy import zeros

n = g.vcount()
common_neis = zeros(n, n)
for v in xrange(g.vcount()):
    neis = g.neighbors(v)
    for u, w in combinations(neis, 2):
        # v is a common neighbor of u and w
        common_neis[u, w] += 1
        common_neis[w, u] += 1
...