Research map / Graph learning / Graph algorithms and clustering
Network Tight Community Detection
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes tight community detection (TCD), which uses network sub-sampling, averaged co-membership matrices, and DFS to separate tight nodes from scattered nodes before spectral clustering of tight communities.
Problem
Standard community detection forces every node into a cluster, but many real networks contain scattered nodes with no community affiliation, which biases the recovered communities.
Approach
Scattered nodes are randomly assigned to communities across repeated sub-sampled spectral clusterings, whereas tight nodes co-cluster consistently; TCD exploits this by thresholding an averaged co-membership matrix with DFS to find tight components and then runs spectral clustering on tight nodes only.
Key results
- On semi-real benchmarks with scattered nodes at one-fourth size, TCD reaches F-score 83.0% on Football versus 36.8% for the next best (RADAR).
- On the COVID-19 PPI network, TCD achieves the lowest Ncut of 0.087 and OEPR of 0.000, identifying 37 scattered nodes and 254 tight nodes in two communities.
- In synthetic GSBM experiments, TCD's F-score rises to nearly 1 and its misclustering rate decays to zero as network size grows, outperforming CBNs and other baselines.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TCD instead of Extraction | Community detection · Football | F-score (%): 83.0 ± 2.8 vs 39.7 ± 5.3 | Helped |
| Use TCD instead of RADAR | Community detection · Football | misclustering rate (%): 11.4 ± 2.6 vs 16.0 ± 3.1 | Helped |
| Use TCD instead of Extraction | Community detection · Polbooks | F-score (%): 68.7 ± 3.2 vs 54.1 ± 8.7 | Helped |
| Use TCD instead of RCD | Community detection · Polbooks | misclustering rate (%): 31.0 ± 3.2 vs 21.1 ± 3.3 | Hurt |
| Use TCD instead of ONE | Community detection · Polblogs | F-score (%): 54.7 ± 2.3 vs 19.6 ± 1.6 | Helped |
| Use TCD instead of RCD | Community detection · Polblogs | misclustering rate (%): 13.3 ± 2.6 vs 26.5 ± 1.2 | Helped |
| Use TCD instead of Extraction | Community detection · BlogCatalog | F-score (%): 43.6 ± 3.2 vs 16.7 ± 4.3 | Helped |
| Use TCD instead of HCD | Community detection · BlogCatalog | misclustering rate (%): 35.3 ± 3.6 vs 56.9 ± 6.2 | Helped |
| Use TCD instead of RADAR | Community detection · COVID-19 PPI network | Ncut: 0.087 vs 0.104 | Helped |
| Use TCD instead of PRN | Community detection · COVID-19 PPI network | OEPR: 0.000 vs 0.000 | No clear effect |
Surprising findings
- Simply adding scattered nodes as an extra cluster in spectral clustering does not fix contamination; tight nodes still co-cluster but scattered nodes stay randomly distributed.
- PRN reports OEPR of zero on the PPI network, which the authors attribute to scattered proteins being unenriched rather than to genuine discrimination.
Limitations
- Performance may degrade on extremely sparse graphs where connectivity scales as 1/n.
- Theory is restricted to the SBM; DCSBM results are empirical only.
- Requires a predefined number of communities K (estimated via cross-validation in experiments).
Experimental setup
Datasets: football polbooks polblogs BlogCatalog COVID-19 protein-protein interaction network (STRING) synthetic GSBM networks
Benchmarks: football polbooks polblogs BlogCatalog COVID-19 PPI network
Metrics: F-score misclustering rate Ncut OEPR
Baselines: Community Boundary Nodes (CBNs) RADAR ANOMALOUS ONE PageRank-Nibble Heat kernel (HK) Extraction ECoHeN HCD RCD
Builds on: tight clustering (Tseng & Wong 2005) network sub-sampling community detection (Mukherjee et al. 2021) general stochastic block model (Cai & Li 2015) sub-sampling for spectral clustering (Chen & Lei 2018)
Closest papers by meaning
- On clustering network-valued data (NeurIPS 2017 · similarity 0.85)
- Detecting Overlapping and Correlated Communities without Pure Nodes: Identifiability and Algorithm (ICML 2019 · similarity 0.84)
- Semantic Community Identification in Large Attribute Networks (AAAI 2016 · similarity 0.84)
- Community Detection in Attributed Graphs: An Embedding Approach (AAAI 2018 · similarity 0.84)
- Learning Persistent Community Structures in Dynamic Networks via Topological Data Analysis (AAAI 2024 · similarity 0.82)
- Community Detection Guarantees using Embeddings Learned by Node2Vec (NeurIPS 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.