Community Detection in Graphs

Mohammed Islam Hadjoudj

Operations Research Specialist

1. The short answer

Community detection splits the vertices of a network into groups that have many edges inside and few edges between them. It is clustering for graphs: friend circles in a social network, teams in an email log, protein complexes in a cell, topics in a citation network. There is no single correct answer, so every method rests on a definition of what a good group is, and most popular methods use the same one, called modularity.

In one sentence: use Louvain, or its successor Leiden, as the default, use label propagation when speed matters more than stability, keep Girvan-Newman for small networks where you want to see the whole hierarchy of splits, and always look at the groups you get instead of trusting a single score. Here, n is the number of vertices and m the number of edges.

2. Fifteen friends, three groups

The running example is a group of fifteen friends, A to O, with an edge between two people who message each other every week. There are 26 edges. The network was built to contain three circles of five friends, A to E, F to J and K to O, joined by five edges, and then checked by computer so that the methods below behave in instructive ways.

Most people would draw the same three circles by eye. One person is less clear: H has six contacts, three in its own group and three outside, including two in the group K to O. Any method has to decide where H belongs, and the rest of this guide uses that decision as a test.

3. Modularity: scoring a split

To compare splits you need a score. Counting the edges inside groups is not enough, because putting everyone in one group puts every edge inside. Modularity, introduced by Mark Newman and Michelle Girvan in 2004, subtracts what chance alone would give:

Q = sum over groups of [ (edges inside the group) / m  -  ( (total degree of the group) / 2m )² ]

The second term is the share of edges you would expect inside the group if every vertex kept its degree but the edges were wired at random. A group earns credit only for the edges it has beyond that expectation. The program below computes Q for five ways of splitting the friends.

# Fifteen friends; an edge joins two people who message each other every week.
FRIENDS = 'AB AC BD BE CE CH DE DJ EM FH FI FJ GH GI HJ HK HM IJ KL KM KN LN LO MN MO NO'.split()

def graph(edges):
    """Edges are 'AB' for single letters or '12-34' for numbers."""
    adj = {}
    for e in edges:
        a, b = e.split('-') if '-' in e else e
        adj.setdefault(a, set()).add(b)
        adj.setdefault(b, set()).add(a)
    return adj

def modularity(adj, groups):
    """Q = sum over groups of (share of edges inside) - (share of degree) squared."""
    m = sum(len(nbrs) for nbrs in adj.values()) / 2
    q = 0.0
    for g in groups:
        inside = sum(1 for v in g for u in adj[v] if u in g) / 2
        degree = sum(len(adj[v]) for v in g)
        q += inside / m - (degree / (2 * m)) ** 2
    return q

def show(groups):
    return ' '.join(sorted(''.join(sorted(g)) for g in groups))

if __name__ == '__main__':
    adj = graph(FRIENDS)
    for name, groups in [('three groups', [set('ABCDE'), set('FGHIJ'), set('KLMNO')]),
                         ('H moved to K', [set('ABCDE'), set('FGIJ'), set('HKLMNO')]),
                         ('two groups', [set('ABCDE'), set('FGHIJKLMNO')]),
                         ('everyone together', [set(adj)]),
                         ('everyone alone', [{v} for v in adj])]:
        print(f'{name:18} Q = {modularity(adj, groups):7.4f}')
# three groups       Q =  0.4712
# H moved to K       Q =  0.4016
# two groups         Q =  0.2951
# everyone together  Q =  0.0000
# everyone alone     Q = -0.0725

The three circles score 0.4712. In numbers: 21 of the 26 edges, 81%, lie inside a group, while random wiring with the same degrees would put 33.65% inside, and 0.8077 - 0.3365 = 0.4712. Everyone in one group scores exactly 0, because it is no better than chance, and everyone alone scores below zero. Moving H to the right-hand group drops the score to 0.4016, so by this measure H belongs with F to J.

