The Joint Lab
Laurent Hébert-Dufresne (LHD) and I recently joined forces and created the Joint Lab — a collaborative exploration across sciences with models and data. It combines the strength of the Laboratory for Structure and Dynamics, led by LHD, and the Complex Data Laboratory, led by myself. We are a big group of researchers with a like-minded approach to complex systems research and data science. And we now have a shinny new website, created in Gatsby by Edward Laurence! Check it out for a list of our latest publications and artifacts, an overview of our team, and job opportunities.
FOSS award at MSR 2021
Our paper “Which contributions count? Analysis of attribution in open source” has won the FOSS award at the 2021 Mining Software Repositories (MSR) conference. The award recognizes papers that show outstanding contributions to the FOSS community. The paper examines the various ways in which people are given credit for their work on Open Source Software, and identifies areas where existing methods of attribution could be improved. This is a huge honor, as it is my first time attending the MSR conference. Many thanks to my awesome collaborators who helped bring this project to life, it truly is a team effort. PS: We also wrote a short op-ed in Nature Computational Sciences a few months back, highlighting some of those problems. Our MSR paper is a continuation of this work.
Tenure track appointment
Big news. I will become an assistant professor at the University of Vermont starting this fall! My primary appointment will be with the Department of Mathematics and Statistics with a joint appointment at the Larner College of Medicine, where I will join the modeling team of the Translational Global Infectious Diseases Research Center (TGIR). I’m also staying on the faculty of the Vermont Complex Systems Center to work with all the fine folks over there, as well as on the faculty of the Computer Science department (secondary appointment). Quite a mouthful!
I will be looking to hire soon, so stay tuned.
Overdue announcement: I am joining the University of Vermont as a Research Assistant Professor to help out with the OCEAN initiative, in collaboration with Google Open Source My primary affiliation will be the Department of Computer Science, and I am also joining the Vermont Complex Systems Center. I am looking forward to many awesome projects with the outstanding faculty and students of UVM!
Big review published in Physics Reports
Our review of higher-order approaches to network science is finally out as Volume 874 of Physics Reports (freely accessible to all). It is the fruit of an extensive (800+ references) collaborative effort led by Federico Battiston and Giovanni Petri. If you want the TL;DR, Iacopo Iacopini wrote an excellent summary of the review that can be found here Needless to say that the field is teeming with exciting ideas and that it was a treat to survey them and their precursors, going decades back.
New Letter in Nature Physics
Laurent Hébert-Dufrense, Samuel Scarpino, and I just published a letter where we argue that interacting contagions look like complex contagions. Sune Lehmann wrote a great perspective piece that explains our work and its implication really well. In a nutshell, we show that one can’t use macroscopic patterns to prove that a contagion is “complex” — simpler mechanistic explanations, like interacting simple contagions, give rise to the same patterns. The upshot is that models of complex contagions are much more tractable than the corresponding models of interacting contagions. Hence, our mapping provides a tractable method to fit models of interacting contagion, and a characterization of their complexity. I have made all the code, slides and material available online; see the following link!
Manuscript published in PRX
I want to highlight the recent publication of “Phase transition in the recoverability of network history” in the open-access journal Physical Review X. In this paper, we look at how to infer the past state of a statically observed growing network; we also uncover a phase transition for the quality of the recovered history, governed by the strength of a rich-get-richer mechanism. When the degree distribution becomes too skewed, we find evidence that past state reconstruction becomes impossible.
The project has been a long time in the making; the Dynamica Lab started working on this project back in 2016 at a retreat (see a picture of the retreat after the break!). The product of our work first appeared as a preprint in 2018, and has significantly changed since: follow the link to take a look at what it became! Enormous thanks should go to the anonymous reviewers for their input that helped shape the manuscript. Details about where to find code, slides, and supplementary information are listed in my publication page.
PS: We already followed up on this work, together with Georce T. Cantwell at the University of Michigan, and Guillaume St-Onge at the Dynamica Labs. In the “sequel,” we derive an efficient and exact recovery algorithm for the past state of growing trees. By limiting ourselves to this special class of networks, we obtain a significant efficiency improvement on the algorithm used in the PRX paper, which relied on a state-of-the-art but costly sequential Monte-Carlo sampling method. Our manuscript is currently on the arXiv as a preprint.
I’m going to attend NetSciX 2020 in Tokyo, to present joint work with Mark Newman and George Cantwell. We have developed a method to automatically and efficiently infer the structure of a network from noisy pairwise observations — we will post an accompanying paper at some point in the future. A proceedings in which I appear as a co-author has also been accepted. It is titled “Connected graphs with a given degree sequence: efficient sampling, correlations, community detection and robustness”, and it is joint work with John Ring and Laurent Hébert-Dufresne. Come and see us!
I will give a few presentations at NetSci 2019 and at the surrounding events. First, I’ve been asked to kick off the SYNS 2019 Pre-Conference Event “I’d like to learn from…” with an overview of Universality of the SBM. This will be a fun laid-back event on Sunday right before the satellites. I’ll then give a flash talk at SINM 2019, in which I’ll present exciting new work on epidemiology that I’ve been doing with Laurent Hébert-Dufresne and Samuel Scarpino. I’ll close out the week with a talk on Friday at the main event, where I’ll discuss of “Compression of treelike complex networks using layered configuration models” (joint work with Antoine Allard and Laurent Hébert-Dufresne). Mark Newman will also touch on some work we’ve done together, in his SINM contributed talk.
Open NetSci Hackathon
I will be co-chairing the first Open NetSci Hackathon with Alice Patania. Our goal is to hold a fun, laid back warm-up event before the flagship NetSci conference. We’re already two months out and hope to see you all there. The line-up of experts is beyond amazing.
PhD defense : check
I have successfully defended my thesis yesterday. So it is now official: I am a PhD! To top it off, my thesis has been added to the Board of Honour for receiving the highest overall mark from all committee members.
This is not a well-kept secret anymore, so I should post this here as well: I’m joining the Center for the Study of Complex System at the University of Michigan as a Postdoctoral Fellow. I’m looking forward to all the new exciting projects that will come out of this.
I’ll be at NetSci 2018 (Paris) to present our recent preprint “Network archaeology: phase transition in the recoverability of network history”. The program is already out: I’m part of the Theory-I parallel session, on day 1 of the main event.
A few additions to the publication page
Two papers on which I appear as a co-author have recently been published in Physical Review E!
First, a deep cut by Guillaume St-Onge: The paper tackles SIS dynamics on time-varying networks with fixed degree sequences. By changing the relative time-scale of the epidemics and of the network’s evolution, we can effectively interpolate between quenched and annealed formalisms of SIS dynamics on networks, thereby unifying many theoretical frameworks in one. My favourite result comes towards the end of the paper, where we show that the endemic phase can be heterogeneous near its onset: If you look at high degree nodes, then you’ll find that the disease’s prevalence scales faster with the network’s size than if you had inspected low degree nodes.
Second, a fun numerical paper with Edward Laurence, Sergey Melnik and Louis J. Dubé, where we show how to exactly solve cascade dynamics on small networks. By exact, I mean that we show how to calculate the probability of every single outcome, with arbitrary precision. Our algorithm scales pretty badly—exponentially to be precise—because there are exponentially many outcomes in the first place. Still, there are a few tricks involved in reaching such a “simple” algorithm.
I should also mention that I have recently uploaded a preprint to the arXiv. This joint work with the extended Dynamica family grew out of a workshop held in 2016. Our goal was to infer the past states of a network, given its current structure as input. I’ll present this work at NetSci 2018 during the first parallel session. Comments are more than welcome!
JSMF Postdoctoral Fellowship
While it was been announced some times ago at Université Laval, I haven’t posted this news here yet. So here goes: I’m beyond thrilled to announce that I have been selected by the James S. McDonnell Foundation for their Postdoctoral Fellowship Awards in “Understanding Dynamic and Multi-scale Systems”.
I have not yet decided where I will be pursuing my postdoctoral studies, but one thing is certain: the next few years are going to be both intellectually stimulating and fun.
The shape of randomness
I’m happy to announce that the results of a fun project with Alice Patania, Giovanni Petri and Francesco Vaccarino are now available in a short paper in Physical Review E. Special thanks to the YRNCS, who funded this collaboration through their Bridge Grant initiative.
Our paper, titled “Construction of and efficient sampling from the simplicial configuration model,” builds on recent work by Owen T. Courtney and Ginestra Bianconi. More specifically, we propose an efficient and provably correct MCMC algorithm for the maximally random ensemble of simplicial complexes with given degree and dimension sequences. This algorithm comes in handy when we use simplicial complexes as an abstraction for the structure of complex systems (as has been done more and more often recently). By randomizing a simplicial complex that encodes the structure of some system X, we get to tell what connection patterns in X are explained by simple local properties (degrees and dimensions), and what patterns are surprising. In our paper, we this method to show that the homology groups of a few real-world systems are decidedly not random, and we suggest some mechanisms that could explain these differences. But one could use the method to investigate different properties.
Voter model on the adaptive SBM
In January 2016, Laurent Hébert-Dufrense, Antoine Allard, Pierre-André Noël, Eric Libby and I got together for a SFI working group, to investigate competitor dynamics on networks. Our starting point was the connection between voter models and the Moran process, and, more generally, questions about the political arena and biology. Our results are now available in a Scientific Reports paper titled “Strategic tradeoffs in competitor dynamics on adaptive networks”.
In the paper, we introduce a voter model on the adaptive SBM—the structure of the network changes depending on who’s claiming what resource. It turns out that the model can be mapped to a well-known evolutionary game theory problem. The upshot? This gives us a game-theoretical perspective on network structure. In turn, this allows us to conclude that, for example, sustaining echo chambers is not a robust and viable strategy. So instead of fostering closed communities, strive for open discourse —across boundaries.
Detectability of the SBM in Phys. Rev. E and more!
Two short news.
First, “Finite size analysis of the detectability limit of the stochastic block model” is now published in Phys. Rev. E; I’ll upload an updated version to the arXiv soon (after NetSci 2017). It is a long paper, so it was a long process. I’m glad to see it through! Our coolest results are, I believe, 1. the symmetry group of the SBM and 2. our approximation solution of the hypersurface equations. The first tells us what transformations of the parameters maintain the difficulty of the detectability/recovery problem, while the second determines the surface of constant detectability in the parameter space.
Second news: I’ll be giving an additional talk at NetSci, during the satellite sessions tomorrow (I’ve already announced this earlier on Twitter). I’ll present the Simplicial Configuration Model and some recent related work done with Alice Patania, Giovanni Petri.
Presenting at NetSci 2017
My submitted talk “Statistical mechanics of mesoscopic structure extraction” has been accepted at NetSci 2017. I will present a unifying point of view of community detection and mesoscopic structure in general, using the language of statistical mechanics. This is joint work with members of my research group, who will also present quite a few talk of their own, see this list of abstracts.
I’m now managing the content of my website with Jekyll. The rewrite took some time, but it is definitely worth it. Jekyll is much more powerful, flexible, and efficient than my previous static website generator. Not that it was exactly hard to beat—up until now, I handled my website with a buggy, incomplete, and partial module of mine called
science-static,. Back then, my goal was to learn python with a practical project, and it definitely helped. But why reinvent the wheel when you know how to drive? Out with
science-static, ìn with
jekyll. Oh, and I also took this opportunity to reskin the site.
New paper in Phys. Rev. E
My latest paper with L. Hébert-Dufresne, A. Allard and L.J. Dubé is now out in Physicial Review E.
In the paper, titled “Growing networks of overlapping communities with internal structure”, we come up with a natural and dynamical explanation of the Dunbar number, i.e., an upper bound on the number of connection that individuals can sustain in a social network. We show how this number is related to the heterogeneity of the degree distribution of nodes within communities and investigates the consequences of this explanation for networks that have a growing and overlapping community structure.
Conferences of summer 2016
Summer has officially ended: on-campus activity levels are back to normal, and classes are picking up. This means that, as usual, I can wrap-up summer conferences and announce my talks after the fact. I really ought to start advertising these before they take place…
First thing first, my collaborators and I presented many new results at Netsci 2016 (Seoul, South Korea), I personally gave two talks about my upcoming paper on the finite size analysis of the detectability limit of the stochastic block model. The first presentation was part of the Statistical Inference for Networks Models satellite (SINM), and the second presentation took place during the lightning talk plenary session—quite the experience! My long-time collaborator Laurent Hébert-Dufresne also gave a lightning talk, where he introduced our new voter model on the adaptive stochastic block model. The associated paper is currently in submission, and available on the arXiv. Two new members of Dynamica—the Université Laval research group on Complex networks—also presented at NetSci: Charles Murphy gave a talk on growing random geometric networks, and Guillaume St-Onges presented a poster on coupled growth and spreading dynamics. Finally, Alice Patania presented our work on growing simplicial complexes, developed during my stay at the ISI Foundation. Slides, papers, and more can all be found on my publications page.
I also gave a tutorial on spectral graph clustering at the “CRM 2016 Summer School on Spectral Theory and Applications”, in Québec, Canada. This summer school was targeted at graduate students beginning their Ph.D. in mathematics, physics, and applied mathematics. I produced a lot of material for the tutorial; You can head over to this page to download the slides, lecture notes, and python notebooks used during the tutorial.
Back to the fold, in time for a new paper
This year started pret-ty intensely, with a working group at the Santa Fe Institute and a month-long residency at the ISI Foundation. The dust is still settling, but a couple of exciting projects should come out of it, to be presented at NetSci 2016 and/or other conferences this upcoming summer.
I’m also happy to announce that a paper with a long history has finally been published in Physical Review E (and that it’s the Editor’s suggestion of the week)! The theory was mostly developed during Laurent Hébert-Dufresne’s time as a Ph.D. student at Université Laval (circa 2014) but has since evolved into a sounder, more comprehensive framework. In the paper, we show how preferential attachment and delayed temporal scaling in the growth of a resource lead to a scale-independent distribution of resources. It turns out that the delayed temporal scaling is strict enough to predict both the past and the present of a scale-free system, from a single snapshot of its present state. It will be interesting to see how this relatively simple mechanism can be coupled with other preferential attachment based models.
End of the year wrap-up
Between conferences, a month-long summer school, a doctoral exam and multiple papers, suffice to say that 2015 has been a crazy year. As a result, I ended up updating this website much less than expected. The Christmas break should allow me to remedy the situation. In the meantime, three papers on which I collaborated appeared in PLoS ONE and Physical Review E. Head over to my publication page for more details. Until then, happy new year!
NetSci 2015 and the SFI Complex Systems Summer School
Summer 2015 will be action-packed.
L. Hébert-Dufresne and I will be at A. Allard’s new base camp in Barcelona, during the week of May 24th. Our joint work has always been fruitful and fun, and this visit should lead to exciting new projects.
The following week, I will be attending the 2015 edition of NetSci, in Zaragoza, Spain, alongside with many current and past colleagues. This year, we are presenting two poster contributions.
The first contribution summarizes the results of a collaboration with E. Laurence, Sergey Melnik that started back in November 2014 when he visited our research group in Québec. In a nutshell, we adapted a set of iterative equations that exactly solves bond percolation on arbitrary networks to the more general cascade dynamics of James Gleeson and colleagues. Bond percolation, node percolation, and the Watts threshold model are all special cases of this approach (!).
The second contribution introduces a large class realistic of benchmark graphs for community detection. These graphs are based on the Structural Preferential Attachment principle and can take on varied structural properties depending on the choice of parameters. Stay tuned, because the source code and associated publication will be available soon.
Right as NetSci ends, I will go back to North America to attend the 2015 edition of the Complex Systems Summer School, held at the Santa Fe Institute, New Mexico, US.
Exciting times ahead!
NIPS 2014 networks workshop
Last week, E. Laurence and I attended the NIPS 2014 workshop session in Montreal, Québec, Canada.
Surya Ganguli gave an excellent talk on deep learning ideas derived from statistical physics. As a “community detection” guy, I found the Networks Science Workshop, especially interesting. Half of the invited speakers presented recent results in that area of network science.
Liza Levina introduced a overlapping spectral detection algorithm, and Cristopher Moore showed us how the ideas of statistical mechanics can be used to better understand community detection.
The accepted papers can be found on the workshop page.
M.Sc. thesis accepted
I’m thrilled to announce that my M.Sc. thesis has been accepted by the review committee, and is now officially available online. While the thesis is mostly written in French, you will find two English chapters, namely a chapter on cascading detection (see this arXiv paper), and a chapter that contains preliminary results taken from a paper that I’m currently writing with L. Hébert-Dufresne (now a James S. McDonnell Postdoctoral Fellow at the Santa Fe Institute). In that chapter, we propose that the internal structure of communities arises from the juxtaposition of two simple stochastic processes. [September 22nd, 2016 update: A much-improved version of the paper now appears in Phys. Rev. E.]