A network is a complicated system with both small-scale structure ("what is the average degree of a node?", "how many nodes are involved in triangles?") that generally depends only on individual nodes and thier neighbors, and large-scale structure ("what is the diameter of the graph?", "how are sets of nodes connected?").
Quantifying network structure, and deciding whether or not that structure is meaningful, depends strongly on a notion of average network structure. In other words, we can understand structural measurements on a network by deciding how much they deviate from an average network, or an appropriately selected null model.
The following measurements of network structure all try to determine how much more connected certain nodes are than average. In order to define an average, all of these measurements use a null model known as the configuration model. The configuration model maintains the degree distribution of a network $\vec{k}$, but rearranges its edges. For any given node, we are essentially asking the question: "are the number of connections of this node special, or the types of other nodes that it is connected to?"
In [ ]:
# Import some libraries
from __future__ import division
import igraph
import numpy as np
from random import shuffle, random
import matplotlib.pyplot as plt
from IPython.display import Image
from tabulate import tabulate
%matplotlib inline
In [ ]:
# get some graphs to use as example graphs
color_dict = {1: "blue", 2: "red", 3: "green", 4: "yellow", 5: "purple", 6: "pink"}
shape_dict = {1: "rectangle", 2: "circle", 3: "triangle-up", 4: "triangle-down"}
# Zachary karate club graph
karate = igraph.Nexus.get("karate")
karate_adjmat = np.matrix([x for x in karate.get_adjacency()])
karate_labels = [int(x) for x in karate.vs["Faction"]]
karate.vs["color"] = [color_dict[x] for x in karate_labels]
karate.vs["shape"] = [shape_dict[x] for x in karate_labels]
karate.vs["label"] = karate.vs["name"]
print karate.summary()
print igraph.Nexus.info("karate")
In [ ]:
igraph.plot(karate)
# Orrr, if you're lame and you couldn't get Cairo to work on your machine :P, uncomment
#Image(filename="karate_club_graph.png", width=600)
In [ ]:
# UK faculty graph (interactions between faculties at UK universities)
UKfaculty = igraph.Nexus.get("UKfaculty")
UKfaculty_adjmat = np.matrix([x for x in UKfaculty.get_adjacency()])
UKfaculty_labels = [int(x) for x in UKfaculty.vs["Group"]]
UKfaculty.vs["color"] = [color_dict[x] for x in UKfaculty_labels]
UKfaculty.vs["shape"] = [shape_dict[x] for x in UKfaculty_labels]
print UKfaculty.summary()
print igraph.Nexus.info("UKfaculty")
In [ ]:
igraph.plot(UKfaculty)
# Orrr, if you're lame and you couldn't get Cairo to work on your machine :P, uncomment
#Image(filename="UKfaculty_graph.png", width=600)
A refresher from networks-201.
Last time we talked about null models as a concept for graphs and a base point for comparing graph structure. We talked briefly about the configuration model, which is a random graph model that has exactly the same degree distribution, but a different structure, than some original graph. Basically, if a graph G has 10 nodes with degrees $\vec{k} = [1,5,2,9,3,6,5,4,1,8]$, then some configuration model graph, G_random would (ideally) have the exact same $\vec{k}$, but the nodes are connected to each other differently (have different neighbors). In reality the algorithm that we use to generate a configuration model of the graph sometimes generates self-loops and multi-edges, which are deleted, leaving the generated graph with slightly fewer edges than the original.
In [ ]:
def config_model(graph):
# build a random graph based on the configuration model
C = graph.copy()
C.delete_edges(None)
# graph with the same edge list as G
# Add random edges
if graph.is_directed():
# vertex list A
A_in = []
A_out = []
for v in graph.vs().indices:
for x in range(0, graph.indegree(v)):
A_in.append(v)
for x in range(0, graph.outdegree(v)):
A_out.append(v)
shuffle(A_in)
shuffle(A_out)
# make the edge list
_E = [(A_out[x], A_in[x]) for x in range(0, len(A_in))]
else:
# vertex list A
A = []
for v in graph.vs().indices:
for x in range(0, graph.degree(v)):
A.append(v)
shuffle(A)
# make the edge list
_E = [(A[2*x], A[2*x+1]) for x in range(0,int(len(A)/2))]
E = set([x for x in _E if x[0]!=x[1]])
# add the edges to C
C.add_edges(E)
# return the configuration model generated graph
return C
For any given network, if we created a configuration model based on that network, the expected number of edges between nodes $a$ and $b$ would be $\frac{k_ak_b}{2m}$ where $k_a$ and $k_b$ are the degrees of nodes $a$ and $b$ respectively, and $m$ is the number of edges in the network.
To justify that claim, consider the following. A node $a$ with degree $k_a$ has $k_a$ edges attached to it. Each of those edges has 2 ends, one attached to node $a$, and the other attached (randomly) to some other node in the network. In the configuration model, each node has a fixed degree, so the probablity of a given edge attaching to a node $b$ with degree $k_b$ is $\frac{k_b}{2m}$ where $k_b$ is the number of ends of edges attached to $b$, and $2m$ is the number of ends of edges in the network (each edge $m$ has two ends). Then the expected number of connections between two vertices (which can usually be interpreted as the probability of a connection between two vertices) is: $$E[\text{edge}] = k_a\frac{k_b}{2m}$$
Interpreting this quantity as a probability for a simple graph (a graph without multi-edges and self-loops) assumes that the graph is sparse (the number of edges is much smaller than the number of possible edges) and that the edges are not overly concentrated in a few nodes. For many social graphs, these are fine assumptions.
In [ ]:
# Calculate the expected number of edges between each pair of nodes, using the configuration model
def expected_edges(adjmat):
(i, j) = adjmat.shape
m = np.sum(adjmat)/2
k_mat = np.sum(adjmat,0)
k = [k_mat[0,x] for x in range(0,i)]
q = np.zeros((i,j))
for row in xrange(0,i):
for col in xrange(0,j):
if (row != col):
q[row,col] = k[row]*k[col]/(2*m)
return q
# calculate the fraction of times two nodes are connected in the null model
def frac_of_times_connected(graph, iterations = 1000):
config_adjmat = np.zeros((len(graph.vs), len(graph.vs)))
for i in range(0, iterations):
config = config_model(graph)
config_adjmat += np.matrix([x for x in config.get_adjacency()])
frac_connected = np.divide(config_adjmat, float(iterations))
return frac_connected
fig, axes = plt.subplots(1,3, figsize=(15,5))
print "Axes are labeled with vertex #"
axes[0].set_title("Expected # edges")
axes[0].matshow(expected_edges(karate_adjmat), cmap = 'gist_heat_r')
axes[1].set_title("Fraction connected in the model")
axes[1].matshow(frac_of_times_connected(karate, iterations = 1000), cmap = 'gist_heat_r')
axes[2].set_title("Edges in the actual graph")
axes[2].matshow(karate_adjmat, cmap = 'gist_heat_r')
plt.show()
Notice how vertices 0 and 34 aren't connected in the real graph (0 and 34 are John A and Mr Hi respectively, the president and the instructor who led the splitting factions), but they are almost always connected in the configuration model of the karate graph. That is because they both have a very high degree, and, in edges were assigned at random, would likely connect with eachother. In case you were curious how the names correlate with factions:
In [ ]:
print tabulate({"Mr Hi (Actor 0), Faction 1": [x["name"] for x in karate.vs if x["Faction"] == 1.0],
"John A (Actor 34), Faction 2": [x["name"] for x in karate.vs if x["Faction"] == 2.0]}, headers = "keys")
To what extent does like connect to like?
Reference: Networks Ch 7 S13, Homophily and Assortative Mixing
Modularity, $Q$, measures the fraction of edges connecting like (or unlike) nodes in a network. To do this, we take the difference between that actual fraction of edges connecting nodes fo the same type, Starting with $E[edge] = k_a\frac{k_b}{2m}$ for any given nodes $a$ and $b$, we can then say that: $$E[\text{edges connecting nodes of the same type}] = \frac{1}{2}\sum_{ij}\frac{k_ik_j}{2m}\delta(c_i, c_j) = \text{(for directed graphs)} \frac{1}{2}\sum_{ij}\frac{k_i^{in}k_j^{out}}{2m}\delta(c_i, c_j)$$ Where $c_i$ denotes the "type" of node $i$ and $$ \delta(c_i, c_j) = \left\{ \begin{array}{lr} 1 & : c_i = c_j\\ 0 & : c_i \neq c_{j} \end{array} \right. $$
We can also say that the actual number of edges connecting nodes of like types is: $$\text{Edges connecting like nodes} = \frac{1}{2}\sum_{ij}A_{ij}\delta(c_i, c_j)$$ ($A$ is the adjacency matrix, where $A_{ij} = 1$ if there is an edge between node $i$ and node $j$, and 0 else.
Then the difference between the actual number of in-group edges and the expected number, normalized by the number of edges in the network is given by:
$$Q = \frac{1}{2m}\sum_{ij}\left(A_{ij} - \frac{k_ik_j}{2m}\right)\delta(c_i, c_j)$$We call $Q$ modularity.
In [ ]:
def modularity(adjmat, labels):
(i, j) = adjmat.shape
m = np.sum(adjmat)/2
kin_mat = np.sum(adjmat,0)
kout_mat = np.sum(adjmat,1)
kin = [kin_mat[0,x] for x in range(0,i)]
kout = [kout_mat[x,0] for x in range(0,i)]
q = 0
for row in xrange(0,i):
for col in xrange(0,j):
if (labels[row] == labels[col]):
q += (adjmat[row, col] - kin[row]*kout[col]/(2*m))
Q = q/(2*m)
return Q
If we have labels on the nodes in the network (i.e., "users whose primary language is X"), are users with the same label more connected than average? If we have scalar attributes on the network (i.e., "a user is X years old"), are users with similar attributes more connected than average?
Reference: Mixing Patterns in Networks by MEJ Newman
Discrete assortative mixing is exactly a normalized modularity measurement on node attributes.
We can normalize $Q$ by dividing it by its maximal value on a graph (that is, the value that it would take if all nodes were only conencted to nodes with the same labels).
$$r = \frac{Q}{Q_{max}} = \frac{\sum_{ij}\left(A_{ij} - k_ik_j/2m\right)\delta(c_i, c_j)}{\sum_{ij}\left(1 - k_ik_j/2m\right)\delta(c_i, c_j)} = \text{(for directed graphs) } \frac{\sum_{ij}\left(A_{ij} - k_i^{in}k_j^{out}/2m\right)\delta(c_i, c_j)}{\sum_{ij}\left(1 - k_i^{in}k_j^{out}/2m\right)\delta(c_i, c_j)} $$Now $r$ falls between -1 and 1 for all networks, where a value of $r=1$ is a perfectly assortative network (like connects with like) and $r=-1$ is a perfectly dissassortative network (like connects with dislike).
In [ ]:
def normalized_modularity(adjmat, labels):
(i, j) = adjmat.shape
m = np.sum(adjmat)/2
kin_mat = np.sum(adjmat,0)
kout_mat = np.sum(adjmat,1)
kin = [kin_mat[0,x] for x in range(0,i)]
kout = [kout_mat[x,0] for x in range(0,i)]
Q = 0
Qmax = 0
for row in xrange(0,i):
for col in xrange(0,j):
if labels[row] == labels[col]:
d = 1
else:
d = 0
Q += (adjmat[row, col] - kin[row]*kout[col]/(2*m))*d
Qmax += adjmat[row, col] - (kin[row]*kout[col]/(2*m))*d
r = Q/Qmax
return r
Warning: I'm about to gloss over a little algebra.
Define the matrix $\mathbf{e}$ as a matrix whose entries $\mathbf{e}_{ij}$ are the fraction of edges in the graph connecting nodes of type $i$ to nodes of type $j$. Call $\mathbf{e}$ the mixing matrix of the graph.
Then with some algebra (pg 225 of Networks & in Mixing Patterns of Networks) we can turn our expression for normalized modularity into this expression: $$ r = \frac{\mathbf{Tr}(e) - ||\mathbf{e}^2||}{1- || \mathbf{e}^2||} $$
In [ ]:
# Calculate the mixing matrix e
def mixing_matrix(adjmat, labels):
(i, j) = adjmat.shape
m = np.sum(adjmat)
labels_to_indices = {}
index = 0
for l in labels:
if l not in labels_to_indices.keys():
labels_to_indices[l] = index
index += 1
e = np.zeros((index, index))
for row in xrange(0,i):
for col in xrange(0,j):
e[labels_to_indices[labels[row]], labels_to_indices[labels[col]]] += adjmat[row, col]
e = np.divide(e, m)
return e
# Use e to calculate the assortativity
def assortativity(adjmat, labels):
e = mixing_matrix(adjmat, labels)
sum_e_squared = np.sum(np.dot(e,e))
r = (e.trace() - sum_e_squared)/(1 - sum_e_squared)
return r
In [ ]:
print "----------------------------------------------------"
print "The mixing matrix for the karate club graph:"
print mixing_matrix(karate_adjmat, karate_labels)
print "'Normalized modularity' of the karate club graph: {}".format(normalized_modularity(karate_adjmat, karate_labels))
print "'Assortativity' of the karate club graph: {}".format(assortativity(karate_adjmat, karate_labels))
print "----------------------------------------------------"
print "The mixing matrix for the UKfaculty graph:"
print mixing_matrix(UKfaculty_adjmat, UKfaculty_labels)
print "'Normalized modularity' of the UKfaculty graph: {}".format(normalized_modularity(UKfaculty_adjmat, UKfaculty_labels))
print "'Assortativity' of the UKfaculty graph: {}".format(assortativity(UKfaculty_adjmat, UKfaculty_labels))
print "----------------------------------------------------"
print "Hint: those last two numbers are the same"
We can also measure the assortativity of a network on scalar characteristics, such as age. In this way, the question is, "do nodes with more similar characteristics associate more?"
The following is essentially a correlation coefficient calculation on node connectivity over scalar charcteristics $x$.
$$r = \frac{\sum_{ij}\left(A_{ij} - k_i^{in}k_j^{out}/2m\right)x_i x_j}{\sum_{ij}\left(A_{ij}x_i^2 - \left(k_i^{in}k_j^{out}/2m \right) x_i x_j\right)}$$
In [ ]:
def assortativity_scalar(adjmat, values):
(i, j) = adjmat.shape
m = np.sum(adjmat)/2
kin_mat = np.sum(adjmat,0)
kout_mat = np.sum(adjmat,1)
kin = [kin_mat[0,x] for x in range(0,i)]
kout = [kout_mat[x,0] for x in range(0,i)]
covar = 0
var = 0
for row in xrange(0,i):
for col in xrange(0,j):
covar += (adjmat[row, col] - kin[row]*kout[col]/(2*m))*values[row]*values[col]
var += adjmat[row, col]*values[row]**2 - (kin[row]*kout[col]/(2*m))*values[row]*values[col]
r = covar/var
return r
One very common scalar assortativity coefficient is measuring assortativity by degree. There are more clever ways to use the graph structure to compute this, but I'll stick with the above algorithm for now.
In [ ]:
assortativity_scalar(karate_adjmat, karate.degree())
How can we be sure of the validity of an assortativity measurement?
In this model, we assume that every edge has independent probabilty of existing, where the probabilty of an edge between two nodes is related (somehow) to thier individual characteristics (this formulation of a network leads to the idea of the Stochastic Block Model). By assuming every edge in independent, we can ask the question "how much does this measurement change with a small perturbation in the graph structure?" Using small perturbation = removing one edge, calculate the expected standard deviation of assortativity as:
$$ \sigma_r^2 = \sum^M_{i=1}(r_i - r)^2 $$where $r_i$ is the value of $r$ in which the $i$th edge is removed.
This is not the most efficient way to make an error measurement here (on a graph with more than a hundred or so nodes, it takes ages), but it is the most intuitive.
In [ ]:
def assortativity_error(adjmat, labels, directed, assortativity_function):
(i, j) = adjmat.shape
# list of all of the edges as positions in the adjmat
# make sure not to double-count edges if the network is not directed
edges= []
for x in xrange(0,i):
for y in xrange(0,j):
if adjmat[x,y] != 0:
if directed:
edges.append((x,y))
if not directed:
edges.append(tuple(sorted([x,y])))
if not directed:
edges = list(set(edges))
# original assortativity r
r = assortativity_function(adjmat, labels)
sigma = 0
# remove one edge at a time, and compute assortativity
for edge in edges:
adjmat[edge] = 0
sigma += (assortativity_function(adjmat, labels) - r)**2
adjmat[edge] = 1
return sigma
In [ ]:
assortativity_error(UKfaculty_adjmat, UKfaculty_labels, True, assortativity)
How can we find sets of nodes that are more tightly (structurally) associated than average? Once we have defined modularity, how do we use it to determine tightly clustered nodes?
Reference: Modularity and Community Structure in Networks by MEJ Newman, Finding Community Structure in Very Large Networks by Clauset, Newman and Moore
The answer: by finding the partitions (labelings) of nodes in the graph that maximizes modularity (minimizes out-group edges, maximizes in-group edges). Often those partitions are called communities in the graph.
There are many implementations of algorithms to maximize modularity, but most rely on greedy aglomerative methods of grouping nodes. Known as the CNM algorithm, or a fast-greedy method for modularity maximization, the algortithm essentially does the following:
I won't implemet the algortithm here, I will just show an example from the igraph python library.
You can actually find a few more examples of using igraph community-detection algortihms in network-igraph-101
In [ ]:
# Make the dendrogram according the fast-greedy aglomerative algorithm
karate_dendrogram = karate.community_fastgreedy()
# Find the community partitions that maximize modularity
karate_communities_opt = karate_dendrogram.as_clustering()
i = 0
for community in karate_communities_opt:
i += 1
for v in community:
karate.vs[v]["karate_communities_opt"] = i
# Find the maximal-modularity 2-division (cheating: we are looking for 2 factions because we know this graph)
karate_communities_2 = karate_dendrogram.as_clustering(2)
i = 0
for community in karate_communities_2:
i += 1
for v in community:
karate.vs[v]["karate_communities_2"] = i
# Show the dendrogram
igraph.plot(karate_dendrogram)
# Or just open the PNG
#Image(filename="karate_dendrogram.png", width=600)
The optimal modularity community assignment
In [ ]:
# shapes = "Faction" in the social network
# colors = community assigned by the algorithm
igraph.plot(karate, vertex_color = [color_dict[x] for x in karate.vs["karate_communities_opt"]])
# Or the PNG
#Image(filename="karate_comms_3.png", width=600)
The 2-community grouping
In [ ]:
# shapes = "Faction" in the social network
# colors = community assigned by the algorithm
igraph.plot(karate, vertex_color = [color_dict[x] for x in karate.vs["karate_communities_2"]])
#Image(filename="karate_comms_2.png", width=600)
Just for fun, let's draw the UKfaculty graph too. I won't show the dendrogram though: too many nodes.
In [ ]:
# This algorithm only takes undirected graphs, so we get to use some graph manipulation tools from earlier
UKfaculty_undirected = UKfaculty.copy()
UKfaculty_undirected.to_undirected(mode = "collapse", combine_edges = {'weight': sum})
UKfaculty_dendrogram = UKfaculty_undirected.community_fastgreedy(weights = 'weight')
# you can set the number of communities by setting n =
# UKfaculty_communities = UKfaculty_dendrogram.as_clustering(n = 4)
UKfaculty_communities = UKfaculty_dendrogram.as_clustering()
i = 0
for community in UKfaculty_communities:
i += 1
for v in community:
UKfaculty.vs[v]["UKfaculty_communities"] = i
igraph.plot(UKfaculty, vertex_color = [color_dict[x] for x in UKfaculty.vs["UKfaculty_communities"]])
# or PNG
#Image(filename="UKfaculty_comms.png", width=600)
The real world is messy!
Reference: Resolution Limit in Community Detection by Fortunato and Barthélemy
In [ ]:
ring = igraph.Graph.Ring(36)
ring_adjmat = np.matrix([x for x in ring.get_adjacency()])
igraph.plot(ring)
In [ ]:
# Make the dendrogram according the fast-greedy aglomerative algorithm
ring_dendrogram = ring.community_fastgreedy()
# Find the community partitions that maximize modularity
ring_communities = ring_dendrogram.as_clustering()
i = 0
for community in ring_communities:
i += 1
for v in community:
ring.vs[v]["community"] = i
# Show the dendrogram
igraph.plot(ring_dendrogram)
In [ ]:
igraph.plot(ring, vertex_color = [color_dict[x] for x in ring.vs["community"]])
The modularity-maximization community detection algortihm just found communities in a graph where every vertex is identical. What gives?
It turns out that there is a natural "resolution limit" for modularity measurements--the concept of maximizing modularity can never resolve communities that are less than some characteristic fraction of the size of the entire network. Let's derive things.
Focusing on an undirected network (because things are complicated enough already), recall modularity: $$Q = \frac{1}{2m}\sum_{ij}\left(A_{ij} - \frac{k_ik_j}{2m}\right)\delta(c_i, c_j)$$ $$ = \sum_{ij}\left(\frac{A_{ij}}{2m}\right)\delta(c_i, c_j) - \sum_{ij}\left(\frac{k_ik_j}{(2m)^2}\right)\delta(c_i, c_j) $$ Now say that there are $P$ total partitions, corresponding to $c = 1,2,3,...P$. The terms of the sum are only non-zero when $c_i = c_j$, so split the sum up by partition, $c$, each time considering only nodes in the partition $c$: $$ = \sum_{c=1}^P \left( \sum_{ij, c_i = c_j = c}\left(\frac{A_{ij}}{2m}\right) - \sum_{ij, c_i = c_j = c}\left(\frac{k_ik_j}{(2m)^2}\right) \right) $$
Then $\sum_{ij, c_i = c_j = c}A_{ij}$ is simply equal to the total number of edges inside the partition where $c_i=c_j=c$, times 2 because we count $A_{ij}$ and $A_{ji}$ call the value $=2m_c$.
$$ = \sum_{c=1}^P \left( \frac{m_c}{m}- \frac{1}{(2m)^2}\sum_{ij, c_i = c_j = c}k_ik_j\right) $$And some algebra can show that $\sum_{ij, c_i = c_j = c}k_ik_j = \left(\sum_{ij, c_i = c}k_i\right)^2$. Call $\sum_{ij, c_i = c}k_i = K_c$, the total degree of all of the nodes in partition $c$.
(If you don't believe me, write out the simple case: $i,j = 1,2$, then $\sum_{ij}k_ik_j = k_1^2 + 2k_1k_2 + k_2^2 = (k_1 + k_2)^2 = \left(\sum_{ij}k_i\right)^2 $)
So:
$$ Q = \sum_{c=1}^P \left( \frac{m_c}{m}- \left(\frac{K_c}{2m}\right)^2 \right) $$Each term in the sum corresponds to a partition, and the term is positive (the partition makes a positive contribution to the total modularity of the graph) if $ \frac{m_c}{m}- \left(\frac{K_c}{2m}\right)^2 > 0 $.
$K_c = = 2m_c + m_c^{out}$ (in summing the degrees of the nodes, each in-community edge gets counted twice), where again $m_c$ is the total number of edges inside the community and $m_c^{out}$ is the total number of edges connecting the community to the rest of the graph.
$$ Q = \sum_{c=1}^P \left( \frac{m_c}{m}- \left(\frac{2m_c + m_c^{out}}{2m}\right)^2 \right) $$Now consider the ring graph, or a more general ring graph where each node in the graph shown above is its own connected community. Assuming a fully connected graph, these communities each have the minimum number of out-connections, $m_c^{out} =2$, and with the minumal number of out-connections, should be maximally modular. For this graph:
$$ Q = \sum_{c=1}^P \left( \frac{m_c}{m}- \left(\frac{2m_c + 2}{2m}\right)^2 \right) = \sum_{c=1}^P \left( \frac{m_c}{m}- \left(\frac{m_c + 1}{m}\right)^2 \right)$$And also on the ring graph, the total number of between-community edges is equal to the total number of partitions $P$, so $\sum_{c=1}^P m_c = m - P$
$$ Q = \frac{m - P}{m} - \sum_{c=1}^P \left(\frac{m_c + 1}{m}\right)^2 $$Assuming a connected graph (all modules have at least 1 out-link) and given a constant total number of edges $m$, the above expression for $Q$ is maximized when each community has the same number of internal links $m_c = m/P - 1$ (a more rigorous demonstration of this is in the paper, but it should make intuitive sense). Then:
$$ Q_{max} = \frac{m - P}{m} - P\left(\frac{\frac{m}{P} - 1+ 1}{m}\right)^2 = 1 - \frac{P}{m} - P\left(\frac{1}{P}\right)^2 = 1 - \frac{P}{m} - \frac{1}{P}$$
In [ ]:
P = range(1,400)
m = 400
Qmax = [1-(p/m)-(1/p) for p in P]
plt.plot(P, Qmax)
plt.title("Maximal modularity on a constructed ring graph with 400 nodes")
plt.xlabel("Number of modules")
plt.ylabel("Modularity Q")
ylim = plt.ylim([-1,1])
Now find the maximum $Q$ of this maximally modular network in terms of the number of modules (number of partitions $P$). Find $\frac{\delta Q_{max}}{\delta P} = -\frac{1}{m} + \frac{1}{P^2} = 0$ at $P = \sqrt{m}$
The maximal number of partitions $P$ is $\sqrt{m}$.
Then, assuming that the communities are connected and since we have $m$ edges in the network, only $P$ out-community edges, and the modules have the same number of edges, each community must have $m_c = \sqrt{m} - 1$ in-community edges. Assuming that the communities are connected subgraphs, $m_c = \sqrt{m} - 1$ in-edges can connect at most $\sqrt{m}$ nodes.
The maximum number of nodes per maximal-modularity partition is $\sqrt{m}$.
This means that modularity maximization cannot resolve communities where the number of communities in the graph is greater than the square root of the number of edges in the graph, $\sqrt{m}$.
Conclusion (from Resolution Limit in Community Detection): Communities found using a modularity-maximization strategy with a size $m_c \approx \sqrt{2m}$ or smaller may be the result of an arbitrary merge of similar smaller structures.
Revisit the ring graph.
In [ ]:
# Example:
myPartition1 = [1,1,1,1,1,1,
2,2,2,2,2,2,
3,3,3,3,3,3,
4,4,4,4,4,4,
5,5,5,5,5,5,
6,6,6,6,6,6]
print "Modularity for 6 (sqrt(36)) evenly sized groups: {}".format(modularity(ring_adjmat, myPartition1))
myPartition2 = [1 for x in range(0,36)]
print "Modularity for 1 large partition: {}".format(modularity(ring_adjmat, myPartition2))
myPartition3 = range(0,36)
print "Modularity for 36 partitions: {}".format(modularity(ring_adjmat, myPartition3))
Anyway, that's about it. When modularity works, when it doesn't, and how to use it. Modularity and assortativity remain some of the most-used metrics in network science, especially when we are talking about social networks and community detection. Many, many papers use the output of a CNM (the fast-greedy aglomerative modularity maximization algorithm discussed here) as groud-truth when partitioning networks into communities. It is convenient, relatively fast (as fast as anything seraching a space of the size of the nth Bell number can be), and common enough that you can find an implementation somewhere (I chose igraph). It isn't necessarily wrong, but there are always caveats.