0
$\begingroup$

According to Wikipedia,

Modularity is the fraction of the edges that fall within the given groups minus the expected fraction if edges were distributed at random

This definition is easy to understand for unweighted graphs, but several community detection algorithms that use modularity optimization, work for weighted graphs as well. All the community detection algorithms in igraph for instance, have a parameter to pass edge weights.

I'm trying to figure out how to interpret the communities for weighted networks in the light of modularity optimization.

$\endgroup$
1
$\begingroup$

The the way it's most likely done would be to use the edge weights to modify the definition of counting edges.

For example, suppose that $E$ is the set of all edges, and $S$ is the set of edges in a given group. We somehow take a sample $E' \subseteq E$ with $|E'| = p |E|$. Then the actual fraction of edges chosen from $S$ is $\frac{|E' \cap S|}{|S|}$, and the expected fraction if $E'$ were random is $p|S|$. We can use these to compute modularity.

Now suppose that each edge $e \in E$ has a weight $w_e$. Then the weighted size of $S$ is not $|S|$ but $\sum_{e \in S} w_e$. Similarly, the weighted fraction of edges chosen from $S$ is $$ \frac{\sum_{e \in E' \cap S} w_e}{\sum_{e \in S} w_e}, $$ while the expected weighted fraction if $E'$ were random is just $p \sum_{e \in S} w_e$.

I can't guarantee that an algorithm whose implementation I've never looked at uses this definition, but in my opinion it is the most reasonable one to use: in general, the way definitions are generalized to weighted objects is often to replace the size of a set with the sum of weights in that set. This reduces to the ordinary definition if all weights are set to $1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.