Review 20471:

1. The high level idea of Sect. 4 is summarized in the 2nd paragraph of the section. We will add more examples and explanations.

2. In all the presented experiments, we fix the algorithm parameters (#edges to track, significance level). We run experiment on networks with different sizes (number of vertices, row 4-6 in Table 3), and different Erdos-Renyi parameters (density, not included due to page limit). We will add a link to our technical report for more details and more results.

3. Two previous work on change point detection also assume "a latent generative model governing the network dynamics": Bridges et al. 2015, Peel and Clauset 2014. (See the 3rd paragraph of our Sect 2).
Moreover, Jure Leskovec et al. (Graph Evolution: Densification and Shrinking Diameters) propose two generative models to explain the densification phenomenon in dynamic networks.



Review 26649:
1. MLE is a natural estimator when we have the likelihood function, but surprisingly it does not work very well. We analyze the drawbacks of MLE, and propose a simpler estimator which works better (Fig 3) and has theoretical guarantee (Proposition 1 & 2). We provide the negative result for the sake of completeness. Other researchers can avoid this path in the future.

2. We will add a link to our technical report for more details and more results.

3. We will correct the formatting problem.


Review 28833:
C1: N is the total number of nodes in a network (network size). It is the input, not a parameter. The number of dyads to track is k, a parameter in the algorithm. We sample and track dyads (in other word, node pairs) in stead of nodes. 
The number of dyads to track, k, is indeed related to network size, N. We don't expect 250 dyads suffice to capture the dynamic of a one-trillion-node network. However, in the experiments we conduct (Table 3, network size no greater than 50k nodes), to sample and track 250 dyads is sufficient and works pretty well. The reason to use fixed constant is to restrict time complexity and space complexity. We vary this parameter k from 100 to 1k, and find 250 is sufficient. We will add a link to our technical report in which sample size selection is discussed.

C2: In many cases (UN session, US Congress, etc.), there are natural window sizes (each session is yearly, each Congress is biennial). For the synthetic datasets with no ground truth window size, the size selection is a trade-off between bias and variance. Currently we choose window size empirically and heuristically, and we believe the temporal dependency \alpha (Eq 6) can provide information on window size determination, which leave as future work for now.
C2.2: The dyads are sampled uniformly at random. There is no trick in implementation. We can provide the code when necessary.

C3: We will add the pseudo-code.

C4: We will add this citation.

E1: This question is related to C1. 1.2G is a combinatorial number: a network with 50k nodes have nchoosek(50k,2) dyads, which equal to 1,249,975,000, and hence 1.2G. We will add a link to our technical report for more experiment results.

E2: The number of snapshots is 5k, which is mentioned in the 2nd paragraph of Sect 5.1; network size (number of nodes in a network) is reported in the 2nd column of Table 3; 250 dyads are sampled and tracked, which is again mentioned in the 2nd paragraph of Sect 5.1. Our technical report has more details.

E3: "Network size" means the number of nodes/vertices in a network; DNF means Did Not Finish; the temporal units will be re-formatted for better display.

E4: We have found that typo and it has been corrected.