Is 0.4712 the best possible? A network of 15 vertices can be split in 1,382,958,545 different ways, too many to list one by one, but a dynamic program over the 32,768 subsets of the vertices finds the maximum exactly. The best split is the three circles, with Q = 0.4712. On large networks no such check is possible: Ulrik Brandes and colleagues proved in 2008 that finding the split with maximum modularity is NP-hard, which is why every practical method is a heuristic.

4. Girvan-Newman: cut the bridges between groups

Michelle Girvan and Mark Newman's method of 2002 works from the top down. An edge that connects two groups carries many shortest paths, because every route from one group to the other must use it or one of the few others like it. That is the edge betweenness of the edge, computed with the same breadth-first search as betweenness centrality. The method deletes the edge with the highest betweenness, recomputes, and repeats. Each time the network falls into more pieces, it records the split and its modularity.

from collections import deque
from modularity import FRIENDS, graph, modularity, show

def edge_betweenness(adj):
    """Brandes' algorithm, crediting edges instead of vertices."""
    score = {}
    for s in adj:
        order, preds, sigma, dist = [], {v: [] for v in adj}, dict.fromkeys(adj, 0), {s: 0}
        sigma[s] = 1
        queue = deque([s])
        while queue:
            v = queue.popleft()
            order.append(v)
            for w in adj[v]:
                if w not in dist:
                    dist[w] = dist[v] + 1
                    queue.append(w)
                if dist[w] == dist[v] + 1:
                    sigma[w] += sigma[v]
                    preds[w].append(v)
        delta = dict.fromkeys(adj, 0.0)
        for w in reversed(order):
            for v in preds[w]:
                credit = sigma[v] / sigma[w] * (1 + delta[w])
                edge = tuple(sorted((v, w)))
                score[edge] = score.get(edge, 0) + credit / 2   # each pair is seen from both ends
                delta[v] += credit
    return score

def components(adj):
    seen, parts = set(), []
    for s in sorted(adj):
        if s not in seen:
            part, stack = set(), [s]
            while stack:
                v = stack.pop()
                if v not in part:
                    part.add(v)
                    stack.extend(adj[v])
            seen |= part
            parts.append(part)
    return parts

def girvan_newman(adj, verbose=False):
    """Delete the edge with the highest betweenness, recompute, repeat; keep every split."""
    work = {v: set(nbrs) for v, nbrs in adj.items()}
    splits = {1: [set(adj)]}
    while any(work.values()):
        score = edge_betweenness(work)
        a, b = max(sorted(score), key=score.get)
        work[a].discard(b)
        work[b].discard(a)
        parts = components(work)
        if len(parts) not in splits:
            splits[len(parts)] = parts
            if verbose:
                print(f'cut {a}{b}: {len(parts):2} groups  Q = {modularity(adj, parts):.4f}')
    best = max(splits.values(), key=lambda p: modularity(adj, p))
    return best, splits

if __name__ == '__main__':
    adj = graph(FRIENDS)
    best, splits = girvan_newman(adj, verbose=True)
    print('best:', show(best), round(modularity(adj, best), 4))
# cut DJ:  2 groups  Q = 0.2951
# cut HM:  3 groups  Q = 0.4712
# cut CE:  4 groups  Q = 0.4312
# cut GI:  5 groups  Q = 0.3780
# cut KM:  6 groups  Q = 0.3070
# cut HJ:  7 groups  Q = 0.2744
# cut LO:  8 groups  Q = 0.2241
# cut AC:  9 groups  Q = 0.1901
# cut BE: 10 groups  Q = 0.1287
# cut DE: 11 groups  Q = 0.0991
# cut FJ: 12 groups  Q = 0.0377
# cut IJ: 13 groups  Q = 0.0081
# cut MO: 14 groups  Q = -0.0429
# cut NO: 15 groups  Q = -0.0725
# best: ABCDE FGHIJ KLMNO 0.4712

