p*o
2 楼
【 以下文字转载自 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
三个for循环蛮干的话时间复杂度是节点数的立方，有没有快一些的算法？
发信人: 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
三个for循环蛮干的话时间复杂度是节点数的立方，有没有快一些的算法？
k*0
3 楼
祝大家好运
g*t
4 楼
虽然不认为他有多大贡献,但他说的倒确实没错过.
【在 H*******s 的大作中提到】
: 但愿， 他的 其他 预测 别说对了。 我猜。 P838 的 PD 可能 就是 2006年初。
【在 H*******s 的大作中提到】
: 但愿， 他的 其他 预测 别说对了。 我猜。 P838 的 PD 可能 就是 2006年初。
w*g
5 楼
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
: 三个for循环蛮干的话时间复杂度是节点数的立方，有没有快一些的算法？
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
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
: 三个for循环蛮干的话时间复杂度是节点数的立方，有没有快一些的算法？
r*q
6 楼
good luck!
p*8
7 楼
Mr.O email is o********[email protected], p838 = b838 = p636透露的
s*r
8 楼
Fast Counting of Triangles in Large Real Networks:
Algorithms and Laws
Algorithms and Laws
a*b
9 楼
are we supposed to wait until friday?
D*9
10 楼
it will be out around 6 pm
l*e
11 楼
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
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
: done
: remove V from graph
: done
k*0
12 楼
still not posted..
【在 a*****b 的大作中提到】
: are we supposed to wait until friday?
【在 a*****b 的大作中提到】
: are we supposed to wait until friday?
f*n
13 楼
哪天？
【在 D******9 的大作中提到】
: it will be out around 6 pm
【在 D******9 的大作中提到】
: it will be out around 6 pm
l*e
14 楼
lz wants enumerating, not approx counting...
【在 s********r 的大作中提到】
: Fast Counting of Triangles in Large Real Networks:
: Algorithms and Laws
【在 s********r 的大作中提到】
: Fast Counting of Triangles in Large Real Networks:
: Algorithms and Laws
j*e
15 楼
开始焦虑了。。。。
A*d
16 楼
guys, do not send emails individually unless you have urgent request.
Otherwise O will feel uncomfortable and overwhelmed by tons of emails. It is
not beneficial to our Chinese group.
I do not know which organization P838 claimed he is in when he talked with O
. The sense is that he must claim he represents an organization otherwise O
won't communicate with him regularly.
I am just curious about which organization P838 claims himself, LIA or NIU
to O. Who knows?
【在 p**8 的大作中提到】
: Mr.O email is o********[email protected], p838 = b838 = p636透露的
Otherwise O will feel uncomfortable and overwhelmed by tons of emails. It is
not beneficial to our Chinese group.
I do not know which organization P838 claimed he is in when he talked with O
. The sense is that he must claim he represents an organization otherwise O
won't communicate with him regularly.
I am just curious about which organization P838 claims himself, LIA or NIU
to O. Who knows?
【在 p**8 的大作中提到】
: Mr.O email is o********[email protected], p838 = b838 = p636透露的
w*g
17 楼
the related work section gives some enumerating methods though.
【在 l******e 的大作中提到】
: lz wants enumerating, not approx counting...
【在 l******e 的大作中提到】
: lz wants enumerating, not approx counting...
v*m
18 楼
passed C!
H*s
19 楼
p888 ===== p838 = b838 = p636 ?
故意放 电子邮件， 捣乱。
故意放 电子邮件， 捣乱。
p*o
20 楼
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
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
j*e
21 楼
haha nailed mlc
p*6
22 楼
发信人: p838 (只关心EB-2共同利益), 信区: EB23
标 题: Re: July VB:EB2C = Nov 22,2005, EB3C = Aug 15,2003, EB2I =
发信站: BBS 未名空间站 (Wed Jun 9 14:43:11 2010, 美东)
我和他他联系时，还只有LIA，还没有NIU。
is
O
O
标 题: Re: July VB:EB2C = Nov 22,2005, EB3C = Aug 15,2003, EB2I =
发信站: BBS 未名空间站 (Wed Jun 9 14:43:11 2010, 美东)
我和他他联系时，还只有LIA，还没有NIU。
is
O
O
x*g
23 楼
pass mfe, mlc :-)
p*6
24 楼
how are you? P888
is it a real email address? I never told you the address.
【在 p**8 的大作中提到】
: Mr.O email is o********[email protected], p838 = b838 = p636透露的
is it a real email address? I never told you the address.
【在 p**8 的大作中提到】
: Mr.O email is o********[email protected], p838 = b838 = p636透露的
k*0
25 楼
o yeah me 2
【在 x**********g 的大作中提到】
: pass mfe, mlc :-)
【在 x**********g 的大作中提到】
: pass mfe, mlc :-)
p*6
26 楼
are you 捣乱?
【在 H*******s 的大作中提到】
: p888 ===== p838 = b838 = p636 ?
: 故意放 电子邮件， 捣乱。
【在 H*******s 的大作中提到】
: p888 ===== p838 = b838 = p636 ?
: 故意放 电子邮件， 捣乱。
M*e
27 楼
包子。。。
w*i
28 楼
没看出来排期是那天?
a*b
29 楼
楼上过了的发包子吧
N*s
30 楼
good i am indian and will be emailing him like crazy!
t*y
31 楼
少来，你自己 肯定过了FETE
【在 M***e 的大作中提到】
: 包子。。。
【在 M***e 的大作中提到】
: 包子。。。
M*e
32 楼
咳咳，低调。。。 你老发包子吧
【在 t****y 的大作中提到】
: 少来，你自己 肯定过了FETE
【在 t****y 的大作中提到】
: 少来，你自己 肯定过了FETE
f*u
33 楼
为什么我还查不到成绩...
w*1
34 楼
SOA only Released Passing Candidate Numbers for the November 2009 Exams
today. You will see your grade on the next Monday.
【在 f*********u 的大作中提到】
: 为什么我还查不到成绩...
n*e
35 楼
恭喜毛哥！
【在 M***e 的大作中提到】
: 咳咳，低调。。。 你老发包子吧
【在 M***e 的大作中提到】
: 咳咳，低调。。。 你老发包子吧
t*r
36 楼
FETE, pass here:)
I*R
37 楼
你们两个老革命都该给新同志做点表率么
【在 M***e 的大作中提到】
: 咳咳，低调。。。 你老发包子吧
【在 M***e 的大作中提到】
: 咳咳，低调。。。 你老发包子吧
f*u
38 楼
谢谢～ 看到 Passing Candidate Numbers了～
【在 w**********1 的大作中提到】
:
: SOA only Released Passing Candidate Numbers for the November 2009 Exams
: today. You will see your grade on the next Monday.
【在 w**********1 的大作中提到】
:
: SOA only Released Passing Candidate Numbers for the November 2009 Exams
: today. You will see your grade on the next Monday.
M*e
39 楼
莫急，过两个月做完dmac拿完证书我捐几百伪币到版上
【在 I**R 的大作中提到】
: 你们两个老革命都该给新同志做点表率么
【在 I**R 的大作中提到】
: 你们两个老革命都该给新同志做点表率么
I*R
40 楼
此据
虽然现在利息不高，但是这两个月的利钱，嘿嘿，您琢磨着给添点儿？
【在 M***e 的大作中提到】
: 莫急，过两个月做完dmac拿完证书我捐几百伪币到版上
虽然现在利息不高，但是这两个月的利钱，嘿嘿，您琢磨着给添点儿？
【在 M***e 的大作中提到】
: 莫急，过两个月做完dmac拿完证书我捐几百伪币到版上
x*g
41 楼
2 10 hoho
【在 x**********g 的大作中提到】
: pass mfe, mlc :-)
【在 x**********g 的大作中提到】
: pass mfe, mlc :-)
k*0
42 楼
呵呵，这不是赤裸裸的。。。
【在 x**********g 的大作中提到】
: 2 10 hoho
【在 x**********g 的大作中提到】
: 2 10 hoho
相关阅读