I need help with modularity of a network. i want to understand the modularity defined by Newman : https://arxiv.org/pdf/cond-mat/0308217.pdf He says that M is between 0 and 1 if the modularity M is determined as \begin{equation} M = \sum_i (e_{ii} - a_i^2) \end{equation} while $e_{ij}$ "is the fraction of all edges in the network that link vertices in community i to vertices in community j" and \begin{equation} a_i = \sum_j e_{ij}, \end{equation} You get a $kxk$ Matrix $e$ ( k communities) with $e_{ij}$ as elements. Now, i constructed a Graph with such a clustering : selfmade graph
For this i get the matrix:
e =
(1/7 -- 2/7 )
(2/7 -- 4/7 ) (sorry my latex matrix code is not woriking here)
Now if i put these into the modularity formula i get M = -0,204. With optimal clustering into two communites i get M = 0,2. Can someone explain? Somewhere else it is stated taht the modularity is between [-1,1), but im not sure if the other (spektral formula with Adjacency Matrix) is meant. Thanks!
Modularity involves a few ingredients. First off there is the graph/network, then there is the partition of the vertices, then there are the details of the definition of modularity. Embedded in the definition is a null model which is used to specify what we mean exactly by "random". Typically the choice of null model is the configuration model which is a random graph model that can be read about here.
Once the definition of modularity is fixed, we essentially have a function that maps a graph/network and a partition of the vertices to a value. This value is between $-1$ and $1$ (assuming a certain normalization---sometimes it can be between $-1/2$ and $1$). Given a graph/network that seems to have community structure (such as the example you linked to), you can still get a negative modularity score if the partition used to calculate modularity doesn't correspond to the community structure. However, computing the modularity score corresponding to your example graph and a 'good' partition of the vertices results in a positive modularity score.
A lot of community detection focuses on finding this partition in a process called modularity maximization, which are typically approximative algorithms for finding the partition of vertices that results in the largest modularity score (the number of partitions of vertices grows very, very fast). For a graph/network with a large number of vertices, it's typical some partitions have positive scores and some will have negative scores. Finding a partition with a positive score is not proof that the graph/network has community structure. For an excellent paper on this topic, check out: Cristopher Moore's The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness.
EDIT/UPDATE We can find the modularity score for each graph and each partition of its vertices. As we said, this can be a negative value. We can also assign a maximum modularity score (i.e., a single value) to a graph by taking the maximum score over all of the partitions of its vertices. I believe this is what Newman & Girvan are referring to in the paper that you linked to in your question. The trivial partition, where all vertices are in the same community, leads to a modularity score of $0$ and there are graphs where the trivial partition is the maximally modular partition, meaning that all other partitions have non-positive modularity scores. Thus $0$ is the minimum that the maximum modularity can take. I believe that for most graphs there will be both partitions with negative modularity scores and partitions with positive modularity scores.