计算Adamic-Adar的快速算法

Question

我正在进行图分析。 我想计算一个N乘N的相似性矩阵，其中包含每两个顶点之间的Adamic Adar相似度。 为了概述Adamic Adar，让我从这个介绍开始：给定一个无向图G的邻接矩阵A。CN是两个顶点x、y的所有公共邻居的集合。两个顶点的公共邻居是指两个顶点都有一条边/链接到该邻居节点，即在A中对应的公共邻居节点上，两个顶点都将具有1。kn是节点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 

- Jack Twain

---

你可以通过不构建common_ns_degs来节省一些计算量，而是将-log10（cn_deg）添加到S [i，j]中，其中你现在调用list（）时将其初始化为零。顺便说一句，它应该是log10（1.0 / cn_deg），而不是1.0 / log10（cn_deg）。 - dmuir

Adamic-Adar指数的公式与提供的略有不同。它是针对共同邻居k_n的sum(1/log(k_n))。代码似乎是正确的。 - Papples

Answer 1

因为你正在使用numpy，所以你可以大大减少在算法的每个操作中需要迭代的次数。我的numpy和向量化技巧并不是最好的，但以下代码在大约13,000个节点的图上运行时间约为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的答案不同，这个代码确实构建了完整的对称矩阵，但效率（对我来说）还算可以接受，鉴于执行时间。

- Mike

Answer 2

我认为你使用的方法较慢。最好还是回退到以下步骤：
- 将AA（Adamic-Adar）矩阵初始化为零
- 对于每个节点k，获取它的度数k_deg
- 计算d = log(1.0/k_deg)（为什么是log10 - 它是否重要？）
- 将d添加到所有AA_ij中，其中i,j-是邻接矩阵中第k行的所有1对的位置
编辑：
- 对于稀疏图，将k_th行中所有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

- MBo

---

“将 d 添加到所有AAij中”？您需要查找节点对P是否为共同邻居。那不也是O（n ^ 3）吗？ - Niklas B.

啊，我明白了。不错的方法，应该有很低的常数因子。 - Niklas B.

对于稀疏图，提取所有1的位置非常有用。那么如何做呢？这就是我在进行交集操作的原因，以避免O(V*3)。 - Jack Twain

你能否为你的方法写一些伪代码？ - Jack Twain

@AlexTwain 你有一个稀疏图吗？因为如果是这样的话，你为什么要使用邻接矩阵呢？ - Niklas B.

Answer 3

我相信在python_igraph中也一定有类似于R igraph中one这样的函数，用于节点相似性计算（包括Adamic_Adar）。

- academic.user

Answer 4

我看不出有降低时间复杂度的方法，但可以进行向量化：

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

使用正常的Numpy数组 A。看起来您正在使用 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不能包含权重，只能包含零和一。

- user2379410

---

我真的很喜欢这种方法。如果你想将其应用于正确的公式，如上面提到的链接。你可以将它改为：from scipy.sparse import csr_matrix A = adjacency(graph) degrees = A.sum(axis=0) degrees[degrees == 1] = 0 #节点度数为1会导致错误且不是中间节点 weights = csr_matrix(1./np.log(degrees)) adamic_adar = A.multiply(weights) * A.T - Papples