快速计算Adamic-Adar的算法

Question

我正在做图分析，想要计算一个N乘N的相似度矩阵，这个矩阵里包含每两个顶点之间的Adamic Adar相似度。为了让大家更好地理解Adamic Adar，我先做个简单介绍：

给定一个无向图G的邻接矩阵A。CN是两个顶点x和y的所有共同邻居的集合。两个顶点的共同邻居是指这两个顶点之间有边/连接的节点，也就是说在A中，这两个顶点对应的共同邻居节点的值都是1。k_n是节点n的度数，也就是它连接的边的数量。

Adamic-Adar的定义如下：

我尝试计算这个相似度的方法是从A中提取x和y节点的两行数据，然后把它们相加。接着查找值为2的元素，再获取它们的度数并应用公式。然而，这样计算起来真的非常耗时。我尝试用一个包含1032个顶点的图进行计算，结果花了很长时间。开始时需要7分钟，后来我就取消了计算。所以我的问题是：有没有更好的算法来计算这个？

这是我用Python写的代码：

def aa(graph):

"""
    Calculates the Adamic-Adar index.

"""
N = graph.num_vertices()
A = gts.adjacency(graph)
S = np.zeros((N,N))
degrees = get_degrees_dic(graph)
for i in xrange(N):
    A_i = A[i]
    for j in xrange(N):
        if j != i:
            A_j = A[j]
            intersection = A_i + A_j
            common_ns_degs = list()
            for index in xrange(N):
                if intersection[index] == 2:
                    cn_deg = degrees[index]
                    common_ns_degs.append(1.0/np.log10(cn_deg))
            S[i,j] = np.sum(common_ns_degs)
return S 

Answer 1

我觉得在 python_igraph 里，应该也有一个类似于 这个 的函数，用来计算节点之间的相似度（比如 Adamic_Adar 方法）。

Answer 2

我看不出有什么办法可以降低时间复杂度，但可以通过向量化来提高效率：

degrees = A.sum(axis=0)
weights = np.log10(1.0/degrees)
adamic_adar = (A*weights).dot(A.T)

这里的 A 是一个普通的 Numpy 数组。你似乎在使用 graph_tool.spectral.adjacency，所以 A 应该是一个稀疏矩阵。在这种情况下，代码应该是：

from scipy.sparse import csr_matrix

degrees = A.sum(axis=0)
weights = csr_matrix(np.log10(1.0/degrees))
adamic_adar = A.multiply(weights) * A.T

这种方法比使用 Python 的循环要快得多。不过，有一点小警告：使用这种方法时，你需要确保 A 和 adamic_adar 的主对角线上的值是你所期望的。此外，A 不能包含权重，只能是零和一。

Answer 3

我觉得你现在的方法有点慢。可以试试换个做法：
- 首先，把AA（Adamic-Adar）矩阵初始化为全零
- 然后，对于每个节点k，获取它的度数k_deg
- 计算 d = log(1.0/k_deg) （这里用log10重要吗？）
- 接着，把d加到所有AA_ij中，其中i,j是邻接矩阵中第k行的所有1的配对
补充：
- 对于稀疏图，提取第k行中所有1的位置到一个列表中，这样可以把复杂度降到O(V*(V+E))，而不是O(V^3)

AA = np.zeros((N,N))
for k = 0 to N - 1 do
    AdjList = []
    for j = 0 to N - 1 do
        if A[k, j] = 1 then
            AdjList.Add(j)
    k_deg = AdjList.Length
    d = log(1/k_deg)
    for j = 0 to AdjList.Length - 2 do
      for i = j+1 to AdjList.Length - 1 do
         AA[AdjList[i],AdjList[j]] = AA[AdjList[i],AdjList[j]] + d  
         //half of matrix filled, it is symmetric for undirected graph

Answer 4

因为你在使用numpy，所以你可以大大减少在算法中每次操作时的循环次数。我的numpy和向量化的技巧不是特别好，但下面的代码在大约有13000个节点的图上运行大约需要2.5秒：

def adar_adamic(adj_mat):    
    """Computes Adar-Adamic similarity matrix for an adjacency matrix"""

    Adar_Adamic = np.zeros(adj_mat.shape)
    for i in adj_mat:
        AdjList = i.nonzero()[0] #column indices with nonzero values
        k_deg = len(AdjList)
        d = np.log(1.0/k_deg) # row i's AA score

        #add i's score to the neighbor's entry
        for i in xrange(len(AdjList)):
            for j in xrange(len(AdjList)):
                if AdjList[i] != AdjList[j]:
                    cell = (AdjList[i],AdjList[j])
                    Adar_Adamic[cell] = Adar_Adamic[cell] + d

    return Adar_Adamic

与MBo的回答不同，这段代码确实构建了完整的对称矩阵，不过对于我来说，这种效率上的损失是可以接受的，因为执行时间还算不错。