Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Improved spectral community detection in large heterogeneous networks
Authors: Hafiz TIOMOKO ALI, Romain COUILLET
JMLR 2017 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Numerical simulations show that the proposed method outperforms state-of-the-art spectral approaches both on synthetic graphs and on real world networks. Numerical simulations |
| Researcher Affiliation | Academia | Haļ¬z TIOMOKO ALI EMAIL Centrale Sup elec Universit e Paris Saclay Laboratoire des Signaux et Syst emes 3 rue Joliot Curie, 91192 Gif-Sur-Yvette Romain COUILLET EMAIL Centrale Sup elec Universit e Paris Saclay Laboratoire des Signaux et Syst emes 3 rue Joliot Curie, 91192 Gif-Sur-Yvette |
| Pseudocode | Yes | Algorithm 1: Spectral algorithm 1: Compute the, say, āeigenvectors u1, . . . , uā Rn corresponding to the dominant (largest or smallest) eigenvalues of one of the matrix representations of the network (adjacency, modularity, Laplacian) of size n n. 2: Stack the vectors ui s columnwise in a matrix W = [ui, . . . , uā] Rn ā. 3: Let r1, . . . , rn Rābe the rows of W. Cluster ri Rā, 1 i n in one of K groups using any low-dimensional classiļ¬cation algorithm (e.g., k-means (Hartigan and Wong, 1979) or Expectation Maximization (EM) (Ng et al., 2012)). The label assigned to ri then corresponds to the label of node i. ... Algorithm 2: Improved spectral algorithm 1: Evaluate Ī± = ĖĪ±opt = argminĪ± A limx ĖSĪ± ĖgĪ±(x) as per Proposition 12. 2: Retrieve the āeigenvectors corresponding to the ālargest eigenvalues of LĪ± = (2m)Ī± 1 n D Ī± h A dd T 2m i D Ī±. Denote uĪ± 1 , . . . , uĪ± āthose eigenvectors. 3: Letting vĪ± i = DĪ± 1uĪ± i and vĪ± i = vĪ± i vĪ± i , stack the vectors vĪ± i s columnwise in a matrix W = [ vĪ± 1 , . . . , vĪ± ā] Rn ā. 4: Let r1, . . . , rn Rābe the rows of W. Cluster ri Rā, 1 i n in one of the K groups using any low-dimensional classiļ¬cation algorithm (e.g., k-means or EM). The label assigned to ri then corresponds to the label of node i. |
| Open Source Code | Yes | A Python implementation of the algorithm is available in (Tiomoko Ali and Couillet, 2017). ... Haļ¬z Tiomoko Ali and Romain Couillet. Improved spectral community detection algorithm in large dense graphs. https://github.com/hafiz Tiomoko/improved_spectral_ community_detection, March 2017. |
| Open Datasets | Yes | As suggested in the practical case of the popular Political Blogs graph (Adamic and Glance, 2005) (see Figure 4), a more realistic model, the Degree-Corrected SBM (DCSBM), was proposed in (Coja-Oghlan and Lanka, 2009; Karrer and Newman, 2011) to account for degree heterogeneity inside communities. |
| Dataset Splits | No | The paper uses synthetic graphs generated based on various parameters (e.g., 'n = 3000 nodes', 'K = 3 classes', 'Āµ = 3/4Ī“q(1) + 1/4Ī“q(2)', 'M = I3', 'ci = 1/3') and the Political blogs graph. However, it does not explicitly describe any training/test/validation dataset splits or methodologies for data partitioning to reproduce experiments. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware (e.g., CPU, GPU models, memory) used to run the simulations or experiments. |
| Software Dependencies | No | A Python implementation of the algorithm is available in (Tiomoko Ali and Couillet, 2017). The paper mentions Python but does not provide specific version numbers for Python or any other libraries, solvers, or software components used in the implementation. |
| Experiment Setup | Yes | A deeper study of the regularized eigenvectors allows us to improve the initial setting of the EM algorithm (in the step 3 of the spectral algorithm described above) in comparison with a random setting. ... To show the eļ¬ect of our setting of initial parameters of EM based on the ļ¬ndings Ī½ and Ī£ , Figure 8 compares the empirical performances of our new spectral algorithm based on the regularized eigenvector of L0.5 for diļ¬erent initial settings of the EM parameters i) random setting (Random EM) ii) our theoretical setting (by assuming that the class proportions are known) and iii) the ground truth setting (oracle EM where we set the initial points to the empirically evaluated means and covariances of each cluster based on ground truth). |