Seminar

Zoom Link

Modularity, despite known flaws, is a quality function on clusterings of networks which is commonly used in clustering algorithms. For a given graph G, each clustering of the vertices has a modularity score, with higher values taken to indicate that the clustering better captures community structure in G. The modularity of G is the maximum over all clusterings and lies in [0,1].   



Modularity redemption?: Guimerà, Sales-Pardo and Amaral discovered high modularity of the Erdős-Rényi (ER) random graph with constant average degree and suggested it stems from the random fluctuations in its edge distribution. With minor assumptions on the degree sequence we show that any graph with average degree d, has modularity at least order 1/sqrt(d) matching that in ER up to order of magnitude. These lower bounds offer a certain level of validation to modularity as a measure for community structure. Since, by these results, random graphs do, up to order of magnitude, have the minimum achievable modularity for a given density.

We relate two important notions in graph theory: expander and modularity. More precisely, we show that a graph having modularity bounded below 1 is equivalent to it having a large subgraph which is an expander. The resolution limit says that in an m-edge graph any component of size less than sqrt(2m) will not be split in any modularity optimal component (Fortunato-Barthélemy). We generalise this and show that whether or not a component is split is a function only a conductance measure on the component and the relative size of the component.

I will end with some open questions. Joint work with Vilhelm Agdur, Nina Kamčev, Baptiste Louf, Colin McDiarmid.