0
# Community Detection
1

2
Advanced community detection algorithms for identifying groups and clusters within networks. igraph provides over 10 different algorithms for finding communities, from fast heuristics to sophisticated optimization methods.
3

4
## Capabilities
5

6
### Modularity-Based Methods
7

8
Community detection algorithms based on optimizing modularity, a measure of community structure quality.
9

10
```python { .api }
11
class Graph:
12
    def community_leiden(self, weights=None, resolution=1.0, beta=0.01, initial_membership=None, n_iterations=2):
13
        """
14
        Leiden algorithm for community detection (improved Louvain).
15
        
16
        Parameters:
17
        - weights: str/list, edge weights or attribute name
18
        - resolution: float, resolution parameter (higher = smaller communities)
19
        - beta: float, randomness in moving vertices
20
        - initial_membership: list, starting community assignment
21
        - n_iterations: int, number of iterations
22
        
23
        Returns:
24
        VertexClustering, community assignment
25
        """
26

27
    def community_multilevel(self, weights=None, resolution=1.0):
28
        """
29
        Louvain method for community detection (multilevel optimization).
30
        
31
        Parameters:
32
        - weights: edge weights
33
        - resolution: resolution parameter
34
        
35
        Returns:
36
        VertexClustering, community assignment
37
        """
38

39
    def community_fastgreedy(self, weights=None):
40
        """
41
        Fast greedy modularity optimization.
42
        
43
        Parameters:
44
        - weights: edge weights
45
        
46
        Returns:
47
        VertexDendrogram, hierarchical community structure
48
        """
49
```
50

51
**Usage Examples:**
52

53
```python
54
import igraph as ig
55

56
# Create sample network
57
g = ig.Graph.Famous("Zachary")  # Karate club network
58

59
# Leiden algorithm (recommended)
60
leiden_comm = g.community_leiden(resolution=1.0)
61
print(f"Leiden communities: {len(leiden_comm)}")
62
print(f"Modularity: {leiden_comm.modularity:.3f}")
63

64
# Louvain method  
65
louvain_comm = g.community_multilevel()
66
print(f"Louvain communities: {len(louvain_comm)}")
67

68
# Fast greedy (returns dendrogram)
69
fg_dendro = g.community_fastgreedy()
70
fg_comm = fg_dendro.as_clustering()  # Convert to flat clustering
71
print(f"Fast greedy communities: {len(fg_comm)}")
72

73
# With edge weights
74
g.es["weight"] = [1 + i*0.1 for i in range(g.ecount())]
75
weighted_comm = g.community_leiden(weights="weight", resolution=0.8)
76

77
# Compare different resolutions
78
for res in [0.5, 1.0, 2.0]:
79
    comm = g.community_leiden(resolution=res)
80
    print(f"Resolution {res}: {len(comm)} communities, modularity {comm.modularity:.3f}")
81
```
82

83
### Information-Theoretic Methods
84

85
Community detection based on information theory and compression principles.
86

87
```python { .api }
88
class Graph:
89
    def community_infomap(self, edge_weights=None, vertex_weights=None, trials=10):
90
        """
91
        Infomap algorithm based on information theory.
92
        
93
        Parameters:
94
        - edge_weights: str/list, edge weights
95
        - vertex_weights: str/list, vertex weights  
96
        - trials: int, number of attempts
97
        
98
        Returns:
99
        VertexClustering, community assignment
100
        """
101

102
    def community_label_propagation(self, weights=None, initial=None, fixed=None):
103
        """
104
        Label propagation algorithm.
105
        
106
        Parameters:
107
        - weights: edge weights
108
        - initial: list, initial labels
109
        - fixed: list of bool, which vertices have fixed labels
110
        
111
        Returns:
112
        VertexClustering, community assignment
113
        """
114
```
115

116
**Usage Examples:**
117

118
```python
119
# Infomap algorithm
120
infomap_comm = g.community_infomap(trials=100)
121
print(f"Infomap communities: {len(infomap_comm)}")
122

123
# Label propagation
124
lp_comm = g.community_label_propagation()
125
print(f"Label propagation communities: {len(lp_comm)}")
126

127
# With vertex weights (e.g., based on degree)
128
g.vs["weight"] = g.degree()
129
weighted_infomap = g.community_infomap(vertex_weights="weight")
130
```
131

132
### Hierarchical Methods
133

134
Algorithms that produce hierarchical community structures (dendrograms).
135

