Interest in GSoC 2025: "Degree-Constrained Null Models Project"

Development
1

Hello igraph Community,

I’m Sunav Sunil Mattoo, a first-year student with an AI/ML background, interested in graph algorithms and network science. I am applying for GSoC 2025 and have chosen to work on the “Degree-Constrained Null Models & Graph Construction” project.

I have been exploring the existing implementations of rewire(), realize_degree_sequence(), and is_graphical() and reviewing efficient algorithms for degree-constrained graph generation. I would appreciate insights on:

:one: Key challenges-- when extending these functions.
:two: Performance bottlenecks-- in the current implementation.
:three: Graph classes-- where existing methods struggle (e.g., bipartite, acyclic).
:four: Best practices for testing & benchmarking-- new implementations.

2

Hello @sunav1411, it’s great to see your interest in this project. @Abhishek has indicated interest as well.

I suggest the following first steps towards developing your proposal:

First, familiarize yourself with the main topics of this project idea, namely graphicality testing, graph construction and degree-preserving randomization (as a means of unbiased sampling). I recommend reading the following paper, up to (but not including) section 4: Radware Bot Manager Captcha

You will need to familiarize yourself with the igraph C library and make sure you are comfortable working with it. Getting a PR merged before the application is highly recommended. I looked through the current issues and labelled easier ones with the good first issue label. Those related to the topic at hand as labelled as degseq. Please see the issue list at GitHub · Where software is built

First steps for getting started with contributions are here: Quickstart for new contributors · igraph/igraph Wiki · GitHub

Let me now answer your questions:

People who take on this challenge should have a strong interest in discrete mathematics. While the algorithms are all concise, and deceptively simple, understanding them requires some attention, and will necessitate reading some mathematics papers.

To give you a taste, have a look at the Erdős-Gallai graphicality theorem, and think for a moment about how you would check this set of inequalities in linear time: Erdős–Gallai theorem - Wikipedia Then check this (easy to read) paper for the solution: Is This for Real? Fast Graphicality Testing | IEEE Journals & Magazine | IEEE Xplore

Generally, the aim of the project is to implement existing algorithms, not to invent new ones. However, ideas for new ones are welcome as well.

An example of a graph construction performance issue is here: `realize_degree_sequence()` (Havel-Hakimi algorithm) has poor performance · Issue #2725 · igraph/igraph · GitHub

A similar issue almost certinaly affects igraph_realize_bipartite_degree_sequence().

Notice that most igraph functions have the time complexity indicated in their documentation. When this is not the case (such as with graph realization functions), part of the task is to verify complexity and check if there is a need for improvement.

Note that there are some checks which are not yet implemented, and should be implemented with an algorithm that has good complexity. We will assist with the algorithm, but the main task is writing a production quality implementation. Example: Wishlist: Is a degree sequence potentially connected? · Issue #2727 · igraph/igraph · GitHub

This is a non-exhaustive list of features that are not yet implemented:

  • Directed graph construction in igraph_realize_degree_sequence(): “largest first” and “smallest first” methods should be updated to choose the largest/smallest degree out of either in- or out-degrees (currently only one is considered)
  • Construction of undirected graphs with self-loops but no multi-edges
  • Construction of any type of directed non-simple graph
  • Test for potentially strongly and weakly connected degree sequence
  • Test for threshold sequence
  • Degree-preserving rewiring for bipartite, undirected/directed, multigraph, loopy graph cases. Only the undirected simple graph case is implemented (directed simple case is not fully correct, see igraph_rewire cannot reach all directed graphs with the same degree sequence · Issue #1456 · igraph/igraph · GitHub)
  • Degree-preserving rewiring while controlling assortativity
  • Rewiring that preserves only in-degrees or only out-degrees but not both, and keeps the graph simple.
  • Graphicality, construction and rewiring of directed acyclic graphs is a work-in-progress on our side and the literature review / algorithms are not complete yet.
  • etc.

Please see the quick start guide I linked, as well as existing benchmarks / tests. There are some “good first issues” which are purely on benchmarking. Developing benchmarks for the existing degree-based construction functions can also be a good first step.

There are already partial benchmarks for igraph_is_graphical() and igraph_degree_sequence_game().

3

Hello Mentor,

Thank you for your detailed response! I’ve started familiarizing myself with graphicality testing, graph construction, and degree-preserving randomization. I also went through some of the degseq issues and the quickstart guide.

To make meaningful progress before the proposal deadline, I wanted to ask:

  • Among the degseq issues, is there one you think would best demonstrate my understanding of the core concepts?
  • For a first contribution, should I focus on implementing a missing feature or refining an existing function for better performance?
  • Are there any particular challenges in igraph’s current implementation that you’d like contributors to explore further?

I’d love to work on something that aligns well with the project’s goals. Looking forward to your advice!

Thanks again for your support.

4

Perhaps this is a good start: `realize_degree_sequence()` (Havel-Hakimi algorithm) has poor performance · Issue #2725 · igraph/igraph · GitHub

5

Thank you for the guidance!
I have started working on the realize_degree_sequence() issue already.

To ensure I approach the solution effectively:

  • I’ll “profile the current implementation” to identify performance bottlenecks.
  • I’ll experiment with “maintaining a sorted order” throughout the process to avoid repetitive re-sorting, as suggested.
  • I’ll also run the “test cases” afterward to verify the correctness and measure performance improvements.

If I encounter any challenges or need clarification, I’ll reach out for your insights.
Looking forward to contributing to the project!

6

Hi @szhorvat and igraph team!

I’m Zara, a university student studying computer science and mathematics. Graph theory and network theory have been a huge interest of mine, so I would love to contribute something to igraph. I recently came across GSoC - hope I’m not too late to the conversation!

I’ve filled myself in on the paper linked earlier and am familiarizing myself with the library and its configuration. Once that’s set up, I’ll be looking at ‘good first issues’ and working on a contribution.

Looking forward to learning more,
Zara

7

Welcome @zara, I responded to your other question about a good first issue in another thread.

The rich club coefficient \phi is an interesting choice, as the rewiring functions that would be implemented as part of this project can serve as a null model for normalizing \phi.

8

As a general suggestion, people interested in this project should do two things to get started:

  1. Complete a contribution to the igraph C library. Ideally we’d have a PR merged (or on track to be merged soon) when you submit the application. I opened a few “good first issue” tickets, several of which won’t take too much work. Please see the list of issues. Here’s a quick-start guide as well: Quickstart for new contributors · igraph/igraph Wiki · GitHub Do let us know before you start work on an issue, so we can coordinate!

  2. Read up a bit on theory, and see if you would enjoy working on this topic: