有向图相似度计算--优化数学代码

Question

我希望优化以下计算。首先是一些解释：

解释

我有一个有向图，它的邻接矩阵可能只包含1s和0。节点i和j的相似性定义如下：

1. 计算有多少个节点具有指向i和j的边，并计算i和j都指向多少个节点。
2. 将这两个计数的和除以i或j连接到的节点总数。

我需要找到图中每个节点的最大相似度(它与除其本身之外的任何其他节点的相似性)，并计算这些数字的平均值。

我正在处理的图不一定是连通的，但它们没有大小为1的组件(即没有连接到任何其他节点的节点)。

代码

meanMaxSim[g_Graph] :=
 Module[{am, pList, similarityMatrix},
  am = AdjacencyMatrix[g];
  pList = Transpose@Join[am, Transpose[am]];
  similarityMatrix = Outer[Total[#1 #2]/Total[Sign[#1 + #2]] &, pList, pList, 1];
  Mean[Max /@ dropDiagonal[similarityMatrix]]
]

(Sign用于保持0，并将任何较大的值转换为1s。)

此函数只是删除n乘n矩阵对角线上的元素，最后得到n乘n-1矩阵：

dropDiagonal[matrix_] := 
 MapThread[Drop[#1, {#2}] &, {matrix, Range@Length[matrix]}]

Graph[]只在数学8中可用，但这与此无关，因为大多数时间都是在Outer[]上度过的。如果您有一个较早的版本，只需假设您以邻接矩阵作为SparseArray作为起点。

我正在寻找修改，以加快这一速度(超过3x)，但任何其他评论的代码是最受欢迎的。希望在不显著增加代码复杂度的情况下可以加快速度。

Notes

用机器编号进行计算是可以的，但我没有费心去做，因为它没有提供显著的加速效果。

关于自循环的一个注意事项:它们在图中是允许的，是的，在这个实现中它们是双重计数的。

编辑：

我问这个问题太快了。下面是使用Compile的~4x加速比。我仍然对评论/进一步的加速感兴趣。

simMatCompiled = 
  Compile[{{p, _Real, 2}},
    Table[Total[a b]/Total@Sign[a + b], {a, p}, {b, p}]
  ];

mxSim[g_Graph] :=
  Module[{am, pList, similarityMatrix},
    am = N@AdjacencyMatrix[g];
    pList = Transpose@Join[am, Transpose[am]];
    similarityMatrix = simMatCompiled[Normal[pList]];
    Mean[Max /@ dropDiagonal[similarityMatrix]]
  ]

我需要将Outer更改为Table，以便Compile能够完成它的工作。

Answer 1

略有改进，但考虑使用：

pList = ArrayFlatten[{{am\[Transpose], am}}];

和

dropDiagonal = MapThread[Delete, {#, Range@Length@#}] &;

我也尝试过dropDiagonal = MapIndexed[Drop, #] &，但这比较慢，至少在v7中是这样的。

取代：

Total[#1 #2]/Total[Sign[#1 + #2]] &

通过以下方式：

#.#2 / Tr@Unitize[#1 + #2] &

我认为这是对您编写的功能的改进：

Compile[{{p, _Real, 2}}, 
  With[{b = p\[Transpose]},
    #.b / Total@Sign[# + b] & /@ p
  ]
]