136
```python { .api }
137
class Graph:
138
    def community_walktrap(self, weights=None, steps=4):
139
        """
140
        Walktrap algorithm based on random walks.
141
        
142
        Parameters:
143
        - weights: edge weights
144
        - steps: int, length of random walks
145
        
146
        Returns:
147
        VertexDendrogram, hierarchical community structure
148
        """
149

150
    def community_edge_betweenness(self, weights=None, directed=True):
151
        """
152
        Girvan-Newman algorithm using edge betweenness.
153
        
154
        Parameters:
155
        - weights: edge weights
156
        - directed: bool, respect edge directions
157
        
158
        Returns:
159
        VertexDendrogram, hierarchical structure
160
        """
161

162
    def community_leading_eigenvector(self, clusters=None, weights=None, arpack_options=None):
163
        """
164
        Newman's leading eigenvector method.
165
        
166
        Parameters:
167
        - clusters: int, desired number of clusters (None for automatic)
168
        - weights: edge weights
169
        - arpack_options: ARPACKOptions, eigensolver options
170
        
171
        Returns:
172
        VertexClustering, community assignment
173
        """
174
```
175

176
**Usage Examples:**
177

178
```python
179
# Walktrap algorithm
180
wt_dendro = g.community_walktrap(steps=4)
181
wt_comm = wt_dendro.as_clustering()
182
print(f"Walktrap communities: {len(wt_comm)}")
183

184
# Edge betweenness (Girvan-Newman)
185
eb_dendro = g.community_edge_betweenness()
186
eb_comm = eb_dendro.as_clustering()
187
print(f"Edge betweenness communities: {len(eb_comm)}")
188

189
# Leading eigenvector
190
le_comm = g.community_leading_eigenvector(clusters=3)
191
print(f"Leading eigenvector communities: {len(le_comm)}")
192

193
# Working with dendrograms
194
print(f"Optimal cut for walktrap: {wt_dendro.optimal_count}")
195
for n_clusters in [2, 3, 4, 5]:
196
    comm_n = wt_dendro.as_clustering(n_clusters)
197
    print(f"{n_clusters} clusters: modularity {comm_n.modularity:.3f}")
198
```
199

200
### Specialized Methods
201

202
Algorithms for specific types of networks or community structures.
203

204
```python { .api }
205
class Graph:
206
    def community_spinglass(self, weights=None, spins=25, parupdate=False, start_temp=1, stop_temp=0.01, cool_fact=0.99, update_rule="config", gamma=1.0):
207
        """
208
        Spinglass algorithm for community detection.
209
        
210
        Parameters:
211
        - weights: edge weights
212
        - spins: int, number of spins (max communities)
213
        - parupdate: bool, parallel update
214
        - start_temp: float, starting temperature
215
        - stop_temp: float, stopping temperature
216
        - cool_fact: float, cooling factor
217
        - update_rule: str, update rule ("config", "random", "simple")
218
        - gamma: float, resolution parameter
219
        
220
        Returns:
221
        VertexClustering, community assignment
222
        """
223

224
    def community_optimal_modularity(self):
225
        """
226
        Exact modularity optimization (small graphs only).
227
        
228
        Returns:
229
        VertexClustering, optimal community assignment
230
        """
231
232
```
233

234
**Usage Examples:**
235

236
```python
237
# Spinglass (works best on smaller graphs)
238
if g.vcount() <= 100:  # Limit to smaller graphs
239
    sg_comm = g.community_spinglass(spins=10)
240
    print(f"Spinglass communities: {len(sg_comm)}")
241

242
# Optimal modularity (very small graphs only)
243
small_g = ig.Graph.Ring(12)
244
optimal_comm = small_g.community_optimal_modularity()
245
print(f"Optimal modularity: {optimal_comm.modularity:.3f}")
246
247
```
248

249
### Community Comparison
250

251
Methods for comparing different community structures and measuring their similarity.
252

253
```python { .api }
254
def compare_communities(comm1, comm2, method="vi", remove_none=False):
255
    """
256
    Compare two community structures.
257
    
258
    Parameters:
259
    - comm1, comm2: Clustering objects to compare
260
    - method: str, comparison method
261
      ("vi" - variation of information, "nmi" - normalized mutual information,
262
       "split-join", "rand", "adjusted_rand")
263
    - remove_none: bool, ignore vertices not in any community
264
    
265
    Returns:
266
    float, similarity/distance measure
267
    """
268

269
def split_join_distance(comm1, comm2):
270
    """
271
    Calculate split-join distance between clusterings.
272
    
273
    Parameters:
274
    - comm1, comm2: Clustering objects
275
    
276
    Returns:
277
    int, split-join distance
278
    """
279
```
280

281
**Usage Examples:**
282