The first edge to go is D-J, which already separates the left group: two pieces, Q = 0.2951. Next H-M falls and the right group comes free: three pieces, Q = 0.4712. After that the cuts start breaking real groups apart, and modularity only falls, down to -0.0725 when every vertex stands alone. Keeping the split with the highest score gives the three circles again.

The weakness is cost. Each round recomputes betweenness for every edge, which takes O(mn) time, and there are up to m rounds, so the whole method takes about O(m²n). That is fine for a few hundred edges and hopeless for a few million.

5. Louvain: grow groups from the bottom up

The Louvain method, published in 2008 by Vincent Blondel, Jean-Loup Guillaume, Renaud Lambiotte and Etienne Lefebvre at the Université catholique de Louvain, maximises modularity greedily in two phases that repeat:

1. Local moves. Start with every vertex in its own group. Visit the vertices one by one and move each to the neighbouring group that raises modularity most, if any move does. Repeat until no single move helps.
2. Aggregation. Merge each group into a single vertex. Edges inside the group become a loop on the new vertex, and edges between groups add up.

Then run phase 1 again on the smaller network. The gain of a move can be computed from a handful of sums, without recomputing Q from scratch, which is what makes the method fast.

from modularity import FRIENDS, graph, modularity, show

def louvain(adj, verbose=False):
    """Louvain: move single vertices while Q rises, then merge each group into one vertex."""
    w = {v: {u: 1 for u in adj[v]} for v in adj}       # w[v][v] holds edges inside a merged vertex
    members = {v: {v} for v in adj}
    m2 = sum(len(nbrs) for nbrs in adj.values())        # twice the number of edges
    level = 0
    while True:
        k = {v: sum(w[v].values()) for v in w}           # degree of each (merged) vertex
        group, total = {v: v for v in w}, dict(k)        # total = sum of degrees in a group
        moved = True
        while moved:
            moved = False
            for v in sorted(w):
                old = group[v]
                total[old] -= k[v]
                links = {}
                for u, x in w[v].items():
                    if u != v:
                        links[group[u]] = links.get(group[u], 0) + x
                gain = lambda g: links.get(g, 0) - total[g] * k[v] / m2
                best = old
                for g in sorted(links):
                    if gain(g) > gain(best) + 1e-12:
                        best = g
                group[v] = best
                total[best] += k[v]
                moved |= best != old
        if len(set(group.values())) == len(w):           # nothing merged: finished
            break
        level += 1
        merged = {}
        for v, g in group.items():
            merged.setdefault(g, {})
            for u, x in w[v].items():
                merged[g][group[u]] = merged[g].get(group[u], 0) + x
        members = {g: set().union(*(members[v] for v in w if group[v] == g)) for g in merged}
        w = merged
        if verbose:
            print(f'pass {level}: {len(w)} groups  Q = {modularity(adj, members.values()):.4f}')
    return list(members.values())

if __name__ == '__main__':
    adj = graph(FRIENDS)
    groups = louvain(adj, verbose=True)
    print('result:', show(groups))
# pass 1: 4 groups  Q = 0.4312
# pass 2: 3 groups  Q = 0.4712
# result: ABCDE FGHIJ KLMNO

The first pass ends with four groups: the middle and right circles are already complete, but the left circle has split into A, C and B, D, E, with Q = 0.4312. Vertex moves alone cannot fix that, because moving any single person between those two halves lowers the score. The second pass moves whole groups, merges the two halves, and reaches the optimum of 0.4712.

Louvain has two known flaws. It inherits every limit of modularity, described in section 7. And its groups can be badly connected, or even fall apart: a vertex that held a group together can move away in a later pass and leave the rest disconnected. Vincent Traag, Ludo Waltman and Nees Jan van Eck's Leiden algorithm of 2019 adds a refinement step that guarantees connected groups, and it is often recommended in Louvain's place.

6. Label propagation: fast, and different every time

