p**o
发帖数: 3409 | 1 【 以下文字转载自 Mathematics 讨论区 】
发信人: pulo (普罗), 信区: Mathematics
标 题: How to efficiently enumerate triangles in a large network?
发信站: BBS 未名空间站 (Mon Aug 16 11:12:59 2010, 美东)
无向图，10万个节点，50万条边。
已经在Matlab中用spconvert读入成上三角的0-1稀疏方阵A。
请问如何迅速找齐满足以下条件的所有(i,j,k)？
i
A(i,j)=A(j,k)=A(i,k)=1
三个for循环蛮干的话时间复杂度是节点数的立方，有没有快一些的算法？ | w***g
发帖数: 5958 | 2 how about this:
while graph not empty
do
pick a vertex V at random
for each pair of different U1, U2 in V's neighbors
do
if edge exists then emit triangle {V, U1, U2}
done
remove V from graph
done
It's not O(N^3), but O(ND^2), D=maximal degree.
One refinement of the algorithm would be to eliminate vertices according to
ascending order of degree, and keep that order as you remove vertices. At
each loop, the removal of one vertex will cause the degree of a few vertices
(the number is m
【在 p**o 的大作中提到】
: 【 以下文字转载自 Mathematics 讨论区 】
: 发信人: pulo (普罗), 信区: Mathematics
: 标 题: How to efficiently enumerate triangles in a large network?
: 发信站: BBS 未名空间站 (Mon Aug 16 11:12:59 2010, 美东)
: 无向图，10万个节点，50万条边。
: 已经在Matlab中用spconvert读入成上三角的0-1稀疏方阵A。
: 请问如何迅速找齐满足以下条件的所有(i,j,k)？
: i: A(i,j)=A(j,k)=A(i,k)=1
: 三个for循环蛮干的话时间复杂度是节点数的立方，有没有快一些的算法？
| s********r
发帖数: 277 | 3 Fast Counting of Triangles in Large Real Networks:
Algorithms and Laws | l******e
发帖数: 470 | 4 foreach edge (u,v)
foreach neighbor w of v
check if (v,w) exists
time O(ED), slightly better :)
【在 w***g 的大作中提到】
: how about this:
: while graph not empty
: do
: pick a vertex V at random
: for each pair of different U1, U2 in V's neighbors
: do
: if edge exists then emit triangle {V, U1, U2}
: done
: remove V from graph
: done
| l******e
发帖数: 470 | 5 lz wants enumerating, not approx counting...
【在 s********r 的大作中提到】
: Fast Counting of Triangles in Large Real Networks:
: Algorithms and Laws
| w***g
发帖数: 5958 | 6 the related work section gives some enumerating methods though.
【在 l******e 的大作中提到】
: lz wants enumerating, not approx counting...
| p**o
发帖数: 3409 | 7 Thanks for your input! I got the codes optimized:
len = length(A);
for i=1:(len-2)
index = find( A(i,(i+1):len)==1 ) +i;
for jj = 1:(length(index)-1)
j=index(jj);
for kk=(jj+1):length(index)
k=index(kk);
if A(j,k)==1
% record (i,j,k)
end
end
end
end
The complexity looks like O( |V|* (|V|+max_degree^2) )
= O(|V|^2) for sparse matrices,
assuming "find" is of O(|V|) and accessing A(j,k) costs O(1).
The most naiv |
|
