从对称邻接矩阵的两列中寻找公共元素

Question

我有一个稀疏对称矩阵，它表示某本书的作者。如果与索引i和j相关联的人是合著者，则元素Ai，j和Aj，i都等于1，否则等于0。我试图在矩阵表示中找到一种方法，这样给定两列(作者(，我就可以找到它们的共同作者。最好使用Matlab或Julia代码表示。

Answer 1

列之间的二进制&以元素方式应用，将返回一个具有1s的向量，仅当两列都具有1s时。您可以在此基础上执行findall，然后返回结果为1的索引，这表示共同作者。

julia> A
5×5 SparseMatrixCSC{Bool, Int64} with 12 stored entries:
⋅  1  ⋅  1  1
1  ⋅  ⋅  ⋅  1
⋅  ⋅  ⋅  ⋅  1
1  ⋅  ⋅  ⋅  1
1  1  1  1  ⋅
julia> common = A[:, 1] .& A[:, 5]
5-element SparseVector{Bool, Int64} with 2 stored entries:
[2]  =  1
[4]  =  1
julia> findall(common)
2-element Vector{Int64}:
2
4

这在Julia中发现了作者1和5之间的共同作者。&之前的.表示运算符应按元素应用。为了对此进行概括，您可以将其写成如下函数：

julia> function findcommoncoauths(adjmat, author1, author2)
@views findall(adjmat[:, author1] .& adjmat[:, author2])
end

(@views是为了避免不必要地为列分配新内存，这对于高性能代码来说是一种很好的做法。(

Answer 2

如果作者协作矩阵很大，那么利用稀疏性是很好的。SparseArrays提供了许多优化的功能(有些已导出，有些未导出(。例如，计算点积的稀疏矢量上的dot(在LinearAlgebra中定义(。由于稀疏矩阵存储在列中(CSC格式(，因此将列作为SparseVectors很快。因此，计算作者i和j之间的共同作者数量：

@views dot(adjmat[:,i], adjmat[:,j])

工作速度快。这里有一个例子：

julia> using SparseArrays, LinearAlgebra
julia> M = sprand(Bool,100,100,0.1);  # random boolean matrix
julia> M = M .| M';            # symetric coauthorship
julia> M[diagind(M)] .= false; # no self-coauthorship
julia> M
100×100 SparseMatrixCSC{Bool, Int64} with 1841 stored entries:
⠊⡠⠗⠀⠕⡛⢲⣢⠼⠥⠀⢀⡂⠲⠦⠋⡐⠰⠆⠲⠊⠖⡷⠿⠅⠘⡫⠱⠳⠔
⠙⠁⣏⠙⡣⢎⠓⢮⢢⠣⡴⢀⡂⣊⢙⣈⣯⢮⡁⣂⣺⡏⡰⢁⠯⢜⠐⣈⠼⠜
⣵⠡⡩⢎⡁⡨⣦⣥⠙⡌⠯⡙⣏⡬⢛⠀⢡⢀⢔⢔⢲⡍⠚⣁⣉⢥⡁⣆⣤⠇
⠸⣲⡹⣄⠌⣿⢴⠓⣝⠒⣂⢕⠏⡱⡒⣠⠶⡰⠆⣈⠑⡖⣇⡐⠺⠠⠄⡖⠹⡦
⠖⡇⠬⡒⡓⠤⢳⠙⠋⠄⠜⢰⡖⠨⡀⡄⣒⡨⠒⡘⠤⠄⠆⠆⢮⢜⠥⠴⠔⠄
⠀⢀⠐⢋⣏⠣⢌⢜⢒⣁⣋⠘⡎⢍⠸⠢⢻⣸⡀⢋⡈⣂⣏⠋⢸⢰⣖⢰⡡⡆
⢨⡈⡨⢨⡋⡽⢏⡡⡘⡉⡎⢍⣊⠘⢯⣍⡸⡪⢅⣫⣾⡉⠶⠀⠿⠈⢥⠽⢅⡍
⡬⠃⡓⢰⠛⠐⠘⣨⠀⠬⠲⡂⡏⢷⣀⠘⠊⢲⠃⡰⠠⡆⢂⠔⣕⢂⡄⣺⠖⠮
⢐⡈⡫⣟⠁⢒⢘⡣⡘⡸⣛⣲⡲⡪⢪⣀⠎⠅⣒⣙⣙⡇⠳⢊⠕⢸⣢⣒⡫⣂
⢨⡁⠡⢨⢐⢕⡈⢡⣘⠠⡤⢈⡥⣱⢉⡠⣜⢸⢤⡷⠨⠍⣹⠀⠀⢰⢺⣫⠬⡥
⢪⠄⡾⠾⡜⠶⢱⠤⠀⠇⠢⢨⡞⠻⠠⠦⠷⠼⡆⠆⠴⠃⢾⠔⠖⠘⢇⠞⠲⡶
⣽⡏⠔⢊⠞⢠⢉⠹⠨⠅⡯⠙⠘⠃⢈⠔⡹⢂⠓⠚⢚⠗⡎⠉⠟⢊⠂⡑⣡⠁
⣁⠁⣋⢇⠇⣜⠚⡂⣊⢗⢒⣒⡛⠃⠱⢙⣑⣁⢀⣀⣘⠁⡻⢁⠺⠂⡿⢚⠟⡐
⢏⡊⡐⢠⠡⢬⢠⠥⢁⡇⢘⣙⣅⡗⣠⣩⢨⢺⡾⣲⣩⠕⢌⠠⣻⢋⠀⠀⢩⣣
⢙⠆⣒⠇⠤⠟⠳⡦⠐⠅⠡⠮⡅⠵⡸⡅⠫⢪⠆⡧⢸⡦⠅⠚⢛⠡⠧⣲⠀⠀
julia> @views dot(M[:,1], M[:,2])
5

最后一行显示作者#1和作者#2有5个共同的合著者。

这个问题需要一个常见合著者的列表，不幸的是dot通过聚合丢失了这些信息。

这篇文章的另一个答案(Sundar(提供了一个解决方案：

function findcommoncoauths(adjmat, author1, author2)
@views findall(adjmat[:, author1] .& adjmat[:, author2])
end

给出上述矩阵的结果：

julia> findcommoncoauths(M, 1, 2)
5-element Vector{Int64}:
17
74
78
80
88

该方法使用.&算子，该算子使用广播，因此不利用矩阵稀疏性。此外，尽管问题没有具体说明，但可能只需要普通的合著者进行处理，而不一定需要存储，所以最好对它们进行迭代。

下面是一个迭代器：

struct SparseColumnCommon{T,I}
iistart::I
jjstart::I
iimax::I
jjmax::I
parent::SparseMatrixCSC{T,I}
end
function sparsecolumncommon(M::SparseMatrixCSC{T,I}, i::I, j::I) where {T,I}
ii = first(nzrange(M,i))
iimax = last(nzrange(M,i))
jj = first(nzrange(M,j))
jjmax = last(nzrange(M,j))
SparseColumnCommon{T,I}(ii, jj, iimax, jjmax, M)
end
Base.eltype(::Type{SparseColumnCommon{T,I}}) where {T,I} = Tuple{I, T, T}
Base.IteratorSize(::Type{SparseColumnCommon{T,I}}) where {T,I} = Iterators.Base.SizeUnknown()
function Base.iterate(it::SparseColumnCommon, state=(it.iistart, it.jjstart))
ii, jj = state
while ii <= it.iimax && jj <= it.jjmax
ri, rj = (it.parent.rowval)[ii], (it.parent.rowval)[jj]
if ri == rj
return ((ri, (it.parent.nzval)[ii], (it.parent.nzval)[jj]), (ii+1, jj+1))
elseif ri < rj
ii += 1
else rj < ri
jj += 1
end
end
return nothing
end

有了这个定义(也许在一个单独的包含文件中(，我们可以用它来定义：

findcommoncoauths2(adjmat, author1, author2) = 
map(first, sparsecolumncommon(adjmat, author1, author2))

和以前一样：

julia> findcommoncoauths2(M,1,2)
5-element Vector{Int64}:
17
74
78
80
88

迭代器还可以用于逐个处理常见的合著者，而无需分配可能有用的输出向量。

最后，也许这个迭代器也可以用于其他稀疏矩阵列任务。它在每次迭代中返回一个三元组：(row, column1val, column2val)。

这已经是一个很长的答案了，但基准测试表明，对于稀疏且足够大的矩阵(足够大也不算太大(，使用这种迭代器会更快。