Label propagation, proposed by Usha Nandini Raghavan, Réka Albert and Soundar Kumara in 2007, does not compute modularity at all. Every vertex starts with its own label. In random order, each vertex adopts the label that is most common among its neighbours, breaking ties at random. Dense groups settle on one label quickly, and the process stops when every vertex already has a most common label. Each sweep takes O(m) time, and few sweeps are usually needed.

import random
from collections import Counter
from modularity import FRIENDS, graph, show

def label_propagation(adj, seed):
    """Everyone starts with their own label and keeps adopting the most common one nearby."""
    rnd = random.Random(seed)
    label = {v: v for v in adj}
    for _ in range(1000):
        order = sorted(adj)
        rnd.shuffle(order)
        changed = False
        for v in order:
            if not adj[v]:
                continue
            count = Counter(label[u] for u in adj[v])
            top = max(count.values())
            best = sorted(l for l, c in count.items() if c == top)
            if label[v] not in best:                  # keep your label if it is among the best
                label[v] = rnd.choice(best)
                changed = True
        if not changed:
            break
    groups = {}
    for v, l in label.items():
        groups.setdefault(l, set()).add(v)
    return list(groups.values())

if __name__ == '__main__':
    adj = graph(FRIENDS)
    results = Counter(show(label_propagation(adj, seed)) for seed in range(1000))
    print('different results in 1000 runs:', len(results))
    for groups, n in results.most_common(4):
        print(f'{n:4}  {groups}')
# different results in 1000 runs: 49
#  387  ABCDE FGHIJ KLMNO
#  275  AC BDE FGHIJ KLMNO
#   46  ABCDE FIJ GHKLMNO
#   35  AB CE DFGHIJ KLMNO

The randomness matters. In 1,000 runs on the fifteen friends, label propagation produced 49 different answers. It found the three circles 387 times. The second most common answer, found 275 times, splits the left circle into A, C and B, D, E, the same intermediate state that Louvain's first pass reached. Other runs pulled G and H into the right-hand group, or merged two circles.

Nothing here is a bug: every one of those results is a valid stopping state. If you use label propagation, run it several times and keep the result with the best modularity, or compare how often each pair of vertices ends up together.

7. The resolution limit

Modularity has a blind spot that no algorithm can fix, because it is in the score itself. Santo Fortunato and Marc Barthélemy showed in 2007 that in a large network, maximising modularity can merge small groups that are obviously separate. The cause is the expected-edges term: it shrinks as the network grows, so merging two small groups costs almost nothing, while the single edge between them counts as a gain.

The standard example is a ring of cliques: groups of people who all know each other, each joined to the next by a single edge. The next program builds 30 groups of five and scores two splits.

from modularity import modularity
from louvain import louvain

def ring_of_cliques(n, size):
    """n complete groups of `size` people, each joined to the next by a single edge."""
    adj = {v: set() for v in range(n * size)}
    for c in range(n):
        people = range(c * size, (c + 1) * size)
        for a in people:
            adj[a] |= set(people) - {a}
        a, b = c * size, ((c + 1) % n) * size + 1
        adj[a].add(b)
        adj[b].add(a)
    return adj

if __name__ == '__main__':
    n, size = 30, 5
    adj = ring_of_cliques(n, size)
    cliques = [set(range(c * size, (c + 1) * size)) for c in range(n)]
    pairs = [cliques[i] | cliques[i + 1] for i in range(0, n, 2)]
    print('one group per clique:   Q =', round(modularity(adj, cliques), 4))
    print('cliques merged in pairs: Q =', round(modularity(adj, pairs), 4))
    found = louvain(adj)
    whole = all(any(g == set().union(*[c for c in cliques if c <= g]) for _ in [0]) for g in found)
    print('Louvain:', len(found), 'groups, Q =', round(modularity(adj, found), 4),
          ', every group a union of whole cliques:', whole)
