Master Thesis: Research on time varying networks
My first step into research started with my Master’s thesis (2016-2017) on large time-varying networks with Prof. Jean-Charles Delvenne.
- Antoine Aspeel. Community Detection in Large-Scale Time-Varying Networks, A Modularity Based Approach, 2017
In my Master’s thesis, we developed fast optimization methods for community detection in time-varying graphs, that is, graphs where nodes and edges are added and removed. This work led to the following publications in SIAM journals:
Michaël Fanuel, Antoine Aspeel, Michael T Schaub, Jean-Charles Delvenne. Ellipsoidal embeddings of graphs. SIAM Journal on Applied Mathematics, 2024.
Michaël Fanuel, Antoine Aspeel, Jean-Charles Delvenne, and Johan AK Suykens. Positive semi-definite embedding for dimensionality reduction and out-of-sample extensions. SIAM Journal on Mathematics of Data Science, 2022.
A common paradigm for community detection is to find a partition of the nodes that maximizes the modularity, a measure of the quality of the partition with respect to the graph structure [1].
The Louvain method has been proposed as an efficient heuristic to maximize modularity [2]. It proceeds by creating a hierarchical community structure: nodes are grouped into communities, and communities are grouped into communities-of-communities, etc. While offering computational benefits, the Louvain method and its hierarchical structure are not well-suited for time-varying graphs.
Challenge: Classical community detection methods, such as the Louvain algorithm, are not well-suited for time-varying graphs. When the graph changes, these methods require recalculating the community structure from scratch, failing to leverage previous computations to adapt efficiently to the changes.
Solution: To face this issue, the method I developed in my Master’s thesis is based on graph embedding, where each node of the graph is associated with a point on a $(r-1)$-dimensional sphere $\mathbb{S}^{r-1}\subset\mathbb{R}^r$. Then, modularity maximization is relaxed into a smooth optimization problem over the sphere. The manifold structure of the sphere allows to use efficient methods for constrained optimization [3]. Then, the community structure of the graph is obtained by clustering the points on the sphere using the $k$-means algorithm.
A key advantage of our embed-and-partition approach is its adaptability to time-varying graphs. When the graph undergoes changes, the existing embedding can serve as a warm start for the iterative optimization process, significantly reducing computational time.
Embeddings are low dimensional
A natural question that arises when using our method is how to choose the embedding dimension $r$ for the sphere $\mathbb{S}^{r-1}$. Indeed, this is a user-defined parameter with no a priori upper bound. In addition, using a large $r$ increases the dimension of the optimization problem, leading to more computation time.
However, numerical demonstrations show that the optimal embedding is often very low dimensional, allowing one to choose a small value for the embedding dimension $r$ without compromising the quality of the solution (see figures below). We have been able to provide a theoretical explanation to the low dimensionality of the embeddings. Indeed, we proved that the optimization problem we are solving to find the graph embedding is equivalent to a nuclear norm minimization subject to linear constraints. Since the nuclear norm is the tightest convex relaxation of the rank [4], it promotes low rank solutions which correspond to low-dimensional embeddings. This finding provides theoretical support for the use of low-dimensional embeddings, resulting in significant reductions in computation time.
References
[1] M. E. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Physical review E, vol. 69, no. 2, p. 026 113, 2004.
[2] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” Journal of statistical mechanics: theory and experiment, vol. 2008, no. 10, P10008, 2008.
[3] P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization algorithms on matrix manifolds. Princeton University Press, 2008.
[4] M. Fazel, H. Hindi, and S. P. Boyd, “A rank minimization heuristic with application to minimum order system approximation,” in Proceedings of the 2001 American Control Conference., IEEE, vol. 6, 2001, pp. 4734–4739.