AdamicAd的快速算法

Question

我在做图形分析。我想计算一个N乘N的相似矩阵，其中包含每两个顶点之间的adam Adar相似性。为了概述ADAMAC Adar，让我从这个介绍开始：

给出无向图G的邻接矩阵A。CN是两个顶点x，y的所有公共邻域的集合。两个顶点的公共邻居是两个顶点都有一个边/链接的地方，也就是说，对于A中对应的公共邻居节点，两个顶点都有1。k_n是节点n的度数。在

adamicadar定义如下：

我的计算尝试是从A获取x和{}节点的两行，然后求和。然后寻找以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

我看不到一种降低时间复杂性的方法，但它可以矢量化：

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

使用A一个常规Numpy数组。似乎您使用的是^{}，因此{}将是一个稀疏矩阵。在这种情况下，代码将是：

^{pr2}$

这比使用Python循环要快得多。不过，有一个小警告：使用这种方法，您确实需要确保主对角线上的值（即A和{}）是您期望的值。另外，A不能包含权重，只能包含0和1。在

Answer 2

我相信你用的方法很慢。最好还原一下-
-用零初始化AA（Adamic Adar）矩阵
-对于每个节点k，它的度为k_deg
-计算d = log(1.0/k_deg)（为什么log10-它重要吗？）
-将d加到所有AA_ij，其中i，j-k_th行中的所有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

Answer 3

因为您使用的是numpy，所以可以真正减少对算法中每个操作进行迭代的需求。我的numpy和向量化fu并不是最棒的，但是下面的代码在一个有大约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的回答不同，这确实构建了完整的对称矩阵，但考虑到执行时间，效率低下（对我来说）是可以忍受的。在