# one group per clique:   Q = 0.8758
# cliques merged in pairs: Q = 0.8879
# Louvain: 15 groups, Q = 0.8879 , every group a union of whole cliques: True

Keeping the 30 groups apart scores 0.8758. Merging them in pairs scores 0.8879, so even a perfect modularity maximiser would never return the 30 natural groups, and Louvain merges them in pairs: it returns 15 groups. Jörg Reichardt and Stefan Bornholdt's resolution parameter γ multiplies the expected-edges term; values above 1 favour smaller groups and values below 1 larger ones. It moves the limit rather than removing it, so it pays to check the size of the groups you find against what you know about the network.

8. A real test: Zachary's karate club

In the 1970s the anthropologist Wayne Zachary recorded the friendships among 34 members of a university karate club while a dispute between the instructor and the club's administrator split it in two. His 1977 paper listed 78 friendships, and because the actual split is known, the network became the standard first test for community detection. The next program runs all three methods and compares them with the side each member joined, using the labels distributed with the NetworkX library. These record the club each member joined after the split. Zachary's faction data put member 9 with the administrator's side, although he joined the instructor's club, so studies that score against the factions, as Girvan and Newman did, count only member 3 as misplaced.

from collections import Counter
from modularity import graph, modularity
from girvan_newman import girvan_newman
from louvain import louvain
from lpa import label_propagation

# Zachary's karate club (1977): 34 members, 78 friendships, and the side each member took
# when the club split (H = the instructor's club, O = the administrator's), members 1 to 34.
CLUB = ('1-2 1-3 1-4 1-5 1-6 1-7 1-8 1-9 1-11 1-12 1-13 1-14 1-18 1-20 1-22 1-32 2-3 2-4 2-8 '
        '2-14 2-18 2-20 2-22 2-31 3-4 3-8 3-9 3-10 3-14 3-28 3-29 3-33 4-8 4-13 4-14 5-7 5-11 '
        '6-7 6-11 6-17 7-17 9-31 9-33 9-34 10-34 14-34 15-33 15-34 16-33 16-34 19-33 19-34 '
        '20-34 21-33 21-34 23-33 23-34 24-26 24-28 24-30 24-33 24-34 25-26 25-28 25-32 26-32 '
        '27-30 27-34 28-34 29-32 29-34 30-33 30-34 31-33 31-34 32-33 32-34 33-34').split()
SIDE = dict(zip([str(i) for i in range(1, 35)], 'HHHHHHHHHOHHHHOOHHOHOHOOOOOOOOOOOO'))

def wrong(groups):
    """Members placed in a group whose majority took the other side."""
    bad = []
    for g in groups:
        majority = Counter(SIDE[v] for v in g).most_common(1)[0][0]
        bad += sorted((v for v in g if SIDE[v] != majority), key=int)
    return bad

if __name__ == '__main__':
    adj = graph(CLUB)
    best, splits = girvan_newman(adj)
    print('Girvan-Newman, first split:', [len(g) for g in splits[2]], 'misplaced:', wrong(splits[2]))
    print('Girvan-Newman, best Q:', len(best), 'groups, Q =', round(modularity(adj, best), 4))
    groups = louvain(adj)
    print('Louvain:', len(groups), 'groups, Q =', round(modularity(adj, groups), 4),
          'sizes', sorted(len(g) for g in groups))
    runs = Counter(len(label_propagation(adj, s)) for s in range(1000))
    print('label propagation, groups found in 1000 runs:', dict(sorted(runs.items())))
# Girvan-Newman, first split: [15, 19] misplaced: ['3', '9']
# Girvan-Newman, best Q: 5 groups, Q = 0.4013
# Louvain: 4 groups, Q = 0.4188 sizes [5, 6, 11, 12]
# label propagation, groups found in 1000 runs: {1: 6, 2: 218, 3: 369, 4: 295, 5: 104, 6: 8}

