Lancichinetti-Fortunato-Radicchi generators

[fcdimitr]

Hello! This pull request adds support for generating Lancichinetti-Fortunato-Radicchi graphs.

The function calls the C/C++ generators implemented by the original authors.

[simonschoelly]

Thanks, while such graphs could certainly be interesting, we try to keep the number of dependencies of this package as low as possible. Therefore the only way I see here is either:

• Implement all algorithms with Julia
• Add these algorithms to an other package that uses Graphs.jl as a dependency. Such a package can as well be in the JuliaGraphs Github project - either in a new one or by adding it to an existing package. In theory, LightGraphsExtras.jl would be an ideal package - but unfortunately that one is not really maintained at the moment, and might not even work.

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 94.87179% with 2 lines in your changes are missing coverage. Please review.

Project coverage is 97.21%. Comparing base (7133460) to head (5b8572b).

Files	Patch %	Lines
src/SimpleGraphs/generators/randgraphs.jl	94.87%	2 Missing :warning:

Additional details and impacted files

@@            Coverage Diff             @@
##           master     #345      +/-   ##
==========================================
- Coverage   97.28%   97.21%   -0.08%     
==========================================
  Files         115      115              
  Lines        6789     6819      +30     
==========================================
+ Hits         6605     6629      +24     
- Misses        184      190       +6     

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[fcdimitr]

Thank you, @simonschoelly. If I understand correctly, I could create a new package under the JuliaGraphs project, named LFRBenchmarks, for example, and move the codes to that package. How can I prepare and create a new repository under the JuliaGraphs project/organization? Do I need to coordinate with a maintainer?

[simonschoelly]

I think we probably would need to set it up for you, if you wish so.

But maybe it would make sense if we would instead create a package GraphsExtra.jl (or GraphsExtras.jl) for you and then you could push your code there? In the future we can then port some of the code there to Graphs.jl using extensions - but we cannot do that as long as we try to support Julia v1.6.

And eventually we can also carry over some of the code from LightGraphsExtras.jl

What do you think about that? Also quickly checking with @gdalle or anyone else who has an opinion on that.

Btw. your code does not run Julia v1.6 right now.

[fcdimitr]

I saw the "Graphs community calls" in Discourse. There is a meeting this Thursday. I can join, and maybe I can also contribute some other functions/packages that I have developed? Perhaps this is the easiest way to coordinate the best course of action for this "extra" functionality.

Regarding v1.6, I am using the redirect_stdio, which was not available. I can easily switch to redirect_stdout and redirect_stderr. I will make the changes when we migrate this function to the correct package 😄

Thank you!

[gdalle]

Thanks for the ping @simonschoelly :) I definitely agree that Graphs.jl should not take on more dependencies, especially for very specific algorithms.

My recommendation would be to reimplement the LFR sampling procedure in Julia: a quick look at the wikipedia article tells me this should be feasible. I understand the temptation to wrap the original code, but given how it is presented on the authors' website (downloadable archives, not even a repo), I have severe doubts about long term maintenance and reliability. IIRC, there were similar issues with GraphsMatching.jl because it uses an unmaintained wrapper of the Blossom algorithm, where the original implementation is hosted on the author's personal website.

Doing everything in pure Julia is a bit of a hassle at first, but it will make maintenance significantly easier in the future. If you agree to do this, we can definitely help you! Just expect the usual delay in PR review, none of us have lots of time to give JuliaGraphs at the moment.

[gdalle]

There is a meeting this Thursday. I can join, and maybe I can also contribute some other functions/packages that I have developed?

By all means @fcdimitr, you're welcome to join! Excited to meet new contributors. All the info is on the Julia community calendar as well.

[gdalle]

maybe it would make sense if we would instead create a package GraphsExtra.jl (or GraphsExtras.jl) for you and then you could push your code there?

The Graphs.jl already contains various graph generation utilities like ER or SBM, so semantically I think it makes sense to put LFR (in pure Julia) with this bunch.

More generally, the LightGraphsExtras.jl repo was a weird collection of unrelated utilities. Just like I'm trying to move flow and matching code back into Graphs.jl or GraphsOptim.jl, I would love to archive these "extras", or possibly find them a better name

[fcdimitr]

There is a meeting this Thursday. I can join, and maybe I can also contribute some other functions/packages that I have developed?

By all means @fcdimitr, you're welcome to join! Excited to meet new contributors. All the info is on the Julia community calendar as well.

Thank you @gdalle! This functionality was a side-project that emerged while developing some community detection packages in Julia. It makes perfect sense to translate the implementation in pure Julia. I was thinking that until I finish the translation, I could share the wrapper to the C/C++ implementation as a point of comparison.

I can discuss more about it in the meeting and also discuss some other Julia graph analysis packages we have developed over the past couple of years. I would love to be able to contribute additional functionality to community detection and structure identification in networks!

[simonschoelly]

maybe it would make sense if we would instead create a package GraphsExtra.jl (or GraphsExtras.jl) for you and then you could push your code there?

The Graphs.jl already contains various graph generation utilities like ER or SBM, so semantically I think it makes sense to put LFR (in pure Julia) with this bunch.

More generally, the LightGraphsExtras.jl repo was a weird collection of unrelated utilities. Just like I'm trying to move flow and matching code back into Graphs.jl or GraphsOptim.jl, I would love to archive these "extras", or possibly find them a better name

I don't think extra is that weird of a name - people use that fairly often do specify "extra" dependencies. The main reason why we don't have GraphExtras.jl at the moment is that I did not find enough time to get the JuMP dependencies in LightGraphsExtras.jl working. And as mentioned above, in the future we might use the extra dependency mechanism introduced in Julia 1.9.

While I would not say, that we should not wrap code written in other languages (especially if its not in the main Graphs.jl repo) I agree that downloading archives is not something that we should strive for. So I think some kind of repo + clear versioning + clear open source license is something that we should require of all dependencies in the main Julia branch.

And if it is easy, a clear Julia version is of course preferred and then can also life in Graphs.jl - the main issue I see at the moment, is that we won't find much time to review the code - so if it is a non-trivial new algorithm then they often get stuck unmerged for months.

My suggestion here, is to add a Contrib submodule where we have some relaxed standards - but let me outline that in a new issue.

[gdalle]

If there are JuMP dependencies in LightGraphsExtras, can we maybe move those to GraphsOptim? I haven't yet found time to clean it up and register it but I could

[fcdimitr]

As per our discussion, I moved these functions to https://github.com/fcdimitr/LFRBenchmarkGraphs.jl and registered the package https://github.com/JuliaRegistries/General/pull/102043. I am closing this issue. I will reopen it when I have the Julia version of the generators ready for review. Thank you!