Các láng giềng chung và ma trận điểm chấp nhận ưu tiên sử dụng igraph cho python

Question

Có cách nào hiệu quả để tính toán điểm ma trận cho những người hàng xóm chung (CC) và tập tin đính kèm ưu tiên (PA) trong python không? Tôi đang sử dụng igraph để tính toán các ma trận điểm cho các phương thức khác như hệ số của jaccard (Graph.similarity_jaccard()), dice (Graph.similarity_dice) và adamic/adar (Graph.similarity_inverse_log_weighted()), nhưng tôi không tìm thấy bất kỳ hàm nào để tính toán các ma trận điểm cho CC và PA.

Hiện nay tôi đang làm:

#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)) 

nhưng tôi phải làm điều này cho tất cả các cạnh (i, j) trong mạng mà trong trường hợp của tôi là thực sự lớn.

Nếu có ai biết bất kỳ phép toán ma trận toán học nào tạo ra các ma trận điểm số như tôi đang tìm, tôi cũng sẽ đánh giá cao.

Answer 1

Không có chức năng trực tiếp cho điều này trong igraph. Tuy nhiên, lưu ý rằng len(g.neighbors(i)) chỉ đơn giản là mức độ của đỉnh i, vì vậy bạn có thể gọi g.degree(), coi nó là ma trận 1D bằng cách sử dụng NumPy, sau đó nhân nó với s.t. một vector cột được nhân với một vectơ hàng từ bên phải. Điều này sẽ cho bạn những ưu đãi ma trận điểm tập tin đính kèm:

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

Những người hàng xóm chung điểm là phức tạp hơn sử dụng ký hiệu ma trận, và tôi sẽ không hoạt động với ma trận anyway nếu đồ thị của bạn là thực sự lớn (ngay cả với chỉ 2000 đỉnh, bạn sẽ có ma trận với 4 triệu phần tử). Tôi sẽ chỉ đơn giản là cache cơ quan đại diện của g.neighbors(i) đặt cho tất cả các giá trị có thể có trong một danh sách, và sau đó sử dụng để tính điểm hàng xóm phổ biến như bộ có thể được giao nhau một cách hiệu quả:

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ếu bạn thực sự muốn dính vào ma trận, bạn có thể tạo một mã vạch n bởi n gồm số không chỉ sử dụng hàm zeros từ NumPy và sau đó lặp lại các đỉnh một lần. Nhận được tất cả những người hàng xóm của đỉnh v và lưu ý rằng bất kỳ cặp của các nước láng giềng của v có một người hàng xóm chung: v bản thân:

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