The first split made by Girvan-Newman divides the club into 15 and 19 members and misplaces two people, members 3 and 9; both have friends on each side. Its best modularity is reached later, at five groups with Q = 0.4013. Louvain finds four groups with Q = 0.4188, very close to 0.4198, the proven maximum for this network, and each of its four groups lies on one side of the real split except for members 9 and 10. Label propagation varies again: in 1,000 runs it found anywhere from one to six groups, three most often.

The lesson is that the "true" answer of a real network depends on the question. The club split into two, but modularity prefers four groups, because the two factions each contain tighter circles. Neither answer is wrong; they answer different questions.

9. When groups blur: a measured benchmark

To measure accuracy you need networks with known groups. Girvan and Newman's benchmark of 2002 has 128 vertices in four groups of 32. Every vertex has about 16 edges, of which on average z_out lead to other groups. The larger z_out, the harder the groups are to see. Accuracy is measured by normalised mutual information (NMI), a score from 0 to 1 that is 1 only when the found groups match the planted ones exactly, as proposed for this purpose by Leon Danon and colleagues in 2005.

import math, random
from louvain import louvain
from lpa import label_propagation

def planted(rnd, z_out, groups=4, size=32, degree=16):
    """Girvan and Newman's test: 4 groups of 32, each vertex with about z_out edges leaving its group."""
    n = groups * size
    adj = {v: set() for v in range(n)}
    p_in, p_out = (degree - z_out) / (size - 1), z_out / (n - size)
    for a in range(n):
        for b in range(a + 1, n):
            if rnd.random() < (p_in if a // size == b // size else p_out):
                adj[a].add(b)
                adj[b].add(a)
    return adj

def nmi(found, size=32):
    """Normalised mutual information between the found groups and the planted ones (1 = identical)."""
    n = sum(len(g) for g in found)
    planted = {}
    for g in found:
        for v in g:
            planted.setdefault(v // size, []).append(v)
    h = lambda parts: -sum(len(p) / n * math.log(len(p) / n) for p in parts)
    mutual = 0.0
    for g in found:
        for p in planted.values():
            k = len(g & set(p))
            if k:
                mutual += k / n * math.log(k * n / (len(g) * len(p)))
    hf, hp = h(found), h(list(planted.values()))
    return 1.0 if hf + hp == 0 else 2 * mutual / (hf + hp)

if __name__ == '__main__':
    rnd = random.Random(7)
    print('edges out   Louvain   label propagation   (average NMI over 10 networks)')
    for z_out in range(1, 10):
        a = b = 0.0
        for _ in range(10):
            adj = planted(rnd, z_out)
            a += nmi(louvain(adj)) / 10
            b += nmi(label_propagation(adj, rnd.randrange(10**6))) / 10
        print(f'{z_out:9} {a:9.2f} {b:12.2f}')
# edges out   Louvain   label propagation   (average NMI over 10 networks)
#         1      1.00         1.00
#         2      1.00         1.00
#         3      1.00         1.00
#         4      1.00         0.90
#         5      0.99         0.85
#         6      0.97         0.35
#         7      0.80         0.10
#         8      0.50         0.02
#         9      0.20         0.00

Both methods are perfect while groups are clear. From 4 edges out of 16, label propagation starts to slip, and at 6 its score has collapsed to 0.35 while Louvain still scores 0.97. At 8, half of each vertex's edges leave its group, although the inside of a group is still 3.1 times denser than the space between groups, and even Louvain is down to 0.50. At z_out = 12 the groups would be no denser inside than outside. In fact they become impossible to recover sooner: Aurelien Decelle and colleagues showed in 2011 that in large networks built this way, no method can do better than chance once z_out passes about 9.

10. Where community detection is used

• Social networks. Finding circles of friends, colleagues or interest groups, and the people who bridge them, often together with the centrality measures.
• Biology. Groups in protein interaction networks often correspond to complexes or pathways; the guide to graph theory in biology covers these networks.
• Recommendation and marketing. Users who form a community tend to share interests, which helps to suggest content and to segment audiences.
• Fraud and security. Accounts that transact mostly with each other can form a tightly knit group that stands out from normal behaviour.
• Software. Groups in a dependency graph suggest natural module boundaries, and edges between groups show the couplings worth reviewing.

11. A short history

Splitting graphs into parts is old: Brian Kernighan and Shen Lin's heuristic of 1970 split a graph into parts of given sizes while cutting as few edges as possible, a problem that arose in placing electronic circuits on circuit boards. Community detection in today's sense, where the number and size of the groups are not given in advance, took off with Girvan and Newman's paper of 2002, which also popularised Zachary's karate club as a test. Newman and Girvan defined modularity in 2004, and the same year Aaron Clauset, Newman and Cristopher Moore published a fast greedy method to maximise it. Label propagation followed in 2007, the same year as the resolution limit, and the Louvain method in 2008. Santo Fortunato's 2010 survey is a standard overview, and the Leiden algorithm of 2019 fixed Louvain's disconnected groups.

12. Common mistakes

13. Glossary

15. References

The algorithms, results and attributions above come from these sources, listed in chronological order.

1. Kernighan, B. W. and Lin, S. (1970). "An Efficient Heuristic Procedure for Partitioning Graphs." Bell System Technical Journal 49(2), 291 to 307.
2. Zachary, W. W. (1977). "An Information Flow Model for Conflict and Fission in Small Groups." Journal of Anthropological Research 33(4), 452 to 473.
3. Girvan, M. and Newman, M. E. J. (2002). "Community Structure in Social and Biological Networks." Proceedings of the National Academy of Sciences 99(12), 7821 to 7826.
4. Newman, M. E. J. and Girvan, M. (2004). "Finding and Evaluating Community Structure in Networks." Physical Review E 69, 026113.
5. Clauset, A., Newman, M. E. J. and Moore, C. (2004). "Finding Community Structure in Very Large Networks." Physical Review E 70, 066111.
6. Danon, L., Díaz-Guilera, A., Duch, J. and Arenas, A. (2005). "Comparing Community Structure Identification." Journal of Statistical Mechanics: Theory and Experiment, P09008.
7. Reichardt, J. and Bornholdt, S. (2006). "Statistical Mechanics of Community Detection." Physical Review E 74, 016110.
8. Fortunato, S. and Barthélemy, M. (2007). "Resolution Limit in Community Detection." Proceedings of the National Academy of Sciences 104(1), 36 to 41.
9. Raghavan, U. N., Albert, R. and Kumara, S. (2007). "Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks." Physical Review E 76, 036106.
10. Brandes, U., Delling, D., Gaertler, M., Görke, R., Hoefer, M., Nikoloski, Z. and Wagner, D. (2008). "On Modularity Clustering." IEEE Transactions on Knowledge and Data Engineering 20(2), 172 to 188.
11. Agarwal, G. and Kempe, D. (2008). "Modularity-Maximizing Graph Communities via Mathematical Programming." European Physical Journal B 66(3), 409 to 418.
12. Blondel, V. D., Guillaume, J.-L., Lambiotte, R. and Lefebvre, E. (2008). "Fast Unfolding of Communities in Large Networks." Journal of Statistical Mechanics: Theory and Experiment, P10008.
13. Fortunato, S. (2010). "Community Detection in Graphs." Physics Reports 486(3 to 5), 75 to 174.
14. Decelle, A., Krzakala, F., Moore, C. and Zdeborová, L. (2011). "Asymptotic Analysis of the Stochastic Block Model for Modular Networks and Its Algorithmic Applications." Physical Review E 84(6), 066106.
15. Traag, V. A., Waltman, L. and van Eck, N. J. (2019). "From Louvain to Leiden: Guaranteeing Well-Connected Communities." Scientific Reports 9, 5233.