Clustering stochastic block model graphs

[agosztolai]

Hello,

thanks for developing this interesting algorithm!

I'm trying to use your algorithm to cluster stochastic blockmodel graphs, so far with little success.

I used this networkx function to generate the SBM. The parameters are set suck that the average degree is approx. 3.

G = nx.planted_partition_graph(2, 500, 0.00596, 4e-05)

Following your tutorial .ipynb, I do the following to compute the Ricci flow

ricci_flow = OllivierRicci(G,alpha=0.5)
ricci_flow.compute_ricci_flow(iterations=100)

and finally

cc = ricci_flow.ricci_community()

to obtain the clusters.

However, the results I got are not so nice.

Could you please advise me on how to increase the accuracy? Alternatively, could you please share the script you used to generate the SBM results in your paper?

Thanks very much!

[saibalmars]

Hi,

Thanks for your question.
Up to my knowledge, SBM for low intra-community link probability (0.00596 in your case) is very hard to detect for most modularity-based/ community density-based algorithms like ours and Louvain. In our paper, the SBM model is with p_intra=0.15 to make it work.

This is mostly due to the fact that the community graphs SBM create don't come with some known community properties such as small world or preferential attachment (power-law degree distribution/long tail degree distribution). Without these properties, the communities created by SBM don't really come with a "core", which led to high graph diameter and hence hard to be capture by density-based algorithms. In the attached image, I created an SBM graph with your setting (nx.planted_partition_graph(2, 500, 0.00596, 4e-05)) and do 20 iterations of Ricci flow with the default setting. Then remove all edges with weight greater than 1.3. You can see that because there is no core in the graph, what we extract via Ricci flow here is nothing but a long chain, and that's the reason we cannot get a good result in here yet. Because of the reason above, we mainly use LFR model graph to create artificial community graphs.

Let me know if you have more questions, I'm happy to discuss more offline.

[agosztolai]

Hi Chien-Chun, Thanks for the clarification! Yes, I was knowingly pushing the limits of your method because I’m very interested in sparse graphs. We have a paper out (https://www.researchgate.net/publication/349213242_Unfolding_the_multiscale_structure_of_networks_with_dynamical_Ollivier-Ricci_curvature <https://www.researchgate.net/publication/349213242_Unfolding_the_multiscale_structure_of_networks_with_dynamical_Ollivier-Ricci_curvature>), which focuses on community detection in sparse graphs using an extension of the OR curvature with diffusion processes. It is currently under review and I want to make sure that I give a fair comparison with your method. Best wishes, Adam

…

On 19 Apr 2021, at 00:52, Chien-Chun Ni ***@***.***> wrote: Hi, Thanks for your question. Up to my knowledge, SBM for low intra community link probability (0.00596 in your case) is very hard to detect for most of modularity based/ community density based algorithm like ours and louvian. In our paper, the SBM model is with p_intra=0.15 to make it work. This is mostly due to the fact that the community graphs SBM create doesn't come with the some known community properties such as small world <https://en.wikipedia.org/wiki/Small-world_network> or preferential attachment <https://en.wikipedia.org/wiki/Preferential_attachment> (power-law degree distribution/long tail degree distribution). Without these property, the communities created by SBM doens't really comes with a "core", which led to high graph diameter and hence hard to be capture by density based algorithms. In the attached image, I created a SBM graph with your setting (nx.planted_partition_graph(2, 500, 0.00596, 4e-05)) and do 20 iterations of Ricci flow with the default setting. Then remove all edges with weight greater than 1.3. You can see that because there is no core in the graph, what we extract via ricci flow here is nothing but a long chain, and that's the reason we cannot get a good result in here yet. Because of the reason above, we mainly use LFR model graph <https://networkx.org/documentation/stable/reference/generated/networkx.generators.community.LFR_benchmark_graph.html> to create artifitial community graphs. <https://user-images.githubusercontent.com/4888846/115162534-e84f2800-a058-11eb-83d1-942739852d7a.png> Let me know if you have more question, I'm happy to discuss more offline. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#23 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AK6WK5HZ4DCCSB2LGMENPQDTJNPEBANCNFSM43BZFOOA>.