Community Detection on Evolving Graphs
Authors: Aris Anagnostopoulos, Jakub Łącki, Silvio Lattanzi, Stefano Leonardi, Mohammad Mahdian
NeurIPS 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, we perform simulations, which demonstrate that our main asymptotic results hold true also in practice. |
| Researcher Affiliation | Collaboration | Aris Anagnostopoulos Sapienza University of Rome aris@dis.uniroma1.it Jakub Ł acki Sapienza University of Rome j.lacki@mimuw.edu.pl Silvio Lattanzi Google silviol@google.com Stefano Leonardi Sapienza University of Rome leonardi@dis.uniroma1.it Mohammad Mahdian Google mahdian@google.com |
| Pseudocode | No | The paper describes algorithms verbally and proves properties about them, but does not include any structured pseudocode blocks or algorithms labeled as such. |
| Open Source Code | No | The paper does not provide any statements about the availability of open-source code for the described methodology, nor does it include links to a code repository. |
| Open Datasets | No | The paper states, "To compare these three probing strategies we construct a synthetic instance of our model as follows." No specific link, DOI, repository name, or formal citation is provided for this synthetic dataset, nor is it identified as a well-known public dataset. |
| Dataset Splits | No | The paper does not explicitly mention training, validation, or test dataset splits. It describes generating a synthetic graph and running evolution steps, but not how the data itself is partitioned for evaluation. |
| Hardware Specification | No | The paper mentions 'probing a large graphs stored across many machines' as a motivation, but does not provide specific details (e.g., GPU/CPU models, memory, or cloud instance types) about the hardware used to run the experiments or simulations. |
| Software Dependencies | No | The paper does not mention any specific software dependencies or their version numbers that would be necessary to replicate the experiments (e.g., Python, PyTorch, TensorFlow, or specific solvers with versions). |
| Experiment Setup | Yes | To compare these three probing strategies we construct a synthetic instance of our model as follows. We build a graph with 10000 nodes with communities of expected size between 50 and 250. The number of communities with expected size ℓis proportional to ℓ c for c = 0, 1, 2, 3. So the distribution of communities size follows a power-law distribution with parameter c {0, 1, 2, 3}. To generate random communities in our experiment we use p = 0.5 and q = 0.001. ... In the first 10k evolution steps, we construct the data structure described in Lemma 3 by exploring the clusters of a single random node per step. Finally, we run the three different strategies for 25k additional steps in which we update the clusterings by exploring a single node in each step and by retrieving its cluster. ... At any point during the execution of the algorithm we compute the cluster of a node by exploring at most 30 of its neighbors. |