Dear list,
I'm trying to fit a nested blockmodel to a (bipartite) network with ~10^6 edges. The algorithm minimize_nested_blockmodel_dl() doesn't terminate; it keeps on adding layers indefinitely until it runs out of memory / hits walltime, see below. What could be going on?
Many thanks in advance,
Peter
level 2 : replaced (94, 1) -> (94, 16) , dS: -15452.0134871 3
l=3 B: 8 <- 16 shrinking 16 -> 11
l=3 B: 8 <- 16 B=11 niter: 1 count: 1 breaks: 1 min_S: 1002.5742 max_S: 1002.5742 S: 1002.5742 ΔS: 0.00000 moves: 0
l=3 B: 8 <- 16 shrinking 11 -> 8
l=3 B: 8 <- 16 B=8 niter: 1 count: 1 breaks: 1 min_S: 838.70438 max_S: 838.70438 S: 838.70438 ΔS: 0.00000 moves: 0
l=3 Current bracket: (2, 8, 16) (691.21840695494018, 838.70438205706921, 1340.6798309766764)
l=3 B: 5 <- 8 shrinking 8 -> 5
l=3 B: 5 <- 8 B=5 niter: 1 count: 0 breaks: 0 min_S: 752.39171 max_S: 753.34067 S: 752.39171 ΔS: -0.948956 moves: 2
l=3 B: 5 <- 8 B=5 niter: 2 count: 0 breaks: 0 min_S: 751.86303 max_S: 753.34067 S: 751.86303 ΔS: -0.528683 moves: 1
l=3 B: 5 <- 8 B=5 niter: 3 count: 1 breaks: 1 min_S: 751.86303 max_S: 753.34067 S: 751.86303 ΔS: 0.00000 moves: 0
l=3 Current bracket: (2, 5, 8) (691.21840695494018, 751.86302859686145, 838.70438205706921)
l=3 B: 3 <- 5 shrinking 5 -> 3
l=3 B: 3 <- 5 B=3 niter: 1 count: 0 breaks: 0 min_S: 720.12311 max_S: 720.62000 S: 720.12311 ΔS: -0.496886 moves: 1
l=3 B: 3 <- 5 B=3 niter: 2 count: 1 breaks: 1 min_S: 720.12311 max_S: 720.62000 S: 720.12311 ΔS: 0.00000 moves: 0
l=3 Current bracket: (2, 3, 5) (691.21840695494018, 720.123114036723, 751.86302859686145)
l=3 Current bracket: (2, 2, 3) (691.21840695494018, 691.21840695494018, 720.123114036723)
l=3 Bisect at B = 2 with S = 691.2184069549402
l=3 Best result: B = 2, S = 691.2184069549402
level 3 : replaced (16, 1) -> (16, 2) , dS: -628.252218219 4
l=4 Current bracket: (2, 2, 2) (26.653307346627116, 26.653307346627116, 26.653307346627116)
l=4 Current bracket: (2, 2, 2) (26.653307346627116, 26.653307346627116, 26.653307346627116)
l=4 Bisect at B = 2 with S = 26.65330734662712
l=4 Best result: B = 2, S = 26.65330734662712
level 4 : replaced (2, 1) -> (2, 2) , dS: -1.86264514923e-09 5
l=5 Current bracket: (2, 2, 2) (26.653307346627116, 26.653307346627116, 26.653307346627116)
l=5 Current bracket: (2, 2, 2) (26.653307346627116, 26.653307346627116, 26.653307346627116)
l=5 Bisect at B = 2 with S = 26.65330734662712
l=5 Best result: B = 2, S = 26.65330734662712
level 5 : replaced (2, 1) -> (2, 2) , dS: -1.86264514923e-09 6
l=6 Current bracket: (2, 2, 2) (26.653307346627116, 26.653307346627116, 26.653307346627116)
l=6 Current bracket: (2, 2, 2) (26.653307346627116, 26.653307346627116, 26.653307346627116)
l=6 Bisect at B = 2 with S = 26.65330734662712
l=6 Best result: B = 2, S = 26.65330734662712
level 6 : replaced (2, 1) -> (2, 2) , dS: -1.86264514923e-09 7
l=7 Current bracket: (2, 2, 2) (26.653307346627116, 26.653307346627116, 26.653307346627116)
l=7 Current bracket: (2, 2, 2) (26.653307346627116, 26.653307346627116, 26.653307346627116)
l=7 Bisect at B = 2 with S = 26.65330734662712
l=7 Best result: B = 2, S = 26.65330734662712
level 7 : replaced (2, 1) -> (2, 2) , dS: -1.86264514923e-09 8
l=8 Current bracket: (2, 2, 2) (26.653307346627116, 26.653307346627116, 26.653307346627116)
l=8 Current bracket: (2, 2, 2) (26.653307346627116, 26.653307346627116, 26.653307346627116)
l=8 Bisect at B = 2 with S = 26.65330734662712 and l is increasing into the thousands if the left alone.
On 18.01.2017 01:36, Peter Straka wrote:
Dear list,
I'm trying to fit a nested blockmodel to a (bipartite) network with ~10^6 edges. The algorithm minimize_nested_blockmodel_dl() doesn't terminate; it keeps on adding layers indefinitely until it runs out of memory / hits walltime, see below. What could be going on?
This is a silly bug due to finite machine precision. It has already been fixed in git, and will be available in the next release.
Best, Tiago
Great, thanks Tiago
On Wed, 18 Jan 2017 at 20:06 Tiago de Paula Peixoto tiago@skewed.de wrote:
On 18.01.2017 01:36, Peter Straka wrote:
Dear list,
I'm trying to fit a nested blockmodel to a (bipartite) network with ~10^6 edges. The algorithm minimize_nested_blockmodel_dl() doesn't terminate;
it
keeps on adding layers indefinitely until it runs out of memory / hits walltime, see below. What could be going on?
This is a silly bug due to finite machine precision. It has already been fixed in git, and will be available in the next release.
Best, Tiago
-- Tiago de Paula Peixoto tiago@skewed.de _______________________________________________ graph-tool mailing list graph-tool@skewed.de https://lists.skewed.de/mailman/listinfo/graph-tool
Just thought I mention that I've reproduced this bug again on my laptop. Below some output, it keeps repeating at infinitum (got as far as level l=14021)... This is for just the minimize_nested_blockmodel_dl(), no layers, no weights, bipartite structure. Hope this helps, Peter
l=1 Current bracket: (2, 2, 2) (31.317096602087641, 31.317096602087641, 31.317096602087641)
l=1 Current bracket: (2, 2, 2) (31.317096602087641, 31.317096602087641, 31.317096602087641)
l=1 Bisect at B = 2 with S = 31.31709660208764
l=1 Best result: B = 2, S = 31.31709660208764
level 1 : rejected replacement (2, 1) -> (2, 2) , dS: nan
l=1 Current bracket: (2, 2, 2) (31.317096602087641, 31.317096602087641, 31.317096602087641)
l=1 Current bracket: (2, 2, 2) (31.317096602087641, 31.317096602087641, 31.317096602087641)
l=1 Bisect at B = 2 with S = 31.31709660208764
l=1 Best result: B = 2, S = 31.31709660208764
level 2 : inserted 2 , dS: nan
l=3 Current bracket: (2, 2, 2) (31.317096602087641, 31.317096602087641, 31.317096602087641)
l=3 Current bracket: (2, 2, 2) (31.317096602087641, 31.317096602087641, 31.317096602087641)
l=3 Bisect at B = 2 with S = 31.31709660208764
l=3 Best result: B = 2, S = 31.31709660208764
level 3 : rejected replacement (2, 1) -> (2, 2) , dS: nan
l=3 Current bracket: (2, 2, 2) (31.317096602087641, 31.317096602087641, 31.317096602087641)
l=3 Current bracket: (2, 2, 2) (31.317096602087641, 31.317096602087641, 31.317096602087641)
l=3 Bisect at B = 2 with S = 31.31709660208764
l=3 Best result: B = 2, S = 31.31709660208764
level 4 : inserted 2 , dS: nan
l=5 Current bracket: (2, 2, 2) (31.317096602087641, 31.317096602087641, 31.317096602087641)
l=5 Current bracket: (2, 2, 2) (31.317096602087641, 31.317096602087641, 31.317096602087641)
l=5 Bisect at B = 2 with S = 31.31709660208764
l=5 Best result: B = 2, S = 31.31709660208764
On Thu, 19 Jan 2017 at 08:52 Peter Straka p.straka@unsw.edu.au wrote:
Great, thanks Tiago
On Wed, 18 Jan 2017 at 20:06 Tiago de Paula Peixoto tiago@skewed.de wrote:
On 18.01.2017 01:36, Peter Straka wrote:
Dear list,
I'm trying to fit a nested blockmodel to a (bipartite) network with ~10^6 edges. The algorithm minimize_nested_blockmodel_dl() doesn't terminate;
it
keeps on adding layers indefinitely until it runs out of memory / hits walltime, see below. What could be going on?
This is a silly bug due to finite machine precision. It has already been fixed in git, and will be available in the next release.
Best, Tiago
-- Tiago de Paula Peixoto tiago@skewed.de _______________________________________________ graph-tool mailing list graph-tool@skewed.de https://lists.skewed.de/mailman/listinfo/graph-tool
-- Dr Peter Straka Research Fellow (DECRA) School of PEMS | UNSW Canberra Google Scholar https://scholar.google.com.au/citations?user=BV5PkWUAAAAJ&hl=en&authuser=1 E: p.straka@unsw.edu.au T: +61 (2) 938*5 7024 *| +1 313 757 0137 <(313)%20757-0137>
Hi,
This is not very useful without the actual script and network that causes it, otherwise I cannot try to reproduce it.
Are you using the newest version? Does it also happen with the current git version?
Best, Tiago
On 27.03.2017 23:25, Peter Straka wrote:
Just thought I mention that I've reproduced this bug again on my laptop. Below some output, it keeps repeating at infinitum (got as far as level l=14021)... This is for just the minimize_nested_blockmodel_dl(), no layers, no weights, bipartite structure. Hope this helps, Peter
l=1 Current bracket: (2, 2, 2) (31.317096602087641, 31.317096602087641,31.317096602087641)
l=1 Current bracket: (2, 2, 2) (31.317096602087641, 31.317096602087641,31.317096602087641)
l=1 Bisect at B = 2 with S = 31.31709660208764 l=1 Best result: B = 2, S = 31.31709660208764level 1 : rejected replacement (2, 1) -> (2, 2) , dS: nan
l=1 Current bracket: (2, 2, 2) (31.317096602087641, 31.317096602087641,31.317096602087641)
l=1 Current bracket: (2, 2, 2) (31.317096602087641, 31.317096602087641,31.317096602087641)
l=1 Bisect at B = 2 with S = 31.31709660208764 l=1 Best result: B = 2, S = 31.31709660208764level 2 : inserted 2 , dS: nan
l=3 Current bracket: (2, 2, 2) (31.317096602087641, 31.317096602087641,31.317096602087641)
l=3 Current bracket: (2, 2, 2) (31.317096602087641, 31.317096602087641,31.317096602087641)
l=3 Bisect at B = 2 with S = 31.31709660208764 l=3 Best result: B = 2, S = 31.31709660208764level 3 : rejected replacement (2, 1) -> (2, 2) , dS: nan
l=3 Current bracket: (2, 2, 2) (31.317096602087641, 31.317096602087641,31.317096602087641)
l=3 Current bracket: (2, 2, 2) (31.317096602087641, 31.317096602087641,31.317096602087641)
l=3 Bisect at B = 2 with S = 31.31709660208764 l=3 Best result: B = 2, S = 31.31709660208764level 4 : inserted 2 , dS: nan
l=5 Current bracket: (2, 2, 2) (31.317096602087641, 31.317096602087641,31.317096602087641)
l=5 Current bracket: (2, 2, 2) (31.317096602087641, 31.317096602087641,31.317096602087641)
l=5 Bisect at B = 2 with S = 31.31709660208764 l=5 Best result: B = 2, S = 31.31709660208764On Thu, 19 Jan 2017 at 08:52 Peter Straka <p.straka@unsw.edu.au mailto:p.straka@unsw.edu.au> wrote:
Great, thanks Tiago On Wed, 18 Jan 2017 at 20:06 Tiago de Paula Peixoto <tiago@skewed.de <mailto:tiago@skewed.de>> wrote: On 18.01.2017 01:36, Peter Straka wrote: > Dear list, > > I'm trying to fit a nested blockmodel to a (bipartite) network with ~10^6 > edges. The algorithm minimize_nested_blockmodel_dl() doesn't terminate; it > keeps on adding layers indefinitely until it runs out of memory / hits > walltime, see below. What could be going on? This is a silly bug due to finite machine precision. It has already been fixed in git, and will be available in the next release. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de <mailto:tiago@skewed.de>> _______________________________________________ graph-tool mailing list graph-tool@skewed.de <mailto:graph-tool@skewed.de> https://lists.skewed.de/mailman/listinfo/graph-tool -- Dr Peter Straka Research Fellow (DECRA) School of PEMS | UNSW Canberra Google Scholar <https://scholar.google.com.au/citations?user=BV5PkWUAAAAJ&hl=en&authuser=1> E: p.straka@unsw.edu.au <mailto:p.straka@unsw.edu.au> T: +61 (2) 938*5 7024 *| +1 313 757 0137 <tel:(313)%20757-0137>* *
graph-tool mailing list graph-tool@skewed.de https://lists.skewed.de/mailman/listinfo/graph-tool
Hi Tiago, yeah, sorry, I don't have enough to file a real bug report. This is on 2.22 (there's always a bit of lag until our high performance computing cluster team can update graph-tool). But I just thought I mention this as a warning that this machine precision bug might still be around. Peter
On 28 March 2017 at 09:41, Tiago de Paula Peixoto tiago@skewed.de wrote:
Hi,
This is not very useful without the actual script and network that causes it, otherwise I cannot try to reproduce it.
Are you using the newest version? Does it also happen with the current git version?
Best, Tiago
On 27.03.2017 23:25, Peter Straka wrote:
Just thought I mention that I've reproduced this bug again on my laptop. Below some output, it keeps repeating at infinitum (got as far as level l=14021)... This is for just the minimize_nested_blockmodel_dl(), no layers, no
weights,
bipartite structure. Hope this helps, Peter
l=1 Current bracket: (2, 2, 2) (31.317096602087641,31.317096602087641,
31.317096602087641)
l=1 Current bracket: (2, 2, 2) (31.317096602087641,31.317096602087641,
31.317096602087641)
l=1 Bisect at B = 2 with S = 31.31709660208764 l=1 Best result: B = 2, S = 31.31709660208764level 1 : rejected replacement (2, 1) -> (2, 2) , dS: nan
l=1 Current bracket: (2, 2, 2) (31.317096602087641,31.317096602087641,
31.317096602087641)
l=1 Current bracket: (2, 2, 2) (31.317096602087641,31.317096602087641,
31.317096602087641)
l=1 Bisect at B = 2 with S = 31.31709660208764 l=1 Best result: B = 2, S = 31.31709660208764level 2 : inserted 2 , dS: nan
l=3 Current bracket: (2, 2, 2) (31.317096602087641,31.317096602087641,
31.317096602087641)
l=3 Current bracket: (2, 2, 2) (31.317096602087641,31.317096602087641,
31.317096602087641)
l=3 Bisect at B = 2 with S = 31.31709660208764 l=3 Best result: B = 2, S = 31.31709660208764level 3 : rejected replacement (2, 1) -> (2, 2) , dS: nan
l=3 Current bracket: (2, 2, 2) (31.317096602087641,31.317096602087641,
31.317096602087641)
l=3 Current bracket: (2, 2, 2) (31.317096602087641,31.317096602087641,
31.317096602087641)
l=3 Bisect at B = 2 with S = 31.31709660208764 l=3 Best result: B = 2, S = 31.31709660208764level 4 : inserted 2 , dS: nan
l=5 Current bracket: (2, 2, 2) (31.317096602087641,31.317096602087641,
31.317096602087641)
l=5 Current bracket: (2, 2, 2) (31.317096602087641,31.317096602087641,
31.317096602087641)
l=5 Bisect at B = 2 with S = 31.31709660208764 l=5 Best result: B = 2, S = 31.31709660208764On Thu, 19 Jan 2017 at 08:52 Peter Straka <p.straka@unsw.edu.au mailto:p.straka@unsw.edu.au> wrote:
Great, thanks Tiago On Wed, 18 Jan 2017 at 20:06 Tiago de Paula Peixoto <tiago@skewed.de <mailto:tiago@skewed.de>> wrote: On 18.01.2017 01:36, Peter Straka wrote: > Dear list, > > I'm trying to fit a nested blockmodel to a (bipartite) network with ~10^6 > edges. The algorithm minimize_nested_blockmodel_dl() doesn't terminate; it > keeps on adding layers indefinitely until it runs out ofmemory / hits
> walltime, see below. What could be going on? This is a silly bug due to finite machine precision. It hasalready been
fixed in git, and will be available in the next release. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de <mailto:tiago@skewed.de_______________________________________________ graph-tool mailing list graph-tool@skewed.de <mailto:graph-tool@skewed.de> https://lists.skewed.de/mailman/listinfo/graph-tool -- Dr Peter Straka Research Fellow (DECRA) School of PEMS | UNSW Canberra Google Scholar <https://scholar.google.com.au/citations?user=BV5PkWUAAAAJ&hl=en&authuser=1>
E: p.straka@unsw.edu.au <mailto:p.straka@unsw.edu.au> T: +61 (2) 938*5 7024 *| +1 313 757 0137 <tel:(313)%20757-0137>* *
graph-tool mailing list graph-tool@skewed.de https://lists.skewed.de/mailman/listinfo/graph-tool
-- Tiago de Paula Peixoto tiago@skewed.de
graph-tool mailing list graph-tool@skewed.de https://lists.skewed.de/mailman/listinfo/graph-tool
On 28.03.2017 00:00, Peter Straka wrote:
Hi Tiago, yeah, sorry, I don't have enough to file a real bug report. This is on 2.22 (there's always a bit of lag until our high performance computing cluster team can update graph-tool). But I just thought I mention this as a warning that this machine precision bug might still be around.
This problem seems different from the previous one in this thread, since the entropy difference is yielding NAN.
I haven't observed this problem myself yet. But if it is there, providing an actual reproducible case would be helpful in fixing it.
Best, Tiago
Maybe the entropy difference is NAN because it's infinity - infinity? As in, too big for machine representation. My dataset has 1,961,256 vertices and 4,465,869 edges...
On 28 March 2017 at 10:06, Tiago de Paula Peixoto tiago@skewed.de wrote:
On 28.03.2017 00:00, Peter Straka wrote:
Hi Tiago, yeah, sorry, I don't have enough to file a real bug report. This is on
2.22
(there's always a bit of lag until our high performance computing cluster team can update graph-tool). But I just thought I mention this as a
warning
that this machine precision bug might still be around.
This problem seems different from the previous one in this thread, since the entropy difference is yielding NAN.
I haven't observed this problem myself yet. But if it is there, providing an actual reproducible case would be helpful in fixing it.
Best, Tiago
-- Tiago de Paula Peixoto tiago@skewed.de
graph-tool mailing list graph-tool@skewed.de https://lists.skewed.de/mailman/listinfo/graph-tool
On 28.03.2017 00:43, Peter Straka wrote:
Maybe the entropy difference is NAN because it's infinity - infinity? As in, too big for machine representation. My dataset has 1,961,256 vertices and 4,465,869 edges...
This is not quite big enough to exhaust machine precision. Any system would run out of memory much sooner.
I have used networks with upwards of 30 million edges, without any problems.
It must be something else.
-
Peter Straka -
Tiago de Paula Peixoto