🔵 Community Detection (Louvain)

Modularity Q measures how much more densely connected nodes within the same community are compared to what you'd expect from a random graph with the same degree sequence. The formula Q = (1/2m)·Σ[A_ij − k_i k_j/2m]·δ(c_i,c_j) sums, over every pair of nodes in the same community, the actual edge weight A_ij minus the expected weight k_i k_j/2m under random wiring. Q ranges roughly from -0.5 to 1, and higher values indicate a stronger community structure.

For each node, the algorithm temporarily removes it from its current community and considers moving it to any community that one of its neighbours belongs to. It computes the modularity gain for each candidate community and moves the node to whichever gives the largest positive gain, or leaves it in place if no move helps. This repeats for every node, over multiple sweeps, until a full sweep produces no more moves.

Once local moving stabilizes, every detected community is collapsed into a single super-node. Edges between two communities become a single weighted edge between their super-nodes, and edges within a community become a self-loop on the super-node that stores their combined internal weight. Local moving is then re-run on this smaller graph, effectively looking for communities of communities, which is why the process produces a hierarchy of levels rather than a single flat partition.

Louvain is a greedy heuristic, not an exact optimizer, so it can only follow moves that improve modularity immediately and can get stuck in a local optimum. When p_in and p_out are close together, as in the "Weak structure" or "Random" presets, the planted groups aren't actually much denser than the rest of the graph, so there is little modularity signal for the algorithm to detect, and it may merge, split, or miss the true groups.

No. Dragging only changes the on-screen (x, y) position of a node in the force-directed layout used for drawing; it does not touch the underlying adjacency data that Louvain operates on. The layout step itself just runs a simple repulsion/attraction simulation between all node pairs and edges each frame to keep the picture readable, completely separately from the community-detection logic.