Plot dendrogram of community reconstruction on a graph

[Francesco Bonacina]

Hi all!

I'm Francesco, I'm physics student.  I'm working on my master thesis project on network theory.

One issue of my project was to plot dendrograms from community reconstruction performed on graphs. So I implemented few functions to accomplish this, starting from partitions detected by Girvan-Newman function.

The Girvan–Newman algorithm detects communities by progressively removing edges from the original graph. So it exposes the binary tree associated with the divisive process of community reconstruction, which can be depicted as a dendrogram.

Usually the `scipy.cluster.hierarchy.dendrogram` function is used to draw dendrograms. It receives in input a matrix which encodes the hierarchical clustering to be rendered as a dendrogram. For many cases it is enough to have this matrix generated by the `scipy.cluster.hierarchy.linkage` function, but not so, for example, in graph community detection.

My module, `dendrogram_from_gn.py`, provides functions that generate a matrix of this type (I named it `agglomerative matrix`) starting from the community reconstruction of a graph, performed with the 'girvan_newman' function  from 'networkx.algorithms.community.centrality'. The `agglomerative matrix` is suitable to be taken in input by the 'scipy.cluster.hierarchy.dendrogram()' function. The module is mainly based on networkx, but it uses also `community_louvain.modularity` from `community` to compute the modularity of the graph partitions and possibly select the optimal partitioning.

Here's a github repo with a description and a proof-of-work of this module: https://github.com/FrancescoBonacina/dendrogram_girvan-newman/blob/master/README.md

I'm writing you to ask for feedback & tips on my work and to learn the proper way of merging my module with the `networkx` master code. 

Thank you all!

Francesco Bonacina

------------------------

Indirizzo istituzionale di posta elettronica degli studenti e dei laureati dell'Università degli Studi di Torino

Official University of Turin email address for students and graduates 

[Dan Schult]

Thank you for this code and your message.

The process for moving your code to be included in the main NetworkX code base consists of you cloning the main repository, putting your code into the networkx/algorithms/community/<somename.py> module. Then make sure it plays nicely with existing functions (like girvan_newman for example). And tests are needed in the tests folder. Documentation is automatically generated from your doc_strings if you add pointers in the doc/reference/algorithms/community.rst file.  You should think about function names -- abbreviations like gn_stuff should probably be written out fully, or maybe changed so the whole ecosystem of functions are clearly delineated. The first line of the doc_string should be one line followed by a blank line and then a paragraph (couple sentences) with the rest of the info.  This short first line is very helpful to describe the function in our automatically created lists of available functions.

Then create a pull request and we'll go from there. 

:)

Dan

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/5627348c-c035-4eaa-b603-6a8dd0a76f7c%40googlegroups.com.

[Francesco Bonacina]

Hi!

Thank you Dan for your answer and you suggestions.

Few hours ago I did my Pull Request, but, as I wrote in the PR message, my code is not ready to be merged yet. In particular I need for some other advice:

1) I ask for reviews of the code of my module 'dendrogram_from_girvan_newman' in network/algorithms/community .

2) I added pointers in the doc/reference/algorithms/community.rst file to automatically generate the documentation, but I'm not sure I did it correctly. I wasn't able to find guidelines for this.

3) I have not yet implemented the tests in the networkx/algorithms/community/tests folder. I'm asking for guidance: I've never used 'pytest' and I'm also not sure what I should test. In addition to checking if my functions work properly, should I add tests to check if the inputs are as I expect them to be? Should I check, for example, that a dictionary that is passed as input to a function has the right format?

Is there a detailed guide that explains how to implement the tests?

Thanks in advance for your help!

Francesco Bonacina

P.S. After the first PR I made some changes to be consistent with PEP8. Now I hope my code it's fine regarding that.

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/CA%2BXMcTNjVV33NouV00gSz0yTeYFz8WuTNUC2TmxBcO1DEFhVeQ%40mail.gmail.com.