283
```python
284
from igraph import compare_communities, split_join_distance
285

286
# Compare different algorithms
287
leiden_comm = g.community_leiden()
288
louvain_comm = g.community_multilevel()
289
infomap_comm = g.community_infomap()
290

291
# Variation of information (lower = more similar)
292
vi_leiden_louvain = compare_communities(leiden_comm, louvain_comm, method="vi")
293
vi_leiden_infomap = compare_communities(leiden_comm, infomap_comm, method="vi")
294

295
# Normalized mutual information (higher = more similar)
296
nmi_leiden_louvain = compare_communities(leiden_comm, louvain_comm, method="nmi")
297
nmi_leiden_infomap = compare_communities(leiden_comm, infomap_comm, method="nmi")
298

299
print(f"Leiden vs Louvain - VI: {vi_leiden_louvain:.3f}, NMI: {nmi_leiden_louvain:.3f}")
300
print(f"Leiden vs Infomap - VI: {vi_leiden_infomap:.3f}, NMI: {nmi_leiden_infomap:.3f}")
301

302
# Split-join distance
303
sj_dist = split_join_distance(leiden_comm, louvain_comm)
304
print(f"Split-join distance: {sj_dist}")
305

306
# Compare with ground truth (if available)
307
# g.vs["true_community"] = [...] # True community labels
308
# true_clustering = ig.VertexClustering.FromAttribute(g, "true_community")
309
# accuracy = compare_communities(leiden_comm, true_clustering, method="nmi")
310
```
311

312
### Community Evaluation
313

314
Methods for evaluating and validating community structures.
315

316
```python { .api }
317
class VertexClustering:
318
    def modularity(self):
319
        """
320
        Calculate modularity of the clustering.
321
        
322
        Returns:
323
        float, modularity value (-0.5 to 1.0)
324
        """
325

326
    def crossing(self):
327
        """
328
        Get edges that cross between communities.
329
        
330
        Returns:
331
        list of bool, True for crossing edges
332
        """
333

334
    def giant(self):
335
        """
336
        Get largest community.
337
        
338
        Returns:
339
        list of int, vertices in largest community
340
        """
341

342
    def size(self, idx):
343
        """
344
        Get size of specific community.
345
        
346
        Parameters:
347
        - idx: int, community index
348
        
349
        Returns:
350
        int, number of vertices in community
351
        """
352

353
    def sizes(self):
354
        """
355
        Get sizes of all communities.
356
        
357
        Returns:
358
        list of int, community sizes
359
        """
360
```
361

362
**Usage Examples:**
363

364
```python
365
# Evaluate community structure
366
comm = g.community_leiden()
367

368
# Basic statistics
369
print(f"Number of communities: {len(comm)}")
370
print(f"Modularity: {comm.modularity:.3f}")
371
print(f"Community sizes: {comm.sizes()}")
372
print(f"Largest community size: {comm.size(comm.giant())}")
373

374
# Edge analysis
375
crossing_edges = comm.crossing()
376
n_crossing = sum(crossing_edges)
377
print(f"Edges crossing communities: {n_crossing}/{g.ecount()}")
378

379
# Community size distribution
380
sizes = comm.sizes()
381
print(f"Size distribution - Mean: {sum(sizes)/len(sizes):.1f}, "
382
      f"Min: {min(sizes)}, Max: {max(sizes)}")
383

384
# Identify vertices in specific community
385
comm_0_vertices = [i for i, c in enumerate(comm.membership) if c == 0]
386
print(f"Vertices in community 0: {comm_0_vertices}")
387
```
388

389
### Resolution and Parameter Tuning
390

391
Techniques for selecting optimal parameters and exploring different resolution scales.
392

393
**Usage Examples:**
394

395
```python
396
# Resolution parameter exploration for Leiden
397
modularities = []
398
n_communities = []
399
resolutions = [0.1, 0.2, 0.5, 1.0, 1.5, 2.0, 3.0, 5.0]
400

401
for res in resolutions:
402
    comm = g.community_leiden(resolution=res)
403
    modularities.append(comm.modularity)
404
    n_communities.append(len(comm))
405

406
# Find resolution with best modularity
407
best_idx = modularities.index(max(modularities))
408
best_resolution = resolutions[best_idx]
409
print(f"Best resolution: {best_resolution} (modularity: {modularities[best_idx]:.3f})")
410

411
# Stability analysis - run multiple times
412
stability_results = []
413
for _ in range(10):
414
    comm = g.community_leiden(resolution=1.0)
415
    stability_results.append((len(comm), comm.modularity))
416

417
avg_communities = sum(r[0] for r in stability_results) / len(stability_results)
418
avg_modularity = sum(r[1] for r in stability_results) / len(stability_results)
419
print(f"Stability - Avg communities: {avg_communities:.1f}, Avg modularity: {avg_modularity:.3f}")
420

421
# Multi-scale analysis with hierarchical methods
422
dendro = g.community_walktrap()
423
for n_clusters in range(2, min(11, g.vcount())):
424
    comm = dendro.as_clustering(n_clusters)
425
    print(f"{n_clusters} clusters: modularity {comm.modularity:.3f}")
426
```