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 A(i,j)=A(j,k)=A(i,k)=1
三个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 楼
祝大家好运
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 : A(i,j)=A(j,k)=A(i,k)=1
: 三个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
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透露的
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透露的
M*e
27 楼
包子。。。
w*i
28 楼
没看出来排期是那天?
a*b
29 楼
楼上过了的发包子吧
N*s
30 楼
good i am indian and will be emailing him like crazy!
f*u
33 楼
为什么我还查不到成绩...
t*r
36 楼
FETE, pass here:)
相关阅读
明天面试 预祝好运啊Merry ChristmasMidwest 公司招精算师 (ASA, near FSA or FSA)考过FSA,在国内待遇大概多少medical economics analyst的经验有用么?报offer, 该去哪个?P&C的童鞋们,能否进来帮我看下这个?多谢有人了解progressive这个公司么,求指点Job posting想找上海工作,上海的年会值得去吗Updated:Job postings东海岸考试的不知道有多少人会受影响刚电面完TW,求blessACTEX MLC Study Manual (2012 Edition) for sale帮人招志愿者背粪!有从精算转Marketing Research & Analytics的吗?salary surveys 2012考试快的烦恼?中国的寿险是传销?