Why Compare Weighted and Unweighted Graphs?
A cell graph records which cells are connected, but it may also record how strong each connection is. That strength might encode a similarity, an affinity, or another nonnegative measure used to construct the graph. A binary graph keeps only whether a connection exists; a weighted graph retains the recorded strength. These representations have the same topology when they have the same vertices and the same set of nonzero edges, but they need not lead to the same community partition.
The choice matters because community detection uses edge information to define what counts as a cohesive group. If all present edges are treated equally, a weak connection has the same direct contribution as a strong one. If weights are used, both the observed within-community connection strength and the graph-wide baseline used by the objective can change. Thus, “weighted” does not simply mean “the same answer with more detail”: it changes the optimization problem.
The binary representation discards the magnitudes of all positive \(a_{ij}\). The weighted representation is meaningful only if larger weights genuinely indicate stronger connections for the method being used. For example, a distance for which larger values mean less similar cells cannot be inserted directly as an affinity weight: doing so would tell an affinity-based objective that dissimilar pairs are strongly connected. A distance must first be converted using a defensible transformation, or the graph method must be designed for distances.
Weighted and Binary Modularity
For a simple undirected graph with nonnegative weights and no self-loops, define the strength of vertex \(i\) as \(k_i=\sum_j a_{ij}\), and the total edge weight as \(m=\frac{1}{2}\sum_{i,j}a_{ij}\). In the binary graph, the corresponding degree is \(d_i=\sum_j b_{ij}\), and the number of edges is \(m_B=\frac{1}{2}\sum_{i,j}b_{ij}\). The factor of one-half avoids counting each undirected edge twice.
At resolution parameter \(\gamma>0\), weighted modularity for a partition \(g\) is
Here \(\mathbf{1}(g_i=g_j)\) is 1 when vertices \(i\) and \(j\) belong to the same community and 0 otherwise. Binary modularity \(Q_{\gamma}^{(B)}\) has the same form with \(b_{ij}\), \(d_i\), and \(m_B\) replacing \(a_{ij}\), \(k_i\), and \(m\). In each case the first term reflects observed edges within communities; the second is a degree- or strength-based reference term. The objective favors partitions with more within-community connection than that reference predicts.
For a community \(C\), let \(L_C\) be the sum of weights on edges whose two endpoints are in \(C\), counting each edge once, and let \(K_C=\sum_{i\in C}k_i\). Grouping the terms of the weighted modularity sum by community gives a useful equivalent expression:
The binary expression uses the number of internal edges and the sum of binary degrees in place of \(L_C\) and \(K_C\). This form makes clear why converting a graph to binary can affect more than the internal edges: it also changes every vertex’s degree, the total edge count, and hence the reference term.
Why the Objective Changes
The modularity formula can be understood as comparing observed adjacency with a degree-based null expectation. In the weighted configuration reference, the expected weight between vertices \(i\) and \(j\) is \(k_i k_j/(2m)\). Subtracting this expected contribution from observed weight gives the bracketed quantity in the definition. Summing only pairs assigned to the same community and normalizing by \(2m\) yields \(Q_{\gamma}^{(W)}\). Replacing weights with indicators changes both the observed adjacency and the strengths used in this reference; it is not merely a rescaling of the final score.
If every positive edge has the same weight \(c>0\), weighted and binary modularity are identical for every partition at the same \(\gamma\): \(a_{ij}=c b_{ij}\), \(k_i=c d_i\), and \(m=c m_B\), so the factors of \(c\) cancel in the objective. When weights vary, that cancellation does not generally occur. It is therefore the relative pattern of weights, not their overall units, that can change the weighted modularity ranking of partitions.
Worked Example: Unequal Weights Resolve a Binary Tie
Consider four hypothetical cells with edges forming a cycle: \(1\!-\!2\), \(2\!-\!3\), \(3\!-\!4\), and \(4\!-\!1\). Suppose edges \(1\!-\!2\) and \(3\!-\!4\) each have weight 3, while the other two edges each have weight 1. Compare the partition \(A=\{\{1,2\},\{3,4\}\}\) with \(B=\{\{1,4\},\{2,3\}\}\), using \(\gamma=1\).
For the binary graph, there are \(m_B=4\) edges, and every vertex has degree 2. In either partition there are two internal edges, and each community has degree sum 4. Thus,
The binary objective cannot distinguish these two partitions: it has discarded the difference between strong and weak edges. In the weighted graph, \(m=8\), each vertex has strength 4, and each community in either partition has strength sum 8. Partition \(A\) has internal weight \(L_C=3\) in each community, whereas \(B\) has internal weight \(L_C=1\) in each community. Therefore,
Among these two candidates, weighted modularity favors \(A\), the partition that retains the two strong pairs. This calculation does not by itself prove that \(A\) is the global maximum over every possible partition; it shows exactly how the weighting changes the comparison. The binary scores tie, while the weighted scores differ by 0.50.
Worked Example: Uniform Rescaling Does Not Change the Result
Use the same four-vertex cycle, but suppose all four edges have weight 2. Compare weighted modularity with binary modularity for partition \(A=\{\{1,2\},\{3,4\}\}\) at \(\gamma=1\).
For the weighted graph, \(m=8\), each vertex has strength 4, and each community has internal weight 2 and strength sum 8. Hence
The binary graph has four edges, degree 2 at every vertex, two internal edges in total, and degree sum 4 in each community. Its score is
The agreement is not evidence that weighted and binary analysis always agree. In this example every present edge had the same weight, so multiplying every binary edge by 2 changed the units but not the relative edge pattern. With unequal weights, the preceding example shows that the ranking can differ.
When Binarization Can Matter
Discarding weights is consequential when their variation represents meaningful differences in connection strength and those differences align with possible community boundaries. In the first example, the strong within-pair edges and weak between-pair edges distinguish a partition that the binary graph cannot prefer. In other graphs, weights may vary but be arranged so that the best partition remains unchanged. A change is not guaranteed merely because weights are nonconstant: the full objective, including its reference term, determines the result.
The formula also explains why “keep the strongest edges” and “use a weighted graph” are not equivalent operations. Thresholding removes edges and changes the graph’s support; binarizing retains every positive edge but sets its magnitude to one. Both are modeling choices, and either may change the partition, but for different reasons. This tutorial’s comparison assumes the edge support is held fixed.
For a fair comparison, use the same cell set, the same nonzero edge support, the same resolution parameter where it has the same interpretation, and compatible algorithm settings. Then calculate or report the objective appropriate to each representation. A weighted modularity value and a binary modularity value have different inputs and generally should not be compared as though their numerical scales were directly interchangeable. The useful comparison is primarily between the resulting assignments and the assumptions that produced them.
Confirm that larger values indicate stronger affinity for the chosen algorithm. Inspect the transformation from any original distance or similarity measure.
Keep the same vertices and nonzero edge support, and form the binary graph by replacing each positive weight with 1.
Use a method that supports weighted edges, and match the objective and resolution settings as closely as their definitions allow.
Identify which cells change communities and check whether those changes correspond to distinctions in edge strengths rather than an accidental difference in graph construction.
Assumptions, Diagnostics, and Alternatives
The modularity calculations above assume an undirected graph with nonnegative weights, no self-loops, and a positive total edge weight. They also assume that the weights have a meaningful interpretation as connection strengths. Directed graphs require a directed objective, and negative weights require a method whose definition explicitly accommodates them. Do not silently apply the undirected nonnegative formula to either case.
Several checks can reveal a problematic comparison. Verify that binarization preserved exactly the intended edge support; confirm that weights are finite, nonnegative, and oriented so larger means stronger; and check that any normalization or thresholding was applied consistently. If every weight is identical, the weighted and binary modularity objectives must agree at the same \(\gamma\); a discrepancy suggests a coding or setup error. If the graphs differ in vertices or edge support, the comparison no longer isolates the effect of retaining weights.
Modularity is not the only community-detection objective. Methods based on random walks or spectral structure can also use weights, but their behavior depends on how weights enter their transition probabilities or matrices. The Constant Potts Model uses a different objective and reference structure; a weighted version must be defined for the weights at hand. Therefore, a conclusion about weighted versus unweighted modularity should not automatically be generalized to every graph-clustering method. When the scientific question concerns edge strength, a weighted method is a natural candidate; when weights are noisy or lack a defensible interpretation, binary analysis may be more robust to their magnitudes, though it still depends on the chosen edge support.
A common mistake is to say, “The weighted partition must be better because its modularity is larger.” This compares unlike objectives if the weighted and binary graphs were scored separately, and it treats an optimization score as a direct measure of biological truth. The correction is to report the representation, objective, and settings; compare the assignments; and ask whether the edge weights encode reliable information relevant to the question. Neither representation is universally preferable. Weighted analysis can preserve useful distinctions, but it can also amplify unreliable weights; binary analysis is simpler, but it erases all distinctions among retained edges.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions.
- For a weighted undirected graph, what is the strength \(k_i\), and why is total edge weight defined with a factor of one-half?
- If all positive edges have the same weight \(c>0\), what relationship should hold between weighted and binary modularity at the same \(\gamma\)?
- In the four-cell cycle example, why did the binary scores tie while the weighted scores favored partition \(A\)?
- A graph stores Euclidean distances as edge weights, with larger values meaning less similar cells. What should be checked before using those values in an affinity-based weighted method?
Solutions. (1) \(k_i=\sum_j a_{ij}\), the sum of the weights incident to vertex \(i\). The factor of one-half in \(m=\frac12\sum_{i,j}a_{ij}\) prevents counting each undirected edge twice. (2) The objectives agree for every fixed partition: \(a_{ij}=c b_{ij}\), \(k_i=c d_i\), and \(m=c m_B\), so the scale cancels. (3) The binary graph treats all four edges equally, whereas the weighted graph gives greater internal weight to the two strong pairs in \(A\); the calculation gives binary scores 0 for both candidates and weighted scores 0.25 for \(A\) and \(-0.25\) for \(B\). (4) Check that the method interprets larger weights as stronger affinities. The distances may need a justified transformation, or a method designed to use distances.